一、CAS算法的內(nèi)容
1、基本思想和步驟
CAS算法的基本思想是，先比較內(nèi)存M中的值與寄存器A中的值（舊的預(yù)期值，expectValue）是否
相等，如果相等，則將寄存器B中的值（新值，swapValue）寫入內(nèi)存；如果不相等，則不做任何操作。
整個(gè)過程是原子的，不會(huì)被其他并發(fā)操作中斷。
這里雖然涉及到內(nèi)存與寄存器值的“交換”，但更多時(shí)候我們并不關(guān)心寄存器中存的值是什么，而是更
關(guān)心內(nèi)存中的數(shù)值（內(nèi)存中存的值即變量的值）。所以這里的“交換”可以不用看成交換，直接看成
是賦值操作就行，即把寄存器B中的值直接賦值到內(nèi)存M中了。
CAS 操作包括三個(gè)操作數(shù)：一個(gè)內(nèi)存位置（通常是共享變量）、期望的值和新值。CAS 操作的執(zhí)行過程如下：
- 讀取內(nèi)存位置的當(dāng)前值。
- 比較當(dāng)前值與期望的值是否相等。
- 如果相等，將新值寫入內(nèi)存位置；否則，操作失敗。
2、CAS偽代碼（如果把CAS想象成一個(gè)函數(shù)）
boolean CAS(address, expectValue, swapValue) { if (&address == expectedValue) {
&address = swapValue; return true; } return false; }
上面給出的代碼只是偽代碼，并不是真實(shí)的CAS代碼。事實(shí)上，CAS操作是一條由CPU硬件支持的、
原子的硬件指令，這一條指令就能完成上述這一段代碼的功能。
“一條指令”和“一段代碼”的最大區(qū)別在于原子性。上述這一段偽代碼不是原子的，運(yùn)行過程中可能隨著線
程的調(diào)度有概率產(chǎn)生線程安全問題；但原子的指令不會(huì)有線程安全問題。
同時(shí)，CAS也不會(huì)有內(nèi)存可見性的問題，內(nèi)存可見性相當(dāng)于是編譯器把一系列指令的進(jìn)行了調(diào)整，把讀
內(nèi)存的指令調(diào)整成讀寄存器的指令。但CAS本身就是指令級(jí)別讀取內(nèi)存的操作，所以不會(huì)有內(nèi)存可見性帶來的線程不安全問題。
因此，CAS可以做到不加鎖也能一定程度地保證線程安全。這樣就引申出基于CAS算法的一系列操作。
二、CAS算法的應(yīng)用
CAS可以用于實(shí)現(xiàn)無鎖編程。實(shí)現(xiàn)原子類和實(shí)現(xiàn)自旋鎖就是無鎖編程的其中兩個(gè)方式。
1、實(shí)現(xiàn)原子類
標(biāo)準(zhǔn)庫 java.util.concurrent.atomic 包中有很多類使用了很高效的機(jī)器級(jí)指令（而不是使用鎖） 來
保證其他操作的原子性。
例如， Atomiclnteger 類提供了方法 incrementAndGet、getAndIncrement 和 decrementAndGet、
getAndDecrement，它們分別以原子方式將一個(gè)整數(shù)自增或自減。
AtomicIntegernum=newAtomicInteger(0);Threadt1=newThread(()->{//num++num.getAndIncrement();
//++numnum.incrementAndGet();//num--num.getAndDecrement();//--numnum.decrementAndGet();});
例如，可以安全地生成數(shù)值序列，如下所示：
importjava。util。concurrent。atomic。AtomicInteger；publicclassTest2{publicstaticvoidmain（String［］args）
throwsInterruptedException{AtomicIntegernum=newAtomicInteger（0）；Threadt1=newThread
（（）->{for（inti=0；i<50000；i++）{//num++num。getAndIncrement（）；}}）；
Threadt2=newThread（（）->{for（inti=0；i<50000；i++）{//num++num。getAndIncrement（）；}}）；
t1。start（）；t2。start（）；t1。join（）；t2。join（）；System。out。println（num。get（））；}}
運(yùn)行結(jié)果：最終num的值正好是100000
這是因?yàn)?nbsp;getAndIncrement() 方法以原子的方式獲得 num 的值，并將 num 自增。也就是說， 獲得值、 增 1 并設(shè)置
然后生成新值的操作不會(huì)中斷。可以保證即使是多個(gè)線程并發(fā)地訪問同一個(gè)實(shí)例，也會(huì)計(jì)算并返回正確的值。
通過查看源碼可以發(fā)現(xiàn)，getAndIncrement() 方法并沒有用到加鎖（synchronized）：
但再進(jìn)入 getAndAddInt 方法可以發(fā)現(xiàn)，其中用到了 CAS 算法：
再進(jìn)入 compareAndSwapInt 方法后會(huì)發(fā)現(xiàn)，這是一個(gè)由 native 修飾的方法。CAS算法的實(shí)現(xiàn)依賴于底層硬件和操
作系統(tǒng)提供的原子操作支持，因此它是更偏向底層的操作。
補(bǔ)充 - 與之形成對(duì)比的線程不安全的案例是：
下面就是一個(gè)線程不安全的例子。該代碼中創(chuàng)建了一個(gè)counter變量，同時(shí)分別創(chuàng)建了兩個(gè)線程t1和t2，讓這兩
個(gè)線程針對(duì)同一個(gè)counter令其自增5w次。
classCounter{privateintcount=0；//讓count增加publicvoidadd（）{count++；}//獲得count
publicintget（）{returncount；}}publicclassTest{publicstaticvoidmain（String［］args）throwsInterruptedException
{Countercounter=newCounter（）；//創(chuàng)建兩個(gè)線t1和t2，讓這兩個(gè)線程分別對(duì)同一個(gè)counter自增5w次
Threadt1=newThread（（）->{for（inti=0；i<50000；i++）{counter。add（）；}}）；
Threadt2=newThread（（）->{for（inti=0；i<50000；i++）{counter。add（）；}}）；t1。start（）；
t2。start（）；//main線程等待兩個(gè)線程都執(zhí)行結(jié)束，然后再查看結(jié)果t1。join（）；t2。join（）；System。out。
println（counter。get（））；}}
按理來說，最終輸出counter的結(jié)果應(yīng)當(dāng)是10w次。但我們運(yùn)行程序后發(fā)現(xiàn)，不但結(jié)果不是10w，而且每次
運(yùn)行的結(jié)果都不一樣——實(shí)際結(jié)果看起來像一個(gè)隨機(jī)值。
由于線程的隨即調(diào)度，count++這一語句并不是原子的，它本質(zhì)上是由3個(gè)CPU指令構(gòu)成：
- load。把內(nèi)存中的數(shù)據(jù)讀取到CPU寄存器中。
- add。把寄存器中的值進(jìn)行 +1 運(yùn)算。
- save。把寄存器中的值寫回到內(nèi)存中。
CPU需要分三步走才能完成這一自增操作。如果是單線程中，這三步?jīng)]有任何問題；但在多線程編程中，情況就會(huì)不同。
由于多線程調(diào)度順序是不確定的，實(shí)際執(zhí)行過程中，這倆線程的count++操作的指令排列順序會(huì)有很多種不同的可能：
上面只列出了非常小的一部分可能，實(shí)際中有更多可能的情況。而不同的排列順序下，程序執(zhí)行的結(jié)果可能
是截然不同的！比如以下兩種情況的執(zhí)行過程：
因此， 由于實(shí)際中線程的調(diào)度順序是無序的，我們并不能確定這倆線程在自增過程中經(jīng)歷了什么，也不能確定到底有多少
次指令是“順序執(zhí)行”的，有多少次指令是“交錯(cuò)執(zhí)行”的。最終得到的結(jié)果也就成了變化的數(shù)值，count一定是小于等于10w的
（來自文章：Java多線程基礎(chǔ)-6：線程安全問題及解決措施）
*偽代碼實(shí)現(xiàn)原子類
代碼：
classAtomicInteger{privateintvalue；publicintgetAndIncrement（）{intoldValue=value；
while（CAS （value，oldValue，oldValue+1）！=true）{oldValue=value；}returnoldValue；}}
上面代碼中，雖然看似剛剛把 value 賦值給 oldValue 后，就緊接著比較 value 和 oldvalue是否相等，但比較結(jié)果依然是可能不相等的。
因?yàn)檫@是在多線程的環(huán)境下。value 是成員變量，如果兩個(gè)線程同時(shí)調(diào)用 getAndIncrement 方法，就有可能出現(xiàn)不相等的情況。
其實(shí)此處的 CAS 就是在確認(rèn)當(dāng)前 value 是否變過。如果沒變過，才能自增；如果變過了，就先更新值，再自增。
之前的線程不安全，有一個(gè)很大的原因就是一個(gè)線程不能及時(shí)感知到另一個(gè)線程對(duì)內(nèi)存的修改：
之前線程不安全，是因?yàn)閠1在自增的時(shí)候先讀后自增。此時(shí)在t1自增之前，t2已經(jīng)自增過了，t1是卻還是在一開始的0的基礎(chǔ)上
自增的，此時(shí)就會(huì)出現(xiàn)問題。
但CAS操作使得t1在執(zhí)行自增之前，先比較一下寄存器和內(nèi)存中的值是否一致，只有一致了才執(zhí)行自增，否則就重新將內(nèi)存中
的值向寄存器同步一下。
這個(gè)操作不涉及阻塞等待，因此會(huì)比之前加鎖的方案快很多。
2、實(shí)現(xiàn)自旋鎖
自旋鎖是一種忙等待鎖的機(jī)制。當(dāng)一個(gè)線程需要獲取自旋鎖時(shí)，它會(huì)反復(fù)地檢查鎖是否可用，而不是立即被阻塞。如果獲取鎖失敗
（鎖已經(jīng)被其他線程占用），當(dāng)前線程會(huì)立即再嘗試獲取鎖，不斷自旋（空轉(zhuǎn)）等待鎖的釋放，直到獲取到鎖為止。第一次獲取鎖
失敗，第二次的嘗試會(huì)在極短的時(shí)間內(nèi)到來。這樣能保證一旦鎖被其他線程釋放，當(dāng)前線程能第一時(shí)間獲取到鎖。一般樂觀鎖的
情況下（鎖沖突概率低），實(shí)現(xiàn)自旋鎖是比較合適的。
*偽代碼實(shí)現(xiàn)自旋鎖
publicclassSpinLock{privateThreadowner=null；publicvoidlock（）{//通過CAS看當(dāng)前鎖是否被某個(gè)線程持有/
/如果這個(gè)鎖已 經(jīng)被別的線程持有，
那么就自旋等待//如果這個(gè)鎖沒有被別的線程持有，那么就把owner設(shè)為當(dāng)前嘗試加鎖的線程
while（！CAS（this。owner，null，Thread。currentThread（）））{}}publicvoidunlock（）{this。owner=null；}}
三、CAS的ABA問題
CAS的ABA問題是使用CAS時(shí)遇到的一個(gè)經(jīng)典的問題。
已知 CAS 的關(guān)鍵是對(duì)比內(nèi)存和寄存器中的值，看二者是否相同，就是通過這個(gè)比較來判斷內(nèi)存中的值是否發(fā)生過改變。然而，
萬一對(duì)比的時(shí)候是相同的，但其實(shí)內(nèi)存中的值并不是沒變過，而是從A值變成B值后又變回了A值呢？
此時(shí)，有一定概率會(huì)出問題。這樣的情況就叫做ABA問題。CAS只能對(duì)比值是否相同，但不能確定這個(gè)值是否中間發(fā)生過改變。
這就好比我們從某魚上買了一個(gè)手機(jī)，但無法判定這個(gè)手機(jī)是剛出廠的新手機(jī)，還是別人用舊過了之后又翻新過的翻新機(jī)。
1、ABA問題引發(fā)的BUG
其實(shí)大部分的情況下ABA問題影響并不大。但是不排除一些特殊情況：
假設(shè)小明有 100 存款。他想從 ATM 取 50 塊錢。取款機(jī)創(chuàng)建了兩個(gè)線程，并發(fā)地來執(zhí)行 -50
（從賬戶中扣款50塊錢）這一操作。
我們期望兩個(gè)線程中一個(gè)線程執(zhí)行 -50 成功，另一個(gè)線程 -50 失敗。如果使用 CAS 的方式來完成這個(gè)扣款過程，就可能出現(xiàn)問題。
正常的過程
- 存款 100。線程1 獲取到當(dāng)前存款值為 100，期望值更新為 50；線程2 獲取到當(dāng)前存款值為 100，期望值更新為 50。
- 線程1 執(zhí)行扣款成功，存款被改成 50；線程2 阻塞等待中。
- 輪到線程2 執(zhí)行了，發(fā)現(xiàn)當(dāng)前存款為 50，和之前讀到的 100 不相同，執(zhí)行失敗。
異常的過程
- 存款 100。線程1 獲取到當(dāng)前存款值為 100，期望值更新為 50；線程2 獲取到當(dāng)前存款值為 100，期望值更新為 50。
- 線程1 執(zhí)行扣款成功，存款被改成 50。線程2 阻塞等待中。
- 在線程2 執(zhí)行之前，小明的朋友正好給小明轉(zhuǎn)賬了 50，此時(shí)小明賬戶的余額又變成了 100！
- 輪到線程2 執(zhí)行了，發(fā)現(xiàn)當(dāng)前存款為 100， 和之前讀到的 100 相同， 再次執(zhí)行扣款操作。
這個(gè)時(shí)候, 扣款操作被執(zhí)行了兩次！這都是 ABA 問題引起的。
2、解決ABA問題——使用版本號(hào)
ABA 問題的關(guān)鍵是內(nèi)存中共享變量的值會(huì)反復(fù)橫跳。如果約定數(shù)據(jù)只能單方向變化，問題就迎刃而解了。
由此引入“版本號(hào)” 這一概念。約定版本號(hào)只能遞增（每次修改變量時(shí)，都會(huì)增加一個(gè)版本號(hào)）。而且每次 CAS 在對(duì)比的時(shí)候，
對(duì)比的就不是數(shù)值本身，而是對(duì)比版本號(hào)。這樣其他線程在進(jìn)行 CAS 操作時(shí)可以檢查版本號(hào)是否發(fā)生了變化，從而避免 ABA 問題的發(fā)生。
（以版本號(hào)為基準(zhǔn)，而不以變量數(shù)值為基準(zhǔn)。約定了版本號(hào)只能遞增，就不會(huì)出現(xiàn)ABA這樣的反復(fù)橫跳問題。）
不過在實(shí)際情況中，大部分情況下即使遇到了ABA問題，也沒有什么關(guān)系。知曉版本號(hào)可以用來解決ABA問題即可。
| 
