-
Notifications
You must be signed in to change notification settings - Fork 10
Chapter 07, Designing lock free concurrent data structures
Chapter 07, Designing lock-free concurrent data structures
이 챕쳐에서는 아래 사항들을 이야기 한다.
- lock 를 사용하지 않고 concurrency 를 위하여 설계된 data structures 의 구현물
- lock free data structures 에서 memory 를 관리하는 기술
- lock free data structures 를 작성하는데 도움을 주는 간단한 가이드
전 챕터에서 동시성을 위한 자료구조를 디자인하는 일반적인 방법과 그것들을 안전하게 디자인하는것에 대한 가이드를 포함한 방법을 확인 하였다. 몇몇 공통의 자료구조를 확인 하였고 공유 데이터를 보호하기 위하여 mutex 와 lock 를 사용한 구현물의 예제에 대해서도 확인하였다. 첫 몇개의 예제는 전체의 자료구조를 보호하기 위하여 하나의 mutex 를 사용하였다 그러나 마지막에는 자료구조의 몇몇의 작은부분들을 보호하기 위하여 하나 이상의 mutex 들이 사용 되었고 이것은 자료구조를 접근하는데 보다 높은 동시성이 허용 된다. . Mutex 는 여러개의 thread 가 race condition 이나 broken invariants 를 접하지 않고 자료구조를 안전하게 접근 할수 있는 강력한 도구 이다. 그것들을 사용하는 코드의 동작에 대한 이유는 상대적으로 간단하다. data 를 보호하는 mutex 로 lock 이 존재하는 것과 그렇지 않은 코드사이에
However, it’s not all a bed of roses;
그러나 그것은...
챕터 3에서 lock 의 잘못된 사용이 어떻게 deadlock 를 발생시키지와 locking 의 범위가 진정한 동시성에 미치는 영향을 lock-based 큐 와 table lookup 하는 예제들을 통하여 확인하였다. lock없이 동시 접근에 대하여 안전한 자료구조를 작성할수 있으면 이 문제들을 피할수 있다. 그런 자료구조를 lock-free 자료구조라고 부른다. 이 챕터에서는 챕터 5에서 소개한 atomic 연산의 memory-ordering 속성이 어떻게 lock-free 자료구조를 작성하지에 대하여 알아보겠다. 그런 자료구조를 설계할때는 극도로 주의가 필요 하다. 왜나면 옳게 작성하기 힘들고 설계가 실패되는 조건이 아주 가끔 발생한다. lock-free 가 되는 자료구조가 우선을 무엇을 의미하는지에 대하여 확인하는것 부터 시작해보자. 그리고 몇몇 예제를 통하여 확인하기 전에 그것들을 사용하는 이유에 대해서 확인할것이다. 그리고 몇몇 일반적인 가이드라인에 대해 말할것이다.
mutex 나 조건변수를 사용하고, 데이터 동시화 시키는 알고리즘과 자료구조를 blocking 자료구조와 알고리즘으로 불린다. 어플리케이션은 다른 쓰레드가 수행을 완료하기 전까지 쓰레드의 실행을 멈추는 라이브리러 함수를 호출한다. 그런 라이브러리 호출은 blocking 호출이라고 한다. 쓰레드가 block 이 없어 지기 전까지 그지점을 통과해서 진행할수 없기 때문이다. 일반적으로 OS 는 다른 쓰레드의 적합한 행동으로부터 block 이 풀리기 전(mutex 을 해제 하고 조건변수를 통하여 알려주거나 future ready 로 변경을 통하여)까지는 완전히 block 된 쓰레드의 동작을 멈출것이다.
block 라이브러리 함수를 사용하지 않은 자료구조와 알고리즘은 non-blocking 이라고 말할수 있다. 그래서 다양한 타압의 non-blocking 자료구조에 대해서 살펴보자.
챕터 5로 돌아가서 스핀락으로 std::atomic_flag을 사용한 기본 mutex 를 구현하였다. 그 코드는 아래 listing 에서 다시 보여진다.
listing 7.1 Implementation of a spin-lock mutex using std::atomic_flag
class spinlock_mutex
{
std::atomic_flag flag;
public:
spinlock_mutex() : flag( ATOMIC_FLAG_INIT )
{
}
void lock()
{
while( flag.test_and_set( std::memory_order_acquire ) );
}
void unlock()
{
flag.clear( std::memory_order_release );
}
};이 코드는 어떤 block 함수도 호출하지 않는다. lock() 함수는 test_ans_set() 함수가 false 를 반환하기 전까지 반복을 유지한다. 이것이 반복문을 도는 스핀(spins)이기 때문에 spin-lock 이라는 이름의 이유이다. 어쨋든 block 호출은 없다. 그래서 공유 데이터를 보호하기 위하여 뮤텍스를 사용한 어떤 코드도 non-blocking 이다. 그렇지만 mutex가 아직 존재하고 한번에 오직 한 쓰레드에서 lock 을 잡기 때문에 이것은 lock free 는 아니다. lock free 의 정의를 확인해보고 무슨 종류의 자료구조로 해결할수 있는지 확인해보자.
lock-free 에 필요한 자료구조를 위하여 하나 이상의 쓰레드가 동시에 자료구조에 접근할수 있어야 한다. 같은 연산을 수행하는것은 가능하지 않다. lock-free 큐는 하나의 쓰레드가 push 를 하고 하나는 pop 을 할수 있다. 그러나 두 쓰레다가 동시에 새로운 아이템을 push 를 시도한다면 가능하지 않을것이다. 그것 뿐만 이나라 자료구조에 접근하는 쓰레드중 하나가 스케쥴러에 의하여 그 연산을 수행하는 도중에 정지 된다면, 다른 쓰레드는 정지된 쓰레드를 대기하지 않고 그자신의 연산을 완료할수 있어야 한다.
자료구조에 compare/exchange 연산(이후로CAS)을 사용한 알고리즘은 그것안에 반복문을 가지고 있다. CAS 연산을 사용한 이유는 다른 쓰레드가 동시에 데이터를 변경을 할수 있어야 한다. 이와 같은경우 코드는 CAS 를 시도하기 전에 그 연산의 redo 부분(연산 이전으로 되돌릴수 있는 )이 필요로 한다. 다른 쓰레드가 정지했을때 CAS 가 결국 성공한하는 코드는 lock-free 라고 할수 있다. 만약 그렇지 못하면 본질적으로 non-blocking 이지만 lock-free 가 아닌 spin lock 이다.
또 다른 쓰레드가 '잘못된' 타이밍으로 연산을 수행하려고 한다면 첫 쓰레드가 그 연산을 계속 재 시도하는 동안 다른 쓰레들이 진행을 할것이다. 그런 반복들을 가지고 있는 lock-free 알고리즘은 한 쓰레드가 계속 대기하게 되는 결과를 가지고 올수 있다. 이런 문제를 피할수 있는 자료구조는 lock-free 일 뿐만 아니라 wait-free 이다.
wait-free 자료구조는 lock-free 자료구조에서 추가적으로 자료구조에 접근하는 쓰레드가 다른 쓰레드의 행동과 무관하게 그자신의 연산을 제한된 수의 스텝안에 완료할수 있는 속성을 가지고 있다. 제한되지 않은 수의 재 시도를 하는 알고리즘은 다른 쓰레드들과의 충돌 때문에 wait-free가 아니다. Wait-free 자료구조를 올바르게 작성하는것은 아주 많이 힘들다.
In order to ensure that every thread can complete its operations within a bounded number of steps, you have to ensure that each operation can be performed in a single pass and that the steps performed by one thread don’t cause an operation on another thread to fail.
모든 쓰레드는 그자신의 연산을 제한된 수의 스텝안에 완료할수 있기 위해서는 각 연산은 single pass 안에 수행되어야 하고 한 쓰레드에 의해 수행된 스탭은 다른 쓰레드의 연산이 실패가 되면 안된다. 이것이 다양한 연산에 대한 알고리즘을 보다 더 어렵게 만든다.
Given how hard it is to get a lock-free or wait-free data structure right, 이것을 작성하기 위한 좋은 이유가 필요하다. 비용을 능가하는 이익에 대하여 확신이 필요하다.
Let’s therefore examine the points that affect the balance. 그러므로 이익과 비용의 균형을 만드는 포인트에 대해 확인해보자.
근복적으로, lock-free 자료구조를 사용하는 첫째 이유는 최대 동시성이 가능하기 때문이다. lock 기반의 컨테이너를 사용하면 한 쓰레드는 첫 쓰레드가 완료되기전에 다른 쓰레드들은 그자신들의 연산을 완료하기 위하여 대기하는 block 이 될 가능성이 언제나 있다. mutual exclusion(상호 배제)을 통하여 concurrency 를 막는 것이 mutex lock 의 전체적인 목적이다. lock free 자료구조를 사용하면 몇 쓰레드들은 매 스텝을 진행할수 있다. wait-free 자료구조를 사용하면 모든 쓰레드는 다른 쓰레드가 무엇을 하든지 상관없이 앞으로 진행할 수 있다. 대기는 필요치 않다. 이것이 가지고 있는 바람직한 속성이지만 얻기는 쉽지가 않다. 기본적으로 spin lock 으로 작성하는것은 너무 쉽다. lock free 자료구조를 사용하는 두번째 이유는 견고함(robustness) 때문이다. lock 을 잡고 있는 쓰레드가 죽는다면 자료구조는 영원히 접근할수 없다. 그러나 lock free 자료구조에서 연산중에 쓰레드가 종료되어도 쓰레드의 데이터를 제외하면 아무것도 잃을것이 없다. 다른 쓰레드는 정상적으로 진행이 가능하다. 여기에 다른면이 있다. 자료구조에 접근하는것부터 쓰레드를 제외하지 못한다면 불변성(invariants) 을 유지하거나 불변성을 유지할수 있는 대안을 확실히 해야한다. 또한 연산에 도입된 ordering 제약에 주의를 기울여야 한다. data race 와 같은 정의되지 않은 행동(undefined behavior) 를 피하기 위하여 변경 작업에는 atomic 연산을 사용하여야 한다. 그러나 이것만으로는 충분하지 않다. 이 변경점들이 맞는 순서로 다른 쓰레드들이 볼수 있도록 하여야 한다. 이러한 모든것이 lock 을 사용하지 않고 작성된 thread-safe 한 자료구조들은 lock 을 사용한것 보다 많이 어렵다. 어떤 락도 존재 하지 않기 때문에 데드락은 lock-free 자료구조에서 불가능합니다. 대신에 라이브 락의 가능성은 존재 한다. 두 쓰레드가 각 자료구조를 변경하려고 시도 할때 라이브 락이 발생한다. 그러나 각 쓰레드에서 다른 쓰레드에서 수행한 변경때문에 연산은 다시 수행하도록 요구 된다. 그래서 둘다 반복문을 다시 수행하고 시도 한다. 두 사람이 좁은 통로를 통과하려고 시도하려는것을 상상해 봐라. 둘다 한번에 가려고 한다면 그 둘다 못간다. 그래서 그들은 되돌아가고 다시 시도한다. 누군가 먼저 그곳에 가지 않는한( 동의에 의해서, 더 빠르게, 운이 좋아서.. ) 그 싸이클은 반복될것이다. 이 간단한 예처럼, live lock 은 일반적으로 잛게 생성된다. 그것들은 쓰레드의 정밀한 스케쥴에 의존적이기 때문이다. 그러므로 그것들이 장기적 문제를 일으키기보다 성능을 약화시킬것이다. 그러나 주의해야할 어떤것이 아직 있다. 정의에 따르면, waif-free 코드는 언제나 연산을 수행하는데 필요한 스텝의 수의 상한(제한)이 존재 하기 때문에 라이브락을 겪지 않는다. 여기에 다른면이 있다. 알고리즘은 다른것보다 좀더 복잡해질 가능성이 있다. 자료 구조에 접근하는 쓰레드가 존재하지 않더라도 더 많은 스텝이 필요로 한다. lock-free 와 wait-free 코드의 다른 단점이 여기 있다. 자료구조에 대하여 연산의 동시성에 대한 가능성을 증가 시켰고 개별 쓰레드가 대기하는데 소요되는 시간이 줄어 들었지만 이것은 전체적인 성능을 하락시킨다. 먼저 lock-free 코드에 사용되는 atomic 연산은 non-atomic 연산 보다 느리다. 그리고 lock free 자료구조의 코드는 lock-based 자료구조의 뮤텍스 locking 코드에서 보다 atomic 연산이 더 많이 사용된다. 그것 뿐만 아니라 하드웨어는 같은 atomic 변수를 접근하는 쓰레드 사이의 데이터를 동기화 시킨다. 챕터 8에서 본것처럼, 여러 쓰레드 에서 같은 atomic 변수를 접근하는것과 같은 cache ping-pong 은 중요한 성능 하락을 가져 온다. 모든것과 마찬가지로 (최악의 대기 시간, 평균 대시 시간, 전체 수행 시간 이나 그것외에) lock-based 자료구조와 lock-free 자료구조 둘다 반영전 중요한 성능 양상을 확인하는것은 중요하다. 이제 몇몇 예제를 확인해 보자.
세션 7.2.2. 로 돌아가 reader 쓰레드가 접근하고 있는 노드를 삭제를 하는 문제에 대해서 보았다. 노드가 참조여부를 안전하고 확실하게 알수 있으면 아무 쓰레드도 이 노드들에게 접근하지 않을때 그것을 삭제할수 있다. Hazard 포인터는 사용하고 있는 노드의 리스트를 저장함으로써 문제를 방지한다. 참조 카운팅은 각 노드에 접근하는 쓰레드의 수를 저장함으로써 문제를 방지한다. 이것은 좋고, 쉬워보인다. 그러나 이것을 관리하기란 엄청 어렵다. 먼저 std::shared_ptr<> 와 같은 어떤것을 작업에 사용할 것이다. 결국 그것이 참조 카운트 포인터 이다. 불행히도 비록 std::shared_ptr<> 의 몇몇 연산이 atomic 이라도 lock free 를 보장하지 않는다. 그 자체로는 atomic 타입의 어떤 종류 연산과 다른점이 없다고 하더라도 std::shared_ptr<> 은 많은 context 에서 사용되도록 설계되었고 atomic 연산을 lock free 로 만드는것은 그 클래스의 모든 사용에 부담을 가중시킬수 있다. std::stomic_is_lock_free(&some_shared_ptr) 이 true로 반환되는 플랫폼을 사용한다면 모든 메모리 reclamation 문제는 없다. 그냥 밑의 listing 처럼 list 에 std::sharted_ptr을 사용해라.
Listing 7.9 A lock-free stack using a lock-free std::shared_ptr<> implementation
template<typename T>
class lock_free_stack
{
private:
struct node
{
std::shared_ptr<T> data;
std::shared_ptr<node> next;
node( T const & data_ ) : data( std::make_shared<T>( data_ ) )
{}
};
std::shared_ptr<node> head;
public:
void push( T const & data )
{
std::shared_ptr<node> const new_node = std::make_shared<node>( data );
new_node->next = head.load();
while( !std::atomic_compare_exchange_weak( & head,
& new_node->next,
new_node ) );
}
std::shared_ptr<T> pop()
{
std::shared_ptr<node> old_head = std::atomic_load( &head );
while( old_head &&
!std::atomic_compare_exchange_weak( &head,
&old_head,
old_head->next ) );
return old_head ? old_head->data : std::shared_ptr<T>();
}
};이 있을법한 케이스에서 shared_ptr<> 구현체는 lock free 가 아니다. 수동으로 참조 카운팅을 관리해주어야 한다. 한 가능한 방법은 각 노드가 하나의 참조 카운트가 아니라 내부 카운트와 외부 카운트로 두개의 참조카운트사용한다. 노드를 참조하는 총 개수가 이 값들의 합이다. 외부 카운트는 노드를 가리키는 포인트와 함께 유지되고 포인터를 읽을때마다 증가 한다. 리더가 노드의 작업을 끝냈을때 내부 카운트가 감소 한다. 포인터를 읽는 간단한 연산은 외부 카운트를 1 증가 시킨다. 그리고 그것이 끝났을때 내부 카운트를 감소 시킨다. 외부 카운트/포인터 짝이 더이상 필요하지 않을때( 즉, 노드가 여러 스레드에 액세스 할 수 있는 위치에서 액세스 할 수 없게된다.) 내부 카운트는 외부 카운트에서 1을 뺀 수를 증가 시킨다. 그리고 외부 카운트는 폐기한다. 내부 카운트가 0이 되면 아무도 노드를 참조하지 않고 있다 그렇게 때문에 안전하게 삭제가 가능하다. 공유 데이터의 갱신을 위해서 atomic 연산을 사용하는 것은 중요하다. 자 안전하게 삭제할수 있을때만 노드를 삭제하는 이 방법를 사용한 lock free 스택의 구현체를 확인해보자 다음 리스팅은 내부 자료구조와 push 의 구현체이다. 이것은 간단하고 좋다.
Listing 7.10 Pushing a node on a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr <- (1)
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count; <- (2)
counted_node_ptr next; <- (3)
node( T const& data_ ) : data(std::make_shared<T>( data_ ) ),
internal_count( 0 )
{}
};
std::atomic<counted_node_ptr> head; <- (4)
public:
~lock_free_stack()
{
while( pop() );
}
void push( T const& data ) <- (5)
{
counted_node_ptr new_node;
new_node.ptr = new node( data );
new_node.external_count = 1;
new_node.ptr->next = head.load();
while( !head.compare_exchange_weak( new_node.ptr->next,
new_node ) );
}
};먼저 (2) 에서 보는거 처럼 외부 카운트는 counted_noe_ptr 구조체안에 노드 포인터와 같이 쌓여져 있다. 이것은 내부 카운트(2)와 함께 노드 구조체의 next 포인터(3)로 사용되어 진다. counted_node_ptr 은 간단한 구조이기 때문에 그것을 list 의 head 로 atomic<> template 으로 사용할수 있다.(4) ouble-word-compare-and-swap 연산을 지원하는 플렛폼에서는 이 구조체 lock free로써 std::atomic<counted_noe_ptr> 를 사용해도 충분하다. (플랫폼이 지원하지 않는다면 ) std::atomic<> 은 타입이 플랫폼에서 지원하는 atomic instructions 보다 큰 경우에 atomicity 를 보장하기 위해서 mutex 를 사용하기 때문에 listing 7.9 에서 봤던 std::sharted_ptr 를 사용한 버젼이 좋을지도 모른다. (결국 'lock-free' 알고리즘을 lock 기반으로 만든다.) 또한 카운터의 크기를 제한하려면 플래폼이 포인터안에 여분의 비트를 가지고 있는것을 알고 있다. (예를 들면 주소 크기는 단지 48비트 이다 그러나 포인터는 64비트이다.) 포인터의 여분의 비트안에 single machine word 안에 모두 다시 맞게 카운트를 저장할수 있다. 그런 트릭은 플랫폼에 대한 지식이 필요하다 그리고 그것은 이 책 범위의 밖이다. (5)에서 보는 push() 는 상대적으로 간단하다. 새로 할당된 노드할당하고 data 와 연결하고 노드의 next 값에 head 의 현재 값을 넣고 counted_node_ptr 를 만든다. 단지 전의 listings 처럼 compare_exchange_weak() 을 사용하여 head 의 값을 넣는다. 이것은 새로운 노드이기 때문에 현재 노드에 하나의 외부 참조만 있다. (head 포인터) 다음 listing 에서 보여지는것 처럼 pop() 의 구현물이 언제나 복잡합니다.
Listing 7.11 Popping a node from a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
void increase_head_count( counted_node_ptr& old_counter )
{
counted_node_ptr new_counter;
do
{
new_counter = old_counter;
++new_counter.external_count;
}
while( !head.compare_exchange_strong( old_counter,
new_counter ) ); <- (1)
old_counter.external_count = new_counter.external_count;
}
public:
std::shared_ptr<T> pop()#
{
counted_node_ptr old_head = head.load();
for(;;)
{
increase_head_count( old_head );
node* const ptr = old_head.ptr; <- (2)
if( !ptr )
{
return std::shared_ptr<T>();
}
if( head.compare_exchange_strong( old_head,
ptr->next ) ) <- (3)
{
std::shared_ptr<T> res;
res.swap(ptr->data); <- (4)
int const count_increase = old_head.external_count-2; <- (5)
if( ptr->internal_count.fetch_add( count_increase ) ==- count_increase ) <-(6)
{
delete ptr;
}
return res; <- (7)
}
else if( ptr->internal_count.fetch_sub(1)==1 )
{
delete ptr; <- (8)
}
}
}
};이번에는 head 의 값을 읽을때 먼저 head 노드를 참조하는것을 나타내기 위해서 외부 참조의 카운트를 증가시켜야 한다. 그리고 안전하게 그것을 역참조 할수 있다. 참조 카운트를 증가시키기전에 포인터를 역참조 하면 다른 쓰레드에서 역참조하려는 쓰레드에서 접근하기 전에 노드를 해제 할수 있다. 그리고 dangling 포인터로 남게 된다. 이것이 분리된 참조 카운트를 사용하는 주된 이유이다. 외부 참조 카운트를 증가 시킴으로 다른곳에서 접근 하는 동안 포인트가 유효하게 된다. 동시에 다른 쓰레드들이 이 포인터를 변경하지 못하도록 모든 구조체에 compares and set 를 수행하는 (1)의 compare_exchange_strong() 반복을 통하여 증가를 수행한다.
카운트가 증가가 되었을때 안전하게 가리키는 노드에 접근하기 위해서 head 로 부터 읽은 값의 ptr 필드를 역참조 할수 있다. (2) 포인터가 null 포인터면 list 의 끝이다. 이것은 더 이상 개체가 존재하지 않는다. null 포인터가 아니면 head 에 compare_exchange_strong() 호출을 통하여 node 를 삭제하려 할수 있다.
compare_exchange_string() 이 성공하면 node 의 소유권을 가지고 왔다. (4)와 같이 반환값 준비를 위하여 data 를 swap 할수 있다. 이것은 data를 활용되지 않다는것을 보증한다. 스택에 접근하는 다른 쓰레드 이 노드의 포인터를 아직도 가지고 있을수 있기 때문이다. 노드의 외부 카운트와 내부 카운트를 atomic fetch_add 를 통하여 더한다.(6) 참조카운트(fetch_add 의 결과값)가 0이면 전 값은 무엇을 더했던간에 음수 였다. 이 경우 노드를 삭제 할수 있다. 더하는 값이 실제로는 외부카운트에서 2를 빼는것은 중요하다.(5) 리스트에서 노드를 삭제하고 그것의 카운트를 하나 떨어뜨려야 한다. 그리고 이 쓰레드는 더이상 노드를 접근하지 않을 것이다. 그렇게 때문에 그것의 카운트를 하어느쪽이든지
compare_exchange 가 실패하면 다른 쓰레드가 pop 하기전에 노드를 삭제 하였거나 다른 쓰레드가 스택에 새로운 노드를 추가 했다. compare/exchange 호출을 통하여 head 의 새 값을 가지고 다시 시작해야할 필요가 있다.나더 떨어 뜨린다. 노드를 삭제 하였던 삭제하지 않았던 간에 작업은 끝났다. 그래서 data 를 반환한다.(7) 그러나 먼저 삭제 하려고 했던 노드의 참조 카운트를 감소시켰다. 이 쓰레드는 더이상 그것에 접근하지 못한다. 참조자를 잡고 있는 마지막 쓰레드라면 ( 다른 쓰레드는 스택으로 부터 그것을 삭제 하기 때문에 ) 내부 참조 카운트는 1일 것이다. 그래서 1를 빼면 0이 된다. 이 케이스에서 여기 반복전에 노드를 삭제 할수 있다.(8)
지금까지 모든 atomic 연산으로 기본 std::memory_order_seq_cst memory ordering 를 사용하였다. 대부분의 시스템에서 다른 memory ordering 보다 동기화 오버헤드와 실행시간 면에서 더 비싼 연산이다. 지금 자료구조의 로직은 올바르게 동작한다. 이런 memory ordering 요구 사항을 좀 완화 시키는것을 생각할수 있다. 스택 사용자에게 불 필요한 오버헤드를 부과하고 싶지 않다.
memory ordering 을 변경하기전에 연산을 검토하고 필요한 관계에 대해 확인할 필요가 있다. 돌아가서 이 필요한 관계를 제공할수 있는 최소한의 memory ordering 을 찾아야 한다. 이것을 하기 위해서는 여러 다른 시나리오에서 쓰레드들의 관점에서 상황을 살펴보아야 한다. 최대한 간단한 시나리오는 한 쓰레드가 stack 에 data item 을 push() 을 수행하고 약간의 시간후에 다른 쓰레드에서 data item 을 pop() 을 수행하는 상황이다. 여기서 부터 시작해보자.
이 간단한 케이스에서 data 의 3개의 중요한 부분이 관여되어 있다. 첫째는 data:head 를 복사하는데 사용된 counted_node_ptr 이다. 둘째로는 head 가 참조한 노드 구조체이고, 세번재로는 그 노드가 가리키는 data item 이다.
push() 을 수행하는 쓰레드는 먼저 data item 과 노드를 구축하고(constructs, 생성) 그것을 head 로 만든다. pop() 을 수행하는 쓰레드는 먼저 head 값을 얻고 참조 카운트를 증가 시키기 위하여 head에 compare/exchange 반복문을 수행한다. 그 이후 next 값이 포함된 노드의 구조체를 읽는다. 지금 필요한 관계를 확인할수 있다. next 값은 일반적인 nonatomic 객체이다. 그래서 이것을 안전하게 읽기 위해서는 (push 하는 쓰레드에서)저장과 (pop 하는 쓰레드에서)읽는 과정사이는 happens-before relationship 이어야 한다. push() 에서 atomic 연산은 오직 compare_exchange_weak() 뿐이기 때문에 쓰레드 간에 happens-before relationship 을 얻을 수 있는 release 연산이 필요하다. compare_exchange_weak() 은 std::memory_order_release 나 stronger 이어야만 한다. compare_exchange_weak() 호출이 실패하면 아무것도 변하지 않고 반복문은 유지된다. 그래서 이 케이스에서는 단지 std::memory_order_relaxed 가 필요하다.
void push( T const& data )
{
counted_node_ptr new_node;
new_node.ptr = new node( data );
new_node.external_count = 1;
new_node.ptr->next=head.load( std::memory_order_relaxed );
while( !head.compare_exchange_weak( new_node.ptr->next,
new_node,
std::memory_order_release,
std::memory_order_relaxed ) );
}pop() 코드는 어떨까? 필요한 happens-before relationship 을 얻기 위하여 next에 접근하기 전에 std::memory_order_acquire 나 stronger 연산이 있어야 한다. next 필드에 접근하기 위한 역참조하는 포인터는 increase_head_count() 에서 compare_exchange_strong() 으로 읽은 옜날 값이다. 그래서 성공한다면 그것에 대한 ordering 이 필요하다. push()에서의 호출처럼 exchange 이 실패하면 반복문을 다시 수행해야 한다. 그래서 실패시 relaxed ordering 을 사용하여야 한다.
void increase_head_count( counted_node_ptr& old_counter )
{
counted_node_ptr new_counter;
do
{
++new_counter.external_count;
} while( !head.compare_exchange_strong( old_counter,
new_counter,
std::memory_order_acquire,
std::memory_order_relaxed ) );
old_counter.external_count = new_counter.external_count;
}compare_exchange_strong() 호출이 성공하면
If the compare_exchange_strong() call succeeds, you know that the value read had the ptr field set to what’s now stored in old_counter.
읽은 값은 old_counter 에 저장된다. 읽은 값이 ptr 필드를 가지고 있는것을 알수 있다. old_counter 에 지금 저장된 무언가
push()에서 저장하는 작업은 release 연산이었고 이 compare_exchange_strong() 은 acquire 연산이다. 저장하는 작업과 읽는 작업은 동기화되고 happens-before relationship 이다. 결론적으로 push()에서 ptr 필드를 저장하는 연산은 pop()에서 ptr->next 접근 전에 일어 난다. 그렇기 때문에 안전하다.
초기 head.load()의 memory ordering 은 이 분석에서는 상관없다. 그래서 그것을 위해서 std::memory_order_relaxed 를 안전하게 사용할수 있다.
다음은 old_head.ptr->next 을 head 로 설정하는 compare_exchange_strong() 이다. 이 쓰레드의 데이터 통합을 보장하기 위하여 이 연산은 아무것도 필요 없는가? 변경에 성공하면 ptr->data 에 접근하고 읽기 전에 push() 쓰레드에서 ptr->data 에 저장이 이루어 지는것을 확신할 필요가 있다. 그러나 이미 이것은 보장된다. increase_head_count() 의 acquire 연산은 push() 쓰레드의 저장 연산과 compare/exchange 사이에서 synchronizes-with relationship 을 보장한다. push()에서 데이터의 저장은 head 를 저장하기 전에 이루어진다. increase_head_count()의 호출은 ptr->data 을 읽기 전에 이루어진다. 이것은 happens-before relationship 이다. 그래서 pop() 에서 compare/exchange가 std::memory_order_relaxed 를 사용하더라도 모든것은 괜찮다. ptr->data가 변경되는 다른곳은 swap()을 호출하는 곳이다. 그래서 다른 쓰레드는 같은 노드에 연산을 수행할수 없다.; compare/exchange의 모든 요점이다.
compare_exchange_strong() 이 실패하면 old_head 의 새 값은 다음번 반복까지 관여하지 않는다. 그리고 increase_head_count() 에서 std::memory_order_acquire 가 이미 충분하다고 판단하였고 또한 std::memory_order-relaxed 도 역시 거기에서 충분하다고 판단하였다.
다른 쓰레드들은 어떤가? 다른 쓰레드가 안전하기 위해서는 어떠한 stronger 도 필요가 없는가? 대답은 ‘필요없다’이다. compare/exchange 연산으로 head 는 변경되기 때문이다. 왜냐하면 read-modify-write 연산이 있다. push()에서 compare/exchange의 앞부분의 release 순서의 부분으로 형성되어 있다. 그러므로 push() 에서 compare_exchange_weak()은 increase_head_count() 의 compare_exchange_strong()와 동기화된다. 동시에 많은 다른 쓰레드들이 head 를 변경할지라도 저장된 값을 읽는다.
마지막에 거의 다 왔다. 남아 있는 다룰 연산은 fetch_add() 이다.
이 노드로부터 데이터를 반환받는 쓰레드는 진행되고 The thread that got to return the data from this node can proceed, safe in the knowledge that no other thread can have modified the node data.
그러나 데이터 검색을 성공적으로 하지 못한 어떤 쓰레드는 노드의 데이터를 다른 쓰레드가 변경 한것을 알고 있습니다.; 참조된 data item 을 검색하는데 swap 이 사용된다. 그러므로 data race 를 피하기 위해서 delete 전에 swap() 이 이루어져야 할 필요가 있습니다. 이것을 하는 쉬운 방법은 성공적인 반환을 하는 가지에서 fetch_add() 는 std::memory_order_release 를 사용하고 다시 반복문을 수행해야 하는 fetch_add()는 std::memory_order_acquire 를 사용하도록 만든다. 그러나 이것은 과하다. 한 쓰레드는 단지 delete 를 수행한다.( count 를 0 으로 만드는것),
fetch_add()는 read-modify-write 연산이기 때문이다. 이것은 release 순서의 부분을 형성하고 있다. 그래서 추가적인 load() 와 같이 수행할수 있다. 다시 반복해야 하는 가지에서 참조 카운트를 0 으로 줄인다면 synchronizes-with relationship 을 얻기 위하여 std::memory_order_acquire 를 사용하여 참조 카운트를 다시 읽어야 한다. 그리고 fetch_add()는 std::memory_order_relaxed 를 사용해야 한다. 새로운 버젼의 pop()을 포함한 마지막 스택 구현물이 여기에 있다.
Listing 7.12 A lock-free stack with reference counting and relaxed atomic operations
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count;
counted_node_ptr next;
node( T const& data_ ):
data( std::make_shared<T>( data_ ) ), internal_count(0)
{
}
};
std::atomic<counted_node_ptr> head;
void increase_head_count( counted_node_ptr& old_counter )
{
counted_node_ptr new_counter;
do {
new_counter=old_counter;
++new_counter.external_count;
} while( !head.compare_exchange_strong( old_counter,
new_counter,
std::memory_order_acquire,
std::memory_order_relaxed ) );
old_counter.external_count = new_counter.external_count;
}
public:
~lock_free_stack()
{
while(pop());
}
void push(T const& data)
{
counted_node_ptr new_node;
new_node.ptr = new node( data );
new_node.external_count = 1;
new_node.ptr->next = head.load( std::memory_order_relaxed );
while( !head.compare_exchange_weak( new_node.ptr->next,
new_node,
std::memory_order_release,
std::memory_order_relaxed ));
}
std::shared_ptr<T> pop()
{
counted_node_ptr old_head = head.load( std::memory_order_relaxed );
for(;;)
{
increase_head_count( old_head );
node* const ptr = old_head.ptr;
if( !ptr )
{
return std::shared_ptr<T>();
}
if( head.compare_exchange_strong( old_head,
ptr->next,
std::memory_order_relaxed ) )
{
std::shared_ptr<T> res;
res.swap( ptr->data );
int const count_increase = old_head.external_count - 2;
if( ptr->internal_count.fetch_add( count_increase,
std::memory_order_release )
==-count_increase)
{
delete ptr;
}
return res;
}
else if( ptr->internal_count.fetch_add( -1,
std::memory_order_relaxed )
== 1 )
{
ptr->internal_count.load( std::memory_order_acquire );
delete ptr;
}
}
}
};꽤 힘든 작업이었다. 그러나 끝부분까지 왔고 스택을 보다 나아지게 만들었다. in a carefully thought-through mannger 에서 relaxed 연산을 사용함으로써 정확성에 영향을 주지 않고 성능을 향상 시켰다.
As you can see, the implementation of pop() is now 37 lines rather than the 8 lines of the equivalent pop() in the lock-based stack of listing 6.1 and the 7 lines of the basic lock-free stack without memory management in listing 7.2.
lock free 큐를 작성하는 것으로 이동하여, 비슷한 패턴을 볼수 있다. lock free 코드에서 복잡한 많은 것들은 메모리 관리하는 것부터 온다.
큐에서의 push()와 pop() 연산은 자료구조의 다른부분을 접근하기 때문에 큐는 스택과는 약간 다른 방법으로 구현한다. 따라서 동기화해야하는 부분이 다르다. You need to ensure that changes made to one end are correctly visible to accesses at the other. 그러나 listing 6.6 에서 큐의 try_pop()의 구조는 listing 7.2 에서 lock free 스택의 pop() 과 크게 다르지 않다. 그렇기 때문에 lock free 코드는 다르지 않다는것을 충분히 알수 있다. 어떻게 하는지 한번 보자. listing 6.6 에서 기반으로 한다면 2 노드 포인터가 필요 하다. 하나는 list 의 앞 부분이고 다른 하나는 끝 부분이다. 여러 쓰레드에서 이것들을 접근할것이고 mutex 를 사용하지 않기 위해서는 이것들은 atomic 이어야 합니다. 작은 변경 부터 시작해보자, see where it gets you. 아래에 있는 listing 에서 결과를 확인한다.
Listing 7.13 A single-producer, single-consumer lock-free queue
template<typename T>class lock_free_queue
{
private:
struct node
{
std::shared_ptr<T> data;
node* next;
node() : next(nullptr)
{
}
};
std::atomic<node*> head;
std::atomic<node*> tail;
node* pop_head()
{
node* const old_head=head.load();
if( old_head == tail.load() ) // <- <1>
{
return nullptr;
}
head.store( old_head->next );
return old_head;
}
public:
lock_free_queue(): head(new node),
tail(head.load())
{}
lock_free_queue( const lock_free_queue& other ) = delete;
lock_free_queue& operator=( const lock_free_queue& other ) = delete;
~lock_free_queue()
{
while( node* const old_head = head.load() )
{
head.store( old_head->next );
delete old_head;
}
}
std::shared_ptr<T> pop()
{
node* old_head = pop_head();
if( !old_head )
{
return std::shared_ptr<T>();
}
std::shared_ptr<T> const res( old_head->data ); // <- <2>
delete old_head;
return res;
}
void push( T new_value )
{
std::shared_ptr<T> new_data( std::make_shared<T>( new_value ) );
node* p = new node; // <- <3>
node* const old_tail = tail.load() // <- <4>
old_tail->data.swap( new_data ); // <- <5>
old_tail->next = p; // <- <6>
tail.store( p ); // <- <7>
}
};언뜻보면 이것은 나쁘지 않다. 그리고 한번에 한 쓰레드가 push()을 호출하거나 오로지 한 쓰레드가 pop() 을 호출한다면 완벽하다. 이 케이스에서 중요한것은 전체 데이터를 보호하기 위한 push() 와 pop() 사이의 happens-before relationship 이다. tail에 저장연산<7>은 tail로 부터 읽는연산<1> 과 동기화 되어야 한다. 선행 노드의 데이터 포인터를 저장하는 연산<5>은 tail 에 저장하는 연산 전에 있어야 한다; 그리고 tail 로 부터 읽는 연산은 데이터 포인터로부터 읽는 연산<2>전에 위치해야 한다. 그래서 데이터를 읽기 전에 데이터를 저장이 이루어지고 모든것이 괜찮다. 그러므로 이것은 완벽하게 서비스 할수 있는 하나의 생산자, 하나의 소비자(SPSC) 큐이다. 여러 쓰레드가 동시에 push()를 호출하거나 pop() 을 호출하면 문제가 발생한다. 먼저 push()을 보자. 만약 push()를 동시에 호출하는 2개의 쓰레드가 있다고 가정해 보자, 둘다 새로운 dummy 노드로 새로운 노드를 할당 받고, tail 로 부터 같은 값을 읽는다<4>. 그리고 결론적으로 데이터와 next 포인터를 설정할때<5><6> 같은 노드의 데이터 멤버를 둘다 갱신한다. 이것이 data race(데이터 경합?) 이다. pop_head()에도 비슷한 문제가 있다. 동시에 2개의 쓰레드가 호출하면 head 의 같은 값을 둘다 읽고 둘다 같은 next 포인터에 옜날 값을 덮어쓴다. 두 쓰레드다 망할 지름길인 같은 노드 를 찾았다고 생각한다. 하나의 쓰레드에서 아이템을 얻기 위하여 pop() 연산을 확실히 하는것 뿐만 아니라 다른 쓰레드도 head 을 읽어 노드의 next 멤버에 안전하게 접근하도록 하여야 한다. 이것은 정확하게 lock free 스택의 pop() 에서 보았던 문제이다. 그래서 그 해결책중 하나를 여기에 사용할 수 있다. pop() 연산도 해결된 문제라면 push() 연산은 어떻게 하는가? push() 연산과 pop() 연산 사이에 필요한 happens-before relationship 얻기 위한 문제가 여기에 있다. tail 를 갱신하기전에 dummy 노드에 데이터 아이템을 설정할 필요가 있다. 그러나 push()을 동시에 호출하는것은 같은 tail 포인터를 읽기 때문에 같은 데이터를 경쟁하는것을 의미한다.
실제 노드 사이에 dummy 노드를 추가 하는 방법이 있다. 갱신이 필요한 현 tail 노드의 한 부분은 next 포인터이다. 그러므로 이것은 atomic 으로 되어야 한다.(This way, the only part of the current tail node that needs updating is the next pointer, which could therefore be made atomic.) 쓰레드는 nullptr 에서 그 새로운 노드로의 next 포인터의 변경을 성공적으로 관리하려면 포인터를 성공적으로 추가한다. 그렇지 않으면 반복문을 다시 시작하고 tail 를 다시 읽어야 한다. null 데이터 포인터를 가지는 노드를 취소하고 다시 반복문을 수행하기 위하여 pop() 연산에 조그마한 변화가 필요하다. 매번 pop() 호출은 2 노드를 제거 해야 하고 큰 메모리 할당이 2개가 되는 단덤이 있다. 다른 방법으로는 데이터 포인터를 atomic으로 생성하고 compare/exchange(CAS) 호출을 사용하여 값을 설정 한다. 호출이 성공하면 이것은 tail 노드이고 새로운 노드를 next 포인터에 안전하기 설정하고 tail을 갱신할수 있다. compare/exchange 가 실패 하면 다른 쓰레드가 data 를 정장 하였기 때문에 반복문을 다시 수행하고 tail 을 다시 읽고 다시 처음 부터 수행한다. std::shared_ptr<> 의 atomic 연산이 lock free 면 you’re home free. 만약 아니면 대안이 필요 하다. std::unique_ptr<>(결국 객체에 대한 참조) 을 반환하는 pop() 연산과 큐에 일반 포인터로 데이터를 저장하는 하나의 가능성이 있다. std::atomic<T*> 으로 저장 가능하게 하고 필요한 compare_exchange_strong() 호출을 지원한다. 다중 쓰레드에서 pop()과 push()을 처리하기 위하여 listing 7.11 에서 참조 카운팅 방식을 사용한 방법은 다음과 같다.
listing 7.14 A (broken) First attempt at revising push()
void push( T new_value )
{
std::unique_ptr<T> new_data( new T( new_value ) );
counted_node_ptr new_next;
new_next.ptr = new node;
new_next.external_count = 1;
for(;;)
{
node* const old_tail = tail.load(); // <- <1>
T* old_data = nullptr;
if( old_tail->data.compare_exchange_strong(
old_data,
new_data.get() ) ) // <- <2>
{
old_tail->next = new_next;
tail.store( new_next.ptr ); // <- <3>
new_data.release();
break;
}
}
}참조 카운팅 방식은 이런 특별한 경합을 피할수 있다. 그러나 push()에서만 경합이 있는 것이 아니다. listing 7.14 에서 push() 의 수정된 버젼을 보면 atomic 포인터를 읽고<1> 그 포인터에 참조된 위치의 값을 읽는<2> 스택에서 보았던 패턴을 볼수 있다. 그 동안에 다른 쓰레드는 그 포인터를 갱신이 가능하고 결국 (pop() 에서) 해제된 노드을 연결한다. 포인터에 참조된 위치의 값을 읽기 전에 그 노드가 할당해제 된다면 그것은 정의되지 않은 행동(undefined behavior) 이다. 이런 head 에서 한 작업 처럼 tail 에 외부 카운트(external count)를 추가하는것은 매력적이다. 그러나 각 노드는 이미 큐의 이전 노드의 next 포인터에 대한 외부 카운트(external count)를 가지고 있다. 같은 노드를 위해 2개의 외부 카운트(external count)를 사용하는것은 너무 일찍 노드가 삭제 되는것을 피하기 위한 참조 카운트의 변경이 필요로 하다. (해당 하는 외부 카운트(external count) 를 내부 카운트(internal count) 에 더하는것과 마찬가지로) 각 외부 카운트(external count)가 없어질때 노드 구조체 안의 외부 카운트(external count) 의 수를 세고 이 숫자를 감소시켜 이것을 해결할수 있다. 내부 카운트(internal count)가 0이면 외부 카운트(external count)는 없다. 그렇기 때문에 노드를 안전하게 삭제 할수 있다. 이것은 Joe Seigh’s Atomic Ptr Plus Project.5 를 통하여 처음으로 본 기술이다. 다음 listing 은 이 방법으로 push() 를 변경 하였다.
Listing 7.15 Implementing push() for a lock-free queue with a reference-counted tail
template<typename T>
class lock_free_queue
{
private:
struct node;
struct counted_node_ptr
{
int external_count;
node* ptr;
};
std::atomic<counted_node_ptr> head;
std::atomic<counted_node_ptr> tail; // <- <1>
struct node_counter
{
unsigned internal_count:30;
unsigned external_counters:2; // <- <2>
};
struct node
{
std::atomic<T*> data;
std::atomic<node_counter> count; // <- <3>
counted_node_ptr next;
node()
{
node_counter new_count;
new_count.internal_count = 0;
new_count.external_counters = 2; // <- <4>
count.store( new_count );
next.ptr = nullptr;
next.external_count = 0;
}
};
public:
void push( T new_value )
{
std::unique_ptr<T> new_data( new T(new_value) ); // <- <5>
counted_node_ptr new_next;
new_next.ptr = new node;
new_next.external_count = 1;
counted_node_ptr old_tail = tail.load();
for(;;)
{
increase_external_count( tail,old_tail );
T* old_data = nullptr;
if( old_tail.ptr->data.compare_exchange_strong( // <- <6>
old_data,
new_data.get() ) )
{
old_tail.ptr->next = new_next;
old_tail=tail.exchange( new_next );
free_external_counter( old_tail ); // <- <7>
new_data.release();
break;
}
old_tail.ptr->release_ref();
}
}
};listing 7.15 에서 tail 은 atomic<counted_node_ptr> 이고 head 도 마찬가지이다<1>. 노드 구조체는 이전 값으로 부터 내부 카운트(internal count)를 대신하는 count 멤버를 가지고 있다<3>. 이 카운트는 내부 카운트(internal count)와 외부 카운트(external count)를 포함하는 구조 이다<2>. 최대 2개의 카운터가 존재 하기 때문에 외부 카운트(external count)는 단지 2비트만이 필요하다. 내부 카운트(internal count)를 30비트 값으로 지정하여 비트 필드를 사용하면 총 카운터의 크기는 32비트 이다. 이것은 32비트와 64비트 머신의 머신 word 안에 모든 구조를 맞추어서 충분한 범위의 큰 내부 카운트(internal count) 값을 줄수있다. 간단하게 본것처럼 경쟁 상태(race condition)를 피하기 위하여 이 카운트들의 갱신이 한번(single entity)에 이루워 지는것은 중요하다. 머신 word 안에 구조체를 유지시키면 (Keeping the structure within a machine word makes it more likely that the atomic operations can be lock-free on many platforms.) 큐에 새로운 노드를 실제로 추가 할때 tail 과 이전 노드의 next 포인터로 부터 참조가 시작 되기 때문에 내부 카운트(internal count)를 0으로 외부 카운트(external count)를 0 으로 노드느 초기화한다<4>. listing 7.14 와 push() 는 비슷하다. 노드의 데이터 멤버인 compare_exchange_strong() 을 호출<6>하기 위하여 tail 로 부터 읽은 포인트에 참조된 위치의 값을 읽기 전에 카운트를 증가시키는 새로운 increase_external_count() 함수를 호출<5>하고 그후에 old tail 값의 free_external_ount() 을 호출<7> 한다. push() 에서 처리 방식을 토대로 pop()도 살펴보자. listing 7.11 에서 pop() 구현물에서 참조 카운트 방식과 listing 7.13 에서 queue-pop 로직을 섞여져 이다.
listing 7.16 Popping a node from a lock-free queue with a reference-counted tail
template<typename T>
class lock_free_queue
{
private:
struct node
{
void release_ref();
};
public:
std::unique_ptr<T> pop()
{
counted_node_ptr old_head = head.load(std::memory_order_relaxed); // <- <1>
for(;;)
{
increase_external_count( head,old_head ); // <- <2>
node* const ptr = old_head.ptr;
if( ptr == tail.load().ptr )
{
ptr->release_ref(); // <- <3>
return std::unique_ptr<T>();
}
if( head.compare_exchange_strong( old_head,
ptr->next ) ) // <- <4>
{
T* const res = ptr->data.exchange( nullptr );
free_external_counter( old_head ); // <- <5>
return std::unique_ptr<T>( res );
}
ptr->release_ref(); // <- <6>
}
}
};for 반복문에 들어가기전과 외부 카운트(external count)를 증가<2> 시키기 전에 old head 값을 읽어서<1> pop 할 준비가 되었다. tail 노드와 head 노드가 같다면 큐에 데이터가 없기 때문에 reference 를 release<3> 시키고 null 포인터를 반환할수 있다. 데이터가 있으면 compare_exchange_strong()을 호출<4>하여 데이터를 얻는 작업을 수행한다. listing 7.11 의 스택에서 처럼 외부카운트(external count) 와 포인터의 비교를 한번에 수행해야 한다. 둘중 하나라도 변화 하였으면 reference 를 release<6> 후에 for 반복문을 다시 수행한다. 변경에 성공하였으면 노드의 데이터를 획득하였다. 그렇기 때문에 pop할 노드의 외부 카운터(external counter)를 release<5> 후 호출한 함수에 노드를 반환한다. 외부 참조 카운트(external reference count)가 해제 되었고 내부 카운트(internal count) 가 0으로 되었으면 노드는 삭제가 가능하다. 이 모든것을 처리하는 참조 카운팅 함수는 listing 7.17, 7.18, 7.19 에서 확인할수 있다.
Listing 7.17 Releasing a node reference in a lock-free queue
template<typename T>
class lock_free_queue
{
private:
struct node
{
void release_ref()
{
node_counter old_counter = count.load(std::memory_order_relaxed);
node_counter new_counter;
do
{
new_counter = old_counter;
--new_counter.internal_count; // <- <1>
}
while( !count.compare_exchange_strong( // <- <2>
old_counter,
new_counter,
std::memory_order_acquire,
std::memory_order_relaxed ) );
if( !new_counter.internal_count &&
!new_counter.external_counters )
{
delete this; // <- <3>
}
}
};
};node::release_ref() 의 구현물은 listing 7.11 의 lock_free_stack::pop() 의 구현물의 동일한 코드에서 약간의 변경이 있다.
listing 7.11의 코드는 하나의 외부 카운트(external count)만 처리만 하면 되었다 그렇기 때문에 간단한 fetch_sub 를 사용하였다. 내부 카운트(internal count)필드를 변경하더라도 모든 카운트 구조체를 한번에(atomically) 변경하여야 한다<1>. 그러므로 compare_exchange 반복구문<2>이 필요 하다. 내부카운트(internal count)을 줄일때 내부(internal)와 외부(external) 카운트(count)가 0이면 이것은 마지막 참조이다. 그렇기 때문에 노드를 삭제<3> 할수 있다.
List 7.18 Obtaining a new reference to a node in a lock-free queue
template<typename T>
class lock_free_queue
{
private:
static void increase_external_count(
std::atomic<counted_node_ptr>& counter,
counted_node_ptr& old_counter )
{
counted_node_ptr new_counter;
do
{
new_counter = old_counter;
++new_counter.external_count;
} while( !counter.compare_exchange_strong(
old_counter,
new_counter,
std::memory_order_acquire,
std::memory_order_relaxed ) );
old_counter.external_count = new_counter.external_count;
}
};listing 7.18 은 반대 쪽이다. 이번에는 reference 을 release 하지 않고 새로운 것을 얻고 외부 카운트(external count) 를 증가시킨다. 첫번째 파라미터로 갱신할 외부 카운터(external counter) 를 취하는 정적 멤버 함수안에서 이루지는 것을 제외하면 increase_external_count()는 listing 7.12의 increase_head_count() 함수와 비슷하다.
Listing 7.19 Freeing an external counter to a node in a lock-free queue
template<typename T>
class lock_free_queue
{
private:
static void free_external_counter( counted_node_ptr &old_node_ptr )
{
node* const ptr = old_node_ptr.ptr;
int const count_increase = old_node_ptr.external_count-2;
node_counter old_counter = ptr->count.load( std::memory_order_relaxed );
node_counter new_counter;
do
{
new_counter = old_counter;
--new_counter.external_counters; // <- <1>
new_counter.internal_count += count_increase; // <- <2>
} while( !ptr->count.compare_exchange_strong( // <- <3>
old_counter,
new_counter,
std::memory_order_acquire,
std::memory_order_relaxed ) );
if( !new_counter.internal_count &&
!new_counter.external_counters )
{
delete ptr; // <- <4>
}
}
};increase_external_count() 를 카운터 부분은 free_external_count()이다. listing 7.11 의 lock_free_stack::pop()의 코드와 비슷하다. 그러나 외부 카운터(external_counters) 수를 처리하는 부분을 수정하여야 한다. 하나의 compare_exchange_strong()을 사용하여 모든 카운트 구조체의 2개의 카운트를 갱신한다<2>. 내부 카운트 값은 0이면 아무도 노드를 참조 하지 않는다. 그렇기 때문에 노드를 안전하게 삭제 할수 있다<4>. 경쟁 상태를 피하기 위하여 하나의 작업으로 완료 되어야 한다.(그러므로 compare/exchange 반복구문이 필요하다.) 만약 개별적으로 갱신되면 정의되지 않은 행동(undefined behavior)로써 두 쓰레다가 마지막 노드라고 생각하고 둘다 노드를 삭제 할수 있다. 지금 이 작업이 race free 라도 성능상 문제는 아직 가지고 있다. 한 쓰레드가 old_tail.ptr->data 의 compare_exchange_strong() 을 성공적으로 완료하여 push() 연산을 시작 하였을때 다른 쓰레드는 push() 연산을 수행할수 없다. 시도하는 어떤 쓰레드는 nullptr 대신에 새로운 값을 볼것이다. 이것은 compare_exchange_strong() 를 실패하고 쓰레드 반복을 다시 수행하게 한다. 이것은 어떤것도 얻는것이 없이 CPU cycle을 소모하는 busy-wait이다. 결론적으로 이것은 lock 이다. 첫 push()는 완료되기 전까지 다른 쓰레드들은 block 된다. 그래서 이 코드는 더이상 lock free 가 아니다. 뿐만 아니라 운영체제는 뮤텍스로 락을 잡은 쓰레드가 block 되어 있으면 우선순위를 줄수 있다. 그러나 이 경우 에는 그렇게 되지 않는다. 그저 block 된 쓰레드는 첫 쓰레드가 완료되기 전까지 그저 CPU cycle만 소모하고 있다. This calls for the next trick from the lock-free bag of tricks: the waiting thread can help the thread that’s doing the push()
In order to restore the lock-free property of the code, you need to find a way for a waiting thread to make progress even if the thread doing the push() is stalled. One way to do this is to help the stalled thread by doing its work for it.
이 경우 완료 되어야 할 것들을 정확히 파악해야 한다. 새로운 dummy 노드는 tail 의 next 포인터가 가리키고, tail 포인터로 갱신되어야 한다. dummy 노드에 대한 것은 모두에게 동일하다. data 를 성공적으로 push 한 쓰레드가 생성한 dummy 노드를 하용하거나 push 를 대기하고 있는 쓰레드중 하나의 dummy 노드를 사용하여도 문제가 없다. 노드의 next 포인터를 atomic 하게 만들면 포인터에 무엇을 가리키게 할때는 compare_exchange_strong() 함수를 사용할수 있다. next 포인터를 설정할때 같은 원본 노드를 아직 참조하고 있는 동안은 tail를 결정 하기 위해서 compare_exchange_weak() 반복을 할수 있다. 그렇지 않으면 누군가 갱신을 하고 시도를 멈추거나 반복을 다시 할수 있다. next 포인터를 읽기 위하여 pop()함수는 조그마한 변경이 필요하다. 다음 listing 에서 확인하자.
Listing 7.20 pop() modified to allow helping on the push() side
template<typename T>
class lock_free_queue
{
private:
struct node
{
std::atomic<T*> data;
std::atomic<node_counter> count;
std::atomic<counted_node_ptr> next; // <- <1>
};
public:
std::unique_ptr<T> pop()
{
counted_node_ptr old_head = head.load( std::memory_order_relaxed );
for(;;)
{
increase_external_count( head,old_head );
node* const ptr = old_head.ptr;
if( ptr == tail.load().ptr )
{
return std::unique_ptr<T>();
}
counted_node_ptr next = ptr->next.load(); // <- <2>
if( head.compare_exchange_strong( old_head,next ) )
{
T* const res = ptr->data.exchange( nullptr );
free_external_counter( old_head );
return std::unique_ptr<T>( res );
}
ptr->release_ref();
}
}
};미리 말한것 처럼 여기에서 변경은 간단하다. next 포인터는 지금 atomic 이다.<1> 그래서 읽는 연산(load) 역시 atomic 하다.<2> 이 예제에서 기본 memory_order_seq_cst_ordering 을 사용하였다. 그리고 load()에서 명시적인 호출을 생략할수 있다. counted_node_ptr 로 묵시적으로 변환이 load 를 신뢰할수 있다. 그러나 명시적 호출을 넣는것이 나중에 이디서 명시적으로 memory ordering 를 하는지 알수 있다. push() 코드는 좀더 복잡하다. 한번 확인해 보자.
Listing 7.21 A sample push() with helping for a lock-free queue
template<typename T>
class lock_free_queue
{
private:
void set_new_tail( counted_node_ptr &old_tail, // <- <1>
counted_node_ptr const &new_tail)
{
node* const current_tail_ptr = old_tail.ptr;
while( !tail.compare_exchange_weak( old_tail,
new_tail) && // <- <2>
old_tail.ptr == current_tail_ptr );
if( old_tail.ptr == current_tail_ptr ) // <- <3>
free_external_counter( old_tail ); // <- <4>
else
current_tail_ptr->release_ref(); // <- <5>
}
public:
void push( T new_value )
{
std::unique_ptr<T> new_data( new T( new_value ) );
counted_node_ptr new_next;
new_next.ptr = new node;
new_next.external_count = 1;
counted_node_ptr old_tail = tail.load();
for(;;)
{
increase_external_count( tail,old_tail );
T* old_data = nullptr;
if( old_tail.ptr->data.compare_exchange_strong( // <- <6>
old_data,
new_data.get() ) )
{
counted_node_ptr old_next={ 0 };
if( !old_tail.ptr->next.compare_exchange_strong( // <- <7>
old_next,
new_next ) )
{
delete new_next.ptr; // <- <8>
new_next = old_next; // <- <9>
}
set_new_tail( old_tail,
new_next );
new_data.release();
break;
}
else // <- <10>
{
counted_node_ptr old_next = { 0 };
if( old_tail.ptr->next.compare_exchange_strong( // <- <11>
old_next,
new_next ) )
{
old_next = new_next; // <- <12>
new_next.ptr = new node; // <- <13>
}
set_new_tail( old_tail,
old_next ); // <- <14>
}
}
}
};listing 7.15 의 기본 push()와 유사하다. 그러나 여기에는 중요한 차이가 있다. data 포인터를 설정하려면<6>, 다른 쓰레드 If you do set the data pointer <6> , you need to handle the case where another thread has helped you, and there’s now an else clause to do the helping <10>.
노드의 data 포인터를 설정<6>했다. 이 새로운 버젼의 push() 함수는 compare_exchange_strong() 함수를 통하여 next 포인터를 갱신한다.<7> 반복을 피하기 위하여 compare_exchange_strong() 함수를 사용한다. 만약 변경이 실패 되었으면 다른 쓰레드가 이미 next 포인터를 갱신하였다 그래서 시작할때 할당받았던 새로운 노드가 필요 없다 그래서 그것을 삭제 한다.<8> 다른 쓰레드가 설정한 next 값을 tail 갱신을 위하여 사용하여야 한다<9> set_new_tail() 함수에서 실제 tail 포인터의 갱신이 이루어 진다. tail 갱신을 위하여 compare_exchange_weak 반복을 사용한다. 다른 쓰레드가 새로운 노드를 push()하고 있으면 external_count 부분이 변경 되었고 그것을 잃지 않기를 원한다. 그러나 다른 쓰레드가 이미 변경을 하였으면 그 값이 변경되지 않도록 주의해야 한다. 그렇지 않으면 큐에서 반복문을 끝난다. 이것은 나쁜 생각이다. 따라서 compare/exchange 가 실패되면 읽는 값의 ptr 부분은 같아야 한다. 반복의 끝났을때 ptr 이 같으면 tail을 성공적으로 갱신하였다. 그래서 old external counter 를 해제할수 있다. 만약 값이 다르면 다른 쓰레드가 counter 를 해제할수 있다. 그래서 이 쓰레드가 잡고 있는 single reference 를 release 한다. <5> push()를 호출한 쓰레드가 반복문을 통하여 이번에 data 포인터를 설정에 실패 하면 갱신을 완료하기 위하여 성공적으로 쓰레드를 도와야 한다. 첫째, 이 쓰레드에서 할당한 새로운 노드를 next 포인터로 갱신을 시도한다.<11> 이것이 성공하면 새로운 tail 노드로 할당된 노드를 사용하고<12>, 큐에 아이템을 push()를 실직적으로 관리될것을 예측하고 다른 새로운 노드를 할당할 필요가 있다.<13> 다시 반복문을 수행하기전에 set_net_tail 호출하여 tail 노드에 설정을 시도할수 있다. push()에서 새로운 노드가 할당되고 pop()에서 삭제되기 때문에 코드의 작은 부분들에서 많은 new 와 delete 호출이 있는 것을 알아야 한다. 그러므로 메모리 할당자의 효율은 이 코드의 성능에 큰 영향을 미친다. 나쁜 할당자는 완전히 이것과 같은 lock free 콘테이너의 확장가능성 속성을 무너뜨린다. 그런 할당자의 선택과 구현은 이책의 범위에서 벗어 난다. 그러나 코드의 성능을 보다 나은 할당자의 선택 전후 성능측정을 해야 한다는것을 명심해라. 최적화된 메모리 할당의 공통적인 기술은 각 쓰레드에서 메모리 관리자를 분리하는것과 관리자에서 메모리를 반납하는것보다 노드의 재활용을 위하여 free list 를 사용한다. 충분한 예제가 있다. 대신에, 예제를 통하여 lock free 자료구조를 작성하는 몇가지 가이드 라인에 대하여 알아보자.
이챕터의 모든 예제들을 따라왔으면 올바른 lock free 코드의 복장성에 대하여 알아 볼 것이다. 자료구조를 설계하려면 집중해야할 몇몇 가이드 라인이 있다. 동시성 자료구조를 위한 일반적 자료주고는 챕터 6 시작부터 적용하였지만 더많은 것들이 있다. lock free 자료구조를 디자인 할때 참조할 예제를 통하여 몇몇 유용한 가이드 라인을 소개 한다.
lock free 코드의 가장 큰 어려움중에 하나는 메모리 관리이다. 다른 쓰레드가 그것들을 아직 참조 하고 있을때 객체를 삭제 하는것을 피하는것은 필수적이다. 그러나 과도한 메모리를 사용을 피하기 위하여 가능한 한 빨리 객체를 삭제하기를 원한다. 이 챕터에서는 메모리를 안전하게 활용하는 3가지 기술을 보였다. ■ 자료구조에 접근하는 쓰레드가 없을때까지 대기하는것과 삭제를 대기하는 모든 객체를 삭제 하는것 ■ 쓰레드가 특정한 객체에 접근하는것을 식별을 위해 위험한 포인터를 사용하는것 ■ 객체를 참조하는것이 없을때까지 삭제 되지 않을수 있는 객체의 reference-counting 모든 케이스에서 중요한 아이디어는 특정한 객체에 접근하는 많은 쓰레드를 어떻게 추적하는 방법과 어디에서도 더이상 참조되지 않을때 각 객체를 삭제 하는 방법을 사용한다. lock free 자료구조에서 메모리를 재 사용하는 많은 다른 방법이 있다. 예를 들어 이상적인 시나리오는 garbage collector 를 사용하는 것이다. 모드가 더이상 사용되지 않을때 garbage collector 가 노드를 해제하고 그전에는 해제하지 않는다면 알고리즘을 작성하기가 무척 쉬워진다. 다른 방법은 노드를 재사용하고 자료구조가 없어질때 그것들을 해제 한다. 노드가 재사용되기 때문에 메모리공간은 계속 유효하다. 그래서 정의되지 않은 행동(undefined behavior)의 몇몇 어려운 문제를 피할수 있다. 여기에서 다른 문제가 보다 일반적이 되는 단점이 있다. 이문제를 ABA문제라고 부른다.
ABA 문제는 compare/exchange 알고리즘에서 쥐의해야 한다.
- 쓰레드 1은 atomic 변수 x 를 읽고 A 값을 가지고 있는 것을 찾았다.
- 쓰레드 1은 이 값과 관련되어 (그것이 포인터라면) 그것이 가리키는 곳의 값을 읽거나 찾는 연산을 수행한다.
- 쓰레드 1은 OS에 의하여 중지된다.
- 다른 쓰레드가 변수 x을 b 로 값을 변경하는 연산을 수행한다.
- 데이터를 변경한 쓰레드는 A 값과 관련이 있다. 쓰레드1에서 잡고 잇는 값은 더이상 유효하지 않다.
- 쓰레드는 새로운 데이터를 기반으로 변수 x 를 다시 A 로 변경한다. 이것이 포인터라면 새로운객체일것이다. 옛날 것으로 같은 주소로 공유가 일어 났다.
- 쓰레드 1이 다시 수행되고 x 에 compare/exchange로 A 와 비교를 수행한다.(값이 A이기때문에)compare/exchange 는 성공한다. 2번에서 읽은 원래 데이터는 더이상 유효하지 않다. 그러나 쓰레드 1은 알수 있는 방법이 없고 자료구조는 손상되었다. 이문제로 고생하는 알고리즘은 여기에 없다. 그러나 그렇게 동작하는 lock free 알고리즘은 작성하기 쉽다. 이 문제를 피할수 있는 공통 방법은 변수 x와 함께 ABA 카운터도 포함하는것이다. compare/exchange 연산은 하나의 구조 처럼 x 에 더하여 결합된 구조체로 완료 된다. 매번 값은 변경되고 카운터는 증가된다. 그래서 x 가 값을 가지고 있더라도 다른 쓰레드가 x 를 변경하였으면 compare/exchange 는 실패한다. ABA 문제는 free list 를 사용하거나 할당자에 반납하는 방법보다 node 를 재사용하는 알고리즘에서 일반적으로 발생한다.
마지막으로 큐의 예제에서 어떻게 push() 연산을 수행하는 쓰레드가 연산을 수행하기전에 다른 쓰레드 또한 push() 완료를 대기하는것을 확인하였다. 놓고보면 이것은 대기하는 쓰레드가 진행을 못하는 동안 CPU 시간을 소모하는 busy-wait 반복문이다. busy wait 반복문으로 끝난다면 blocking 연산을 수행하고 뮤텍스와 락을 사용하는것이 효율적이다. 알고리즘을 수정하였기때문에 대기하는 쓰레드는 완료되지 못한 단계를 수행하였다 만약 기본 쓰레드가 연산을 완료되기전에 수행하게 된다면 busy-wait 를 없애고 연산은 더이상 blocking 이 아니다. 큐의 예제에서 데이터 멤버를 nonatomic 변수 보다 atomic 변수로 변경하고 값을 설정 하기 위하여 compare/exchange 연산이 필요하다 그러다 더 복잡한 자료구조는 더 큰 변경이 필요로 할것이다.
챕터 6의 lock 기반의 자료구조에 따르며 이 챕터에서는 스택과 큐로 시작하여 다양한 lock free 자료구조의 간단한 구현을 보았다. data race 가 존재하지 않아야 하고 각 쓰레드가 자료구조의 일관된 view 를 보도록 atomic 연산을 통하여 memory ordering 을 어떻게 신경 써야 하는지 확인하였다. lock 기반 자료구조 보다 lock free 자료구조에서 메모리의 관리는 어떻게 더 어려워 졌는지 그것을 처리하는 몇몇 원리에 대해서 확인하였다. 그 연산의 완료를 대기하는 쓰레드를 지원하여 어떻게 대기를 반복을 피하는지를 확인하였다. lock free 자료구조를 설계하는 것은 어려운 일이고 실수하기가 쉽다. 그러나 이런 자료구조는 같은 상황에서 중요한 확장 속성을 가지고 있다. 이챕터에서 예제와 가이드라인을 통하여 lock free 자료구조의 디자인과 research paper 로 부터 하나를 구현하거나 동료가 회사를 그만 두기전에 그 직원이 만든 버그를 찾을 준비가 되었다. 쓰레드 사이에 데이터가 공유되면 쓰레드사이에서 어떻게 데이터를 동기화 하는 방법과 사용해야할 자료구조를 생각할 필요가 있다. 동시성 관련 자료구조를 디자인하여 데이터 구조를 추상화 시킴으로써 남은 코드는 data 동기화보다 data 를 연산을 하는 태스크에 집중할수 있다. 동시성 관련 자료구조에서 동시성 코드로 옮겨 가면서 챕터8에서 이것을 확인해 볼수 있다. 병렬 알고리즘은 성능을 올리기 위하여 여러 쓰레드를 사용한다. 그리고 그 알고리즘은 work 쓰레드가 데이터를 공유하기 위한 동시성 자료구조의 선택은 결정적이다.