美團一面：什么是CAS？有什么優缺點？我說我知道AtomicInteger
引言
傳統的并發控制手段，如使用synchronized關鍵字或者ReentrantLock等互斥鎖機制，雖然能夠有效防止資源的競爭沖突，但也可能帶來額外的性能開銷，如上下文切換、鎖競爭導致的線程阻塞等。而此時就出現了一種樂觀鎖的策略，以其非阻塞、輕量級的特點，在某些場合下能更好地提升并發性能，其中最為關鍵的技術便是Compare And Swap（簡稱CAS）。
CAS是一種無鎖算法，它在硬件級別提供了原子性的條件更新操作，允許線程在不加鎖的情況下實現對共享變量的修改。在Java中，CAS機制被廣泛應用于java.util.concurrent.atomic包下的原子類以及高級并發工具類如AbstractQueuedSynchronizer（AQS）的實現中。
CAS的基本概念與原理
CAS是一種原子指令，常用于多線程環境中的無鎖算法。CAS操作包含三個基本操作數：內存位置、期望值和新值。在執行CAS操作時，計算機會檢查內存位置當前是否存放著期望值，如果是，則將內存位置的值更新為新值；若不是，則不做任何修改，保持原有值不變，并返回當前內存位置的實際值。
在Java中，CAS機制被封裝在jdk.internal.misc.Unsafe類中，盡管這個類并不建議在普通應用程序中直接使用，但它是構建更高層次并發工具的基礎，例如java.util.concurrent.atomic包下的原子類如AtomicInteger、AtomicLong等。這些原子類通過JNI調用底層硬件提供的CAS指令，從而在Java層面上實現了無鎖并發操作。
這里指的注意的是，在JDK1.9之前CAS機制被封裝在sun.misc.Unsafe類中，在JDK1.9之后就使用了 jdk.internal.misc.Unsafe。這點由java.util.concurrent.atomic包下的原子類可以看出來。而sun.misc.Unsafe被許多第三方庫所使用。
CAS實現原理
在Java中，雖然Java語言本身并未直接提供CAS這樣的原子指令，但是Java可以通過JNI調用本地方法來利用硬件級別的原子指令實現CAS操作。在Java的標準庫中，特別是jdk.internal.misc.Unsafe類提供了一系列compareAndSwapXXX方法，這些方法底層確實是通過C++編寫的內聯匯編來調用對應CPU架構的cmpxchg指令，從而實現原子性的比較和交換操作。
cmpxchg指令是多數現代CPU支持的原子指令，它能在多線程環境下確保一次比較和交換操作的原子性，有效解決了多線程環境下數據競爭的問題，避免了數據不一致的情況。例如，在更新一個共享變量時，如果期望值與當前值相匹配，則原子性地更新為新值，否則不進行更新操作，這樣就能在無鎖的情況下實現對共享資源的安全訪問。 我們以java.util.concurrent.atomic包下的AtomicInteger為例，分析其compareAndSet方法。
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
//由這里可以看出來，依賴jdk.internal.misc.Unsafe實現的
private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");
private volatile int value;
public final boolean compareAndSet(int expectedValue, int newValue) {
// 調用 jdk.internal.misc.Unsafe的compareAndSetInt方法
return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
}
}Unsafe中的compareAndSetInt使用了@HotSpotIntrinsicCandidate注解修飾，@HotSpotIntrinsicCandidate注解是Java HotSpot虛擬機（JVM）的一個特性注解，它表明標注的方法有可能會被HotSpot JVM識別為“內聯候選”，當JVM發現有方法被標記為內聯候選時，會嘗試利用底層硬件提供的原子指令（比如cmpxchg指令）直接替換掉原本的Java方法調用，從而在運行時獲得更好的性能。
public final class Unsafe {
@HotSpotIntrinsicCandidate
public final native boolean compareAndSetInt(Object o, long offset,
int expected,
int x);
}compareAndSetInt這個方法我們可以從openjdk的hotspot源碼（位置：hotspot/src/share/vm/prims/unsafe.cpp）中可以找到：
{CC "compareAndSetObject",CC "(" OBJ "J" OBJ "" OBJ ")Z", FN_PTR(Unsafe_CompareAndSetObject)},
{CC "compareAndSetInt", CC "(" OBJ "J""I""I"")Z", FN_PTR(Unsafe_CompareAndSetInt)},
{CC "compareAndSetLong", CC "(" OBJ "J""J""J"")Z", FN_PTR(Unsafe_CompareAndSetLong)},
{CC "compareAndExchangeObject", CC "(" OBJ "J" OBJ "" OBJ ")" OBJ, FN_PTR(Unsafe_CompareAndExchangeObject)},
{CC "compareAndExchangeInt", CC "(" OBJ "J""I""I"")I", FN_PTR(Unsafe_CompareAndExchangeInt)},
{CC "compareAndExchangeLong", CC "(" OBJ "J""J""J"")J", FN_PTR(Unsafe_CompareAndExchangeLong)},關于openjdk的源碼，本文源碼版本為1.9，如需要該版本源碼或者其他版本下載方法，請關注本公眾號【碼農Academy】后，后臺回復【openjdk】獲取
而hostspot中的Unsafe_CompareAndSetInt函數會統一調用Atomic的cmpxchg函數：
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
oop p = JNIHandles::resolve(obj);
jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);
// 統一調用Atomic的cmpxchg函數
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
} UNSAFE_END而Atomic的cmpxchg函數源碼(位置：hotspot/src/share/vm/runtime/atomic.hpp)如下：
/**
*這是按字節大小進行的`cmpxchg`操作的默認實現。它使用按整數大小進行的`cmpxchg`來模擬按字節大小進行的`cmpxchg`。不同的平臺可以通過定義自己的內聯定義以及定義`VM_HAS_SPECIALIZED_CMPXCHG_BYTE`來覆蓋這個默認實現。這將導致使用特定于平臺的實現而不是默認實現。
* exchange_value：要交換的新值。
* dest：指向目標字節的指針。
* compare_value：要比較的值。
* order：內存順序。
*/
inline jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte* dest,
jbyte compare_value, cmpxchg_memory_order order) {
STATIC_ASSERT(sizeof(jbyte) == 1);
volatile jint* dest_int =
static_cast<volatile jint*>(align_ptr_down(dest, sizeof(jint)));
size_t offset = pointer_delta(dest, dest_int, 1);
// 獲取當前整數大小的值，并將其轉換為字節數組。
jint cur = *dest_int;
jbyte* cur_as_bytes = reinterpret_cast<jbyte*>(&cur);
// 設置當前整數中對應字節的值為compare_value。這確保了如果初始的整數值不是我們要找的值，那么第一次的cmpxchg操作會失敗。
cur_as_bytes[offset] = compare_value;
// 在循環中，不斷嘗試更新目標字節的值。
do {
// new_val
jint new_value = cur;
// 復制當前整數值，并設置其中對應字節的值為exchange_value。
reinterpret_cast<jbyte*>(&new_value)[offset] = exchange_value;
// 嘗試使用新的整數值替換目標整數。
jint res = cmpxchg(new_value, dest_int, cur, order);
if (res == cur) break; // 如果返回值與原始整數值相同，說明操作成功。
// 更新當前整數值為cmpxchg操作的結果。
cur = res;
// 如果目標字節的值仍然是我們之前設置的值，那么繼續循環并再次嘗試。
} while (cur_as_bytes[offset] == compare_value);
// 返回更新后的字節值
return cur_as_bytes[offset];
}而由cmpxchg函數中的do...while我們也可以看出，當多個線程同時嘗試更新同一內存位置，且它們的期望值相同但只有一個線程能夠成功更新時，其他線程的CAS操作會失敗。對于失敗的線程，常見的做法是采用自旋鎖的形式，即循環重試直到成功為止。這種方式在低競爭或短時間窗口內的并發更新時，相比于傳統的鎖機制，它避免了線程的阻塞和喚醒帶來的開銷，所以它的性能會更優。
Java中的CAS實現與API
在Java中，CAS操作的實現主要依賴于兩個關鍵組件：sun.misc.Unsafe類、jdk.internal.misc.Unsafe類以及java.util.concurrent.atomic包下的原子類。盡管Unsafe類提供了對底層硬件原子操作的直接訪問，但由于其API是非公開且不穩定的，所以在常規開發中并不推薦直接使用。Java標準庫提供了豐富的原子類，它們是基于Unsafe封裝的安全、便捷的CAS操作實現。
java.util.concurrent.atomic包
Java標準庫中的atomic包為開發者提供了許多原子類，如AtomicInteger、AtomicLong、AtomicReference等，它們均內置了CAS操作邏輯，使得我們可以在更高的抽象層級上進行無鎖并發編程。
圖片
原子類中常見的CAS操作API包括：
? compareAndSet(expectedValue, newValue)：嘗試將當前值與期望值進行比較，如果一致則將值更新為新值，返回是否更新成功的布爾值。
? getAndAdd(delta)：原子性地將當前值加上指定的delta值，并返回更新前的原始值。
? getAndSet(newValue)：原子性地將當前值設置為新值，并返回更新前的原始值。
這些方法都是基于CAS原理，能夠在多線程環境下保證對變量的原子性修改，從而在不引入鎖的情況下實現高效的并發控制。
CAS的優缺點與適用場景
CAS摒棄了傳統的鎖機制，避免了因獲取和釋放鎖產生的上下文切換和線程阻塞，從而顯著提升了系統的并發性能。并且由于CAS操作是基于硬件層面的原子性保證，所以它不會出現死鎖問題，這對于復雜并發場景下的程序設計特別重要。另外，CAS策略下線程在無法成功更新變量時不需要掛起和喚醒，只需通過簡單的循環重試即可。
但是，在高并發條件下，頻繁的CAS操作可能導致大量的自旋重試，消耗大量的CPU資源。尤其是在競爭激烈的場景中，線程可能花費大量的時間在不斷地嘗試更新變量，而不是做有用的工作。這個由剛才cmpxchg函數可以看出。對于這個問題，我們可以參考synchronize中輕量級鎖經過自旋，超過一定閾值后升級為重量級鎖的原理，我們也可以給自旋設置一個次數，如果超過這個次數，就把線程掛起或者執行失敗。(自適應自旋)
另外，Java中的原子類也提供了解決辦法，比如LongAdder以及DoubleAdder等，LongAdder過分散競爭點來減少自旋鎖的沖突。它并沒有像AtomicLong那樣維護一個單一的共享變量，而是維護了一個Base值和一組Cell（桶）結構。每個Cell本質上也是一個可以進行原子操作的計數器，多個線程可以分別在一個獨立的Cell上進行累加，只有在必要時才將各個Cell的值匯總到Base中。這樣一來，大部分時候線程間的修改不再是集中在同一個變量上，從而降低了競爭強度，提高了并發性能。
圖片
1. ABA問題： 單純的CAS無法識別一個值被多次修改后又恢復原值的情況，可能導致錯誤的判斷。比如現在有三個線程：image.png即線程1將str從A改成了B，然后線程3將str又從B改成了A，而此時對于線程2來說，他就覺得這個值還是A，所以就不會在更改了。
圖片
而對于這個問題，其實也很好解決，我們給這個數據加上一個時間戳或者版本號（樂觀鎖概念）。即每次不僅比較值，還會比較版本。比如上述示例，初始時str的值的版本是1，然后線程2操作后值變成B，而對應版本變成了2，然后線程3操作后值變成了A，版本變成了3，而對于線程2來說，雖然值還是A，但是版本號變了，所以線程2依然會執行替換的操作。
Java的原子類就提供了類似的實現，如AtomicStampedReference和AtomicMarkableReference引入了附加的標記位或版本號，以便區分不同的修改序列。
圖片
圖片
總結
Java中的CAS原理及其在并發編程中的應用是一項非常重要的技術。CAS利用CPU硬件提供的原子指令，實現了在無鎖環境下的高效并發控制，避免了傳統鎖機制帶來的上下文切換和線程阻塞開銷。Java通過JNI接口調用底層的CAS指令，封裝在jdk.internal.misc類和java.util.concurrent.atomic包下的原子類中，為我們提供了簡潔易用的API來實現無鎖編程。
CAS在帶來并發性能提升的同時，也可能引發循環開銷過大、ABA問題等問題。針對這些問題，Java提供了如LongAdder、AtomicStampedReference和AtomicMarkableReference等工具類來解決ABA問題，同時也通過自適應自旋、適時放棄自旋轉而進入阻塞等待等方式降低循環開銷。
理解和熟練掌握CAS原理及其在Java中的應用，有助于我們在開發高性能并發程序時作出更明智的選擇，既能提高系統并發性能，又能保證數據的正確性和一致性。
