看AtomicInteger源碼學(xué)習(xí)CAS算法

一、線程

1.1 線程的概述

  • 一個運行程序就是一個進程，而線程是進程中獨立運行的子任務(wù)
  • 線程是操作系統(tǒng)執(zhí)行流中的最小單位，一個進程可以有多個線程，這些線程與該進程共享同一個內(nèi)存空間
  • 線程是系統(tǒng)獨立調(diào)度和分派CPU的基本單位，通常有就緒、運行、阻塞三種基本狀態(tài)
  • 隨著硬件水平的提高，多線程能使系統(tǒng)的運行效率得到大幅度的提高，同時異步操作也增加復(fù)雜度和各種并發(fā)問題

1.2 多線程的風(fēng)險之一上下文切換

上下文切換： CPU通過時間片分配算法來循環(huán)執(zhí)行任務(wù)，當(dāng)前任務(wù)執(zhí)行一個時間片后會切換到下一個任務(wù)。但是，在切換前會保存上一個任務(wù)的狀態(tài)，以便下次切換回這個任務(wù)時可以重新加載這個任務(wù)的狀態(tài)。所有任務(wù)從保存到再加載的過程就是一次上下文切換
多線程性能問題：由于線程有創(chuàng)建和上下文切換的開銷，在多線程環(huán)境下，這種開銷對時間和資源的利用都是一個極大的負(fù)擔(dān)，很可能導(dǎo)致并發(fā)任務(wù)執(zhí)行速度還不如串行快
減少上下文切換： 無鎖并發(fā)編程、CAS算法、減少并發(fā)、使用最少線程、協(xié)程 .

二、并發(fā)編程中的鎖

2.1 悲觀鎖

Java在JDK1.5之前都是靠synchronized關(guān)鍵字保證同步的，這種通過使用一致的鎖定協(xié)議來協(xié)調(diào)對共享狀態(tài)的訪問，可以確保無論哪個線程持有共享變量的鎖，都采用獨占的方式來訪問這些變量。獨占鎖其實就是一種悲觀鎖，所以可以說synchronized是悲觀鎖。存在以下問題：
在多線程競爭下，加鎖、釋放鎖會導(dǎo)致比較多的上下文切換和調(diào)度延時，引起性能問題；一個線程持有鎖會導(dǎo)致其它所有需要此鎖的線程掛起；
如果一個優(yōu)先級高的線程等待一個優(yōu)先級低的線程釋放鎖會導(dǎo)致優(yōu)先級倒置，引起性能風(fēng)險。

2.2 樂觀鎖

樂觀鎖（ Optimistic Locking）其實是一種思想。相對悲觀鎖而言，樂觀鎖假設(shè)認(rèn)為數(shù)據(jù)一般情況下不會造成沖突，所以在數(shù)據(jù)進行提交更新的時候，才會正式對數(shù)據(jù)的沖突與否進行檢測，如果發(fā)現(xiàn)沖突了，則讓返回用戶錯誤的信息，讓用戶決定如何去做。
上面提到的樂觀鎖的概念中其實已經(jīng)闡述了他的具體實現(xiàn)細(xì)節(jié)：主要就是兩個步驟：沖突檢測和數(shù)據(jù)更新。其實現(xiàn)方式有一種比較典型的就是Compare and Swap(CAS)。

三、無鎖執(zhí)行者CAS

3.1 無鎖的概念

在談?wù)摕o鎖概念時，總會關(guān)聯(lián)起樂觀派與悲觀派，對于樂觀派而言，他們認(rèn)為事情總會往好的方向發(fā)展，總是認(rèn)為壞的情況發(fā)生的概率特別小，可以無所顧忌地做事，但對于悲觀派而已，他們總會認(rèn)為發(fā)展事態(tài)如果不及時控制，以后就無法挽回了，即使無法挽回的局面幾乎不可能發(fā)生。這兩種派系映射到并發(fā)編程中就如同加鎖與無鎖的策略，即加鎖是一種悲觀策略，無鎖是一種樂觀策略，因為對于加鎖的并發(fā)程序來說，它們總是認(rèn)為每次訪問共享資源時總會發(fā)生沖突，因此必須對每一次數(shù)據(jù)操作實施加鎖策略。而無鎖則總是假設(shè)對共享資源的訪問沒有沖突，線程可以不停執(zhí)行，無需加鎖，無需等待，一旦發(fā)現(xiàn)沖突，無鎖策略則采用一種稱為CAS的技術(shù)來保證線程執(zhí)行的安全性，這項CAS技術(shù)就是無鎖策略實現(xiàn)的關(guān)鍵，下面我們進一步了解CAS技術(shù)的奇妙之處。

