1 CAS

1.1 CAS應(yīng)用分析

CAS:Compare and Swap, 翻譯成比較并交換。
java.util.concurrent包中借助CAS實(shí)現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂觀鎖。

本文先從CAS的應(yīng)用說起，再深入原理解析。

CAS有3個(gè)操作數(shù)，內(nèi)存值V，舊的預(yù)期值A，要修改的新值B。當(dāng)且僅當(dāng)預(yù)期值A和內(nèi)存值V相同時(shí)，將內(nèi)存值V修改為B，否則什么都不做。

看下非阻塞算法 （nonblocking algorithms）

一個(gè)線程的失敗或者掛起不應(yīng)該影響其他線程的失敗或掛起的算法。
現(xiàn)代的CPU提供了特殊的指令，可以自動更新共享數(shù)據(jù)，而且能夠檢測到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。
那么拿出AtomicInteger來研究在沒有鎖的情況下是如何做到數(shù)據(jù)正確性的。
private volatile int value;
首先毫無以為，在沒有鎖的機(jī)制下可能需要借助volatile原語，保證線程間的數(shù)據(jù)是可見的（共享的）。
這樣才獲取變量的值的時(shí)候才能直接讀取。

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操作，每次從內(nèi)存中讀取數(shù)據(jù)然后將此數(shù)據(jù)和+1后的結(jié)果進(jìn)行CAS操作，如果成功就返回結(jié)果，否則重試直到成功為止。
而compareAndSet利用JNI來完成CPU指令的操作

public final boolean compareAndSet(int expect, int update) {   
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

整體的過程就是這樣子的，利用CPU的CAS指令，同時(shí)借助JNI來完成Java的非阻塞算法。其它原子操作都是利用類似的特性完成的。
其中unsafe.compareAndSwapInt(this, valueOffset, expect, update);
類似與：

if (this == expect) {
  this = update
 return true;
} else {
return false;
}

那么問題就來了，成功過程中需要2個(gè)步驟：比較this == expect，替換this = update，compareAndSwapInt如何這兩個(gè)步驟的原子性呢

1.2 CAS原理

CAS通過調(diào)用JNI的代碼實(shí)現(xiàn)的。JNI:Java Native Interface為JAVA本地調(diào)用，允許java調(diào)用其他語言。
而compareAndSwapInt就是借助C來調(diào)用CPU底層指令實(shí)現(xiàn)的。
下面從分析比較常用的CPU（intel x86）來解釋CAS的實(shí)現(xiàn)原理。
下面是sun.misc.Unsafe類的compareAndSwapInt()方法的源代碼：

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

可以看到這是個(gè)本地方法調(diào)用。這個(gè)本地方法在openjdk中依次調(diào)用的c++代碼為：unsafe.cpp，atomic.cpp和atomicwindowsx86.inline.hpp。這個(gè)本地方法的最終實(shí)現(xiàn)在openjdk的如下位置：openjdk-7-fcs-src-b147-27jun2011\openjdk\hotspot\src\oscpu\windowsx86\vm\ atomicwindowsx86.inline.hpp（對應(yīng)于windows操作系統(tǒng)，X86處理器）。下面是對應(yīng)于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
  }
}

如上面源代碼所示，程序會根據(jù)當(dāng)前處理器的類型來決定是否為cmpxchg指令添加lock前綴。如果程序是在多處理器上運(yùn)行，就為cmpxchg指令加上lock前綴（lock cmpxchg）。反之，如果程序是在單處理器上運(yùn)行，就省略lock前綴（單處理器自身會維護(hù)單處理器內(nèi)的順序一致性，不需要lock前綴提供的內(nèi)存屏障效果）。

intel的手冊對lock前綴的說明如下：
確保對內(nèi)存的讀-改-寫操作原子執(zhí)行。在Pentium及Pentium之前的處理器中，帶有lock前綴的指令在執(zhí)行期間會鎖住總線，使得其他處理器暫時(shí)無法通過總線訪問內(nèi)存。很顯然，這會帶來昂貴的開銷。從Pentium 4，Intel X eon及P6處理器開始，intel在原有總線鎖的基礎(chǔ)上做了一個(gè)很有意義的優(yōu)化：如果要訪問的內(nèi)存區(qū)域（area of memory）在lock前綴指令執(zhí)行期間已經(jīng)在處理器內(nèi)部的緩存中被鎖定（即包含該內(nèi)存區(qū)域的緩存行當(dāng)前處于獨(dú)占或以修改狀態(tài)），并且該內(nèi)存區(qū)域被完全包含在單個(gè)緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會一直被鎖定，其它處理器無法讀/寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個(gè)操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷，但是當(dāng)多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時(shí)，仍然會鎖住總線。
禁止該指令與之前和之后的讀和寫指令重排序。
把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

