multithreading - 轮询无锁队列的最快无竞争方法是什么？

Question

假设我们有一个单生产者线程单消费者线程无锁队列，并且生产者可能长时间不生产任何数据。当队列中没有任何内容时让消费者线程休眠将是有益的(为了节能和为其他进程/线程释放 CPU)。如果队列不是无锁的，解决这个问题的直接方法是让生产线程锁定一个互斥锁，做它的工作，发出一个条件变量并解锁，读取线程锁定互斥锁，等待条件变量，阅读，然后解锁。但是，如果我们使用无锁队列，那么使用互斥锁的方式完全相同，首先会消除我们从使用无锁队列中获得的性能。

天真的解决方案是让生产者在每次插入队列后锁定互斥锁，通知条件变量，然后解锁互斥锁，将实际工作(插入队列)完全置于锁之外，并让消费者做同样，锁定互斥锁，等待条件变量，解锁它，将所有内容从队列中拉出，然后重复，将队列的读取保持在锁之外。不过这里有一个竞争条件:在读者退出队列和进入休眠之间，生产者可能已经将一个项目插入到队列中。现在读者将进入休眠状态，并可能无限期地停留，直到生产者插入另一个项目并再次向条件变量发出信号。这意味着您有时可能会发现特定项目似乎需要很长时间才能通过队列。如果您的队列始终处于事件状态，这可能不是问题，但如果它始终处于事件状态，您可能会完全忘记条件变量。

AFAICT 的解决方案是让生产者的行为与常规需求锁定队列相同。它应该锁定互斥锁，插入无锁队列，通知条件变量，解锁。但是，消费者的行为应该有所不同。当它唤醒时，它应该立即解锁互斥锁，而不是等到它读取队列。然后它应该尽可能多地拉出队列并处理它。最后，只有当消费者想 sleep 时，才应该锁定互斥锁，检查是否有数据，如果有，则解锁并处理它，如果没有，则等待条件变量。通过这种方式，互斥锁的竞争频率低于锁定队列时的情况，但不存在因数据仍留在队列中而进入休眠状态的风险。

这是最好的方法吗？有替代品吗？

备注 :“最快”我的意思是“最快而不用专门的内核一遍又一遍地检查队列”，但这不适合标题；p

另一种选择 :采用简单的解决方案，但让消费者等待条件变量，超时对应于您愿意容忍的项目通过队列的最大延迟。但是，如果所需的超时时间相当短，则它可能低于操作系统的最短等待时间，或者仍然消耗过多 CPU。

Answer 1

我假设您正在使用来自 Dr Dobbs article 的无锁单生产者单消费者队列。 - 或类似的东西 - 所以我将使用那里的术语。

在这种情况下，您在以“AFAICT”开头的段落中建议的答案很好，但我认为可以稍微优化一下:

在消费者中 - 正如您所说，当消费者耗尽队列并正在考虑 sleep (并且只有那时)时，它会锁定互斥锁，再次检查队列，然后

如果队列中有新项目，则释放互斥锁并继续工作

或在条件变量上阻塞(自然地，当它醒来以找到非空队列时释放互斥锁)。

在生产者中:

先取一份last ，称之为 saved_last

添加项目 new_item像往常一样，然后复制一份 divider指针，称之为 saved_divider .

如果saved_divider的值等于 new_item ，你刚刚插入的对象，那么你的对象已经被消费了，你的工作就完成了。

否则，如果 saved_divider 的值不等于 saved_last ，那么你就不需要唤醒消费者了。这是因为:

在严格添加新对象之后的某个时间，您知道 divider还没有达到new_item或 saved_last

自从您开始插入以来，last只有这两个值

消费者只会在 divider 时停止等于 last

因此，消费者必须仍然醒着，并且会在 sleep 前拿到您的新商品。

否则锁定互斥锁，向 condvar 发出信号，然后释放互斥锁。 (在此处获取互斥体可确保您不会在消费者注意到队列为空和实际阻塞 condvar 之间的时间内向 condar 发出信号。)

这确保了在消费者倾向于保持忙碌的情况下，当您知道消费者仍然醒着(而不是即将休眠)时，您可以避免锁定互斥锁。它还最大限度地减少了持有互斥锁的时间，以进一步降低争用的可能性。

上面的解释很罗嗦(因为我想包括它为什么起作用的解释，而不仅仅是算法是什么)，但是由此产生的代码应该很简单。

当然，它是否真的值得做取决于很多事情，我鼓励您衡量性能是否对您至关重要。 mutex/condvar 原语的良好实现在大多数情况下在内部使用原子操作，因此它们通常只在需要时进行内核调用(最昂贵的位!) - 即如果需要阻塞，或者肯定有一些线程等待 - 因此不调用互斥函数节省的时间可能仅相当于库调用的开销。