language-agnostic - 如何构建无锁队列？

Question

今天我一直在研究无锁队列。我有多个生产者，多个消费者的情况。为了测试，我在 Win32 下使用 Interlocked SList 实现了一个系统，它使我的基于重线程任务的代码的性能提高了一倍。但不幸的是，我希望支持多个平台。在多个平台上互锁本身不是问题，我可以放心地假设我可以毫无问题地互锁。然而，实际的实现让我失望。

最大的问题似乎是您需要保证列表推送/弹出将只使用一个互锁调用。否则，您就会为另一条线留出空间来咬住并搞砸。我不确定微软的实现是如何在幕后工作的，我很想知道更多。

任何人都可以向我指出有用的信息(平台和语言非常不相关)？

除此之外，我很想知道是否可以实现无锁向量。这对我来说会有很大的用处:)
干杯!

编辑:阅读了 Herb 的 DDJ 文章后，我可以看到一个减少的锁队列，它与我已经拥有的锁队列非常相似。但是我注意到最后有一些论文可以使用双重比较和交换(DCAS)操作来完成真正的无锁队列。有没有人使用 cmpxchg8b(或 cmpxchg16b)实现队列？

我现在只是在思考(还没有读过论文)，但是您可以使用该系统同时更新头指针和尾指针，从而避免在 2 个原子操作之间跳转的另一个线程出现任何问题。但是，您仍然需要获取下一个头指针以针对尾指针进行测试，以查看您是否刚刚修改了尾。当另一个线程准备自己这样做时，您如何避免另一个线程更改此信息？这是如何以无锁方式实现的？还是我最好阅读研究论文的不可破译性？ ;)

Answer 1

您可能可以轻松实现有限大小的队列......我最近在考虑并提出了这个设计，但您可能会发现许多其他有趣的想法:(警告:它可能有一些问题!)

队列是指向项目的指针数组

您必须管理 2 个指针(头、尾)，它们以与循环缓冲区相同的方式在队列中工作

如果 head == tail , 没有项目

如果你想 enqueue(ptr) , 互锁交换 tail with NULL ( prev_tail 是交换的值)

如果 prev_tail == NULL ，再试一次

如果 prev_tail + 1 (带环绕)== head ，您的队列已满

否则把你的 ptr在 *prev_tail并分配 prev_tail+1至 tail (注意缓冲区环绕)

为 dequeue()复制 tmp_head=head 并检查 tmp_head == tail

如果为真，则返回，因为队列为空

如果是假的

保存 *tmp_head如 ptr

做一个CAS:比较head与 tmp_head交换 head与 head+1

如果 CAS 失败——启动整个函数

如果成功——返回 ptr

您可以等待头和尾 CAS 操作，但如果队列没有争用，您应该第一次成功，没有不必要的锁。

无限大小的队列“有点”困难；) 但是您应该能够为大多数需求创建一个足够大的队列。