關于CAS的研究

• 引言
• 什麼是CAS
• CAS的目的及應用
• CAS存在的問題
• concurrent包的實作
• Refer

一、引言

在JDK 5之前Java語言是靠synchronized關鍵字保證同步的，這會導緻有鎖。

鎖機制存在以下問題：

（1）在多線程競争下，加鎖、釋放鎖會導緻比較多的上下文切換和排程延時，引起性能問題。

（2）一個線程持有鎖會導緻其它所有需要此鎖的線程挂起。

（3）如果一個優先級高的線程等待一個優先級低的線程釋放鎖會導緻優先級倒置，引起性能風險。

volatile是不錯的機制，但是volatile不能保證原子性。是以對于同步最終還是要回到鎖機制上來。

獨占鎖是一種悲觀鎖，synchronized就是一種獨占鎖，會導緻其它所有需要鎖的線程挂起，等待持有鎖的線程釋放鎖。而另一個更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。樂觀鎖用到的機制就是CAS，Compare and Swap。

二、什麼是CAS

CAS,compare and swap的縮寫，中文翻譯成比較并交換。

我們都知道，在java語言之前，并發就已經廣泛存在并在伺服器領域得到了大量的應用。是以硬體廠商老早就在晶片中加入了大量并發操作的原語，進而在硬體層面提升效率。在intel的CPU中，使用cmpxchg指令。

在Java發展初期，java語言是不能夠利用硬體提供的這些便利來提升系統的性能的。而随着java不斷的發展,Java本地方法(JNI)的出現，使得java程式越過JVM直接調用本地方法提供了一種便捷的方式，因而java在并發的手段上也多了起來。而在Doug Lea提供的cucurenct包中，CAS理論是它實作整個java包的基石。

CAS 操作包含三個操作數 —— 記憶體位置（V）、預期原值（A）和新值(B)。 如果記憶體位置的值與預期原值相比對，那麼處理器會自動将該位置值更新為新值 。否則，處理器不做任何操作。無論哪種情況，它都會在 CAS 指令之前傳回該 位置的值。（在 CAS 的一些特殊情況下将僅傳回 CAS 是否成功，而不提取目前 值。）CAS 有效地說明了“我認為位置 V 應該包含值 A；如果包含該值，則将 B 放到這個位置；否則，不要更改該位置，隻告訴我這個位置現在的值即可。”

通常将 CAS 用于同步的方式是從位址 V 讀取值 A，執行多步計算來獲得新 值 B，然後使用 CAS 将 V 的值從 A 改為 B。如果 V 處的值尚未同時更改，則 CAS 操作成功。

類似于 CAS 的指令允許算法執行讀-修改-寫操作，而無需害怕其他線程同時 修改變量，因為如果其他線程修改變量，那麼 CAS 會檢測它（并失敗），算法可以對該操作重新計算。

關于CPU的鎖有如下3種：

1 處理器自動保證基本記憶體操作的原子性

首先處理器會自動保證基本的記憶體操作的原子性。處理器保證從系統記憶體當中讀取或者寫入一個位元組是原子的，意思是當一個處理器讀取一個位元組時，其他處理器不能通路這個位元組的記憶體位址。奔騰6和最新的處理器能自動保證單處理器對同一個緩存行裡進行16/32/64位的操作是原子的，但是複雜的記憶體操作處理器不能自動保證其原子性，比如跨總線寬度，跨多個緩存行，跨頁表的通路。但是處理器提供總線鎖定和緩存鎖定兩個機制來保證複雜記憶體操作的原子性。

2 使用總線鎖保證原子性

第一個機制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進行讀改寫（i++就是經典的讀改寫操作）操作，那麼共享變量就會被多個處理器同時進行操作，這樣讀改寫操作就不是原子的，操作完之後共享變量的值會和期望的不一緻，舉個例子：如果i=1,我們進行兩次i++操作，我們期望的結果是3，但是有可能結果是2。

