data-structures - 无锁队列算法，重复读取一致性

Question

我正在研究 lock-free (en-,de-)queue algorithms of Michael and Scott .问题是我无法解释/理解几行(除了代码本身的注释之外，论文也无法解释)。

排队:

  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？正确性取决于它吗？还是仅仅是一种优化？如果另一个线程成功执行了 E17 或下面的 D10(并更改了 Q->Tail)，而第一个线程已执行 E5 但尚未执行 E7，则此 if 可能会失败。但是，如果在第一个线程执行 E7 之后立即执行 E17 怎么办？

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

出队:

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 需要是易变的，所以我们知道我们不仅仅是在读取缓存在寄存器中的副本，而是在读取真实的东西，这将被翻译在阅读前加上某种栅栏)，所以我不确定这里到底发生了什么……谢谢。

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

Answer 1

我被困在同一个问题上，怀疑这可能是一种优化，所以我问了这篇论文的作者之一 Maged Michael。这是他的回应:

E7 and D5 are needed for correctness.

The following case shows why E7 is needed:

• Thread P reads the value <A,num1> from Q->Tail in line E5

• Other threads change the queue such that the node A is removed and maybe later reused in a different queue (or a different structure with similar node structure) or allocated by a thread to insert it in this same queue. In any case A is not in this queue and its next field has the value <NULL, num2>.

• In line E6, P reads the value <NULL, num2> from A->next into next.

• (Skipping line E7)

• In line E8, P finds next.ptr == NULL

• In line E9, P executes a successful CAS on A->next as it finds A->next == <NULL, num2> and sets it to <node,num2+1>.

• Now, the new node is incorrectly inserted after A which doesn't belong to this queue. This might also corrupt another unrelated structure.

With line E7, P would have discovered that Q->Tail has changed and would have started over.

Similarly for D5.

基本上，如果我们从 tail.ptr->next 读取将使我们相信下一个指针为空(因此我们可以写入节点)，我们必须仔细检查此空指的是当前队列的末尾。如果在我们读取 null 后该节点仍在队列中，我们可以假设它确实是队列的末尾，并且比较和交换将(给定计数器)捕获该节点发生任何事情的情况 在 E7 中的测试之后(从队列中删除节点必然涉及改变其下一个指针)。