1、什么是CAS？

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

jdk5增加了并發(fā)包java.util.concurrent.*,其下面的類使用CAS算法實現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂觀鎖。JDK 5之前Java語言是靠synchronized關(guān)鍵字保證同步的，這是一種獨占鎖，也是是悲觀鎖。

2、CAS算法理解

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

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

do{
       備份舊數(shù)據(jù)；
       基于舊數(shù)據(jù)構(gòu)造新數(shù)據(jù)；
}while(!CAS( 內(nèi)存地址，備份的舊數(shù)據(jù)，新數(shù)據(jù) ))

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

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

假設(shè)t1在與t2線程競爭中線程t1能去更新變量的值，而其他線程都失敗。（失敗的線程并不會被掛起，而是被告知這次競爭中失敗，并可以再次發(fā)起嘗試）。t1線程去更新變量值改為57，然后寫到內(nèi)存中。此時對于t2來說，內(nèi)存值變?yōu)榱?7，與預(yù)期值56不一致，就操作失敗了（想改的值不再是原來的值）。

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

就是指當兩者進行比較時，如果相等，則證明共享數(shù)據(jù)沒有被修改，替換成新值，然后繼續(xù)往下運行；如果不相等，說明共享數(shù)據(jù)已經(jīng)被修改，放棄已經(jīng)所做的操作，然后重新執(zhí)行剛才的操作。容易看出 CAS 操作是基于共享數(shù)據(jù)不會被修改的假設(shè)，采用了類似于數(shù)據(jù)庫的commit-retry 的模式。當同步?jīng)_突出現(xiàn)的機會很少時，這種假設(shè)能帶來較大的性能提升。

3、CAS開銷

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

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

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

• CPU0 檢查本地高速緩存，沒有找到緩存線。
• 請求被轉(zhuǎn)發(fā)到 CPU0 和 CPU1 的互聯(lián)模塊，檢查 CPU1 的本地高速緩存，沒有找到緩存線。
• 請求被轉(zhuǎn)發(fā)到系統(tǒng)互聯(lián)模塊，檢查其他三個管芯，得知緩存線被 CPU6和 CPU7 所在的管芯持有。
• 請求被轉(zhuǎn)發(fā)到 CPU6 和 CPU7 的互聯(lián)模塊，檢查這兩個 CPU 的高速緩存，在 CPU7 的高速緩存中找到緩存線。
• CPU7 將緩存線發(fā)送給所屬的互聯(lián)模塊，并且刷新自己高速緩存中的緩存線。
• CPU6 和 CPU7 的互聯(lián)模塊將緩存線發(fā)送給系統(tǒng)互聯(lián)模塊。
• 系統(tǒng)互聯(lián)模塊將緩存線發(fā)送給 CPU0 和 CPU1 的互聯(lián)模塊。
• CPU0 和 CPU1 的互聯(lián)模塊將緩存線發(fā)送給 CPU0 的高速緩存。
• CPU0 現(xiàn)在可以對高速緩存中的變量執(zhí)行 CAS 操作了

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

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

4、CAS算法在JDK中的應(yīng)用

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

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

由此可見，AtomicInteger.incrementAndGet的實現(xiàn)用了樂觀鎖技術(shù)，調(diào)用了類sun.misc.Unsafe庫里面的 CAS算法，用CPU指令來實現(xiàn)無鎖自增。所以，AtomicInteger.incrementAndGet的自增比用synchronized的鎖效率倍增。

以上就是深入理解 CAS 算法原理已經(jīng)在jdk中的運用的詳細內(nèi)容，更多關(guān)于CAS 算法原理的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論