JAVA并發基石——CAS

引言

我們知道，鎖分為樂觀鎖，悲觀鎖

• 獨占鎖是一種悲觀鎖，而 synchronized 就是一種獨占鎖，synchronized會導致其它所有未持有鎖的執行緒阻塞，而等待持有鎖的執行緒釋放鎖，
• 所謂樂觀鎖就是，每次不加鎖而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止，而樂觀鎖用到的機制就是CAS，

下面我們來寫一段代碼

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

public class Demo {
    static int count=0;
    public  static void request() throws InterruptedException {
        TimeUnit.MICROSECONDS.sleep(5);
        count++;

    }


    public  static void main(String[] args) throws InterruptedException {
        long startIime=System.currentTimeMillis();
        int threadSize=100;
        CountDownLatch countDownLatch=new CountDownLatch(threadSize);
        for (int i=0;i<threadSize;i++){
            Thread thread=new Thread(new Runnable() {
                @Override
                public void run() {
                 try {
                     for (int j=0;j<10;j++){
                         request();
                     }
                 }catch (InterruptedException e){
                     e.printStackTrace();
                 }finally {
                     countDownLatch.countDown();
                 }
                }
            });
            thread.start();
        }
        countDownLatch.await();
        long endTime=System.currentTimeMillis();
        System.out.println(Thread.currentThread().getName()+"耗時："+(endTime-startIime+"  count:"+count));

    }
}

我們可以看到，代碼中總共有一千次的回圈，按理來說，最后的count應該是1000，但是，最后的答案卻不是1000，這是為什么呢？

其實count++ 這一行代碼一共有三步操作：

• 1.獲取count的值，記做A : A=count
• 2.將A值+1，得到B ：B=A+1
• 3.將B值賦值給count

那么，如果有A.B兩個執行緒同時執行count++,他們通知執行到上面步驟的第一步，得到的count是一樣的，3步操作結束后，count只加了1，導致count結果不正確，那么，我們是否可以在A=count這里一步把它鎖住呢？

我們來寫下一段代碼

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

public class Demo2 {
    static int count=0;
    public synchronized static void request() throws InterruptedException {
        TimeUnit.MICROSECONDS.sleep(5);
        count++;

    }


    public  static void main(String[] args) throws InterruptedException {
        long startIime=System.currentTimeMillis();
        int threadSize=100;
        CountDownLatch countDownLatch=new CountDownLatch(threadSize);
        for (int i=0;i<threadSize;i++){
            Thread thread=new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        for (int j=0;j<10;j++){
                            request();
                        }
                    }catch (InterruptedException e){
                        e.printStackTrace();
                    }finally {
                        countDownLatch.countDown();
                    }
                }
            });
            thread.start();
        }
        countDownLatch.await();
        long endTime=System.currentTimeMillis();
        System.out.println(Thread.currentThread().getName()+"耗時："+(endTime-startIime+"  count:"+count));

    }
}

在這里我們用**synchronized 修飾了方法，但是，我們發現修飾后需要的時間大大上升，這是因為被synchronized **修飾后，synchronized關鍵字會讓沒有得到鎖資源的執行緒進入BLOCKED狀態，而后在爭奪到鎖資源后恢復為RUNNABLE狀態，這個程序中涉及到作業系統用戶模式和內核模式的轉換，代價比較高，

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

我們來再寫一段代碼

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

public class Demo3 {
    static int count=0;
    public  static void request() throws InterruptedException {
        TimeUnit.MICROSECONDS.sleep(5);
        int expectCount;
        while(!compareAndSwap(expectCount=getCount(),expectCount+1)){

        }

    }

    public static synchronized boolean compareAndSwap(int expectCount,int newCount){
        if(getCount()==expectCount){
            count=newCount;
            return true;
        }
        return false;
    }
    public  static int getCount(){return count;}

    public  static void main(String[] args) throws InterruptedException {
        long startIime=System.currentTimeMillis();
        int threadSize=100;
        CountDownLatch countDownLatch=new CountDownLatch(threadSize);
        for (int i=0;i<threadSize;i++){
            Thread thread=new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        for (int j=0;j<10;j++){
                            request();
                        }
                    }catch (InterruptedException e){
                        e.printStackTrace();
                    }finally {
                        countDownLatch.countDown();
                    }
                }
            });
            thread.start();
        }
        countDownLatch.await();
        long endTime=System.currentTimeMillis();
        System.out.println(Thread.currentThread().getName()+"耗時："+(endTime-startIime+"  count:"+count));

    }
}

可以看到，這里消耗的時間很少，而且結果也是我們想要的1000

CAS機制

CAS機制全稱compare and swap，翻譯為比較并交換，是一種有名的無鎖（lock-free）演算法，也是一種現代 CPU 廣泛支持的CPU指令級的操作，只有一步原子操作，所以非常快，而且CAS避免了請求作業系統來裁定鎖的問題，直接在CPU內部就完成了，CAS機制當中使用了3個基本運算元：記憶體地址V，舊的預期值A，要修改的新值B，更新一個變數的時候，只有當變數的預期值A和記憶體地址V當中的實際值相同時，才會將記憶體地址V對應的值修改為B，這樣說或許有些抽象，我們來看一個例子：

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

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

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

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

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

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

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

CAS的缺點

1.CPU開銷較大

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

2.不能保證代碼塊的原子性

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

 因為它本身就只是一個鎖住總線的原子交換操作啊，兩個CAS操作之間并不能保證沒有重入現象，

3.ABA問題

這是CAS機制最大的問題所在，什么是ABA呢？就是A變成了B又變成了A，我們來舉個例子

假設記憶體中有一個值為A的變數，存盤在地址V當中，

此時有三個執行緒想使用CAS的方式更新這個變數值，每個執行緒的執行時間有略微的偏差，執行緒1和執行緒2已經獲得當前值，執行緒3還未獲得當前值，

接下來，執行緒1先一步執行成功，把當前值成功從A更新為B；同時執行緒2因為某種原因被阻塞住，沒有做更新操作；執行緒3在執行緒1更新之后，獲得了當前值B，

再之后，執行緒2仍然處于阻塞狀態，執行緒3繼續執行，成功把當前值從B更新成了A，

最后，執行緒2終于恢復了運行狀態，由于阻塞之前已經獲得了“當前值”A，并且經過compare檢測，記憶體地址V中的實際值也是A，所以成功把變數值A更新成了B，

這樣子看著好像也沒有什么問題，那我們用一個實際的業務來舉一個例子

• 小明的卡上有5000元，他去銀行取2000塊錢
• 這個時候因為某種故障，取錢的請求發出了兩次
• 這個時候，小明的媽媽給他寄過去2000塊錢

我們來分析一下結果

按照我們的想法，應該是第一個請求發出去，卡上就只有3000元了，這個時候另一個請求發過來，卡上變成5000元，然后被阻塞的請求失敗，卡上還有5000元，但是事實不是這樣的，結果是第三次請求又會扣除卡里2000元，這樣，就出現了一個很大的問題，

如何應對ABA問題

其實也不是什么很難的問題，我們加一個版本號就行了，我們仍然以最初的例子來說明一下，假設地址V中存盤著變數值A，當前版本號是01，執行緒1獲得了當前值A和版本號01，想要更新為B，但是被阻塞了，

這時候，記憶體地址V中的變數發生了多次改變，版本號提升為03，但是變數值仍然是A，

隨后執行緒1恢復運行，進行Compare操作，經過比較，執行緒1所獲得的值和地址V的實際值都是A，但是版本號不相等，所以這一次更新失敗，

在Java當中，AtomicStampedReference類就實作了用版本號做比較的CAS機制，