Lock-free-Stack 算法探讨

这几天看了许多关于 lock-free 和 memory-reordering 的资料，在看到 C++ Concurrency in Action 时候写了一个自己理解的 lock-free 结构。


class LockFreeStack
{
    using T = int;

private:
    struct Node
    {
        T val;
        Node *next;
    };

public:
    LockFreeStack() : head(nullptr), length(0){};

    void Push(const T &val)
    {
        Node *new_node = new Node{val, nullptr};
        Node *old_head = nullptr;
        do
        {
            old_head = head.load(std::memory_order_release);
        } while (!head.compare_exchange_strong(old_head, new_node, std::memory_order_acquire, std::memory_order_acquire));
        new_node->next = old_head;
        length.fetch_add(1, std::memory_order_relaxed);
    }
};

但是和书上不一致：

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); // 1
        new_node->next=head.load(); //2 
        while(!head.compare_exchange_weak(new_node->next,new_node)); //3
    } 
};

我就很疑惑，他算法中一个线程 A 如果执行到 @2 被休眠，如果其他 push 线程直接执行 @2 ，@3 ，修改了 head atomic 值，线程 A 不就一直卡死了吗？

exch4nge

2023-05-17 22:03:25 +08:00

贴的第一个代码不对，贴的第二个跟链接里的代码是对的。原因上面 @piaodazhu @C47CH 说了，虽然重复我也说一下。

贴的第一个：
- head 已经在 compare exchange 修改了，不过 new_node 的 next 没设置，导致断了
- 用 compare_exchange_weak 就好，不过我不确定你用的 memory order 对不对
- 这里 length 更新会比实际慢，所以会有差异
- while 里的 old_head = head.load(std::memory_order_release); 除了第一次有用外，没什么用，应该放在 do 上面

贴的第二个，解答你的问题。
如果线程 A 如果执行到 @2 被休眠，如果其他 push 线程直接执行 @2 ，@3 修改了 head atomic 值，线程 A 不就一直卡死了吗？
不会卡死，因为 compare_exchange_weak 会失败，同时会设置 new_node->next 的值。所以是对的。

4L 你的问题：new_node->next = old_head 放到 while 循环里后逻辑是对的。其它问题参考上面的问题列表

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/940789