在无锁设置中是否可以实现多生产者、单消费者？
我有一堆线程相互之间进行大量通信。 我希望这是无锁的。
对于每个线程，我希望有一个邮箱，其他线程可以在其中向其发送消息（但只有所有者可以删除消息）。这是多生产者单消费者的情况。我可以在无锁/高性能的情况下做到这一点吗？ （这是一个巨大模拟的内循环。）
I have a bunch of threads that are doing lots of communication with each other.
I would prefer this be lock free.
For each thread, I want to have a mailbox, where other threads can send it messages, (but only the owner can remove messages). This is a multiple-producer single-consumer situation. is it possible for me to do this in a lockfree / high performance matter? (This is in the inner loop of a gigantic simulation.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
无锁多生产者单消费者 (MPSC) 队列是最容易实现的无锁算法之一。
最基本的实现需要一个简单的无锁单链表（SList），只有push（）和flush（）。这些函数在 Windows API 中以 InterlockedFlushSList() 和 InterlockedPushEntrySList() 的形式提供，但您自己也可以轻松实现这些函数。
多个生产者使用 CAS（互锁比较和交换）将项目推送到 SList 上。
单个消费者执行flush()，它使用XCHG（互锁交换）将SList 的头部与NULL 交换。然后，消费者将获得一个按相反顺序排列的项目列表。
要按顺序处理项目，您必须简单地反转从flush()返回的列表，然后再处理它。如果你不关心顺序，你可以简单地立即遍历列表来处理它。
如果您使用自己的函数，请注意以下两点：
1) 如果您使用的系统内存排序较弱（即 PowerPC），则需要在 push() 函数的开头放置一个“释放内存屏障”和一个“获取内存”屏障”位于flush()函数的末尾。
2) 您可以使函数大大简化和优化，因为 SList 的 ABA 问题发生在 pop() 函数期间。如果仅使用push() 和flush()，则SList 不会出现ABA 问题。这意味着您可以将其实现为与非无锁代码非常相似的单个指针，并且不需要 ABA 预防序列计数器。
Lock-free Multiple Producer Single Consumer (MPSC) Queue is one of the easiest lock-free algorithms to implement.
The most basic implementation requires a simple lock-free singly-linked list (SList) with only push() and flush(). The functions are available in the Windows API as InterlockedFlushSList() and InterlockedPushEntrySList() but these are very easy to roll on your own.
Multiple Producer push() items onto the SList using a CAS (interlocked compare-and-swap).
The Single Consumer does a flush() which swaps the head of the SList with a NULL using an XCHG (interlocked exchange). The Consumer then has a list of items in the reverse-order.
To process the items in order, you must simply reverse the list returned from flush() before processing it. If you do not care about order, you can simply walk the list immediately to process it.
Two notes if you roll your own functions:
1) If you are on a system with weak memory ordering (i.e. PowerPC), you need to put a "release memory barrier" at the beginning of the push() function and an "aquire memory barrier" at the end of the flush() function.
2) You can make the functions considerably simplified and optimized because the ABA-issue with SLists occur during the pop() function. You can not have ABA-issues with a SList if you use only push() and flush(). This means you can implement it as a single pointer very similar to the non-lockfree code and there is no need for an ABA-prevention sequence counter.
当然，如果您有一个原子
CompareAndSwap指令：读取消息后，使用线程只需设置
mailbox[i].ready = false; mailbox[i].owned = false;（按顺序）。Sure, if you have an atomic
CompareAndSwapinstruction:After reading a message, the consuming thread just sets
mailbox[i].ready = false; mailbox[i].owned = false;(in that order).这是来自罗切斯特大学的论文，说明了非阻塞并发队列。论文中描述的算法展示了一种制作无锁队列的技术。
Here's a paper from the University of Rochester illustrating a non-blocking concurrent queue. The algorithm described in the paper shows one technique for making a lockless queue.
可能想看看英特尔线程构建模块，我记得在英特尔开发人员的演讲中提到了类似的内容。
may want to look at Intel thread building blocks, I recall being to lecture by Intel developer that mentioned something along those lines.