CAS原理分析，解決銀行轉(zhuǎn)賬ABA難題

什么是CAS

CAS即Compare And Swap的縮寫，翻譯成中文就是比較并交換，其作用是讓CPU比較內(nèi)存中某個(gè)值是否和預(yù)期的值相同，如果相同則將這個(gè)值更新為新值，不相同則不做更新，也就是CAS是原子性的操作(讀和寫兩者同時(shí)具有原子性)，其實(shí)現(xiàn)方式是通過借助C/C 調(diào)用CPU指令完成的，所以效率很高。

CAS的原理很簡(jiǎn)單，這里使用一段Java代碼來描述

public boolean compareAndSwap(int value, int expect, int update) {//如果內(nèi)存中的值value和期望值expect一樣 則將值更新為新值update if (value == expect) { value = update; return true; } else { return false; }}

大致過程是將內(nèi)存中的值、我們的期望值、新值交給CPU進(jìn)行運(yùn)算，如果內(nèi)存中的值和我們的期望值相同則將值更新為新值，否則不做任何操作。這個(gè)過程是在CPU中完成的，這里不好描述CPU的工作過程，就拿Java代碼來描述了。

Unsafe源碼分析

Java是在Unsafe(sun.misc.Unsafe)類實(shí)現(xiàn)CAS的操作，而我們知道Java是無法直接訪問操作系統(tǒng)底層的API的(原因是Java的跨平臺(tái)性限制了Java不能和操作系統(tǒng)耦合)，所以Java并沒有在Unsafe類直接實(shí)現(xiàn)CAS的操作，而是通過JDI(Java Native Interface) 本地調(diào)用C/C 語言來實(shí)現(xiàn)CAS操作的。

Unsafe有很多個(gè)CAS操作的相關(guān)方法，這里舉例幾個(gè)

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

我們拿public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);進(jìn)行分析，這個(gè)方法是比較內(nèi)存中的一個(gè)值(整型)和我們的期望值(var4)是否一樣，如果一樣則將內(nèi)存中的這個(gè)值更新為var5，參數(shù)中的var1是值所在的對(duì)象，var2是值在對(duì)象(var1)中的內(nèi)存偏移量，參數(shù)var1和參數(shù)var2是為了定位出值所在內(nèi)存的地址。

Unsafe.java 在這里發(fā)揮的作用有：

1. 將對(duì)象引用、值在對(duì)象中的偏移量、期望的值和欲更新的新值傳遞給Unsafe.cpp

   
   

2. 如果值更新成功則返回true給開發(fā)者，沒有更新則返回false

   
   

Unsafe.cpp 在這里發(fā)揮的作用有：

1. 接受從Unsafe傳遞過來的對(duì)象引用、偏移量、期望的值和欲更新的新值，根據(jù)對(duì)象引用和偏移量計(jì)算出值的地址，然后將值的地址、期望的值、欲更新的新值傳遞給CPU

   
   

2. 如果值更新成功則返回true給Unsafe.java，沒有更新則返回false

   
   

CPU在這里發(fā)揮的作用：

1. 接受從Unsafe.cpp傳遞過來的地址、期望的值和欲更新的新值，執(zhí)行指令cmpxchg，比較地址中的值是否和期望的值一樣，一樣則將值更新為新的值，不一樣則不做任何操作

   
   

2. 將操作結(jié)果返回給Unsafe.cpp

   
   

CAS的缺點(diǎn)

CAS雖然高效的實(shí)現(xiàn)了原子性操作，但是也存在一些缺點(diǎn)，主要表現(xiàn)在以下三個(gè)方面。

ABA問題

在多線程場(chǎng)景下CAS會(huì)出現(xiàn)ABA問題，關(guān)于ABA問題這里簡(jiǎn)單科普下，例如有2個(gè)線程同時(shí)對(duì)同一個(gè)值(初始值為A)進(jìn)行CAS操作，這三個(gè)線程如下

1. 線程1，期望值為A，欲更新的值為B

   
   

2. 線程2，期望值為A，欲更新的值為B

   
   

