前言

CAS（compare and swap, 比較并交換）红选，是原子操作的一種澜公，可用于在多線程編程中實現(xiàn)不被打斷的數(shù)據(jù)交換操作，從而避免多線程同時改寫某一數(shù)據(jù)時由于執(zhí)行順序不確定性以及中斷的不可預(yù)知性產(chǎn)生的數(shù)據(jù)不一致問題喇肋。
簡單來說坟乾，CAS可以保證多線程對數(shù)據(jù)寫操作時數(shù)據(jù)的一致性迹辐。
CAS的思想：三個參數(shù)，一個當(dāng)前內(nèi)存值V甚侣、舊的預(yù)期值A(chǔ)明吩、即將更新的值B，當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時殷费，將內(nèi)存值修改為B并返回true印荔，否則什么都不做，并返回false宗兼。

數(shù)據(jù)不一致問題

一個n++的問題

public class Case {

    public volatile int n;

    public void add() {
        n++;
    }
}

通過javap -verbose Case查看add方法的字節(jié)碼指令

public void add();
    flags: ACC_PUBLIC
    Code:
      stack=3, locals=1, args_size=1
         0: aload_0       
         1: dup           
         2: getfield      #2                  // Field n:I
         5: iconst_1      
         6: iadd          
         7: putfield      #2                  // Field n:I
        10: return

可以看到n++的操作分為以下三步

1. getfield獲得n的值
2. idd進行加1操作
3. putfield把累加后的值寫回給n
   變量n通過volatile修飾躏鱼，可保證其在線程之間的可見性，但不能保證該3個指令的原子執(zhí)行殷绍。例如：線程A、B同時操作n++鹊漠，n應(yīng)該等于4主到，但結(jié)果為3。
   
   n++數(shù)據(jù)不一致.png

解決辦法

1. 在add上添加synchronized修飾解決躯概。但性能較差
2. 將n的類型由int改為AtomicInterger原子變量

原子變量的實現(xiàn)

原子變量是如何保證數(shù)據(jù)的一致性登钥？
答案：CAS
以AtomicInterger為例，

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            // 變量偏移地址
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    public final int get() {
        return value;
    }

1. Unsafe娶靡，是JDK中的一個內(nèi)部類牧牢，由于Java方法無法直接訪問底層系統(tǒng)，需要通過本地（native）方法來訪問姿锭，Unsafe相當(dāng)于一個后門塔鳍，基于該類可以直接操作特定內(nèi)存的數(shù)據(jù)。
2. 變量valueOffset呻此，表示該變量值在內(nèi)存中的偏移地址轮纫，因為Unsafe就是根據(jù)內(nèi)存偏移地址獲取數(shù)據(jù)的。
3. 變量value用volatile修飾焚鲜，保證了多線程之間的內(nèi)存可見性掌唾。

看看AtomicInteger如何實現(xiàn)并發(fā)下的累加操作：

// delta:增加的值
public final int getAndAdd(int delta) {    
    return unsafe.getAndAddInt(this, valueOffset, delta);
}

調(diào)用unsafe.getAndAddInt方法

// unsafe.getAndAddInt
// var1：原子變量對象
// var2：變量值的偏移地址
// var4：增加的值
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        // 根據(jù)偏移地址var2，從對象var1中獲得變量值
        var5 = this.getIntVolatile(var1, var2);
       // 比較上一步獲得的變量值var5與當(dāng)前內(nèi)存中的變量值
       // 若相同忿磅，則修改內(nèi)存值var5+var4糯彬，否則繼續(xù)循環(huán)
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}

假設(shè)線程A和線程B同時執(zhí)行g(shù)etAndAdd操作（分別跑在不同CPU上）：

1. AtomicInteger里面的value原始值為3，即主內(nèi)存中AtomicInteger的value為3葱她，根據(jù)Java內(nèi)存模型撩扒，線程A和線程B各自持有一份value的副本，值為3览效。
2. 線程A通過getIntVolatile(var1, var2)拿到value值3却舀，這時線程A被掛起虫几。
3. 線程B也通過getIntVolatile(var1, var2)方法獲取到value值3，運氣好挽拔，線程B沒有被掛起辆脸，并執(zhí)行compareAndSwapInt方法比較內(nèi)存值也為3，成功修改內(nèi)存值為2螃诅。
4. 這時線程A恢復(fù)啡氢，執(zhí)行compareAndSwapInt方法比較，發(fā)現(xiàn)自己手里的值(3)和內(nèi)存的值(2)不一致术裸，說明該值已經(jīng)被其它線程提前修改過了倘是，那只能重新來一遍了。
5. 重新獲取value值袭艺，因為變量value被volatile修飾搀崭，所以其它線程對它的修改，線程A總是能夠看到猾编，線程A繼續(xù)執(zhí)行compareAndSwapInt進行比較替換瘤睹，直到成功。

整個過程中答倡，利用CAS保證了對于value的修改的并發(fā)安全

Unsafe類的CAS實現(xiàn)

繼續(xù)深入看看Unsafe類中的compareAndSwapInt方法實現(xiàn)轰传。

public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);

