概述

CAS（Compare-and-Swap），即比較并替換，是一種實現(xiàn)并發(fā)算法時常用到的技術(shù)，Java并發(fā)包中的很多類都使用了CAS技術(shù)。CAS也是現(xiàn)在面試經(jīng)常問的問題，本文將深入的介紹CAS的原理。

案例

介紹CAS之前，我們先來看一個例子。

上面這個例子在volatile關(guān)鍵字詳解文中用過，我們知道，運行完這段代碼之后，并不會獲得期望的結(jié)果，而且會發(fā)現(xiàn)每次運行程序，輸出的結(jié)果都不一樣，都是一個小于200000的數(shù)字。

通過分析字節(jié)碼我們知道，這是因為volatile只能保證可見性，無法保證原子性，而自增操作并不是一個原子操作（如下圖所示），在并發(fā)的情況下，putstatic指令可能把較小的race值同步回主內(nèi)存之中，導(dǎo)致我們每次都無法獲得想要的結(jié)果。那么，應(yīng)該怎么解決這個問題了？

解決方法：

首先我們想到的是用synchronized來修飾increase方法。

使用synchronized修飾后，increase方法變成了一個原子操作，因此是肯定能得到正確的結(jié)果。但是，我們知道，每次自增都進行加鎖，性能可能會稍微差了點，有更好的方案嗎？

答案當然是有的，這個時候我們可以使用Java并發(fā)包原子操作類（Atomic開頭），例如以下代碼。

我們將例子中的代碼稍做修改：race改成使用AtomicInteger定義，“race++”改成使用“race.getAndIncrement()”，AtomicInteger.getAndIncrement()是原子操作，因此我們可以確保每次都可以獲得正確的結(jié)果，并且在性能上有不錯的提升（針對本例子，在JDK1.8.0_151下運行）。

通過方法調(diào)用，我們可以發(fā)現(xiàn)，getAndIncrement方法調(diào)用getAndAddInt方法，最后調(diào)用的是compareAndSwapInt方法，即本文的主角CAS，接下來我們開始介紹CAS。

getAndAddInt方法解析：拿到內(nèi)存位置的最新值v，使用CAS嘗試修將內(nèi)存位置的值修改為目標值v+delta，如果修改失敗，則獲取該內(nèi)存位置的新值v，然后繼續(xù)嘗試，直至修改成功。

CAS是什么？

CAS是英文單詞CompareAndSwap的縮寫，中文意思是：比較并替換。CAS需要有3個操作數(shù)：內(nèi)存地址V，舊的預(yù)期值A(chǔ)，即將要更新的目標值B。

CAS指令執(zhí)行時，當且僅當內(nèi)存地址V的值與預(yù)期值A(chǔ)相等時，將內(nèi)存地址V的值修改為B，否則就什么都不做。整個比較并替換的操作是一個原子操作。

源碼分析

上面源碼分析時，提到最后調(diào)用了compareAndSwapInt方法，接著繼續(xù)深入探討該方法，該方法在Unsafe中對應(yīng)的源碼如下。

可以看到調(diào)用了“Atomic::cmpxchg”方法，“Atomic::cmpxchg”方法在linux_x86和windows_x86的實現(xiàn)如下。

linux_x86的實現(xiàn)：

windows_x86的實現(xiàn)：

Atomic::cmpxchg方法解析：

mp是“os::is_MP()”的返回結(jié)果，“os::is_MP()”是一個內(nèi)聯(lián)函數(shù)，用來判斷當前系統(tǒng)是否為多處理器。

如果當前系統(tǒng)是多處理器，該函數(shù)返回1。

否則，返回0。

LOCK_IF_MP(mp)會根據(jù)mp的值來決定是否為cmpxchg指令添加lock前綴。

如果通過mp判斷當前系統(tǒng)是多處理器（即mp值為1），則為cmpxchg指令添加lock前綴。

否則，不加lock前綴。

這是一種優(yōu)化手段，認為單處理器的環(huán)境沒有必要添加lock前綴，只有在多核情況下才會添加lock前綴，因為lock會導(dǎo)致性能下降。cmpxchg是匯編指令，作用是比較并交換操作數(shù)。

intel手冊對lock前綴的說明如下：

確保對內(nèi)存的讀-改-寫操作原子執(zhí)行。在Pentium及Pentium之前的處理器中，帶有l(wèi)ock前綴的指令在執(zhí)行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內(nèi)存。很顯然，這會帶來昂貴的開銷。從Pentium 4，Intel Xeon及P6處理器開始，intel在原有總線鎖的基礎(chǔ)上做了一個很有意義的優(yōu)化：如果要訪問的內(nèi)存區(qū)域（area of memory）在lock前綴指令執(zhí)行期間已經(jīng)在處理器內(nèi)部的緩存中被鎖定（即包含該內(nèi)存區(qū)域的緩存行當前處于獨占或以修改狀態(tài)），并且該內(nèi)存區(qū)域被完全包含在單個緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會一直被鎖定，其它處理器無法讀/寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷，但是當多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時，仍然會鎖住總線。

禁止該指令與之前和之后的讀和寫指令重排序。

把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

上面的第1點保證了CAS操作是一個原子操作，第2點和第3點所具有的內(nèi)存屏障效果，保證了CAS同時具有volatile讀和volatile寫的內(nèi)存語義。

CAS的缺點

CAS雖然很高效的解決了原子操作問題，但是CAS仍然存在三大問題。

循環(huán)時間長開銷很大。

只能保證一個共享變量的原子操作。

ABA問題。

循環(huán)時間長開銷很大：我們可以看到getAndAddInt方法執(zhí)行時，如果CAS失敗，會一直進行嘗試。如果CAS長時間一直不成功，可能會給CPU帶來很大的開銷。

只能保證一個共享變量的原子操作：當對一個共享變量執(zhí)行操作時，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對多個共享變量操作時，循環(huán)CAS就無法保證操作的原子性，這個時候就可以用鎖來保證原子性。

什么是ABA問題？ABA問題怎么解決？

如果內(nèi)存地址V初次讀取的值是A，并且在準備賦值的時候檢查到它的值仍然為A，那我們就能說它的值沒有被其他線程改變過了嗎？

如果在這段期間它的值曾經(jīng)被改成了B，后來又被改回為A，那CAS操作就會誤認為它從來沒有被改變過。這個漏洞稱為CAS操作的“ABA”問題。Java并發(fā)包為了解決這個問題，提供了一個帶有標記的原子引用類“AtomicStampedReference”，它可以通過控制變量值的版本來保證CAS的正確性。因此，在使用CAS前要考慮清楚“ABA”問題是否會影響程序并發(fā)的正確性，如果需要解決ABA問題，改用傳統(tǒng)的互斥同步可能會比原子類更高效。