JDK成長記17：Atomic類的原理—CAS+valotile

file

經(jīng)過volatile和synchronize關(guān)鍵字的底層原理的洗禮，不知道你是否有一種感覺，要想弄明白它們的原理是一個非常難的過程。為什么費這么大的力氣要弄明白這些并發(fā)基礎(chǔ)知識呢？

其實是為了之后更好的掌握并發(fā)組件、并發(fā)集合這些內(nèi)容。JDK中的juc（并發(fā)包）的知識大體可以分為如下幾塊:

file

并發(fā)基礎(chǔ)中除了volatile、synchronied、線程狀態(tài)變化之外，還有很重要的兩個知識CAS和AQS。而其他并發(fā)組件和集合都是基于這些知識來實現(xiàn)的工具而已。

這一節(jié)我們通過Atomic類來學(xué)習(xí)下它的底層原理，實際它的底層通過CAS+volatile的原理來實現(xiàn)的。我們來具體看看：

  • JDK中的CAS如何實現(xiàn)的？又是如何應(yīng)用在Atomic中的？
  • CAS的自旋性能問題怎么優(yōu)化？
  • CAS的ABA問題怎么解決？

在Java代碼中，CAS是如何應(yīng)用在Atomic中的？

<div class="output_wrapper" id="output_wrapper_id" style="width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: 'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;"><h3 id="hdddd" style="width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;"><span style="font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;">在Java代碼中，CAS是如何應(yīng)用在Atomic中的？</span></h3></div>

之前學(xué)習(xí)synchronized的時候，就接觸過CAS。CAS一般稱作Compare And Swap操作。操作流程如下：

file

上面CAS操作簡單描述可以如下：當(dāng)更新一個值從E->V時，更新的時候需要讀取E最新的值N，如果發(fā)生了變化，也就是當(dāng)E!=N，就不會更新成功，重新嘗試，否則更新值成功，變?yōu)閂。

來看一個Demo：

private static AtomicInteger j = new AtomicInteger(0);

public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
    new Thread(() -> {
      System.out.println(AtomicIntegerDemo.j.incrementAndGet());
    }).start();
  }
}

這段程序有10個線程，它們可能同時更新J的值。但是輸出結(jié)果是按順序輸出了0到10的數(shù)字。這是因為在AtomicInteger底層，每個線程的更新都是CAS操作，它保證了多線程修改同一個值的原子性。

首先你可以先看一下AtomicInteger 整體脈絡(luò)：

file

根據(jù)之前分析源碼的思想，先脈絡(luò)后細(xì)節(jié)，你應(yīng)該可以看出，它核心脈絡(luò)就是一個Unsafe對象，int的value。如下

public class AtomicInteger extends Number implements java.io.Serializable {
  // setup to use Unsafe.compareAndSwapInt for updates
  private static final Unsafe unsafe = Unsafe.getUnsafe();

  private static final long valueOffset;


  static {
    try {
      valueOffset = unsafe.objectFieldOffset
        (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
  }

  private volatile int value;

}

核心變量：

  • value是一個volatile的int值。通過volatile的可見性，可以保證有一個線程更新了，其他線程可以得到最新值。
  • valueOffset,類初始化的時候，來進(jìn)行執(zhí)行的，valueOffset，value這個字段在AtomicInteger這個類中的偏移量，在底層，這個類是有自己對應(yīng)的結(jié)構(gòu)的，無論是在磁盤的.class文件里，還是在JVM內(nèi)存中。大概可以理解為：value這個字段具體是在AtomicInteger這個類的哪個位置，offset，偏移量，這個是很底層的操作，是通過unsafe來實現(xiàn)的。剛剛在類初始化的時候，就會完成這個操作的，final的，一旦初始化完畢，就不會再變更了。
  • Usafe類，進(jìn)行真正CAS操作的類

當(dāng)通過new AtomicInteger(0)這句話創(chuàng)建的對象，實際是給value賦值了一個初始值0而已。（int默認(rèn)就是0）

 public AtomicInteger(int initialValue) {
    value = initialValue;
  }

現(xiàn)在你可以得到AtomicInteger的核心組件圖如下：

file

接著每個線程會調(diào)用incrementAndGet這個方法：

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

可以看到直接調(diào)用了Unsafe的getAndAddInt方法，如下：

  public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
      v = getIntVolatile(o, offset);
    } while (!compareAndSwapInt(o, offset, v, v + delta));
    return v;
  }

