簡(jiǎn)介
CAS，即Compare and Swap，意為比較并交換
關(guān)于鎖，也許最先想到的是synchronized關(guān)鍵字，但synchronized關(guān)鍵字會(huì)讓沒(méi)有得到鎖資源的線程進(jìn)入BLOCKED狀態(tài)，而后在爭(zhēng)奪到鎖資源后恢復(fù)為RUNNABLE狀態(tài)，這個(gè)過(guò)程中涉及到操作系統(tǒng)用戶模式和內(nèi)核模式的轉(zhuǎn)換，代價(jià)比較高。
盡管JAVA 1.6為synchronized做了優(yōu)化，增加了從偏向鎖到輕量級(jí)鎖再到重量級(jí)鎖的過(guò)過(guò)度，但是在最終轉(zhuǎn)變?yōu)橹亓考?jí)鎖之后，性能仍然比較低。所以面對(duì)這種情況，我們就可以使用java中的“原子操作類”。即是java.util.concurrent.atomic包下，一系列以Atomic開(kāi)頭的包裝類。如AtomicBoolean，AtomicUInteger，AtomicLong。它們分別用于Boolean，Integer，Long類型的原子性操作。
Atomic操作類的底層正是用到了“CAS機(jī)制”
接下來(lái)就詳細(xì)講講什么是“CAS機(jī)制”
詳解
來(lái)看這樣一段代碼
import java.util.concurrent.atomic.AtomicInteger;
public class CASTest {
private static Integer count = 0;
private static Integer count2 = 0;
private static AtomicInteger count3 = new AtomicInteger(0);
public static void main(String[] args) {
for (int j=0;j<2;j++){
new Thread(()->{
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int i=0;i<100;i++){
count++;
}
}).start();
}
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("count="+count);
for (int j=0;j<2;j++){
new Thread(()->{
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int i=0;i<100;i++){
synchronized (CASTest.class){
count2++;
}
}
}).start();
}
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("count2="+count2);
for (int j=0;j<2;j++){
new Thread(()->{
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int i=0;i<100;i++){
count3.incrementAndGet();
}
}).start();
}
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("count3="+count3);
}
}
這段輸出的結(jié)果：
也就是說(shuō)，不加鎖無(wú)法保證count最后結(jié)果為200，加synchronized關(guān)鍵字和使用Atomic類能保證最終結(jié)果為200，但是使用Atomic類的性能會(huì)更高一些。因?yàn)锳tomic操作類的底層正是用到了“CAS機(jī)制”。
CAS機(jī)制中使用了3個(gè)基本操作數(shù)：內(nèi)存地址V，舊的預(yù)期值A(chǔ)，要修改的新值B。
更新一個(gè)變量的時(shí)候，只有當(dāng)變量的預(yù)期值A(chǔ)和內(nèi)存地址V當(dāng)中的實(shí)際值相同時(shí)，才會(huì)將內(nèi)存地址V對(duì)應(yīng)的值修改為B。
我們看一個(gè)例子：
1. 在內(nèi)存地址V當(dāng)中，存儲(chǔ)著值為10的變量。
2. 此時(shí)線程1想把變量的值增加1.對(duì)線程1來(lái)說(shuō)，舊的預(yù)期值A(chǔ)=10，要修改的新值B=11.
3. 在線程1要提交更新之前，另一個(gè)線程2搶先一步，把內(nèi)存地址V中的變量值率先更新成了11。
4. 線程1開(kāi)始提交更新，首先進(jìn)行A和地址V的實(shí)際值比較，發(fā)現(xiàn)A不等于V的實(shí)際值，提交失敗。
5. 線程1 重新獲取內(nèi)存地址V的當(dāng)前值，并重新計(jì)算想要修改的值。此時(shí)對(duì)線程1來(lái)說(shuō)，A=11，B=12。這個(gè)重新嘗試的過(guò)程被稱為自旋。
6. 這一次比較幸運(yùn)，沒(méi)有其他線程改變地址V的值。線程1進(jìn)行比較，發(fā)現(xiàn)A和地址V的實(shí)際值是相等的。
7. 線程1進(jìn)行交換，把地址V的值替換為B，也就是12.
從思想上來(lái)說(shuō)，synchronized屬于悲觀鎖，悲觀的認(rèn)為程序中的并發(fā)情況嚴(yán)重，所以嚴(yán)防死守，CAS屬于樂(lè)觀鎖，樂(lè)觀地認(rèn)為程序中的并發(fā)情況不那么嚴(yán)重，所以讓線程不斷去重試更新。
在java中除了上面提到的Atomic系列類，以及Lock系列類奪得底層實(shí)現(xiàn)，甚至在JAVA1.6以上版本，synchronized轉(zhuǎn)變?yōu)橹亓考?jí)鎖之前，也會(huì)采用CAS機(jī)制。
下面通過(guò)看下并發(fā)包中的原子操作類AtomicInteger來(lái)看下，如何在不使用鎖的情況下保證線程安全，主要看下getAndIncrement方法，相當(dāng)于i++的操作：
public class AtomicInteger extends Number implements java.io.Serializable {
private volatile int value;
public final int get() {
return value;
}
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
}
首先value使用了volatile修飾，這就保證了他的可見(jiàn)性與有序性，getAndIncrement采用CAS操作，每次從內(nèi)存中讀取數(shù)據(jù)然后將數(shù)據(jù)進(jìn)行+1操作，然后對(duì)原數(shù)據(jù)，+1后的結(jié)果進(jìn)行CAS操作，成功的話返回結(jié)果，否則重試直到成功為止。其中調(diào)用了compareAndSet利用JNI（java navite Interface navite修飾的方法，都是java調(diào)用其他語(yǔ)言的方法來(lái)實(shí)現(xiàn)的）來(lái)完成CPU的操作。其中compareAndSwapInt類似如下邏輯：
if (this == expect) {
this = update
return true;
} else {
return false;
}
this == expect和this = update，這兩個(gè)步驟是如何保證原子性的呢？
JAVA實(shí)現(xiàn)CAS的原理：
compareAndSwapInt是借助C來(lái)調(diào)用CPU底層指令實(shí)現(xiàn)的。
下面從分析比較常用的CPU（intel x86）來(lái)解釋CAS的實(shí)現(xiàn)原理。下面是sun.misc.Unsafe類的compareAndSwapInt()方法的源代碼：
public final native boolean compareAndSwapInt(Object o, long offset,
int expected, int x);
再看下在JDK中依次調(diào)用的C++代碼為：
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
__asm je L0 \
__asm _emit 0xF0 \
__asm L0:
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
// alternative for InterlockedCompareExchange
int mp = os::is_MP();
__asm {
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
LOCK_IF_MP(mp)
cmpxchg dword ptr [edx], ecx
}
}
如上面源代碼所示，程序會(huì)根據(jù)當(dāng)前處理器（CPU）的類型來(lái)決定是否為cmpxchg指令添加lock前綴。如果程序是在多處理器（多核CPU）上運(yùn)行，就為cmpxchg指令加上lock前綴（lock cmpxchg）。反之，如果程序是在單處理器上運(yùn)行，就省略lock前綴（單處理器自身會(huì)維護(hù)單處理器內(nèi)的順序一致性，不需要lock前綴提供的內(nèi)存屏障效果）。也就是說(shuō)，最終會(huì)執(zhí)行到現(xiàn)成的編譯指令cmpxchg，但是這條指令無(wú)法保證操作的原子性，加上lock前綴，也就是最終指令lock cmpxchg使得這一操作為原子操作
CAS的缺點(diǎn)：
1、CPU開(kāi)銷(xiāo)過(guò)大
自旋CAS（不成功，就一直循環(huán)執(zhí)行，直到成功）如果長(zhǎng)時(shí)間不成功，會(huì)給CPU帶來(lái)非常大的執(zhí)行開(kāi)銷(xiāo)。如果JVM能支持處理器提供的pause指令那么效率會(huì)有一定的提升，pause指令有兩個(gè)作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會(huì)消耗過(guò)多的執(zhí)行資源，延遲的時(shí)間取決于具體實(shí)現(xiàn)的版本，在一些處理器上延遲時(shí)間是零。第二它可以避免在退出循環(huán)的時(shí)候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執(zhí)行效率。
2、不能保證代碼塊的原子性
CAS機(jī)制所保證的知識(shí)一個(gè)變量的原子性操作，而不能保證整個(gè)代碼塊的原子性。比如需要保證3個(gè)變量共同進(jìn)行原子性的更新，就不得不使用synchronized了。
3、ABA問(wèn)題
假設(shè)內(nèi)存中有一個(gè)值為A的變量，存儲(chǔ)在地址V中。
此時(shí)有三個(gè)線程想使用CAS的方式更新這個(gè)變量的值，每個(gè)線程的執(zhí)行時(shí)間有略微偏差。線程1和線程2已經(jīng)獲取當(dāng)前值，線程3還未獲取當(dāng)前值。
接下來(lái)，線程1先一步執(zhí)行成功，把當(dāng)前值成功從A更新為B；同時(shí)線程2因?yàn)槟撤N原因被阻塞住，沒(méi)有做更新操作；線程3在線程1更新之后，獲取了當(dāng)前值B。
在之后，線程2仍然處于阻塞狀態(tài)，線程3繼續(xù)執(zhí)行，成功把當(dāng)前值從B更新成了A。
最后，線程2終于恢復(fù)了運(yùn)行狀態(tài)，由于阻塞之前已經(jīng)獲得了“當(dāng)前值A(chǔ)”，并且經(jīng)過(guò)compare檢測(cè)，內(nèi)存地址V中的實(shí)際值也是A，所以成功把變量值A(chǔ)更新成了B。
總結(jié)
CAS與Synchronized的使用情景：
1、對(duì)于資源競(jìng)爭(zhēng)較少（線程沖突較輕）的情況，使用synchronized同步鎖進(jìn)行線程阻塞和喚醒切換以及用戶態(tài)內(nèi)核態(tài)間的切換操作額外浪費(fèi)消耗cpu資源；而CAS基于硬件實(shí)現(xiàn)，不需要進(jìn)入內(nèi)核，不需要切換線程，操作自旋幾率較少，因此可以獲得更高的性能。
2、對(duì)于資源競(jìng)爭(zhēng)嚴(yán)重（線程沖突嚴(yán)重）的情況，CAS自旋的概率會(huì)比較大，從而浪費(fèi)更多的CPU資源，效率低于synchronized。
補(bǔ)充： synchronized在jdk1.6之后，已經(jīng)改進(jìn)優(yōu)化。synchronized的底層實(shí)現(xiàn)主要依靠Lock-Free的隊(duì)列，基本思路是自旋后阻塞，競(jìng)爭(zhēng)切換后繼續(xù)競(jìng)爭(zhēng)鎖，稍微犧牲了公平性，但獲得了高吞吐量。在線程沖突較少的情況下，可以獲得和CAS類似的性能；而線程沖突嚴(yán)重的情況下，性能遠(yuǎn)高于CAS。
參考文章：
https://blog.csdn.net/qq_37113604/article/details/81582784
https://blog.csdn.net/qq_32998153/article/details/79529704
