本文來源于微信公衆号【胖滾豬學程式設計】、轉載請注明出處
在漫畫并發程式設計系統博文中，我們講了N篇關于鎖的知識，确實，鎖是解決并發問題的萬能鑰匙，可是并發問題隻有鎖能解決嗎？今天要出場一個大BOSS：CAS無鎖算法，可謂是并發程式設計核心中的核心！
溫故
首先我們再回顧一下原子性問題的原因，參考
【漫畫】JAVA并發程式設計 如何解決原子性問題。
兩個線程同時把count=0加載到自己的工作記憶體，線程B先執行count++操作，此時主記憶體已經變化成了1，但是線程A依舊以為count=0，這是導緻問題的根源。
是以解決方案就是：不能讓線程A以為count=0，而是要和主記憶體進行一次compare(比較)，如果記憶體中的值是0，說明沒有其他線程更新過count值，那麼就swap(交換)，把新值寫回主記憶體。如果記憶體中的值不是0，比如本案例中，記憶體中count就已經被線程B更新成了1，比較0!=1，是以compare失敗，不把新值寫回主記憶體。
本文來源于微信公衆号【胖滾豬學程式設計】、以漫畫形式讓程式設計so easy and interesting！轉載請注明出處
CAS概念
CAS （compareAndSwap），中文叫比較交換，一種無鎖原子算法。
CAS算法包含 3 個參數 CAS（V，E，N），V表示要更新變量在記憶體中的值，E表示舊的預期值，N表示新值。
僅當 V值等于E值時，才會将V的值設為N。
如果V值和E值不同，則說明已經有其他線程做兩個更新，那麼目前線程不做更新，而是自旋。
模拟CAS實作
既然我們了解了CAS的思想，那可以手寫一個簡單的CAS模型：
// count必須用volatile修飾 保證不同線程之間的可見性
private volatile static int count;
public void addOne() {
int newValue;
do {
newValue = count++;
} while (!compareAndSwapInt(expectCount, newValue)); //自旋 循環
}
public final boolean compareAndSwapInt(int expectCount, int newValue) {
// 讀目前 count 的值
int curValue = count;
// 比較目前 count 值是否 == 期望值
if (curValue == expectCount) {
// 如果是，則更新 count 的值
count = newValue;
return true;
}
//否則傳回false 然後循環
return false;
} 這個簡單的模拟代碼，其實基本上把CAS的思想展現出來了，但實際上CAS原理可要複雜很多哦，我們還是看看JAVA是怎麼實作CAS的吧！
原子類
要了解JAVA中CAS的實作，那不得不提到大名鼎鼎的原子類，原子類的使用非常簡單，而其中深奧的原理就是CAS無鎖算法。
Java 并發包裡提供的原子類内容很豐富，我們可以将它們分為五個類别：原子化的基本資料類型、原子化的對象引用類型、原子化數組、原子化對象屬性更新器和原子化的累加器。
原子類的使用可謂非常簡單，相信隻要看一下api就知道如何使用，是以不過多解釋，如有需要可以參考本人github代碼。
此處隻以AtomicInteger為例子，測試一下原子類是否名副其實可以保證原子性：
private static AtomicInteger count = new AtomicInteger(0);
private static int count1 = 0;
//省略代碼 同時啟動10個線程 分别測試AtomicInteger和普通int的輸出結果
private static void add10K() {
int idx = 0;
while (idx++ < 10000) {
//使用incrementAndGet實作i++功能
count.incrementAndGet();
}
countDownLatch.countDown();
}
private static void add10K1() {
int idx = 0;
while (idx++ < 10000) {
count1++;
}
countDownLatch.countDown();
} 通過測試可以發現，使用AtomicInteger可以保證輸出結果為100000，而普通int則不能保證。
CAS源碼分析
據此，我們又可以回歸正題，JAVA是怎麼實作CAS的呢？跟蹤一下AtomicInteger中的incrementAndGet()方法，相信就會有答案了。
首先關注一下AtomicInteger.java中這麼幾個東西：
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;//資料在記憶體中的位址偏移量，通過偏移位址可以擷取資料原值
static {
try {
//計算變量 value 在類對象中的偏移量
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;//要修改的值 volatile保證可見性
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
} Unsafe，是CAS的核心類，由于Java方法無法直接通路底層系統，需要通過本地（native）方法來通路，Unsafe相當于一個後門，基于該類可以直接操作特定記憶體的資料。
變量valueOffset，表示該變量值在記憶體中的偏移位址，因為Unsafe就是根據記憶體偏移位址擷取資料的。
變量value必須用volatile修飾，保證了多線程之間的記憶體可見性。
當然具體實作我們還是得瞧瞧getAndAddInt方法：
//内部使用自旋的方式進行CAS更新（while循環進行CAS更新，如果更新失敗，則循環再次重試）
public final int getAndAddInt(Object var1, long var2, int var4) {
//var1為目前這個對象，如count.getAndIncrement()，則var1為count這個對象
//第二個參數為AtomicInteger對象value成員變量在記憶體中的偏移量
//第三個參數為要增加的值
int var5;
do {
//var5 擷取對象記憶體位址偏移量上的數值v 即預期舊值
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//循環判斷記憶體位置的值與預期原值是否相比對
return var5;
} 此時我們還想繼續了解compareAndSwapInt的實作，點進去看，首先映入眼簾的是四個參數：1、目前的執行個體 2、執行個體變量的記憶體位址偏移量 3、預期的舊值 4、要更新的值
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5); 還想繼續刨根問底，會發現點不動了。因為用native修飾的方法代表是底層方法，當然如果你非得一探究竟你也可以找找對應的unsafe.cpp 檔案進行深度解析C代碼：
個人認為沒必要深究，畢竟術業有專攻，你隻需要知道其實核心代碼就是一條 cmpxchg 指令。
cmpxchg: 即“比較并交換”指令。與我們上面說的思想是一樣的：将 eax 寄存器中的值（compare_value）與 [edx] 雙字記憶體單元中的值進行對比，如果相同，則将 ecx 寄存器中的值（exchange_value）存入 [edx] 記憶體單元中。
總之：你隻需要記住：CAS是靠硬體實作的，進而在硬體層面提升效率。實作方式是基于硬體平台的彙編指令，在intel的CPU中，使用的是cmpxchg指令。 核心思想就是：比較要更新變量的值V和預期值E（compare），相等才會将V的值設為新值N（swap）。
CAS真有這麼好嗎？
CAS和鎖都解決了原子性問題，和鎖相比，由于其非阻塞的，它對死鎖問題天生免疫，并且，線程間的互相影響也非常小。更為重要的是，使用無鎖的方式完全沒有鎖競争帶來的系統開銷，也沒有線程間頻繁排程帶來的開銷，是以，他要比基于鎖的方式擁有更優越的性能。
但是，CAS真的有那麼好嗎？又到挑刺時間了！
要讓我們失望了，CAS并沒有那麼好，主要表現在三個方面：
- 1、循環時間太長
- 2、隻能保證一個共享變量原子操作
- 3、ABA問題。
循環時間太長
如果CAS長時間地不成功，我們知道會持續循環、自旋。必然會給CPU帶來非常大的開銷。在JUC中有些地方就限制了CAS自旋的次數，例如BlockingQueue的SynchronousQueue。
隻能保證一個共享變量原子操作
看了CAS的實作就知道這隻能針對一個共享變量，如果是多個共享變量就隻能使用鎖了，當然如果你有辦法把多個變量整成一個變量，利用CAS也不錯。例如讀寫鎖中state的高低位。
ABA問題
這可是個面試重點問題哦！認真聽好！
CAS需要檢查操作值有沒有發生改變，如果沒有發生改變則更新。但是存在這樣一種情況：如果一個值原來是A，變成了B，然後又變成了A，那麼在CAS檢查的時候會發現沒有改變，但是實質上它已經發生了改變，這就是所謂的ABA問題。
某些情況我們并不關心 ABA 問題，例如數值的原子遞增，但也不能所有情況下都不關心，例如原子化的更新對象很可能就需要關心 ABA 問題，因為兩個 A 雖然相等，但是第二個 A 的屬性可能已經發生變化了。
對于ABA問題其解決方案是加上版本号，即在每個變量都加上一個版本号，每次改變時加1，即A —> B —> A，變成1A —> 2B —> 3A。
原子類之AtomicStampedReference可以解決ABA問題，它内部不僅維護了對象值，還維護了一個Stamp（可把它了解為版本号，它使用整數來表示狀态值）。當AtomicStampedReference對應的數值被修改時，除了更新資料本身外，還必須要更新版本号。當AtomicStampedReference設定對象值時，對象值以及版本号都必須滿足期望值，寫入才會成功。是以，即使對象值被反複讀寫，寫回原值，隻要版本号發生變化，就能防止不恰當的寫入。
// 參數依次為：期望值 寫入新值 期望版本号 新版本号
public boolean compareAndSet(V expectedReference, V
newReference, int expectedStamp, int newStamp);
//獲得目前對象引用
public V getReference();
//獲得目前版本号
public int getStamp();
//設定目前對象引用和版本号
public void set(V newReference, int newStamp); 說理論太多也沒用，還是親自實驗它是否能解決ABA問題吧：
private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(10, 0);
public static void main(String[] args) {
Thread main = new Thread(() -> {
int stamp = count.getStamp(); //擷取目前版本
log.info("線程{} 目前版本{}",Thread.currentThread(),stamp);
try {
Thread.sleep(1000); //等待1秒 ，以便讓幹擾線程執行
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean isCASSuccess = count.compareAndSet(10, 12, stamp, stamp + 1); //此時expectedReference未發生改變，但是stamp已經被修改了,是以CAS失敗
log.info("CAS是否成功={}",isCASSuccess);
}, "主操作線程");
Thread other = new Thread(() -> {
int stamp = count.getStamp(); //擷取目前版本
log.info("線程{} 目前版本{}",Thread.currentThread(),stamp);
count.compareAndSet(10, 12, stamp, stamp + 1);
log.info("線程{} 增加後版本{}",Thread.currentThread(),count.getStamp());
// 模拟ABA問題 先更新成12 又更新回10
int stamp1 = count.getStamp(); //擷取目前版本
count.compareAndSet(12, 10, stamp1, stamp1 + 1);
log.info("線程{} 減少後版本{}",Thread.currentThread(),count.getStamp());
}, "幹擾線程");
main.start();
other.start();
} 輸出結果如下：
線程Thread[主操作線程,5,main] 目前版本0
[幹擾線程] INFO - 線程Thread[幹擾線程,5,main] 目前版本0
[幹擾線程] INFO - 線程Thread[幹擾線程,5,main] 增加後版本1
[幹擾線程] INFO - 線程Thread[幹擾線程,5,main] 減少後版本2
[主操作線程] INFO - CAS是否成功=false 總結
JAVA博大精深，解決并發問題可不僅僅是鎖才能擔此大任。CAS無鎖算法對于解決原子性問題同樣是勢在必得。而原子類，則是無鎖工具類的典範，原子類包括五大類型(原子化的基本資料類型、原子化的對象引用類型、原子化數組、原子化對象屬性更新器和原子化的累加器)。
CAS 是一種樂觀鎖，樂觀鎖會以一種更加樂觀的态度對待事情，認為自己可以操作成功。而悲觀鎖會讓線程一直阻塞。是以CAS具有很多優勢，比如性能佳、可以避免死鎖。但是它沒有那麼好，你應該考慮到ABA問題、循環時間長的問題。是以需要綜合選擇，适合自己的才是最好的。
附錄：
并發程式設計全系列代碼github