java基礎(chǔ)教學(xué)專欄介紹分析Java CAS

推薦（免費(fèi)）：java基礎(chǔ)教學(xué)

1、簡(jiǎn)介

CAS 全名為compare and swap，一種用於在多執(zhí)行緒環(huán)境下實(shí)現(xiàn)同步功能的機(jī)制。 CAS 運(yùn)算包含三個(gè)運(yùn)算元 -- 記憶體位置、預(yù)期數(shù)值和新值。 CAS 的實(shí)作邏輯是將記憶體位置的數(shù)值??與預(yù)期數(shù)值想比較，若相等，則將記憶體位置的值替換為新值。若不相等，則不做任何操作。

在 Java 中，Java 並沒有直接實(shí)作 CAS，CAS 相關(guān)的實(shí)作是透過 C 內(nèi)聯(lián)彙編的形式實(shí)現(xiàn)的。 Java 程式碼需透過 JNI 才能呼叫。關(guān)於實(shí)現(xiàn)上的細(xì)節(jié)，我將會(huì)在第3章進(jìn)行分析。

前面說了 CAS 操作的流程，並不是很難。但僅有上面的說明還不夠，接下來我將會(huì)再介紹一點(diǎn)其他的背景知識(shí)。有這些背景知識(shí)，才能更好的理解後續(xù)的內(nèi)容。

2.背景介紹

我們都知道，CPU 是透過匯流排和記憶體進(jìn)行資料傳輸?shù)?。在多核心時(shí)代下，多個(gè)核心透過同一條匯流排和記憶體以及其他硬體進(jìn)行通訊。如下圖：

圖片來源：《深入理解電腦系統(tǒng)》

上圖是較簡(jiǎn)單的電腦結(jié)構(gòu)圖，雖然簡(jiǎn)單，但足以說明問題。在上圖中，CPU 透過兩個(gè)藍(lán)色箭頭標(biāo)註的匯流排與記憶體通訊。大家考慮一個(gè)問題，CPU 的多個(gè)核心同時(shí)對(duì)同一片記憶體進(jìn)行操作，若不加以控制，會(huì)導(dǎo)致什麼樣的錯(cuò)誤？這裡簡(jiǎn)單說明一下，假設(shè)核心1經(jīng)32位元頻寬的匯流排向記憶體寫入64位元的數(shù)據(jù)，核心1要進(jìn)行兩次寫入才能完成整個(gè)操作。若在核心1第一次寫入32位元的資料後，核心2從核心1寫入的記憶體位置讀取了64位元資料。由於核心1還未完全將64位的數(shù)據(jù)全部寫入內(nèi)存中，核心2就開始從該內(nèi)存位置讀取數(shù)據(jù)，那麼讀取出來的數(shù)據(jù)必定是混亂的。

不過對(duì)於這個(gè)問題，其實(shí)不用擔(dān)心。透過 Intel 開發(fā)人員手冊(cè)，我們可以了解到自奔騰處理器開始，Intel 處理器會(huì)保證以原子的方式讀寫按64位元邊界對(duì)齊的四字（quadword）。

根據(jù)上面的說明，我們可總結(jié)出，Intel 處理器可以保證單次存取記憶體對(duì)齊的指令以原子的方式執(zhí)行。但如果是兩次訪存的指示呢？答案是無法保證。例如遞增指令inc dword ptr [...]，等價(jià)於DEST = DEST 1。此指令包含三個(gè)操作讀取->改->寫，涉及兩次訪問?？紤]這樣一種情況，在記憶體指定位置處，存放了一個(gè)為1的數(shù)值。現(xiàn)在 CPU 兩個(gè)核心同時(shí)執(zhí)行該條指令。兩個(gè)核心交替執(zhí)行的流程如下：

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

