c++ - 双锁并发队列算法问题

Question

所以我正在浏览文章 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms由 Maged M. Michael 和 Michael L. Scott 撰写，有一个小问题我没有弄清楚:

假设我们有两个并发线程，它们在队列初始化后立即被触发。其中一个线程调用 enqueue，另一个调用 dequeue。是什么阻止他们同时访问虚拟节点的 next 字段？不能 dequeue 线程读取 next 字段，而 enqueue 线程写入它吗？他们都使用不同的锁......所以我不明白他们之间同步的是什么......

谢谢。

Answer 1

enqueue() 只操作尾部，dequeue() 只操作头部，因此它们不需要使用相同的锁。当 head 和 tail 指向同一个节点时有一种特殊情况，即在 initialize 中创建的“虚拟”节点。你是对的，enqueue() 可能正在写入该节点的下一个指针，而 dequeue() 试图读取它。

并发读写没有问题。注意 enqueue() 创建一个新节点，并完全初始化该对象，然后通过将其写入 tail->next 使其可见。因此，没有其他代码可以看到这个处于半初始化状态的新节点。此外，对指针的读/写是原子的，因此 dequeue() 不可能获得指针的一半。

因此，在您立即调用 enqueue() 和 dequeue() 的情况下，有两种可能性:

• enqueue() 在 dequeue() 从 head->next 读取之前写入 tail->next。在这种情况下，dequeue() 将看到已入队的节点并将其返回。
• dequeue() 在 enqueue() 写入 tail->next 之前从 head->next 读取。在这种情况下，dequeue() 认为队列为空并返回 false。