编写单个生产者/单个消费者队列的最有效方式 [英] Most efficient way of writing a single producer/single consumer queue
问题描述
编写一个生产者/消费者队列的最有效方式是，一个线程是生产者，另一个是消费者。在一篇论文中，作者说，它需要一个原子操作来将一个元素插入到他的队列中，但他没有解释如何。
另外，他的队列是一个循环队列，当队列满时生产者等待队列为空时，消费者等待。他怎么能实施这样一个队列。通过原子操作，他是指某种互斥体或只是一个原子变量。注意他说，一个原子操作。
如果您没有实现无锁队列的经验，唯一的答案可以是：最高效（安全）的方式是通过pthreads（mutex或cond var）提供的一个锁。
无锁算法通常会（但不一定）给你一点额外的性能，但它们如果你不确切知道你在做什么，可能会犯错。
另一方面，Linux下的phtreads实现尽可能避免锁定，并使用 futex ，当它需要的时候（同样， futex 是快速的，但你应该知道你在做什么）< 这样的队列每秒传递十万个任务并不困难。这可能看起来有些限制，但是真的如果你需要每秒传递1000万个任务，那么你做错了。理想情况下，您可能会在队列上每秒传递几十到几百个任务（任务更少，但工作组更大）。您想要创建50个任务，每个工作半兆字节数据，而不是2千万个任务处理一个字节的数据。
如果你仍然坚持给无锁实现一个尝试可能出于学术兴趣），您将需要一个原子比较交换操作（在C语言的GCC文档中查找legacy __sync函数，对于C ++，您将使用新的原子操作符）。
Be一定要仔细阅读像ABA这样的微妙细节，对于这些微妙的细节你通常需要某种指针操作（在最低3位存储一个refcount）或者用明确引用计数的双字交换。
或者，无锁队列可以只用原子加或不加任何原子操作来实现（如果你只是为了好奇而感兴趣，请参见快进队列） ，如果你做出一些假设。但是，这些只有在假设成立的情况下才有效，而且它们更容易出错，所以最好远离它们。
What is the most efficient way of writing a producer/consumer queue where one thread is the producer and the other is a consumer. In one paper, the author said that it requires one atomic operation to insert an element into his queue, but he didn't explain how.
Also his queue is a circular queue and the consumer waits if queue is empty while the producer waits if queue is full. How could he have implemented such a queue. By atomic operation, did he mean some kind of mutex or just an atomic variable. Note he said, one atomic operation.
If you have no experience with implementing a lockless queue, the only answer can be: The most efficient (and safe) way is to use a lock, as provided by pthreads (mutex or cond var).
Lockless algorithms will usually (but not necessarily) give you a little extra performance, but they can go terribly wrong if you don't know exactly what you're doing.
On the other hand, the phtreads implementation under Linux avoids locks when possible and uses futex when it needs to (again, futex is something that's fast but where you should know what you're doing).
Such a queue has no trouble passing a hundred thousand tasks per second. This may seem limiting, but really if you need to pass 10 million tasks per second, you are doing it wrong. Ideally you will maybe pass a few dozen to a hundred or so tasks per second on a queue (fewer tasks, but bigger workgroups). You want to e.g. create 50 tasks working on half a megabyte of data each, not 25 million tasks working on one byte of data.
If you still insist on giving a lockless implementation a try (maybe out of academic interest), you will need an atomic compare-exchange operation (look up "legacy __sync functions" in the GCC documentation for C, for C++ you would use the new atomic ops).
Be sure to read up on subtle details like ABA, for which you usually need some kind of pointer manipulation (storing a refcount in the lowest 3 bits) or a double word exchange with an explicit reference count.
Alternatively, a lockless queue can be implemented with only atomic add or without any atomic operations at all (see "fast forward queue" if you're interested just for curiosity), if you make some assumptions. However, these only work if the assumptions hold true, and they are even more error-prone, so best stay away from them.
这篇关于编写单个生产者/单个消费者队列的最有效方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
