[導(dǎo)讀]簡(jiǎn)介 CAS的全稱是compare and swap，它是java同步類(lèi)的基礎(chǔ)，java.util.concurrent中的同步類(lèi)基本上都是使用CAS來(lái)實(shí)現(xiàn)其原子性的。 CAS的原理其實(shí)很簡(jiǎn)單，為了保證在多線程環(huán)境下我們的更新是符合預(yù)期的，或者說(shuō)一個(gè)線程在更新某個(gè)對(duì)象的時(shí)候，沒(méi)有其他的線程
CAS的全稱是compare and swap，它是java同步類(lèi)的基礎(chǔ)，java.util.concurrent中的同步類(lèi)基本上都是使用CAS來(lái)實(shí)現(xiàn)其原子性的。
CAS的原理其實(shí)很簡(jiǎn)單，為了保證在多線程環(huán)境下我們的更新是符合預(yù)期的，或者說(shuō)一個(gè)線程在更新某個(gè)對(duì)象的時(shí)候，沒(méi)有其他的線程對(duì)該對(duì)象進(jìn)行修改。在線程更新某個(gè)對(duì)象（或值）之前，先保存更新前的值，然后在實(shí)際更新的時(shí)候傳入之前保存的值，進(jìn)行比較，如果一致的話就進(jìn)行更新，否則失敗。
注意，CAS在java中是用native方法來(lái)實(shí)現(xiàn)的，利用了系統(tǒng)本身提供的原子性操作。
那么CAS在使用中會(huì)有什么問(wèn)題呢？
一般來(lái)說(shuō)CAS如果設(shè)計(jì)的不夠完美的話，可能會(huì)產(chǎn)生ABA問(wèn)題，而ABA問(wèn)題又可以分為兩類(lèi)，我們先看來(lái)看一類(lèi)問(wèn)題。
我們考慮下面一種ABA的情況：
在多線程的環(huán)境中，線程a從共享的地址X中讀取到了對(duì)象A。
在線程a準(zhǔn)備對(duì)地址X進(jìn)行更新之前，線程b將地址X中的值修改為了B。
接著線程b將地址X中的值又修改回了A。
最新線程a對(duì)地址X執(zhí)行CAS，發(fā)現(xiàn)X中存儲(chǔ)的還是對(duì)象A，對(duì)象匹配，CAS成功。
上面的例子中CAS成功了，但是實(shí)際上這個(gè)CAS并不是原子操作，如果我們想要依賴CAS來(lái)實(shí)現(xiàn)原子操作的話可能就會(huì)出現(xiàn)隱藏的bug。
第一類(lèi)問(wèn)題的關(guān)鍵就在2和3兩步。這兩步我們可以看到線程b直接替換了內(nèi)存地址X中的內(nèi)容。
在擁有自動(dòng)GC環(huán)境的編程語(yǔ)言，比如說(shuō)java中，2，3的情況是不可能出現(xiàn)的，因?yàn)樵趈ava中，只要兩個(gè)對(duì)象的地址一致，就表示這兩個(gè)對(duì)象是相等的。
2，3兩步可能出現(xiàn)的情況就在像C++這種，不存在自動(dòng)GC環(huán)境的編程語(yǔ)言中。
因?yàn)榭梢宰约嚎刂茖?duì)象的生命周期，如果我們從一個(gè)list中刪除掉了一個(gè)對(duì)象，然后又重新分配了一個(gè)對(duì)象，并將其add back到list中去，那么根據(jù) MRU memory allocation算法，這個(gè)新的對(duì)象很有可能和之前刪除對(duì)象的內(nèi)存地址是一樣的。這樣就會(huì)導(dǎo)致ABA的問(wèn)題。
如果我們?cè)趽碛凶詣?dòng)GC的編程語(yǔ)言中，那么是否仍然存在CAS問(wèn)題呢？
考慮下面的情況，有一個(gè)鏈表里面的數(shù)據(jù)是A->B->C,我們希望執(zhí)行一個(gè)CAS操作，將A替換成D，生成鏈表D->B->C。
考慮下面的步驟：
線程a讀取鏈表頭部節(jié)點(diǎn)A。
線程b將鏈表中的B節(jié)點(diǎn)刪掉，鏈表變成了A->C
線程a執(zhí)行CAS操作，將A替換從D。
最后我們的到的鏈表是D->C，而不是D->B->C。
問(wèn)題出在哪呢？CAS比較的節(jié)點(diǎn)A和最新的頭部節(jié)點(diǎn)是不是同一個(gè)節(jié)點(diǎn)，它并沒(méi)有關(guān)心節(jié)點(diǎn)A在步驟1和3之間是否內(nèi)容發(fā)生變化。
我們舉個(gè)例子：
上面的例子中，我們使用了AtomicReference的CAS方法來(lái)判斷對(duì)象是否發(fā)生變化。在CAS b和a之后，我們將a的name進(jìn)行了修改，我們看下最后的輸出結(jié)果：
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
三個(gè)CAS的結(jié)果都是true。說(shuō)明CAS確實(shí)比較的兩者是否為同一對(duì)象，對(duì)其中內(nèi)容的變化并不關(guān)心。
第二類(lèi)問(wèn)題可能會(huì)導(dǎo)致某些集合類(lèi)的操作并不是原子性的，因?yàn)槟悴⒉荒鼙ＷC在CAS的過(guò)程中，有沒(méi)有其他的節(jié)點(diǎn)發(fā)送變化。
第一類(lèi)問(wèn)題在存在自動(dòng)GC的編程語(yǔ)言中是不存在的，我們主要看下怎么在C++之類(lèi)的語(yǔ)言中解決這個(gè)問(wèn)題。
根據(jù)官方的說(shuō)法，第一類(lèi)問(wèn)題大概有四種解法：
使用中間節(jié)點(diǎn) – 使用一些不代表任何數(shù)據(jù)的中間節(jié)點(diǎn)來(lái)表示某些節(jié)點(diǎn)是標(biāo)記被刪除的。
使用自動(dòng)GC。
使用hazard pointers – hazard pointers 保存了當(dāng)前線程正在訪問(wèn)的節(jié)點(diǎn)的地址，在這些hazard pointers中的節(jié)點(diǎn)不能夠被修改和刪除。
使用read-copy update (RCU) – 在每次更新的之前，都做一份拷貝，每次更新的是拷貝出來(lái)的新結(jié)構(gòu)。
第二類(lèi)問(wèn)題其實(shí)算是整體集合對(duì)象的CAS問(wèn)題了。一個(gè)簡(jiǎn)單的解決辦法就是每次做CAS更新的時(shí)候再添加一個(gè)版本號(hào)。如果版本號(hào)不是預(yù)期的版本，就說(shuō)明有其他的線程更新了集合中的某些節(jié)點(diǎn)，這次CAS是失敗的。
我們舉個(gè)AtomicStampedReference的例子：
AtomicStampedReference的compareAndSet方法，多出了兩個(gè)參數(shù)，分別是expectedStamp和newStamp，兩個(gè)參數(shù)都是int型的，需要我們手動(dòng)傳入。
ABA問(wèn)題其實(shí)是由兩類(lèi)問(wèn)題組成的，需要我們分開(kāi)來(lái)對(duì)待和解決。
特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
欲知詳情，請(qǐng)下載word文檔
下載文檔
本站聲明： 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀點(diǎn)，本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專(zhuān)欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請(qǐng)及時(shí)聯(lián)系本站刪除。
