- CAS(Compare And Swap)算法是一條原子的CPU指令(Atomic::cmpxchg(x, addr, e) == e;)抽高,需要三個(gè)操作數(shù):變量的內(nèi)存地址(或者是偏移量valueOffset) V 截汪,預(yù)期值 A 和更新值 B颁独,CAS指令執(zhí)行時(shí):當(dāng)且僅當(dāng)對(duì)象偏移量V上的值和預(yù)期值A(chǔ)相等時(shí),才會(huì)用更新值B更新V內(nèi)存上的值,否則不執(zhí)行更新。但是無論是否更新了V內(nèi)存上的值炉抒,最終都會(huì)返回V內(nèi)存上的舊值。
1. 為什么使用CAS代替synchronized
- synchronized加鎖稚叹,同一時(shí)間段只允許一個(gè)線程訪問焰薄,能夠保證一致性但是并發(fā)性下降拿诸。而是用CAS算法使用do-while不斷判斷而沒有加鎖(實(shí)際是一個(gè)自旋鎖),保證一致性和并發(fā)性塞茅。
- 原子性保證:CAS算法依賴于rt.jar包下的sun.misc.Unsafe類亩码,該類中的所有方法都是native修飾的,直接調(diào)用操作系統(tǒng)底層資源執(zhí)行相應(yīng)的任務(wù)野瘦。
// unsafe.class
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
// 獲取對(duì)象var1描沟,偏移量為var2地址上的值,并賦值給var5
var5 = this.getIntVolatile(var1, var2);
/**
* 再次獲取對(duì)象var1鞭光,偏移量var2地址上的值吏廉,并和var5進(jìn)行比較:
* - 如果不相等,返回false惰许,繼續(xù)執(zhí)行do-while循環(huán)
* - 如果相等席覆,將返回的var5數(shù)值和var4相加并返回
*/
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
// 最終總是返回對(duì)象var1,偏移量為var2地址上的值汹买,即上述所說的V佩伤。
return var5;
}
- 內(nèi)存可見性和禁止指令重排序的保證:AtomicXxx類中的成員變量value是由volatile修飾的:private volatile int value;上一小節(jié)中已經(jīng)介紹過。
2. CAS算法的缺點(diǎn)
- do-while循環(huán)晦毙,如果CAS失敗就會(huì)一直進(jìn)行嘗試生巡,即一直在自旋,導(dǎo)致CPU開銷见妒,這也是自旋鎖的缺點(diǎn)孤荣;
- 只能保證一個(gè)共享變量的原子操作,如果操作多個(gè)共享變量則需要加鎖實(shí)現(xiàn)须揣;
- ABA問題:如果一個(gè)線程在初次讀取時(shí)的值為A垃环,并且在準(zhǔn)備賦值的時(shí)候檢查該值仍然是A,但是可能在這兩次操作之間返敬,有另外一個(gè)線程現(xiàn)將變量的值改成了B,然后又將該值改回為A寥院,那么CAS會(huì)誤認(rèn)為該變量沒有變化過劲赠。
3. ABA問題解決方案
- 可以使用AtomicStampedReference或者AtomicMarkableReference來解決CAS的ABA問題,思路類似于SVN版本號(hào)秸谢,SpringBoot熱部署中trigger.txt:
- AtomicStampedReference解決方案:每次修改都會(huì)讓stamp值加1凛澎,類似于版本控制號(hào)
/**
* ABA問題解決方案,AtomicStampedReference
*
* @author sherman
*/
public class AtomicStampedReferenceABA {
private static AtomicReference<Integer> ar = new AtomicReference<>(0);
private static AtomicStampedReference<Integer> asr =
new AtomicStampedReference<>(0, 1);
public static void main(String[] args) {
System.out.println("=============演示ABA問題(AtomicReference)===========");
new Thread(() -> {
ar.compareAndSet(0, 1);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
ar.compareAndSet(1, 0);
System.out.println(Thread.currentThread().getName() + "進(jìn)行了一次ABA操作");
}, "子線程").start();
try {
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean res = ar.compareAndSet(0, 100);
if (res) {
System.out.println("main成功修改, 未察覺到子線程進(jìn)行了ABA操作");
}
System.out.println("=============解決ABA問題(AtomicStampReference)===========");
new Thread(() -> {
int curStamp = asr.getStamp();
System.out.println("當(dāng)前stamp: " + curStamp);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
asr.compareAndSet(0, 1, curStamp, curStamp + 1);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
asr.compareAndSet(1, 0, asr.getStamp(), asr.getStamp() + 1);
}, "t1").start();
new Thread(() -> {
int curStamp = asr.getStamp();
System.out.println("當(dāng)前stamp: " + curStamp);
try {
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean result = asr.compareAndSet(0, 100, curStamp, curStamp + 1);
if (!result) {
System.out.println("修改失敗! 預(yù)期stamp: " + curStamp + ", 實(shí)際stamp: " + asr.getStamp());
}
}, "t2").start();
}
}
- AtomicMarkableReference:如果不關(guān)心引用變量中途被修改了多少次估蹄,而只關(guān)心是否被修改過塑煎,可以使用AtomicMarkableReference:
/**
* ABA問題解決方案,AtomicMarkableReference
*
* @author sherman
*/
public class AtomicMarkableReferenceABA {
private static AtomicMarkableReference<Integer> amr = new AtomicMarkableReference<>(0, false);
public static void main(String[] args) {
new Thread(() -> {
amr.compareAndSet(0, 1, false, true);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
amr.compareAndSet(1, 0, true, true);
System.out.println("子線程進(jìn)行了ABA修改!");
}, "子線程").start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean res = amr.compareAndSet(0, 100, false, true);
if (!res) {
System.out.println("修改失敗! 當(dāng)前isMarked: " + amr.isMarked());
}
}
}
3.3 補(bǔ)充:CAS算法實(shí)際使用
在Spring容器刷新方法 refresh() 方法中:obtainFreshBeanFactory()->refreshBeanFactory()【GenericApplicationContext實(shí)現(xiàn)類】:
@Override
protected final void refreshBeanFactory() throws IllegalStateException {
// cas算法
// private final AtomicBoolean refreshed = new AtomicBoolean();
if (!this.refreshed.compareAndSet(false, true)) {
throw new IllegalStateException(
"GenericApplicationContext does not support multiple refresh attempts: just call 'refresh' once");
}
this.beanFactory.setSerializationId(getId());
}