1.3 CPU鎖分類

見下面的原子操作

1.4 CAS缺點(diǎn)

CAS優(yōu)勢：

• 無鎖機(jī)制：CAS 是一種無鎖的原子操作，這比傳統(tǒng)的基于鎖（如 synchronized 或 ReentrantLock）的并發(fā)控制更加高效。
• 性能優(yōu)越：因?yàn)?CAS 并不需要阻塞線程，所以在高并發(fā)場景下，CAS 的性能優(yōu)于傳統(tǒng)鎖的實(shí)現(xiàn)。
• 簡潔性：相比加鎖，CAS 的實(shí)現(xiàn)非常簡單，不需要額外的同步代碼，能輕松做到線程安全。

CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環(huán)時(shí)間長開銷大和只能保證一個(gè)共享變量的原子操作

1.4.1 ABA問題

因?yàn)?code>CAS需要在操作值的時(shí)候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新，但是如果一個(gè)值原來是A，變成了B，又變成了A，那么使用CAS進(jìn)行檢查時(shí)會發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實(shí)際上卻變化了。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時(shí)候把版本號加一，那么A－B－A 就會變成1A-2B－3A。
從Java1.5開始JDK的atomic包里提供了一個(gè)類AtomicStampedReference來解決ABA問題。這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值。
關(guān)于ABA問題參考文檔: http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html

1.4.2 循環(huán)時(shí)間長開銷大

自旋CAS如果長時(shí)間不成功，會給CPU帶來非常大的執(zhí)行開銷。如果JVM能支持處理器提供的pause指令那么效率會有一定的提升，pause指令有兩個(gè)作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會消耗過多的執(zhí)行資源，延遲的時(shí)間取決于具體實(shí)現(xiàn)的版本，在一些處理器上延遲時(shí)間是零。第二它可以避免在退出循環(huán)的時(shí)候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執(zhí)行效率。

1.4.3 只能保證一個(gè)共享變量的原子操作

只能保證一個(gè)共享變量的原子操作，當(dāng)對一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對多個(gè)共享變量操作時(shí)，循環(huán)CAS就無法保證操作的原子性，這個(gè)時(shí)候就可以用鎖，或者有一個(gè)取巧的辦法，就是把多個(gè)共享變量合并成一個(gè)共享變量來操作。比如有兩個(gè)共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個(gè)變量放在一個(gè)對象里來進(jìn)行CAS操作。

1.5 concurrent包的實(shí)現(xiàn)

由于java的CAS同時(shí)具有 volatile 讀和volatile寫的內(nèi)存語義，因此Java線程之間的通信現(xiàn)在有了下面四種方式：

• A線程寫volatile變量，隨后B線程讀這個(gè)volatile變量。
• A線程寫volatile變量，隨后B線程用CAS更新這個(gè)volatile變量。
• A線程用CAS更新一個(gè)volatile變量，隨后B線程用CAS更新這個(gè)volatile變量。
• A線程用CAS更新一個(gè)volatile變量，隨后B線程讀這個(gè)volatile變量。

Java的CAS會使用現(xiàn)代處理器上提供的高效機(jī)器級別原子指令，這些原子指令以原子方式對內(nèi)存執(zhí)行讀-改-寫操作，這是在多處理器中實(shí)現(xiàn)同步的關(guān)鍵（從本質(zhì)上來說，能夠支持原子性讀-改-寫指令的計(jì)算機(jī)器，是順序計(jì)算圖靈機(jī)的異步等價(jià)機(jī)器，因此任何現(xiàn)代的多處理器都會去支持某種能對內(nèi)存執(zhí)行原子性讀-改-寫操作的原子指令）。同時(shí)，volatile變量的讀/寫和CAS可以實(shí)現(xiàn)線程之間的通信。把這些特性整合在一起，就形成了整個(gè)concurrent包得以實(shí)現(xiàn)的基石。如果我們仔細(xì)分析concurrent包的源代碼實(shí)現(xiàn)，會發(fā)現(xiàn)一個(gè)通用化的實(shí)現(xiàn)模式：

• 聲明共享變量為volatile；
• 使用CAS的原子條件更新來實(shí)現(xiàn)線程之間的同步；
• 配合以volatile的讀/寫和CAS所具有的volatile讀和寫的內(nèi)存語義來實(shí)現(xiàn)線程之間的通信。

AQS，非阻塞數(shù)據(jù)結(jié)構(gòu)和原子變量類（java.util.concurrent.atomic包中的類），這些concurrent包中的基礎(chǔ)類都是使用這種模式來實(shí)現(xiàn)的，而concurrent包中的高層類又是依賴于這些基礎(chǔ)類來實(shí)現(xiàn)的。從整體來看，concurrent包的實(shí)現(xiàn)示意圖如下：

