无锁队列轮询最快的无竞争方法是什么？
假设我们有一个单生产者线程的单用户线程无锁队列，并且生产者可以长时间运行而不产生任何数据。当队列中没有任何东西时，让使用者线程休眠将是有益的(为了节省电力和为其他进程/线程释放CPU )。如果队列不是无锁的，那么解决此问题的简单方法是让生成线程锁定互斥锁，完成其工作，发送条件变量并解锁，以及读取线程锁定互斥锁，等待条件变量，执行其读取，然后解锁。但是，如果我们使用的是无锁队列，使用互斥锁的方式完全相同，那么首先使用无锁队列将消除我们所获得的性能。
天真的解决方案是让生产者在每次插入队列后锁定互斥锁，向条件变量发送信号，然后解锁互斥锁，将实际工作(插入队列)完全保持在锁之外，并让使用者也这样做，锁定互斥锁，等待条件变量，解锁，将所有内容从队列中取出，然后重复，保持队列外面的队列读取。不过，这里有一个竞争条件:在读取器从队列中取出队列和进入休眠状态之间，生产者可能已经将一项插入到队列中。现在，读取器将进入睡眠状态，并且可能会无限期地停留，直到生产者插入另一项并再次发出条件变量的信号。这意味着，有时您可能会得到一些特定的物品，似乎需要很长时间才能在队列中穿行。如果您的队列始终处于活动状态，这可能不是一个问题，但是如果它始终处于活动状态，您可能会完全忘记条件变量。
AFAICT的解决方案是生产者的行为与正常的需求锁定队列一样。它应该锁定互斥锁，插入无锁队列，向条件变量发送信号，解锁。然而，消费者的行为应该有所不同。当它醒来时，它应该立即解锁互斥锁，而不是等到它读取队列。然后，它应该尽可能多地拉出队列并处理它。最后，只有当使用者考虑睡觉时，它才应该锁定互斥锁，检查是否有任何数据，如果有，则解锁并处理它，如果没有，则等待条件变量。这样，互斥锁的竞争频率要比锁满队列的低，但不存在使用队列中仍然保留的数据的风险。
这是最好的方法吗？还有其他选择吗？
Note：我所说的“最快的”实际上是指“最快的”，而不是用一个核心来反复检查队列，但这不符合标题；
一个可选的：使用简单的解决方案，但是让使用者在条件变量上等待一个超时，该超时与您愿意容忍的穿越队列的项目的最大延迟相对应。如果所需的超时时间相当短，那么它可能低于操作系统的最小等待时间，或者仍然占用过多的CPU。
回答 1
Stack Overflow用户
发布于 2010-12-09 21:41:16
我假设您使用的是来自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时，消费者才会停止。 - 因此，消费者必须仍然清醒，并将达到您的新项目睡觉前。
- 在添加新对象之后，您知道
- 先拿一份
- Otherwise lock the mutex, signal the condvar then release the mutex. (Obtaining the mutex here ensures you don't signal the condar in the time between the consumer noticing the queue is empty, and actually blocking on the condvar.)
这确保了，在消费者往往保持忙碌的情况下，当您知道使用者仍然醒着(而不是要睡觉)时，您可以避免锁定互斥锁。它还减少了互斥锁保持的时间，以进一步减少争用的可能性。
上面的解释非常冗长(因为我想解释它为什么工作，而不仅仅是算法是什么)，但是由此产生的代码应该非常简单。
当然，它是否真正值得去做将取决于很多事情，我鼓励你去衡量你的表现对你来说是否重要。在大多数情况下，mutex/condvar原语的良好实现在内部使用原子操作，因此它们通常只进行内核调用(最昂贵的位！)如果需要--也就是说，如果需要阻塞，或者肯定有一些线程在等待--那么不调用互斥函数所节省的时间可能只相当于库调用的开销。
https://stackoverflow.com/questions/4235721
复制相似问题
腾讯云开发者
