Java 理論與實踐 ：關于非阻塞算法簡介
發布: 2008-10-07 11:38 | 作者: 不詳 | 來源: 領測軟件測試網采編 | 查看: 22次 | 進入領測軟件測試網論壇討論
原子變量類之所以被稱為原子的，是因為它們提供了對數字和對象引用的細粒度的原子更新，但是在作為非阻塞算法的基本構造塊的意義上，它們也是原子的。非阻塞算法作為科研的主題，已經有 20 多年了，但是直到 Java 5.0 出現，在 Java 語言中才成為可能。
現代的處理器提供了特殊的指令，可以自動更新共享數據，而且能夠檢測到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。（如果要做的只是遞增計數器，那么 AtomicInteger 提供了進行遞增的方法，但是這些方法基于 compareAndSet()，例如 NonblockingCounter.increment()）。
非阻塞版本相對于基于鎖的版本有幾個性能優勢。首先，它用硬件的原生形態代替 JVM 的鎖定代碼路徑，從而在更細的粒度層次上（獨立的內存位置）進行同步，失敗的線程也可以立即重試，而不會被掛起后重新調度。更細的粒度降低了爭用的機會，不用重新調度就能重試的能力也降低了爭用的成本。即使有少量失敗的 CAS 操作，這種方法仍然會比由于鎖爭用造成的重新調度快得多。
NonblockingCounter 這個示例可能簡單了些，但是它演示了所有非阻塞算法的一個基本特征 ?? 有些算法步驟的執行是要冒險的，因為知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作樂觀算法，因為它們繼續操作的假設是不會有干擾。如果發現干擾，就會回退并重試。在計數器的示例中，冒險的步驟是遞增 ?? 它檢索舊值并在舊值上加一，希望在計算更新期間值不會變化。如果它的希望落空，就會再次檢索值，并重做遞增計算。
非阻塞堆棧
非阻塞算法稍微復雜一些的示例是清單 3 中的 ConcurrentStack。ConcurrentStack 中的 push() 和 pop() 操作在結構上與 NonblockingCounter 上相似，只是做的工作有些冒險，希望在 “提交” 工作的時候，底層假設沒有失效。push() 方法觀察當前最頂的節點，構建一個新節點放在堆棧上，然后，如果最頂端的節點在初始觀察之后沒有變化，那么就安裝新節點。如果 CAS 失敗，意味著另一個線程已經修改了堆棧，那么過程就會重新開始。
清單 3. 使用 Treiber 算法的非阻塞堆棧