深入理解 CAS 算法原理已經在jdk中的運用

Posted on by

1、什麼是CAS？

CAS：Compare and Swap，即比較再交換。

jdk5增加瞭並發包java.util.concurrent.*,其下面的類使用CAS算法實現瞭區別於synchronouse同步鎖的一種樂觀鎖。JDK 5之前Java語言是靠synchronized關鍵字保證同步的，這是一種獨占鎖，也是是悲觀鎖。

2、CAS算法理解

對CAS的理解，CAS是一種無鎖算法，CAS有3個操作數，內存值V，舊的預期值A，要修改的新值B。當且僅當預期值A和內存值V相同時，將內存值V修改為B，否則什麼都不做。

CAS比較與交換的偽代碼可以表示為：

do{
       備份舊數據；
       基於舊數據構造新數據；
}while(!CAS( 內存地址，備份的舊數據，新數據 ))

註：t1，t2線程是同時更新同一變量56的值

因為t1和t2線程都同時去訪問同一變量56，所以他們會把主內存的值完全拷貝一份到自己的工作內存空間，所以t1和t2線程的預期值都為56。

假設t1在與t2線程競爭中線程t1能去更新變量的值，而其他線程都失敗。（失敗的線程並不會被掛起，而是被告知這次競爭中失敗，並可以再次發起嘗試）。t1線程去更新變量值改為57，然後寫到內存中。此時對於t2來說，內存值變為瞭57，與預期值56不一致，就操作失敗瞭（想改的值不再是原來的值）。

（上圖通俗的解釋是：CPU去更新一個值，但如果想改的值不再是原來的值，操作就失敗，因為很明顯，有其它操作先改變瞭這個值。）

就是指當兩者進行比較時，如果相等，則證明共享數據沒有被修改，替換成新值，然後繼續往下運行；如果不相等，說明共享數據已經被修改，放棄已經所做的操作，然後重新執行剛才的操作。容易看出 CAS 操作是基於共享數據不會被修改的假設，采用瞭類似於數據庫的commit-retry 的模式。當同步沖突出現的機會很少時，這種假設能帶來較大的性能提升。

3、CAS開銷

前面說過瞭，CAS（比較並交換）是CPU指令級的操作，隻有一步原子操作，所以非常快。而且CAS避免瞭請求操作系統來裁定鎖的問題，不用麻煩操作系統，直接在CPU內部就搞定瞭。但CAS就沒有開銷瞭嗎？不！有cache miss的情況。這個問題比較復雜，首先需要瞭解CPU的硬件體系結構：

上圖可以看到一個8核CPU計算機系統，每個CPU有cache（CPU內部的高速緩存，寄存器），管芯內還帶有一個互聯模塊，使管芯內的兩個核可以互相通信。在圖中央的系統互聯模塊可以讓四個管芯相互通信，並且將管芯與主存連接起來。數據以“緩存線”為單位在系統中傳輸，“緩存線”對應於內存中一個 2 的冪大小的字節塊，大小通常為 32 到 256 字節之間。當 CPU 從內存中讀取一個變量到它的寄存器中時，必須首先將包含瞭該變量的緩存線讀取到 CPU 高速緩存。同樣地，CPU 將寄存器中的一個值存儲到內存時，不僅必須將包含瞭該值的緩存線讀到 CPU 高速緩存，還必須確保沒有其他 CPU 擁有該緩存線的拷貝。

比如，如果 CPU0 在對一個變量執行“比較並交換”（CAS）操作，而該變量所在的緩存線在 CPU7 的高速緩存中，就會發生以下經過簡化的事件序列：

  • CPU0 檢查本地高速緩存，沒有找到緩存線。
  • 請求被轉發到 CPU0 和 CPU1 的互聯模塊，檢查 CPU1 的本地高速緩存，沒有找到緩存線。
  • 請求被轉發到系統互聯模塊，檢查其他三個管芯，得知緩存線被 CPU6和 CPU7 所在的管芯持有。
  • 請求被轉發到 CPU6 和 CPU7 的互聯模塊，檢查這兩個 CPU 的高速緩存，在 CPU7 的高速緩存中找到緩存線。
  • CPU7 將緩存線發送給所屬的互聯模塊，並且刷新自己高速緩存中的緩存線。
  • CPU6 和 CPU7 的互聯模塊將緩存線發送給系統互聯模塊。
  • 系統互聯模塊將緩存線發送給 CPU0 和 CPU1 的互聯模塊。
  • CPU0 和 CPU1 的互聯模塊將緩存線發送給 CPU0 的高速緩存。
  • CPU0 現在可以對高速緩存中的變量執行 CAS 操作瞭

以上是刷新不同CPU緩存的開銷。最好情況下的 CAS 操作消耗大概 40 納秒，超過 60 個時鐘周期。這裡的“最好情況”是指對某一個變量執行 CAS 操作的 CPU 正好是最後一個操作該變量的CPU，所以對應的緩存線已經在 CPU 的高速緩存中瞭，類似地，最好情況下的鎖操作（一個“round trip 對”包括獲取鎖和隨後的釋放鎖）消耗超過 60 納秒，超過 100 個時鐘周期。這裡的“最好情況”意味著用於表示鎖的數據結構已經在獲取和釋放鎖的 CPU 所屬的高速緩存中瞭。鎖操作比 CAS 操作更加耗時，是因深入理解並行編程
為鎖操作的數據結構中需要兩個原子操作。緩存未命中消耗大概 140 納秒，超過 200 個時鐘周期。需要在存儲新值時查詢變量的舊值的 CAS 操作，消耗大概 300 納秒，超過 500 個時鐘周期。想想這個，在執行一次 CAS 操作的時間裡，CPU 可以執行 500 條普通指令。這表明瞭細粒度鎖的局限性。

以下是cache miss cas 和lock的性能對比：

4、CAS算法在JDK中的應用

在原子類變量中，如java.util.concurrent.atomic中的AtomicXXX，都使用瞭這些底層的JVM支持為數字類型的引用類型提供一種高效的CAS操作，而在java.util.concurrent中的大多數類在實現時都直接或間接的使用瞭這些原子變量類。

Java 1.7中AtomicInteger.incrementAndGet()的實現源碼為：

由此可見，AtomicInteger.incrementAndGet的實現用瞭樂觀鎖技術，調用瞭類sun.misc.Unsafe庫裡面的 CAS算法，用CPU指令來實現無鎖自增。所以，AtomicInteger.incrementAndGet的自增比用synchronized的鎖效率倍增。

以上就是深入理解 CAS 算法原理已經在jdk中的運用的詳細內容，更多關於CAS 算法原理的資料請關註WalkonNet其它相關文章！

推薦閱讀：