出自 [JAVA CAS原理深度分析](http://blog.csdn.net/hsuxu/article/details/9467651) [TOC=1,2] 看了一堆文章，終于把JAVA CAS的原理深入分析清楚了。 感謝GOOGLE強大的搜索，借此挖苦下百度，依靠百度什么都學習不到！ 參考文檔： http://www.blogjava.net/xylz/archive/2010/07/04/325206.html http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html http://www.searchsoa.com.cn/showcontent_69238.htm http://ifeve.com/atomic-operation/ http://www.infoq.com/cn/articles/java-memory-model-5 java.util.concurrent包完全建立在CAS之上的，沒有CAS就不會有此包。可見CAS的重要性。 ? ## **CAS** CAS:Compare and Swap, 翻譯成比較并交換。? java.util.concurrent包中借助CAS實現了區別于synchronouse同步鎖的一種樂觀鎖。 本文先從CAS的應用說起，再深入原理解析。 ## **CAS應用** CAS有3個操作數，內存值V，舊的預期值A，要修改的新值B。當且僅當預期值A和內存值V相同時，將內存值V修改為B，否則什么都不做。 ## **非阻塞算法 （nonblocking algorithms）** > 一個線程的失敗或者掛起不應該影響其他線程的失敗或掛起的算法。 現代的CPU提供了特殊的指令，可以自動更新共享數據，而且能夠檢測到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。 拿出AtomicInteger來研究在沒有鎖的情況下是如何做到數據正確性的。 > private volatile int value; 首先毫無以為，在沒有鎖的機制下可能需要借助volatile原語，保證線程間的數據是可見的（共享的）。 這樣才獲取變量的值的時候才能直接讀取。 > public final int get() { > ??????? return value; > ??? } 然后來看看++i是怎么做到的。 > public final int incrementAndGet() { > ??? for (;;) { > ??????? int current = get(); > ??????? int next = current + 1; > ??????? if (compareAndSet(current, next)) > ??????????? return next; > ??? } > } 在這里采用了CAS操作，每次從內存中讀取數據然后將此數據和+1后的結果進行CAS操作，如果成功就返回結果，否則重試直到成功為止。 而compareAndSet利用JNI來完成CPU指令的操作。 > public final boolean compareAndSet(int expect, int update) {??? > ??? return unsafe.compareAndSwapInt(this, valueOffset, expect, update); > ??? } 整體的過程就是這樣子的，利用CPU的CAS指令，同時借助JNI來完成Java的非阻塞算法。其它原子操作都是利用類似的特性完成的。 其中 unsafe.compareAndSwapInt(this, valueOffset, expect, update); 類似： if (this ==?expect) { ? this =?update ?return true; } else { return false; } 那么問題就來了，成功過程中需要2個步驟：比較this ==?expect，替換this =?update，compareAndSwapInt如何這兩個步驟的原子性呢？ 參考CAS的原理。 ## **CAS原理** ?CAS通過調用JNI的代碼實現的。JNI:Java Native Interface為JAVA本地調用，允許java調用其他語言。 而compareAndSwapInt就是借助C來調用CPU底層指令實現的。 下面從分析比較常用的CPU（intel x86）來解釋CAS的實現原理。 ?下面是sun.misc.Unsafe類的compareAndSwapInt()方法的源代碼： ~~~ public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x); ~~~ 可以看到這是個本地方法調用。這個本地方法在openjdk中依次調用的c++代碼為：unsafe.cpp，atomic.cpp和atomic*windows*x86.inline.hpp。這個本地方法的最終實現在openjdk的如下位置：openjdk-7-fcs-src-b147-27*jun*2011\openjdk\hotspot\src\os*cpu\windows*x86\vm\ atomic*windows*x86.inline.hpp（對應于windows操作系統，X86處理器）。下面是對應于intel x86處理器的源代碼的片段： ~~~ // Adding a lock prefix to an instruction on MP machine // VC++ doesn't like the lock prefix to be on a single line // so we can't insert a label after the lock prefix. // By emitting a lock prefix, we can define a label after it. #define LOCK_IF_MP(mp) __asm cmp mp, 0 \ __asm je L0 \ __asm _emit 0xF0 \ __asm L0: inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) { // alternative for InterlockedCompareExchange int mp = os::is_MP(); __asm { mov edx, dest mov ecx, exchange_value mov eax, compare_value LOCK_IF_MP(mp) cmpxchg dword ptr [edx], ecx } } ~~~ 如上面源代碼所示，程序會根據當前處理器的類型來決定是否為cmpxchg指令添加lock前綴。如果程序是在多處理器上運行，就為cmpxchg指令加上lock前綴（lock cmpxchg）。反之，如果程序是在單處理器上運行，就省略lock前綴（單處理器自身會維護單處理器內的順序一致性，不需要lock前綴提供的內存屏障效果）。 ## ?intel的手冊對lock前綴的說明如下： 1. 確保對內存的讀-改-寫操作原子執行。在Pentium及Pentium之前的處理器中，帶有lock前綴的指令在執行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內存。很顯然，這會帶來昂貴的開銷。從Pentium 4，Intel Xeon及P6處理器開始，intel在原有總線鎖的基礎上做了一個很有意義的優化：如果要訪問的內存區域（area of memory）在lock前綴指令執行期間已經在處理器內部的緩存中被鎖定（即包含該內存區域的緩存行當前處于獨占或以修改狀態），并且該內存區域被完全包含在單個緩存行（cache line）中，那么處理器將直接執行該指令。由于在指令執行期間該緩存行會一直被鎖定，其它處理器無法讀/寫該指令要訪問的內存區域，因此能保證指令執行的原子性。這個操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低lock前綴指令的執行開銷，但是當多處理器之間的競爭程度很高或者指令訪問的內存地址未對齊時，仍然會鎖住總線。 2. 禁止該指令與之前和之后的讀和寫指令重排序。 3. 把寫緩沖區中的所有數據刷新到內存中。 ## 備注知識： 關于CPU的鎖有如下3種： 　　3.1 處理器自動保證基本內存操作的原子性 　　首先處理器會自動保證基本的內存操作的原子性。處理器保證從系統內存當中讀取或者寫入一個字節是原子的，意思是當一個處理器讀取一個字節時，其他處理器不能訪問這個字節的內存地址。奔騰6和最新的處理器能自動保證單處理器對同一個緩存行里進行16/32/64位的操作是原子的，但是復雜的內存操作處理器不能自動保證其原子性，比如跨總線寬度，跨多個緩存行，跨頁表的訪問。但是處理器提供總線鎖定和緩存鎖定兩個機制來保證復雜內存操作的原子性。? 　　3.2 使用總線鎖保證原子性 　　第一個機制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進行讀改寫（i++就是經典的讀改寫操作）操作，那么共享變量就會被多個處理器同時進行操作，這樣讀改寫操作就不是原子的，操作完之后共享變量的值會和期望的不一致，舉個例子：如果i=1,我們進行兩次i++操作，我們期望的結果是3，但是有可能結果是2。如下圖  　　原因是有可能多個處理器同時從各自的緩存中讀取變量i，分別進行加一操作，然后分別寫入系統內存當中。那么想要保證讀改寫共享變量的操作是原子的，就必須保證CPU1讀改寫共享變量的時候，CPU2不能操作緩存了該共享變量內存地址的緩存。 　　處理器使用總線鎖就是來解決這個問題的。所謂總線鎖就是使用處理器提供的一個LOCK＃信號，當一個處理器在總線上輸出此信號時，其他處理器的請求將被阻塞住,那么該處理器可以獨占使用共享內存。 　　3.3 使用緩存鎖保證原子性 　　第二個機制是通過緩存鎖定保證原子性。在同一時刻我們只需保證對某個內存地址的操作是原子性即可，但總線鎖定把CPU和內存之間通信鎖住了，這使得鎖定期間，其他處理器不能操作其他內存地址的數據，所以總線鎖定的開銷比較大，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進行優化。 　　頻繁使用的內存會緩存在處理器的L1，L2和L3高速緩存里，那么原子操作就可以直接在處理器內部緩存中進行，并不需要聲明總線鎖，在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實現復雜的原子性。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內存區域在LOCK操作期間被鎖定，當它執行鎖操作回寫內存時，處理器不在總線上聲言LOCK＃信號，而是修改內部的內存地址，并允許它的緩存一致性機制來保證操作的原子性，因為緩存一致性機制會阻止同時修改被兩個以上處理器緩存的內存區域數據，當其他處理器回寫已被鎖定的緩存行的數據時會起緩存行無效，在例1中，當CPU1修改緩存行中的i時使用緩存鎖定，那么CPU2就不能同時緩存了i的緩存行。 　　但是有兩種情況下處理器不會使用緩存鎖定。第一種情況是：當操作的數據不能被緩存在處理器內部，或操作的數據跨多個緩存行（cache line），則處理器會調用總線鎖定。第二種情況是：有些處理器不支持緩存鎖定。對于Inter486和奔騰處理器,就算鎖定的內存區域在處理器的緩存行中也會調用總線鎖定。 　　以上兩個機制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實現。比如位測試和修改指令BTS，BTR，BTC，交換指令XADD，CMPXCHG和其他一些操作數和邏輯指令，比如ADD（加），OR（或）等，被這些指令操作的內存區域就會加鎖，導致其他處理器不能同時訪問它。 ## **CAS缺點** ?CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環時間長開銷大和只能保證一個共享變量的原子操作 1\. ?**ABA問題**。因為CAS需要在操作值的時候檢查下值有沒有發生變化，如果沒有發生變化則更新，但是如果一個值原來是A，變成了B，又變成了A，那么使用CAS進行檢查時會發現它的值沒有發生變化，但是實際上卻變化了。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加一，那么A－B－A 就會變成1A-2B－3A。 **從Java1**.5開始JDK的atomic包里提供了一個類AtomicStampedReference來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當前引用是否等于預期引用，并且當前標志是否等于預期標志，如果全部相等，則以原子方式將該引用和該標志的值設置為給定的更新值。 關于ABA問題參考文檔:?http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html **2\. 循環時間長開銷大**。自旋CAS如果長時間不成功，會給CPU帶來非常大的執行開銷。如果JVM能支持處理器提供的pause指令那么效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取決于具體實現的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因內存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執行效率。 **3\. 只能保證一個共享變量的原子操作**。當對一個共享變量執行操作時，我們可以使用循環CAS的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性，這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了**AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象里來進行CAS操作。** ## concurrent包的實現 由于java的CAS同時具有 volatile 讀和volatile寫的內存語義，因此Java線程之間的通信現在有了下面四種方式： 1. A線程寫volatile變量，隨后B線程讀這個volatile變量。 2. A線程寫volatile變量，隨后B線程用CAS更新這個volatile變量。 3. A線程用CAS更新一個volatile變量，隨后B線程用CAS更新這個volatile變量。 4. A線程用CAS更新一個volatile變量，隨后B線程讀這個volatile變量。 Java的CAS會使用現代處理器上提供的高效機器級別原子指令，這些原子指令以原子方式對內存執行讀-改-寫操作，這是在多處理器中實現同步的關鍵（從本質上來說，能夠支持原子性讀-改-寫指令的計算機器，是順序計算圖靈機的異步等價機器，因此任何現代的多處理器都會去支持某種能對內存執行原子性讀-改-寫操作的原子指令）。同時，volatile變量的讀/寫和CAS可以實現線程之間的通信。把這些特性整合在一起，就形成了整個concurrent包得以實現的基石。如果我們仔細分析concurrent包的源代碼實現，會發現一個通用化的實現模式： 1. 首先，聲明共享變量為volatile； 2. 然后，使用CAS的原子條件更新來實現線程之間的同步； 3. 同時，配合以volatile的讀/寫和CAS所具有的volatile讀和寫的內存語義來實現線程之間的通信。 AQS，非阻塞數據結構和原子變量類（java.util.concurrent.atomic包中的類），這些concurrent包中的基礎類都是使用這種模式來實現的，而concurrent包中的高層類又是依賴于這些基礎類來實現的。從整體來看，concurrent包的實現示意圖如下：