如何构建无锁队列？

Question

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

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

有没有人能告诉我有用的信息(平台和语言无关紧要)？

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

编辑:读过herb的DDJ文章后，我可以看到一个简化的锁队列，它与我已经拥有的锁队列非常相似。然而，我注意到在最后有一些论文可以使用双重比较和交换(DCAS)操作来实现真正的无锁队列。有没有人使用cmpxchg8b (或cmpxchg16b )实现过队列？

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

Answer 1

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

• 队列是指向项的指针数组，您必须管理两个指针(头、尾)，它们以与循环缓冲区相同的方式在队列中工作如果
• head == tail，则没有项

H19如果您要enqueue(ptr)，互锁交换tail with NULL (prev_tail是交换值)

• 如果prev_tail == NULL
• 如果prev_tail + 1 (带环绕) == ，head，您的队列是full
• otherwise，将您的ptr放入*prev_tail，并将prev_tail+1赋值给tail (注意缓冲区缓冲区

​

• dequeue()制作副本并检查ptr
• do
  • 如果为真，则返回原因是队列为空，如果为假则将D40保存为ptr
  • do a CAS:将D44与D45与head+1
  • if CAS交换失败--在H250上启动整个函数如果成功，则将H151保存为ptr
  • do a CAS --在H250上启动整个函数--返回ptr

​

​

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

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

Answer 2

我认为关于这个话题有一些有趣的讨论，特别是here，尤其是this thread.

Answer 3

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

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

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