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

Question

我有一堆线程正在彼此进行大量的沟通。我希望这是免费的。

对于每个线程，我想要一个邮箱，其他线程可以向其发送消息（但只有所有者可以删除消息）。这是一个多生产者单一消费者的情况。我可以在无锁/高性能的事情上做到这一点吗？ （这是一个巨大模拟的内循环。）

Answer 1

当然，如果你有一个原子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;（按此顺序）。

Answer 2

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

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

使用CAS（互锁比较和交换）将多个生产者push（）项目放到SList上。

Single Consumer执行flush（），使用XCHG（互锁交换）将SList的头部与NULL交换。然后，消费者具有相反顺序的项目列表。

要按顺序处理项目，必须在处理之前简单地反转从flush（）返回的列表。如果您不关心订单，您可以立即走到列表中进行处理。

如果您推出自己的功能，请注意以下两点

1）如果您使用的是内存排序较弱的系统（即PowerPC），则需要在push（）函数的开头设置“释放内存屏障”，并在刷新结束时设置“获取内存屏障”（ ）功能。

2）您可以使功能大大简化和优化，因为SLA的ABA问题发生在pop（）函数期间。如果仅使用push（）和flush（），则不能在SList中出现ABA问题。这意味着您可以将其实现为与非lockfree代码非常相似的单个指针，并且不需要ABA防止序列计数器。

Answer 3

这是一个paper from the University of Rochester illustrating a non-blocking concurrent queue。本文中描述的算法显示了一种制作无锁队列的技术。

Answer 4

我可能想看看英特尔的线程构建模块，我记得英特尔开发人员正在讲述这些内容。