聊聊并發（六）——CAS算法

　　強烈建議讀者看這篇之前，先看這篇 初識JUC 的前兩節，對原子性，原子變量，記憶體可見性有一個初步認識。

　　CAS（Compare and Swap）是一種硬體對并發的支援，針對多處理器操作而設計的處理器中的一種特殊指令，用于管理對共享資料的并發通路，是硬體對于并發操作共享資料的支援。它是一個原子性的操作，對應到CPU指令為cmpxchg。它是一條CPU并發原語。

　　CAS包含了3個操作數：記憶體值V，比較值A，更新值B。當且僅當V == A時，V = B，否則不執行任何操作。

　　CAS算法：當多個線程并發的對主存中的資料進行修改的時候。有且隻有一個線程會成功，其他的都會失敗（同時操作，隻是會失敗而已，并不會被鎖之類的）。

　　CAS是一種無鎖的非阻塞算法，是樂觀鎖的一種實作。不存在上下文切換的問題。

　　CAS比普通同步鎖效率高，原因：CAS算法當這一次不成功的時候，它下一次不會阻塞，也就是它不會放棄CPU的執行權，它可以立即再次嘗試，再去更新。

　　通俗的說：我要将變量 i 由 2 修改為 3。當記憶體中 i == 2，且修改成功，才為成功。若記憶體中 i 由于其他線程的操作已經不是 2 了，那此次我的修改視為失敗。

　　JDK 1.5 以後java.util.concurrent.atomic包下提供了常用的原子變量。它支援單個變量上的無鎖線程安全程式設計。這些原子變量具備以下特點：volatile的記憶體可見性；CAS算法保證資料的原子性。

　　atomic包描述：圖檔來源API文檔

　　代碼示例：原子變量使用

　　分析：很簡單，設定初始值為 2。

　　①由 3 修改成5，而設定初始值記憶體值為2，是以修改失敗，傳回false。

　　②由 2 修改成10，初始值記憶體值為2，是以修改成功，傳回true。

　　這些原子變量底層就是通過CAS算法來保證資料的原子性。

　　源碼示例：AtomicInteger 類

　　說明：public final boolean compareAndSet(int expect, int update)

　　變量valueOffset：通過靜态代碼塊擷取變量value在記憶體中的偏移位址。

　　變量value：用volatile修飾，這裡展現了"多線程之間的記憶體可見性"。

　　this：即 AtomicInteger 對象本身。

　　很容易了解：就是将目前對象 this 的變量value，由期望值 expect 修改為 update。

　　源碼示例：Unsafe 類

　　Unsafe是CAS的核心類，其所有方法都是native修飾的。也就是說Unsafe類中的方法都直接調用作業系統底層資源執行相應任務，是由C/C++編寫的本地方法。CAS算法的實作，也是由Unsafe類通過調用本地方法直接操作特定記憶體資料來實作的。

　　getAndIncrement()方法能夠在多線程環境保證變量的原子性自增。但源碼中，并沒有加synchronized或者lock鎖，那麼，它是如何保證的呢？其實很簡單：

　　先擷取一次變量的記憶體值，然後通過CAS算法進行比較更新。失敗了就一直不停的重試，是一個循環的過程，這個過程也稱作自旋。

　　這就是為什麼 AtomicInteger 的自增操作具備原子性。

　　（1）ABA問題。

　　（2）循環時間變長：高并發情況下，使用CAS可能會存在一些線程一直循環修改不成功，導緻循環時間變長，這會給CPU帶來很大的執行開銷。由于AtomicInteger中的變量是volatile的，為了保證記憶體可見性，需要保證緩存一緻性，通過總線傳輸資料，當有大量的CAS循環時，會産生總線風暴。

　　（3）隻能保證一個變量的原子操作：如果需要保證多個變量操作的原子性，是做不到的。對于這種情況隻能使用synchronized或者juc包中的Lock工具。

　　代碼示例：示範ABA問題

　　如何了解ABA問題？

　　可能你會覺得，線程 t2 不就是要将"A"改為"C"嘛，雖然中間變化了，但對 t2 也沒影響呀！

　　比如：你的銀行卡裡有10w，中間你領了工資1w，然後，又被扣除還了房貸1w，此時，你的銀行卡裡還是10w。雖然結果沒變，但餘額已經不是原來的餘額了。而且，你一定在意中間你的錢去哪裡了，是以是不一樣的。

　　再比如：對于公司财務來說，可能某一時刻，賬戶是100w，你偷偷挪用了公款20w，後來又悄悄補上了。雖然結果沒變，但中間的記賬明細，其實我們是關心的，因為這個時候你已經犯法了。

　　帶時間戳的原子引用：Java提供了AtomicStampedReference來解決ABA問題。其實其實就是加了版本号，每一次的修改，版本号都 +1。比對的是 記憶體值 + 版本号 是否一緻。

　　代碼示例：解決ABA問題

　　compareAndSet()方法的 4 個參數：

　　expectedReference：表示期望的引用值 　　newReference：表示要修改後的新引用值 　　expectedStamp：表示期望的戳（版本号） 　　newStamp：表示修改後新的戳（版本号）

　　很簡單，維護了一對Pair，裡面除了引用reference，還有一個int類型的戳（版本号）。比較更新的時候，兩個變量都要比較。

　　《阿裡巴巴Java開發手冊》推薦使用LongAdder。

　　AtomicLong，本質上是多個線程同時操作同一個目标資源，有且隻有一個線程執行成功，其他線程都會失敗，不斷重試（自旋），自旋會成為瓶頸。

　　而LongAdder的思想就是把要操作的目标資源[分散]到數組Cell中，每個線程對自己的Cell變量的value進行原子操作，大大降低了失敗的次數。

　　這就是為什麼在高并發場景下，推薦使用LongAdder的原因。

　　參考文檔：https://www.matools.com/api/java8

　　《阿裡巴巴Java開發手冊》百度網盤：https://pan.baidu.com/s/1aWT3v7Efq6wU3GgHOqm-CA 密碼: uxm8

作者：Craftsman-L

出處：https://www.cnblogs.com/originator

本部落格所有文章僅用于學習、研究和交流目的，版權歸作者所有，歡迎非商業性質轉載。

如果本篇部落格給您帶來幫助，請作者喝杯咖啡吧！點選下面打賞，您的支援是我最大的動力！