面試中如何答好：CAS
如何回答什么是CAS？
CAS是Compare And Swap的簡稱，單從字面理解是比較并替換，實(shí)際指的是Unsafe類中的三個(gè)方法compareAndSwapObject，compareAndSwapInt，compareAndSwapLong，三個(gè)方法分別是以比較并替換的方式對(duì)Object類型的數(shù)據(jù)，對(duì)int類型的數(shù)據(jù)，對(duì)long類型的數(shù)據(jù)保證其操作的原子性。
在CAS比較并替換的邏輯中有三個(gè)重要的概念：預(yù)估值，內(nèi)存值，更新值，而比較替換的邏輯為：如果預(yù)估值等于內(nèi)存值，則將內(nèi)存值更新為更新值，否則就不更新。
比較和替換這兩個(gè)動(dòng)作，無論是在java層面實(shí)現(xiàn)還是在jvm層面實(shí)現(xiàn)在不加鎖的情況下都是無法完全保證原子性的，因此不得不依賴硬件對(duì)于并發(fā)的支持，即操作系統(tǒng)底層提供了cmpxchg指令，這一個(gè)指令就可以完成比較和替換兩個(gè)動(dòng)作。那么即便是將兩個(gè)動(dòng)作濃縮到一個(gè)匯編指令里面，就能保證原子性嗎？
答案是肯定的，這是因?yàn)橛?jì)算機(jī)硬件自身支持一個(gè)匯編指令執(zhí)行過程是不允許被中斷的，這兩個(gè)動(dòng)作已經(jīng)濃縮到了cmpxchg這一個(gè)匯編指令里面了，不能中斷意味著這兩個(gè)動(dòng)作必須在同個(gè)cpu時(shí)間片段內(nèi)完成，一氣呵成，所以cmpxchg指令本身就具備了原子性。
但是不同的平臺(tái)實(shí)現(xiàn)cas有不同的方式。這個(gè)匯編指令的名字可能也會(huì)不同，這個(gè)需要注意。
分析：
分析CAS前必須先明白原子性是什么。
什么是原子性
原子性：指事務(wù)的不可分割性，一個(gè)事務(wù)的所有操作要么不間斷地全部被執(zhí)行，要么一個(gè)也沒有執(zhí)行。
前置了解
我們都知道所有的程序都是運(yùn)行在cpu上的，cpu執(zhí)行的是機(jī)器碼，如00,01,0A。因?yàn)檫@些指令操作起來太麻煩且不好記憶，所以后來有人發(fā)明了更加方便操作和好懂的匯編語言，匯編是一種低級(jí)語言，這里可以理解為機(jī)器碼對(duì)外所呈現(xiàn)的樣子，也可以干脆理解為cpu執(zhí)行的就是匯編語言。基本每種平臺(tái)都實(shí)現(xiàn)了自己的匯編語言，所以不同平臺(tái)的匯編語言是不能通用的。
匯編和機(jī)器碼的對(duì)應(yīng)關(guān)系如下：
ADD reg8/mem8,reg8 對(duì)應(yīng) 00
ADD reg16/mem16,reg16 對(duì)應(yīng) 01
OR reg8,reg8/mem8 對(duì)應(yīng) 0A
OR reg16,reg16/mem16 對(duì)應(yīng) 0B
jvm是一個(gè)虛擬機(jī)，它有一套自己的字節(jié)碼指令，它有一套內(nèi)存管理機(jī)制和垃圾回收機(jī)制，它有自己的運(yùn)行機(jī)制，它有類似與寄存器的操作數(shù)棧，它自身就是一臺(tái)計(jì)算機(jī)，它專門運(yùn)行java語言，java語言依靠jvm運(yùn)行，需要先編譯成字節(jié)碼指令，就像C++語言運(yùn)行要先編譯成匯編語言一樣。
jvm是C實(shí)現(xiàn)的，歸根結(jié)底要運(yùn)行在cpu上,所以我們可以知道java語言的運(yùn)行過程為：java編譯成c++，再編譯成匯編，再編譯成機(jī)器碼。
通過一個(gè)例子來看下java代碼到機(jī)器碼的翻譯過程：
java代碼：i++
java代碼編譯成字節(jié)碼反編譯的代碼：getstatic i 獲取i的值 iconst_1 準(zhǔn)備常量1 iadd 加1 putstatic 將修改后的值寫回變量i
iadd會(huì)被jvm翻譯成類似于下面的匯編代碼：mov (%rsp),%edx add $0x8,%rsp add %edx,%eax
而匯編指令add對(duì)應(yīng)的二進(jìn)制機(jī)器碼為00,01等。
現(xiàn)在來理解下原子性概念中的不可分割和不間斷執(zhí)行
不可分割性就是原子性。而事物的不可分割則是事務(wù)不受外界影響。
不管是java還是c++代碼，最終運(yùn)行的時(shí)候都要被編譯成機(jī)器碼，而機(jī)器碼是cpu運(yùn)行的基本單元，所以只有一個(gè)機(jī)器碼指令才是天然的不可分割，而為了方便開發(fā)和理解，每個(gè)平臺(tái)都有一套對(duì)應(yīng)機(jī)器碼的匯編語言，以linux為例，操作系統(tǒng)會(huì)保證每個(gè)匯編指令的執(zhí)行都是不允許被中斷的，也就是一個(gè)匯編指令也是不可分割的。
多個(gè)指令就一定是分割的嗎？
不一定，只要多個(gè)指令能夠不間斷執(zhí)行就可以認(rèn)為是沒有被分割的。
那如何才算不間斷執(zhí)行呢？
不間斷就是幾個(gè)指令能夠順序執(zhí)行，且執(zhí)行過程中或者線程不可中斷，或者線程中斷后不受其他線程影響。
那什么是中斷呢？
中斷就是線程被掛起。
那什么時(shí)候線程才會(huì)被掛起呢？
java程序員都知道，線程執(zhí)行過程中遇到鎖的時(shí)候，如果沒有獲取到鎖就會(huì)阻塞掛起。當(dāng)調(diào)用wait方法，join方法，park方法的時(shí)候都會(huì)進(jìn)入阻塞掛起的狀態(tài)，但是這些狀態(tài)都是程序員人為的，是可以避免的。
但是有一種掛起是不可避免的，我們知道cpu是串行的運(yùn)行模式，一個(gè)時(shí)間點(diǎn)上只能運(yùn)行一個(gè)線程。為了讓所有的線程看起來都是在同時(shí)運(yùn)行，操作系統(tǒng)的機(jī)制是將cpu的執(zhí)行時(shí)間分成很多個(gè)細(xì)小的時(shí)間片段，由操作系統(tǒng)為每個(gè)線程分配時(shí)間片段，當(dāng)輪到某個(gè)時(shí)間片段執(zhí)行時(shí)，綁定此時(shí)間片段的線程才會(huì)被執(zhí)行，當(dāng)這個(gè)時(shí)間片段用完，當(dāng)前的線程如果還沒有執(zhí)行完的話就會(huì)被掛起，等待再次被調(diào)度執(zhí)行。這個(gè)過程中線程就被中斷了。
中斷后不受其他線程影響怎么理解？
例如synchronized代碼塊，雖然線程在執(zhí)行代碼塊邏輯的時(shí)候會(huì)被cpu時(shí)間片段調(diào)度中斷，但是synchronized關(guān)鍵字通過加鎖的方式只允許一個(gè)線程進(jìn)入代碼塊邏輯，這就保證了當(dāng)前線程在運(yùn)行代碼塊中邏輯的時(shí)候雖然會(huì)中斷，但是不受其他線程的影響。
不能看出上面的說不可中斷和中斷不受其他線程影響對(duì)應(yīng)的正是cas的方式和加鎖的方式實(shí)現(xiàn)原子性。
本篇我們只看CAS方式
CAS實(shí)現(xiàn)原理
計(jì)算機(jī)做了什么？
我們知道了cas最終是靠計(jì)算機(jī)底層原語cmpxchg支持，下面就是linux_x86底層的匯編實(shí)現(xiàn)。
linux_x86底層實(shí)現(xiàn)
\hotspot\src\os_cpu\linux_x86\vm\atomic_linux_x86.inline.hpp
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
int mp = os::is_MP(); // 內(nèi)聯(lián)函數(shù)，用來判斷當(dāng)前系統(tǒng)是否為多處理器
__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;
}在這個(gè)方法中最關(guān)鍵的是一行代碼是：LOCK_IF_MP(%4) "cmpxchgl %1,(%3)，cmpxchgl關(guān)鍵字就是匯編指令原語，這個(gè)原語在不同的計(jì)算機(jī)的實(shí)現(xiàn)不一樣，在linux_x86就叫做cmpxchgl。
而cmpxchg方法可以理解為linux_x86平臺(tái)對(duì)外提供cas支持的API。
這段代碼中我們看到LOCK_IF_MP關(guān)鍵字，看到lock一般我們會(huì)想到加鎖，這里確實(shí)是加鎖的意思，或許你會(huì)說cas操作為什么還要加鎖，如果這樣，那直接用加鎖的方式實(shí)現(xiàn)原子性不就可以了，這段代碼的邏輯其實(shí)是先判斷是否為多核處理器，如果是多核就會(huì)加鎖，如果單核就不加鎖。而這個(gè)加鎖的實(shí)現(xiàn)根據(jù)系統(tǒng)平臺(tái)的不同會(huì)有不同的實(shí)現(xiàn)方式，大致分為鎖總線和鎖緩存。
我們說了，一條機(jī)器指令（或者說匯編指令）一定能在一個(gè)cpu時(shí)間片段內(nèi)完成，如果兩個(gè)線程占據(jù)兩個(gè)時(shí)間片，這個(gè)兩個(gè)時(shí)間片段都是要執(zhí)行同一個(gè)指令，當(dāng)一個(gè)時(shí)間片段執(zhí)行完，才能執(zhí)行下一個(gè)時(shí)間片段，這樣看起來單個(gè)指令的執(zhí)行是串行的，不會(huì)有問題，但是現(xiàn)在的處理器一般都會(huì)存在多核，甚至多cpu，每個(gè)核都會(huì)有自己的緩存，所以，多核情況下僅僅靠cas是無法保證原子性的，操作系統(tǒng)內(nèi)部通過鎖來規(guī)避。
這屬于操作系統(tǒng)為實(shí)現(xiàn)更高效而不得不付出的復(fù)雜性。這里牽扯到緩存一致性協(xié)議，介紹操作系統(tǒng)的時(shí)候再細(xì)說。
JVM做了什么？
既然計(jì)算機(jī)提供了cas支持，那么應(yīng)用程序怎么應(yīng)用呢，java虛擬機(jī)為java實(shí)現(xiàn)提供了支持。
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); //查找要指定的對(duì)象
jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); //獲取要操作的是對(duì)象的字段的內(nèi)存地址
return (jint)(Atomic::cmpxchg(x, addr, e)) == e; //執(zhí)行Atomic類中的cmpxchg
UNSAFE_END以上源碼中真正實(shí)現(xiàn)cas的代碼為：
Atomic::cmpxchg(x, addr, e)
不難看出，x為新值，addr為地址，e為期望值
jvm底層調(diào)用了匯編代碼中的方法cmpxchg，這個(gè)方法就是上面匯編代碼中方法。
上面這個(gè)方法是jvm底層實(shí)現(xiàn)，也是jvm對(duì)于cas的支持，jvm對(duì)外也提供了API,只不過是以本地方法的形式提供給java使用，它的體現(xiàn)就是 Unsafe類下面提供的三個(gè)本地方法compareAndSwapObject，compareAndSwapInt，compareAndSwapLong。
圖片
這個(gè)幾個(gè)方法的具體實(shí)現(xiàn)都在jvm內(nèi)部。上面的jvm代碼對(duì)應(yīng)的就是compareAndSwapInt本地方法的具體實(shí)現(xiàn)，其他方法也都大同小異。
Unsafe類是java層面提供的用于內(nèi)存管理的類，除內(nèi)存操作方法外，同時(shí)還提供線程調(diào)度操作，，內(nèi)存屏障相關(guān)操作等，但是它不是應(yīng)用類加載器加載的，因此程序員是不能直接使用的。
我們來解釋下這幾個(gè)參數(shù)：
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);var1：要修改的對(duì)象起始地址 如：0x00000111
var2：需要修改的具體內(nèi)存地址 如100 。0x0000011+100 = 0x0000111就是要修改的值的地址
注意沒有var3
var4：期望內(nèi)存中的值，拿這個(gè)值和0x0000111內(nèi)存中的中值比較，如果為true，則修改，返回ture,否則返回false，等待下次修改。
var5：如果上一步比較為ture，則把var5更新到0x0000111其實(shí)的內(nèi)存中。
原子操作，直接操作內(nèi)存。
JAVA做了什么？
java提供了java.util.concurrent.atomic包，包下面提供了各種原子類，如下圖。
圖片
這些原子類底層基本都是依賴Unsafe類的三個(gè)方法實(shí)現(xiàn)。
接下來以AtomicInteger來介紹
先來看例子：
static int i=0;
public static void main(String[] args) throws IOException, InterruptedException {
Thread T1=new Thread(new Runnable(){
@Override
public void run(){
for(int n=0;n<10000;n++){
i++;
}
}
});
Thread T2=new Thread(new Runnable(){
@Override
public void run(){
for(int n=0;n<10000;n++){
i++;
}
}
});
T1.start();
T2.start();
T1.join();
T2.join();
System.out.println(i);大家都清楚這段代碼最終打印的結(jié)果不一定是20000，因?yàn)閕++這個(gè)操作不是原子性的。
上述代碼的邏輯我們替換為AtomicInteger來實(shí)現(xiàn)
static AtomicInteger atomic=new AtomicInteger();
public static void main(String[] args) throws IOException, InterruptedException {
Thread T1=new Thread(new Runnable(){
@Override
public void run(){
for(int n=0;n<10000;n++){
atomic.getAndAdd(1);
}
}
});
Thread T2=new Thread(new Runnable(){
@Override
public void run(){
for(int n=0;n<10000;n++){
atomic.getAndAdd(1);
}
}
});
T1.start();
T2.start();
T1.join();
T2.join();
System.out.println(atomic);這段代碼實(shí)現(xiàn)得到的結(jié)果是正確的20000。
先來看看AtomicInteger類的源碼（只貼出主要代碼）
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
private static final Unsafe unsafe = Unsafe.getUnsafe();
private volatile int value;
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) {
throw new Error(ex);
}
}
public AtomicInteger(int initialValue) {
value = initialValue;
}
public AtomicInteger() {
}
private volatile int value;
public final int getAndAdd(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta);
}
}先來解釋下getAndAddInt方法中的這幾個(gè)參數(shù)
value是AtomicInteger對(duì)象的成員變量，它就是實(shí)際要被操作的變量；
this是指當(dāng)前AtomicInteger對(duì)象；
valueOffse是指value這個(gè)屬性所代表的具體值位于AtomicInteger對(duì)象所分配的內(nèi)存空間的偏移量。
從上面的代碼中可以看出valueOffse的值是通過靜態(tài)方法確定的，也就是說在創(chuàng)建AtomicInteger對(duì)象前這個(gè)值就已經(jīng)確定了且是固定的。之所以能固定下來，是因?yàn)閖ava中的類在類加載的時(shí)候就已經(jīng)確定了類中的成員變量所處整個(gè)內(nèi)存空間的地址。所以同個(gè)類下的所有對(duì)象的這個(gè)偏移量值都是一樣的。
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;
}這個(gè)方法中var1就是AtomicInteger對(duì)象本身，var2是偏移量，var4是要加加的值。var5是查詢出的當(dāng)前AtomicInteger對(duì)象內(nèi)存空間在valueOffse偏移量處的值是多少。
getAndAddInt方法的整體邏輯就是先獲取當(dāng)前內(nèi)存值作為預(yù)估值，利用compareAndSwapInt方法進(jìn)行cas，即比較預(yù)估值和計(jì)算底層的內(nèi)存值，如果相等就用更新值替換內(nèi)存值，如果不等就返回false,然后重復(fù)上面的步驟，直到替換成功。
借助這個(gè)思想，也可以解決一些數(shù)據(jù)庫層面的問題
int c=0;
while(c=0){
1 select ov from t where id=1;
2 int nv=ov*x;
3 c = update t set ov=nv where id=1 and ov=ov;
}CAS的問題
不支持高并發(fā)
CAS只能用于并發(fā)不是很高的場(chǎng)景，java中的源碼我們看到了，一般為了保證一定能替換成功需要在cas外套一個(gè)循環(huán)，如果并發(fā)很高，處于循環(huán)中的線程很多，就會(huì)導(dǎo)致cpu飆升，一般并發(fā)很高的場(chǎng)景需要用鎖解決。
ABA問題
使用CAS需要注意ABA問題，所謂ABA問題其實(shí)很簡單，先羅列下步驟
獲取：獲取內(nèi)存值作為預(yù)期值
比較：預(yù)期值和內(nèi)存值；
替換：內(nèi)存值=更新值；
如果在獲取和比較之間內(nèi)存值由1被改為2，又由2被改回了1，這種情況下是不會(huì)影響后面的比較和替換的。這便是ABA問題。可能結(jié)果上沒有問題，但是在邏輯上是有問題的。不能確保所有的場(chǎng)景都有問題。
ABA問題的解決
jdk提供 AtomicStampedReference 原子類解決ABA問題。
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}pair是一個(gè)靜態(tài)內(nèi)部類，也是在類加載的時(shí)候計(jì)算固定的偏移量，只不過這個(gè)內(nèi)部類中有兩個(gè)屬性，一個(gè)是具體的值，一個(gè)是時(shí)間戳。
通過compareAndSwapObject進(jìn)行cas操作。
不難看出，原來是通過比較value的值容易出現(xiàn)ABA問題，現(xiàn)在是通過compareAndSwapObject方法比較value和時(shí)間戳來判斷是否要替換，替換的時(shí)候，會(huì)把value和時(shí)間戳都替換。
