이 자물쇠가없는 스택 클래스의 '삭제'노드가 경쟁 조건을 유발하는 이유는 무엇입니까? 7.2.1 절에서 앤서니 윌리엄스 "액션 C++ 동시성"라는 제목의 책에서

Question

는 잠금이없는 스택 구현이 나열됩니다

이

template <typename T> 
class lock_free_stack { 
    struct node { 
     shared_ptr<T> data_; 
     node* next_; 
     node(const T& data) : data_(make_shared(data)) {} 
    }; 
    atomic<node*> head_; 
public: 
    void push(const T& data) 
    { 
     node* new_node = new node(data); 
     new_node->next_ = head_.load(); 
     while(!head.compare_exchange_weak(new_node->next_, new_node)); 
    } 
    shared_ptr<T> pop() 
    { 
     node* old_head = head_.load(); 
     while (old_head && 
       !head_.compare_exchange_weak(old_head, head_->next_)); 
     return old_head ? old_head->data_ : shared_ptr<T>(); 
    } 
}; 

다음 섹션 7.2.2에서, 저자는 말한다. " .. pop()에서 우리는 하나의 스레드가 노드를 삭제하는 경쟁 조건을 피하기 위해 노드 누설을 선택했다. 반면 다른 스레드는 아직 참조 해제하려고하는 포인터를 보유하고있다. "

1) 다음과 같은 팝업() 함수 경쟁 조건이 발생할 왜 이러한 시나리오가 일어날 이유를 이해하지 않습니다

shared_ptr<T> pop() 
{ 
    node* old_head = head_.load(); // (1) 
    while (old_head && 
      !head_.compare_exchange_weak(old_head, head_->next_)); // (2) 
    shared_ptr<T> res; // (3) 
    if (old_head) { 
     res.swap(old_head->data); 
     delete old_head; 
     return res; 
    } else { 
     return {}; 
    } 
} 

2) 어떻게 오는 팝업을 호출 다중 스레드() 동시에 'old_head'변수는 line (3) 뒤에 동일한 노드 객체를 가리킬 수 있습니까?

Answer 1

스레드 1은 (2)로 진행됩니다. 그것은 head_->next을 평가하기 시작합니다. 레지스터에 head_을로드 한 다음 우선 순위를 포기합니다.

스레드 2는 함수의 처음부터 끝까지 진행됩니다. 삭제를 통해 head_을 존재에서 제거하고 head_의 내용을 반환합니다.

스레드 1이 깨어납니다. ->next 필드를 가져 오는 레지스터에 head_이옵니다. 그러나 스레드 2는 이미 head_이 가리키는 데이터를 삭제했으며, 우리는 매달린 포인터를 따라갔습니다.