原因是有可能多個處理器同時從各自的緩存中讀取變量i，分别進行加一操作，然後分别寫入系統記憶體當中。那麼想要保證讀改寫共享變量的操作是原子的，就必須保證CPU1讀改寫共享變量的時候，CPU2不能操作該共享變量記憶體位址的緩存。

處理器使用總線鎖就是來解決這個問題的。所謂總線鎖就是使用處理器提供的一個LOCK＃信号，當一個處理器在總線上輸出此信号時，其他處理器的請求将被阻塞住,那麼該處理器可以獨占使用共享記憶體。

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的目的及應用

利用CPU的CAS指令，同時借助JNI來完成Java的非阻塞算法。其它原子操作都是利用類似的特性完成的。而整個J.U.C都是建立在CAS之上的，是以對于synchronized阻塞算法，J.U.C在上有了很大的提升。

非阻塞算法 （nonblocking algorithms）

一個線程的失敗或者挂起不應該影響其他線程的失敗或挂起的算法。

volatile 實作可見性，CAS 實作原子性，進而實作線程安全

現代的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 + ;
            if (compareAndSet(current, next))
                return next;
        }
    }
           

/**
* 模拟CAS
* 
* @param current
* @param next
* @return
*/
private synchronized boolean compareAndSet(int current, int next) {
if (current == value) {
value = next;
return true;
} else {
return false;
}
}
           

在這裡采用了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;

}
           

四、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

1. 循環時間長開銷大。自旋CAS如果長時間不成功，會給CPU帶來非常大的執行開銷。如果JVM能支援處理器提供的pause指令那麼效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取決于具體實作的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因記憶體順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），進而提高CPU的執行效率。
2. 隻能保證一個共享變量的原子操作。當對一個共享變量執行操作時，我們可以使用循環CAS的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性，這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量i＝2,j=a，合并一下ij=2a，然後用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象裡來進行CAS操作。

五、concurrent包的實作

由于java的CAS同時具有 volatile 讀和volatile寫的記憶體語義，是以Java線程之間的通信現在有了下面四種方式：

• A線程寫volatile變量，随後B線程讀這個volatile變量。
• A線程寫volatile變量，随後B線程用CAS更新這個volatile變量。
• A線程用CAS更新一個volatile變量，随後B線程用CAS更新這個volatile變量。
• A線程用CAS更新一個volatile變量，随後B線程讀這個volatile變量。

Java的CAS會使用現代處理器上提供的高效機器級别原子指令，這些原子指令以原子方式對記憶體執行讀-改-寫操作，這是在多處理器中實作同步的關鍵（從本質上來說，能夠支援原子性讀-改-寫指令的計算機器，是順序計算圖靈機的異步等價機器，是以任何現代的多處理器都會去支援某種能對記憶體執行原子性讀-改-寫操作的原子指令）。同時，volatile變量的讀/寫和CAS可以實作線程之間的通信。把這些特性整合在一起，就形成了整個concurrent包得以實作的基石。如果我們仔細分析concurrent包的源代碼實作，會發現一個通用化的實作模式：

• 首先，聲明共享變量為volatile；
• 然後，使用CAS的原子條件更新來實作線程之間的同步；
• 同時，配合以volatile的讀/寫和CAS所具有的volatile讀和寫的記憶體語義來實作線程之間的通信。

AQS，非阻塞資料結構和原子變量類（java.util.concurrent.atomic包中的類），這些concurrent包中的基礎類都是使用這種模式來實作的，而concurrent包中的高層類又是依賴于這些基礎類來實作的。從整體來看，concurrent包的實作示意圖如下：

六、Refer

1、JAVA CAS實作原理與使用

2、Java中CAS詳解

3、非阻塞同步算法與CAS(Compare and Swap)無鎖算法

4、JAVA并發程式設計學習筆記之CAS操作

5、為什麼volatile不能保證原子性而Atomic可以？

6、原子操作的原理