如何建立无锁队列? [英] How do I build a lockless queue?

问题描述

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

I've spent today looking into lockless queues. I have a multiple producer, multiple consumer situation. I implemented, for testing, a system using the Interlocked SList thing under Win32 and it doubled the performance of my heavily threaded task based code. Unfortunately, though, I wish to support multiple platforms. Interlocking on multiple platforms itself is not a problem and I can safely assume I can interlock without problems. However the actual implementation loses me.

最大的问题似乎是您需要确保列表推送/弹出仅使用一个互锁的呼叫.否则，您将留出空间来夹住另一根线并拧紧东西.我不确定Microsoft实施如何在后台运行，并且想了解更多.

The big problem appears to be that you need to guarantee a list push/pop will use only one Interlocked call. Otherwise you are leaving space for another thread to nip in and screw things up. I'm unsure how the microsoft implementation works under-the-hood and would love to know more.

有人能指出我有用的信息吗(平台和语言无关紧要)?

Can anyone point me towards useful information (Platform and language are pretty irrelevant)?

我想知道是否有可能实现无锁向量.那对我将有巨大的用处:) 干杯！

Added to that I'd love to know if its possible to implement a lockless vector. That would have huge amounts of use for me :) Cheers!

阅读了Herb的DDJ文章后，我可以看到减少了的锁队列，该队列与我已经拥有的锁队列非常相似.但是，我注意到最后有一些论文可以使用双重比较和交换(DCAS)操作进行真正的无锁排队.是否有人使用cmpxchg8b(或cmpxchg16b)实现了队列?

Having read herb's DDJ article I can see a reduced lock queue that is pretty similar to the one I already had. However I notice that there are papers at the end that can do the true lockless queue'ing using a double compare-and-swap (DCAS) operation. Has anyone implemented a queue using cmpxchg8b (or cmpxchg16b for that matter)?

这时我只是在沉思(尚未阅读论文)，但是您可以使用该系统同时更新头和尾指针，从而避免在2个原子操作之间跳转的另一个线程引起任何问题.但是，您仍然需要获取下一个头部指针，以针对尾部指针进行测试，以了解您是否刚刚修改了尾部.在另一个线程本身准备这样做时，如何避免另一个线程更改此信息?如何精确地以无锁方式实现?还是我更好地阅读了一份研究论文的不可理解性? ;)

I'm just musing at this point (having not read the papers) but you could use this system to update the head and tail pointer simultaneously and thus avoid any issues with another thread jumping inbetween the 2 atomic operations. However you still need to get the next head pointer to test that against the tail pointer to see if yo have just modified the tail. How do you avoid another thread changing this information while the other thread is preparing to do so itself? How exactly is this implemented in a lockless way? Or am i better off reading the undecipherability that is a research paper? ;)

推荐答案

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

You could probably implement a limited-size queue with least difficulty... I was thinking about it lately and came up with this design, but you can probably find many other interesting ideas: (WARNING: it might have some issues!)

• 队列是指向项目的指针的数组
• 您必须管理2个指针(头，尾)，它们在队列中的工作方式与循环缓冲区相同.
• 如果head == tail，则没有项目
• 如果要enqueue(ptr)，则将互锁交换tail与NULL(prev_tail是交换值)一起使用
  • 如果prev_tail == NULL，请重试
  • 如果prev_tail + 1(带有环绕)== head，则您的队列已满
  • 否则，将您的ptr放入*prev_tail并将prev_tail+1分配给tail(请注意缓冲区环绕)
  • the queue is an array of pointers to items
  • you have to manage 2 pointers (head, tail) which work over the queue in the same way as a circular buffer
  • if head == tail, there are no items
  • if you want to enqueue(ptr), Interlocked-Swap tail with NULL (prev_tail is the swapped value)
    • if prev_tail == NULL, try again
    • if prev_tail + 1 (with wraparound) == head, your queue is full
    • otherwise put your ptr in *prev_tail and assign prev_tail+1 to tail (watch out for buffer wrap-around)
    • 如果为真，则返回，因为队列为空
    • 如果它是假的
      • 将*tmp_head另存为ptr
      • 执行CAS:比较head与tmp_head交换head与head+1
      • 如果CAS失败-重新启动整个功能
      • 如果成功-返回ptr
      • if it's true, return because the queue is empty
      • if it's false
        • save *tmp_head as ptr
        • do a CAS: compare head with tmp_head swap head with head+1
        • if CAS failed -- start the whole function over
        • if it succeeded -- return ptr

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

        You can wait on both head and tail CAS operations, but if the queue is not contended, you should succeed the first time, without unnecessary locks.

        大小不限的队列要困难一些；)但是您应该能够为大多数需求创建足够大的队列.

        Unlimited-size queues are "a bit" harder ;) But you should be able to create a big-enough queue for most needs.

        这篇关于如何建立无锁队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！