1、LOGOIBM&重慶大學第第15章章 原子變量與非阻塞算法原子變量與非阻塞算法 2008年度“教育部-IBM精品課程”建設項目 IBM公司經費支持重慶大學計算機學院建設2009年3月IBM&重慶大學內容內容原子變量類2鎖的劣勢3 1非阻塞算法3 3IBM&重慶大學15.1 鎖的劣勢鎖的劣勢Java虛擬機能夠對非競爭鎖的獲取和釋放進行優化，讓它們非常高效，但是如果有多個線程同時請求鎖，一些線程將可能被掛起，并稍后恢復運行。掛起和恢復線程會帶來很大的開銷，并通常伴有冗長的中斷。對于基于鎖，并且其操作過度細分的類（比如同步容器類，大多數方法只包含很少的操作），當頻繁地發生鎖的

2、競爭時，調度與真正用于工作的開銷間的比值會很可觀。 IBM&重慶大學15.1 鎖的劣勢鎖的劣勢當一個線程正在等待鎖時，它不能做任何其他事情。如果一個線程在持有鎖的情況下發生了延遲（原因包括頁錯誤、調度延遲，或者類似情況），那么其他所有需要該鎖的線程都不能前進了。如果阻塞的線程是優先級很高的線程，持有鎖的線程優先級較低，那么會造成性能風險，被稱為優先級倒置（priority inversion）。加鎖對于小的操作而言，仍然是重量級（heavy weight）的機制，比如自增操作。 IBM&重慶大學15.2 原子變量類原子變量類 所有原子變量類都公開“比較并設置”原語（與比較并交換

3、類似），這些原語都是使用平臺上可用的最快本機結構（比較并交換、加載鏈接/條件存儲，最壞的情況下是旋轉鎖）來實現的。IBM&重慶大學15.2 原子變量類原子變量類原子變量類共有12個，分成4組： 計量器 域更新器（field updater） 數組 復合變量最常用的原子變量是計量器：AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。他們都支持CAS（比較并設置）；AtomicInteger和AtomicLong還支持算術運算。 IBM&重慶大學15.2 原子變量類原子變量類原子變量類可以認為是volatile變量的泛化

4、，它擴展了volatile變量的概念，來支持原子條件的比較并設置更新。讀取和寫入原子變量與讀取和寫入對volatile變量的訪問具有相同的存取語義。 原子變量的操作會變為平臺提供的用于并發訪問的硬件原語 IBM&重慶大學15.2 原子變量類原子變量類調整具有競爭的并發應用程序的可伸縮性的通用技術是降低使用的鎖對象的粒度，希望更多的鎖請求從競爭變為不競爭。從鎖轉換為原子變量可以獲得相同的結果，通過切換為更細粒度的協調機制，競爭的操作就更少，從而提高了吞吐量。 IBM&重慶大學15.2 原子變量類原子變量類使用原子變量后的計數器：package jdkapidemo;importp

5、ublic class AtomicCounter private AtomicInteger value = new AtomicInteger();public int getValue() return value.get();public int increment() return value.incrementAndGet();IBM&重慶大學15.2 原子變量類原子變量類public int increment(int i) return value.addAndGet(i);public int decrement() return value.decrementAnd

6、Get();public int decrement(int i) return value.addAndGet(-i); IBM&重慶大學15.2 原子變量類原子變量類測試類： package jdkapidemo;public class AtomicCounterTest extends Thread AtomicCounter counter;public AtomicCounterTest(AtomicCounter counter) this.counter = counter;Overridepublic void run() int i = counter.increm

7、ent();System.out.println(generated number: + i);IBM&重慶大學15.2 原子變量類原子變量類public static void main(String args) AtomicCounter counter = new AtomicCounter();for (int i = 0; i 10; i+) /10個線程new AtomicCounterTest(counter).start();IBM&重慶大學15.2 原子變量類原子變量類運行結果如下：generated number:1generated number:2gen

8、erated number:3generated number:4generated number:5generated number:7generated number:6generated number:9generated number:10generated number:8會發現10個線程運行中，沒有重復的數字，原子量類使用本機CAS實現了值修改的原子性。 IBM&重慶大學15.3 非阻塞算法非阻塞算法 基于鎖的算法會帶來一些活躍度失敗的風險。 一個線程的失敗或掛起不應該影響其他線程的失敗或掛起，這樣的算法被稱為非阻塞（nonblocking）算法。 如果算法的每一步驟中都有

