本文首發(fā)：WindCoder
什么是CAS？
全稱：Compare And Swap治唤，翻譯為比較并替換钝计。
CAS機(jī)制當(dāng)中使用了3個(gè)基本操作數(shù)：
- 內(nèi)存地址V
- 舊的預(yù)期值A(chǔ)
- 要修改的新值B
當(dāng)且僅當(dāng)變量的預(yù)期值A(chǔ)和內(nèi)存地址V當(dāng)中的實(shí)際值相同時(shí)酿炸，才會(huì)將內(nèi)存地址V對應(yīng)的值修改為B 瘫絮。
例：
1.在內(nèi)存地址V中，存著值為10的變量填硕。
2.此時(shí)線程1想要把變量的值加1麦萤。對線程1來說，舊的預(yù)期值A(chǔ)=10扁眯，要修改的新值B=11壮莹。
3.在線程1提交更新之前，另一個(gè)線程2先行一步姻檀，把內(nèi)存地址V中的變量先更成了11命满。
4.線程1提交更新，首先A和地址V中的實(shí)際值比較绣版，發(fā)現(xiàn)A不等于V的實(shí)際值胶台，提交失敗。
5.線程1重新獲取內(nèi)存地址的當(dāng)前值杂抽，并重新計(jì)算想要修改的新值B诈唬。此時(shí)對線程1來說，A=11,B=12缩麸。這個(gè)重新嘗試的過程被稱為自旋铸磅。
6.這次比較幸運(yùn)，沒有其他線程改變V中的值匙睹，線程1進(jìn)行Compare愚屁，發(fā)現(xiàn)A與V中的值相等。
7.線程1進(jìn)行SWAP,把地址V中的值替換為B痕檬，即12。
從思想上來說：
- Synchronized屬于悲觀鎖送浊，悲觀地認(rèn)為程序中的并發(fā)情況嚴(yán)重梦谜，所以嚴(yán)防死守。
- CAS屬于樂觀鎖，樂觀地認(rèn)為程序中的并發(fā)情況不那么嚴(yán)重唁桩，所以讓線程不斷去嘗試更新闭树。
使用場景
- Synchronized同步鎖更適合在并發(fā)量非常高的情況下。
- CAS機(jī)制用于如Atomic系列類荒澡，Lock系列類的底層實(shí)現(xiàn)报辱；Java1.6以上版本，Synchronized轉(zhuǎn)變?yōu)橹亓考?jí)鎖之前也會(huì)采用单山。
CAS缺點(diǎn)
1.CPU開銷較大
在并發(fā)量比較高的情況下碍现，如果許多線程反復(fù)嘗試更新某個(gè)變量，卻一直不成功米奸，循環(huán)往復(fù)昼接，會(huì)給CPU帶來很大的壓力。
2.不能保證代碼塊的原子性
CAS機(jī)制所保證的只是一個(gè)變量的原子性操作悴晰，而不能保證整個(gè)代碼塊的原子性慢睡。
比如需要保證3個(gè)變量共同進(jìn)行原子性的更新，就不得不使用Synchronized了铡溪。
3.ABA問題
當(dāng)一個(gè)值從A更新成B漂辐，又更新會(huì)A，普通CAS機(jī)制會(huì)誤判通過檢測棕硫。
例：
假設(shè)內(nèi)存中有個(gè)值為100的變量者吁，存儲(chǔ)在地址V中。
此時(shí)有3個(gè)線程想使用CAS的方式更新這個(gè)值饲帅，每個(gè)線程執(zhí)行的時(shí)間有略微的偏差复凳。線程1和線程2已經(jīng)獲得當(dāng)前值，線程3還未獲得當(dāng)前值灶泵。即：
- 線程1：獲取當(dāng)前值100育八，期望更新為50；
- 線程2：獲取當(dāng)前值100赦邻，期望更新為50髓棋；
- 線程3：期望更新為100；
之后惶洲，線程1先執(zhí)行成功按声，把100更新為50，線程2因?yàn)槟承┰虮蛔枞衤溃醋龈虑┰颍痪€程3在1更新后，獲得當(dāng)前值50.
- 線程1：獲取當(dāng)前值100铐料，成功更新為50渐裂；
- 線程2：獲取當(dāng)前值100豺旬，期望更新為50，BLOCK柒凉；
- 線程3：獲取當(dāng)前值50族阅，期望更新為100；
此時(shí)膝捞，線程2仍處于阻塞狀態(tài)坦刀，線程3繼續(xù)執(zhí)行，把50更新為100蔬咬。
- 線程1：獲取當(dāng)前值100鲤遥，成功更新為50，已返回计盒；
- 線程2：獲取當(dāng)前值100渴频，期望更新為50，BLOCK北启；
- 線程3：獲取當(dāng)前值50卜朗，成功更新為100；
最后咕村，線程2終于恢復(fù)運(yùn)行狀態(tài)场钉，由于阻塞之前已經(jīng)獲得“當(dāng)前值”100，并經(jīng)過compare檢測懈涛，內(nèi)存地址V的實(shí)際值也是100逛万，所以成功把變量100更新為50.
- 線程1：獲取當(dāng)前值100，成功更新為50批钠，已返回宇植；
- 線程2：獲取當(dāng)前值100，成功更新為50埋心；
- 線程3：獲取當(dāng)前值50指郁，成功更新為100，已返回拷呆；
這個(gè)過程中闲坎，線程2獲取到的變量100是一個(gè)舊值，盡管和當(dāng)前的實(shí)際值相同茬斧，但內(nèi)存地址V中的變量已經(jīng)經(jīng)歷了100->50->100（即A->B->A)的改變腰懂。
解決方案
利用版本號(hào)比較可以有效解決ABA問題。即项秉，在Compare階段不僅要比較期望值A(chǔ)和地址V中的實(shí)際值绣溜，還要比較變量的版本號(hào)是否一致。
在Java當(dāng)中伙狐，Java并發(fā)包中提供了一個(gè)帶有標(biāo)記的原子引用類AtomicStampedReference涮毫，其可以通過控制變量值的版本來保證CAS的正確性瞬欧。
Java當(dāng)中CAS的底層實(shí)現(xiàn)
下面以AtomicInteger的實(shí)現(xiàn)為例分析贷屎。
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
.....
/**
* Gets the current value.
*
* @return the current value
*/
public final int get() {
return value;
}
//省略部分代碼
......
}
- 1.Unsafe罢防，是CAS的核心類，由于Java方法無法直接訪問底層系統(tǒng)唉侄，需要通過本地（native）方法來訪問咒吐，Unsafe相當(dāng)于一個(gè)后門，基于該類可以直接操作特定內(nèi)存的數(shù)據(jù)属划。unsafe為我們提供了硬件級(jí)別的原子操作恬叹。
- 2.變量valueOffset，表示該變量值在內(nèi)存中的偏移地址同眯，因?yàn)閁nsafe就是根據(jù)內(nèi)存偏移地址獲取數(shù)據(jù)的绽昼。我們可以簡單地把valueOffset理解為value變量的內(nèi)存地址。
- 3.變量value用volatile修飾须蜗，保證了多線程之間的內(nèi)存可見性硅确。即可當(dāng)做V中的值
看看AtomicInteger如何實(shí)現(xiàn)并發(fā)下的累加操作：
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
// unsafe.getAndAddInt
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
public native int getIntVolatile(Object var1, long var2);
線程通過getIntVolatile(var1, var2)拿到value值，compareAndSwapInt比較并替換明肮，若不相等繼續(xù)執(zhí)行g(shù)etIntVolatile菱农，然后再compareAndSwapInt,直到成功。
整個(gè)過程中柿估，利用CAS保證了對于value的修改的并發(fā)安全循未，繼續(xù)深入看看Unsafe類中的compareAndSwapInt方法實(shí)現(xiàn)。
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Unsafe類中的compareAndSwapInt秫舌，是一個(gè)本地方法的妖，該方法的實(shí)現(xiàn)位于unsafe.cpp中（此部分及以下大部分來源自占小狼博客）
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
UnsafeWrapper("Unsafe_CompareAndSwapInt");
oop p = JNIHandles::resolve(obj);
jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
先想辦法拿到變量value在內(nèi)存中的地址。
通過Atomic::cmpxchg實(shí)現(xiàn)比較替換足陨，其中參數(shù)x是即將更新的值嫂粟，參數(shù)e是原內(nèi)存的值。
如果是Linux的x86钠右，Atomic::cmpxchg方法的實(shí)現(xiàn)如下：
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
int mp = os::is_MP();
__asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
: "=a" (exchange_value)
: "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
: "cc", "memory");
return exchange_value;
}
-
__asm__表示匯編的開始 -
volatile表示禁止編譯器優(yōu)化 -
LOCK_IF_MP是個(gè)內(nèi)聯(lián)函數(shù)
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
Window的x86實(shí)現(xiàn)如下：
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
int mp = os::isMP(); //判斷是否是多處理器
_asm {
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
LOCK_IF_MP(mp)
cmpxchg dword ptr [edx], ecx
}
}
// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
__asm je L0 \
__asm _emit 0xF0 \
__asm L0:
LOCK_IF_MP根據(jù)當(dāng)前系統(tǒng)是否為多核處理器決定是否為cmpxchg指令添加lock前綴赋元。
- 1.如果是多處理器，為cmpxchg指令添加lock前綴飒房。
- 2.反之搁凸，就省略lock前綴。（單處理器會(huì)不需要lock前綴提供的內(nèi)存屏障效果）
intel手冊對lock前綴的說明如下：
- 1.確保后續(xù)指令執(zhí)行的原子性狠毯。
在Pentium及之前的處理器中护糖，帶有l(wèi)ock前綴的指令在執(zhí)行期間會(huì)鎖住總線，使得其它處理器暫時(shí)無法通過總線訪問內(nèi)存嚼松，很顯然嫡良，這個(gè)開銷很大锰扶。在新的處理器中，Intel使用緩存鎖定來保證指令執(zhí)行的原子性寝受，緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷坷牛。
- 2.禁止該指令與前面和后面的讀寫指令重排序。
- 3.把寫緩沖區(qū)的所有數(shù)據(jù)刷新到內(nèi)存中很澄。
上面的第2點(diǎn)和第3點(diǎn)所具有的內(nèi)存屏障效果京闰，保證了CAS同時(shí)具有volatile讀和volatile寫的內(nèi)存語義。
擴(kuò)展知識(shí)-關(guān)于CPU的鎖
關(guān)于CPU的鎖有如下3種：
1.處理器自動(dòng)保證基本內(nèi)存操作的原子性
首先處理器會(huì)自動(dòng)保證基本的內(nèi)存操作的原子性甩苛。
處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個(gè)字節(jié)是原子的蹂楣，意思是當(dāng)一個(gè)處理器讀取一個(gè)字節(jié)時(shí)，其他處理器不能訪問這個(gè)字節(jié)的內(nèi)存地址讯蒲。
奔騰6和最新的處理器能自動(dòng)保證單處理器對同一個(gè)緩存行里進(jìn)行16/32/64位的操作是原子的痊土，但是復(fù)雜的內(nèi)存操作處理器不能自動(dòng)保證其原子性，比如跨總線寬度墨林，跨多個(gè)緩存行赁酝，跨頁表的訪問。
但是處理器提供總線鎖定和緩存鎖定兩個(gè)機(jī)制來保證復(fù)雜內(nèi)存操作的原子性萌丈。
2.使用總線鎖保證原子性
第一個(gè)機(jī)制是通過總線鎖保證原子性赞哗。
如果多個(gè)處理器同時(shí)對共享變量進(jìn)行讀改寫（i++就是經(jīng)典的讀改寫操作）操作，那么共享變量就會(huì)被多個(gè)處理器同時(shí)進(jìn)行操作辆雾，這樣讀改寫操作就不是原子的肪笋，操作完之后共享變量的值會(huì)和期望的不一致，舉個(gè)例子：如果i=1,我們進(jìn)行兩次i++操作度迂，我們期望的結(jié)果是3藤乙，但是有可能結(jié)果是2。
原因是有可能多個(gè)處理器同時(shí)從各自的緩存中讀取變量i惭墓，分別進(jìn)行加一操作坛梁，然后分別寫入系統(tǒng)內(nèi)存當(dāng)中。那么想要保證讀改寫共享變量的操作是原子的腊凶，就必須保證CPU1讀改寫共享變量的時(shí)候划咐，CPU2不能操作緩存了該共享變量內(nèi)存地址的緩存。
處理器使用總線鎖就是來解決這個(gè)問題的钧萍。所謂總線鎖就是使用處理器提供的一個(gè)LOCK＃信號(hào)褐缠，當(dāng)一個(gè)處理器在總線上輸出此信號(hào)時(shí)，其他處理器的請求將被阻塞住,那么該處理器可以獨(dú)占使用共享內(nèi)存风瘦。
3.使用緩存鎖保證原子性
第二個(gè)機(jī)制是通過緩存鎖定保證原子性队魏。
在同一時(shí)刻我們只需保證對某個(gè)內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間通信鎖住了万搔，這使得鎖定期間胡桨，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)官帘，所以總線鎖定的開銷比較大，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進(jìn)行優(yōu)化昧谊。
頻繁使用的內(nèi)存會(huì)緩存在處理器的L1刽虹，L2和L3高速緩存里，那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行揽浙，并不需要聲明總線鎖状婶，在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實(shí)現(xiàn)復(fù)雜的原子性意敛。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內(nèi)存區(qū)域在LOCK操作期間被鎖定馅巷，當(dāng)它執(zhí)行鎖操作回寫內(nèi)存時(shí)，處理器不在總線上聲言LOCK＃信號(hào)草姻，而是修改內(nèi)部的內(nèi)存地址钓猬，并允許它的緩存一致性機(jī)制來保證操作的原子性，因?yàn)榫彺嬉恢滦詸C(jī)制會(huì)阻止同時(shí)修改被兩個(gè)以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù)撩独，當(dāng)其他處理器回寫已被鎖定的緩存行的數(shù)據(jù)時(shí)會(huì)起緩存行無效敞曹，在例1中，當(dāng)CPU1修改緩存行中的i時(shí)使用緩存鎖定综膀，那么CPU2就不能同時(shí)緩存了i的緩存行澳迫。
但是有兩種情況下處理器不會(huì)使用緩存鎖定。第一種情況是：當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部剧劝，或操作的數(shù)據(jù)跨多個(gè)緩存行（cache line）橄登，則處理器會(huì)調(diào)用總線鎖定。第二種情況是：有些處理器不支持緩存鎖定讥此。對于Inter486和奔騰處理器,就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會(huì)調(diào)用總線鎖定拢锹。
以上兩個(gè)機(jī)制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實(shí)現(xiàn)。比如位測試和修改指令BTS萄喳，BTR卒稳，BTC，交換指令XADD他巨，CMPXCHG和其他一些操作數(shù)和邏輯指令充坑，比如ADD（加），OR（或）等染突，被這些指令操作的內(nèi)存區(qū)域就會(huì)加鎖捻爷，導(dǎo)致其他處理器不能同時(shí)訪問它。
參考資料
最開始了解CAS機(jī)制來源于看小灰的公眾號(hào)（chengxuyuanxiaohui）役衡，里面一共是兩篇文章，這里僅放出一篇地址薪棒，有興趣可以去公眾號(hào)查看手蝎。
小灰里面對AtomicInteger的分析部分比較簡單而且看代碼可能略微舊些榕莺，于是找到了占小狼的和下面一篇。這主要參考了對AtomicInteger的CAS底層實(shí)現(xiàn)分析以及深到匯編的部分棵介。
這里也存在一些匯編钉鸯，由于和占的部分重疊就沒再多看，里面有個(gè)C++文件地址所在目錄邮辽，雖然是openjdk7的唠雕，但可以參考。主要留存了下里面的備注知識(shí)-關(guān)于CPU的鎖吨述。
