CAS算法簡介

  • 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());
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末臭蚁,一起剝皮案震驚了整個(gè)濱河市最铁,隨后出現(xiàn)的幾起案子讯赏,更是在濱河造成了極大的恐慌,老刑警劉巖冷尉,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件漱挎,死亡現(xiàn)場離奇詭異,居然都是意外死亡雀哨,警方通過查閱死者的電腦和手機(jī)磕谅,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來雾棺,“玉大人膊夹,你說我怎么就攤上這事“坪疲” “怎么了放刨?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長嘉栓。 經(jīng)常有香客問我宏榕,道長,這世上最難降的妖魔是什么侵佃? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任麻昼,我火速辦了婚禮,結(jié)果婚禮上馋辈,老公的妹妹穿的比我還像新娘抚芦。我一直安慰自己,他們只是感情好迈螟,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布叉抡。 她就那樣靜靜地躺著,像睡著了一般答毫。 火紅的嫁衣襯著肌膚如雪褥民。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天洗搂,我揣著相機(jī)與錄音消返,去河邊找鬼。 笑死耘拇,一個(gè)胖子當(dāng)著我的面吹牛撵颊,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播惫叛,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼倡勇,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼!你這毒婦竟也來了嘉涌?” 一聲冷哼從身側(cè)響起妻熊,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤夸浅,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后固耘,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體题篷,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年厅目,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了番枚。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡损敷,死狀恐怖葫笼,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情拗馒,我是刑警寧澤路星,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站诱桂,受9級(jí)特大地震影響洋丐,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜挥等,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一友绝、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧肝劲,春花似錦迁客、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至榄檬,卻和暖如春卜范,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背鹿榜。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來泰國打工先朦, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人犬缨。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像棉浸,于是被迫代替她去往敵國和親怀薛。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361