概述

上一篇文章Java鎖分類(lèi)中，有提到一種分類(lèi)的思想：樂(lè)觀鎖和悲觀鎖。悲觀鎖，總認(rèn)為每次訪問(wèn)共享資源的時(shí)候，都有可能發(fā)生資源競(jìng)爭(zhēng)，所以在線程獲取到共享資源后，需要加鎖，其余線程無(wú)法再對(duì)共享資源進(jìn)行操作。而樂(lè)觀鎖，總認(rèn)為每次訪問(wèn)共享資源時(shí)，都不會(huì)發(fā)生資源競(jìng)爭(zhēng)，線程可以不停的執(zhí)行，無(wú)需加鎖，無(wú)需等待；當(dāng)發(fā)生沖突的時(shí)候，會(huì)采用CAS來(lái)保證線程執(zhí)行的安全性。

CAS全稱(chēng)Compare And Swap，即比較和交換，該技術(shù)是實(shí)現(xiàn)用于多線程中原子指令。其算法核心思想如下：CAS（V,A,B），其中V代表內(nèi)存中的值，A為預(yù)期值，B為改變后的新值。

CAS原理

我們知道在多線程環(huán)境下，有些共享資源存儲(chǔ)在主內(nèi)存中，每個(gè)線程對(duì)共享資源都有自己的一份線程副本，當(dāng)“線程1”在線程本地副本中經(jīng)過(guò)一系列操作后，將比較值A(chǔ)1修改為新值B1后，需要更新主內(nèi)存中的V值。這時(shí)會(huì)拿V值與A1值進(jìn)行比較，如果相等，則說(shuō)明V值在"線程1"執(zhí)行期間沒(méi)有被修改，那么將主存中的V值修改為B1。

假如“線程2”與“線程1”同時(shí)拿到共想資源的值，線程2執(zhí)行操作較慢，在線程2本地內(nèi)存副本中經(jīng)過(guò)操作，將A2值修改為B2值，然后去更新主存中的值，這時(shí)候發(fā)現(xiàn)V與預(yù)期值A(chǔ)2不想等，那么說(shuō)明V值在“線程2”執(zhí)行期間被修改。那么“線程2”可以選擇放棄執(zhí)行，或者會(huì)重新讀取新的V值到本地線程副本中，重新執(zhí)行操作，再重新判斷是否更新V值。以下圖為例：

CAS原理.png

基于這樣的原理，CAS操作即使沒(méi)有加鎖，一樣能夠知道其他線程對(duì)共享資源是否產(chǎn)生影響，并做出相應(yīng)的措施。同時(shí)從這點(diǎn)也可以看出，由于無(wú)鎖操作中沒(méi)有鎖的存在，所以不可能出現(xiàn)死鎖的情況。

說(shuō)到這里，我們可能會(huì)產(chǎn)生這樣的疑問(wèn)：會(huì)不會(huì)存在“線程1”的A1值與主存V比較時(shí)相等，但是在將V更新為B1的時(shí)候，V值卻被其余線程修改了呢？答案是否定的，因?yàn)镃AS是一種系統(tǒng)原語(yǔ)，原語(yǔ)屬于操作系統(tǒng)用語(yǔ)范疇，是有若干條指令組成的，用語(yǔ)完成某個(gè)功能的一個(gè)過(guò)程，并且系統(tǒng)原語(yǔ)的執(zhí)行必須是連續(xù)的，在執(zhí)行過(guò)程中不允許被中斷，也就是說(shuō)CAS是CPU的原子性操作，不會(huì)造成數(shù)據(jù)不一致問(wèn)題。

UnSafe類(lèi)

Java中CAS的實(shí)現(xiàn)依賴(lài)于Unsafe類(lèi)的方法，Unsafe類(lèi)的內(nèi)部方法可以像C語(yǔ)言一樣直接操作系統(tǒng)內(nèi)存，其所有方法都是native關(guān)鍵字修飾，單從名稱(chēng)看，該類(lèi)就是不安全的，畢竟Unsafe類(lèi)擁有像C一樣操作內(nèi)存的方法，所以我們不應(yīng)該優(yōu)先使用Unsafe類(lèi)，Java官方也不建議使用該類(lèi)。