在這里插入圖片描述

1.6 和其他鎖比較

1.6.1 CAS鎖和Synchronized比較

假如cas可以保證操作的線程安全嗎，為什么還要用Synchronized呢
原因：CAS也是適用一些場合的，比如資源競爭小時(shí)，是非常適用的，不用進(jìn)行內(nèi)核態(tài)和用戶態(tài)之間的線程上下文切換，同時(shí)自旋概率也會大大減少，提升性能，但資源競爭激烈時(shí)（比如大量線程對同一資源進(jìn)行寫和讀操作）并不適用，自旋概率會大大增加，浪費(fèi)CPU資源，降低性能，就很不劃算
點(diǎn)此了解Synchronized更多知識點(diǎn)

2 原子操作

2.1 引言

原子（atom）本意是不能被進(jìn)一步分割的最小粒子，而原子操作（atomic operation）意為不可被中斷的一個(gè)或一系列操作 。在多處理器上實(shí)現(xiàn)原子操作就變得有點(diǎn)復(fù)雜。本文讓我們一起來聊一聊在Inter處理器和Java里是如何實(shí)現(xiàn)原子操作的

2.2 術(shù)語定義

2.3 處理器如何實(shí)現(xiàn)原子操作

現(xiàn)在大致cpu,緩存,主存圖示

在這里插入圖片描述

2.3.1 處理器自動保證基本內(nèi)存操作的原子性

首先處理器會自動保證基本的內(nèi)存操作的原子性。 處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個(gè)字節(jié)是原子的，意思是當(dāng)一個(gè)處理器讀取一個(gè)字節(jié)時(shí)，其他處理器不能訪問這個(gè)字節(jié)的內(nèi)存地址 。奔騰6和最新的處理器能自動保證單處理器對同一個(gè)緩存行里進(jìn)行16/32/64位的操作是原子的，但是復(fù)雜的內(nèi)存操作處理器不能自動保證其原子性，比如跨總線寬度，跨多個(gè)緩存行，跨頁表的訪問。但是處理器提供 總線鎖定 和 緩存鎖定 兩個(gè)機(jī)制來保證復(fù)雜內(nèi)存操作的原子性

2.3.2 使用總線鎖保證原子性

第一個(gè)機(jī)制是通過總線鎖保證原子性。如果多個(gè)處理器同時(shí)對共享變量進(jìn)行讀改寫（i++就是經(jīng)典的讀改寫操作）操作，那么共享變量就會被多個(gè)處理器同時(shí)進(jìn)行操作，這樣讀改寫操作就不是原子的，操作完之后共享變量的值會和期望的不一致，舉個(gè)例子：如果i=1,我們進(jìn)行兩次i++操作，我們期望的結(jié)果是3，但是有可能結(jié)果是2。如下圖

在這里插入圖片描述

2.3.3 使用緩存鎖保證原子性

第二個(gè)機(jī)制是通過緩存鎖定保證原子性。在同一時(shí)刻我們只需保證對某個(gè)內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間通信鎖住了，這使得鎖定期間，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)，所以總線鎖定的開銷比較大，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進(jìn)行優(yōu)化。
頻繁使用的內(nèi)存會緩存在處理器的L1，L2和L3高速緩存里，那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行，并不需要聲明總線鎖，在奔騰6和最近的處理器中可以使用緩存鎖定的方式來實(shí)現(xiàn)復(fù)雜的原子性。
所謂緩存鎖定就是如果緩存在處理器緩存行中內(nèi)存區(qū)域在LOCK操作期間被鎖定，當(dāng)它執(zhí)行鎖操作回寫內(nèi)存時(shí)，處理器不在總線上聲言LOCK＃信號，而是修改內(nèi)部的內(nèi)存地址，并允許它的緩存一致性機(jī)制來保證操作的原子性，因?yàn)榫彺嬉恢滦詸C(jī)制會阻止被兩個(gè)以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù)同時(shí)修改，當(dāng)其他處理器回寫已被鎖定的緩存行的數(shù)據(jù)時(shí)會起緩存行無效，在例1中，當(dāng)CPU1修改緩存行中的i時(shí)使用緩存鎖定，那么CPU2就不能同時(shí)緩存了i的緩存行。

