Java CAS 原理分析

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

1.簡介

CAS 全稱是 compare and swap,是一種用於在多執行緒環境下實現同步功能的機制。CAS 操作包含三個運算元 — 記憶體位置、預期數值和新值。CAS 的實現邏輯是將記憶體位置處的數值與預期數值想比較,若相等,則將記憶體位置處的值替換為新值。若不相等,則不做任何操作。

在 Java 中,Java 並沒有直接實現 CAS,CAS 相關的實現是通過 C 內聯彙編的形式實現的。Java 程式碼需通過 JNI 才能呼叫。關於實現上的細節,我將會在第3章進行分析。

前面說了 CAS 操作的流程,並不是很難。但僅有上面的說明還不夠,接下來我將會再介紹一點其他的背景知識。有這些背景知識,才能更好的理解後續的內容。

2.背景介紹

我們都知道,CPU 是通過匯流排和記憶體進行資料傳輸的。在多核心時代下,多個核心通過同一條匯流排和記憶體以及其他硬體進行通訊。如下圖:

圖片出處:《深入理解計算機系統》

上圖是一個較為簡單的計算機結構圖,雖然簡單,但足以說明問題。在上圖中,CPU 通過兩個藍色箭頭標註的匯流排與記憶體進行通訊。大家考慮一個問題,CPU 的多個核心同時對同一片記憶體進行操作,若不加以控制,會導致什麼樣的錯誤?這裡簡單說明一下,假設核心1經32位頻寬的匯流排向記憶體寫入64位的資料,核心1要進行兩次寫入才能完成整個操作。若在核心1第一次寫入32位的資料後,核心2從核心1寫入的記憶體位置讀取了64位資料。由於核心1還未完全將64位的資料全部寫入記憶體中,核心2就開始從該記憶體位置讀取資料,那麼讀取出來的資料必定是混亂的。

不過對於這個問題,實際上不用擔心。通過 Intel 開發人員手冊,我們可以瞭解到自奔騰處理器開始,Intel 處理器會保證以原子的方式讀寫按64位邊界對齊的四字(quadword)。

根據上面的說明,我們可總結出,Intel 處理器可以保證單次訪問記憶體對齊的指令以原子的方式執行。但如果是兩次訪存的指令呢?答案是無法保證。比如遞增指令inc dword ptr [...],等價於DEST = DEST 1。該指令包含三個操作讀->改->寫,涉及兩次訪存。考慮這樣一種情況,在記憶體指定位置處,存放了一個為1的數值。現在 CPU 兩個核心同時執行該條指令。兩個核心交替執行的流程如下:

  1. 核心1 從記憶體指定位置出讀取數值1,並載入到暫存器中
  2. 核心2 從記憶體指定位置出讀取數值1,並載入到暫存器中
  3. 核心1 將暫存器中值遞減1
  4. 核心2 將暫存器中值遞減1
  5. 核心1 將修改後的值寫回記憶體
  6. 核心2 將修改後的值寫回記憶體

經過執行上述流程,記憶體中的最終值時2,而我們期待的是3,這就出問題了。要處理這個問題,就要避免兩個或多個核心同時操作同一片記憶體區域。那麼怎樣避免呢?這就要引入本文的主角 – lock 字首。關於該指令的詳細描述,可以參考 Intel 開發人員手冊 Volume 2 Instruction Set Reference,Chapter 3 Instruction Set Reference A-L。我這裡引用其中的一段,如下:

LOCK—Assert LOCK# Signal Prefix
Causes the processor’s LOCK# signal to be asserted during execution of the accompanying instruction (turns the instruction into an atomic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted.

上面描述的重點已經用黑體標出了,在多處理器環境下,LOCK# 訊號可以確保處理器獨佔使用某些共享記憶體。lock 可以被新增在下面的指令前:

ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG.

通過在 inc 指令前新增 lock 字首,即可讓該指令具備原子性。多個核心同時執行同一條 inc 指令時,會以序列的方式進行,也就避免了上面所說的那種情況。那麼這裡還有一個問題,lock 字首是怎樣保證核心獨佔某片記憶體區域的呢?答案如下:

