3

我正在阅读 Anthony Williams Concurrency 的 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>();
}
};

让我感到困惑的那一行是 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 语句从下一个节点而不是堆栈顶部的旧头返回数据。

我是否错误地解释了这一点？

4

2 回答 2

3

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

只有当它返回时false，它才会修改old_head

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

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

线程一被换掉（比如说）

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

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

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

其次，这有经典的 ABA 问题。我不会费心解释这一点，因为它有据可查且易于理解。搜索它。

于 2013-06-24T18:48:36.237 回答
1

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

于 2013-06-24T18:47:57.520 回答