經(jīng)過執(zhí)行上述流程，記憶體中的最終值時(shí)2，而我們期待的是3，這就出問題了。要處理這個(gè)問題，就要避免兩個(gè)或多個(gè)核心同時(shí)操作同一片記憶體區(qū)域。那麼要怎樣避免呢？這就要引入本文的主角 - lock 前綴。關(guān)於該指令的詳細(xì)描述，可以參考 Intel 開發(fā)人員手冊(cè) 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 micion into an mic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted.

##上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述的重點(diǎn)已經(jīng)用上面描述。黑體標(biāo)示了，在多處理器環(huán)境下，LOCK# 訊號(hào)可以確保處理器獨(dú)佔(zhàn)使用某些共享記憶體。 lock 可以加入下面的指令：

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

在 inc 指令前面加上 lock 前綴，即可讓指令具備原子性。多個(gè)核心同時(shí)執(zhí)行同一條 inc 指令時(shí)，會(huì)以串列的方式進(jìn)行，也就避免了上面所說的那種情況。那麼這裡還有一個(gè)問題，lock 前綴是怎麼保證核心獨(dú)佔(zhàn)某片記憶體區(qū)域的呢？答案如下：

在 Intel 處理器中，有兩種??方式確保處理器的某個(gè)核心獨(dú)佔(zhàn)某片記憶體區(qū)域。第一種方式是透過鎖定匯流排，讓某個(gè)核心獨(dú)佔(zhàn)使用匯流排，但這樣代價(jià)太大?？偩€被鎖定後，其他核心就無法存取記憶體了，可能會(huì)導(dǎo)致其他核心短暫內(nèi)停止工作。第二種方式是鎖定緩存，若某處記憶體資料緩存在處理器快取中。處理器發(fā)出的 LOCK# 訊號(hào)不會(huì)鎖定匯流排，而是鎖定快取行對(duì)應(yīng)的記憶體區(qū)域。其他處理器在這片記憶體區(qū)域鎖定期間，無法對(duì)這片記憶體區(qū)域進(jìn)行相關(guān)操作。相對(duì)於鎖定總線，鎖定快取的代價(jià)明顯比較小。關(guān)於匯流排鎖和快取鎖，更詳細(xì)的描述請(qǐng)參考 Intel 開發(fā)人員手冊(cè) Volume 3 Software Developer’s Manual，Chapter 8 Multiple-Processor Management。

3.原始碼分析

有了上面的背景知識(shí)，現(xiàn)在我們就可以從容不迫的閱讀 CAS 的源碼了。本章的內(nèi)容將對(duì)java.util.concurrent.atomic 套件下的原子類AtomicInteger 中的compareAndSet 方法進(jìn)行分析，相關(guān)分析如下：

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?{
????????????//?計(jì)算變量?value?在類對(duì)象中的偏移
????????????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?實(shí)際上只是一個(gè)殼子，主要的邏輯封裝在?Unsafe?的?
?????????*?compareAndSwapInt?方法中
?????????*/
????????return?unsafe.compareAndSwapInt(this,?valueOffset,?expect,?update);
????}
????
????//?......
}

public?final?class?Unsafe?{
????//?compareAndSwapInt?是?native?類型的方法，繼續(xù)往下看
????public?final?native?boolean?compareAndSwapInt(Object?o,?long?offset,
??????????????????????????????????????????????????int?expected,
??????????????????????????????????????????????????int?x);
????//?......
}

//?unsafe.cpp
/*
?*?這個(gè)看起來好像不像一個(gè)函數(shù)，不過不用擔(dān)心，不是重點(diǎn)。UNSAFE_ENTRY?和?UNSAFE_END?都是宏，
?*?在預(yù)編譯期間會(huì)被替換成真正的代碼。下面的?jboolean、jlong?和?jint?等是一些類型定義（typedef）：
?*?
?*?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);
??//?根據(jù)偏移量，計(jì)算?value?的地址。這里的?offset?就是?AtomaicInteger?中的?valueOffset
??jint*?addr?=?(jint?*)?index_oop_from_field_offset_long(p,?offset);
??//?調(diào)用?Atomic?中的函數(shù)?cmpxchg，該函數(shù)聲明于?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");
??/*
???*?根據(jù)操作系統(tǒng)類型調(diào)用不同平臺(tái)下的重載函數(shù)，這個(gè)在預(yù)編譯期間編譯器會(huì)決定調(diào)用哪個(gè)平臺(tái)下的重載
???*?函數(shù)。相關(guān)的預(yù)編譯邏輯如下：
???*?
???*?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?函數(shù)實(shí)現(xiàn)
???*/
??return?(unsigned?int)Atomic::cmpxchg((jint)exchange_value,?(volatile?jint*)dest,
???????????????????????????????????????(jint)compare_value);
}

