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 回答