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

1. 為什么使用CAS代替synchronized

• synchronized加鎖，同一時間段只允許一個線程訪問，能夠保證一致性但是并發(fā)性下降。而是用CAS算法使用do-while不斷判斷而沒有加鎖（實際是一個自旋鎖），保證一致性和并發(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 {
        // 獲取對象var1，偏移量為var2地址上的值，并賦值給var5
        var5 = this.getIntVolatile(var1, var2);
        /**
         * 再次獲取對象var1，偏移量var2地址上的值，并和var5進(jìn)行比較：
         * - 如果不相等，返回false，繼續(xù)執(zhí)行do-while循環(huán)
         * - 如果相等，將返回的var5數(shù)值和var4相加并返回
         */
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    // 最終總是返回對象var1，偏移量為var2地址上的值，即上述所說的V。
    return var5;
}

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

2. CAS算法的缺點

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

3. ABA問題解決方案

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

• AtomicStampedReference解決方案：每次修改都會讓stamp值加1，類似于版本控制號

/**
 * 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 + ", 實際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算法實際使用

在Spring容器刷新方法 refresh() 方法中：obtainFreshBeanFactory()->refreshBeanFactory()【GenericApplicationContext實現(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());
}