簡(jiǎn)介

在計(jì)算機(jī)科學(xué)中，比較和交換（Conmpare And Swap）是用于實(shí)現(xiàn)多線程同步的原子指令。它將內(nèi)存位置的內(nèi)容與給定值進(jìn)行比較，只有在相同的情況下，將該內(nèi)存位置的內(nèi)容修改為新的給定值。這是作為單個(gè)原子操作完成的。 原子性保證新值基于最新信息計(jì)算; 如果該值在同一時(shí)間被另一個(gè)線程更新，則寫入將失敗。操作結(jié)果必須說明是否進(jìn)行替換; 這可以通過一個(gè)簡(jiǎn)單的布爾響應(yīng)（這個(gè)變體通常稱為比較和設(shè)置），或通過返回從內(nèi)存位置讀取的值來完成。

核心思想

一個(gè) CAS 涉及到以下操作： 我們假設(shè)內(nèi)存中的原數(shù)據(jù)V，舊的預(yù)期值A(chǔ)，需要修改的新值B。

比較 A 與 V 是否相等。（比較） 如果比較相等，將 B 寫入 V。（交換） 返回操作是否成功。 當(dāng)多個(gè)線程同時(shí)對(duì)某個(gè)資源進(jìn)行CAS操作，只能有一個(gè)線程操作成功，但是并不會(huì)阻塞其他線程,其他線程只會(huì)收到操作失敗的信號(hào)?？梢?CAS 其實(shí)是一個(gè)樂觀鎖。

image.png

如上圖中，主存中保存V值，線程中要使用V值要先從主存中讀取V值到線程的工作內(nèi)存A中，然后計(jì)算后變成B值，最后再把B值寫回到內(nèi)存V值中。多個(gè)線程共用V值都是如此操作。CAS的核心是在將B值寫入到V之前要比較A值和V值是否相同，如果不相同證明此時(shí)V值已經(jīng)被其他線程改變，重新將V值賦給A，并重新計(jì)算得到B，如果相同，則將B值賦給V。

如果不使用CAS機(jī)制，看看存在什么問題:

假如V=1，現(xiàn)在Thread1要對(duì)V進(jìn)行加1，Thread2也要對(duì)V進(jìn)行加1，首先Thread1讀取V=1到自己工作內(nèi)存A中此時(shí)A=1，假設(shè)Thread2此時(shí)也讀取V=1到自己的工作內(nèi)存A中，分別進(jìn)行加1操作后，兩個(gè)線程中B的值都為2，此時(shí)寫回到V中時(shí)發(fā)現(xiàn)V的值為2，但是兩個(gè)線程分別對(duì)V進(jìn)行加處理結(jié)果卻只加了1有問題。

CAS 實(shí)現(xiàn)

本文將對(duì) java.util.concurrent.atomic 包下的原子類 AtomicInteger 中的 compareAndSet 方法進(jìn)行分析，就能發(fā)現(xiàn)最終調(diào)用的是 sum.misc.Unsafe 這個(gè)類。 看名稱 Unsafe 就是一個(gè)不安全的類，這個(gè)類是利用了 Java 的類和包在可見性的的規(guī)則中的一個(gè)恰到好處處的漏洞。Unsafe 這個(gè)類為了速度，在Java的安全標(biāo)準(zhǔn)上做出了一定的妥協(xié)。

再往下尋找我們發(fā)現(xiàn) Unsafe的compareAndSwapInt 是 Native 的方法：

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);</pre>

也就是說，這幾個(gè) CAS 的方法應(yīng)該是使用了本地的方法。所以這幾個(gè)方法的具體實(shí)現(xiàn)需要我們自己去 jdk 的源碼中搜索。 最終到搜索 cmpxchg 函數(shù)

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {  // 判斷是否是多核 CPU
  int mp = os::is_MP();
  __asm {    // 將參數(shù)值放入寄存器中
    mov edx, dest    // 注意: dest 是指針類型，這里是把內(nèi)存地址存入 edx 寄存器中
    mov ecx, exchange_value
    mov eax, compare_value    
    // LOCK_IF_MP
    cmp mp, 0
    /*
     * 如果 mp = 0，表明是線程運(yùn)行在單核 CPU 環(huán)境下。此時(shí) je 會(huì)跳轉(zhuǎn)到 L0 標(biāo)記處，
     * 也就是越過 _emit 0xF0 指令，直接執(zhí)行 cmpxchg 指令。也就是不在下面的 cmpxchg 指令
     * 前加 lock 前綴。
     */
    je L0    /*
     * 0xF0 是 lock 前綴的機(jī)器碼，這里沒有使用 lock，而是直接使用了機(jī)器碼的形式。至于這樣做的
     * 原因可以參考知乎的一個(gè)回答：
     *     https://www.zhihu.com/question/50878124/answer/123099923
     */ 
    _emit 0xF0L0:    /*
     * 比較并交換。簡(jiǎn)單解釋一下下面這條指令，熟悉匯編的朋友可以略過下面的解釋:
     *   cmpxchg: 即“比較并交換”指令
     *   dword: 全稱是 double word，在 x86/x64 體系中，一個(gè) 
     *          word = 2 byte，dword = 4 byte = 32 bit
     *   ptr: 全稱是 pointer，與前面的 dword 連起來使用，表明訪問的內(nèi)存單元是一個(gè)雙字單元
     *   [edx]: [...] 表示一個(gè)內(nèi)存單元，edx 是寄存器，dest 指針值存放在 edx 中。
     *          那么 [edx] 表示內(nèi)存地址為 dest 的內(nèi)存單元
     *          
     * 這一條指令的意思就是，將 eax 寄存器中的值（compare_value）與 [edx] 雙字內(nèi)存單元中的值
     * 進(jìn)行對(duì)比，如果相同，則將 ecx 寄存器中的值（exchange_value）存入 [edx] 內(nèi)存單元中。
     */
    cmpxchg dword ptr [edx], ecx
  }
}

