無(wú)鎖的思想

眾所周知，Java中對(duì)并發(fā)控制的最常見方法就是鎖，鎖能保證同一時(shí)刻只能有一個(gè)線程訪問臨界區(qū)的資源，從而實(shí)現(xiàn)線程安全。然而，鎖雖然有效，但采用的是一種悲觀的策略。它假設(shè)每一次對(duì)臨界區(qū)資源的訪問都會(huì)發(fā)生沖突，當(dāng)有一個(gè)線程訪問資源，其他線程就必須等待，所以鎖是會(huì)阻塞線程執(zhí)行的。

當(dāng)然，凡事都有兩面，有悲觀就會(huì)有樂觀。而無(wú)鎖就是一種樂觀的策略，它假設(shè)線程對(duì)資源的訪問是沒有沖突的，同時(shí)所有的線程執(zhí)行都不需要等待，可以持續(xù)執(zhí)行。如果遇到?jīng)_突的話，就使用一種叫做CAS (比較交換) 的技術(shù)來鑒別線程沖突，如果檢測(cè)到?jīng)_突發(fā)生，就重試當(dāng)前操作到?jīng)]有沖突為止。

CAS概述

CAS的全稱是 Compare-and-Swap，也就是比較并交換，是并發(fā)編程中一種常用的算法。它包含了三個(gè)參數(shù)：V，A，B。

其中，V表示要讀寫的內(nèi)存位置，A表示舊的預(yù)期值，B表示新值

CAS指令執(zhí)行時(shí)，當(dāng)且僅當(dāng)V的值等于預(yù)期值A(chǔ)時(shí)，才會(huì)將V的值設(shè)為B，如果V和A不同，說明可能是其他線程做了更新，那么當(dāng)前線程就什么都不做，最后，CAS返回的是V的真實(shí)值。

而在多線程的情況下，當(dāng)多個(gè)線程同時(shí)使用CAS操作一個(gè)變量時(shí)，只有一個(gè)會(huì)成功并更新值，其余線程均會(huì)失敗，但失敗的線程不會(huì)被掛起，而是不斷的再次循環(huán)重試。正是基于這樣的原理，CAS即時(shí)沒有使用鎖，也能發(fā)現(xiàn)其他線程對(duì)當(dāng)前線程的干擾，從而進(jìn)行及時(shí)的處理。

CAS的應(yīng)用類

Java中提供了一系列應(yīng)用CAS操作的類，這些類位于java.util.concurrent.atomic包下，其中最常用的就是AtomicInteger，該類可以看做是實(shí)現(xiàn)了CAS操作的Integer，所以，下面我們就通過學(xué)習(xí)該類的案例來一窺全貌CAS的妙用。

學(xué)習(xí)AtomicInteger之前，我們先來看一段代碼實(shí)例：

public class AtomicDemo {

    public static int NUMBER = 0;

    public static void increase() {
        NUMBER++;
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicDemo test = new AtomicDemo();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                for (int j = 0; j < 1000; j++)
                    test.increase();
            }).start();
        }
        Thread.sleep(200);
        System.out.println(test.NUMBER);
    }
}

在main函數(shù)中開啟了10個(gè)線程，執(zhí)行后會(huì)輪流調(diào)用 increase()，當(dāng)然我們知道，運(yùn)行后輸出的結(jié)果肯定不是我們期望的值，因?yàn)闆]有做線程安全的處理，所以10個(gè)線程流量操作臨界區(qū)的資源NUMBER就會(huì)出錯(cuò)。

解決辦法并不難，用我們之前學(xué)過的鎖，例如synchronized修飾代碼塊，程序就會(huì)正常輸出10000。當(dāng)然，用鎖解決并不是我們想要的方式，因?yàn)殒i會(huì)阻塞線程，影響程序的性能，這時(shí)候，AtomicInteger就可以派上用場(chǎng)了。

將上面的程序改造一下，變成下面這樣：

public static AtomicInteger NUMBER = new AtomicInteger(0);

public static void increase() {
    NUMBER.getAndIncrement();
}

public static void main(String[] args) throws InterruptedException {
    AtomicDemo test = new AtomicDemo();
    for (int i = 0; i < 10; i++) {
        new Thread(() -> {
            for (int j = 0; j < 1000; j++)
                test.increase();
        }).start();
    }
    Thread.sleep(200);
    System.out.println(test.NUMBER);
}

