无锁队列：为什么要读两次`Atomic*`？

Question

我正在阅读 The Art of Multiprocessor Programming, 2ed 我注意到以下模式用于读取多个 Atomic* 字段：

while (true) {
    var v1 = atomic1.get();
    var v2 = atomic2.get();
    ...
    var vN = atomicN.get();
    if (v1 == atomic1.get()) {
        // do work
    }
}

这个构造的目的是什么？

我在书中找到的唯一解释是：

... checks that the values read are consistent ...

我不明白这个解释。

这里是 LockFreeQueue，它使用了书中的这种模式：

public class LockFreeQueue<T> {
  
  AtomicReference<Node> head, tail;

  public LockFreeQueue() {
    Node node = new Node(null);
    head = new AtomicReference(node);
    tail = new AtomicReference(node);
  }

  public void enq(T value) {
    Node node = new Node(value);
    while (true) {
      Node last = tail.get();
      Node next = last.next.get();
      if (last == tail.get()) {   // <=== WHY: reading tail.get() again
        if (next == null) {
          if (last.next.compareAndSet(next, node)) {
            tail.compareAndSet(last, node);
            return;
          }
        } else {
          tail.compareAndSet(last, next);
        }
      }
    }
  }

  public T deq() throws EmptyException {
    while (true) {
      Node first = head.get();
      Node last = tail.get();
      Node next = first.next.get();
      if (first == head.get()) {  // <=== WHY: reading head.get() again
        if (first == last) {
          if (next == null) {
            throw new EmptyException();
          }
          tail.compareAndSet(last, next);
        } else {
          T value = next.value;
          if (head.compareAndSet(first, next))
            return value;
        }
      }
    }
  }
}

public class Node {
  
  public T value;
  public AtomicReference<Node> next;

  public Node(T value) {
    this.value = value;
    next = new AtomicReference<Node>(null);
  }
}

我在 SO 上看到另一个类似的问题：Lock-free queue algorithm, repeated reads for consistency。
但是：

已接受的答案得分为负，并声明所有答案无需重复阅读即可工作，但未提供证明
它讨论了一种不同的算法：该算法显式释放节点，而本书主要是关于 java 中的算法（其中节点由 GC 隐式释放）。

UPD：书上说 LockFreeQueue 是 a queue algorithm by Maged Michael and Michael Scott 的略微简化版本。
这与 the similar SO question mentioned above.

中讨论的算法相同

Answer 1

我认为一般的想法是作者将按给定的顺序更新字段，并且每次“更新”时第一个字段的值将始终更改。因此，如果 reader 在第二次读取时发现第一个字段没有改变，那么它就知道它已经读取了所有的一组一致的值（快照）字段。

Answer 2

谢谢 and 的回答。
我想现在我明白了，下面是我尝试详细解释的尝试：

原来 LockFreeQueue 是 the queue algorithm by Maged Michael and Michael Scott 的简化版本。

在原始算法中，重复读取确实用于读取所有字段的一组一致的值（快照）：

To obtain consistent values of various pointers we rely on sequences of reads that re-check earlier values to be sure they haven’t changed. These sequences of reads are similar to, but simpler than, the snapshots of Prakash et al.(we need to check only one shared variable rather than two).

简化的 LockFreeQueue 实际上在没有重复读取的情况下也能正常工作（至少这是我得到的——论文中提到的所有安全属性始终有效，即使我删除了重复读取）。
尽管重复读取可能会提供更好的性能。

原始算法使用重复读取也是为了正确性（又名安全性）。
这主要是因为算法重用了从队列中移除的 Node 个对象。
完整算法 LockFreeQueueRecycle<T> 的 Java 版本在本书后面给出（它使用 AtomicStampedReference 而不是 AtomicReference）：

/* 1  */ public T deq() throws EmptyException {
/* 2  */     int[] lastStamp = new int[1];
/* 3  */     int[] firstStamp = new int[1];
/* 4  */     int[] nextStamp = new int[1];
/* 5  */     while (true) {
/* 6  */         Node first = head.get(firstStamp);
/* 7  */         Node last = tail.get(lastStamp);
/* 8  */         Node next = first.next.get(nextStamp);
/* 9  */         if (head.getStamp() == firstStamp[0]) {
/* 10 */             if (first == last) {
/* 11 */                 if (next == null) {
/* 12 */                     throw new EmptyException();
/* 13 */                 }
/* 14 */                 tail.compareAndSet(last, next,
/* 15 */                        lastStamp[0], lastStamp[0]+1);
/* 16 */             } else {
/* 17 */                 T value = next.value;
/* 18 */                 if (head.compareAndSet(first, next, firstStamp[0],
                                    firstStamp[0]+1)) {
/* 19 */                     free(first);
/* 20 */                     return value;
/* 21 */                 }
/* 22 */             }
/* 23 */         }
/* 24 */     }
/* 25 */ }

此处第 19 行 free(first) 使 Node 对象可重用。

第 9 行的重复读取 head.getStamp() == firstStamp[0] 允许我们读取 head、tail 和 head.next.
的一致值 head.getStamp() 没有改变的事实意味着 head 没有改变 ⇒ 没有节点从队列中删除 ⇒ tail 和 head.next 指向正确的（尚未回收) 节点。
如果不检查第 9 行，可能会出现错误行为：想象一下，在第 7 行之后：

我们有first == last、first.next !== null
当前线程被OS
另一个线程执行deq()几次直到first节点被回收。在回收期间 first.next 设置为 null.
当前线程由 OS
第 8 行：next = null — 我们从重用的 first 节点
第 9 行：已跳过
第 10 行：first == last 是 true
第 11 行：next == null 是 true
第 12 行：EmptyException 被错误抛出（如果在 enq() 执行期间队列从未为空的事件）。

this answer 中显示了另一个不正确行为的示例。

无锁队列：为什么要读两次`Atomic*`？

Lock-free queue: why read `Atomic*` twice?

java

multithreading

atomic

lock-free