一、并發(fā)模擬

首先，用1000個客戶端進(jìn)程來模擬并發(fā)，并使用信號量Semaphore 控制同時100個線程并發(fā)執(zhí)行，采用同步器CountDownLatch 確保并發(fā)線程總數(shù)執(zhí)行完成。模擬代碼如下：

// 請求總數(shù)
public static int clientTotal = 1000;
// 同時并發(fā)執(zhí)行的線程數(shù)
public static int threadTotal = 100;
public static int count = 0;


public static void main(String[] args) throws Exception {
    ExecutorService executorService = Executors.newCachedThreadPool();
    final Semaphore semaphore = new Semaphore(threadTotal);
    final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
    for (int i = 0; i < clientTotal ; i++) {
        executorService.execute(() - > {
            try {
                semaphore.acquire();
                add();
                semaphore.release();
            } catch (Exception e) {
                log.error("exception", e);
            }
            countDownLatch.countDown();
        });
    }
    countDownLatch.await();
    executorService.shutdown();
    log.info("count:{}", count);
}


private static void add() {
    count++;
}

1. 同步器CountDownLatch

同步器CountDownLatch是計數(shù)器向下減的閉鎖；保證線程執(zhí)行完再進(jìn)行其他的處理。工作原理圖如下：

主線程調(diào)用await()方法后進(jìn)入等待狀態(tài)，其他線程每次調(diào)用countDown()會使同步器計數(shù)減1，當(dāng)同步器計數(shù)為0時，主線程繼續(xù)執(zhí)行。

2. 同步器Semaphore

同步器Semaphore的作用是阻塞線程，并且控制同一時間的請求的并發(fā)量。工作原理同CountDownLatch，不同的是Semaphore計數(shù)是向上計數(shù)，使用前需要指定一個目標(biāo)數(shù)值。

上述并發(fā)模擬代碼我們多次執(zhí)行，發(fā)現(xiàn)是線程不安全的，原因是i++不是原子性的。我們反編譯如下代碼：

public void inc() {
    ++i;
}

使用Javap -c命令查看匯編代碼，如下：

public void inc() {
    Code:
      0: aload_0
      1: dup
      2: getfield     
      5: lconst_1
      6: ladd
      7: putfield     
     10: return
}

由此可見，簡單的++i由2，5，6，7四步組成：

• 2是獲取當(dāng)前i的值并放入棧頂
• 5是把常量1放入棧頂
• 6是把當(dāng)前棧頂中兩個值相加并把結(jié)果放入棧頂
• 7是把棧頂?shù)慕Y(jié)果賦給i變量

因此，java中簡單的一句++i被轉(zhuǎn)換成匯編后就不具有原子性了。這里保證多個操作的原子性可以使用synchronized來實(shí)現(xiàn)i的內(nèi)存可見性，但更好的方式是使用非阻塞的CAS算法實(shí)現(xiàn)的原子性操作類。下面我們使用cas把它改造成線程安全的。

二、CAS原理

1.cas保證原子性

并發(fā)模擬代碼修改：

public static AtomicLong count = new AtomicLong(0);


private static void add() {
    count.incrementAndGet();
}

incrementAndGet源碼：

public final long incrementAndGet() {
    return unsafe.getAndAddLong(this, valueOffset, 1L) + 1L;
}

getAndAddLong源碼：

public final long getAndAddLong(Object var1, long var2, long var4) {
    long var6;
    do {
        var6 = this.getLongVolatile(var1, var2);
    } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));


    return var6;
}

// 用native標(biāo)識的方法，代表的是java底層的方法，不是用java實(shí)現(xiàn)的
public native long getLongVolatile(Object var1, long var2);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

方法調(diào)用過程：

• var1指的是當(dāng)前傳過來的count對象
• var2指的是當(dāng)前的值
• var4指的是數(shù)字1
• var6指的是調(diào)用底層方法得到底層當(dāng)前的值，如果沒有其他線程處理count變量的時候，正常返回var2的值

對于var1這個對象，如果當(dāng)前的值var2跟底層的值var6相同的話，就把底層的值var6更新成var6 + var4。那么為什么會出現(xiàn)當(dāng)前的值var2跟底層的值var6不相同的情況呢？答案是和java內(nèi)存模型有關(guān)，關(guān)于java內(nèi)存模型我們下次再詳細(xì)介紹。

2.cas底層原理

分析getAndAddLong源碼：CAS有四個操作數(shù)，分別為：對象內(nèi)存位置，對象中的變量的偏移量，變量預(yù)期值和新值。其操作含義是，如果對象obj中內(nèi)存偏移量為valueOffset的變量值為expect，則使用新的值update替換舊值expect。此操作具有 volatile 讀和寫的內(nèi)存語義。

下面分別從編譯器和處理器的角度來分析,CAS 如何同時具有 volatile 讀和 volatile 寫的內(nèi)存語義。