（可以下載OpenJDK源碼或訪問http://hg.openjdk.java.net/jdk/jdk/file/a1ee9743f4ee/jdk/src/share/classes/sun/misc/Unsafe.java）

上面這段代碼從脈絡(luò)上可以看出來，是經(jīng)典的CAS操作，首先通過一次volatile讀，讀到最新的v值，之后再通過compareAndSwapInt這個方法，進(jìn)行CAS操作。如果CAS操作失敗，會返回false，while循環(huán)繼續(xù)執(zhí)行，進(jìn)行自旋，重新嘗試CAS操作。如果CAS更新操作成功，返回原值。

返回原值之后，incrementAndGet進(jìn)行了+1操作，incrementAndGet方法返回，就會的得到更新后的值。

如下圖所示：

file

在Java代碼層面，很多Atomic原子類底層核心的原理就是CAS，有人也把這種操作稱為無鎖化，樂觀鎖，自旋鎖之類的。（稱呼這種東西是用來交流的，大家能明白就好，不要太過較真）。

CAS操作每次嘗試修改的時候，就對比一下，有沒有人修改過這個值，沒有人修改，自己就修改，如果有人修改過，就重新查出來最新的值，再次重復(fù)那個過程。

而AtomicLong、AtomicLongArray、AtomicBoolean這些原子操作類和AtomicIneger底層是類似的，都是通過Unsafe類來做到CAS操作的。

file

也正是這種操作，可以保證多線程更新的時候的原子性，如下圖所示：

file

在JVM中的CAS如何實現(xiàn)的？

<div class="output_wrapper" id="output_wrapper_id" style="width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: 'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;"><h3 id="hdddd" style="width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;"><span style="font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;">在JVM中的CAS如何實現(xiàn)的？</span></h3></div>

具體的CAS操作方法都是native的方法，是通過C++的代碼實現(xiàn)的。

  public native int   getIntVolatile(Object o, long offset);
  
  public final native boolean compareAndSwapInt(Object o, long offset,
                         int expected,
                         int x);

這就需要我們進(jìn)一步深入JVM來看下CAS是如何實現(xiàn)的。我給大家找到了對應(yīng)的C++代碼如下：

// unsafe.cpp
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))

 UnsafeWrapper("Unsafe_CompareAndSwapInt");

 oop p = JNIHandles::resolve(obj);

 jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);

 return (jint)(Atomic::cmpxchg(x, addr, e)) == e;

UNSAFE_END

通過觀察，可以發(fā)現(xiàn)，核心的CAS操作是通過Atomic::cmpxchg(x, addr, e)這個方法實現(xiàn)的。這個方法從名字上cmpxchg就可以猜到是compare and exchange和compare and swap(CAS)是一個意思。

但是你繼續(xù)跟蹤代碼會發(fā)現(xiàn)，這個Atomic::cmpxchg方法有很多實現(xiàn)。如下圖右側(cè)：

file

因為不同的操作系統(tǒng)和CPU對應(yīng)的CAS指令可能有所不同，所以有了不同的CAS實現(xiàn)。

這里可以看一下atomic_linux_x86.inline.hpp 93行的這個實現(xiàn)方法。代碼如下：

#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

inline jint   Atomic::cmpxchg  (jint   exchange_value, volatile jint*   dest, jint   compare_value) {

 int mp = os::is_MP();

 __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
          : "=a" (exchange_value)
          : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
          : "cc", "memory");

 return exchange_value;
}