總結(jié)一下 JAVA 的 cas 是怎么實(shí)現(xiàn)的：

• java 的 cas 利用的的是 unsafe 這個(gè)類提供的 cas 操作。
• unsafe 的cas 依賴了的是 jvm 針對(duì)不同的操作系統(tǒng)實(shí)現(xiàn)的 Atomic::cmpxchg
• Atomic::cmpxchg 的實(shí)現(xiàn)使用了匯編的 cas 操作，并使用 cpu 硬件提供的 lock信號(hào)保證其原子性

ABA 問題

CAS 由三個(gè)步驟組成，分別是“讀取->比較->寫回”。 考慮這樣一種情況，線程1和線程2同時(shí)執(zhí)行 CAS 邏輯，兩個(gè)線程的執(zhí)行順序如下：

時(shí)刻1：線程1執(zhí)行讀取操作，獲取原值 A，然后線程被切換走 時(shí)刻2：線程2執(zhí)行完成 CAS 操作將原值由 A 修改為 B 時(shí)刻3：線程2再次執(zhí)行 CAS 操作，并將原值由 B 修改為 A 時(shí)刻4：線程1恢復(fù)運(yùn)行，將比較值（compareValue）與原值（oldValue）進(jìn)行比較，發(fā)現(xiàn)兩個(gè)值相等。 然后用新值（newValue）寫入內(nèi)存中，完成 CAS 操作

如上流程，線程1并不知道原值已經(jīng)被修改過了，在它看來并沒什么變化，所以它會(huì)繼續(xù)往下執(zhí)行流程。對(duì)于 ABA 問題，通常的處理措施是對(duì)每一次 CAS 操作設(shè)置版本號(hào)。java.util.concurrent.atomic 包下提供了一個(gè)可處理 ABA 問題的原子類 AtomicStampedReference，具體的實(shí)現(xiàn)這里就不分析了，有興趣的朋友可以自己去看看。

ABA問題的解決辦法

1.在變量前面追加版本號(hào)：每次變量更新就把版本號(hào)加1，則A-B-A就變成1A-2B-3A。 2.atomic包下的AtomicStampedReference類：其compareAndSet方法首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用的該標(biāo)志的值設(shè)置為給定的更新值。

其他問題

CAS除了ABA問題，仍然存在循環(huán)時(shí)間長(zhǎng)開銷大和只能保證一個(gè)共享變量的原子操作

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

自旋CAS如果長(zhǎng)時(shí)間不成功，會(huì)給CPU帶來非常大的執(zhí)行開銷。 如果JVM能支持處理器提供的pause指令那么效率會(huì)有一定的提升，pause指令有兩個(gè)作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會(huì)消耗過多的執(zhí)行資源，延遲的時(shí)間取決于具體實(shí)現(xiàn)的版本，在一些處理器上延遲時(shí)間是零。第二它可以避免在退出循環(huán)的時(shí)候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執(zhí)行效率。

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

當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無法保證操作的原子性，這個(gè)時(shí)候就可以用鎖，或者有一個(gè)取巧的辦法，就是把多個(gè)共享變量合并成一個(gè)共享變量來操作。

比如有兩個(gè)共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對(duì)象之間的原子性，你可以把多個(gè)變量放在一個(gè)對(duì)象里來進(jìn)行CAS操作。

CAS 的應(yīng)用

1.Java的concurrent包下就有很多類似的實(shí)現(xiàn)類，如Atomic開頭那些。 2.自旋鎖 3.令牌桶限流器

令牌桶限流器 就是系統(tǒng)以恒定的速度向桶內(nèi)增加令牌。每次請(qǐng)求前從令牌桶里面獲取令牌。如果獲取到令牌就才可以進(jìn)行訪問。當(dāng)令牌桶內(nèi)沒有令牌的時(shí)候，拒絕提供服務(wù)。我們來看看 eureka 的限流器是如何使用 CAS 來維護(hù)多線程環(huán)境下對(duì) token 的增加和分發(fā)的。

參考文章

https://www.jb51.net/article/125232.htm https://www.imooc.com/article/40690 https://segmentfault.com/a/1190000013127775 https://www.cnblogs.com/barrywxx/p/8487444.html