Michael-Scott 非阻塞队列算法中的插入

CAS的基本使用模式：在更新某个值时存在不确定性，以及在更新失败时重新尝试。构建非阻塞算法的技巧在于：将执行原子修改的范围缩小到单个变量上。

　　链接队列比栈更为复杂，因为它必须支持对头节点和尾节点的快速访问。因此，它需要单独维护的头指针和尾指针。有两个指针指向尾部的节点：当前最后一个元素的next指针，以及尾节点。当成功地插入一个新元素时，这两个指针都需要采用原子操作来更新。

　　这里需要一些技巧来完成，第一个技巧是，即使在一个包含多个步骤的更新操作中，也要确保数据结构总是处于一致的状态。这样，当线程B到达时，如果发现线程A正在执行更新，那么线程B就可以知道有一个操作已部分完成，并且不能立即开始执行自己的更新操作。然后，B可以等待（通过反复检查队列的状态）并直到A完成更新，从而使两个线程不会相互干扰。

　　虽然这种方法能够使不同的线程“轮流”访问呢数据结构，并且不会造成破坏，但如果一个线程在更新操作中失败了，那么其他的线程都无法在访问队列。要使得该算法成为一个非阻塞算法，必须确保当一个线程失败时不会妨碍其他线程继续执行下去。因此，第二个技巧是，如果当B到达时发现A正在修改数据结构，那么在数据结构中应该有足够多的信息，使得B能完成A的更新操作。如果B“帮助”A完成了更新操作，那么B可以执行自己的操作，而不用等到A的操作完成。当A恢复后再试图完成其操作时，会发现B已经替它完成了。

　　在下面的程序中，给出了 Michael-Scott 提出的非阻塞连界队列算法中的插入部分，它是由 ConcurrentLinkedQueue 实现的。在许多队列算法中，空队列通常都包含一个“哨兵节点”或者“哑（Dummy）节点”，并且头节点和尾节点在初始化时都指向该哨兵节点。尾节点通常要么指向哨兵节点（如果队列为空），即队列的最后一个元素，要么（当有操作正在执行更新时）指向倒数第二个元素。下图1给出了一个处于正常状态（或者说稳定状态）的包含两个元素的队列。

Michael-Scott 非阻塞队列算法中的插入：

 1 @ThreadSafe
 2 public class LinkedQueue<E> {
 3     private static class Node <E> {
 4         final E item;
 5         final AtomicReference<LinkedQueue.Node<E>> next;
 6 
 7         public Node(E item, LinkedQueue.Node<E> next) {
 8             this.item = item;
 9             this.next = new AtomicReference<LinkedQueue.Node<E>>(next);
10         }
11     }
12 
13     private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);
14     private final AtomicReference<LinkedQueue.Node<E>> head
15             = new AtomicReference<LinkedQueue.Node<E>>(dummy);
16     private final AtomicReference<LinkedQueue.Node<E>> tail
17             = new AtomicReference<LinkedQueue.Node<E>>(dummy);
18 
19     public boolean put(E item) {
20         LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);
21         while (true) {
22             LinkedQueue.Node<E> curTail = tail.get();
23             LinkedQueue.Node<E> tailNext = curTail.next.get();
24             if (curTail == tail.get()) {
25                 if (tailNext != null) {  // A
26                     // 队列处于中间状态，推进尾节点
27                     tail.compareAndSet(curTail, tailNext); // B
28                 } else {
29                     // 处于稳定状态，尝试插入新节点
30                     if (curTail.next.compareAndSet(null, newNode)) { // C
31                         // 插入操作成功，尝试推进尾节点
32                         tail.compareAndSet(curTail, newNode); // D
33                         return true;
34                     }
35                 }
36             }
37         }
38     }
39 }

　　　　图1 处于稳定状态并包含两个元素的对立

　　当插入一个新的元素时，需要更新两个指针。首先更新当前最后一个元素的next 指针，将新节点链接到队列队尾，然后更新尾节点，将其指向这个新元素。在两个操作之间，队列处于一种中间状态，如图2。在等二次更新完成后，队列将再次处于稳定状态，如图3所示。

　　实现这两个技巧的关键在于：当队列处于稳定状态时，尾节点的next域将为空，如果队列处于中间状态，那么tail.next 将为非空。因此，任何线程都能够通过检查tail.next 来获取队列当前的状态。而且，当队列处于中间状态时，可以通过将尾节点移动一个节点，从而结束其他线程正在执行的插入元素操作，并使得队列恢复为稳定状态。

  　　　　图2  在插入过程中处于中间状态的对立

　　　　图3 在插入操作完成后，队列再次处于稳定状态

　　LinkedQueue.put 方法在插入新元素之前，将首先检查队列是否处于中间状态（步骤A）。如果是，那么有另一个线程正在插入元素（在步骤C和D之间）。此时当前线程不会等待其他线程执行完成，而是帮助它完成操作，并将尾节点向前推进一个节点（步骤B）。然后，它将重复执行这种检查，以免另一个线程已经开始插入新元素，并继续推进尾节点，直到它发现队列处于稳定状态之后，才会开始执行自己的插入操作。

　　由于步骤C中的CAS将把新节点链接到队列尾部，因此如果两个线程同时插入元素，那么这个CAS将失败。在这样的情况下，并不会造成破坏：不会发生任何变化，并且当前的线程只需要重新读取尾节点并再次重试。如果步骤C成功了，那么插入操作将生效，第二个CAS（步骤D）被认为是一个“清理操作”，因为它既可以由执行插入操作的线程来执行，也可以由其他任何线程来执行。如果步骤D失败，那么执行插入操作的线程将返回，而不是重新执行CAS，因为不再需要重试——另一个线程已经在步骤B中完成了这个工作。

　　这种方式能够工作，因为在任何线程尝试将一个新节点插入到队列之前，都会首先通过检查tail.next是否非空来判断是否需要清理队列。如果是，它首先会推荐尾节点（可能需要执行多次），直到队列处于稳定状态。