Lock-free-Stack 算法探讨

[Reiouf]

这几天看了许多关于 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 不就一直卡死了吗？

总结时间：C++ Concurrency in Action 算法没错，我把 compare-exchage 当成了 CAS ，还是要仔细看一下官方文档比较好 Q_Q

还有人吗 ，我写了个测试程序，开了 20000 个线程做小型运算，系统资源就爆了。

[Reiouf]

怎么没人捏

[Reiouf]

我看了 http://15418.courses.cs.cmu.edu/spring2013/article/46 cmu 的一个作业也是在 while 套 cas 如此解决的。

[piaodazhu]

第一个在倒数第二三行之间有可能出现暂时的断链情况？
第二个我也感觉有问题。
你发那个链接里第一个代码倒是可以理解的。

[Reiouf]

@piaodazhu 你说的是` new_node->next = old_head;` 在执行之前就被 睡掉了的情况吗？确实可能诶
那我把 new_node->next = old_head; 放到 while 里就完美了
你觉得呢

[C47CH]

去看了下 compare_exchange_weak 的定义，如果不相等的话会更新 new_node->next 的值，然后继续比较，最后会完成修改。

[DeltaC]

打开 Cppreference 的 compare_exchange 正巧就是你这个算法的这个问题。
看了下注释，这和编译器版本有关。

> https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

[exch4nge]

贴的第一个代码不对，贴的第二个跟链接里的代码是对的。原因上面 @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 循环里后逻辑是对的。其它问题参考上面的问题列表

[artnowben]

lockfree 队列比较实用，DPDK 里面的实现性能非常高，有官方文档介绍。

[piaodazhu]

学习了！ compare_exchange_weak 和 compare_exchange_strong 还是很不一样的

[Reiouf]

@piaodazhu 我重新看了 cppdocs ，compare_exchange_strong 会在失败的时候置换 expected 值的，他两的差异点在于 week 可能 fail spuriously.

[Reiouf]

@artnowben 害 我先看看书把

[artnowben]

@Reiouf
相信 intel 把 lock free 玩得最溜
http://doc.dpdk.org/guides/prog_guide/ring_lib.html#ring-library

[Reiouf]

C++ concurrency in Actionn 内容真太丰富了，后面看的速度降了好多

[Reiouf]

@artnowben get 不到他们的点