從 Atomic 到 CAS ，值20K的面試題

本文公眾號(hào)來源：JavaKeeper

作者：π大新

本文已收錄至我的GitHub

??? 面試官：“

• CAS 知道嗎，如何實(shí)現(xiàn)？
• 講一講AtomicInteger，為什么要用 CAS 而不是 synchronized？
• CAS 底層原理，談?wù)勀銓?duì) UnSafe 的理解？
• CAS 有什么缺點(diǎn)嗎？
• AtomicInteger 的ABA問題，能說一下嗎，原子更新引用知道嗎？
• 如何規(guī)避 ABA 問題？”

前言

Java 內(nèi)存模型要保證可見性，原子性和有序性。

在 JDK 5之前 Java 語言是靠 synchronized 關(guān)鍵字保證同步的，但 synchronized 是一種獨(dú)占鎖，是一種悲觀鎖， 會(huì)導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖 ，效率不是很高。

Java 虛擬機(jī)又提供了一個(gè)輕量級(jí)的同步機(jī)制——volatile（面試必問的 volatile，你真的理解了嗎）

但是 volatile 算是乞丐版的 synchronized，并不能保證原子性 ，所以，又增加了java.util.concurrent.atomic包， 這個(gè)包下提供了一系列原子類。

1. Atomic 原子類

Atomic 原子類可以保證多線程環(huán)境下，當(dāng)某個(gè)線程在執(zhí)行 atomic 的方法時(shí)，不會(huì)被其他線程打斷，而別的線程就像自旋鎖一樣，一直等到該方法執(zhí)行完成，才由 JVM 從等待隊(duì)列中選擇一個(gè)線程執(zhí)行。Atomic 類在軟件層面上是非阻塞的，它的原子性其實(shí)是在硬件層面上借助相關(guān)的指令來保證的。

Atomic 包中的類可以分成 4 組：

1. 基本類型：AtomicBoolean，AtomicInteger，AtomicLong
2. 數(shù)組類型：tomicIntegerArray，AtomicLongArray，AtomicReferenceArray
3. 引用類型：AtomicReference，AtomicMarkableReference，AtomicStampedReference
4. 對(duì)象的屬性修改類型 ：AtomicIntegerFieldUpdater，AtomicLongFieldUpdater，AtomicReferenceFieldUpdater
5. JDK1.8新增：DoubleAccumulator、LongAccumulator、DoubleAdder、LongAdder、Striped64

以 AtomicInteger 為例了解常用方法

Coding~~~

public class CASDemo {
    public static void main(String[] args) {
        System.out.println(num.compareAndSet(6, 7) + "\t + current num:" + num);
        System.out.println(num.compareAndSet(6, 7) + "\t current num:" + num);
    }
}

true	 + current num:7
false	 current num:7

執(zhí)行兩次結(jié)果卻不同，Why?

compareAndSet() 嘗試新增后對(duì)比，若增加成功則返回true否則返回false。其實(shí)就是比較并交換，判斷用當(dāng)前值和期望值（第一個(gè)參數(shù)），是否一致，如果一致，修改為更新值（第二個(gè)參數(shù)），這就是大名鼎鼎的 CAS。

2. CAS 是什么

2.1 CAS 算法

• CAS：全稱 Compare and swap，即比較并交換，它是一條 CPU 同步原語。是一種硬件對(duì)并發(fā)的支持，針對(duì)多處理器操作而設(shè)計(jì)的一種特殊指令，用于管理對(duì)共享數(shù)據(jù)的并發(fā)訪問。
• CAS 是一種無鎖的非阻塞算法的實(shí)現(xiàn)。
• CAS 包含了 3 個(gè)操作數(shù)：
• 需要讀寫的內(nèi)存值 V
• 舊的預(yù)期值 A
• 要修改的更新值 B
• 當(dāng)且僅當(dāng) V 的值等于 A 時(shí)，CAS 通過原子方式用新值 B 來更新 V 的 值，否則不會(huì)執(zhí)行任何操作（他的功能是判斷內(nèi)存某個(gè)位置的值是否為預(yù)期值，如果是則更改為新的值，這個(gè)過程是原子的。）

CAS 并發(fā)原語體現(xiàn)在 Java 語言中的 sum.misc.Unsafe 類中的各個(gè)方法。調(diào)用 Unsafe 類中的 CAS 方法， JVM 會(huì)幫助我們實(shí)現(xiàn)出 CAS 匯編指令。這是一種完全依賴于硬件的功能，通過它實(shí)現(xiàn)了原子操作。再次強(qiáng)調(diào)，由于 CAS是一種系統(tǒng)原語，原語屬于操作系統(tǒng)用于范疇，是由若干條指令組成的，用于完成某個(gè)功能的一個(gè)過程，并且原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷，CAS 是一條 CPU 的原子指令，不會(huì)造成數(shù)據(jù)不一致問題。

我們常用的 java.util.concurrent 包就建立在CAS之上。

2.2 用 CAS 分析 AtomicInteger 類

查看 AtomicInteger 代碼如下，可以看到該類下的方法大部分是 調(diào)用了 Unsafe 類