緩存一致性協(xié)議中，最出名的就是Intel 的MESI協(xié)議，MESI協(xié)議保證了每個(gè)緩存中使用的共享變量的副本是一致的。它核心的思想是：當(dāng)CPU寫數(shù)據(jù)時(shí)，如果發(fā)現(xiàn)操作的變量是共享變量，即在其他CPU中也存在該變量的副本，會發(fā)出信號通知其他CPU將該變量的緩存行置為無效狀態(tài)，因此當(dāng)其他CPU需要讀取這個(gè)變量時(shí)，發(fā)現(xiàn)自己緩存中緩存該變量的緩存行是無效的，那么它就會從內(nèi)存重新讀取

但是有兩種情況下處理器不會使用緩存鎖定。
第一種情況是：當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部，或操作的數(shù)據(jù)跨多個(gè)緩存行（cache line），則處理器會調(diào)用總線鎖定。第二種情況是：有些處理器不支持緩存鎖定。對于Inter486和奔騰處理器,就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會調(diào)用總線鎖定。
以上兩個(gè)機(jī)制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實(shí)現(xiàn)。比如位測試和修改指令BTS，BTR，BTC，交換指令XADD，CMPXCHG和其他一些操作數(shù)和邏輯指令，比如ADD（加），OR（或）等，被這些指令操作的內(nèi)存區(qū)域就會加鎖，導(dǎo)致其他處理器不能同時(shí)訪問它

點(diǎn)擊了解volatile中偽共享問題

2.4 JAVA如何實(shí)現(xiàn)原子操作

在java中可以通過鎖和循環(huán)CAS的方式來實(shí)現(xiàn)原子操作。

2.4.1 使用循環(huán)CAS實(shí)現(xiàn)原子操作

JVM中的CAS操作正是利用了上面中提到的處理器提供的CMPXCHG指令實(shí)現(xiàn)的。自旋CAS實(shí)現(xiàn)的基本思路就是循環(huán)進(jìn)行CAS操作直到成功為止，以下代碼實(shí)現(xiàn)了一個(gè)基于CAS線程安全的計(jì)數(shù)器方法safeCount和一個(gè)非線程安全的計(jì)數(shù)器count

    public class Counter {
       private AtomicInteger atomicI = new AtomicInteger(0);
       private int i = 0;
       public static void main(String[] args) {
              final Counter cas = new Counter();
              List<Thread> ts = new ArrayList<Thread>(600);
              long start = System.currentTimeMillis();
              for (int j = 0; j < 100; j++) {
                     Thread t = new Thread(new Runnable() {
                            @Override
                            public void run() {
                                   for (int i = 0; i < 10000; i++) {
                                          cas.count();
                                          cas.safeCount();
                                   }
                            }
                     });
                     ts.add(t);
              }
              for (Thread t : ts) {
                     t.start();
              }
       // 等待所有線程執(zhí)行完成
              for (Thread t : ts) {
                     try {
                            t.join();
                     } catch (InterruptedException e) {
                            e.printStackTrace();
                     }
              }
              System.out.println(cas.i);
              System.out.println(cas.atomicI.get());
              System.out.println(System.currentTimeMillis() - start);
       }
       /**
        * 使用CAS實(shí)現(xiàn)線程安全計(jì)數(shù)器
        */
       private void safeCount() {
              for (;;) {
                     int i = atomicI.get();
                     boolean suc = atomicI.compareAndSet(i, ++i);
                     if (suc) {
                            break;
                     }
              }
       }
       /**
        * 非線程安全計(jì)數(shù)器
        */
       private void count() {
              i++;
       }
}

從Java1.5開始JDK的并發(fā)包里提供了一些類來支持原子操作，如AtomicBoolean（用原子方式更新的 boolean 值），AtomicInteger（用原子方式更新的 int 值），AtomicLong（用原子方式更新的 long 值），這些原子包裝類還提供了有用的工具方法，比如以原子的方式將當(dāng)前值自增1和自減1。
在Java并發(fā)包中有一些并發(fā)框架也使用了自旋CAS的方式來實(shí)現(xiàn)原子操作，比如LinkedTransferQueue類的Xfer方法。CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環(huán)時(shí)間長開銷大和只能保證一個(gè)共享變量的原子操作

2.4.2 使用鎖機(jī)制實(shí)現(xiàn)原子操作

鎖機(jī)制保證了只有獲得鎖的線程能夠操作鎖定的內(nèi)存區(qū)域。JVM內(nèi)部實(shí)現(xiàn)了很多種鎖機(jī)制，有偏向鎖，輕量級鎖和互斥鎖，有意思的是除了偏向鎖，JVM實(shí)現(xiàn)鎖的方式都用到的循環(huán)CAS，當(dāng)一個(gè)線程想進(jìn)入同步塊的時(shí)候使用循環(huán)CAS的方式來獲取鎖，當(dāng)它退出同步塊的時(shí)候使用循環(huán)CAS釋放鎖