淺探CAS(Compare And Swap)實現原理

作者：java小當家 2021-01-15 07:41:24

CAS，全稱是Compare And Swap，即比較并交換，是一種樂觀鎖的實現。

前言

CAS，全稱是Compare And Swap，即比較并交換，是一種樂觀鎖的實現。

悲觀鎖與樂觀鎖

悲觀鎖

總是假設最壞的情況，線程a每次去獲取或更新數據的時候，都會覺得別的線程也正在修改這個數據，為了避免自己的更新操作丟失，線程a會嘗試獲取此數據的鎖，線程a獲取到之后，才能對此數據進行一些更新操作。在此期間，別的線程無法更新，只能等到線程a釋放鎖之后，才能進行更新。

之所以叫做悲觀鎖，是因為這是一種對數據的修改抱有悲觀態度的并發控制方式。我們一般認為數據被并發修改的概率比較大，所以需要在修改之前先加鎖。

悲觀并發控制，實際上是一種“先取鎖再訪問”的保守策略。

synchronized就是對悲觀鎖的一種實現。

樂觀鎖

樂觀鎖假設數據一般不會造成沖突，所以在拿數據的時候不會去加鎖，但是會在更新的時候判斷此期間內有沒有別的線程修改過數據。

CAS機制就是對樂觀鎖的一種實現。

樂觀鎖的實現——CAS

CAS操作一般包含3個參數，期望值、內存值、新值。如果期望值與內存值相等，則用新值去更新這個內存值。如果不相等，則可以再次進行比較，一直到成功為止。

CAS是一種非阻塞的算法，線程在更新失敗時，不需要掛起，因此省去了大量線程上下文切換的開銷。

java使用Unsafe類來支持CAS操作，對Unsafe類不了解的同學可以先參考我的另外一篇文章JUC基石——Unsafe類。

我們用java代碼來簡要模擬CAS的過程：

/** 
    * @param expect 期望值 
    * @param update 新值 
    * @return 
    */ 
   public int cas(int expect, int update) { 
       //更新失敗就一直進行忙循環 
       while (true) { 
           //get方法從內存中獲取最新的值 
           int memory = get(); 
           if (memory == expect) { 
               //set方法將內存中的值設置為新值 
               set(update); 
               return update; 
           } 
       } 
   }

當然這只是一個模擬，實際cas操作將會用到底層的系統指令，這些指令將會保證整個cas操作具有原子性，關于這些指令，可能要另開篇幅講解。

悲觀鎖的實現——synchronized

synchronized是悲觀鎖的典型實現，有關它的用法，可以參考我的這篇文章淺說Synchronized，早期的synchronized十分笨重，所幸在1.6之后進行了大量的優化，鎖性能提升了很多，關于synchronized的優化，可以參考我的這篇文章Synchronized的優化。

CAS的缺陷——ABA問題

假設有這樣的一種情況，x的內存值首先是A，線程1讀取到了A，之后忙別的事情了，該值在之后被線程2改成了B，接著又被線程3改成了A，線程1此時進行CAS操作，發現內存值還是A，于是進行了更新操作。但是這個A已經不是原來的A了，或者說不是之前那個版本的A了。

解決這種缺陷，可以使用帶版本號或時間戳的CAS，A值每次被更新后，版本號加1，或者更新時間戳。此時內存值與期望值相等，但卻不是線程期望的版本號。

此時的A→B→A，就變成了A(version=1)→B(version=2)→A(version=3)。當使用帶版本號的CAS后，就可以避免ABA問題。

CAS與synchronized適用場景

線程沖突比較小時，CAS進行自旋操作，synchronized升級為輕量級鎖，也是在自旋，兩者的效率差不多。

線程沖突嚴重時，CAS絕大部分的自旋操作將大量浪費CPU的時間片，此時synchronized升級為重量級鎖，但在這種情況下，synchronized的效率遠高于CAS。(因為在線程沖突嚴重時，synchronized已經意識到輕量級鎖的自旋操作效率低下，主動升級為重量級鎖，所以這里的忙循環的開銷遠遠大于線程切換的開銷)。

JAVA中的CAS操作

AtomicInteger實現了CAS，可以原子性地更新一個int類型數據，其實底層也是調用Unsafe類。但是如果要一次原子性地更新多個變量，可以使用AtomicReference，當然這個存在上述的ABA問題，這時可以使用帶版本號機制的CAS實現類——AtomicStampedReference，該類使用了一個stamp字段來表示版本號，代碼如下圖所示：

數據庫中的CAS操作

數據庫中的樂觀鎖機制不需要借助表鎖、行鎖等，以修改庫存為例，樂觀鎖實現如下：

update goods set quantity=99 where id=1 and quantity = 100;

這個情景比較簡單，暫不考慮ABA問題。

以上SQL其實還是有一定的問題的，就是一旦高并發的時候，就只有一個線程可以修改成功，那么就會存在大量的失敗。所以，需要減小樂觀鎖的粒度。

有一條比較好的建議，可以減小樂觀鎖力度，最大程度的提升吞吐率，提高并發能力!如下：

update goods set quantity=quantity - 1 where id = 1 and quantity - 1 > 0

將quantity=100轉化成了quantity - 1 > 0，大大減少了樂觀鎖的力度，效率得到很大的提升。

JVM中的CAS操作

Java調用new object()會創建一個對象，這個對象會被分配到JVM的堆中。那么這個對象到底是怎么在堆中保存的呢?

首先，new object()執行的時候，這個對象需要多大的空間，其實是已經確定的，因為java中的各種數據類型，占用多大的空間都是固定的。怎么去確定對象大小，可以參考我的這篇文章對象的內存布局，怎樣確定對象的大小。那么接下來的工作就是在堆中找出那么一塊空間用于存放這個對象。

在單線程的情況下，一般有兩種分配策略：

指針碰撞：這種一般適用于內存是絕對規整的(內存是否規整取決于內存回收策略)。用過的內存放在一邊，空閑的內內存放在另外一邊，之間有一個分界指針，分配空間的工作只是將分界指針向空閑內存一側移動對象大小的距離即可。
空閑列表：這種適用于內存非規整的情況，這種情況下JVM會維護一個內存列表，記錄哪些內存區域是空閑的，大小是多少。給對象分配空間的時候去空閑列表里查詢到合適的區域然后進行分配即可。

然而，對象的創建工作是很頻繁的，為了保證效率，JVM可以并發地給對象分配內存空間。由于分配內存的時候不是原子性的操作，至少需要以下幾步：查找空閑列表、分配內存、修改空閑列表等等，這是不安全的。解決并發時的安全問題也有兩種策略：

CAS：實際上虛擬機采用CAS配合上失敗重試的方式保證更新操作的原子性，原理和上面講的一樣。
TLAB：如果使用CAS其實對性能還是會有影響的，所以JVM又提出了一種更高級的優化策略：每個線程在Java堆中預先分配一小塊內存，稱為本地線程分配緩沖區(TLAB)，線程內部需要分配內存時直接在TLAB上分配就行，避免了線程沖突。只有當緩沖區的內存用光需要重新分配內存的時候才會進行CAS操作分配更大的內存空間。虛擬機是否使用TLAB，可以通過-XX:+/-UseTLAB參數來進行配置(jdk5及以后的版本默認是啟用TLAB的)。

責任編輯：姜華來源：今日頭條