前言

?在并發編程時，常常會出現線程安全問題，那么如何保證原子性呢？常用的方法就是加鎖。在Java語言中可以使用 Synchronized和CAS實現加鎖效果。
?Synchronized關鍵字保證同步的，這會導致有鎖，但是鎖機制存在以下問題：

1. 在多線程競爭下，加鎖、釋放鎖會導致比較多的上下文切換和調度延時，引起性能問題。

2. 一個線程持有鎖會導致其它所有需要此鎖的線程掛起。

3. 如果一個優先級高的線程等待一個優先級低的線程釋放鎖會導致優先級倒置，引起性能風險。

而volatile是不錯的機制，但是volatile不能保證原子性。因此對于同步最終還是要回到鎖機制上來。
?獨占鎖是一種悲觀鎖，synchronized就是一種獨占鎖，會導致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖。而另一個更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。樂觀鎖用到的機制就是CAS，Compare and Swap。

---

一、什么是CAS？

1.1 概念：

?CAS全稱Compare and swap，字面意思:”比較并交換“，它是一條 CPU 并發原語，用于判斷內存中某個值是否為預期值，如果是則更改為新的值，這個過程是原子的。

1.2 實現步驟

具體步驟如下所示：

1. 一個初始值變量V，值為5；一開始先讀取V實際內存中的值賦值給E。
2. 比如我們需要給最原始的V+1操作，那么此時用E+1來進行操作（這是防止V在其他線程已經被改變），這樣完成了U=E+1的操作。
3. 判斷E和V的值是否一致，如果一致則證明在以上操作過程中V沒有被其他線程改變則將U的值賦值給V，如果不一致那V就被其他改變了，這樣給U的+1操作就不成立，返回當前的V。
   

1.3 CAS 偽代碼

boolean CAS(address, expectValue, swapValue) {if (&address == expectedValue) {&address = swapValue;return true;}return false;
}

當多個線程同時對某個資源進行CAS操作，只能有一個線程操作成功，但是并不會阻塞其他線程,其他線程只會收到操作失敗的信號。

1.4 實現自旋鎖

基于 CAS 實現更靈活的鎖，獲取到更多的控制權。

public class SpinLock {private Thread owner = null;public void lock(){// 通過 CAS 看當前鎖是否被某個線程持有.// 如果這個鎖已經被別的線程持有, 那么就自旋等待.// 如果這個鎖沒有被別的線程持有, 那么就把 owner 設為當前嘗試加鎖的線程.while(!CAS(this.owner, null, Thread.currentThread())){}}public void unlock (){this.owner = null;}
}

二、CAS中的問題

2.1 ABA問題

?ABA 是 CAS 操作的一個經典問題，假設有一個變量初始值為 A，修改為 B，然后又修改為 A，這個變量實際被修改過了，但是 CAS 操作可能無法感知到。
?假設存在兩個線程 t1 和 t2，有一個共享變量 num，初始值為 A。接下來, 線程 t1 想使用 CAS 把 num 值改成 Z, 那么就需要

1. 先讀取 num 的值, 記錄到 oldNum 變量中；
2. 使用 CAS 判定當前 num 的值是否為 A, 如果為 A, 就修改成 Z.

但是, 在 t1 執行這兩個操作之間，t2 線程可能把 num 的值從 A 改成了 B，又從 B 改成了 A。

?如果是整形還好，不會影響最終結果，但如果是對象的引用類型包含了多個變量，引用沒有變實際上包含的變量已經被修改，這就會造成大問題

2.2 ABA問題帶來的BUG

大部分的情況下，t2 線程這樣的一個反復橫跳改動，對于 t1 是否修改 num 是沒有影響的，但是不排除一些特殊情況。

我們接下來舉一個銀行取款大的例子：
假設 小明 有 100 存款，小明想從 ATM 取 50 塊錢。取款機創建了兩個線程, 并發的來執行 -50 操作。我們期望一個線程執行 -50 成功，另一個線程 -50 失敗。如果使用 CAS 的方式來完成這個扣款過程就可能出現問題。

正常過程：

1. 存款 100，線程1 獲取到當前存款值為 100，期望更新為 50; 線程2 獲取到當前存款值為 100, 期望更新為 50；
2. 線程1 執行扣款成功, 存款被改成 50. 線程2 阻塞等待中；
3. 輪到線程2 執行了，發現當前存款為 50, 和之前讀到的 100 不相同, 執行失敗。

異常的過程

1. 存款 100，線程1 獲取到當前存款值為 100，期望更新為 50; 線程2 獲取到當前存款值為 100，期望更新為 50；
2. 線程1 執行扣款成功，存款被改成 50，線程2 阻塞等待中；
3. 線程2 執行之前，小明的朋友正好給小明轉賬 50，賬戶余額變成 100；
4. 輪到線程2 執行了，發現當前存款為 100，和之前讀到的 100 相同，再次執行扣款操作。
   這個時候, 扣款操作被執行了兩次! 都是 ABA 問題導致的結果。

2.3 ABA解決方案

給要修改的值，引入版本號，在 CAS 比較數據當前值和舊值的同時，也要比較版本號是否符合預期。

1. CAS 操作在讀取舊值的同時，也要讀取版本號。
2. 真正修改的時候，
   如果當前版本號和讀到的版本號相同, 則修改數據, 并把版本號 +1；
   如果當前版本號高于讀到的版本號，就操作失敗(認為數據已經被修改過了)。

我們依然舉一個銀行取款的例子：

為了解決 ABA 問題, 給余額搭配一個版本號, 初始設為 1：

1. 存款 100， 線程1 獲取到 存款值為 100，版本號為 1，期望更新為 50; 線程2 獲取到存款值為 100，版本號為 1，期望更新為 50。
2. 線程1 執行扣款成功，存款被改成 50，版本號改為2。線程2 阻塞等待中。
3. 在線程2 執行之前, 小明的朋友正好給小明轉賬 50, 賬戶余額變成 100, 版本號變成3.
4. 輪到線程2 執行了，發現當前存款為 100，和之前讀到的 100 相同， 但是當前版本號為 3，之前讀 到的版本號為 1，版本小于當前版本, 認為操作失敗。

總結

講解下自己理解的 CAS 機制

?全稱 Compare and swap, 即 “比較并交換”， 相當于通過一個原子的操作, 同時完成 “讀取內存, 比較是否相等, 修改內存” 這三個步驟. 本質上需要 CPU 指令的支撐。

ABA問題如何解決

?給要修改的數據引入版本號， 在 CAS 比較數據當前值和舊值的同時,也要比較版本號是否符合預期。如果發現當前版本號和之前讀到的版本號一致，就真正執行修改操作，并讓版本號自增；如果發現當前版本號比之前讀到的版本號大， 就認為操作失敗。