11

我正在编写一个带有消费者线程和生产者线程的程序，现在看来队列同步在程序中是一个很大的开销，我寻找了一些无锁队列实现，但只找到了 Lamport 的版本和 PPoPP 上的改进版本08:

enqueue_nonblock(data) {
    if (NULL != buffer[head]) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}

dequeue_nonblock(data) {
    data = buffer[tail];
    if (NULL == data) {
        return EWOULDBLOCK;
    }
    buffer[tail] = NULL;
    tail = NEXT(tail);
    return 0;
}

两个版本都需要为数据预先分配数组，我的问题是是否有任何使用 malloc() 动态分配空间的单消费者单生产者无锁队列实现？

另一个相关的问题是，我如何测量队列同步中的确切开销？比如pthread_mutex_lock()需要多少时间等等。

4

9 回答 9

7

如果您担心性能，将 malloc() 添加到组合中将无济于事。如果您不担心性能，为什么不简单地通过互斥锁控制对队列的访问。您是否实际测量过这种实现的性能？对我来说，这听起来好像你走的是过早优化的熟悉路线。

于 2009-06-13T13:30:44.240 回答
4

您展示的算法能够工作，因为虽然两个线程共享资源（即队列），但它们以非常特殊的方式共享它。因为只有一个线程改变了队列的头索引（生产者），并且每个线程都改变了尾索引（当然是消费者），所以您无法获得共享对象的不一致状态。同样重要的是，生产者在更新头部索引之前放入实际数据，消费者在更新尾部索引之前读取它想要的数据。

它的工作原理和 b/c 一样好，数组是相当静态的；两个线程都可以依靠存储的元素。您可能无法完全替换数组，但您可以做的是更改数组的用途。

即，不是将数据保存在数组中，而是使用它来保存指向数据的指针。然后您可以 malloc() 和 free() 数据项，同时通过数组在线程之间传递对它们的引用（指针）。

此外，posix 确实支持读取纳秒时钟，尽管实际精度取决于系统。您可以在前后读取这个高分辨率时钟，然后减去。

于 2009-06-13T13:21:15.400 回答
3

是的。

存在许多无锁多读多写队列。

Michael 和 Scott 从他们 1996 年的论文中实现了一个。

我将（经过更多测试）发布一个小型的无锁数据结构库（C 语言），其中将包含这个队列。

于 2009-07-20T08:52:36.040 回答
3

你应该看看 FastFlow 库

于 2010-04-22T19:08:26.943 回答
2

我记得几年前看过一个看起来很有趣的东西，但现在我似乎找不到了。:( 提出的无锁实现确实需要使用CAS 原语，尽管即使锁定实现（如果您不想使用 CAS 原语）也具有相当好的性能特征——锁只会阻止多个读取器或多个生产者同时进入队列，生产者仍然从未与消费者竞争。

我确实记得队列背后的基本概念是创建一个链表，其中总是有一个额外的“空”节点。这个额外的节点意味着列表的头和尾指针只会在列表为空时引用相同的数据。我希望我能找到这篇论文，我的解释不是在做算法正义......

啊哈！

我发现有人在没有本文其余部分的情况下转录了该算法。这可能是一个有用的起点。

于 2009-06-13T13:39:37.540 回答
2

我使用了一个相当简单的队列实现来满足您的大多数标准。它使用了一个静态最大大小的字节池，然后我们在其中实现了消息。有一个进程将移动的头指针和另一个进程将移动的尾指针。

仍然需要锁，但我们使用了 Peterson 的 2-Processor Algorithm，它非常轻量级，因为它不涉及系统调用。只有非常小的、有界的区域才需要锁：最多几个 CPU 周期，所以你永远不会长时间阻塞。

于 2009-06-13T13:46:31.160 回答
2

我认为分配器可能是一个性能问题。您可以尝试使用自定义多线程内存分配器，它使用链表来维护释放的块。如果你的块不是（几乎）相同的大小，你可以实现一个“好友系统内存分配器”，女巫非常快。您必须将队列（环形缓冲区）与互斥锁同步。

为避免过多的同步，您可以尝试在每次访问时向队列写入/读取多个值。

如果您仍想使用无锁算法，那么您必须使用预分配数据或使用无锁分配器。有一篇关于无锁分配器“Scalable Lock-Free Dynamic Memory Allocation”的论文，还有一个实现Streamflow

在开始使用无锁的东西之前，请查看：循环无锁缓冲区

于 2009-06-13T17:19:12.210 回答
2

添加 malloc 会扼杀您可能获得的任何性能提升，而基于锁的结构将同样有效。之所以如此，是因为 malloc 在堆上需要某种 CAS 锁，因此某些形式的 malloc 有自己的锁，因此您可能会锁定在内存管理器中。

要使用 malloc，您需要预先分配所有节点并使用另一个队列管理它们......

请注意，您可以制作某种形式的可扩展数组，如果它被扩展，则需要锁定。

此外，虽然互锁在 CPU 上是无锁的，但它们确实会在指令期间放置内存锁并阻塞内存，并且经常使流水线停止。

于 2010-02-04T02:11:42.230 回答
0

此实现使用 C++ 的 new 和 delete，可以使用 malloc 和 free 轻松地将其移植到 C 标准库：

http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448?pgno=2

于 2018-04-24T14:26:27.430 回答