編譯器

編譯器不會對 volatile 讀與 volatile 讀后面的任意內(nèi)存操作重排序；編譯器不會對 volatile 寫與 volatile 寫前面的任意內(nèi)存操作重排序。組合這兩個條件，意味著為了同時實(shí)現(xiàn) volatile 讀和 volatile 寫的內(nèi)存語義，編譯器不能對 CAS 與 CAS 前面和后面的任意內(nèi)存操作重排序。

處理器

下面是 sun.misc.Unsafe 類的 compareAndSwapLong() 方法的源代碼：

public final native boolean compareAndSwapLong(Object var1, 
                                               long var2, 
                                               long var4, 
                                               long var6);

下面是對應(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
  }
}

可以看到調(diào)用了“Atomic::cmpxchg”方法：

mp是 os::is_MP() 的返回結(jié)果， os::is_MP() 是一個內(nèi)聯(lián)函數(shù)，用來判斷當(dāng)前系統(tǒng)是否為多處理器。如果當(dāng)前系統(tǒng)是多處理器，該函數(shù)返回1。否則，返回0。 LOCK_IF_MP(mp) 會根據(jù)mp的值來決定是否 為cmpxchg指令添加lock前綴 。如果通過mp判斷當(dāng)前系統(tǒng)是多處理器（即mp值為1），則為cmpxchg指令添加lock前綴。否則，不加lock前綴。（單處理器自身會維護(hù)單處理器內(nèi)的順序一致性，不需要 lock 前綴提供的內(nèi)存屏障效果）。

intel 的手冊對 lock 前綴的說明如下：

• 確保對內(nèi)存的讀 - 改 - 寫操作原子執(zhí)行。在 Pentium 及 Pentium 之前的處理器中，帶有 lock 前綴的指令在執(zhí)行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內(nèi)存。很顯然，這會帶來昂貴的開銷。從 Pentium 4，Intel Xeon 及 P6 處理器開始，intel 在原有總線鎖的基礎(chǔ)上做了一個很有意義的優(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ū)域被完全包含在單個緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會一直被鎖定，其它處理器無法讀 / 寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低 lock 前綴指令的執(zhí)行開銷，但是當(dāng)多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時，仍然會鎖住總線。
• 禁止該指令與之前和之后的讀和寫指令重排序。
• 把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

上面的第 2 點(diǎn)和第 3 點(diǎn)所具有的內(nèi)存屏障效果足以同時實(shí)現(xiàn) volatile 讀和volatile 寫的內(nèi)存語義。

三、CAS存在的問題

1.ABA問題

ABA問題是指在CAS操作的時候，其他線程將變量的值A(chǔ)改成了B，又改回了A，當(dāng)前線程使用期望值A(chǔ)與當(dāng)前變量A進(jìn)行比較的時候發(fā)現(xiàn)A變量值沒有變，于是CAS就將A值進(jìn)行了交換操作。這個時候，其實(shí)該值已經(jīng)被其他線程改變過，這與設(shè)計思想是不符合的。ABA問題的解決思路：每次變量更新的時候，把變量的版本號加1，那么之前的就變成了1A2B3A，從而解決了ABA問題。AtomicStampedReference的compareAndSet:

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair< V > current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

這個方法相對于之前的compareAndSet方法，多了一個stamp的比較，stamp的值由每次更新的時候來維護(hù)的。

2.循環(huán)時間長開銷大

自旋CAS如果長時間不成功，會給CPU帶來非常大的執(zhí)行開銷。CAS的底層實(shí)現(xiàn)，是在一個死循環(huán)內(nèi)不斷的嘗試修改目標(biāo)值，直到修改成功。如果競爭不激烈的情況下，它修改成功的幾率很高，競爭激烈的情況下，修改失敗的幾率就很高，在大量修改失敗的時候，這些原子操作就會進(jìn)行多次的循環(huán)嘗試，因此性能會受到影響。

基于這個原因，jdk1.8新增了一個原子類LongAdder用來解決這個問題。新增LongAdder與原始AtomicLong工作原理對比如下如所示：

這里有個知識點(diǎn)：對于普通類型的long和double變量，JVM允許將64位的讀操作或?qū)懖僮鳎鸪蓛蓚€32位的操作。那么LongAdder的實(shí)現(xiàn)是基于什么思想呢？它的核心其實(shí)是將熱點(diǎn)數(shù)據(jù)分離，比如說，它可以將AtomicLong內(nèi)部核心數(shù)據(jù)value分離成一個數(shù)組，每個線程訪問時，通過hash等算法，定位到其中一個數(shù)字進(jìn)行計數(shù)，而最終的計數(shù)結(jié)果是這個數(shù)組的求和累加，其中熱點(diǎn)數(shù)據(jù)value會被分割成多個單元的cell，每個cell獨(dú)自維護(hù)內(nèi)部的值，當(dāng)前對象的實(shí)際值，由多有的cell累計合成，這樣的話熱點(diǎn)就進(jìn)行了有效的分離，并提高了并行度。這樣一來呢，LongAdder相當(dāng)于是在AtomicLong的基礎(chǔ)上，將單點(diǎn)的更新壓力，分散到各個節(jié)點(diǎn)上；在低并發(fā)的時候，通過對base的直接更新，可以很好的保證和AtomicLong性能基本一致，而在高并發(fā)的時候，則通過分散提高了性能。