3.2 CAS

CAS是項樂觀鎖技術(shù)，當(dāng)多個線程嘗試使用CAS同時更新同一個變量時，只有其中一個線程能更新變量的值，而其它線程都失敗，失敗的線程并不會被掛起，而是被告知這次競爭中失敗，并可以再次嘗試。其算法核心思想如下

執(zhí)行函數(shù)：CAS(V,E,N)

其包含3個參數(shù)

  • V表示要更新的變量

  • E表示預(yù)期值

  • N表示新值

如果V值等于E值，則將V的值設(shè)為N。若V值和E值不同，則說明已經(jīng)有其他線程做了更新，則當(dāng)前線程什么都不做。通俗的理解就是CAS操作需要我們提供一個期望值，當(dāng)期望值與當(dāng)前線程的變量值相同時，說明還沒線程修改該值，當(dāng)前線程可以進行修改，也就是執(zhí)行CAS操作，但如果期望值與當(dāng)前線程不符，則說明該值已被其他線程修改，此時不執(zhí)行更新操作，但可以選擇重新讀取該變量再嘗試再次修改該變量，也可以放棄操作，原理圖如下:

CAS原理圖

四、Java對CAS的支持

我們以java.util.concurrent中的AtomicInteger為例，看一下在不使用鎖的情況下是如何保證線程安全的。

