1斤寇、什么是CAS感论？
CAS：Compare and Swap焚鲜，即比較再交換。
jdk5增加了并發(fā)包java.util.concurrent.*,其下面的類(lèi)使用CAS算法實(shí)現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂(lè)觀鎖幸撕。JDK 5之前Java語(yǔ)言是靠synchronized關(guān)鍵字保證同步的薇组，這是一種獨(dú)占鎖，也是是悲觀鎖坐儿。
2律胀、CAS算法理解
對(duì)CAS的理解，CAS是一種無(wú)鎖算法貌矿，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線(xiàn)程是同時(shí)更新同一變量56的值
因?yàn)閠1和t2線(xiàn)程都同時(shí)去訪(fǎng)問(wèn)同一變量56停团，所以他們會(huì)把主內(nèi)存的值完全拷貝一份到自己的工作內(nèi)存空間，所以t1和t2線(xiàn)程的預(yù)期值都為56掏熬。
假設(shè)t1在與t2線(xiàn)程競(jìng)爭(zhēng)中線(xiàn)程t1能去更新變量的值佑稠，而其他線(xiàn)程都失敗。（失敗的線(xiàn)程并不會(huì)被掛起旗芬，而是被告知這次競(jìng)爭(zhēng)中失敗舌胶，并可以再次發(fā)起嘗試）。t1線(xiàn)程去更新變量值改為57疮丛，然后寫(xiě)到內(nèi)存中幔嫂。此時(shí)對(duì)于t2來(lái)說(shuō)漱办，內(nèi)存值變?yōu)榱?7，與預(yù)期值56不一致婉烟，就操作失敗了（想改的值不再是原來(lái)的值）。
（上圖通俗的解釋是：CPU去更新一個(gè)值暇屋，但如果想改的值不再是原來(lái)的值似袁，操作就失敗，因?yàn)楹苊黠@咐刨，有其它操作先改變了這個(gè)值昙衅。）
就是指當(dāng)兩者進(jìn)行比較時(shí)，如果相等定鸟，則證明共享數(shù)據(jù)沒(méi)有被修改而涉，替換成新值，然后繼續(xù)往下運(yùn)行联予；如果不相等啼县，說(shuō)明共享數(shù)據(jù)已經(jīng)被修改，放棄已經(jīng)所做的操作沸久，然后重新執(zhí)行剛才的操作季眷。容易看出 CAS 操作是基于共享數(shù)據(jù)不會(huì)被修改的假設(shè)，采用了類(lèi)似于數(shù)據(jù)庫(kù)的commit-retry 的模式卷胯。當(dāng)同步?jīng)_突出現(xiàn)的機(jī)會(huì)很少時(shí)子刮，這種假設(shè)能帶來(lái)較大的性能提升。
3窑睁、CAS開(kāi)銷(xiāo)
前面說(shuō)過(guò)了挺峡，CAS（比較并交換）是CPU指令級(jí)的操作，只有一步原子操作担钮，所以非吵髟快。而且CAS避免了請(qǐng)求操作系統(tǒng)來(lái)裁定鎖的問(wèn)題裳朋，不用麻煩操作系統(tǒng)病线，直接在CPU內(nèi)部就搞定了。但CAS就沒(méi)有開(kāi)銷(xiāo)了嗎鲤嫡？不送挑！有cache miss的情況。這個(gè)問(wèn)題比較復(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è)管芯相互通信，并且將管芯與主存連接起來(lái)挤安。數(shù)據(jù)以“緩存線(xiàn)”為單位在系統(tǒng)中傳輸谚殊，“緩存線(xiàn)”對(duì)應(yīng)于內(nèi)存中一個(gè) 2 的冪大小的字節(jié)塊，大小通常為 32 到 256 字節(jié)之間蛤铜。當(dāng) CPU 從內(nèi)存中讀取一個(gè)變量到它的寄存器中時(shí)嫩絮，必須首先將包含了該變量的緩存線(xiàn)讀取到 CPU 高速緩存。同樣地围肥，CPU 將寄存器中的一個(gè)值存儲(chǔ)到內(nèi)存時(shí)剿干，不僅必須將包含了該值的緩存線(xiàn)讀到 CPU 高速緩存，還必須確保沒(méi)有其他 CPU 擁有該緩存線(xiàn)的拷貝穆刻。
比如置尔，如果 CPU0 在對(duì)一個(gè)變量執(zhí)行“比較并交換”（CAS）操作，而該變量所在的緩存線(xiàn)在 CPU7 的高速緩存中氢伟，就會(huì)發(fā)生以下經(jīng)過(guò)簡(jiǎn)化的事件序列：
CPU0 檢查本地高速緩存榜轿，沒(méi)有找到緩存線(xiàn)。
請(qǐng)求被轉(zhuǎn)發(fā)到 CPU0 和 CPU1 的互聯(lián)模塊朵锣，檢查 CPU1 的本地高速緩存差导，沒(méi)有找到緩存線(xiàn)。
請(qǐng)求被轉(zhuǎn)發(fā)到系統(tǒng)互聯(lián)模塊猪勇，檢查其他三個(gè)管芯设褐，得知緩存線(xiàn)被 CPU6和 CPU7 所在的管芯持有。
請(qǐng)求被轉(zhuǎn)發(fā)到 CPU6 和 CPU7 的互聯(lián)模塊泣刹，檢查這兩個(gè) CPU 的高速緩存助析，在 CPU7 的高速緩存中找到緩存線(xiàn)。
CPU7 將緩存線(xiàn)發(fā)送給所屬的互聯(lián)模塊椅您，并且刷新自己高速緩存中的緩存線(xiàn)外冀。
CPU6 和 CPU7 的互聯(lián)模塊將緩存線(xiàn)發(fā)送給系統(tǒng)互聯(lián)模塊。
系統(tǒng)互聯(lián)模塊將緩存線(xiàn)發(fā)送給 CPU0 和 CPU1 的互聯(lián)模塊掀泳。
CPU0 和 CPU1 的互聯(lián)模塊將緩存線(xiàn)發(fā)送給 CPU0 的高速緩存雪隧。
CPU0 現(xiàn)在可以對(duì)高速緩存中的變量執(zhí)行 CAS 操作了
以上是刷新不同CPU緩存的開(kāi)銷(xiāo)。最好情況下的 CAS 操作消耗大概 40 納秒员舵，超過(guò) 60 個(gè)時(shí)鐘周期脑沿。這里的“最好情況”是指對(duì)某一個(gè)變量執(zhí)行 CAS 操作的 CPU 正好是最后一個(gè)操作該變量的CPU，所以對(duì)應(yīng)的緩存線(xiàn)已經(jīng)在 CPU 的高速緩存中了马僻，類(lèi)似地庄拇，最好情況下的鎖操作（一個(gè)“round trip 對(duì)”包括獲取鎖和隨后的釋放鎖）消耗超過(guò) 60 納秒，超過(guò) 100 個(gè)時(shí)鐘周期。這里的“最好情況”意味著用于表示鎖的數(shù)據(jù)結(jié)構(gòu)已經(jīng)在獲取和釋放鎖的 CPU 所屬的高速緩存中了措近。鎖操作比 CAS 操作更加耗時(shí)溶弟，是因深入理解并行編程
為鎖操作的數(shù)據(jù)結(jié)構(gòu)中需要兩個(gè)原子操作。緩存未命中消耗大概 140 納秒瞭郑，超過(guò) 200 個(gè)時(shí)鐘周期辜御。需要在存儲(chǔ)新值時(shí)查詢(xún)變量的舊值的 CAS 操作，消耗大概 300 納秒屈张，超過(guò) 500 個(gè)時(shí)鐘周期我抠。想想這個(gè)，在執(zhí)行一次 CAS 操作的時(shí)間里袜茧，CPU 可以執(zhí)行 500 條普通指令。這表明了細(xì)粒度鎖的局限性瓣窄。
以下是cache miss cas 和lock的性能對(duì)比：
4笛厦、CAS算法在JDK中的應(yīng)用
在原子類(lèi)變量中，如java.util.concurrent.atomic中的AtomicXXX俺夕，都使用了這些底層的JVM支持為數(shù)字類(lèi)型的引用類(lèi)型提供一種高效的CAS操作裳凸，而在java.util.concurrent中的大多數(shù)類(lèi)在實(shí)現(xiàn)時(shí)都直接或間接的使用了這些原子變量類(lèi)。
Java 1.7中AtomicInteger.incrementAndGet()的實(shí)現(xiàn)源碼為：
由此可見(jiàn)劝贸，AtomicInteger.incrementAndGet的實(shí)現(xiàn)用了樂(lè)觀鎖技術(shù)姨谷，調(diào)用了類(lèi)sun.misc.Unsafe庫(kù)里面的 CAS算法，用CPU指令來(lái)實(shí)現(xiàn)無(wú)鎖自增映九。所以梦湘，AtomicInteger.incrementAndGet的自增比用synchronized的鎖效率倍增。
