无锁队列应该使用条件变量吗？

Question

假设我在多线程设置中有一个无锁队列。我已经提供了一个try_dequeue()方法，如果队列是空的，它允许一个可选的失败(通过返回类型传递)。

我发现拥有一个总是成功的T dequeue()方法很方便，它在队列为空时不会返回。作为一名消费者，我并不在乎什么时候能买到我的产品，我只是想知道一有货就好。

我的dequeue()实现非常简单：

while (true) {
    if (try_dequeue succeeded) return result;
    std::unique_lock<std::mutex> lk(mtx_);
    cond_.wait(lk, [this]{ return !empty(); });
}

在这里，cond_由排队者和mtx_守卫cond_发出信号。

lk引起的过多的序列化和脱队列争用似乎减缓了速度。empty()当然不需要任何东西被锁定。

无论如何，cond_在这里看起来不合适吗？我不愿删除它的唯一原因是，有一个脱队列者(或多个脱队列者)正在等待一个新的项进入，并且在CPU上空闲地旋转，没有显示队列线程获得优先级。

也许this_thread::yield()在这里更合适，但标准只保证该方法是一个提示，因此这里可能会出现饥饿现象。

看来推动：：无锁：：队列根本不提供dequeue-like方法。希望核选择是可以避免的。

正如用户rwong指出的那样，我们可以将这个问题的解决方案考虑为“混合”或“半阻塞”的方法，因为在空队列上设置去队列块是可取的，但是对于排队者来说，不必同时进行完整的上下文切换也是很好的。

注意:是的，从技术上讲，队列中包含的mtx_删除了无锁属性，但我认为这是一个准确的特性，因为dequeue()是使用mtx_ (无锁定的排队信号)的唯一方法。

Answer 1

您可以在排队时使用try_lock发送cond_的信令。这将具有一个竞赛条件，可以通过使等待计时来规避。

这样做的想法是，如果try_lock失败了，那么另一个排队者也会试图唤醒去排队的人，所以我们最好让他去做这项工作，或者去排队的人正在等待，他可能已经或者可能还没有检查过条件。如果他还没好的话，他会看到队列不是空的，然后释放，然后再试一次，如果他已经检查过了，那么他会在超时结束后再检查一次。