V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Reiouf
V2EX  ›  程序员

Lock-free-Stack 算法探讨

  •  
  •   Reiouf · 2023-05-17 20:10:09 +08:00 · 1334 次点击
    这是一个创建于 546 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  2023-05-18 11:02:35 +08:00
    总结时间:C++ Concurrency in Action 算法没错,我把 compare-exchage 当成了 CAS ,还是要仔细看一下官方文档比较好 Q_Q
    第 2 条附言  ·  2023-05-18 11:50:54 +08:00
    还有人吗 ,我写了个测试程序,开了 20000 个线程做小型运算,系统资源就爆了。
    14 条回复    2023-05-18 16:11:52 +08:00
    Reiouf
        1
    Reiouf  
    OP
       2023-05-17 20:21:39 +08:00
    怎么没人捏
    Reiouf
        2
    Reiouf  
    OP
       2023-05-17 20:24:11 +08:00
    我看了 http://15418.courses.cs.cmu.edu/spring2013/article/46 cmu 的一个作业也是在 while 套 cas 如此解决的。
    piaodazhu
        3
    piaodazhu  
       2023-05-17 20:38:47 +08:00
    第一个在倒数第二三行之间有可能出现暂时的断链情况?
    第二个我也感觉有问题。
    你发那个链接里第一个代码倒是可以理解的。
    Reiouf
        4
    Reiouf  
    OP
       2023-05-17 21:00:12 +08:00
    @piaodazhu 你说的是` new_node->next = old_head;` 在执行之前就被 睡掉了的情况吗?确实可能诶
    那我把 new_node->next = old_head; 放到 while 里就完美了
    你觉得呢
    C47CH
        5
    C47CH  
       2023-05-17 21:17:22 +08:00   ❤️ 1
    去看了下 compare_exchange_weak 的定义,如果不相等的话会更新 new_node->next 的值,然后继续比较,最后会完成修改。
    DeltaC
        6
    DeltaC  
       2023-05-17 21:44:34 +08:00
    打开 Cppreference 的 compare_exchange 正巧就是你这个算法的这个问题。
    看了下注释,这和编译器版本有关。

    > https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange
    exch4nge
        7
    exch4nge  
       2023-05-17 22:03:25 +08:00   ❤️ 1
    贴的第一个代码不对,贴的第二个跟链接里的代码是对的。原因上面 @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
        8
    artnowben  
       2023-05-17 22:11:05 +08:00
    lockfree 队列比较实用,DPDK 里面的实现性能非常高,有官方文档介绍。
    piaodazhu
        9
    piaodazhu  
       2023-05-18 08:59:50 +08:00
    学习了! compare_exchange_weak 和 compare_exchange_strong 还是很不一样的
    Reiouf
        10
    Reiouf  
    OP
       2023-05-18 11:01:11 +08:00
    @piaodazhu 我重新看了 cppdocs ,compare_exchange_strong 会在失败的时候置换 expected 值的,他两的差异点在于 week 可能 fail spuriously.
    Reiouf
        11
    Reiouf  
    OP
       2023-05-18 11:13:48 +08:00
    @artnowben 害 我先看看书把
    artnowben
        12
    artnowben  
       2023-05-18 11:21:27 +08:00
    Reiouf
        13
    Reiouf  
    OP
       2023-05-18 16:07:48 +08:00
    C++ concurrency in Actionn 内容真太丰富了,后面看的速度降了好多
    Reiouf
        14
    Reiouf  
    OP
       2023-05-18 16:11:52 +08:00
    @artnowben get 不到他们的点
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3892 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:14 · PVG 12:14 · LAX 20:14 · JFK 23:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.