下面列舉一下CAS相關(guān)的Unsafe方法：

    public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

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

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

上述三個(gè)方法入?yún)⒒鞠嗤谝粋€(gè)參數(shù)var1為給定的Object對(duì)象，第二個(gè)參數(shù)var2為對(duì)象內(nèi)存的偏移量，通過(guò)該參數(shù)可以快速定位到字段并設(shè)置或獲取字段的值。第三個(gè)參數(shù)var4為預(yù)期值，最后一個(gè)參數(shù)為要設(shè)置的值，這三個(gè)方法都通過(guò)cas原子指令執(zhí)行操作。

Atomic系列中CAS的使用

在java.util.concurrent.atomic包下，有一系列的atomic類(lèi)，提供了很多基于CAS實(shí)現(xiàn)的原子操作類(lèi)，用法方便，性能高效。其中原子操作更新基本類(lèi)型的主要包括以下三類(lèi)：

• AtomicInteger
• AtomicBoolean
• AtomicLong

我們以AtomicInteger為例，來(lái)分析以下源碼

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    //初始化指針類(lèi)Unsafe
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    //變量“value”在AtomicInteger實(shí)例對(duì)象內(nèi)的內(nèi)存偏移量
    private static final long valueOffset;

    static {
        try {
            //通過(guò)unsafe.objectFiledOffset獲取到value的內(nèi)存偏移量，通過(guò)偏移量，可以獲取到value進(jìn)行賦值或取值操作
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    
    private volatile int value;
   
    public AtomicInteger(int initialValue) {
        value = initialValue;
    }

    public AtomicInteger() {
    }
    //獲取最新的value值
    public final int get() {
        return value;
    }
    //設(shè)置當(dāng)前值，具備volatile效果，用final修飾是為了進(jìn)一步保證線程安全
    public final void set(int newValue) {
        value = newValue;
    }
    //最終會(huì)設(shè)置為newValue，但是有一定延遲，使用該方法后可能導(dǎo)致其他線程在之后的一小段時(shí)間內(nèi)獲取到舊的值，類(lèi)似于延遲加載
    public final void lazySet(int newValue) {
        unsafe.putOrderedInt(this, valueOffset, newValue);
    }
    //設(shè)置新值獲取舊值，底層使用CAS操作unsafe.compareAndSwapInt
    public final int getAndSet(int newValue) {
        return unsafe.getAndSetInt(this, valueOffset, newValue);
    }
    //如果當(dāng)前value值等于expect預(yù)期值，那么將value更新為update值
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    //當(dāng)前值加1，返回舊值
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
    //當(dāng)前值減1，返回舊值
    public final int getAndDecrement() {
        return unsafe.getAndAddInt(this, valueOffset, -1);
    }
    //當(dāng)前值加delta,返回舊值
    public final int getAndAdd(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }
    ......

}

分析源碼可以看出，AtomicInteger所有方法，底層都會(huì)調(diào)用Unsafe的相關(guān)方法，而所有關(guān)于值的自增和自減都間接調(diào)用了unsafe.getAndAddInt方法，該方法源碼如下：

    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;
    }

可以看到其通過(guò)while循環(huán)，來(lái)調(diào)用底層CAS方法compareAndSwapInt，直到值修改完成，然后返回舊值。

CAS的ABA問(wèn)題

我們回到之前的場(chǎng)景中，假設(shè)線程1將主存中的V=0值修改為2，然后在線程2修改V值之前，有一個(gè)線程3拿到本地線程副本V值為2，然后通過(guò)運(yùn)算將主存中的V值又修改為0了。那么在線程2再去修改的時(shí)候，它是沒(méi)法感知主存中的V值是被修改過(guò)的，這就是經(jīng)典的ABA問(wèn)題?？赡苡械娜藭?huì)有疑問(wèn)說(shuō)，這樣的操作邏輯上是沒(méi)有問(wèn)題的啊，最終得到的結(jié)果是線程2成功修改主存的值，可是如果我們應(yīng)用到實(shí)際場(chǎng)景中，就會(huì)發(fā)現(xiàn)問(wèn)題所在了。

