C++ 实现无锁队列 - Luyu Huang's Tech Blog

[luyuhuang]

https://luyuhuang.tech/2022/10/30/lock-free-queue.html?

前一篇文章中我们讨论了 C++ 中原子变量的内存顺序, 现在我们来看看原子变量和内存顺序的应用 – 无锁队列. 本文介绍单写单读和多写多读的无锁队列的简单实现, 从中可以看到无锁数据结构设计的一些基本思路.何谓无锁为了实现一个线程安全的数据结构, 最简单的方法就是加锁. 对于队列来说, 应该对入队和出队操作加锁....

[djh-sudo]

Thanks share Memory Order knowledge!

[Scarlett-Jns]

受益匪浅

[rfhits]

请问解决了 ABA problem 吗？
如果 thread A 在 push 时候，还未执行到 (1)，但是被调度出去，此时 tail 值为 tail_old
然后 thread B 和 thread C 对 queue 修改，将 queue 写满后退出，tail 依旧为 tail_old
thread A 成功执行 cas，把 tail 的值更新成为一个和 head 一样的值，现在 tail==head，队列全满

[rfhits]

请问 (3) 上面一行 w=t 有什么作用呢？看起来直接 write.cas(t, w+1%cap) 就够了

        do
        {
            w = t;
        } while (!write.compare_exchange_weak(w, (w + 1) % Cap)); // (3), (3) synchronizes-with (4)

[rfhits]

compare_exchange_* 如果在失败的时候会自动 load atomic 到 expected 中，不需要再 while 判断为 false 后，再 load 一遍

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