非阻塞算法簡介

在不只一個線程訪問一個互斥的變量時，所有線程都必須使用同步，否則就可能會發生一些非常糟糕的事情。Java 語言中主要的同步手段就是?synchronized?關鍵字（也稱為內在鎖），它強制實行互斥，確保執行?synchronized?塊的線程的動作，能夠被后來執行受相同鎖保護的?synchronized?塊的其他線程看到。在使用得當的時候，內在鎖可以讓程序做到線程安全，但是在使用鎖定保護短的代碼路徑，而且線程頻繁地爭用鎖的時候，鎖定可能成為相當繁重的操作。

在?“流行的原子”?一文中，我們研究了原子變量，原子變量提供了原子性的讀-寫-修改操作，可以在不使用鎖的情況下安全地更新共享變量。原子變量的內存語義與 volatile 變量類似，但是因為它們也可以被原子性地修改，所以可以把它們用作不使用鎖的并發算法的基礎。

非阻塞的計數器

清單 1 中的?Counter?是線程安全的，但是使用鎖的需求帶來的性能成本困擾了一些開發人員。但是鎖是必需的，因為雖然增加看起來是單一操作，但實際是三個獨立操作的簡化：檢索值，給值加 1，再寫回值。（在?getValue?方法上也需要同步，以保證調用?getValue?的線程看到的是最新的值。雖然許多開發人員勉強地使自己相信忽略鎖定需求是可以接受的，但忽略鎖定需求并不是好策略。）

在多個線程同時請求同一個鎖時，會有一個線程獲勝并得到鎖，而其他線程被阻塞。JVM 實現阻塞的方式通常是掛起阻塞的線程，過一會兒再重新調度它。由此造成的上下文切換相對于鎖保護的少數幾條指令來說，會造成相當大的延遲。

清單 1. 使用同步的線程安全的計數器

public final class Counter {private long value = 0;public synchronized long getValue() {return value;}public synchronized long increment() {return ++value;}
}

清單 2 中的?NonblockingCounter?顯示了一種最簡單的非阻塞算法：使用?AtomicInteger?的?compareAndSet()?（CAS）方法的計數器。compareAndSet()?方法規定 “將這個變量更新為新值，但是如果從我上次看到這個變量之后其他線程修改了它的值，那么更新就失敗”（請參閱?“流行的原子”?獲得關于原子變量以及 “比較和設置” 的更多解釋。）

清單 2. 使用 CAS 的非阻塞算法