上面的分析看起來比較多，不過主流程並不復(fù)雜。如果不糾結(jié)於程式碼細(xì)節(jié)，還是比較容易看懂的。接下來，我會(huì)分析 Windows 平臺(tái)下的 Atomic::cmpxchg 函數(shù)。繼續(xù)往下看吧。

//?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 預(yù)先編譯標(biāo)識(shí)符和 cmpxchg 函數(shù)組成。為了看到更清楚一些，我們將 cmpxchg 函數(shù)中的 LOCK_IF_MP 替換為實(shí)際內(nèi)容。如下：

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?0xF0
L0:
????/*
?????*?比較并交換。簡(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
??}
}

到這裡 CAS 的實(shí)作過程就講完了，CAS 的實(shí)作離不開處理器的支援。以上這麼多程式碼，其實(shí)核心程式碼就是一條有l(wèi)ock 前綴的 cmpxchg 指令，也就是lock cmpxchg dword ptr [edx], ecx。

4.ABA 問題

談到 CAS，基本上都要談?wù)?CAS 的 ABA 問題。 CAS 由三個(gè)步驟組成，分別是「讀取->比較->寫回」?？紤]這樣一種情況，執(zhí)行緒1和執(zhí)行緒2同時(shí)執(zhí)行CAS 邏輯，兩個(gè)執(zhí)行緒的執(zhí)行順序如下：

1. #時(shí)刻1：執(zhí)行緒1執(zhí)行讀取操作，取得原值A(chǔ)，然後執(zhí)行緒被切換走
2. 時(shí)刻2：執(zhí)行緒2執(zhí)行完成CAS 操作將原值由A 修改為B
3. 時(shí)刻3：執(zhí)行緒2再次執(zhí)行CAS 操作，並將原值由B 修改為A
4. 時(shí)刻4：執(zhí)行緒1恢復(fù)運(yùn)行，將比較值（compareValue）與原值（oldValue）進(jìn)行比較，發(fā)現(xiàn)兩個(gè)值相等。然後用新值（newValue）寫入記憶體中，完成CAS 操作

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

5.總結(jié)

寫到這裡，這篇文章總算接近尾聲了。雖然 CAS 本身的原理，包括實(shí)作都不是很難，但寫起來真的不太好寫。這裡面牽涉到了一些底層的知識(shí)，雖然能看懂，但想說明白，還是有點(diǎn)難度的。由於我底層的知識(shí)比較欠缺，上面的一些分析難免會(huì)出錯(cuò)。所以如有錯(cuò)誤，請(qǐng)輕噴，當(dāng)然最好能說明怎麼錯(cuò)的，感謝。

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

附錄

在前面原始碼分析一節(jié)中用到的幾個(gè)文件，這裡把路徑貼出來。有助於大家進(jìn)行索引，如下：

openjdk/jdk/src/share/classes/sun/misc/Unsafe.javaopenjdk/ hotspot/src/share/vm/prims/unsafe.cppopenjdk/hotspot/src/share/vm/runtime/atomic.cpp

檔案名稱	#路徑
	#Unsafe.java
	unsafe.cpp
	atomic.cpp

######atomic_windows_x86.inline.hpp######openjdk/hotspot/src/os_cpu/windows_x86/vm/atomic_windows_x86.inline.hpp######## #

以上是介紹Java CAS 原理分析的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！