在无锁设置中，多生产者单消费者是否可行？

Question

我有很多线程正在相互通信。我希望这些线程能够无锁。

对于每个线程，我想要一个邮箱，其他线程可以向其发送消息（但只有所有者才能删除消息）。这是一种多生产者单消费者的情况。是否可能以无锁/高性能的方式实现？（这是巨大模拟的内部循环。）

- anon

Answer 1

无锁多生产者单消费者（MPSC）队列是实现最简单的无锁算法之一。

最基本的实现需要一个简单的无锁单向链表（SList），只有push()和flush()两个操作。这些函数在Windows API中可用作InterlockedFlushSList()和InterlockedPushEntrySList()，但也很容易自己实现。

多个生产者使用CAS（比较并交换）操作将项推送到SList中。

单个消费者通过使用XCHG（交换）操作将SList的头部与NULL交换来执行flush()操作。然后消费者会得到一个按相反顺序排列的项目列表。

要按顺序处理项目，您只需在处理之前反转从flush()返回的列表即可。如果您不关心顺序，可以立即遍历列表以处理它。

如果您自己实现函数，请注意以下两点：

1）如果您在具有弱内存排序（例如PowerPC）的系统上，则需要在push()函数开头放置“释放内存屏障”，并在flush()函数末尾放置“获取内存屏障”。

2）您可以使函数变得更简化和优化，因为SLists的ABA问题出现在pop()函数期间。如果您仅使用push()和flush()，则不能出现SList的ABA问题。这意味着您可以将其实现为单指针，非常类似于非无锁代码，而不需要ABA预防序列计数器。

- Adisak

---

你总是需要获取/释放屏障（或C++11释放/获取负载而无需全局屏障），但在x86上，它们编译为零条额外指令，并且只能防止编译时重排序。http://preshing.com/20120625/memory-ordering-at-compile-time/. - Peter Cordes

是的...轻量级同步/编译器屏障/获取/释放是编写无锁代码时需要注意的内容。 - Adisak

Answer 2

当然，如果你有一个原子性的 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;。

- caf

---

你需要在 ready = true/false 和 owned = false 设置上进行获取/释放内存屏障。以及在 CompareAndSwap 中，但通常这只是函数的一部分。 - tony

这完全取决于您的架构内存排序规则。如果写入与从同一处理器发出的其他写入不重新排序（这很常见），那么使用CompareAndSwap的内存屏障本身就足以确保正确性。 - caf

一个RMW原子操作并不一定比使用互斥锁的操作更快。如果你想要速度更快的无锁操作，那么你至少需要一个不使用RMW或者顺序一致性原子操作（也就是只用release和acquire）的算法。 - Carlo Wood

Answer 3

这是一篇来自罗切斯特大学的论文，介绍了一种非阻塞并发队列。论文中描述的算法展示了一种制作无锁队列的技术。请查看论文。

- Reed Copsey

---

Java的ConcurrentLinkedQueue实现了该论文中的算法，供您参考。 - Will Hartung

我相信这也大致是.NET中net ConcurrentQueue<T>实现的基础：http://blogs.msdn.com/pfxteam/archive/2010/01/26/9953725.aspx - Reed Copsey

看起来链接坏了！这是罗切斯特大学论文的更新链接（PDF可以在顶部下载）。 - undefined

Answer 4

你可能想要看一下英特尔线程构建模块，我记得曾经听过一位英特尔开发者的讲座，提到了类似的内容。

- Anycorn