Java? 5.0 第一次讓使用 Java 語言開發非阻塞算法成為可能，java.util.concurrent 包充分地利用瞭這個功能。非阻塞算法屬於並發算法，它們可以安全地派生它們的線程，不通過鎖定派生，而是通過低級的原子性的硬件原生形式 ?? 例如比較和交換。非阻塞算法的設計與實現極為困難，但是它們能夠提供更好的吞吐率，對生存問題（例如死鎖和優先級反轉）也能提供更好的防禦。在這期的 Java 理論與實踐 中，並發性大師 Brian Goetz 演示瞭幾種比較簡單的非阻塞算法的工作方式。
在不隻一個線程訪問一個互斥的變量時，所有線程都必須使用同步，否則就可能會發生一些非常糟糕的事情。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 {
AtomicReference<node> head = new AtomicReference<node>();
public void push(E item) {
Node newHead = new Node(item);
Node oldHead;
do {
oldHead = head.get();
newHead.next = oldHead;
} while (!head.compareAndSet(oldHead, newHead));
}
public E pop() {
Node oldHead;
Node newHead;
do {
oldHead = head.get();
if (oldHead == null)
return null;
newHead = oldHead.next;
} while (!head.compareAndSet(oldHead,newHead));
return oldHead.item;
}
static class Node {
final E item;
Node next;
public Node(E item) { this.item = item; }
}
}
性能考慮
在輕度到中度的爭用情況下，非阻塞算法的性能會超越阻塞算法，因為 CAS 的多數時間都在第一次嘗試時就成功，而