占小狼 轉(zhuǎn)載請注明原創(chuàng)出處角寸，謝謝乖酬！
前言
CAS（Compare and Swap）死相，即比較并替換，實(shí)現(xiàn)并發(fā)算法時(shí)常用到的一種技術(shù)咬像，Doug lea大神在java同步器中大量使用了CAS技術(shù)算撮，鬼斧神工的實(shí)現(xiàn)了多線程執(zhí)行的安全性。
CAS的思想很簡單：三個參數(shù)县昂，一個當(dāng)前內(nèi)存值V肮柜、舊的預(yù)期值A(chǔ)、即將更新的值B倒彰，當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)审洞，將內(nèi)存值修改為B并返回true，否則什么都不做待讳，并返回false芒澜。
問題
一個n++的問題。
public class Case {
public volatile int n;
public void add() {
n++;
}
}
通過javap -verbose Case看看add方法的字節(jié)碼指令
public void add();
flags: ACC_PUBLIC
Code:
stack=3, locals=1, args_size=1
0: aload_0
1: dup
2: getfield #2 // Field n:I
5: iconst_1
6: iadd
7: putfield #2 // Field n:I
10: return
n++被拆分成了幾個指令：
- 執(zhí)行
getfield拿到原始n创淡； - 執(zhí)行
iadd進(jìn)行加1操作痴晦； - 執(zhí)行
putfield寫把累加后的值寫回n；
通過volatile修飾的變量可以保證線程之間的可見性琳彩，但并不能保證這3個指令的原子執(zhí)行誊酌，在多線程并發(fā)執(zhí)行下部凑，無法做到線程安全，得到正確的結(jié)果术辐，那么應(yīng)該如何解決呢砚尽？
如何解決
在add方法加上synchronized修飾解決施无。
public class Case {
public volatile int n;
public synchronized void add() {
n++;
}
}
這個方案當(dāng)然可行辉词，但是性能上差了點(diǎn)，還有其它方案么猾骡？
再來看一段代碼
public int a = 1;
public boolean compareAndSwapInt(int b) {
if (a == 1) {
a = b;
return true;
}
return false;
}
如果這段代碼在并發(fā)下執(zhí)行瑞躺，會發(fā)生什么？
假設(shè)線程1和線程2都過了a==1的檢測兴想，都準(zhǔn)備執(zhí)行對a進(jìn)行賦值幢哨，結(jié)果就是兩個線程同時(shí)修改了變量a，顯然這種結(jié)果是無法符合預(yù)期的嫂便，無法確定a的最終值捞镰。
解決方法也同樣暴力，在compareAndSwapInt方法加鎖同步毙替，變成一個原子操作岸售，同一時(shí)刻只有一個線程才能修改變量a。
除了低性能的加鎖方案厂画，我們還可以使用JDK自帶的CAS方案凸丸，在CAS中，比較和替換是一組原子操作袱院，不會被外部打斷屎慢，且在性能上更占有優(yōu)勢。
下面以AtomicInteger的實(shí)現(xiàn)為例忽洛，分析一下CAS是如何實(shí)現(xiàn)的腻惠。
public class AtomicInteger extends Number implements java.io.Serializable {
// 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;
public final int get() {return value;}
}
- Unsafe，是CAS的核心類欲虚，由于Java方法無法直接訪問底層系統(tǒng)集灌，需要通過本地（native）方法來訪問，Unsafe相當(dāng)于一個后門苍在，基于該類可以直接操作特定內(nèi)存的數(shù)據(jù)绝页。
- 變量valueOffset，表示該變量值在內(nèi)存中的偏移地址寂恬，因?yàn)閁nsafe就是根據(jù)內(nèi)存偏移地址獲取數(shù)據(jù)的续誉。
- 變量value用volatile修飾，保證了多線程之間的內(nèi)存可見性初肉。
看看AtomicInteger如何實(shí)現(xiàn)并發(fā)下的累加操作：
public final int getAndAdd(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta);
}
//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;
}
假設(shè)線程A和線程B同時(shí)執(zhí)行g(shù)etAndAdd操作（分別跑在不同CPU上）：
- AtomicInteger里面的value原始值為3酷鸦，即主內(nèi)存中AtomicInteger的value為3，根據(jù)Java內(nèi)存模型，線程A和線程B各自持有一份value的副本臼隔，值為3嘹裂。
- 線程A通過
getIntVolatile(var1, var2)拿到value值3，這時(shí)線程A被掛起摔握。 - 線程B也通過
getIntVolatile(var1, var2)方法獲取到value值3寄狼，運(yùn)氣好，線程B沒有被掛起氨淌，并執(zhí)行compareAndSwapInt方法比較內(nèi)存值也為3泊愧，成功修改內(nèi)存值為2。 - 這時(shí)線程A恢復(fù)盛正，執(zhí)行
compareAndSwapInt方法比較删咱，發(fā)現(xiàn)自己手里的值(3)和內(nèi)存的值(2)不一致，說明該值已經(jīng)被其它線程提前修改過了豪筝，那只能重新來一遍了痰滋。 - 重新獲取value值，因?yàn)樽兞縱alue被volatile修飾续崖，所以其它線程對它的修改敲街，線程A總是能夠看到，線程A繼續(xù)執(zhí)行
compareAndSwapInt進(jìn)行比較替換袜刷，直到成功聪富。
整個過程中，利用CAS保證了對于value的修改的并發(fā)安全著蟹，繼續(xù)深入看看Unsafe類中的compareAndSwapInt方法實(shí)現(xiàn)墩蔓。
public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);
Unsafe類中的compareAndSwapInt，是一個本地方法萧豆，該方法的實(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;
}
看到這匯編洪鸭，內(nèi)心崩潰 ??
__asm__表示匯編的開始
volatile表示禁止編譯器優(yōu)化
LOCK_IF_MP是個內(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前綴样刷。
- 如果是多處理器，為cmpxchg指令添加lock前綴览爵。
- 反之置鼻，就省略lock前綴。（單處理器會不需要lock前綴提供的內(nèi)存屏障效果）
intel手冊對lock前綴的說明如下：
- 確保后續(xù)指令執(zhí)行的原子性蜓竹。
在Pentium及之前的處理器中箕母，帶有l(wèi)ock前綴的指令在執(zhí)行期間會鎖住總線储藐，使得其它處理器暫時(shí)無法通過總線訪問內(nèi)存，很顯然嘶是，這個開銷很大钙勃。在新的處理器中，Intel使用緩存鎖定來保證指令執(zhí)行的原子性聂喇，緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷辖源。 - 禁止該指令與前面和后面的讀寫指令重排序。
- 把寫緩沖區(qū)的所有數(shù)據(jù)刷新到內(nèi)存中授帕。
上面的第2點(diǎn)和第3點(diǎn)所具有的內(nèi)存屏障效果同木，保證了CAS同時(shí)具有volatile讀和volatile寫的內(nèi)存語義。
CAS缺點(diǎn)
CAS存在一個很明顯的問題跛十，即ABA問題。
問題：如果變量V初次讀取的時(shí)候是A秕硝，并且在準(zhǔn)備賦值的時(shí)候檢查到它仍然是A芥映，那能說明它的值沒有被其他線程修改過了嗎？
如果在這段期間曾經(jīng)被改成B远豺，然后又改回A奈偏，那CAS操作就會誤認(rèn)為它從來沒有被修改過。針對這種情況躯护，java并發(fā)包中提供了一個帶有標(biāo)記的原子引用類AtomicStampedReference惊来，它可以通過控制變量值的版本來保證CAS的正確性。
