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