我今天花了很多时间研究无锁队列.我有一个多生产者,多个消费者的情况.为了测试,我使用Win32下的Interlocked SList实现了一个系统,它使我基于线程的高度基于任务的代码的性能翻了一番.不幸的是,我希望支持多个平台.在多个平台上联锁本身不是问题,我可以安全地假设我可以毫无问题地互锁.然而,实际的实施失去了我.
最大的问题似乎是您需要保证列表推送/弹出只使用一个互锁呼叫.否则你会留下空间让另一个线程夹入并搞砸了.我不确定微软的实现如何在幕后工作,并希望了解更多.
任何人都可以指出我有用的信息(平台和语言是非常无关紧要的)？
除此之外,我很想知道它是否可以实现无锁向量.这对我来说有很大的用处:)干杯!
编辑:阅读了草药的DDJ文章,我可以看到一个减少的锁定队列,它与我已经拥有的非常相似.但是我注意到最后有一些文件可以使用双重比较和交换(DCAS)操作进行真正的无锁队列.有没有人使用cmpxchg8b(或cmpxchg16b)实现队列？
我只是在这一点上思考(没有读过论文),但你可以使用这个系统同时更新头部和尾部指针,从而避免在2个原子操作之间跳过另一个线程的任何问题.但是你仍然需要获得下一个头指针来测试尾部指针,看看你是否刚刚修改了尾部.当另一个线程准备这样做时,你如何避免另一个线程更改此信息？这是如何以无锁方式实现的？或者我最好还是阅读一篇研究论文的难以理解的内容？;)
你可能会以最小的难度实现一个有限大小的队列......我最近在考虑这个问题而想出了这个设计,但你可能会发现许多其他有趣的想法:(警告:它可能有一些问题!)
队列是指向项目的指针数组
你必须管理2个指针(head,tail),它们以与循环缓冲区相同的方式在队列中工作
如果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 =头检查tmp_head == tail
如果是,则返回,因为队列为空
如果它是假的
另存*tmp_head为ptr
做一个CAS:比较head与tmp_head互换head使用head+1
如果CAS失败 - 启动整个功能
如果成功 - 返回 ptr
您可以等待头部和尾部CAS操作,但如果队列没有争用,您应该第一次成功,没有不必要的锁定.
无限大小的队列"有点"难度;但是你应该能够为大多数需求创建一个足够大的队列.
京公网安备 11010802040832号 | 京ICP备19059560号-6 