public class NonblockingCounter {private AtomicInteger value;public int getValue() {return value.get();}public int increment() {int v;do {v = value.get();while (!value.compareAndSet(v, v + 1));return v + 1;}
}

原子變量類之所以被稱為原子的，是因為它們提供了對數字和對象引用的細粒度的原子更新，但是在作為非阻塞算法的基本構造塊的意義上，它們也是原子的。非阻塞算法作為科研的主題，已經有 20 多年了，但是直到 Java 5.0 出現，在 Java 語言中才成為可能。

現代的處理器提供了特殊的指令，可以自動更新共享數據，而且能夠檢測到其他線程的干擾，而?compareAndSet()?就用這些代替了鎖定。（如果要做的只是遞增計數器，那么?AtomicInteger?提供了進行遞增的方法，但是這些方法基于?compareAndSet()，例如?NonblockingCounter.increment()）。

非阻塞版本相對于基于鎖的版本有幾個性能優勢。首先，它用硬件的原生形態代替 JVM 的鎖定代碼路徑，從而在更細的粒度層次上（獨立的內存位置）進行同步，失敗的線程也可以立即重試，而不會被掛起后重新調度。更細的粒度降低了爭用的機會，不用重新調度就能重試的能力也降低了爭用的成本。即使有少量失敗的 CAS 操作，這種方法仍然會比由于鎖爭用造成的重新調度快得多。

NonblockingCounter?這個示例可能簡單了些，但是它演示了所有非阻塞算法的一個基本特征 —— 有些算法步驟的執行是要冒險的，因為知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作樂觀算法，因為它們繼續操作的假設是不會有干擾。如果發現干擾，就會回退并重試。在計數器的示例中，冒險的步驟是遞增 —— 它檢索舊值并在舊值上加一，希望在計算更新期間值不會變化。如果它的希望落空，就會再次檢索值，并重做遞增計算。

非阻塞堆棧

非阻塞算法稍微復雜一些的示例是清單 3 中的?ConcurrentStack。ConcurrentStack?中的?push()?和?pop()?操作在結構上與?NonblockingCounter?上相似，只是做的工作有些冒險，希望在 “提交” 工作的時候，底層假設沒有失效。push()?方法觀察當前最頂的節點，構建一個新節點放在堆棧上，然后，如果最頂端的節點在初始觀察之后沒有變化，那么就安裝新節點。如果 CAS 失敗，意味著另一個線程已經修改了堆棧，那么過程就會重新開始。

清單 3. 使用 Treiber 算法的非阻塞堆棧

public class ConcurrentStack<E> {AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();public void push(E item) {Node<E> newHead = new Node<E>(item);Node<E> oldHead;do {oldHead = head.get();newHead.next = oldHead;} while (!head.compareAndSet(oldHead, newHead));}public E pop() {Node<E> oldHead;Node<E> newHead;do {oldHead = head.get();if (oldHead == null) return null;newHead = oldHead.next;} while (!head.compareAndSet(oldHead,newHead));return oldHead.item;}static class Node<E> {final E item;Node<E> next;public Node(E item) { this.item = item; }}
}

性能考慮

在輕度到中度的爭用情況下，非阻塞算法的性能會超越阻塞算法，因為 CAS 的多數時間都在第一次嘗試時就成功，而發生爭用時的開銷也不涉及線程掛起和上下文切換，只多了幾個循環迭代。沒有爭用的 CAS 要比沒有爭用的鎖便宜得多（這句話肯定是真的，因為沒有爭用的鎖涉及 CAS 加上額外的處理），而爭用的 CAS 比爭用的鎖獲取涉及更短的延遲。

在高度爭用的情況下（即有多個線程不斷爭用一個內存位置的時候），基于鎖的算法開始提供比非阻塞算法更好的吞吐率，因為當線程阻塞時，它就會停止爭用，耐心地等候輪到自己，從而避免了進一步爭用。但是，這么高的爭用程度并不常見，因為多數時候，線程會把線程本地的計算與爭用共享數據的操作分開，從而給其他線程使用共享數據的機會。（這么高的爭用程度也表明需要重新檢查算法，朝著更少共享數據的方向努力。）“流行的原子”?中的圖在這方面就有點兒讓人困惑，因為被測量的程序中發生的爭用極其密集，看起來即使對數量很少的線程，鎖定也是更好的解決方案。

非阻塞的鏈表

目前為止的示例（計數器和堆棧）都是非常簡單的非阻塞算法，一旦掌握了在循環中使用 CAS，就可以容易地模仿它們。對于更復雜的數據結構，非阻塞算法要比這些簡單示例復雜得多，因為修改鏈表、樹或哈希表可能涉及對多個指針的更新。CAS 支持對單一指針的原子性條件更新，但是不支持兩個以上的指針。所以，要構建一個非阻塞的鏈表、樹或哈希表，需要找到一種方式，可以用 CAS 更新多個指針，同時不會讓數據結構處于不一致的狀態。

在鏈表的尾部插入元素，通常涉及對兩個指針的更新：“尾” 指針總是指向列表中的最后一個元素，“下一個” 指針從過去的最后一個元素指向新插入的元素。因為需要更新兩個指針，所以需要兩個 CAS。在獨立的 CAS 中更新兩個指針帶來了兩個需要考慮的潛在問題：如果第一個 CAS 成功，而第二個 CAS 失敗，會發生什么？如果其他線程在第一個和第二個 CAS 之間企圖訪問鏈表，會發生什么？

對于非復雜數據結構，構建非阻塞算法的 “技巧” 是確保數據結構總處于一致的狀態（甚至包括在線程開始修改數據結構和它完成修改之間），還要確保其他線程不僅能夠判斷出第一個線程已經完成了更新還是處在更新的中途，還能夠判斷出如果第一個線程走向 AWOL，完成更新還需要什么操作。如果線程發現了處在更新中途的數據結構，它就可以 “幫助” 正在執行更新的線程完成更新，然后再進行自己的操作。當第一個線程回來試圖完成自己的更新時，會發現不再需要了，返回即可，因為 CAS 會檢測到幫助線程的干預（在這種情況下，是建設性的干預）。

這種 “幫助鄰居” 的要求，對于讓數據結構免受單個線程失敗的影響，是必需的。如果線程發現數據結構正處在被其他線程更新的中途，然后就等候其他線程完成更新，那么如果其他線程在操作中途失敗，這個線程就可能永遠等候下去。即使不出現故障，這種方式也會提供糟糕的性能，因為新到達的線程必須放棄處理器，導致上下文切換，或者等到自己的時間片過期（而這更糟）。

清單 4 的?LinkedQueue?顯示了 Michael-Scott 非阻塞隊列算法的插入操作，它是由?ConcurrentLinkedQueue?實現的：

清單 4. Michael-Scott 非阻塞隊列算法中的插入

public class LinkedQueue <E> {private static class Node <E> {final E item;final AtomicReference<Node<E>> next;Node(E item, Node<E> next) {this.item = item;this.next = new AtomicReference<Node<E>>(next);}}private AtomicReference<Node<E>> head= new AtomicReference<Node<E>>(new Node<E>(null, null));private AtomicReference<Node<E>> tail = head;public boolean put(E item) {Node<E> newNode = new Node<E>(item, null);while (true) {Node<E> curTail = tail.get();Node<E> residue = curTail.next.get();if (curTail == tail.get()) {if (residue == null) /* A */ {if (curTail.next.compareAndSet(null, newNode)) /* C */ {tail.compareAndSet(curTail, newNode) /* D */ ;return true;}} else {tail.compareAndSet(curTail, residue) /* B */;}}}}
}

像許多隊列算法一樣，空隊列只包含一個假節點。頭指針總是指向假節點；尾指針總指向最后一個節點或倒數第二個節點。圖 1 演示了正常情況下有兩個元素的隊列：

圖 1. 有兩個元素，處在靜止狀態的隊列

? ? ? ? ?

如?清單 4?所示，插入一個元素涉及兩個指針更新，這兩個更新都是通過 CAS 進行的：從隊列當前的最后節點（C）鏈接到新節點，并把尾指針移動到新的最后一個節點（D）。如果第一步失敗，那么隊列的狀態不變，插入線程會繼續重試，直到成功。一旦操作成功，插入被當成生效，其他線程就可以看到修改。還需要把尾指針移動到新節點的位置上，但是這項工作可以看成是 “清理工作”，因為任何處在這種情況下的線程都可以判斷出是否需要這種清理，也知道如何進行清理。

隊列總是處于兩種狀態之一：正常狀態（或稱靜止狀態，圖 1?和?圖 3）或中間狀態（圖 2）。在插入操作之前和第二個 CAS（D）成功之后，隊列處在靜止狀態；在第一個 CAS（C）成功之后，隊列處在中間狀態。在靜止狀態時，尾指針指向的鏈接節點的 next 字段總為 null，而在中間狀態時，這個字段為非 null。任何線程通過比較?tail.next?是否為 null，就可以判斷出隊列的狀態，這是讓線程可以幫助其他線程 “完成” 操作的關鍵。

圖 2. 處在插入中間狀態的隊列，在新元素插入之后，尾指針更新之前

? ? ? ? ?

插入操作在插入新元素（A）之前，先檢查隊列是否處在中間狀態，如?清單 4?所示。如果是在中間狀態，那么肯定有其他線程已經處在元素插入的中途，在步驟（C）和（D）之間。不必等候其他線程完成，當前線程就可以 “幫助” 它完成操作，把尾指針向前移動（B）。如果有必要，它還會繼續檢查尾指針并向前移動指針，直到隊列處于靜止狀態，這時它就可以開始自己的插入了。

第一個 CAS（C）可能因為兩個線程競爭訪問隊列當前的最后一個元素而失敗；在這種情況下，沒有發生修改，失去 CAS 的線程會重新裝入尾指針并再次嘗試。如果第二個 CAS（D）失敗，插入線程不需要重試 —— 因為其他線程已經在步驟（B）中替它完成了這個操作！

圖 3. 在尾指針更新后，隊列重新處在靜止狀態

? ? ? ? ?

幕后的非阻塞算法

如果深入 JVM 和操作系統，會發現非阻塞算法無處不在。垃圾收集器使用非阻塞算法加快并發和平行的垃圾搜集；調度器使用非阻塞算法有效地調度線程和進程，實現內在鎖。在 Mustang（Java 6.0）中，基于鎖的?SynchronousQueue?算法被新的非阻塞版本代替。很少有開發人員會直接使用?SynchronousQueue，但是通過?Executors.newCachedThreadPool()?工廠構建的線程池用它作為工作隊列。比較緩存線程池性能的對比測試顯示，新的非阻塞同步隊列實現提供了幾乎是當前實現 3 倍的速度。在 Mustang 的后續版本（代碼名稱為 Dolphin）中，已經規劃了進一步的改進。