Java並發程式設計系列番外篇C A S(Compare and swap)
,文章風格依然是圖文並茂,通俗易懂,讓讀者也能與面試官瘋狂對線。
C A S
作為並發程式設計必不可少的基礎知識,面試時C A S
也是個高頻考點,所以說C A S
是必知必會,本文將帶讀者們深入理解C A S
。
C A S(compareAndSwap)
也叫比較交換,是一種無鎖原子演算法,映射到作業系統就是一條cmpxchg
硬體彙編指令(保證原子性),其作用是讓C P U
將記憶體值更新為新值,但是有個條件,記憶體值必須與期望值相同,且C A S
操作無需用戶態與內核態切換,直接在用戶態對記憶體進行讀寫操作( 意味著不會阻塞/線程上下文切換)。
它包含3
個參數C A S(V,E,N)
,V
表示待更新的記憶體值,E
表示預期值,N
表示新值,當V
值等於E
值時,才會將V
值更新成N
值,如果V
值和E
值不等,不做更新,這就是一次C A S
的運算。
簡單地說,C A S
需要你額外給出一個期望值,也就是你認為這個變數現在應該是什麼樣子的,如果變數不是你想像的那樣,說明它已經被別人修改過了,你只需要重新讀取,設定新期望值,再次嘗試修改就好了。
原子性是指一個或多個運算在C P U
執行的過程中不被中斷的特性,要麼執行,要不執行,不能執行到一半(不可被中斷的一個或一系列操作)。
為了保證C A S
的原子性,C P U
提供了下面兩種方式
匯流排(B U S
)是電腦元件間的傳輸資料方式,也就是說C P U
與其他元件連接傳輸數據,就是靠總線完成的,例如C P U
對記憶體的讀寫。
總線鎖定是指C P U
使用了匯流排鎖,所謂匯流排鎖定就是使用C P U
提供的LOCK
#訊號,當C P U
在總線上輸出LOCK
#訊號時,其他C P U
的匯流排請求將會被阻塞。
總線鎖定方式雖然保證了原子性,但是在鎖定期間,會導致大量阻塞,增加系統的性能開銷,所以現代C P U
為了提升性能,通過鎖定範圍縮小的思想設計出了快取行鎖定(快取行是C P U
快取儲存的最小單位)。
所謂快取鎖定是指C P U
對快取行進行鎖定,當快取行中的共享變數回寫到記憶體時,其他 C P U
會透過匯流排嗅探機制感知該共享變數是否發生變化,如果發生變化,讓自己對應的共享變數快取行失效,重新從記憶體讀取最新的數據,快取鎖定是基於快取一致性機制來實現的,因為快取一致性機制會阻止兩個以上C P U
同時修改同一個共享變數(現代C P U
基本上都支援和使用快取鎖定機制) 。
C A S
和鎖定都解決了原子性問題,和鎖相比沒有阻塞、線程上下文你切換、死鎖,所以C A S
要比鎖擁有更優越的性能,但是C A S
同樣有缺點。
C A S
的問題如下
ABA
問題C A S只能針對一個共享變數使用,如果多個共享變數就只能使用鎖了,當然如果你有辦法把多個變數整成一個變量,利用
C A S也不錯,例如讀寫鎖中
state 的高低位。
#當一個執行緒取得鎖定時失敗,不進行阻塞掛起,而是間隔一段時間再次嘗試獲取,直到成功為止,這種循環獲取的機制被稱為自旋鎖(spinlock
)。
自旋鎖好處是,持有鎖的線程在短時間內釋放鎖,那些等待競爭鎖的線程就不需進入阻塞狀態(無需線程上下文切換/無需用戶態與內核態切換),它們只需要等一等(自旋),等到持有鎖的線程釋放鎖之後即可獲取,這樣就避免了用戶態和內核態的切換消耗。
自旋鎖壞處顯而易見,執行緒在長時間內持有鎖,等待競爭鎖的執行緒一直自旋,即CPU一直空轉,資源浪費在毫無意義的地方,所以一般會限制自旋次數。
最後來說自旋鎖的實現,實現自旋鎖定可以基於C A S
實現,先定義lockValue
物件預設值1
#, 1
代表鎖定資源空閒,0
代表鎖定資源被佔用,程式碼如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
上面定義了AtomicInteger
類型的lockValue
變量,AtomicInteger
是Java
基於C A S
實現的Integer
原子操作類,也定義了3個函數lock、tryLock、unLock
tryLock函數-取得鎖定
##C A S
更新lockValue
值相等,則lockValue
值更新為0
,傳回true
,否則執行下面邏輯lockValue
值不相等,不做任何更新,回傳false
unLock函數-釋放鎖定
0
,更新值1
C A S
更新lockValue
值相等,則lockValue
值更新為1
,傳回true
,否則執行下面邏輯lockValue
#值不相等,不做任何更新,返回false
lock函數-自旋取得鎖定
#tryLock
函數,傳回true
#停止,否則一直循環從上圖可以看出,只有tryLock
成功的執行緒(把lockValue
更新為0
),才會執行程式碼區塊,其他執行緒個tryLock
自旋等待lockValue
被更新成1
,tryLock
成功的線程執行unLock
(把lockValue
#更新為1
),自旋的執行緒才會tryLock
成功。
C A S
需要檢查待更新的記憶體值有沒有被修改,如果沒有則更新,但是存在這樣一種情況,如果一個值原來是A
,變成了B
,然後又變成了A
,在C A S
檢查的時候會發現沒有被修改。
假設有兩個線程,線程1
讀取到記憶體值A
,線程1
時間片用完,切換到線程2
,線程2
也讀取到了記憶體值A
,並且把它修改為B
值,然後再把B
值還原到A
值,簡單說,修改次序是A->B->A
,接著執行緒1
恢復運行,它發現記憶體值還是A
,然後執行C A S
操作,這就是著名的ABA
問題,但好像又看不出什麼問題。
只是簡單的資料結構,確實不會有什麼問題,如果是複雜的資料結構可能就會有問題了(使用AtomicReference
可以把C A S
使用在物件上),以鍊錶資料結構為例,兩個執行緒透過C A S
去刪除頭節點,假設現在鍊錶有A->B
節點
1
刪除A
節點,B
節點成為頭節點,正要執行C A S(A,A,B)
時,時間片用完,切換到執行緒2
2
刪除A、B
節點2
加入C、A
節點,鍊錶節點變成A- >C
1
重新取得時間片,執行C A S(A,A,B)
C
節點要解決A B A
問題也非常簡單,只要追加版本號即可,每次改變時加1
,即A —> B — > A
,變成1A —> 2B —> 3A
,在Java
#中提供了AtomicStampedRdference
可以實作這個方案(面試只要問了C A S
,就一定會問ABA
,這塊一定要搞清楚)。
以上是小白也能與BAT面試官對線:CAS的詳細內容。更多資訊請關注PHP中文網其他相關文章!