例如在銀行場(chǎng)景中，某公司賬戶(hù)有100萬(wàn)存款，某職員通過(guò)某種操作，挪用了公款100萬(wàn)去炒股，在公司查賬之前，又將100萬(wàn)還了回來(lái)，如果這種ABA問(wèn)題不得已解決，那么公司查賬也就無(wú)法感知到該職員有挪用過(guò)公款了，而這種情況在現(xiàn)實(shí)生活中是不被允許的。

可以通過(guò)下列圖示來(lái)理解ABA問(wèn)題

CAS的ABA問(wèn)題.png

Java也提供了兩個(gè)類(lèi)來(lái)解決ABA問(wèn)題，分別是：AtomicStampedReference、AtomicMarkableReference。他們解決的方法類(lèi)似，都是給值加上標(biāo)記，只是一個(gè)是時(shí)間戳，一個(gè)是boolean值。

AtomicStampedReference

public class AtomicStampedReference<V> {
    
    //保存實(shí)例對(duì)象信息的內(nèi)部類(lèi)
    private static class Pair<T> {
        //實(shí)例對(duì)象
        final T reference;
        //時(shí)間戳
        final int stamp;
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
            return new Pair<T>(reference, stamp);
        }
    }

    private volatile Pair<V> pair;
    
    //expectedReference為預(yù)期值，newReference為新值，expectedStamp為預(yù)期時(shí)間戳，newStamp為新的時(shí)間戳
    //只有當(dāng)預(yù)期值與當(dāng)前值相等，并且預(yù)期時(shí)間戳與當(dāng)前的時(shí)間戳相等時(shí)才會(huì)修改值
    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)));
    }

    .......
}

通過(guò)分析源碼，我們可以看到，AtomicStampedReference通過(guò)Pair私有內(nèi)部類(lèi)存儲(chǔ)數(shù)據(jù)和時(shí)間戳, 并構(gòu)造volatile修飾的私有實(shí)例，接著看AtomicStampedReference類(lèi)的compareAndSet（）方法的實(shí)現(xiàn)：同時(shí)對(duì)當(dāng)前數(shù)據(jù)和當(dāng)前時(shí)間進(jìn)行比較，只有兩者都相等是才會(huì)執(zhí)行casPair()方法，單從該方法的名稱(chēng)就可知是一個(gè)CAS方法，最終調(diào)用的還是Unsafe類(lèi)中的compareAndSwapObject方法。到這我們就很清晰AtomicStampedReference的內(nèi)部實(shí)現(xiàn)思想了，只有兩者都符合預(yù)期才會(huì)調(diào)用Unsafe的compareAndSwapObject方法執(zhí)行數(shù)值和時(shí)間戳替換，也就避免了ABA的問(wèn)題。

AtomicMarkableReference

該類(lèi)的解決方案與AtomicStampedReference類(lèi)似，只是AtomicMarkableReference維護(hù)的是boolean標(biāo)識(shí)，也就是維護(hù)true和false的切換，但是也很容易想到因?yàn)橹挥袃煞N狀態(tài)的切換，所以也沒(méi)法完全避免ABA問(wèn)題的發(fā)生。下面簡(jiǎn)單看一下相關(guān)源碼

public class AtomicMarkableReference<V> {

    private static class Pair<T> {
        final T reference;
        final boolean mark;
        private Pair(T reference, boolean mark) {
            this.reference = reference;
            this.mark = mark;
        }
        static <T> Pair<T> of(T reference, boolean mark) {
            return new Pair<T>(reference, mark);
        }
    }

    private volatile Pair<V> pair;

    public boolean compareAndSet(V       expectedReference,
                                     V       newReference,
                                     boolean expectedMark,
                                     boolean newMark) {
            Pair<V> current = pair;
            return
                expectedReference == current.reference &&
                expectedMark == current.mark &&
                ((newReference == current.reference &&
                  newMark == current.mark) ||
                 casPair(current, Pair.of(newReference, newMark)));
        }

        ......
    }

注：本文部分參考一下博文
https://blog.csdn.net/qq_22771739/article/details/82824353
https://www.cnblogs.com/javalyy/p/8882172.html
http://www.itdecent.cn/p/ae25eb3cfb5d