【面試篇】Java多執行緒并發-Java中的CAS機制演算法

Java中的CAS機制演算法

a.CAS例子

再講解CAS機制之前，先來看一道經典的并發執行1000次遞增的問題；

public class Test {
    public static int count = 0;
    public static void main(String[] args){
        // 開啟兩個執行緒
        for (int i=0;i<2;i++){
            new Thread(()->{
                try{
                    Thread.sleep(10);
                }catch (InterruptedException e){
                    e.printStackTrace();
                }
                for (int j=0;j<1000;j++){
                    count++;
                }

            }).start();
        }

        // 主執行緒休息
        try{
            Thread.sleep(2000);
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        System.out.println("count="+count);
    }
}

因為這段代碼是非執行緒安全的，所以最終的自增結果很可能會小于200，我們再加上synchronized同步鎖，再來看一下，

public class Test {
    public static int count = 0;
    public static void main(String[] args){
        // 開啟兩個執行緒
        for (int i=0;i<2;i++){
            new Thread(()->{
                try{
                    Thread.sleep(10);
                }catch (InterruptedException e){
                    e.printStackTrace();
                }
                for (int j=0;j<1000;j++){
                   synchronized (Test.class){
                       count++;
                   }
                }

            }).start();
        }

        // 主執行緒休息
        try{
            Thread.sleep(2000);
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        System.out.println("count="+count);
    }
}

synchronized關鍵字會讓沒有得到鎖資源的執行緒進入BLOCKED狀態，而后在爭奪到鎖資源后恢復為RUNNABLE狀態，這個程序中涉及到作業系統用戶模式和內核模式的轉換，代價比較高，

盡管JAVA 1.6為synchronized做了優化，增加了從偏向鎖到輕量級鎖再到重量級鎖的過過度，但是在最終轉變為重量級鎖之后，性能仍然比較低，所以面對這種情況，我們就可以使用java中的“原子操作類”，

所謂原子操作類，指的是java.util.concurrent.atomic包下，一系列以Atomic開頭的包裝類，如AtomicBoolean，AtomicUInteger，AtomicLong，它們分別用于Boolean，Integer，Long型別的原子性操作，

現在我們使用AtomicInteger類：

ublic class Test {
    public static AtomicInteger count = new AtomicInteger(0);
    public static void main(String[] args){
        // 開啟兩個執行緒
        for (int i=0;i<2;i++){
            new Thread(()->{
                try{
                    Thread.sleep(10);
                }catch (InterruptedException e){
                    e.printStackTrace();
                }
                for (int j=0;j<1000;j++){
                    count.incrementAndGet();
                }

            }).start();
        }

        // 主執行緒休息
        try{
            Thread.sleep(2000);
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        System.out.println("count="+count);
    }
}

而Atomic操作類的底層正是用到了“CAS機制”，

b.CAS概念

CAS即compare and swap（比較與交換），是一種無鎖的演算法，即不使用鎖的情況下實作多執行緒之間的變數同步，

CAS中涉及了三個要素：

• 需要讀寫的記憶體值V
• 進行比較的值A
• 擬寫入的新值B

當且僅當預期值A和記憶體值V相同時，將記憶體值修改為B，否則什么都不做，

以一個例子：

1.在記憶體地址V當中，存盤著值為10的變數，

2.此時執行緒1想要把變數的值增加1，對執行緒1來說，舊的預期值A=10，要修改的新值B=11，

3.在執行緒1要提交更新之前，另一個執行緒2搶先一步，把記憶體地址V中的變數值率先更新成了11，

4.執行緒1開始提交更新，首先進行A和地址V的實際值比較（Compare），發現A不等于V的實際值，提交失敗，

5.執行緒1重新獲取記憶體地址V的當前值，并重新計算想要修改的新值，此時對執行緒1來說，A=11，B=12，這個重新嘗試的程序被稱為自旋，

6.這一次比較幸運，沒有其他執行緒改變地址V的值，執行緒1進行Compare，發現A和地址V的實際值是相等的，

7.執行緒1進行SWAP，把地址V的值替換為B，也就是12，

c.CAS的缺點

• CPU開銷過大

  在并發量比較高的情況下，如果許多執行緒反復嘗試更新某一個變數，卻又一直更新不成功，回圈往復，會給CPU帶來很大的壓力

• 不能保證代碼塊的原子性

  CAS機制所保證的只是一個變數的原子性操作，而不能保證整個代碼塊的原子性，比如需要保證3個變數共同進行原子性的更新，就不得使用synchronized

• ABA問題

  CAS機制的最大的問題所在，

d.ABA問題

假設一個提款機的例子，假設有一個咨詢CAS原理的提款機，小灰有100元存款，要用這個提款機來提款50元，

由于提款機硬體出了點問題，小灰的提款操作被同時提交了兩次，開啟了兩個執行緒，兩個執行緒都是獲取當前值100元，要更新成50元，

理想情況下，應該一個執行緒更新成功，一個執行緒更新失敗，小灰的存款值被扣一次，

執行緒1首先執行成功，把余額從100改成50.執行緒2因為某種原因阻塞，這時，小灰的媽媽剛好給小灰匯款50元，

執行緒2仍然是阻塞狀態，執行緒3執行成功，把余額從50改成了100，

執行緒2恢復運行，由于阻塞之前獲得了“當前值”100，并且經過compare檢測，此時存款實際值也是100，所以會成功把變數值100更新成50，

原本執行緒2應當提交失敗，小灰的正確余額應該保持100元，結果由于ABA問題提交成功了，

那如何解決這個問題呢？在上述的基礎上添加個版本號即可

e.版本號機制

版本號機制是在資料表中加上一個 version 欄位來實作的，表示資料被修改的次數，當執行寫操作并且寫入成功后，version = version + 1，當執行緒A要更新資料時，在讀取資料的同時也會讀取 version 值，在提交更新時，若剛才讀取到的 version 值為當前資料庫中的version值相等時才更新，否則重試更新操作，直到更新成功，

真正要做到嚴謹的CAS機制，我們在compare階段不僅要比較期望值A和地址V中的實際值，還要比較變數的版本號是否一致，

f.CAS與synchronized的使用場景

CAS適用于寫比較少的情況下（多讀場景，沖突一般較少）；

synchronized適用于寫比較多的情況下（多寫場景，沖突一般較多）；

• 對于資源競爭較少(執行緒沖突比較輕)的情況下，使用synchronized同步鎖進行執行緒阻塞和喚醒切換以及用戶態內核態間的切換操作額外浪費消耗cpu資源；而CAS不需要進入內核，不需要切換執行緒，操作內旋幾率較少，因此可以獲得更高的性能，
• 對于資源競爭嚴重(執行緒沖突嚴重)的情況，CAS自旋的概率會比較大，從而浪費更多的CPU資源，效率低于synchronized，

補充：Java并發編程這個領域中 synchronized 關鍵字一直都是元老級的角色，很久之前很多人都會稱它為 “重量級鎖” ，但是，在JavaSE 1.6之后進行了主要包括為了減少獲得鎖和釋放鎖帶來的性能消耗而引入的 偏向鎖 和 輕量級鎖 以及其它各種優化之后變得在某些情況下并不是那么重了，synchronized 的底層實作主要依靠 Lock-Free 的佇列，基本思路是 自旋后阻塞，競爭切換后繼續競爭鎖，稍微犧牲了公平性，但獲得了高吞吐量，在執行緒沖突較少的情況下，可以獲得和 CAS 類似的性能；而執行緒沖突嚴重的情況下，性能遠高于CAS，