我有一堆线程彼此进行大量通信。我希望这是无锁的。
对于每个线程,我想要一个邮箱,其他线程可以向它发送消息,(但只有所有者可以删除消息)。这是一个多生产者单消费者的情况。我可以在无锁/高性能问题上做到这一点吗?(这是在一个巨大模拟的内部循环中。)
无锁多生产者单消费者(MPSC)队列是最容易实现的无锁算法之一。
最基本的实现需要一个简单的无锁单链表 (SList),只有 push() 和 flush()。这些函数在 Windows API 中作为 InterlockedFlushSList() 和 InterlockedPushEntrySList() 可用,但这些函数很容易自行滚动。
使用 CAS(互锁比较和交换)将多个 Producer push() 项放到 SList 上。
Single Consumer 执行一个 flush(),它使用 XCHG(互锁交换)将 SList 的头部与 NULL 交换。然后,消费者有一个反向顺序的项目列表。
要按顺序处理项目,您必须在处理之前简单地反转从 flush() 返回的列表。如果您不关心订单,您可以简单地立即遍历列表来处理它。
如果您推出自己的功能,请注意两点:
1)如果你在一个弱内存排序的系统上(即PowerPC),你需要在push()函数的开头放置一个“释放内存屏障”,在flush()的末尾放置一个“获取内存屏障”。 ) 功能。
2)您可以使函数大大简化和优化,因为 SLists 的 ABA 问题发生在 pop() 函数期间。如果仅使用 push() 和 flush(),则 SList 不会出现 ABA 问题。这意味着您可以将其实现为与非无锁代码非常相似的单个指针,并且不需要 ABA 预防序列计数器。
当然,如果你有一个原子CompareAndSwap
指令:
for (i = 0; ; i = (i + 1) % MAILBOX_SIZE)
{
if ((mailbox[i].owned == false) &&
(CompareAndSwap(&mailbox[i].owned, true, false) == false))
break;
}
mailbox[i].message = message;
mailbox[i].ready = true;
阅读消息后,消费线程只是设置mailbox[i].ready = false; mailbox[i].owned = false;
(按该顺序)。
这是罗切斯特大学的一篇论文,说明了非阻塞并发队列。论文中描述的算法展示了一种制作无锁队列的技术。
可能想看看英特尔线程构建块,我记得英特尔开发人员在讲课时提到了这些方面的内容。