9、一些線程能夠繼續執行，那么這樣的算法稱為鎖自由（lock-free）算法。 IBM&重慶大學15.3 非阻塞算法非阻塞算法 非阻塞算法對死鎖和優先級倒置有“免疫性”。好的非阻塞算法已經應用到多種常見的數據結構上，包括棧、隊列、優先級隊列、哈希表。 在實現相同功能的前提下，非阻塞算法往往比基于鎖的算法更加復雜。 創建非阻塞算法的前提是為了維護數據的一致性，解決如何把原子化范圍縮小到一個唯一變量。 IBM&重慶大學15.3 非阻塞算法非阻塞算法 非阻塞算法相對于基于鎖的算法有幾個性能優勢： 它用硬件的原生形態代替Java虛擬機的鎖定代碼路徑，從而在更細的粒度層次上（獨立的內存位置）

10、進行同步 失敗的線程也可以立即重試，而不會被掛起后重新調度 更細的粒度降低了爭用的機會，不用重新調度就能重試的能力也降低了爭用的成本 即使有少量失敗的CAS操作，這種方法仍然會比由于鎖競爭造成的重新調度快得多 IBM&重慶大學15.3 非阻塞算法非阻塞算法 非阻塞堆棧的示例代碼：public class ConcurrentStack AtomicReferenceNode head = new AtomicReferenceNode(); public void push(E item) Node newHead = new Node(item); Node oldHead; do

11、oldHead = head.get(); newHead.next = oldHead; while (!pareAndSet(oldHead, newHead); IBM&重慶大學15.3 非阻塞算法非阻塞算法 public E pop() Node oldHead; Node newHead; do oldHead = head.get(); if (oldHead = null) return null; newHead = oldHead.next; while (!pareAndSet(oldHead,newHead); return oldHead.item; IBM&a

12、mp;重慶大學15.3 非阻塞算法非阻塞算法 static class Node final E item; Node next; public Node(E item) this.item = item; 對于上面代碼中的ConcurrentStack中的push()和pop()操作，其所做的工作有些冒險，希望在“提交”工作的時候，底層假設沒有失效。push()方法觀察當前的棧頂節點，并構建一個新節點放在堆棧上，然后，觀察最頂端的節點在初始之后有沒有變化，如果沒有變化，那么就安裝新節點。如果CAS失敗，意味著另一個線程已經修改了堆棧，那么過程就會重新開始。IBM&重慶大學15.3 非

13、阻塞算法非阻塞算法 所有非阻塞算法的一個基本特征是： 有些算法步驟的執行是要冒險的，因為假如CAS不成功，可能不得不重做。 非阻塞算法通常叫作樂觀算法，因為它們繼續操作的假設是不會有干擾；假如發現干擾，就會回退并重試。IBM&重慶大學15.3 非阻塞算法非阻塞算法 在輕度到中度的爭用情況下，非阻塞算法的性能會超越阻塞算法 因為CAS的多數時間都在第一次嘗試時就成功，而發生爭用時的開銷也不涉及線程掛起和上下文切換，只多了幾個循環迭代。 沒有爭用的CAS要比沒有爭用的鎖便宜得多（這句話肯定是真的，因為沒有爭用的鎖涉及CAS加上額外的處理），而爭用的CAS比爭用的鎖獲取涉及更短的延遲。 IB

14、M&重慶大學15.3 非阻塞算法非阻塞算法 在高度爭用的情況下（即有多個線程不斷爭用一個內存位置的時候），基于鎖的算法開始提供比非阻塞算法更好的吞吐率 因為當線程阻塞時，它就會停止爭用，耐心地等候輪到自己，從而避免了進一步爭用。 但是，這么高的爭用程度并不常見，因為多數時候，線程會把線程本地的計算與爭用共享數據的操作分開，從而給其他線程使用共享數據的機會。 同時，這么高的爭用程度也表明需要重新檢查算法，朝著更少共享數據的方向努力。IBM&重慶大學15.3 非阻塞算法非阻塞算法 如果深入Java虛擬機和操作系統，會發現非阻塞算法無處不在 垃圾收集器使用非阻塞算法加快并發和平行的垃圾搜集； 調度器使用非阻塞算法有效地調度線程和進程，實現內在鎖。 在Java 6中，基于鎖的