上面這段代碼其實就是CAS最底層的實現(xiàn)方式。

首先通過is_MP 這個判斷表示是否是多核CPU處理的意思（Multi Processor ） 。

接著如果是的話，asm表示匯編指令，發(fā)送一條原子性的匯編指令。也就是說CAS底層實際通過類似于lock cmpxchgl 這種匯編的指令，通知CPU進(jìn)行原子性的更新。這其實一個輕量的loc指令，可以讓CPU保證原子性的操作，所以說CAS是自旋鎖,是有道理的。

好了，到這里CAS在JVM層面的具體實現(xiàn)你應(yīng)該已經(jīng)了解了。接下來我們來看CAS的產(chǎn)生的兩個問題。

CAS的自旋無限循環(huán)性能問題怎么優(yōu)化？

<div class="output_wrapper" id="output_wrapper_id" style="width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: 'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;"><h3 id="hdddd" style="width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;"><span style="font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;">CAS的自旋無限循環(huán)性能問題怎么優(yōu)化？</span></h3></div>

不知道大家想到過沒，CAS操作有一個很大的問題，如果在高并發(fā)，多線程更新的時候，會造成大量線程進(jìn)行自旋，消耗CPU資源。這樣的性能是很不好的（當(dāng)然比synchronized還是要好很多的）。

為了解決這一個問題，Java 8提供的一個對AtomicLong改進(jìn)后的一個類，LongAdder。它具備一個分段CAS的原子操作類。讓我們來看一下它的分段CAS優(yōu)化的思想

什么叫分段CAS,或者說是分段遷移呢？

意思就是，當(dāng)某一個線程如果對一個值更新是，可以看對這個值進(jìn)行分段更新，每一段叫做一個Cell，在更新每一個Cell的時候，發(fā)現(xiàn)說出現(xiàn)了很難更新它的值，出現(xiàn)了多次 CAS失敗了，自旋的時候，進(jìn)行自動遷移段，它會去嘗試更新別的分段Cell的值，這樣的話就可以讓一個線程不會盲目的CAS自旋等待一個更新分段cell的值。

LongAdder正是基于這個思想來實現(xiàn)的。基本原理如下圖所示：

file

LongAdder先嘗試一次cas更新，如果失敗會轉(zhuǎn)而通過Cell[]的方式更新值，如果計算index的方式足夠散列，那么在并發(fā)量大的情況下，多個線程定位到同一個cell的概率也就越低，這有點類似于分段鎖的意思。

但是要注意的是sum方法在并發(fā)情況下sum的值不精確，reset方法不是線程安全的。

  public void reset() {
    Cell[] as = cells; Cell a;
    base = 0L;
   if (as != null) {
      for (int i = 0; i < as.length; ++i) {
        if ((a = as[i]) != null)
          a.value = 0L;
      }
    }
  }


  public long sum() {
    Cell[] as = cells; Cell a;
    long sum = base;
    if (as != null) {
      for (int i = 0; i < as.length; ++i) {
        if ((a = as[i]) != null)
          sum += a.value;
      }
    }
    return sum;

  }

關(guān)于sum不精確

sum方法的實現(xiàn)很簡單，其實就是 base + sum(cells)。由上述源碼可以發(fā)現(xiàn)，sum執(zhí)行時，最終返回的是sum局部變量，初始被復(fù)制為base，而最終返回時，很可能base已經(jīng)被更新了，而此時局部變量sum不會更新，造成不一致。其次，這里對cell的讀取也無法保證是最后一次寫入的值。

所以，sum方法在沒有并發(fā)的情況下，可以獲得正確的結(jié)果。

關(guān)于reset不線程安全

