什么是CAS(Compare and Swap)

CAS(Compare And Swap)是一種原子操作翠拣,用于保證在無鎖情況下的數(shù)據(jù)一致性的問題摆出。在無鎖情況下,假設(shè)有兩個線程 A 和 B濒旦,他們都讀取某一個值 V,修改后再存回內(nèi)存中再登,當它們并行執(zhí)行時疤估,就可能會引起數(shù)據(jù) V 的不一致問題。

CAS 的具體操作是比較和替換霎冯,即第一步比較指定值和內(nèi)存中的值是否一致,若一致則使用新值對內(nèi)存值進行替換钞瀑。

不一致問題的舉例

假設(shè)有兩個線程 A 和 B沈撞,它們分別對數(shù)據(jù) V(值為100)執(zhí)行加 10 和減 10 的操作,代碼執(zhí)行過程如下:

線程A對數(shù)據(jù)V的操作:

  1. 從內(nèi)存中讀取數(shù)據(jù) V(100)雕什;
  2. (在線程中)將數(shù)據(jù) V加10缠俺;
  3. 將加法的結(jié)果 V1(110)存入內(nèi)存中原來的位置(替換掉舊的 V)。

線程 B 對數(shù)據(jù) V 的操作:

  1. 從內(nèi)存中讀取數(shù)據(jù) V(100)贷岸;
  2. (在線程中)將數(shù)據(jù) V 減 10壹士;
  3. 將減法的結(jié)果 V2(90)存入內(nèi)存中原來的位置(替換掉舊的 V)。

假設(shè)這兩個線程并發(fā)執(zhí)行偿警,且 A 首先獲得 CPU 時間片躏救,在 A 的 CPU 時間內(nèi),它先讀取數(shù)據(jù) V 的值,并將其進行了加法操作盒使,獲得數(shù)據(jù) V1(110)崩掘。此時,A 的 CPU 時間片結(jié)束少办,線程 B 開始執(zhí)行苞慢。B 將數(shù)據(jù) V 讀入(此時數(shù)據(jù)V未被改動),并執(zhí)行了減法操作英妓,獲得數(shù)據(jù) V2(90)挽放。此時,B 的 CPU 時間片結(jié)束蔓纠,線程 A 繼續(xù)執(zhí)行辑畦,A 將 V1(110)存入內(nèi)存,A 線程結(jié)束贺纲。B 繼續(xù)執(zhí)行航闺,B 將 V2(90)存入內(nèi)存,B 線程結(jié)束猴誊。

我們可以看到潦刃,此時內(nèi)存中的數(shù)據(jù) V 已經(jīng)變成了 V2(90),與我們原先以為的100(加十減十)預(yù)期不同懈叹,造成了數(shù)據(jù)不一致的問題乖杠。

使用CAS解決數(shù)據(jù)不一致問題

CAS 可以用于解決上述數(shù)據(jù)不一致問題,假設(shè)線程 A 和 B 都使用了 CAS 方式澄成,那么他們的執(zhí)行步驟為:

線程 A 對數(shù)據(jù) V 的操作:

  1. 從內(nèi)存中讀取數(shù)據(jù) V(100)胧洒;
  2. (在線程中)將數(shù)據(jù) V 加 10;
  3. 執(zhí)行 CAS 操作墨状,比較第一步讀取的 V 值(100)與現(xiàn)在內(nèi)存中的 V 值是否相等卫漫,若相等則繼續(xù);否則返回執(zhí)行第一步肾砂;
  4. 將加法的結(jié)果 V1(110)存入內(nèi)存中原來的位置(替換掉舊的 V)列赎。

線程B對數(shù)據(jù)V的操作:

  1. 從內(nèi)存中讀取數(shù)據(jù) V(100);
  2. (在線程中)將數(shù)據(jù) V 減 10镐确;
  3. 執(zhí)行 CAS 操作包吝,比較第一步讀取的 V 值(100)與現(xiàn)在內(nèi)存中的 V 值是否相等,若相等則繼續(xù)源葫;否則返回執(zhí)行第一步诗越;
  4. 將減法的結(jié)果 V2(90)存入內(nèi)存中原來的位置(替換掉舊的 V)。

