11

我有一堆线程彼此进行大量通信。我希望这是无锁的。

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

4

4 回答 4

10

无锁多生产者单消费者（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 预防序列计数器。

于 2010-09-30T02:53:36.800 回答
3

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

于 2010-01-28T02:12:31.170 回答
2

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

于 2010-01-28T02:01:27.907 回答
0

可能想看看英特尔线程构建块，我记得英特尔开发人员在讲课时提到了这些方面的内容。

于 2010-01-28T01:57:46.273 回答