CAS负间，Compare And Swap，即比較并交換甜滨。Doug lea大神在同步組件中大量使用使用CAS技術(shù)鬼斧神工地實(shí)現(xiàn)了Java多線程的并發(fā)操作潘飘。整個(gè)AQS同步組件肮之、Atomic原子類操作等等都是以CAS實(shí)現(xiàn)的掉缺，甚至ConcurrentHashMap在1.8的版本中也調(diào)整為了CAS+Synchronized「昵埽可以說CAS是整個(gè)JUC的基石眶明。
CAS分析
在CAS中有三個(gè)參數(shù)：內(nèi)存值V、舊的預(yù)期值A(chǔ)筐高、要更新的值B搜囱，當(dāng)且僅當(dāng)內(nèi)存值V的值等于舊的預(yù)期值A(chǔ)時(shí)才會將內(nèi)存值V的值修改為B捅儒，否則什么都不干飞蚓。其偽代碼如下：
if(this.value == A){
this.value = B
return true;
}else{
return false;
}
JUC下的atomic類都是通過CAS來實(shí)現(xiàn)的吊履，下面我么就以AtomicInteger為例來闡述CAS的實(shí)現(xiàn)宇立。如下：
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;
Unsafe是CAS的核心類，Java無法直接訪問底層操作系統(tǒng)纯出，而是通過本地（native）方法來訪問奋刽。不過盡管如此滞磺，JVM還是開了一個(gè)后門：Unsafe诫欠，它提供了硬件級別的原子操作涵卵。
valueOffset為變量值在內(nèi)存中的偏移地址浴栽，unsafe就是通過偏移地址來得到數(shù)據(jù)的原值的荒叼。
value當(dāng)前值，使用volatile修飾典鸡，保證多線程環(huán)境下看見的是同一個(gè)被廓。
我們就以
AtomicInteger的addAndGet
()方法來做說明，先看源代碼：
public final int addAndGet(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
}
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;
}
內(nèi)部調(diào)用unsafe的getAndAddInt方法萝玷，在getAndAddInt方法中主要是看compareAndSwapInt方法：
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
該方法為本地方法嫁乘，有四個(gè)參數(shù)，分別代表：對象球碉、對象的地址蜓斧、預(yù)期值、修改值（有位伙伴告訴我他面試的時(shí)候就問到這四個(gè)變量是啥意思...+_+）睁冬。該方法的實(shí)現(xiàn)這里就不做詳細(xì)介紹了挎春，有興趣的伙伴可以看看openjdk的源碼。
CAS可以保證一次的讀-改-寫操作是原子操作豆拨，在單處理器上該操作容易實(shí)現(xiàn)直奋，但是在多處理器上實(shí)現(xiàn)就有點(diǎn)兒復(fù)雜了。
CPU提供了兩種方法來實(shí)現(xiàn)多處理器的原子操作：總線加鎖或者緩存加鎖施禾。
總線加鎖：總線加鎖就是就是使用處理器提供的一個(gè)LOCK#信號脚线，當(dāng)一個(gè)處理器在總線上輸出此信號時(shí)，其他處理器的請求將被阻塞住,那么該處理器可以獨(dú)占使用共享內(nèi)存弥搞。但是這種處理方式顯得有點(diǎn)兒霸道邮绿，不厚道渠旁，他把CPU和內(nèi)存之間的通信鎖住了，在鎖定期間船逮，其他處理器都不能其他內(nèi)存地址的數(shù)據(jù)一死，嗎其開銷有點(diǎn)兒大。所以就有了緩存加鎖傻唾。
緩存加鎖：其實(shí)針對于上面那種情況我們只需要保證在同一時(shí)刻對某個(gè)內(nèi)存地址的操作是原子性的即可投慈。緩存加鎖就是緩存在內(nèi)存區(qū)域的數(shù)據(jù)如果在加鎖期間，當(dāng)它執(zhí)行鎖操作寫回內(nèi)存時(shí)冠骄，處理器不在輸出LOCK#信號伪煤，而是修改內(nèi)部的內(nèi)存地址，利用緩存一致性協(xié)議來保證原子性凛辣。緩存一致性機(jī)制可以保證同一個(gè)內(nèi)存區(qū)域的數(shù)據(jù)僅能被一個(gè)處理器修改抱既，也就是說當(dāng)CPU1修改緩存行中的i時(shí)使用緩存鎖定，那么CPU2就不能同時(shí)緩存了i的緩存行扁誓。
CAS缺陷
CAS雖然高效地解決了原子操作防泵，但是還是存在一些缺陷的，主要表現(xiàn)在三個(gè)方法：循環(huán)時(shí)間太長蝗敢、只能保證一個(gè)共享變量原子操作捷泞、ABA問題。
循環(huán)時(shí)間太長
如果CAS一直不成功呢寿谴？這種情況絕對有可能發(fā)生锁右，如果自旋CAS長時(shí)間地不成功，則會給CPU帶來非常大的開銷讶泰。
只能保證一個(gè)共享變量原子操作
看了CAS的實(shí)現(xiàn)就知道這只能針對一個(gè)共享變量咏瑟，如果是多個(gè)共享變量就只能使用鎖了，當(dāng)然如果你有辦法把多個(gè)變量整成一個(gè)變量痪署，利用CAS也不錯(cuò)码泞。
ABA問題
CAS需要檢查操作值有沒有發(fā)生改變，如果沒有發(fā)生改變則更新狼犯。但是存在這樣一種情況如果一個(gè)值原來是A余寥，變成了B，然后又變成了A辜王，那么在CAS檢查的時(shí)候會發(fā)現(xiàn)沒有改變劈狐，但是實(shí)質(zhì)上它已經(jīng)發(fā)生了改變，這就是所謂的ABA問題呐馆。對于ABA問題其解決方案是加上版本號肥缔，即在每個(gè)變量都加上一個(gè)版本號，每次改變時(shí)加1汹来，即A —> B —> A续膳，變成1A —> 2B —> 3A改艇。
用一個(gè)例子來闡述ABA問題所帶來的影響。
有如下鏈表
假如我們想要把B替換為A坟岔，也就是compareAndSet(this,A,B)谒兄。線程1執(zhí)行B替換A操作，線程2主要執(zhí)行如下動(dòng)作社付，A 承疲、B出棧，然后C鸥咖、A入棧燕鸽，最終該鏈表如下：
完成后線程1發(fā)現(xiàn)仍然是A，那么compareAndSet(this,A,B)成功啼辣，但是這時(shí)會存在一個(gè)問題就是B.next = null,compareAndSet(this,A,B)后啊研，會導(dǎo)致C丟失，改棧僅有一個(gè)B元素鸥拧，平白無故把C給丟失了党远。
CAS的ABA隱患問題，解決方案則是版本號富弦，Java提供了AtomicStampedReference來解決沟娱。AtomicStampedReference通過包裝[E,Integer]的元組來對對象標(biāo)記版本戳stamp，從而避免ABA問題舆声。對于上面的案例應(yīng)該線程1會失敗花沉。
AtomicStampedReference的compareAndSet()方法定義如下：
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)));
}
compareAndSet有四個(gè)參數(shù)柳爽，分別表示：預(yù)期引用媳握、更新后的引用、預(yù)期標(biāo)志磷脯、更新后的標(biāo)志蛾找。源碼部門很好理解預(yù)期的引用 == 當(dāng)前引用，預(yù)期的標(biāo)識 == 當(dāng)前標(biāo)識赵誓，如果更新后的引用和標(biāo)志和當(dāng)前的引用和標(biāo)志相等則直接返回true打毛，否則通過Pair生成一個(gè)新的pair對象與當(dāng)前pair CAS替換。Pair為AtomicStampedReference的內(nèi)部類俩功，主要用于記錄引用和版本戳信息（標(biāo)識）幻枉，定義如下：
private static class Pair<T> {
final T reference;
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;
Pair記錄著對象的引用和版本戳，版本戳為int型诡蜓，保持自增熬甫。同時(shí)Pair是一個(gè)不可變對象，其所有屬性全部定義為final蔓罚，對外提供一個(gè)of方法椿肩，該方法返回一個(gè)新建的Pari對象瞻颂。pair對象定義為volatile，保證多線程環(huán)境下的可見性郑象。在AtomicStampedReference中贡这，大多方法都是通過調(diào)用Pair的of方法來產(chǎn)生一個(gè)新的Pair對象，然后賦值給變量pair厂榛。如set方法：
public void set(V newReference, int newStamp) {
Pair<V> current = pair;
if (newReference != current.reference || newStamp != current.stamp)
this.pair = Pair.of(newReference, newStamp);
}
下面我們將通過一個(gè)例子可以可以看到AtomicStampedReference和AtomicInteger的區(qū)別盖矫。我們定義兩個(gè)線程，線程1負(fù)責(zé)將100 —> 110 —> 100击奶，線程2執(zhí)行 100 —>120炼彪，看兩者之間的區(qū)別。
public class Test {
private static AtomicInteger atomicInteger = new AtomicInteger(100);
private static AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100,1);
public static void main(String[] args) throws InterruptedException {
//AtomicInteger
Thread at1 = new Thread(new Runnable() {
@Override
public void run() {
atomicInteger.compareAndSet(100,110);
atomicInteger.compareAndSet(110,100);
}
});
Thread at2 = new Thread(new Runnable() {
@Override
public void run() {
try {
TimeUnit.SECONDS.sleep(2); // at1,執(zhí)行完
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("AtomicInteger:" + atomicInteger.compareAndSet(100,120));
}
});
at1.start();
at2.start();
at1.join();
at2.join();
//AtomicStampedReference
Thread tsf1 = new Thread(new Runnable() {
@Override
public void run() {
try {
//讓 tsf2先獲取stamp正歼，導(dǎo)致預(yù)期時(shí)間戳不一致
TimeUnit.SECONDS.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
// 預(yù)期引用：100辐马，更新后的引用：110，預(yù)期標(biāo)識getStamp() 更新后的標(biāo)識getStamp() + 1
atomicStampedReference.compareAndSet(100,110,atomicStampedReference.getStamp(),atomicStampedReference.getStamp() + 1);
atomicStampedReference.compareAndSet(110,100,atomicStampedReference.getStamp(),atomicStampedReference.getStamp() + 1);
}
});
Thread tsf2 = new Thread(new Runnable() {
@Override
public void run() {
int stamp = atomicStampedReference.getStamp();
try {
TimeUnit.SECONDS.sleep(2); //線程tsf1執(zhí)行完
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("AtomicStampedReference:" +atomicStampedReference.compareAndSet(100,120,stamp,stamp + 1));
}
});
tsf1.start();
tsf2.start();
}
}
運(yùn)行結(jié)果：
運(yùn)行結(jié)果充分展示了AtomicInteger的ABA問題和AtomicStampedReference解決ABA問題局义。