運(yùn)行main方法，程序輸出的就是我們想要的值，也就是10000。

上面的代碼中，increase方法里調(diào)用了NUMBER.getAndIncrement() ，這是AtomicInteger的自增方法，會(huì)對(duì)當(dāng)前的值加1，并且返回舊值，點(diǎn)進(jìn)方法的源碼，它調(diào)用的是unsafe.getAndAddInt()方法：

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

getAndAddInt的作用是對(duì)當(dāng)前值加1，并返回舊值。

unsafe是Unsafe類的一個(gè)變量，通過Unsafe.getUnsafe()來獲取

private static final Unsafe unsafe = Unsafe.getUnsafe();

Unsafe類是一個(gè)比較特殊的類，它是一個(gè)JDK內(nèi)部使用的專屬類，用一般的編輯器無(wú)法直接查看源碼，只能看到反編譯后的class文件。

這里要擴(kuò)展一個(gè)知識(shí)點(diǎn)，就是Java本身無(wú)法訪問操作系統(tǒng)，需要使用native方法，而Unsafe類中的方法就包含了大量的native方法，提高了Java對(duì)系統(tǒng)底層的原子操作能力。例如我們代碼中使用到的getAndAddInt()底層就是調(diào)用一個(gè)native方法，用idea點(diǎn)擊方法，得到下面反編譯后的代碼：

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

compareAndSwapInt的作用是比較并交換整數(shù)值，如果指定的字段的值等于期望值，也就是CAS中的 'A' (預(yù)期值)，那么就會(huì)把它設(shè)置為新值 (CAS中的 'B')，不難想象，該方法內(nèi)部的實(shí)現(xiàn)必然是依靠原子操作完成的。除此之外，Unsafe類中還提供了其他的原子操作的方法，例如上面源碼中的getIntVolatile就是使用volatile語(yǔ)義獲得給定對(duì)象的值，這些方法通過底層的原子操作高效的提升了應(yīng)用層面的性能。

CAS的缺點(diǎn)

雖然CAS的性能比起鎖要強(qiáng)大很多，但它也存在一些缺點(diǎn)，例如：

1、循環(huán)的時(shí)間開銷大

在getAndAddInt的方法中，我們可以看到，只是簡(jiǎn)單的設(shè)置一個(gè)值卻調(diào)用了循環(huán)，如果CAS失敗，會(huì)一直進(jìn)行嘗試。如果CAS長(zhǎng)時(shí)間不成功，那么循環(huán)就會(huì)不停的跑，無(wú)疑會(huì)給系統(tǒng)造成很大的開銷。

2、ABA問題

前面說過，CAS判斷變量操作成功的條件是V的值和A是一致的，這個(gè)邏輯有個(gè)小小的缺陷，就是如果V的值一開始為A，在準(zhǔn)備修改為新值前的期間曾經(jīng)被改成了B，后來又被改回為A，經(jīng)過兩次的線程修改對(duì)象的值還是舊值，那么CAS操作就會(huì)誤任務(wù)該變量從來沒被修改過。這就是CAS中的“ABA”問題。

當(dāng)然，"ABA"問題也有解決方案，Java并發(fā)包中提供了一個(gè)帶有時(shí)間戳的對(duì)象引用 AtomicStampedReference，其內(nèi)部不僅維護(hù)了一個(gè)對(duì)象值，還維護(hù)了一個(gè)時(shí)間戳，當(dāng)AtomicStampedReference對(duì)應(yīng)的數(shù)值被修改時(shí)，除了更新數(shù)據(jù)本身，還需要更新時(shí)間戳，只有對(duì)象值和時(shí)間戳都滿足期望值，才能修改成功。這是AtomicStampedReference的幾個(gè)有關(guān)時(shí)間戳信息的方法：

//比較設(shè)置 參數(shù)依次為：期望值 寫入新值 期望時(shí)間戳 新時(shí)間戳
public boolean compareAndSet(V expectedReference, V newReference,
                             int expectedStamp, int newStamp)
//獲得當(dāng)前時(shí)間戳
public int getStamp()
//設(shè)置當(dāng)前對(duì)象引用和時(shí)間戳
public void set(V newReference, int newStamp)