액션 북의 동시성에서 분리 된 참조 카운트를 사용하여 잠금없는 스택 구현

Question

앤서니 윌리엄스의 액션 북에서의 동시성 (Concurrency)에서, 그는 split reference count를 사용하여 lock free 스택을 구현합니다. 머리 노드의 초기로드 후. 그는 아래 코드에 나열된 메소드 호출 increase_head_count를 사용합니다.

counted_node_ptr old_head = head.load(); 
increase_head_count(old_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)); 

    old_counter.external_count = new_counter.external_count; 
} 

이 링크 https://github.com/subjam/concurrency-in-action/blob/master/ch7/stack_ref.cpp에서 전체 구현을 찾을 수 있습니다.

내 질문은, 하나 이상의 스레드가 동시에 pop()을 실행하려고 시도하고 모든 스레드가 헤드 노드를 읽은 다음 하나만 종료 될 때까지 실행되고 이후에이 구현이 어떻게 작동하는지 다른 질문이 실행되면 발생합니다.

저는 꽤 오랫동안 여기에 갇혀 있습니다. 누군가 이해하면 도와 주시면 정말 기뻐하실 것입니다.

Answer 1

while 절에서 old_counter가 여전히 new_counter와 같으면 head가 new_counter로 설정됩니다. 한 번에 성공하는 단일 스레드의 경우입니다.

이 메서드에 동시에 액세스하는 다른 스레드의 경우 compare_exchange_strong()은 루프 반복을 유발하는 false를 반환합니다. 그러나 old_counter의 내용에 대해 머리글을 복사합니다.

이것은 다른 (실패한) 스레드에 대한 다음 루프에서 old_counter가 head의 현재 내용으로 업데이트되었음을 ​​의미합니다.