前言
在談CAS算法時，我們先來了解一下無鎖的概念。
無鎖分為以下兩大派系：
- 對于樂觀派系而言，它們認為事情總會往好的方向去發展，總是認為壞的情況發生概率特別小，可以無所顧忌的做任何事情；
- 對于悲觀派系而言，它們總會認為發展事態如果不及時控制，以后就無法挽回，即時此種局面不會發生的情況下。
上述兩大派系映射到并發編程中就如同加鎖與無鎖策略，即加鎖是一種悲觀策略，無鎖是一種樂觀策略，因為對于加鎖的并發程序來說，它們總是認為每次訪問共享資源時總會發生沖突，因此必須對每一次數據操作實施加鎖策略。而無鎖則總是假設對共享資源的訪問沒有沖突，線程可以不停執行，無需加鎖，無需等待，一旦發現沖突，無鎖策略則采用一種稱為CAS的技術來保證線程執行的安全性，這項CAS技術就是無鎖策略實現的關鍵。
什么是CAS？
CAS全稱為Compare And Swap即比較并交換，其算法公式如下：
函數公式：CAS(V,E,N)
V：表示要更新的變量
E：表示預期值
N：表示新值
CAS原理圖
如果V值等于E值，則將V的值設為N。若V值和E值不同，則說明已經有其他線程做了更新，則當前線程什么都不做。通俗的理解就是CAS操作需要我們提供一個期望值，當期望值與當前線程的變量值相同時，說明還沒線程修改該值，當前線程可以進行修改，也就是執行CAS操作，但如果期望值與當前線程不符，則說明該值已被其他線程修改，此時不執行更新操作，但可以選擇重新讀取該變量再嘗試再次修改該變量，也可以放棄操作。
原子包 JAVA.util.concurrent.atomic(鎖自旋)
JDK1.5 的原子包：java.util.concurrent.atomic 這個包里面提供了一組原子類。其基本的特性就 是在多線程環境下，當有多個線程同時執行這些類的實例包含的方法時，具有排他性，即當某個 線程進入方法，執行其中的指令時，不會被其他線程打斷，而別的線程就像自旋鎖一樣，一直等到該方法執行完成，才由 JVM 從等待隊列中選擇一個另一個線程進入，這只是一種邏輯上的理解。
相對于對于 synchronized 這種阻塞算法，CAS 是非阻塞算法的一種常見實現。由于一般 CPU 切換時間比 CPU 指令集操作更加長， 所以 J.U.C 在性能上有了很大的提升。如下代碼：
getAndIncrement 采用了 CAS 操作，每次從內存中讀取數據然后將此數據和+1 后的結果進行CAS 操作，如果成功就返回結果，否則重試直到成功為止。而 compareAndSet 利用 JNI 來完成CPU 指令的操作。
ABA問題
CAS 會導致“ABA 問題”。CAS 算法實現一個重要前提需要取出內存中某時刻的數據，而在下時刻比較并替換，那么在這個時間差類會導致數據的變化。
比如說一個線程 one 從內存位置 V 中取出 A，這時候另一個線程 two 也從內存中取出 A，并且two 進行了一些操作變成了 B，然后 two 又將 V 位置的數據變成 A，這時候線程 one 進行 CAS 操作發現內存中仍然是 A，然后 one 操作成功。盡管線程 one 的 CAS 操作成功，但是不代表這個過程就是沒有問題的。
部分樂觀鎖的實現是通過版本號(version)的方式來解決 ABA 問題，樂觀鎖每次在執行數據的修改操作時，都會帶上一個版本號，一旦版本號和數據的版本號一致就可以執行修改操作并對版本號執行+1 操作，否則就執行失敗。因為每次操作的版本號都會隨之增加，所以不會出現 ABA 問題，因為版本號只會增加不會減少。
