1、什么是CAS？

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

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

2、CAS算法理解

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

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

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

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

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

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

（上圖通俗的解釋是：CPU去更新一個(gè)值，但如果想改的值不再是原來的值，操作就失敗，因?yàn)楹苊黠@，有其它操作先改變了這個(gè)值。）

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

3、CAS開銷

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

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

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

• CPU0 檢查本地高速緩存，沒有找到緩存線。
• 請(qǐng)求被轉(zhuǎn)發(fā)到 CPU0 和 CPU1 的互聯(lián)模塊，檢查 CPU1 的本地高速緩存，沒有找到緩存線。
• 請(qǐng)求被轉(zhuǎn)發(fā)到系統(tǒng)互聯(lián)模塊，檢查其他三個(gè)管芯，得知緩存線被 CPU6和 CPU7 所在的管芯持有。
• 請(qǐng)求被轉(zhuǎn)發(fā)到 CPU6 和 CPU7 的互聯(lián)模塊，檢查這兩個(gè) 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)在可以對(duì)高速緩存中的變量執(zhí)行 CAS 操作了

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

以下是cache miss cas 和lock的性能對(duì)比：

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

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

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

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

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

最新評(píng)論