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