algorithm - 为什么单生产者单消费者循环队列线程不加锁是安全的？

Question

这似乎是真的，但我的想法一直很混乱。有人可以给出一个明确的解释和一些关键情况，它总是在没有锁定的情况下工作吗？谢谢！

Answer 1

单生产者-单消费者循环队列背后的真正技巧是头和尾指针被原子地修改。这意味着如果内存中的某个位置从值 A 更改为值 B，则在其值更改时读取内存的观察者（即阅读器）将得到 A 或 B 作为结果，没有别的。

因此，例如，如果您使用 16 位指针但您在两个 8 位步骤中更改它们（这可能取决于您的 CPU 体系结构和内存对齐要求），您的队列将无法工作。在这种情况下，阅读器可能会读取完全错误的瞬态值。

因此，请确保您的指针在您的平台中被自动修改！

Answer 2

这肯定取决于循环队列的实现。但是，如果它是我想象的那样，你有两个索引——队列的head和tail。生产者与 合作tail，消费者与 合作head。它们共享消息数组，但使用两个不同的指针。

生产者和消费者可能会发生冲突的唯一情况是，例如消费者检查新消息并在检查后立即到达。然而，在这种情况下，消费者会稍等片刻并再次检查。程序的正确性不会丢失。

它与单个生产者单个消费者一起工作的原因主要是因为两个用户不共享太多内存。例如，在多个生产者的情况下，您将有多个线程访问head并且可能会引发冲突。

编辑正如 dasblinkenlight 在他的评论中提到的那样，我的推理只有在两个线程都将各自的计数器递增/递减作为其消费/生产的最后操作时才成立。