無鎖定且無等待算法
如果每個線程在其他線程任意延遲（或甚至失敗）時都將持續進行操作，就可以說該算法是 無等待的。與此形成對比的是， 無鎖定算法要求僅 某個線程總是執行操作。（無等待的另一種定義是保證每個線程在其有限的步驟中正確計算自己的操作，而不管其他線程的操作、計時、交叉或速度。這一限制可以是系統中線程數的函數；例如，如果有 10 個線程，每個線程都執行一次 CasCounter.increment() 操作，最壞的情況下，每個線程將必須重試最多九次，才能完成增加。）
再過去的 15 年里，人們已經對無等待且無鎖定算法（也稱為 無阻塞算法）進行了大量研究，許多人通用數據結構已經發現了無阻塞算法。無阻塞算法被廣泛用于操作系統和 JVM 級別，進行諸如線程和進程調度等任務。雖然它們的實現比較復雜，但相對于基于鎖定的備選算法，它們有許多優點：可以避免優先級倒置和死鎖等危險，競爭比較便宜，協調發生在更細的粒度級別，允許更高程度的并行機制等等。
原子變量類
在 JDK 5.0 之前，如果不使用本機代碼，就不能用 Java 語言編寫無等待、無鎖定的算法。在 java.util.concurrent.atomic 包中添加原子變量類之后，這種情況才發生了改變。所有原子變量類都公開比較并設置原語（與比較并交換類似），這些原語都是使用平臺上可用的最快本機結構（比較并交換、加載鏈接/條件存儲，最壞的情況下是旋轉鎖）來實現的。 java.util.concurrent.atomic 包中提供了原子變量的 9 種風格（ AtomicInteger； AtomicLong； AtomicReference； AtomicBoolean；原子整型；長型；引用；及原子標記引用和戳記引用類的數組形式，其原子地更新一對值）。
原子變量類可以認為是 volatile 變量的泛化，它擴展了可變變量的概念，來支持原子條件的比較并設置更新。讀取和寫入原子變量與讀取和寫入對可變變量的訪問具有相同的存取語義。
雖然原子變量類表面看起來與清單 1 中的 SynchronizedCounter 例子一樣，但相似僅是表面的。在表面之下，原子變量的操作會變為平臺提供的用于并發訪問的硬件原語，比如比較并交換。
更細粒度意味著更輕量級
調整具有競爭的并發應用程序的可伸縮性的通用技術是降低使用的鎖定對象的粒度，希望更多的鎖定請求從競爭變為不競爭。從鎖定轉換為原子變量可以獲得相同的結果，通過切換為更細粒度的協調機制，競爭的操作就更少，從而提高了吞吐量。
 |
ABA 問題
因為在更改 V 之前，CAS 主要詢問“V 的值是否仍為 A”，所以在第一次讀取 V 以及對 V 執行 CAS 操作之前，如果將值從 A 改為 B，然后再改回 A，會使基于 CAS 的算法混亂。在這種情況下，CAS 操作會成功，但是在一些情況下，結果可能不是您所預期的。（注意， 清單 1 和 清單 2 中的計數器和互斥例子不存在這個問題，但不是所有算法都這樣。）這類問題稱為 ABA 問題，通常通過將標記或版本編號與要進行 CAS 操作的每個值相關聯，并原子地更新值和標記，來處理這類問題。 AtomicStampedReference 類支持這種方法。 |
|
java.util.concurrent 中的原子變量
無論是直接的還是間接的，幾乎 java.util.concurrent 包中的所有類都使用原子變量，而不使用同步。類似ConcurrentLinkedQueue 的類也使用原子變量直接實現無等待算法，而類似 ConcurrentHashMap 的類使用 ReentrantLock 在需要時進行鎖定。然后， ReentrantLock 使用原子變量來維護等待鎖定的線程隊列。
如果沒有 JDK 5.0 中的 JVM 改進，將無法構造這些類，這些改進暴露了（向類庫，而不是用戶類）接口來訪問硬件級的同步原語。然后，java.util.concurrent 中的原子變量類和其他類向用戶類公開這些功能。
使用原子變量獲得更高的吞吐量
上月，我介紹了 ReentrantLock 如何相對于同步提供可伸縮性優勢，以及構造通過偽隨機數生成器模擬旋轉骰子的簡單、高競爭示例基準。我向您顯示了通過同步、 ReentrantLock 和公平 ReentrantLock 來進行協調的實現，并顯示了結果。本月，我將向該基準添加其他實現，使用 AtomicLong 更新 PRNG 狀態的實現。
清單 5 顯示了使用同步的 PRNG 實現和使用 CAS 備選實現。注意，要在循環中執行 CAS，因為它可能會失敗一次或多次才能獲得成功，使用 CAS 的代碼總是這樣。
清單 5. 使用同步和原子變量實現線程安全 PRNG
public class PseudoRandomUsingSynch implements PseudoRandom {
private int seed;
public PseudoRandomUsingSynch(int s) { seed = s; }
public synchronized int nextInt(int n) {
int s = seed;
seed = Util.calculateNext(seed);
return s % n;
}
}
public class PseudoRandomUsingAtomic implements PseudoRandom {
private final AtomicInteger seed;
public PseudoRandomUsingAtomic(int s) {
seed = new AtomicInteger(s);
}
public int nextInt(int n) {
for (;;) {
int s = seed.get();
int nexts = Util.calculateNext(s);
if (seed.compareAndSet(s, nexts))
return s % n;
}
}
}
|
下面圖 1 和圖 2 中的圖與上月那些圖相似，只是為基于原子的方法多添加了一行。這些圖顯示了在 8-way Ultrasparc3 和單處理器 Pentium 4 上使用不同數量線程的隨機發生的吞吐量（以每秒轉數為單位）。測試中的線程數不是真實的；這些線程所表現的競爭比通常多得多，所以它們以比實際程序中低得多的線程數顯示了 ReentrantLock 與原子變量之間的平衡。您將看到，雖然 ReentrantLock 擁有比同步更多的優點，但相對于 ReentrantLock，原子變量提供了其他改進。（因為在每個工作單元中完成的工作很少，所以下圖可能無法完全地說明與 ReentrantLock 相比，原子變量具有哪些可伸縮性優點。）
圖 1. 8-way Ultrasparc3 中同步、ReentrantLock、公平 Lock 和 AtomicLong 的基準吞吐量
圖 2. 單處理器 Pentium 4 中的同步、ReentrantLock、公平 Lock 和 AtomicLong 的基準吞吐量
大多數用戶都不太可能使用原子變量自己開發無阻塞算法 — 他們更可能使用 java.util.concurrent 中提供的版本，如 ConcurrentLinkedQueue。但是萬一您想知道對比以前 JDK 中的相類似的功能，這些類的性能是如何改進的，可以使用通過原子變量類公開的細粒度、硬件級別的并發原語。
開發人員可以直接將原子變量用作共享計數器、序號生成器和其他獨立共享變量的高性能替代，否則必須通過同步保護這些變量。
結束語
JDK 5.0 是開發高性能并發類的巨大進步。通過內部公開新的低級協調原語，和提供一組公共原子變量類，現在用 Java 語言開發無等待、無鎖定算法首次變為可行。然后， java.util.concurrent 中的類基于這些低級原子變量工具構建，為它們提供比以前執行相似功能的類更顯著的可伸縮性優點。雖然您可能永遠不會直接使用原子變量，還是應該為它們的存在而歡呼。