美團一面：什麼是CAS？有什麼優缺點？我說我只用過AtomicInteger。。。。

来源:https://www.cnblogs.com/coderacademy/p/18228967
-Advertisement-
Play Games

引言 傳統的併發控制手段，如使用synchronized關鍵字或者ReentrantLock等互斥鎖機制，雖然能夠有效防止資源的競爭衝突，但也可能帶來額外的性能開銷，如上下文切換、鎖競爭導致的線程阻塞等。而此時就出現了一種樂觀鎖的策略，以其非阻塞、輕量級的特點，在某些場合下能更好地提升併發性能，其中 ...


引言

傳統的併發控制手段，如使用synchronized關鍵字或者ReentrantLock等互斥鎖機制，雖然能夠有效防止資源的競爭衝突，但也可能帶來額外的性能開銷，如上下文切換、鎖競爭導致的線程阻塞等。而此時就出現了一種樂觀鎖的策略，以其非阻塞、輕量級的特點，在某些場合下能更好地提升併發性能，其中最為關鍵的技術便是Compare And Swap（簡稱CAS）。

關於synchronize的實現原理，請看移步這篇文章：美團一面：說說synchronized的實現原理？問麻了。。。。

關於synchronize的鎖升級，請移步這篇文章：京東二面：Sychronized的鎖升級過程是怎樣的？

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操作邏輯，使得我們可以在更高的抽象層級上進行無鎖併發編程。
image.png
原子類中常見的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中。這樣一來，大部分時候線程間的修改不再是集中在同一個變數上，從而降低了競爭強度，提高了併發性能。

image.png

  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引入了附加的標記位或版本號，以便區分不同的修改序列。

image.png
image.png

總結

Java中的CAS原理及其在併發編程中的應用是一項非常重要的技術。CAS利用CPU硬體提供的原子指令，實現了在無鎖環境下的高效併發控制，避免了傳統鎖機制帶來的上下文切換和線程阻塞開銷。Java通過JNI介面調用底層的CAS指令，封裝在jdk.internal.misc類和java.util.concurrent.atomic包下的原子類中，為我們提供了簡潔易用的API來實現無鎖編程。

CAS在帶來併發性能提升的同時，也可能引發迴圈開銷過大、ABA問題等問題。針對這些問題，Java提供瞭如LongAdder、AtomicStampedReference和AtomicMarkableReference等工具類來解決ABA問題，同時也通過自適應自旋、適時放棄自旋轉而進入阻塞等待等方式降低迴圈開銷。

理解和熟練掌握CAS原理及其在Java中的應用，有助於我們在開發高性能併發程式時作出更明智的選擇，既能提高系統併發性能，又能保證數據的正確性和一致性。

本文已收錄於我的個人博客：碼農Academy的博客，專註分享Java技術乾貨，包括Java基礎、Spring Boot、Spring Cloud、Mysql、Redis、Elasticsearch、中間件、架構設計、面試題、程式員攻略等


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 通過畫布（Canvas）實現 ZLMRTCClient 同一視頻流多次顯示時只拉取一次
    效果預覽 視頻畫面 網路請求 代碼實現 ZLMRTCClient.js 當前使用的版本： 1.0.1 Mon Mar 27 2023 19:11:59 GMT+0800 首先需要修改 ZLMRTCClient.js 的代碼，解決由於網路導致播放失敗時無法觸發 WEBRTC_OFFER_ANWSER_ ...
  • 常用設計模式總結，附完整圖解
    UML類圖 類圖定義規則 屬性和方法前加上（+、-、#、留空）分別代表：公開（public）、私有（private）、保護（protected）、預設（default） 方法括弧內為參數類型，冒號後為返回值類型 下劃線表示 靜態（static），斜體表示 抽象（abstract） 類圖關係表示法 其 ...
  • 心跳包
    什麼是心跳包（心跳機制） 先看一下wiki上的說法： 心跳包（英語：Heartbeat）在電腦科學中指一種周期性的信號，通過硬體或軟體的形式來檢測行為的正常與否，或者與電腦系統是否一致。[1] 通常，機器間會每隔幾秒鐘發送一次心跳包。 如果接收終端沒有在指定時間內（通常是幾個心跳包發送的時間間隔 ...
  • [設計模式]行為型模式-觀察者模式
    前言 觀察者模式（Observer Pattern）是一種行為型設計模式，它定義了一種一對多的依賴關係，當一個對象的狀態發生改變時，其所有依賴者都會收到通知並自動更新。 在觀察者模式中，有兩種主要的角色： 觀察者（Observer）：觀察者是一個介面或抽象類，它定義了一個更新的介面，使得被觀察者在狀 ...
  • Java爬蟲-爬取疫苗批次信息
    今年3月份開始，就接到通知， 根據《關於開展有關人群第二劑次脊髓灰質炎滅活疫苗補種工作的通知》國疾控衛免發〔2024〕1號文件要求，在2016年3月1日至2019年9月30日之間出生的兒童，凡無接種禁忌者，需補齊2劑次脊髓灰質炎滅活疫苗。由於我家一直是異地打針【在外漂打工，懂的都懂】，疫苗本上信息又 ...
  • 面試必會->Redis篇
    01- 你們項目中哪裡用到了Redis ? 在我們的項目中很多地方都用到了Redis , Redis在我們的項目中主要有三個作用 : 使用Redis做熱點數據緩存/介面數據緩存 使用Redis存儲一些業務數據 , 例如 : 驗證碼 , 用戶信息 , 用戶行為數據 , 數據計算結果 , 排行榜數據等 ...
  • 多項分佈模擬及 Seaborn 可視化教程
    多項分佈是二項分佈的推廣，描述了在n次試驗中k種不同事件出現次數的概率分佈。參數包括試驗次數n、結果概率列表pvals（和為1）和輸出形狀size。PMF公式展示了各結果出現次數的概率。NumPy的`random.multinomial()`可生成多項分佈數據。練習包括模擬擲骰子和抽獎活動。解決方案... ...
  • 從零手寫實現 nginx-01-為什麼不能有 java 版本的 nginx?
    前言 大家好，我是老馬。很高興遇到你。 作為一個 java 開發者，工作中一直在使用 nginx。卻發現一直停留在使用層面，無法深入理解。 有一天我在想，為什麼不能有一個 java 版本的 nginx 呢？ 一者是理解 nginx 的設計靈魂，再者 java 開發者用 java 語言的伺服器不是更加 ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類