linux - 如何实施 ABA 解决方案？

Question

我正在尝试从这里实现 Michael-Scott FIFO 队列。我无法为 ABA 问题实施他们的解决方案。我得到这个错误。

error: incompatible type for argument 1 of '__sync_val_compare_and_swap'

作为参考，我正在使用 linux 机器在英特尔架构上编译它。如果您需要有关我的设置的更多信息，请询问。

似乎sync_val_CAS最多只能处理 32 位值。因此，当我删除他们用于消除 ABA 问题的计数器时，一切都编译并运行良好。

有人知道我应该在这里使用的相关 64 位 CAS 指令吗？

作为另一个问题，是否有更好（更快）的无锁 fifo 队列实现？我遇到了Nir ​​Shavit 等人，这似乎很有趣。我想知道其他人是否看到过类似的努力？谢谢。

Answer 1

GCC，我最后一次查看是在 2009 年，不支持连续双字 CAS。我必须实施内联汇编。

你可以在这里找到我对 M&S 队列的实现（包括在抽象层中 DCAS 的组装实现）和其他无锁数据结构；

http://www.liblfds.org

简单地看一下 Nir ​​Shavit 等人的论文，队列需要安全内存回收，我怀疑你需要实现它 - 它不会内置到队列中。SMR API 将在下一个版本（几周）中可用。

Answer 2

假设 gcc，尝试使用“march”开关。像这样：-march=i686

还有 __sync_bool_compare_and_swap。我不知道它是否更快。

Answer 3

无锁可能不是您想要的，因为无锁不一定是无等待的。如果您需要一个快速的线程安全队列（不是无锁的！），请考虑使用线程构建块 concurrent_queue。