CAS算法簡介

CAS（Compare And Swap）算法是一條原子的CPU指令（Atomic::cmpxchg(x, addr, e) == e;）抽高，需要三個(gè)操作數(shù)：變量的內(nèi)存地址（或者是偏移量valueOffset） V 截汪，預(yù)期值 A 和更新值 B颁独，CAS指令執(zhí)行時(shí)：當(dāng)且僅當(dāng)對(duì)象偏移量V上的值和預(yù)期值A(chǔ)相等時(shí)，才會(huì)用更新值B更新V內(nèi)存上的值，否則不執(zhí)行更新。但是無論是否更新了V內(nèi)存上的值炉抒，最終都會(huì)返回V內(nèi)存上的舊值。

1. 為什么使用CAS代替synchronized

synchronized加鎖稚叹，同一時(shí)間段只允許一個(gè)線程訪問焰薄，能夠保證一致性但是并發(fā)性下降拿诸。而是用CAS算法使用do-while不斷判斷而沒有加鎖（實(shí)際是一個(gè)自旋鎖），保證一致性和并發(fā)性塞茅。
原子性保證：CAS算法依賴于rt.jar包下的sun.misc.Unsafe類亩码，該類中的所有方法都是native修飾的，直接調(diào)用操作系統(tǒng)底層資源執(zhí)行相應(yīng)的任務(wù)野瘦。

// unsafe.class
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        // 獲取對(duì)象var1描沟，偏移量為var2地址上的值，并賦值給var5
        var5 = this.getIntVolatile(var1, var2);
        /**
         * 再次獲取對(duì)象var1鞭光，偏移量var2地址上的值吏廉，并和var5進(jìn)行比較：
         * - 如果不相等，返回false惰许，繼續(xù)執(zhí)行do-while循環(huán)
         * - 如果相等席覆，將返回的var5數(shù)值和var4相加并返回
         */
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    // 最終總是返回對(duì)象var1，偏移量為var2地址上的值汹买，即上述所說的V佩伤。
    return var5;
}

內(nèi)存可見性和禁止指令重排序的保證：AtomicXxx類中的成員變量value是由volatile修飾的：private volatile int value;上一小節(jié)中已經(jīng)介紹過。

2. CAS算法的缺點(diǎn)

do-while循環(huán)晦毙，如果CAS失敗就會(huì)一直進(jìn)行嘗試生巡，即一直在自旋，導(dǎo)致CPU開銷见妒，這也是自旋鎖的缺點(diǎn)孤荣；
只能保證一個(gè)共享變量的原子操作，如果操作多個(gè)共享變量則需要加鎖實(shí)現(xiàn)须揣；
ABA問題：如果一個(gè)線程在初次讀取時(shí)的值為A垃环，并且在準(zhǔn)備賦值的時(shí)候檢查該值仍然是A，但是可能在這兩次操作之間返敬，有另外一個(gè)線程現(xiàn)將變量的值改成了B，然后又將該值改回為A寥院，那么CAS會(huì)誤認(rèn)為該變量沒有變化過劲赠。

3. ABA問題解決方案

可以使用AtomicStampedReference或者AtomicMarkableReference來解決CAS的ABA問題，思路類似于SVN版本號(hào)秸谢，SpringBoot熱部署中trigger.txt：

AtomicStampedReference解決方案：每次修改都會(huì)讓stamp值加1凛澎，類似于版本控制號(hào)

/**
 * ABA問題解決方案，AtomicStampedReference
 *
 * @author sherman
 */
public class AtomicStampedReferenceABA {
    private static AtomicReference<Integer> ar = new AtomicReference<>(0);
    private static AtomicStampedReference<Integer> asr =
            new AtomicStampedReference<>(0, 1);

    public static void main(String[] args) {
        System.out.println("=============演示ABA問題（AtomicReference）===========");
        new Thread(() -> {
            ar.compareAndSet(0, 1);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            ar.compareAndSet(1, 0);
            System.out.println(Thread.currentThread().getName() + "進(jìn)行了一次ABA操作");
        }, "子線程").start();

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        boolean res = ar.compareAndSet(0, 100);
        if (res) {
            System.out.println("main成功修改, 未察覺到子線程進(jìn)行了ABA操作");
        }

        System.out.println("=============解決ABA問題（AtomicStampReference）===========");
        new Thread(() -> {
            int curStamp = asr.getStamp();
            System.out.println("當(dāng)前stamp: " + curStamp);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            asr.compareAndSet(0, 1, curStamp, curStamp + 1);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            asr.compareAndSet(1, 0, asr.getStamp(), asr.getStamp() + 1);
        }, "t1").start();

        new Thread(() -> {
            int curStamp = asr.getStamp();
            System.out.println("當(dāng)前stamp: " + curStamp);
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean result = asr.compareAndSet(0, 100, curStamp, curStamp + 1);
            if (!result) {
                System.out.println("修改失敗! 預(yù)期stamp: " + curStamp + ", 實(shí)際stamp: " + asr.getStamp());
            }
        }, "t2").start();
    }
}

AtomicMarkableReference：如果不關(guān)心引用變量中途被修改了多少次估蹄，而只關(guān)心是否被修改過塑煎，可以使用AtomicMarkableReference：

/**
 * ABA問題解決方案，AtomicMarkableReference
 *
 * @author  sherman
 */
public class AtomicMarkableReferenceABA {
    private static AtomicMarkableReference<Integer> amr = new AtomicMarkableReference<>(0, false);

    public static void main(String[] args) {
        new Thread(() -> {
            amr.compareAndSet(0, 1, false, true);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            amr.compareAndSet(1, 0, true, true);
            System.out.println("子線程進(jìn)行了ABA修改!");
        }, "子線程").start();

        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        boolean res = amr.compareAndSet(0, 100, false, true);
        if (!res) {
            System.out.println("修改失敗! 當(dāng)前isMarked: " + amr.isMarked());
        }
    }
}

3.3 補(bǔ)充：CAS算法實(shí)際使用

在Spring容器刷新方法 refresh() 方法中：obtainFreshBeanFactory()->refreshBeanFactory()【GenericApplicationContext實(shí)現(xiàn)類】:

@Override
protected final void refreshBeanFactory() throws IllegalStateException {
    // cas算法
    // private final AtomicBoolean refreshed = new AtomicBoolean();
    if (!this.refreshed.compareAndSet(false, true)) {
        throw new IllegalStateException(
                "GenericApplicationContext does not support multiple refresh attempts: just call 'refresh' once");
    }
    this.beanFactory.setSerializationId(getId());
}