16

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

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

谁能指出我有用的信息（平台和语言无关紧要）？

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

编辑：阅读herb 的DDJ 文章后，我可以看到一个减少的锁定队列，与我已经拥有的非常相似。但是我注意到最后有一些论文可以使用双重比较和交换（DCAS）操作进行真正的无锁队列。有没有人使用 cmpxchg8b （或 cmpxchg16b ）实现队列？

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

4

5 回答 5

11

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

  • 队列是指向项目的指针数组
  • 您必须管理 2 个指针（头、尾），它们在队列上的工作方式与循环缓冲区相同
  • 如果head== tail，则没有项目
  • 如果你愿意enqueue(ptr)，Interlocked-Swap tailwith NULL（prev_tail是交换的值）
    • 如果prev_tail == NULL，再试一次
    • if prev_tail + 1(with wraparound) == 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 操作，但如果队列没有竞争，您应该第一次成功，没有不必要的锁。

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

于 2009-11-12T23:28:42.507 回答
3

我认为这里有一些关于这个主题的有趣讨论，尤其是这个线程。

于 2009-11-12T22:19:55.640 回答
3

您可能想看看 Herb Sutters 的低锁队列实现。

http://www.drdobbs.com/hpc-high-performance-computing/211601363

它确实使用了 c++0x 原子，但它（应该）很容易用您的特定架构原子操作（使用 GNU 的 __sync_*、solaris 上的 atomic_* 等）来实现。

于 2010-03-11T13:14:44.183 回答
2

这些家伙有，也许你可以在那里找到一些灵感。其他有趣的文件是 yqueue.hpp 和 atomic_ptr.hpp

于 2009-11-12T22:13:09.303 回答
1

viraptor 解决方案是锁定，我知道没有多个生产者/多个消费者无锁队列算法。

于 2010-01-19T07:12:45.857 回答