Unsafe類中的compareAndSwapInt，是一個本地方法瘪撇，該方法的實現(xiàn)位于unsafe.cpp中

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  // 1. 獲得變量value在內(nèi)存中的地址
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  // 2. 通過Atomic::cmpxchg實現(xiàn)比較替換
  //    x是即將更新的值获茬，e為原內(nèi)存的值
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

下面再來看看操作系統(tǒng)中Atomic::cmpxchg的實現(xiàn)
下面重點了解下LOCK_IF_MP和LOCK前綴就行了，其他我也不懂

• Linux的x86實現(xiàn)：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  int mp = os::is_MP(); //判斷是否是多處理器
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

• Windows的x86實現(xiàn)：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
    int mp = os::isMP(); //判斷是否是多處理器
    _asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
        LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
    }
}

// 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:

LOCK_IF_MP根據(jù)當(dāng)前系統(tǒng)是否為多核處理器決定是否為cmpxchg指令添加lock前綴倔既。

1. 如果是多處理器恕曲，為cmpxchg指令添加lock前綴。
2. 反之叉存，就省略lock前綴码俩。（單處理器會不需要lock前綴提供的內(nèi)存屏障效果）

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

1. 確保后續(xù)指令執(zhí)行的原子性。
   在Pentium及之前的處理器中歼捏，帶有l(wèi)ock前綴的指令在執(zhí)行期間會鎖住總線稿存，使得其它處理器暫時無法通過總線訪問內(nèi)存，很顯然瞳秽，這個開銷很大瓣履。在新的處理器中，Intel使用緩存鎖定來保證指令執(zhí)行的原子性练俐，緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷袖迎。
2. 禁止該指令與前面和后面的讀寫指令重排序。
3. 把寫緩沖區(qū)的所有數(shù)據(jù)刷新到內(nèi)存中。

上面的第2點和第3點所具有的內(nèi)存屏障效果燕锥，保證了CAS同時具有volatile讀和volatile寫的內(nèi)存語義辜贵。

CAS的缺點

CAS存在三大問題：ABA問題，循環(huán)時間長開銷大和只能保證一個共享變量的原子操作归形。其中ABA問題作為第三部分重點說明下托慨。

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

自旋CAS如果長時間不成功，會給CPU帶來非常大的執(zhí)行開銷暇榴。如果JVM能支持處理器提供的pause指令那么效率會有一定的提升厚棵，pause指令有兩個作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會消耗過多的執(zhí)行資源蔼紧，延遲的時間取決于具體實現(xiàn)的版本婆硬，在一些處理器上延遲時間是零。第二它可以避免在退出循環(huán)的時候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush）奸例，從而提高CPU的執(zhí)行效率彬犯。

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

當(dāng)對一個共享變量執(zhí)行操作時，可以使用自旋CAS的方式來保證原子操作哩至，但是對多個共享變量操作時躏嚎，自旋CAS就無法保證操作的原子性，這個時候就可以用鎖菩貌，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作重荠。比如有兩個共享變量i＝2,j=a箭阶，合并一下ij=2a，然后用CAS來操作ij戈鲁。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性仇参，可以把多個變量放在一個對象里來進行CAS操作。

ABA問題

ABA問題：CAS需要在操作值的時候檢查下值有沒有發(fā)生變化婆殿，如果沒有發(fā)生變化則更新诈乒，但是如果一個值原來是A，變成了B婆芦，又變成了A怕磨，那么使用CAS進行檢查時會認(rèn)為它的值沒有發(fā)生變化，但是實際上卻變化了消约。
一開始肠鲫，我不明白ABA問題會有什么隱患，值沒發(fā)生變化會有什么影響嗎或粮？
下面通過一個例子來說明ABA問題的隱患：

ABA-1.png

現(xiàn)有一個用單向鏈表實現(xiàn)的堆棧导饲，棧頂為A，這時線程T1已經(jīng)知道A.next為B，然后希望用CAS將棧頂替換為B：

head.compareAndSet(A,B);

在T1執(zhí)行上面這條指令之前渣锦，線程T2介入硝岗，將A、B出棧袋毙，再push D型檀、C、A娄猫，此時堆棧結(jié)構(gòu)如下圖贱除，而對象B此時處于游離狀態(tài)：

ABA-2.png

ABA-3.png

public class ABA {
    private static AtomicInteger atomicInt = new AtomicInteger(100);
    private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(100, 0);

    public static void main(String[] args) throws InterruptedException {

        Thread intT1 = new Thread(new Runnable() {
            public void run() {
                atomicInt.compareAndSet(100, 101);
                atomicInt.compareAndSet(101, 100);
            }
        });

        Thread intT2 = new Thread(new Runnable() {
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                }
                boolean c3 = atomicInt.compareAndSet(100, 101);
                System.out.println(c3); // true
            }
        });

        intT1.start();
        intT2.start();
        intT1.join();
        intT2.join();

        Thread refT1 = new Thread(new Runnable() {
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                }
                atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
            }
        });

        Thread refT2 = new Thread(new Runnable() {
            public void run() {
                int stamp = atomicStampedRef.getStamp();
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                }
                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                System.out.println(c3); // false
            }
        });

        refT1.start();
        refT2.start();
    }
}

參考

1. 維基百科CAS
2. 面試必問的CAS诉植，要多了解
   
3. JAVA-CAS簡介以及ABA問題
   
4. 用AtomicStampedReference解決ABA問題