2.2.1 UnSafe 類

是 CAS 的核心類，由于 Java 方法無法直接訪問底層系統(tǒng)，需要通過本地（native）方法來訪問，UnSafe 相當(dāng)于一個(gè)后門，基于該類可以直接操作特定內(nèi)存的數(shù)據(jù)。UnSafe 類存在與 sum.misc 包中，其內(nèi)部方法可以像 C 語言的指針一樣直接操作內(nèi)存，因?yàn)?Java 中 CAS 操作的執(zhí)行依賴于 UnSafe 類的方法。

UnSafe 類中的所有方法都是 native 修飾的，也就是說該類中的方法都是直接調(diào)用操作系統(tǒng)底層資源執(zhí)行相應(yīng)任務(wù)。

public final class Unsafe {
    private static final Unsafe theUnsafe;
	// ......
    @CallerSensitive
    public static Unsafe getUnsafe() {
        Class var0 = Reflection.getCallerClass();
        if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

    public native int getInt(Object var1, long var2);

    public native void putInt(Object var1, long var2, int var4);

    public native Object getObject(Object var1, long var2);

    public native void putObject(Object var1, long var2, Object var4);
    
    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);
    // ......
}

Unsafe 類為一單例實(shí)現(xiàn)，提供靜態(tài)方法 getUnsafe 獲取 Unsafe 實(shí)例，當(dāng)且僅當(dāng)調(diào)用 getUnsafe 方法的類為引導(dǎo)類加載器所加載時(shí)才合法，否則拋出 SecurityException 異常

2.2.2 valueOffset

AtomicInteger 中的變量 valueOffset 表示該變量值在內(nèi)存中的偏移地址，因?yàn)?UnSafe 就是根據(jù)內(nèi)存偏移地址獲取數(shù)據(jù)。

public final int getAndIncrement() {
	return unsafe.getAndAddInt(this, valueOffset, 1);
}

2.2.3 volatile int value

變量 value 用 volatile 修飾，保證了多線程之間的內(nèi)存可見性。

2.2.4 舉個(gè)栗子

我們用線程安全的 ++i 舉例，也就是 AtomicInteger 中的 ?getAndAdd

逐層看 Unsafe 類中的 getAndAdd() 的源碼如下

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

解毒：

可以看到 getAndAddInt 方法有 4 個(gè)參數(shù)

• val1：AtomicInteger 對(duì)象本身
• var2：該對(duì)象值的引用地址，內(nèi)存偏移量
• var4：需要變動(dòng)的數(shù)量，即 ++i 的 i
• var5：用var1， var2 找出的主內(nèi)存中真實(shí)的值（通過內(nèi)存偏移量）

this.compareAndSwapInt ?用該對(duì)象當(dāng)前的值與 var5 比較，如果相同，更新 var5 + var4 并且返回 true，如果不同，繼續(xù)取值然后再比較，直到更新完成。

這一操作沒有加鎖，反復(fù)執(zhí)行，既保證了一致性，又保證了并發(fā)性。

假設(shè)線程A和線程B兩個(gè)線程同時(shí)執(zhí)行 getAndAddInt 操作（分別跑在不同CPU上）：

1. AtomicInteger 里面的 value 原始值為 3，即主內(nèi)存中 AtomicInteger 的 value 為 3，根據(jù) JMM 模型，線程A和線程B各自持有一份值為 3 的 value 的副本分別到各自的工作內(nèi)存；
2. 線程A通過 getIntVolatile(var1,var2) 拿到 value 值3，這時(shí)線程A被掛起；
3. 線程B也通過 getIntVolatile(var1,var2) 方法獲取到 value 值 3，此時(shí)剛好線程B沒有被掛起并執(zhí)行compareAndSwapInt 方法比較內(nèi)存值為 3，成功修改內(nèi)存值為 4，線程B結(jié)束，一切正常
4. 這時(shí)線程A恢復(fù)，執(zhí)行compareAndSwapInt() 方法比較，發(fā)現(xiàn)自己手里的3和主內(nèi)存的值4不一致，說明該值已經(jīng)被其他線程搶先一步修改過了，那線程A本次修改失敗，重新讀??；
5. 線程A重新獲取value值，因?yàn)樽兞縱alue 被 volatile 修飾，所以其他線程對(duì)它的修改，線程A總是能夠看到，線程A繼續(xù)執(zhí)行compareAndSwapInt進(jìn)行比較替換，直到成功

2.2.5 使用 UnSafe 類

那如若想使用這個(gè)類，該如何獲取其實(shí)例？有如下兩個(gè)可行方案

1. 從getUnsafe 方法的使用限制條件出發(fā)，通過Java命令行命令 -Xbootclasspath/a 把調(diào)用 Unsafe 相關(guān)方法的類A所在 jar 包路徑追加到默認(rèn)的 bootstrap 路徑中，使得A被引導(dǎo)類加載器加載，從而通過Unsafe.getUnsafe方法安全的獲取 Unsafe 實(shí)例。

java -Xbootclasspath/a: ${path}   // 其中path為調(diào)用Unsafe相關(guān)方法的類所在jar包路徑

