首頁 > Java > Java面試題 > 小白也能與BAT面試官對線:CAS

小白也能與BAT面試官對線:CAS

發布: 2023-08-24 15:09:21
轉載
1669 人瀏覽過

前言

Java並發程式設計系列番外篇C A S(Compare and swap),文章風格依然是圖文並茂,通俗易懂,讓讀者也能與面試官瘋狂對線。

C A S作為並發程式設計必不可少的基礎知識,面試時C A S也是個高頻考點,所以說C A S是必知必會,本文將帶讀者們深入理解C A S

大綱

小白也能與BAT面試官對線:CAS

#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的運算。

小白也能與BAT面試官對線:CAS

簡單地說,C A S需要你額外給出一個期望值,也就是你認為這個變數現在應該是什麼樣子的,如果變數不是你想像的那樣,說明它已經被別人修改過了,你只需要重新讀取,設定新期望值,再次嘗試修改就好了。

C A S如何保證原子性

原子性是指一個或多個運算在C P U執行的過程中不被中斷的特性,要麼執行,要不執行,不能執行到一半(不可被中斷的一個或一系列操作)。

為了保證C A S的原子性,C P U提供了下面兩種方式

  • 匯流排鎖定
  • 快取鎖定

#總線鎖定

匯流排(B U S)是電腦元件間的傳輸資料方式,也就是說C P U與其他元件連接傳輸數據,就是靠總線完成的,例如C P U對記憶體的讀寫。

小白也能與BAT面試官對線:CAS

總線鎖定是指C P U使用了匯流排鎖,所謂匯流排鎖定就是使用C P U提供的LOCK#訊號,當C P U在總線上輸出LOCK#訊號時,其他C P U的匯流排請求將會被阻塞。

小白也能與BAT面試官對線:CAS

快取鎖定

總線鎖定方式雖然保證了原子性,但是在鎖定期間,會導致大量阻塞,增加系統的性能開銷,所以現代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同樣有缺點。

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

public class SpinLock {

     

    //lockValue 默认值1

    private AtomicInteger lockValue = new AtomicInteger(1);

     

    //自旋获取锁

    public void lock(){

 

        // 循环检测尝试获取锁

        while (!tryLock()){

            // 空转

        }

 

    }

     

    //获取锁

    public boolean tryLock(){

        // 期望值1,更新值0,更新成功返回true,更新失败返回false

        return lockValue.compareAndSet(1,0);

    }

     

    //释放锁

    public void unLock(){

        if(!lockValue.compareAndSet(1,0)){

            throw new RuntimeException("释放锁失败");

        }

    }

 

}

登入後複製

上面定義了AtomicInteger類型的lockValue變量,AtomicIntegerJava基於C A S實現的Integer原子操作類,也定義了3個函數lock、tryLock、unLock

tryLock函數-取得鎖定

#
  • 期望值1,更新值0
  • #C A S更新
  • 如果期望值與lockValue值相等,則lockValue值更新為0,傳回true,否則執行下面邏輯
  • 如果期望值與lockValue值不相等,不做任何更新,回傳false

unLock函數-釋放鎖定

  • 期望值0,更新值1
  • C A S更新
  • 如果期望值與lockValue值相等,則lockValue值更新為1,傳回true,否則執行下面邏輯
  • #如果期望值與lockValue#值不相等,不做任何更新,返回false

lock函數-自旋取得鎖定

#
  • 執行tryLock函數,傳回true#停止,否則一直循環
小白也能與BAT面試官對線:CAS

從上圖可以看出,只有tryLock成功的執行緒(lockValue更新為0),才會執行程式碼區塊,其他執行緒個tryLock自旋等待lockValue被更新成1tryLock成功的線程執行unLocklockValue#更新為1),自旋的執行緒才會tryLock成功。

ABA問題

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節點

小白也能與BAT面試官對線:CAS
  • 線程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中文網其他相關文章!

相關標籤:
來源:Java后端技术全栈
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板