【多線程】CAS詳解

🌴什么是 CAS

CAS: 全稱Compare and swap字?意思:”?較并交換“，?個 CAS 涉及到以下操作：

我們假設內存中的原數據V，舊的預期值A，需要修改的新值B。

?較 A 與 V 是否相等。（?較）
如果?較相等，將 B 寫? V。（交換）
返回操作是否成功。

🌸CAS 偽代碼

下?寫的代碼不是原?的, 真實的 CAS 是?個原?的硬件指令完成的. 這個偽代碼只是輔助理解 CAS的?作流程.

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

下面看兩種典型的不是原子性的代碼：

check and set (if 判定然后設定值) [上?的 CAS 偽代碼就是這種形式]
read and update (i++) [之前我們講線程安全的代碼例?是這種形式]

CAS原子性的作用：

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

所以

CAS 可以視為是?種樂觀鎖. (或者可以理解成 CAS 是樂觀鎖的?種實現?式)

🎍CAS 是怎么實現的

針對不同的操作系統，JVM ?到了不同的 CAS 實現原理，簡單來講：

java 的 CAS 利?的的是 unsafe 這個類提供的 CAS 操作；
unsafe 的 CAS 依賴了的是 jvm 針對不同的操作系統實現的 Atomic::cmpxchg；
Atomic::cmpxchg 的實現使?了匯編的 CAS 操作，并使? cpu 硬件提供的 lock 機制保證其原?
性。

簡??之，是因為硬件予以了?持，軟件層?才能做到。

🍀CAS 有哪些應?

🌸實現原子類

標準庫中提供了 java.util.concurrent.atomic 包, ??的類都是基于這種?式來實現的.
典型的就是 AtomicInteger 類. 其中的 getAndIncrement 相當于 i++ 操作.

AtomicInteger atomicInteger = new AtomicInteger(0);
// 相當于 i++
atomicInteger.getAndIncrement();

偽代碼實現:

class AtomicInteger {private int value;public int getAndIncrement() {int oldValue = value;while ( CAS(value, oldValue, oldValue+1) != true) {oldValue = value;}return oldValue;}}

假設兩個線程同時調? getAndIncrement

兩個線程都讀取 value 的值到 oldValue 中. (oldValue 是?個局部變量, 在棧上. 每個線程有??的
棧)
線程1 先執? CAS 操作. 由于 oldValue 和 value 的值相同, 直接進?對 value 賦值.

注意:
? CAS 是直接讀寫內存的, ?不是操作寄存器.
? CAS 的讀內存, ?較, 寫內存操作是?條硬件指令, 是原?的.

在這里插入圖片描述
3. 線程2 再執? CAS 操作, 第?次 CAS 的時候發現 oldValue 和 value 不相等, 不能進?賦值. 因此需要進?循環.

在循環?重新讀取 value 的值賦給 oldValue
在這里插入圖片描述
4. 線程2 接下來第?次執? CAS, 此時 oldValue 和 value 相同, 于是直接執?賦值操作.

在這里插入圖片描述
5. 線程1 和線程2 返回各?的 oldValue 的值即可.

通過形如上述代碼就可以實現?個原?類. 不需要使?重量級鎖, 就可以?效的完成多線程的?增操作.

本來 check and set 這樣的操作在代碼?度不是原?的. 但是在硬件層?上可以讓?條指令完成這個
操作, 也就變成原?的了.

🌸實現自旋鎖

基于 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 的 ABA 問題

🌸什么是 ABA 問題？

通過下面的例子理解ABA問題：

假設存在兩個線程 t1 和 t2. 有?個共享變量 num, 初始值為 A.
接下來, 線程 t1 想使? CAS 把 num 值改成 Z, 那么就需要

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

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

線程 t1 的 CAS 是期望 num 不變就修改. 但是 num 的值已經被 t2 給改了. 只不過?改成 A 了. 這個時
候 t1 究竟是否要更新 num 的值為 Z 呢?

到這?步, t1 線程?法區分當前這個變量始終是 A, 還是經歷了?個變化過程.

在這里插入圖片描述
這就好?, 我們買?個?機, ?法判定這個?機是剛出?的新?機, 還是別??舊了, ?翻新過的?機.

🌸ABA 問題引來的 BUG

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

假設滑稽?哥有 100 存款. 滑稽想從 ATM 取 50 塊錢. 取款機創建了兩個線程, 并發的來執? -50 操作.
我們期望?個線程執? -50 成功, 另?個線程 -50 失敗. 如果使? CAS 的?式來完成這個扣款過程就可能出現問題.

正常的過程：

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

異常的過程

存款 100. 線程1 獲取到當前存款值為 100, 期望更新為 50; 線程2 獲取到當前存款值為 100, 期望更
新為 50.
線程1 執?扣款成功, 存款被改成 50. 線程2 阻塞等待中.
在線程2 執?之前, 滑稽的朋友正好給滑稽轉賬 50, 賬?余額變成 100 !!
輪到線程2 執?了, 發現當前存款為 100, 和之前讀到的 100 相同, 再次執?扣款操作

這個時候, 扣款操作被執?了兩次!!! 都是 ABA 問題搞的?!!

🌸解決方案

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

? CAS 操作在讀取舊值的同時, 也要讀取版本號.
? 真正修改的時候,

如果當前版本號和讀到的版本號相同, 則修改數據, 并把版本號 + 1.
如果當前版本號?于讀到的版本號. 就操作失敗(認為數據已經被修改過了).

這就好?, 判定這個?機是否是翻新機, 那么就需要收集每個?機的數據, 第?次掛在電商?站上的?
機記為版本1, 以后每次這個?機出現在電商?站上, 就把版本號進?遞增. 這樣如果買家不在意這是翻
新機, 就買. 如果買家在意, 就可以直接略過.

對?理解上?的轉賬例子

假設滑稽?哥有 100 存款. 滑稽想從 ATM 取 50 塊錢. 取款機創建了兩個線程, 并發的來執? -50 操作.
我們期望?個線程執? -50 成功, 另?個線程 -50 失敗. 為了解決 ABA 問題, 給余額搭配?個版本號, 初始設為 1.

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

在 Java 標準庫中提供了 AtomicStampedReference 類. 這個類可以對某個類進?包裝, 在內
部就提供了上?描述的版本管理功能.