LongAdder缺點(diǎn)：在統(tǒng)計的時候，如果有并發(fā)更新，可能會導(dǎo)致統(tǒng)計的數(shù)據(jù)有些誤差。所以如果是序列號生成等需要準(zhǔn)確的數(shù)值，全局唯一的AtomicLong才是正確的選擇。

3.只能保證一個共享變量的原子操作

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

四、CAS在鎖機(jī)制中的應(yīng)用

1.樂觀鎖

樂觀鎖在Java中是通過使用無鎖編程來實(shí)現(xiàn)，最常采用的是CAS算法，Java原子類中的遞增操作就通過CAS自旋實(shí)現(xiàn)的：

public static AtomicLong atomicLong = new AtomicLong();
atomicLong.incrementAndGet();

2.自旋鎖&自適應(yīng)自旋鎖

自旋鎖的實(shí)現(xiàn)原理同樣也是CAS，AtomicInteger中調(diào)用unsafe進(jìn)行自增操作的源碼中的do-while循環(huán)就是一個自旋操作，如果修改數(shù)值失敗則通過循環(huán)來執(zhí)行自旋，直至修改成功：

public final long getAndAddLong(Object var1, long var2, long var4) {
    long var6;
    do {
        var6 = this.getLongVolatile(var1, var2);
    } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));


    return var6;
}

自適應(yīng)意味著自旋的時間（次數(shù)）不再固定，而是由前一次在同一個鎖上的自旋時間及鎖的擁有者的狀態(tài)來決定。如果在同一個鎖對象上，自旋等待剛剛成功獲得過鎖，并且持有鎖的線程正在運(yùn)行中，那么虛擬機(jī)就會認(rèn)為這次自旋也是很有可能再次成功，進(jìn)而它將允許自旋等待持續(xù)相對更長的時間。如果對于某個鎖，自旋很少成功獲得過，那在以后嘗試獲取這個鎖時將可能省略掉自旋過程，直接阻塞線程，避免浪費(fèi)處理器資源。

3.無鎖

無鎖沒有對資源進(jìn)行鎖定，所有的線程都能訪問并修改同一個資源，但同時只有一個線程能修改成功。無鎖的特點(diǎn)就是修改操作在循環(huán)內(nèi)進(jìn)行，線程會不斷的嘗試修改共享資源。如果沒有沖突就修改成功并退出，否則就會繼續(xù)循環(huán)嘗試。如果有多個線程修改同一個值，必定會有一個線程能修改成功，而其他修改失敗的線程會不斷重試直到修改成功。CAS原理及應(yīng)用即是無鎖的實(shí)現(xiàn)

4.輕量級鎖

是指當(dāng)鎖是偏向鎖的時候，被另外的線程所訪問，偏向鎖就會升級為輕量級鎖，其他線程會通過自旋的形式嘗試獲取鎖，不會阻塞，從而提高性能。

這里說明一下，輕量級鎖和偏向鎖都是JDK1.6對synchronized的優(yōu)化，優(yōu)化后存在四種鎖狀態(tài)。關(guān)于java中的鎖我們下次再詳細(xì)介紹，下面給出這四種鎖狀態(tài)：

5.ReentrantLock

ReentrantLock主要利用CAS+CLH隊列來實(shí)現(xiàn)，基本實(shí)現(xiàn)可以概括為：先通過CAS嘗試獲取鎖。如果此時已經(jīng)有線程占據(jù)了鎖，那就加入CLH隊列并且被掛起。當(dāng)鎖被釋放之后，排在CLH隊列隊首的線程會被喚醒，然后CAS再次嘗試獲取鎖。在這個時候，如果：

• 非公平鎖：如果同時還有另一個線程進(jìn)來嘗試獲取，那么有可能會讓這個線程搶先獲取；
• 公平鎖：如果同時還有另一個線程進(jìn)來嘗試獲取，當(dāng)它發(fā)現(xiàn)自己不是在隊首的話，就會排到隊尾，由隊首的線程獲取到鎖。

CLH隊列：帶頭結(jié)點(diǎn)的雙向非循環(huán)鏈表。結(jié)構(gòu)圖如下：

結(jié)語

cas原理先介紹這些，關(guān)于java線程安全的三個特性：原子性、可見性、有序性以及cas中涉及到的java內(nèi)存模型以及cpu多級緩存，后面會詳細(xì)說明。