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

Question

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

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

AFAICT解决方案是让生产者的行为与使用常规需求锁定队列的行为相同.它应该锁定互斥锁,插入无锁队列,发出条件变量信号,解锁.但是,消费者的行为应该不同.当它唤醒时,它应立即解锁互斥锁,而不是等到它读取队列.然后它应尽可能多地拉出队列并处理它.最后,只有当消费者想要进入睡眠状态时,它是否应该锁定互斥锁,检查是否有任何数据,然后如果解锁并处理它,或者如果没有,则等待条件变量.这样,互斥锁的争用频率低于锁定队列的频率,但是没有数据仍然留在队列中的睡眠风险.

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

注意:通过'最快',我的意思是'最快没有专门核心来反复检查队列',但这不适合标题; p

一种替代方案:使用天真的解决方案,但让消费者等待条件变量,其超时对应于您愿意容忍通过队列的项目的最大延迟.如果所需的超时时间相当短,则可能低于操作系统的最短等待时间,或者仍然消耗过多的CPU.

Answer 1

我假设您正在使用Dobbs 博士文章中的无锁单生产者单消费者队列- 或类似的内容 - 所以我将使用那里的术语。

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

• 在消费者中 - 正如你所说，当消费者耗尽队列并考虑睡眠（只有那时）时，它会锁定互斥体，再次检查队列，然后
  • 如果队列中有新项目，则释放互斥体并继续工作
  • 或者阻塞条件变量（当它醒来发现一个非空队列时，自然地释放互斥体）。
• 在生产者中：
  • 首先复制一份last，调用它saved_last
  • 像往常一样添加项目new_item，然后获取指针的副本divider，将其命名为saved_divider。
  • 如果 的值saved_divider等于new_item您刚刚插入的对象，那么您的对象已经被消耗，并且您的工作已完成。
  • 否则，如果 的值saved_divider不等于saved_last，则无需唤醒消费者。这是因为：
    • 在严格添加新对象之后的某个时间，您知道divider尚未达到new_item或saved_last
    • 自从您开始插入以来，last只有这两个值
    • 消费者只有在divider等于时才会停止last
    • 因此，消费者必须仍然清醒，并且会在睡觉前拿到您的新商品。
  • 否则锁定互斥锁，向 condvar 发出信号，然后释放互斥锁。（在这里获取互斥锁可以确保您在消费者注意到队列为空和实际阻塞 condvar 之间的时间内不会向 condar 发出信号。）

这可以确保，在使用者往往保持忙碌的情况下，当您知道使用者仍然醒着（并且不打算睡觉）时，您可以避免锁定互斥体。它还最大限度地减少了互斥锁的持有时间，以进一步减少争用的可能性。

上面的解释相当冗长（因为我想解释它为什么起作用，而不仅仅是算法是什么），但由此产生的代码应该非常简单。

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