流程修改后息堂,在執(zhí)行過程中嚷狞,當 A 線程執(zhí)行結(jié)束后,內(nèi)存中的值已經(jīng)變?yōu)?V1(110),線程B在存入新的值之前首先比較 V1 是否與 V 相同感耙,因為內(nèi)存中的值已經(jīng)修改褂乍,所以線程B需要重新執(zhí)行讀取操作,從第一步重新執(zhí)行即硼,將 V1(110)減 10 在存入內(nèi)存逃片,得到 V(100)與預(yù)期一致,從而確保了數(shù)據(jù)的一致問題只酥。

實現(xiàn)

CAS 操作基于 CPU 提供的原子操作指令實現(xiàn)褥实。對于 Intel X86 處理器,可通過在匯編指令前增加 LOCK 前綴來鎖定系統(tǒng)總線裂允,使系統(tǒng)總線在匯編指令執(zhí)行時無法訪問相應(yīng)的內(nèi)存地址损离。而各個編譯器根據(jù)這個特點實現(xiàn)了各自的原子操作函數(shù)。[1]

  • C語言绝编,C11 的頭文件 stdatomic.h僻澎。由 GNU 提供了對應(yīng)的 __sync 系列函數(shù)完成原子操作。
  • C++11十饥,STL 提供了 atomic 系列函數(shù)窟勃。
  • JAVA,sun.misc.Unsafe 提供了 compareAndSwap 系列函數(shù)逗堵。
  • C#秉氧,通過 Interlocked 方法實現(xiàn)。
  • Go蜒秤, 通過 import “sync/atomic” 包實現(xiàn)汁咏。
  • Windows,通過 Windows API 實現(xiàn)了 InterlockedCompareExchangeXYZ 系列函數(shù)作媚。

外部鏈接

文章的純 HTML 版本點此鏈接訪問攘滩。

以上。

個人博客原文地址:https://maphical.cn/link/?t=NG0V6G

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖显沈,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異熄攘,居然都是意外死亡嘁信,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門抡爹,熙熙樓的掌柜王于貴愁眉苦臉地迎上來掩驱,“玉大人,你說我怎么就攤上這事∨费ǎ” “怎么了民逼?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長涮帘。 經(jīng)常有香客問我拼苍,道長,這世上最難降的妖魔是什么调缨? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任疮鲫,我火速辦了婚禮,結(jié)果婚禮上弦叶,老公的妹妹穿的比我還像新娘俊犯。我一直安慰自己,他們只是感情好伤哺,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布燕侠。 她就那樣靜靜地躺著,像睡著了一般立莉。 火紅的嫁衣襯著肌膚如雪绢彤。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天桃序,我揣著相機與錄音杖虾,去河邊找鬼。 笑死媒熊,一個胖子當著我的面吹牛奇适,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播芦鳍,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼嚷往,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了柠衅?” 一聲冷哼從身側(cè)響起皮仁,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎菲宴,沒想到半個月后贷祈,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡喝峦,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年势誊,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片谣蠢。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡粟耻,死狀恐怖查近,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情挤忙,我是刑警寧澤霜威,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站册烈,受9級特大地震影響戈泼,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜茄厘,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一矮冬、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧次哈,春花似錦胎署、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至哀卫,卻和暖如春巨坊,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背此改。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工趾撵, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人共啃。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓占调,卻偏偏與公主長得像,于是被迫代替她去往敵國和親移剪。 傳聞我的和親對象是個殘疾皇子究珊,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • iOS網(wǎng)絡(luò)架構(gòu)討論梳理整理中。纵苛。剿涮。 其實如果沒有APIManager這一層是沒法使用delegate的,畢竟多個單...
    yhtang閱讀 5,208評論 1 23
  • 鎖的代價 鎖是用來做并發(fā)最簡單的方式攻人,當然其代價也是最高的取试。內(nèi)核態(tài)的鎖在鎖的時候需要操作系統(tǒng)進行一次上下文切換,加...
    cgw丶閱讀 3,242評論 0 5
  • java.util.concurrent包完全建立在CAS之上怀吻。 AQS瞬浓,非阻塞數(shù)據(jù)結(jié)構(gòu)和原子變量類(java.u...
    光劍書架上的書閱讀 5,634評論 0 8
  • 九種基本數(shù)據(jù)類型的大小,以及他們的封裝類烙博。(1)九種基本數(shù)據(jù)類型和封裝類 (2)自動裝箱和自動拆箱 什么是自動裝箱...
    關(guān)瑋琳linSir閱讀 1,891評論 0 47
  • Java8張圖 11瑟蜈、字符串不變性 12、equals()方法渣窜、hashCode()方法的區(qū)別 13铺根、...
    Miley_MOJIE閱讀 3,709評論 0 11