logo标签列表

C语言中是否有任何单消费者单生产者无锁队列的实现？

cmultithreadingdata-structureslock-free
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()需要多少时间等。

9个回答
7
如果你担心性能问题，添加malloc（）并不会有所帮助。如果你不担心性能问题，为什么不通过互斥锁来控制对队列的访问呢？你是否实际测量过这种实现的性能？听起来好像你正在走向过早优化的老路。
我同意你的malloc观点，但不同意mutex。锁会导致性能下降。因此，在一个生产者和一个消费者的情况下，无锁操作是可行的，应该使用它。现在这个消费者以后可以应用分片逻辑将数据传输到不同的消费者。锁会导致性能下降。 - siddhusingh
4
您展示的算法之所以能够工作，是因为尽管两个线程共享资源（即队列），但它们以一种非常特殊的方式共享。因为只有一个线程会修改队列的头索引（生产者），而只有一个线程会修改尾索引（当然是消费者），所以您无法获得共享对象的不一致状态。此外，生产者在更新头索引之前将实际数据放入队列中非常重要，消费者在更新尾索引之前读取其想要的数据也很重要。
它之所以能够如此有效地工作，是因为数组是相当静态的；两个线程都可以依赖于元素的存储存在。您可能无法完全替换数组，但您可以更改数组的用途。
也就是说，不要将数据保留在数组中，而是将指针保存到数据中。然后，您可以使用malloc()和free()分配和释放数据项，同时通过数组在线程之间传递引用（指针）。
此外，posix确实支持读取纳秒时钟，虽然实际精度取决于系统。您可以在之前和之后读取这个高分辨率时钟，然后进行减法运算。
4
那个算法肯定需要添加一些内存屏障吧？ - bdonlan
1
是的..他说“生产者在更新头索引之前放入实际数据非常重要，消费者在更新尾索引之前读取它想要的数据也很重要。” - ben
1
@bdonlan：（等人）并非如此。这完全取决于操作顺序和单个生产者、单个消费者的事实。在这些情况下，它是可以正常工作的。 - JustJeff
3
只有在不重新排序写操作的机器上（据我所知，这是所有机器），并且更重要的是在不把写操作移到读操作前面的机器上才会产生这种效果。请注意，编译器更改并不像 CPU 重新排序那样重要。 - ben
@ben：我不相信重新排序可以交换超过几个机器指令的操作。这可能取决于CPU吧。无论如何，实现几乎总是包括访问共享缓冲区，进行索引重新计算（H或T），然后更新索引。可能是索引重新计算在两个关键内存访问之间放置了足够多的其他机器指令，以有效地抑制重新排序效应。 - JustJeff
1
@ben 是正确的：在弱序处理器上，存储器的缓存未命中或争用可能会延迟该存储器 很长时间，使得它之前的许多其他操作变得全局可见。使用 C11 stdatomic 发布存储器（release stores）以防止编译时重排序（即使在 x86 上），以及其他平台上的编译和运行时重排序。 - Peter Cordes
3
你应该看一下FastFlow库。
3

是的。

存在一些无锁多读多写队列。

我已经实现了一个来自Michael和Scott在1996年论文中的队列。

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

  1. 这些使用malloc节点往往会影响性能。
  2. 那个算法使用CAS - CAS会在内存上加锁，因此不如上面的算法。实际上，在很少持有锁的情况下（例如快速锁），CAS等同于多核SpinLock。虽然我想看看它的表现。
 - ben
2

添加malloc会导致性能下降，锁定结构同样有效。这是因为malloc需要在堆上进行一些CAS锁定，因此某些形式的malloc具有自己的锁定，因此您可能正在内存管理器中进行锁定。

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

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

另外，在CPU上interlocked确实是无锁的，但它们会放置内存锁并在指令期间阻塞内存，并经常使流水线停顿。

或者您可以使用每个线程的内存池进行分配。但是，这样一来，您需要让消费者线程偶尔将内存归还给生产者线程。如果使用垃圾回收系统，生产者就可以分配链表节点，并使用链表作为队列。 - Peter Cordes
2
我记得几年前看到过一个看起来很有趣的实现，但现在好像找不到了。 :( 这个无锁实现需要使用 CAS原语，但即使是加锁实现（如果你不想使用CAS原语），性能也非常好——锁只是防止多个读者或多个生产者同时访问队列，生产者仍然不会与消费者竞争。
我记得该队列背后的基本概念是创建一个链表，其中始终有一个额外的“空”节点。这个额外的节点意味着当列表为空时，头和尾指针只会引用相同的数据。我希望我能找到这篇论文，我的解释并没有充分说明算法...
啊哈！
我找到了一个人把算法转录出来了，但没有剩余文章。这可能是一个有用的起点。
最重要的是要阅读 URL 中的细则（搜索“powerpc”），并在开始发明自己的无锁结构时牢记这一点。 - Marco van de Voort
你所描述的是Michael和Scott的工作 - 我从上面评论中的链接看到确实是这个工作；那里的伪代码直接取自论文。虚拟节点的想法实际上来自于瓦卢瓦。 - user82238
2
我使用了一个相当简单的队列实现，满足了您的大部分要求。它使用了一个静态最大大小的字节数组池，然后我们在其中实现了消息。有一个头指针由一个进程移动，有一个尾指针由另一个进程移动。
仍然需要锁，但我们使用的是Peterson's 2-Processor Algorithm，这是相当轻量级的，因为它不涉及系统调用。该锁仅需要非常小的、有界的区域：最多几个CPU周期，因此您永远不会长时间阻塞。
2
我认为分配器可能是性能问题的原因。您可以尝试使用自定义的多线程内存分配器，该分配器使用链表维护释放的块。如果您的块大小不相同，可以实现“Buddy系统内存分配器”，它非常快速。您需要使用互斥锁来同步您的队列（环形缓冲区）。 为了避免过多的同步，您可以尝试在每次访问时将多个值写入/从队列中读取。
如果您仍想使用无锁算法，则必须使用预分配数据或使用无锁分配器。 有一篇关于无锁分配器的论文：“Scalable Lock-Free Dynamic Memory Allocation”，以及一个实现：Streamflow。
在开始无锁相关操作之前，请查看：Circular lock-free buffer。
0
如果您的分配器没有每个CPU内存池，那么在生产者中使用new，在消费者中使用delete的链表将会很糟糕。否则，new和delete将会获取全局锁并相互竞争。我很惊讶Herb Sutter在他的文章中没有提到这个警告。也许他最初是为垃圾回收的C#编写的？ - Peter Cordes
啊，但是如果你看一下，delete并没有在消费者线程中被调用。;) 但是感谢你指出来，我从来没有想过这个问题。 - mondaugen
1
消费者函数将仍未分配的对象返回给其调用者，而不是将其复制到调用者提供的缓冲区或按值返回对象。如果消费者将节点添加到自己的数据结构中，则可以保留它的分配状态。但是，在使用内容后避免泄漏，需要在某个时刻删除它。最有可能的情况是在从队列中取出数据后的几个函数调用之后很快进行。 - Peter Cordes
1
这是真的。我猜作为模板实现，类型很可能是指向先前分配的某些内存的指针。如果你意味着像无锁“环形缓冲区”（例如，这个）可能更好，我完全同意。 - mondaugen
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接