c++ - boost::lockfree 中的“wait-free”到底是什么意思？

Question

我正在阅读spsc_queue的文档，即使在其他地方阅读了一些内容后，我也不完全相信“无需等待”的含义。

他们在这里到底是什么意思

布尔推（T const & t）；

将对象 t 推送到环形缓冲区。

注意：线程安全且无需等待

我的意思是同步必须有一些开销。是

some_spscqueue.push(x);

保证花费恒定的时间？它与非线程安全队列相比如何？

PS：别担心，我会测量，但由于我天真无知，我无法想象一个不涉及某种等待的同步机制，我很困惑“无等待”应该告诉我什么。

score 2 · Accepted Answer

并发数据对象的无等待实现是一种保证任何进程可以在有限数量的步骤中完成任何操作，而不管其他进程的执行速度如何。

（来自 Herlihy 文章的摘要）。

另请参阅Wikipedia以及通过在搜索引擎中键入“wait free”立即找到的所有其他资源。

所以无等待并不意味着没有延迟，它意味着你永远不会进入阻塞等待状态，也不能无限期地被阻塞和/或饿死。

换句话说，等待具有特定的技术含义，即您的线程要么处于停顿状态（并且在某些东西唤醒它之前不执行任何指令），要么处于等待满足某些外部条件的循环中（例如自旋锁）。如果它从未被唤醒，或者如果它被唤醒但总是发现它无法继续并不得不再次等待，或者如果循环永远不会退出，那么你的线程正在被饿死并且无法取得进展。

每个操作都有一些延迟，等待免费并没有说明那是什么。

它与非线程安全队列相比如何？

它几乎肯定会比完全不同步的容器更昂贵，因为您仍在做额外的工作（假设您确实只从单个线程访问容器）。

score 0 · Accepted Answer

“将对象推送到环形缓冲区”是指实现队列的数组缓冲区的类型。这可能是使用循环数组将对象存储在队列中来实现的。参见例如：

和

2 回答 2