2. 通過反射技術(shù)暴力獲取 Unsafe 對(duì)象

   private static Unsafe reflectGetUnsafe() {
       try {
         Field field = Unsafe.class.getDeclaredField("theUnsafe");
         field.setAccessible(true);
         return (Unsafe) field.get(null);
       } catch (Exception e) {
         log.error(e.getMessage(), e);
         return null;
       }
   }

美團(tuán)技術(shù)團(tuán)隊(duì)有一篇介紹Unsafe 類的文章：Java魔法類：Unsafe應(yīng)用解析

3. CAS 缺點(diǎn)

• 循環(huán)時(shí)間長，開銷很大。CAS算法需要不斷地自旋來讀取最新的內(nèi)存值，長時(shí)間讀取不到就會(huì)造成不必要的CPU開銷。do while 如果CAS失敗，會(huì)一直進(jìn)行嘗試，如果CAS長時(shí)間一直不成功，可能會(huì)給CPU帶來很大的開銷
• 只能保證一個(gè)共享變量的原子操作。當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來保證原子操作，但是，對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無法保證操作的原子性，這個(gè)時(shí)候就可以用鎖來保證原子性。
• ABA 問題

ABA 問題

ABA 問題是什么？是如何產(chǎn)生的？

CAS算法實(shí)現(xiàn)一個(gè)重要前提是需要取出內(nèi)存中某時(shí)刻的數(shù)據(jù)并在當(dāng)下時(shí)刻比較并替換，那么在這個(gè)時(shí)間差類會(huì)導(dǎo)致數(shù)據(jù)的變化。

比如線程1從內(nèi)存位置 V 中取出A，這時(shí)線程2也從內(nèi)存中取出A，并且線程2進(jìn)行了一些操作將值變成了B，然后線程2又將V位置的數(shù)據(jù)變成A，這個(gè)時(shí)候線程1進(jìn)行CAS操作發(fā)現(xiàn)內(nèi)存中仍然是A，線程1就會(huì)誤認(rèn)為它沒有被修改過，這個(gè)漏洞就是CAS操作的"ABA"問題。

盡管線程1的CAS操作成功，但是不代表這個(gè)過程就是沒有問題的。

原子引用

我們平時(shí)操作的不止是基本數(shù)據(jù)類型，大多數(shù)情況其實(shí)是類對(duì)象，Atomic 提供的引用類型 AtomicReference 通過泛型可以支持對(duì)對(duì)象的原子操作

public class AtomicRefrenceDemo {

    public static void main(String[] args) {

        User tom = new User("tom",18);
        User jim = new User("jim",20);

        AtomicReference user = new AtomicReference<>();
        user.set(tom);

        System.out.println(user.compareAndSet(tom, jim)+"\t"+user.get().toString());
        System.out.println(user.compareAndSet(tom, jim)+"\t"+user.get().toString());

    }
}

class User{
    String name;
    int age;
    public User(String tom, int i) {
    }
}

除了AtomicReference ，Atomic 還提供了AtomicStampedReference、AtomicMarkableReference

解決ABA 問題

各種樂觀鎖的實(shí)現(xiàn)中通常都會(huì)用版本戳 version 來對(duì)記錄或?qū)ο髽?biāo)記，避免并發(fā)操作帶來的問題

在Java中，AtomicStampedReference 也實(shí)現(xiàn)了這個(gè)作用，它通過包裝[E,int]的元組來對(duì)對(duì)象標(biāo)記版本戳stamp，從而避免ABA問題

public class AtomicStampedReferenceDemo {

    static AtomicStampedReference asf = new AtomicStampedReference<>("A", 1);

    public static void main(String[] args) {

        new Thread(() -> {
            String value = asf.getReference();
            System.out.println("Thread1 current value: " + asf.getReference() + ", stamp: " + asf.getStamp());

            asf.compareAndSet(value, "B", asf.getStamp(), asf.getStamp() + 1);
            System.out.println("Thread1：" + value + "——>" + asf.getReference() + ",stamp:" + asf.getStamp());
            value = asf.getReference();
            asf.compareAndSet(asf.getReference(), "A", asf.getStamp(), asf.getStamp() + 1);
            System.out.println("Thread1：" + value + "——>" + asf.getReference() + ",stamp:" + asf.getStamp());
        }).start();

        new Thread(() -> {
            String value = asf.getReference();

            int stamp = asf.getStamp();
            System.out.println("Thread2 current value: " + asf.getReference() + ", stamp: " + stamp);

            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("Thread2: " + value + "——>" + "B" + ",stamp:" + stamp + 1);
            boolean flag = asf.compareAndSet(value, "B", stamp, stamp + 1);
            if (flag) {
                System.out.println("Thread2 update from " + value + " to B");
            } else {
                System.out.println("Thread2 update fail");
            }
        }).start();
    }
}

Thread1 current value: A, stamp: 1
Thread2 current value: A, stamp: 1
Thread1：A——>B,stamp:2
Thread1：B——>A,stamp:3
Thread2: A——>B,stamp:11
Thread2 update fail