因為reset方法并不是原子操作，它先將base重置成0，假設(shè)此時CPU切走執(zhí)行sum，此時的sum就變成了減去base后的值。也就是說，在并發(fā)量大的情況下，執(zhí)行完此方法并不能保證其他線程看到的是重置后的結(jié)果。所以要慎用。

在實際工作中，可根據(jù)LongAdder和AtomicLong的特點來使用這兩個工具。 當(dāng)需要在高并發(fā)下有較好的性能表現(xiàn)，且對值的精確度要求不高時，可以使用LongAdder（例如網(wǎng)站訪問人數(shù)計數(shù)）。 當(dāng)需要保證線程安全，可允許一些性能損耗，要求高精度時，可以使用AtomicLong。LongAdder，替代AtomicLong,完全可以對心跳計數(shù)器來使用LongAdder。

CAS的ABA問題怎么解決？

<div class="output_wrapper" id="output_wrapper_id" style="width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: 'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;"><h3 id="hdddd" style="width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;"><span style="font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;">CAS的ABA問題怎么解決？</span></h3></div>

最后我們聊一下CAS產(chǎn)生的ABA問題。

什么是ABA問題？

如果某個值一開始是A，后來變成了B，然后又變成了A，你本來期望的是值如果是第一個A才會設(shè)置新值，結(jié)果第二個A一比較也ok，也設(shè)置了新值，跟期望是不符合的。

怎么解決呢？

解決辦法也很簡單：加一個類似于版本號的東西，比如郵戳int stamp之類的。記錄更新的次數(shù)即可，比較的時候不光比較value也要比較郵戳。

所以atomic包里有AtomicStampedReference類，就是會比較兩個值的引用是否一致，如果一致，才會設(shè)置新值

你可以自己研究一下它的的源碼。它CAS核心代碼如下：

  // AtomicStampedReference
  public boolean compareAndSet(V  expectedReference,
                 V  newReference,
                 int expectedStamp,
                 int newStamp) {

    Pair<V> current = pair;
    return
      expectedReference == current.reference &&
      expectedStamp == current.stamp &&
      ((newReference == current.reference &&
       newStamp == current.stamp) ||
       casPair(current, Pair.of(newReference, newStamp)));
  }

  private boolean casPair(Pair<V> cmp, Pair<V> val) {
    return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
  }

最后還要說明的一點，就是Atomic類不能保證多變量原子問題，一般的AtomicInteger，只能保證一個變量的原子性。

但是如果多個變量？你可以用AtomicReference，這個是封裝自定義對象的，多個變量可以放一個自定義對象里，然后他會檢查這個對象的引用是不是一個。（注意對象中的變量如果不是Atomic,操作的時候不保證原子性，只能保證操作AtomicReference泛型對應(yīng)的這個對象的引用時是原子的。）

小結(jié)

<div class="output_wrapper" id="output_wrapper_id" style="width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: 'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;"><h3 id="hdddd" style="width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;"><span style="font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;">小結(jié)</span></h3></div>

今天，了解Atomic的類。這里給大家小結(jié)下Atomic類底層原理都是CAS，原理都是類似的。主要分為如下幾類：

1、AtomicInteger/AtomicLong/AtomicBoolean/AtomicReference是關(guān)于對變量的原子CAS更新。

2、AtomicIntegerArray/AtomicLongArray/AtomicReferenceArray是關(guān)于對數(shù)組的原子CAS更新。

3、AtomicIntegerFieldUpdater<T>/AtomicLongFieldUpdater<T>/AtomicReferenceFieldUpdater<T,V>是基于反射的CAS原子更新某個類的字段。

學(xué)完這一節(jié)你應(yīng)該掌握了如下知識

  • CAS的java層面原理（Unsafe+volatile value）
  • CAS的JVM層面（C++/CPU匯編指令lock cmpxchgl前綴指令）
  • ABA問題、無限循環(huán)性能問題、多變量原子更新問題
  • 分段遷移CAS思想、郵戳版本號思想、原子引用思想

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容