4.1 AtomicInteger 類的變量以及靜態(tài)代碼塊

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;
    
    //獲取unsafe對象
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    
    //value在內(nèi)存中的地址偏移量  
    private static final long valueOffset;

    static {
        try {
            //獲得value的內(nèi)存地址偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    //當(dāng)前對象代表的值，注意是volatile(**下面會解釋該關(guān)鍵字**)
    private volatile int value;

4.2 深究Unsafe類

從這個類的名字Unsafe上來說這個類就是一個不安全的類，它存在于sun.misc包中，其內(nèi)部方法操作可以像C的指針一樣直接操作內(nèi)存，單從名稱看來就可以知道該類是非安全的，畢竟Unsafe擁有著類似于C的指針操作，因此總是不應(yīng)該首先使用Unsafe類，Java官方也不建議直接使用的Unsafe類，也不開放給用戶直接使用的（當(dāng)然我們還是可以通過其他一些方法用到）。Java 9中將移除 Sun.misc.Unsafe,原文鏈接：https://yq.aliyun.com/articles/87265

@CallerSensitive
    public static Unsafe getUnsafe() {

        //得到調(diào)用者的class對象，這里即是Unsafe
        Class arg = Reflection.getCallerClass();

       //判斷調(diào)用Unsafe的類是否是BootstrapClassLoader加載的類 
        if (!VM.isSystemDomainLoader(arg.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

這個類本身是單例的，需要通過靜態(tài)方法獲取唯一實例。根據(jù)代碼知道應(yīng)該是通過類加載器限制。一般我們寫的類都是由Application ClassLoader（sun.misc.Launcher$AppClassLoader）進行加載的，層級比較低，這里的SystemDomainLoader就是BootstarpClassLoader（C++寫的），也就是加載rt.jar里面的類的加載器，所以Java.xx用就不會有事，我們用就會有事。
想要使用Unsafe有兩種方式。一種是用反射，比較簡單；另外一種是通過虛擬機啟動參數(shù)-Xbootclasspath，把你的classpath變?yōu)閱勇窂街?，這樣就是BootstarpClassLoader加載你的類，跟java.xx一個待遇了，就不會報錯了。可以看到，雖然是可以調(diào)用，但是會有一步判斷，判斷是不是內(nèi)部會檢查該CallerClass是不是由系統(tǒng)類加載器BootstrapClassLoader加載，因為它是不安全的類，官方api也沒有對這個包下的類進行解釋說明，如果是開發(fā)人員引用這個包下的類則會拋錯。由系統(tǒng)類加載器加載的類調(diào)用getClassLoader()會返回null，所以要檢查類是否為bootstrap加載器加載只需要檢查該方法是不是返回null。
下面會重點講解類加載器

4.3 類加載器

從下面的注釋我們可知只要是由bootstrap加載器加載的類，返回值是null，這也就進一步說明了，java官方禁止自定義使用該類。

 /**
     * Returns the class loader for the class.  Some implementations may use
     * null to represent the bootstrap class loader. This method will return
     * null in such implementations if this class was loaded by the bootstrap
     * class loader.
     *
     */
    @CallerSensitive
    public ClassLoader getClassLoader() {
        ClassLoader cl = getClassLoader0();
        if (cl == null)
            return null;

        //JVM安全管理器，這里不做重點介紹
        SecurityManager sm = System.getSecurityManager();
        if (sm != null) {
            ClassLoader.checkClassLoaderPermission(cl, Reflection.getCallerClass());
        }
        return cl;
    }

    ClassLoader getClassLoader0() { return classLoader; }
4.3.1 Class 文件有哪些來源呢?

首先，最常見的是開發(fā)者在應(yīng)用程序中編寫的類，這些類位于項目目錄下；

然后，有 Java 內(nèi)部自帶的 核心類 如 java.lang、java.math、java.io 等 package 內(nèi)部的類，位于 $JAVA_HOME/jre/lib/ 目錄下，如 java.lang.String 類就是定義在 $JAVA_HOME/jre/lib/rt.jar 文件里；

另外，還有 Java 核心擴展類，位于 $JAVA_HOME/jre/lib/ext 目錄下。開發(fā)者也可以把自己編寫的類打包成 jar 文件放入該目錄下；
最后還有一種，是動態(tài)加載遠(yuǎn)程的 .class 文件。

既然有這么多種類的來源，那么在 Java 里，是由某一個具體的 ClassLoader 來統(tǒng)一加載呢？還是由多個 ClassLoader 來協(xié)作加載呢？

4.3.2 哪些 ClassLoader 負(fù)責(zé)加載上面幾類 Class？

首先，我們來看級別最高的 Java 核心類 ，即$JAVA_HOME/jre/lib 里的核心 jar 文件。這些類是 Java 運行的基礎(chǔ)類，由一個名為 BootstrapClassLoader 加載器負(fù)責(zé)加載，它也被稱作 根加載器／引導(dǎo)加載器。注意，BootstrapClassLoader 比較特殊，它不繼承 ClassLoader，而是由 JVM 內(nèi)部實現(xiàn)；

然后，需要加載 Java 核心擴展類 ，即 $JAVA_HOME/jre/lib/ext 目錄下的 jar 文件。這些文件由 ExtensionClassLoader 負(fù)責(zé)加載，它也被稱作 擴展類加載器。當(dāng)然，用戶如果把自己開發(fā)的 jar 文件放在這個目錄，也會被 ExtClassLoader 加載；

接下來是開發(fā)者在項目中編寫的類，這些文件將由 AppClassLoader 加載器進行加載，它也被稱作 系統(tǒng)類加載器 System ClassLoader；

最后，如果想遠(yuǎn)程加載如（本地文件／網(wǎng)絡(luò)下載）的方式，則必須要自己自定義一個 ClassLoader，復(fù)寫其中的 findClass() 方法才能得以實現(xiàn)。

因此能看出，Java 里提供了至少四類 ClassLoader 來分別加載不同來源的 Class。

4.3.4 解壓查看$JAVA_HOME/jre/lib/rt.jar文件
import
isun\misc的Unsafe類

通過上面兩個圖，證明了，Unsafe類是由BootstrapClassLoader 加載器加載的，所以在獲取classLoader時正常情況下是返回null。

4.3.5 CallerSensitive注解是什么鬼？

細(xì)心的同學(xué)可能已經(jīng)發(fā)現(xiàn)上面獲取類加載器的方法上有該注解，那么它的作用是啥呢？我們先看stackoverflow網(wǎng)站給出的答案

CallerSensitive

簡而言之，用@CallerSensitive注解修飾的方法從一開始就知道具體調(diào)用它的對象，這樣就不用再經(jīng)過一系列的檢查才能確定具體調(diào)用它的對象了。它實際上是調(diào)用sun.reflect.Reflection.getCallerClass方法。

4.4 說下AtomicInteger類的getAndIncrement方法

 public final int getAndIncrement() {

        // 當(dāng)前值加1返回舊值，底層CAS操作
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

//Unsafe類中的getAndAddInt方法
public final int getAndAddInt(Object o, long offset, int x) {
        int expected;
        do {
            //獲得給定對象的指定偏移量offset的int值，使用volatile語義，總能獲取到最新的int值。
            expected= this.getIntVolatile(o, offset);

        //第一個參數(shù)o為給定對象，offset為對象內(nèi)存的偏移量，通過這個偏移量迅速定位字段并設(shè)置或獲取該字段的值，expected表示期望值，expected+x表示要設(shè)置的值。
        } while (!this.compareAndSwapInt(o, offset, expected, expected+ x));

        return expected;
    }

4.5 看線程的掛起與恢復(fù)理解Unsafe運行機制

將一個線程進行掛起是通過park方法實現(xiàn)的，調(diào)用 park后，線程將一直阻塞直到超時或者中斷等條件出現(xiàn)。unpark可以終止一個掛起的線程，使其恢復(fù)正常。Java對線程的掛起操作被封裝在 LockSupport類中，LockSupport類中有各種版本pack方法，其底層實現(xiàn)最終還是使用Unsafe.park()方法和Unsafe.unpark()方法

//線程調(diào)用該方法，線程將一直阻塞直到超時，或者是中斷條件出現(xiàn)。  
public native void park(boolean isAbsolute, long time);  

//終止掛起的線程，恢復(fù)正常.java.util.concurrent包中掛起操作都是在LockSupport類實現(xiàn)的，其底層正是使用這兩個方法，  
public native void unpark(Object thread);

4.6 通過例子加深對Unsafe的理解

 private static Unsafe unsafe;

    public static void main(String[] args) {

        try {
            //通過反射獲取rt.jar下的Unsafe類
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            // 設(shè)置該Field為可訪問
            field.setAccessible(true);
            // 通過Field得到該Field對應(yīng)的具體對象，傳入null是因為該Field為static的
            unsafe = (Unsafe) field.get(null);
            Integer target = 12;
            //compareAndSwapInt方法的屬性分別是：目標(biāo)對象實例，目標(biāo)對象屬性偏移量，當(dāng)前預(yù)期值，要設(shè)的值.
            //compareAndSwapInt方法是通過反射修改對象的值，具體修改對象下面那個值，可以通過偏移量，對象字段的偏移量可以通過objectFieldOffset獲取
            System.out.println(unsafe.compareAndSwapInt(target, 12, 12, 24));
        } catch (Exception e) {
            System.out.println("Get Unsafe instance occur error" + e);
        }
    }

輸入不同的參數(shù)得到以下結(jié)果：

正確的期望值
錯誤的期望值

4.7 CAS的ABA問題及其解決方案

CAS算法實現(xiàn)一個重要前提需要取出內(nèi)存中某時刻的數(shù)據(jù)，而在下時刻比較并替換（比較和交換是原子性），如果在取出和比較并交換之間發(fā)生數(shù)據(jù)變化而不能察覺，就出現(xiàn)所謂的ABA問題了。


image.png

ABA問題導(dǎo)致的原因，是CAS過程中只簡單進行了“值”的校驗，再有些情況下，“值”相同不會引入錯誤的業(yè)務(wù)邏輯（例如庫存），有些情況下，“值”雖然相同，卻已經(jīng)不是原來的數(shù)據(jù)了。

優(yōu)化方向：CAS不能只比對“值”，還必須確保的是原來的數(shù)據(jù)，才能修改成功。

常見實踐：“版本號”的比對，一個數(shù)據(jù)一個版本，版本變化，即使值相同，也不應(yīng)該修改成功。

五、對volatile關(guān)鍵字的理解

5.1 volatile寫操作的內(nèi)存語義

當(dāng)寫一個volatile變量時，JMM會把該線程對應(yīng)的本地內(nèi)存中的共享變量刷新到主內(nèi)存

寫操作

5.2 volatile讀操作的內(nèi)存語義

讀操作

5.3 變量在內(nèi)存中的工作過程

image.png

5.4 volatile非原子原因

  • 多線程環(huán)境下，"數(shù)據(jù)計算"和"數(shù)據(jù)賦值"操作可能多次出現(xiàn)，即操作非原子
  • 若數(shù)據(jù)在加載之后，若主內(nèi)存count變量發(fā)生修改之后，由于線程工作內(nèi)存中的值在此前已經(jīng)加載，從而不會對變更操作做出相應(yīng)變化，即私有內(nèi)存和公共內(nèi)存中變量不同步，進而導(dǎo)致數(shù)據(jù)不一致
  • 對于volatile變量，JVM只是保證從主內(nèi)存加載到線程工作內(nèi)存的值是最新的，也就是數(shù)據(jù)加載時是最新的。由此可見volatile解決的是變量讀時的可見性問題，但無法保證原子性，對于多線程修改共享變量的場景必須使用加鎖同步

六、參考文章

偶然的機會看了下面其中一篇文章便開始對cas產(chǎn)生了興趣，激起我繼續(xù)看源碼寫文章的激情。感謝下面的作者們，深度好文！

https://www.zybuluo.com/kiraSally/note/850631
http://www.10tiao.com/html/249/201706/2651960240/1.html
https://juejin.im/entry/595c599e6fb9a06bc6042514

最后編輯于 ：
?著作權(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)容