c++11 std::atomic compare_exchange_weak 和堆栈容器

Question

我正在阅读 Anthony Williams 的 C++11 并发书。

我对无锁栈的pop实现有点迷惑。

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>();
}
};

让我感到困惑的是 pop 函数的最后两行。

    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函数如果返回true会不会把old_head改成栈中的下一个节点？当 old_head 不是 nullptr 时，这将导致 return 语句从下一个节点返回数据，而不是堆栈顶部的旧头。

我是不是理解错了？

Answer 1

除了我的评论，如果 compare_exchange_weak 成功，它设法将 head 从值 old_head 更新为值 old_head->next 并且因此 old_head 不再是列表的一部分，因此可以正确返回。

只有返回false才修改old_head的值

编辑:显示上述代码的问题。

首先，如果 2 个线程进入 pop 并都读取 head(通过 head.load())并获得相同的值老头

线程一被换出(比方说)

线程二继续运行，弹出头部并返回给调用者，调用者然后删除持有该节点的值。

然后线程 1 恢复并尝试读取 old_head->next 甚至调用 compare_exchange_weak。

但是，old_head 指向已被删除的内存。未定义的行为，如果你有段错误，你很幸运。

其次，这是经典的 ABA 问题。我不会费心去解释它，因为它有据可查和理解。搜索它。