線程1搶先獲得CPU時(shí)間片，而線程2因?yàn)槠渌蜃枞?，線程1取值與期望的A值比較，發(fā)現(xiàn)相等然后將值更新為B，然后這個(gè)時(shí)候出現(xiàn)了線程3，期望值為B，欲更新的值為A，線程3取值與期望的值B比較，發(fā)現(xiàn)相等則將值更新為A，此時(shí)線程2從阻塞中恢復(fù)，并且獲得了CPU時(shí)間片，這時(shí)候線程2取值與期望的值A(chǔ)比較，發(fā)現(xiàn)相等則將值更新為B，雖然線程2也完成了操作，但是線程2并不知道值已經(jīng)經(jīng)過了A->B->A的變化過程。

ABA問題帶來的危害：

小明在提款機(jī)，提取了50元，因?yàn)樘峥顧C(jī)問題，有兩個(gè)線程，同時(shí)把余額從100變?yōu)?0
線程1（提款機(jī)）：獲取當(dāng)前值100，期望更新為50，
線程2（提款機(jī)）：獲取當(dāng)前值100，期望更新為50，
線程1成功執(zhí)行，線程2某種原因block了，這時(shí)，某人給小明匯款50
線程3（默認(rèn)）：獲取當(dāng)前值50，期望更新為100，
這時(shí)候線程3成功執(zhí)行，余額變?yōu)?00，
線程2從Block中恢復(fù)，獲取到的也是100，compare之后，繼續(xù)更新余額為50?。。?br /> 此時(shí)可以看到，實(shí)際余額應(yīng)該為100（100-50 50），但是實(shí)際上變?yōu)榱?0（100-50 50-50）這就是ABA問題帶來的成功提交。

解決方法：在變量前面加上版本號(hào)，每次變量更新的時(shí)候變量的版本號(hào)都1，即A->B->A就變成了1A->2B->3A。

循環(huán)時(shí)間長(zhǎng)開銷大

如果CAS操作失敗，就需要循環(huán)進(jìn)行CAS操作(循環(huán)同時(shí)將期望值更新為最新的)，如果長(zhǎng)時(shí)間都不成功的話，那么會(huì)造成CPU極大的開銷。

這種循環(huán)也稱為自旋

解決方法：限制自旋次數(shù)，防止進(jìn)入死循環(huán)。

只能保證一個(gè)共享變量的原子操作

CAS的原子操作只能針對(duì)一個(gè)共享變量。

解決方法：如果需要對(duì)多個(gè)共享變量進(jìn)行操作，可以使用加鎖方式(悲觀鎖)保證原子性，或者可以把多個(gè)共享變量合并成一個(gè)共享變量進(jìn)行CAS操作。

CAS的應(yīng)用

我們知道CAS操作是一種無鎖操作，并不會(huì)鎖住共享變量，也就是一種非阻塞的同步機(jī)制，CAS就是樂觀鎖的實(shí)現(xiàn)。

1. 樂觀鎖總是假設(shè)最好的情況，每次去操作數(shù)據(jù)都認(rèn)為不會(huì)被別的線程修改數(shù)據(jù)，所以在每次操作數(shù)據(jù)的時(shí)候都不會(huì)給數(shù)據(jù)加鎖，即在線程對(duì)數(shù)據(jù)進(jìn)行操作的時(shí)候，別的線程不會(huì)阻塞仍然可以對(duì)數(shù)據(jù)進(jìn)行操作，只有在需要更新數(shù)據(jù)的時(shí)候才會(huì)去判斷數(shù)據(jù)是否被別的線程修改過，如果數(shù)據(jù)被修改過則會(huì)拒絕操作并且返回錯(cuò)誤信息給用戶。

   
   

   
   

2. 悲觀鎖總是假設(shè)最壞的情況，每次去操作數(shù)據(jù)時(shí)候都認(rèn)為會(huì)被的線程修改數(shù)據(jù)，所以在每次操作數(shù)據(jù)的時(shí)候都會(huì)給數(shù)據(jù)加鎖，讓別的線程無法操作這個(gè)數(shù)據(jù)，別的線程會(huì)一直阻塞直到獲取到這個(gè)數(shù)據(jù)的鎖。這樣的話就會(huì)影響效率，比如當(dāng)有個(gè)線程發(fā)生一個(gè)很耗時(shí)的操作的時(shí)候，別的線程只是想獲取這個(gè)數(shù)據(jù)的值而已都要等待很久。

   
   

Java利用CAS的樂觀鎖、原子性的特性高效解決了多線程的安全性問題，例如JDK1.8中的集合類ConcurrentHashMap、關(guān)鍵字volatile、ReentrantLock等。