无锁队列算法，重复读取保持一致性

Question

我正在研究Michael 和 Scott 的无锁（en-，de-）队列算法。问题是我无法解释/理解（除了代码本身的注释之外，论文也无法解释）几行。

入队：

  enqueue(Q: pointer to queue_t, value: data type)
   E1:   node = new_node()        // Allocate a new node from the free list
   E2:   node->value = value      // Copy enqueued value into node
   E3:   node->next.ptr = NULL    // Set next pointer of node to NULL
   E4:   loop                     // Keep trying until Enqueue is done
   E5:      tail = Q->Tail        // Read Tail.ptr and Tail.count together
   E6:      next = tail.ptr->next // Read next ptr and count fields together
   E7:      if tail == Q->Tail    // Are tail and next consistent?
               // Was Tail pointing to the last node?
   E8:         if next.ptr == NULL
                  // Try to link node at the end of the linked list
   E9:            if CAS(&tail.ptr->next, next, <node, next.count+1>)
  E10:               break        // Enqueue is done.  Exit loop
  E11:            endif
  E12:         else               // Tail was not pointing to the last node
                  // Try to swing Tail to the next node
  E13:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
  E14:         endif
  E15:      endif
  E16:   endloop
         // Enqueue is done.  Try to swing Tail to the inserted node
  E17:   CAS(&Q->Tail, tail, <node, tail.count+1>)

为什么需要E7？正确性取决于它吗？还是仅仅是一种优化？if如果另一个线程成功执行 E17 或下面的 D10（并更改 Q->Tail），而第一个线程已执行 E5 但尚未执行 E7，则此操作可能会失败。但是如果在第一个线程执行 E7 之后立即执行 E17 呢？

编辑：这最后一句话是否证明E7不能超过优化？我的直觉是确实如此，因为我给出了一个场景，“显然”该if语句会做出错误的决定，但算法仍然应该正常工作。但是我们可以用if随机条件替换's 条件，而不会影响正确性。这个论点有什么漏洞吗？

出队：

dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
   D1:   loop                          // Keep trying until Dequeue is done
   D2:      head = Q->Head             // Read Head
   D3:      tail = Q->Tail             // Read Tail
   D4:      next = head.ptr->next      // Read Head.ptr->next
   D5:      if head == Q->Head         // Are head, tail, and next consistent?
   D6:         if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
   D7:            if next.ptr == NULL  // Is queue empty?
   D8:               return FALSE      // Queue is empty, couldn't dequeue
   D9:            endif
                  // Tail is falling behind.  Try to advance it
  D10:            CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
  D11:         else                    // No need to deal with Tail
                  // Read value before CAS
                  // Otherwise, another dequeue might free the next node
  D12:            *pvalue = next.ptr->value
                  // Try to swing Head to the next node
  D13:            if CAS(&Q->Head, head, <next.ptr, head.count+1>)
  D14:               break             // Dequeue is done.  Exit loop
  D15:            endif
  D16:         endif
  D17:      endif
  D18:   endloop
  D19:   free(head.ptr)                // It is safe now to free the old node
  D20:   return TRUE                   // Queue was not empty, dequeue succeeded

同样，为什么需要 D5？正确性还是优化？我不确定这些测试给出的“一致性”是什么，因为在if成功之后它们似乎会变得不一致。

这看起来像是一种标准技术。有人能解释一下背后的动机吗？对我来说，似乎目的是避免在少数情况下执行（昂贵的）CAS，可以注意到它肯定会失败，但代价是总是进行额外的读取，这不应该太多本身更便宜（例如，在 Java 中，Q->Tail需要是 volatile，所以我们知道我们不仅仅是读取缓存在寄存器中的副本，而是读取真实的东西，这将被翻译为在读取之前加上某种栅栏） ，所以我不确定这里到底发生了什么......谢谢。

编辑这已被移植到 Java，更准确地说是在ConcurrentLinkedQueue 中，例如 E7 是第 194 行，而 D5 是第 212 行。

Answer 1

我被同样的问题困住了，并且怀疑这可能是一种优化，所以我问了这篇论文的作者之一 Maged Michael。这是他的回应：

正确性需要 E7 和 D5。

以下案例说明了为什么需要 E7：

• 线程 P<A,num1> 从 E5 行的 Q->Tail读取值

• 其他线程更改队列，以便节点 A 被删除，并且稍后可能会在不同的队列（或具有类似节点结构的不同结构）中重用或由线程分配以将其插入同一队列中。在任何情况下 A 都不在这个队列中，它的下一个字段的值为<NULL, num2>。

• 在 E6 行，P<NULL, num2> 从 A->next读取值到 next。

• （跳线E7）

• 在 E8 行，P 发现 next.ptr == NULL

• 在 E9 行中，P 在 A->next 上执行成功的 CAS，因为它找到A->next == <NULL, num2>并将其设置为<node,num2+1>。

• 现在，新节点被错误地插入到不属于该队列的 A 之后。这也可能会破坏另一个不相关的结构。

使用 E7 行，P 会发现 Q->Tail 已更改并且会重新开始。

D5 也一样。

基本上，如果我们的 read fromtail.ptr->next会让我们相信 next 指针为 null（因此我们可以写入节点），我们必须仔细检查这个 null 是否指的是当前队列的末尾。如果该节点仍然在队列中，我们读到空后，我们可以假设它确实是队列的末尾，并且比较并交换会（给定计数器）赶在那里出了什么事到此节点的情况下后的测试E7（从队列中删除节点必然涉及改变其下一个指针）。