代码之家 › 专栏 › 技术社区 › Goz

如何建立无锁队列?

lockless atomic queue language-agnostic

Goz · 技术社区 · 15 年前

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

最大的问题似乎是,您需要确保列表推送/弹出只使用一个互锁调用。否则,你将为另一条线留下空间,让它咬住并把事情搞砸。我不确定微软的实现是如何在幕后运作的,我想知道更多。

有人能告诉我有用的信息吗(平台和语言是相当无关的)?

另外,我想知道是否可以实现无锁向量。那对我有很大的用处:) 干杯!

编辑:在阅读了Herb的DDJ文章之后,我可以看到一个减少的锁队列,它与我已经拥有的锁队列非常相似。然而,我注意到在末尾有一些文件可以使用双重比较和交换(DCAS)操作来执行真正的无锁队列。是否有人使用cmpxchg8b(或cmpxchg16b)实现队列?

我只是在想这一点(还没有读过论文),但您可以使用这个系统同时更新头部和尾部指针,从而避免在两个原子操作之间的另一个线程跳跃出现任何问题。然而,你仍然需要得到下一个头部指针来测试它对尾部指针,看看你是否刚刚修改了尾部。当另一个线程准备自己更改此信息时,如何避免另一个线程更改此信息?这到底是如何以无锁方式实现的?还是我最好读一下研究论文中的不可破译性?;)

5 回复 | 直到 15 年前

viraptor 15 年前

您可以用最少的困难实现一个有限大小的队列…我最近在想这个设计,但你可能会发现很多其他有趣的想法:(警告:它可能有一些问题!)

队列是指向项的指针数组
您必须管理2个指针(头、尾),这些指针与循环缓冲区在队列中的工作方式相同。
如果 head = tail ,没有项目
如果你想 enqueue(ptr) ,互锁交换 尾 带空值( prev_tail 是交换值)
- 如果 prev_tail == NULL 再试一次
- 如果 prev_tail + 1 (带环绕)== 头 ,您的队列已满
- 否则把你的 ptr 在里面 *prev_tail 并赋值 prev_tail+1 到 尾 (当心缓冲带缠绕)
对于 dequeue() 复制一份tmp_head=head并检查 tmp_head == tail
- 如果为真,则返回,因为队列为空
- 如果是假的
  - 节约 *tmp_head 作为 PTR
  - 做一个CAS:比较 头 具有 tmp_head 掉期 头 具有 head+1
  - 如果cas失败--重新启动整个函数
  - 如果成功——返回 PTR

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

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

MikeB 15 年前

我想关于这个话题有一些有趣的讨论 here ,特别是 this thread.

ScaryAardvark 15 年前

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

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

它确实使用C++0X原子,但它应该是(应该是)容易实现与您的特定架构原子OPS(γ-SycC**使用GNU,Maxix* *在Solaris等)。

nos 15 年前

These 伙计们,也许你们能在那里找到灵感。其他有趣的文件是yqueue.hpp和atomic_ptr.hpp

ben 15 年前

Viraptor解决方案是锁定的,我不知道有多个生产者/多个消费者无锁队列算法。