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的操作:
- 從內(nèi)存中讀取數(shù)據(jù) V(100)雕什;
- (在線程中)將數(shù)據(jù) V加10缠俺;
- 將加法的結(jié)果 V1(110)存入內(nèi)存中原來的位置(替換掉舊的 V)。
線程 B 對數(shù)據(jù) V 的操作:
- 從內(nèi)存中讀取數(shù)據(jù) V(100)贷岸;
- (在線程中)將數(shù)據(jù) V 減 10壹士;
- 將減法的結(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 的操作:
- 從內(nèi)存中讀取數(shù)據(jù) V(100)胧洒;
- (在線程中)將數(shù)據(jù) V 加 10;
- 執(zhí)行 CAS 操作墨状,比較第一步讀取的 V 值(100)與現(xiàn)在內(nèi)存中的 V 值是否相等卫漫,若相等則繼續(xù);否則返回執(zhí)行第一步肾砂;
- 將加法的結(jié)果 V1(110)存入內(nèi)存中原來的位置(替換掉舊的 V)列赎。
線程B對數(shù)據(jù)V的操作:
- 從內(nèi)存中讀取數(shù)據(jù) V(100);
- (在線程中)將數(shù)據(jù) V 減 10镐确;
- 執(zhí)行 CAS 操作包吝,比較第一步讀取的 V 值(100)與現(xiàn)在內(nèi)存中的 V 值是否相等,若相等則繼續(xù)源葫;否則返回執(zhí)行第一步诗越;
- 將減法的結(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ù)作媚。
外部鏈接
- [1] 引用自 Wikipedia CAS 詞條:https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2#%E5%AE%9E%E7%8E%B0
文章的純 HTML 版本點此鏈接訪問攘滩。
以上。
個人博客原文地址:https://maphical.cn/link/?t=NG0V6G