在 Intel 處理器中,有兩種方式保證處理器的某個核心獨佔某片記憶體區域。第一種方式是通過鎖定匯流排,讓某個核心獨佔使用匯流排,但這樣代價太大。匯流排被鎖定後,其他核心就不能訪問記憶體了,可能會導致其他核心短時內停止工作。第二種方式是鎖定快取,若某處記憶體資料被快取在處理器快取中。處理器發出的 LOCK# 訊號不會鎖定匯流排,而是鎖定快取行對應的記憶體區域。其他處理器在這片記憶體區域鎖定期間,無法對這片記憶體區域進行相關操作。相對於鎖定匯流排,鎖定快取的代價明顯比較小。關於匯流排鎖和快取鎖,更詳細的描述請參考 Intel 開發人員手冊 Volume 3 Software Developer’s Manual,Chapter 8 Multiple-Processor Management。

3.原始碼分析

有了上面的背景知識,現在我們就可以從容不迫的閱讀 CAS 的原始碼了。本章的內容將對 java.util.concurrent.atomic 包下的原子類 AtomicInteger 中的 compareAndSet 方法進行分析,相關分析如下:

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 {
            // 計算變數 value 在類物件中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    
    public final boolean compareAndSet(int expect, int update) {
        /*
         * compareAndSet 實際上只是一個殼子,主要的邏輯封裝在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    // ......
}

public final class Unsafe {
    // compareAndSwapInt 是 native 型別的方法,繼續往下看
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);
    // ......
}
// unsafe.cpp
/*
 * 這個看起來好像不像一個函式,不過不用擔心,不是重點。UNSAFE_ENTRY 和 UNSAFE_END 都是巨集,
 * 在預編譯期間會被替換成真正的程式碼。下面的 jboolean、jlong 和 jint 等一些型別也都是巨集:
 * 
 * jni.h
 *     typedef unsigned char   jboolean;
 *     typedef unsigned short  jchar;
 *     typedef short           jshort;
 *     typedef float           jfloat;
 *     typedef double          jdouble;
 * 
 * jni_md.h
 *     typedef int jint;
 *     #ifdef _LP64 /* 64-bit */
 *     typedef long jlong;
 *     #else
 *     typedef long long jlong;
 *     #endif
 *     typedef signed char jbyte;
 */
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);
  // 根據偏移量,計算 value 的地址。這裡的 offset 就是 AtomaicInteger 中的 valueOffset
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  // 呼叫 Atomic 中的函式 cmpxchg,該函式宣告於 Atomic.hpp 中
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

// atomic.cpp
unsigned Atomic::cmpxchg(unsigned int exchange_value,
                         volatile unsigned int* dest, unsigned int compare_value) {
  assert(sizeof(unsigned int) == sizeof(jint), "more work to do");
  /*
   * 根據作業系統型別呼叫不同平臺下的過載函式,這個在預編譯期間編譯器會決定呼叫哪個平臺下的過載
   * 函式。相關的預編譯邏輯如下:
   * 
   * atomic.inline.hpp:
   *    #include "runtime/atomic.hpp"
   *    
   *    // Linux
   *    #ifdef TARGET_OS_ARCH_linux_x86
   *    # include "atomic_linux_x86.inline.hpp"
   *    #endif
   *   
   *    // 省略部分程式碼
   *    
   *    // Windows
   *    #ifdef TARGET_OS_ARCH_windows_x86
   *    # include "atomic_windows_x86.inline.hpp"
   *    #endif
   *    
   *    // BSD
   *    #ifdef TARGET_OS_ARCH_bsd_x86
   *    # include "atomic_bsd_x86.inline.hpp"
   *    #endif
   * 
   * 接下來分析 atomic_windows_x86.inline.hpp 中的 cmpxchg 函式實現
   */
  return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest,
                                       (jint)compare_value);
}

上面的分析看起來比較多,不過主流程並不複雜。如果不糾結於程式碼細節,還是比較容易看懂的。接下來,我會分析 Windows 平臺下的 Atomic::cmpxchg 函式。繼續往下看吧。

// atomic_windows_x86.inline.hpp
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:
              
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

