CAS原理
CAS的定義
- JDK 1.5的時候，Java支持了Atomic類，這些類的操作都屬於原子操作；
- 幫助最大限度地減少在多線程場景中對於一些基本操作的複雜性；
- 而Atomic類的實現都依賴與 CAS（compare and swap） 算法
樂觀鎖和悲觀鎖
悲觀鎖
常見的悲觀鎖
- 獨佔鎖：synchronized
悲觀鎖的實現
- 在多線程的場景下，當線程數量大於CPU數的時候，就需要進行分片處理，即把CPU的時間片，分配給不同的線程輪流執行，也就是我們常說的多線程的並發執行（間隔性執行）；
- 在某個線程執行完時間片之後，就會進行CPU切換；切換過程：清空寄存器和緩存數據，重新加載新的線程所需要的數據（線程私有的：JVM運行時所需的數據：程序計數器、虛擬機棧和本地方法棧）；
- 此時之前的線程就被掛起，加入到阻塞隊列中，在一定的時間和條件下，通過調用 notify() 或 notifyAll() 喚醒，進入就緒狀態（runnable），等待CPU調度。
總結：
- 總是假設最壞的情況，並且只有在確保其他線程不會造成干擾的情況下才會執行；
- 導致其他所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖，再次進行鎖的競爭（公平鎖 / 非公平鎖）。
缺點
- 線程會被頻繁的掛起，喚醒之後需要重新搶佔鎖
- 場景：如果一個線程需要某個資源，但是這個資源的佔用時間很短，當線程第一次搶佔這個資源時，可能這個資源被佔用，如果此時掛起這個線程，但是可能立刻就發現資源已被剛才的線程的釋放，然後又需要花費很長的時間重新搶佔鎖，時間代價就會非常的高。
樂觀鎖
思路
- 每次不加鎖而是假設 沒有衝突 而去完成某種 操作，如果因為衝突失敗就重試，直到成功為止；
- 當某個線程不讓出CPU時，當前線程就一直 while 循環去嘗試獲取鎖，如果失敗就重試，直到成功為止；
- 適用場景：當數據爭用不嚴重時，樂觀鎖效果更好。
樂觀鎖應用
CAS
CAS（Compare and Swap）算法
非阻塞算法
核心參數
- 主內存中存放的 V 值：線程共享（對應JVM的共享內存區：堆和方法區）
- 線程上次從內存中讀取的 V值 A：線程私有，存放在線程的棧幀中
- 需要寫入內存中並改寫V值的B：線程對A值進行操作之後的值，想要存入主內存V中
- V值在主內存中保存，所有線程在對V值操作時，需要先從主存中讀取V值到線程到工作內存A中；
- 然後對A值操作之後，把結果保存在B中，最後再把B值賦給主內存的V；
- 多線程共用V值都是這樣的過程；
- 核心點：將B值賦給V之前，先比較A值和V值是否相等（判斷，當前線程在計算過程中，是否有其他線程已經修改了V值），不相等表示此時的V值已經被其他線程改變，需要重新執行上面的過程；相等就將B值賦給V。
如果沒有CAS這樣的機制，那在多線程的場景下，兩個線程同時對共享數據進行修改，很容易就出錯，導致某一個線程的修改被忽略。
核心代碼
//原子操作
if (A == V) {
V = B;
return B;
} else {
return V;
}
變量 V
如何保證線程每次操作V時，都去主內存中獲取 V 值？
- 自然是在CAS的實現代碼中，變量 V是用 volatile原語 修飾的：保證其可見性；
如何保證在進行 V 和 A 值比較相等之後，而在 B值賦給 V 之前，V值不會被其他線程所修改？
也就是說如何保證比較和替換這兩個步驟的原子性？
看一下CAS原理：
CAS原理
- 底層的實現其實時通過調用 JNI（Java Native Interface 本地調用）的代碼實現的；（其實 JNI 就是為了支持 Java 去調用其他語言）
具體看一下：AtomicInteger類的 compareAndSet() 方法：
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
調用的時 sun.misc 包下 Unsafe 類的 compareAndSwapInt()方法：(本地方法)
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
本地方法會調用 JDK中的幾個cpp文件（這是在widowsX86中的，不同操作系統調用的文件不同，文件中的實現方式也不同）；
具體的C++代碼我就不貼了，知道上層的實現思路就行；
底層大致思路：通過對 cmpxchg 指令添加 lock 前綴（windowsX86中的實現），確保對主內存中 V 值的 讀-改-寫操作原子執行；
不同的操作系統有不同的實現方式，但大致的思路是類似的，目的也都是保證比較賦值操作是原子操作。
更詳細的底層實現，以及相關的一些關於CPU鎖的內容，可以去看一下《Java 並發編程藝術》。
最終的實現作用：
- 確保對主內存中 V 值的 讀-改-寫操作原子執行；
- 禁止該指令與之前和之後的讀（比較）和寫（賦值）指令重排序。
CAS缺點
ABA問題
問題描述
CAS需要在操作值的時候檢查下值有沒有發生變化，如果沒有發生變化則更新，但是如果一個值原來是A，變成了B，又變成了A，那麼使用CAS進行檢查時會發現它的值沒有發生變化，但是實際上卻變化了。
解決方案
版本號
- ABA問題的解決思路就是使用版本號;
- 在變量前面追加上版本號，每次變量更新的時候把版本號加一，那麼A－B－A 就會變成1A-2B－3A
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)));
}
- 跟其他的Atomic類不同的是, 這個多了一個引用的比較;
- 這個會先檢查當前引用是否等於預期引用，並且當前標誌是否等於預期標誌，如果全部相等，則以原子方式將該引用和該標誌的值設置為給定的更新值;
- 所以如果有其他線程修改了, 那麼引用就會改變, 當前線程就執行失敗重試操作;
循環時間長
問題描述
因為CAS機制是: 一直進行失敗重試, 直到成功為止, 那麼自旋CAS 如果長時間不成功, 就會給 CPU 帶來非常大的執行開銷;
解決方案
- 在 JVM 中去支持處理器提供的 pause 指令那麼效率會有一定的提升;
- pause指令的作用:
- 延遲流水線執行指令（de-pipeline）, 使CPU不會消耗過多的執行資源，延遲的時間取決於具體實現的版本，在一些處理器上延遲時間是零;
- 避免在退出循環的時候因內存順序衝突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執行效率。
只能保證一個共享變量的原子操作
問題描述
當對一個共享變量執行操作時，我們可以使用循環 CAS 的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性了
解決方案
- 加鎖
- 把多個共享變量合併成一個共享變量或者把多個變量放在一個對象中, 用 AtomicReference 類來進行CAS操作
總結
-
Java中的CAS操作: 結合 volatile 實現 (volatile 讀和 volatile 寫)
-
而Java中的 CAS 最終調用的是 處理器提供的高效機器級別的原子指令, 這些原子指令 保證 以原子的方式 對主內存中的值 執行 讀-寫-改等一系列操作;
-
所以最本質的就是支持原子性 讀-寫-改指令的計算機
Java 中的 JUC
- volatile 變量的 讀/寫 + CAS 實現線程之間的通信
- 這其實就是 concurrent 包可以實現的基礎, JUC包下源碼實現的通用模式:
- 聲明共享變量為 volatile；
- 使用CAS的原子條件更新來實現線程之間的同步；
- 配合以 volatile 的 讀/寫 和 CAS 所具有的 volatile 讀和寫的內存語義來實現線程之間的通信。
- AQS，非阻塞數據結構 和 原子變量類（java.util.concurrent.atomic包中的類），這些 concurrent 包中的基礎類都是使用這種模式來實現的，而 concurrent 包中的高層類又是依賴於這些基礎類來實現的.
JUC包實現的示意圖:
