C++ 11 std :: atomic compare_exchange_weak и контейнер стека

Question

Я работаю через Антони Уильямс Книга параллелизма для C++ 11.

Я немного смущен поп-реализацией стека, свободного от блокировки.

template<typename T> 
class lock_free_stack 
{ 
private: 
struct node 
{ 
    std::shared_ptr<T> data; 
    node* next; 
    node(T const& data_): data(std::make_shared<T>(data_)){} 
}; 

std::atomic<node*> head; 

public: 

void push(T const& data) 
{ 
    node* const new_node = new node(data); 
    new_node->next = head.load(); 
    while(!head.compare_exchange_weak(new_node->next, new_node)); 
} 

std::shared_ptr<T> pop() 
{ 
    node* old_head = head.load(); 
    while(old_head && !head.compare_exchange_weak(old_head, old_head->next)); 

      // Does This not return the data of the next node before the head if 
      // compare_exchange_weak returns true 
    return old_head ? old_head->data : std::shared_ptr<T>(); 
} 
}; 

Линия, которая вызывает у меня путаницу, является двумя последними строками поп-функции.

while(old_head && !head.compare_exchange_weak(old_head, old_head->next)); 
    return old_head ? old_head->data : std::shared_ptr<T>(); 

Будет ли функция compare_exchange_weak не меняет old_head к следующему узлу в стеке, если она возвращает истину? Это приведет к возврату, возвращающему данные из следующего узла, а не к старой голове в верхней части стека, когда old_head не является nullptr.

Я интерпретировал это неправильно?

Answer 1

Помимо моего комментария, если compare_exchange_weak удалось, ему удалось обновить head от значения old_head до значения old_head->next и поэтому old_head больше не входит в список, и поэтому может быть правильно вернулся.

Его только тогда, когда он возвращается false, что изменяет значение old_head

EDIT: Показаны вопросы с выше кодом.

Во-первых, если 2 нити попадают в pop и оба чтения head (через head.load()) и получить то же самое значение old_head

Thread один получает выгружена (скажем)

резьбы два несет на бег, треска голова и возврат к вызывающему, а вызывающий затем удаляет значение, которое удерживает узел.

Поток один затем возобновляется и пытается читать old_head->next до звонок compare_exchange_weak.

HOWEVER, old_head указывает на удаляемую память. Неопределенное поведение, вам повезло, если вы segfault.

Во-вторых, это классическая проблема с ABA. Я не собираюсь объяснять это, поскольку его хорошо документированы и поняты. Найдите его.

Answer 2

Когда head.compare_exchange_weak возвращается false, он изменяет old_head.

Когда он возвращает true, он изменяет head и не изменяет old_head.

См http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange и/или http://cpp0x.centaur.ath.cx/atomics.types.operations.req.html#p21