上面的程式碼由 LOCK_IF_MP 預編譯識別符號和 cmpxchg 函式組成。為了看到更清楚一些,我們將 cmpxchg 函式中的 LOCK_IF_MP 替換為實際內容。如下:

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  // 判斷是否是多核 CPU
  int mp = os::is_MP();
  __asm {
    // 將引數值放入暫存器中
    mov edx, dest    // 注意: dest 是指標型別,這裡是把記憶體地址存入 edx 暫存器中
    mov ecx, exchange_value
    mov eax, compare_value
    
    // LOCK_IF_MP
    cmp mp, 0
    /*
     * 如果 mp = 0,表明是執行緒執行在單核 CPU 環境下。此時 je 會跳轉到 L0 標記處,
     * 也就是越過 _emit 0xF0 指令,直接執行 cmpxchg 指令。也就是不在下面的 cmpxchg 指令
     * 前加 lock 字首。
     */
    je L0
    /*
     * 0xF0 是 lock 字首的機器碼,這裡沒有使用 lock,而是直接使用了機器碼的形式。至於這樣做的
     * 原因可以參考知乎的一個回答:
     *     https://www.zhihu.com/question/50878124/answer/123099923
     */ 
    _emit 0xF0
L0:
    /*
     * 比較並交換。簡單解釋一下下面這條指令,熟悉彙編的朋友可以略過下面的解釋:
     *   cmpxchg: 即“比較並交換”指令
     *   dword: 全稱是 double word,在 x86/x64 體系中,一個 
     *          word = 2 byte,dword = 4 byte = 32 bit
     *   ptr: 全稱是 pointer,與前面的 dword 連起來使用,表明訪問的記憶體單元是一個雙字單元
     *   [edx]: [...] 表示一個記憶體單元,edx 是暫存器,dest 指標值存放在 edx 中。
     *          那麼 [edx] 表示記憶體地址為 dest 的記憶體單元
     *          
     * 這一條指令的意思就是,將 eax 暫存器中的值(compare_value)與 [edx] 雙字記憶體單元中的值
     * 進行對比,如果相同,則將 ecx 暫存器中的值(exchange_value)存入 [edx] 記憶體單元中。
     */
    cmpxchg dword ptr [edx], ecx
  }
}

到這裡 CAS 的實現過程就講完了,CAS 的實現離不開處理器的支援。以上這麼多程式碼,其實核心程式碼就是一條帶lock 字首的 cmpxchg 指令,即lock cmpxchg dword ptr [edx], ecx

4.ABA 問題

談到 CAS,基本上都要談一下 CAS 的 ABA 問題。CAS 由三個步驟組成,分別是“讀取->比較->寫回”。考慮這樣一種情況,執行緒1和執行緒2同時執行 CAS 邏輯,兩個執行緒的執行順序如下:

  1. 時刻1:執行緒1執行讀取操作,獲取原值 A,然後執行緒被切換走
  2. 時刻2:執行緒2執行完成 CAS 操作將原值由 A 修改為 B
  3. 時刻3:執行緒2再次執行 CAS 操作,並將原值由 B 修改為 A
  4. 時刻4:執行緒1恢復執行,將比較值(compareValue)與原值(oldValue)進行比較,發現兩個值相等。然後用新值(newValue)寫入記憶體中,完成 CAS 操作

如上流程,執行緒1並不知道原值已經被修改過了,在它看來並沒什麼變化,所以它會繼續往下執行流程。對於 ABA 問題,通常的處理措施是對每一次 CAS 操作設定版本號。java.util.concurrent.atomic 包下提供了一個可處理 ABA 問題的原子類 AtomicStampedReference,具體的實現這裡就不分析了,有興趣的朋友可以自己去看看。

5.總結

寫到這裡,這篇文章總算接近尾聲了。雖然 CAS 本身的原理,包括實現都不是很難,但是寫起來真的不太好寫。這裡面涉及到了一些底層的知識,雖然能看懂,但想說明白,還是有點難度的。由於我底層的知識比較欠缺,上面的一些分析難免會出錯。所以如有錯誤,請輕噴,當然最好能說明怎麼錯的,感謝。

好了,本篇文章就到這裡。感謝閱讀,再見。

參考

附錄

在前面原始碼分析一節中用到的幾個檔案,這裡把路徑貼出來。有助於大家進行索引,如下:

檔名路徑
Unsafe.javaopenjdk/jdk/src/share/classes/sun/misc/Unsafe.java
unsafe.cppopenjdk/hotspot/src/share/vm/prims/unsafe.cpp
atomic.cppopenjdk/hotspot/src/share/vm/runtime/atomic.cpp
atomic_windows_x86.inline.hppopenjdk/hotspot/src/os_cpu/windows_x86/vm/atomic_windows_x86.inline.hpp

本文在知識共享許可協議 4.0 下發布,轉載需在明顯位置處註明出處
作者:coolblog
本文同步釋出在我的個人部落格:http://www.coolblog.xyz


本作品採用知識共享署名-非商業性使用-禁止演繹 4.0 國際許可協議進行許可。

相關文章

開發語言 最新文章