前言

Java并發編程系列第四篇AbstractQueuedSynchronizer，文章風格依然是圖文并茂，通俗易懂，本文帶讀者們深入理解AbstractQueuedSynchronizer設計思想，

內容大綱

基礎

AbstractQueuedSynchronizer抽象同步佇列簡稱A Q S，它是實作同步器的基礎組件，如常用的ReentrantLock、Semaphore、CountDownLatch等，

A Q S定義了一套多執行緒訪問共享資源的同步模板，解決了實作同步器時涉及的大量細節問題，能夠極大地減少實作作業，雖然大多數開發者可能永遠不會使用A Q S實作自己的同步器（J U C包下提供的同步器基本足夠應對日常開發），但是知道A Q S的原理對于架構設計還是很有幫助的，面試還可以吹吹牛，下面是A Q S的組成結構，

三部分組成，state同步狀態、Node組成的CLH佇列、ConditionObject條件變數（包含Node組成的條件單向佇列），下面會分別對這三部分做介紹，

先貼下AbstractQueuedSynchronizer提供的核心函式，混個臉熟就夠了，后面會講解

狀態

• getState()：回傳同步狀態
• setState(int newState)：設定同步狀態
• compareAndSetState(int expect, int update)：使用C A S設定同步狀態
• isHeldExclusively()：當前執行緒是否持有資源

獨占資源（不回應執行緒中斷）

• tryAcquire(int arg)：獨占式獲取資源，子類實作
• acquire(int arg)：獨占式獲取資源模板
• tryRelease(int arg)：獨占式釋放資源，子類實作
• release(int arg)：獨占式釋放資源模板

共享資源（不回應執行緒中斷）

• tryAcquireShared(int arg)：共享式獲取資源，回傳值大于等于0則表示獲取成功，否則獲取失敗，子類實作
• acquireShared(int arg)：共享形獲取資源模板
• tryReleaseShared(int arg)：共享式釋放資源，子類實作
• releaseShared(int arg)：共享式釋放資源模板

這里補充下，獲取獨占、共享資源操作還提供超時與回應中斷的擴展函式，有興趣的讀者可以去AbstractQueuedSynchronizer原始碼了解，

同步狀態

在A Q S中維護了一個同步狀態變數state，getState函式獲取同步狀態，setState、compareAndSetState函式修改同步狀態，對于A Q S來說，執行緒同步的關鍵是對state的操作，可以說獲取、釋放資源是否成功都是由state決定的，比如state>0代表可獲取資源，否則無法獲取，所以state的具體語意由實作者去定義，現有的ReentrantLock、ReentrantReadWriteLock、Semaphore、CountDownLatch定義的state語意都不一樣，

• ReentrantLock的state用來表示是否有鎖資源
• ReentrantReadWriteLock的state高16位代表讀鎖狀態，低16位代表寫鎖狀態
• Semaphore的state用來表示可用信號的個數
• CountDownLatch的state用來表示計數器的值

CLH佇列

CLH是A Q S內部維護的FIFO（先進先出）雙端雙向佇列（方便尾部節點插入），基于鏈表資料結構，當一個執行緒競爭資源失敗，就會將等待資源的執行緒封裝成一個Node節點，通過C A S原子操作插入佇列尾部，最終不同的Node節點連接組成了一個CLH佇列，所以說A Q S通過CLH佇列管理競爭資源的執行緒，個人總結CLH佇列具有如下幾個優點：

• 先進先出保證了公平性
• 非阻塞的佇列，通過自旋鎖和C A S保證節點插入和移除的原子性，實作無鎖快速插入
• 采用了自旋鎖思想，所以CLH也是一種基于鏈表的可擴展、高性能、公平的自旋鎖

Node內部類

Node是A Q S的內部類，每個等待資源的執行緒都會封裝成Node節點組成C L H佇列、等待佇列，所以說Node是非常重要的部分，理解它是理解A Q S的第一步，

列Node類中的變數都很好理解，只有waitStatus、nextWaiter沒有細說，下面做個補充說明

waitStatus等待狀態如下

nextWaiter特殊標記

• Node在CLH佇列時，nextWaiter表示共享式或獨占式標記
• Node在條件佇列時，nextWaiter表示下個Node節點指標

流程概述

執行緒獲取資源失敗，封裝成Node節點從C L H佇列尾部入隊并阻塞執行緒，某執行緒釋放資源時會把C L H佇列首部Node節點關聯的執行緒喚醒（此處的首部是指第二個節點，后面會細說），再次獲取資源，

入隊

獲取資源失敗的執行緒需要封裝成Node節點，接著尾部入隊，在A Q S中提供addWaiter函式完成Node節點的創建與入隊，

   /**
     * @author: 程式猿阿星
     * @description:  Node節點入隊-CLH佇列
     * @param mode 標記  Node.EXCLUSIVE獨占式 or Node.SHARED共享式
     */
    private Node addWaiter(Node mode) {
        //根據當前執行緒創建節點，等待狀態為0
        Node node = new Node(Thread.currentThread(), mode);
        // 獲取尾節點
        Node pred = tail;
        if (pred != null) {
            //如果尾節點不等于null，把當前節點的前驅節點指向尾節點
            node.prev = pred;
            //通過cas把尾節點指向當前節點
            if (compareAndSetTail(pred, node)) {
                //之前尾節點的下個節點指向當前節點
                pred.next = node;
                return node;
            }
        }
        //如果添加失敗或佇列不存在，執行end函式
        enq(node);
        return node;
    }

添加節點的時候，如果從C L H佇列已經存在，通過C A S快速將當前節點添加到佇列尾部，如果添加失敗或佇列不存在，則指向enq函式自旋入隊，

    /**
     * @author: 程式猿阿星
     * @description: 自旋cas入隊
     * @param node 節點
     */
    private Node enq(final Node node) {
        for (;;) { //回圈
            //獲取尾節點
            Node t = tail;
            if (t == null) {
                //如果尾節點為空，創建哨兵節點，通過cas把頭節點指向哨兵節點
                if (compareAndSetHead(new Node()))
                    //cas成功，尾節點指向哨兵節點
                    tail = head;
            } else {
                //當前節點的前驅節點設指向之前尾節點
                node.prev = t;
                //cas設定把尾節點指向當前節點
                if (compareAndSetTail(t, node)) {
                    //cas成功，之前尾節點的下個節點指向當前節點
                    t.next = node;
                    return t;
                }
            }
        }
    }

通過自旋C A S嘗試往佇列尾部插入節點，直到成功，自旋程序如果發現C L H佇列不存在時會初始化C L H佇列，入隊程序流程如下圖

第一次回圈

1. 剛開始C L H佇列不存在，head與tail都指向null
2. 要初始化C L H佇列，會創建一個哨兵節點，head與tail都指向哨兵節點

第二次回圈
3. 當前執行緒節點的前驅節點指向尾部節點（哨兵節點）
4. 設定當前執行緒節點為尾部，tail指向當前執行緒節點
5. 前尾部節點的后驅節點指向當前執行緒節點（當前尾部節點）

最后結合addWaiter與enq函式的入隊流程圖如下

出隊

C L H佇列中的節點都是獲取資源失敗的執行緒節點，當持有資源的執行緒釋放資源時，會將head.next指向的執行緒節點喚醒（C L H佇列的第二個節點），如果喚醒的執行緒節點獲取資源成功，執行緒節點清空資訊設定為頭部節點（新哨兵節點），原頭部節點出隊（原哨兵節點）

acquireQueued函式中的部分代碼

//1.獲取前驅節點
final Node p = node.predecessor();
//如果前驅節點是首節點，獲取資源（子類實作）
if (p == head && tryAcquire(arg)) {
    //2.獲取資源成功，設定當前節點為頭節點，清空當前節點的資訊，把當前節點變成哨兵節點
    setHead(node);
    //3.原來首節點下個節點指向為null
    p.next = null; // help GC
    //4.非例外狀態，防止指向finally邏輯
    failed = false;
    //5.回傳執行緒中斷狀態
    return interrupted;
}

private void setHead(Node node) {
    //節點設定為頭部
    head = node;
    //清空執行緒
    node.thread = null;
    //清空前驅節點
    node.prev = null;
}

只需要關注1~3步驟即可，程序非常簡單，假設獲取資源成功，更換頭部節點，并把頭部節點的資訊清除變成哨兵節點，注意這個程序是不需要使用C A S來保證，因為只有一個執行緒能夠成功獲取到資源，

條件變數

Object的wait、notify函式是配合Synchronized鎖實作執行緒間同步協作的功能，A Q S的ConditionObject條件變數也提供這樣的功能，通過ConditionObject的await和signal兩類函式完成，

不同于Synchronized鎖，一個A Q S可以對應多個條件變數，而Synchronized只有一個，

如上圖所示，ConditionObject內部維護著一個單向條件佇列，不同于C H L佇列，條件佇列只入隊執行await的執行緒節點，并且加入條件佇列的節點，不能在C H L佇列， 條件佇列出隊的節點，會入隊到C H L佇列，

當某個執行緒執行了ConditionObject的await函式，阻塞當前執行緒，執行緒會被封裝成Node節點添加到條件佇列的末端，其他執行緒執行ConditionObject的signal函式，會將條件佇列頭部執行緒節點轉移到C H L佇列參與競爭資源，具體流程如下圖

最后補充下，條件佇列Node類是使用nextWaiter變數指向下個節點，并且因為是單向佇列，所以prev與next變數都是null

進階

A Q S采用了模板方法設計模式，提供了兩類模板，一類是獨占式模板，另一類是共享形模式，對應的模板函式如下

• 獨占式
  • acquire獲取資源
  • release釋放資源
• 共享式
  • acquireShared獲取資源
  • releaseShared釋放資源

獨占式獲取資源

acquire是個模板函式，模板流程就是執行緒獲取共享資源，如果獲取資源成功，執行緒直接回傳，否則進入CLH佇列，直到獲取資源成功為止，且整個程序忽略中斷的影響，acquire函式代碼如下

• 執行tryAcquire函式，tryAcquire是由子類實作，代表獲取資源是否成功，如果資源獲取失敗，執行下面的邏輯
• 執行addWaiter函式（前面已經介紹過），根據當前執行緒創建出獨占式節點，并入隊CLH佇列
• 執行acquireQueued函式，自旋阻塞等待獲取資源
• 如果acquireQueued函式中獲取資源成功，根據執行緒是否被中斷狀態，來決定執行執行緒中斷邏輯

acquire函式的大致流程都清楚了，下面來分析下acquireQueued函式，執行緒封裝成節點后，是如何自旋阻塞等待獲取資源的，代碼如下

    /**
     * @author: 程式猿阿星
     * @description: 自旋機制等待獲取資源
     * @param node
     * @param arg
     * @return: boolean
     */
    final boolean acquireQueued(final Node node, int arg) {
        //例外狀態，默認是
        boolean failed = true;
        try {
            //該執行緒是否中斷過，默認否
            boolean interrupted = false;
            for (;;) {//自旋
                //獲取前驅節點
                final Node p = node.predecessor();
                //如果前驅節點是首節點，獲取資源（子類實作）
                if (p == head && tryAcquire(arg)) {
                    //獲取資源成功，設定當前節點為頭節點，清空當前節點的資訊，把當前節點變成哨兵節點
                    setHead(node);
                    //原來首節點下個節點指向為null
                    p.next = null; // help GC
                    //非例外狀態，防止指向finally邏輯
                    failed = false;
                    //回傳執行緒中斷狀態
                    return interrupted;
                }
                /**
                 * 如果前驅節點不是首節點，先執行shouldParkAfterFailedAcquire函式，shouldParkAfterFailedAcquire做了三件事
                 * 1.如果前驅節點的等待狀態是SIGNAL，回傳true，執行parkAndCheckInterrupt函式，回傳false
                 * 2.如果前驅節點的等大狀態是CANCELLED，把CANCELLED節點全部移出佇列（條件節點）
                 * 3.以上兩者都不符合，更新前驅節點的等待狀態為SIGNAL，回傳false
                 */
                if (shouldParkAfterFailedAcquire(p, node) &&
                    //使用LockSupport類的靜態方法park掛起當前執行緒，直到被喚醒，喚醒后檢查當前執行緒是否被中斷，回傳該執行緒中斷狀態并重置中斷狀態
                    parkAndCheckInterrupt())
                    //該執行緒被中斷過
                    interrupted = true;
                }
            } finally {
                // 嘗試獲取資源失敗并執行例外，取消請求，將當前節點從佇列中移除
                if (failed)
                    cancelAcquire(node);
            }
    }

一圖勝千言，核心流程圖如下

獨占式釋放資源

有獲取資源，自然就少不了釋放資源，A Q S中提供了release模板函式來釋放資源，模板流程就是執行緒釋放資源成功，喚醒CLH佇列的第二個執行緒節點（首節點的下個節點），代碼如下

    /**
     * @author: 程式猿阿星
     * @description: 獨占式-釋放資源模板函式
     * @param arg
     * @return: boolean
     */
    public final boolean release(int arg) {

        if (tryRelease(arg)) {//釋放資源成功，tryRelease子類實作
            //獲取頭部執行緒節點
            Node h = head;
            if (h != null && h.waitStatus != 0) //頭部執行緒節點不為null，并且等待狀態不為0
                //喚醒CHL佇列第二個執行緒節點
                unparkSuccessor(h);
            return true;
        }
        return false;
    }
    
    
    private void unparkSuccessor(Node node) {
        //獲取節點等待狀態
        int ws = node.waitStatus;
        if (ws < 0)
            //cas更新節點狀態為0
            compareAndSetWaitStatus(node, ws, 0);
    
        //獲取下個執行緒節點        
        Node s = node.next;
        if (s == null || s.waitStatus > 0) { //如果下個節點資訊例外，從尾節點回圈向前獲取到正常的節點為止，正常情況不會執行
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            //喚醒執行緒節點
            LockSupport.unpark(s.thread);
        }
    }

release邏輯非常簡單，流程圖如下

共享式獲取資源

acquireShared是個模板函式，模板流程就是執行緒獲取共享資源，如果獲取到資源，執行緒直接回傳，否則進入CLH佇列，直到獲取到資源為止，且整個程序忽略中斷的影響，acquireShared函式代碼如下

    /**
     * @author: 程式猿阿星
     * @description: 共享式-獲取資源模板函式
     * @param arg
     * @return: void
     */
    public final void acquireShared(int arg) {
        /**
         * 1.負數表示失敗
         * 2.0表示成功，但沒有剩余可用資源
         * 3.正數表示成功且有剩余資源
         */
        if (tryAcquireShared(arg) < 0) //獲取資源失敗，tryAcquireShared子類實作
            //自旋阻塞等待獲取資源
            doAcquireShared(arg);
    }
    
    

doAcquireShared函式與獨占式的acquireQueued函式邏輯基本一致，唯一的區別就是下圖紅框部分

• 節點的標記是共享式
• 獲取資源成功，還會喚醒后續資源，因為資源數可能>0，代表還有資源可獲取，所以需要做后續執行緒節點的喚醒

共享式釋放資源

A Q S中提供了releaseShared模板函式來釋放資源，模板流程就是執行緒釋放資源成功，喚醒CHL佇列的第二個執行緒節點（首節點的下個節點），代碼如下

    /**
     * @author: 程式猿阿星
     * @description: 共享式-釋放資源模板函式
     * @param arg
     * @return: boolean
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {//釋放資源成功，tryReleaseShared子類實作
            //喚醒后繼節點
            doReleaseShared();
            return true;
        }
        return false;
    }
    
    private void doReleaseShared() {
        for (;;) {
            //獲取頭節點
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
    
                if (ws == Node.SIGNAL) {//如果頭節點等待狀態為SIGNAL
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))//更新頭節點等待狀態為0
                        continue;            // loop to recheck cases
                    //喚醒頭節點下個執行緒節點
                    unparkSuccessor(h);
                }
                //如果后繼節點暫時不需要被喚醒，更新頭節點等待狀態為PROPAGATE
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;               
            }
            if (h == head)              
                break;
        }
    }

與獨占式釋放資源區別不大，都是喚醒頭節點的下個節點，就不做過多描述了，

實戰

說了這么多理論，現在到實戰環節了，正如前文所述，A Q S定義了一套多執行緒訪問共享資源的同步模板，解決了實作同步器時涉及的大量細節問題，能夠極大地減少實作作業，現在我們基于A Q S實作一個不可重入的獨占鎖，直接使用A Q S提供的獨占式模板，只需明確state的語意與實作tryAcquire與tryRelease函式（獲取資源與釋放資源），在這里state為0表示鎖沒有被執行緒持有，state為1表示鎖已經被某個執行緒持有，由于是不可重入鎖，所以不需要記錄持有鎖執行緒的獲取鎖次數，

不可重入的獨占鎖代碼如下

/**
 * @Author 程式猿阿星
 * @Description 不可重入的獨占鎖
 */
public class NonReentrantLock implements Lock {


    /**
     * @Author 程式猿阿星
     * @Description 自定義同步器
     */
    private static class Sync extends AbstractQueuedSynchronizer {

        /**
         * 鎖是否被執行緒持有
         */
        @Override
        protected boolean isHeldExclusively() {
            //0：未持有 1：已持有
            return super.getState() == 1;
        }

        /**
         * 獲取鎖
         */
        @Override
        protected boolean tryAcquire(int arg) {
            if (arg != 1) {
                //獲取鎖操作，是需要把state更新為1，所以arg必須是1
                throw new RuntimeException("arg not is 1");
            }
            if (compareAndSetState(0, arg)) {//cas 更新state為1成功，代表獲取鎖成功
                //設定持有鎖執行緒
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }

        /**
         * 釋放鎖
         */
        @Override
        protected boolean tryRelease(int arg) {
            if (arg != 0) {
                //釋放鎖操作，是需要把state更新為0，所以arg必須是0
                throw new RuntimeException("arg not is 0");
            }
            //清空持有鎖執行緒
            setExclusiveOwnerThread(null);
            //設定state狀態為0，此處不用cas，因為只有獲取鎖成功的執行緒才會執行該函式，不需要考慮執行緒安全問題
            setState(arg);
            return true;
        }

        /**
         * 提供創建條件變數入口
         */
        public ConditionObject createConditionObject() {
            return new ConditionObject();
        }

    }

    private final Sync sync = new Sync();

    /**
     * 獲取鎖
     */
    @Override
    public void lock() {
        //Aqs獨占式-獲取資源模板函式
        sync.acquire(1);
    }
        
    /**
     * 獲取鎖-回應中斷
     */
    @Override
    public void lockInterruptibly() throws InterruptedException {
        //Aqs獨占式-獲取資源模板函式(回應執行緒中斷)
        sync.acquireInterruptibly(1);
    }

    /**
     * 獲取鎖是否成功-不阻塞
     */
    @Override
    public boolean tryLock() {
        //子類實作
        return sync.tryAcquire(1);
    }
    
    /**
     * 獲取鎖-超時機制
     */
    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        //Aqs獨占式-獲取資源模板函式(超時機制)
        return sync.tryAcquireNanos(1,unit.toNanos(time));
    }
    
    /**
     * 釋放鎖
     */
    @Override
    public void unlock() {
        //Aqs獨占式-釋放資源模板函式
        sync.release(0);
    }
    
    /**
     * 創建條件變數
     */
    @Override
    public Condition newCondition() {
        return sync.createConditionObject();
    }
}

NonReentrantLock定義了一個內部類Sync，Sync用來實作具體的鎖操作，它繼承了A Q S，因為使用的是獨占式模板，所以重寫tryAcquire與tryRelease函式，另外提供了一個創建條件變數的入口，下面使用自定義的獨占鎖來同步兩個執行緒對j++，

    private static int j = 0;

    public static void main(String[] agrs) throws InterruptedException {
        NonReentrantLock  nonReentrantLock = new NonReentrantLock();

        Runnable runnable = () -> {
            //獲取鎖
            nonReentrantLock.lock();
            for (int i = 0; i < 100000; i++) {
                j++;
            }
            //釋放鎖
            nonReentrantLock.unlock();
        };

        Thread thread = new Thread(runnable);
        Thread threadTwo = new Thread(runnable);

        thread.start();
        threadTwo.start();

        thread.join();
        threadTwo.join();

        System.out.println(j);
    }
    


無論執行多少次輸出內容都是：
200000

AQS簡化流程圖

嘮叨嘮叨

十分抱歉，這次拖更了，因為AbstractQueuedSynchronizer內容有點多，所以花了較長的時間，希望各位大佬理解一下，手下留情~

另外本文只是阿星的理解，如果哪里有問題，也歡迎各位大佬糾正，下一篇開始寫ReentrantLock，因為有AbstractQueuedSynchronizer鋪墊，ReentrantLock理解起來會非常簡單，所以大家一定要看懂AbstractQueuedSynchronizer，最后如果覺得阿星的文章對您有幫助，也請一鍵三連支持阿星（點贊、再看、轉發）

歷史好文推薦

• 寫給小白看的LockSupport
• 13張圖，深入理解Synchronized
• 由淺入深CAS，小白也能與BAT面試官對線
• 小白也能看懂的Java記憶體模型
• 保姆級教學，22張圖揭開ThreadLocal
• 行程、執行緒與協程傻傻分不清？一文帶你吃透！
• 什么是執行緒安全？一文帶你深入理解

關于我

這里是阿星，一個熱愛技術的Java程式猿，公眾號 「程式猿阿星」 里將會定期分享作業系統、計算機網路、Java、分布式、資料庫等精品原創文章，2021，與您在 Be Better 的路上共同成長！，

非常感謝各位小哥哥小姐姐們能看到這里，原創不易，文章有幫助可以關注、點個贊、分享與評論，都是支持（莫要白嫖）！

愿你我都能奔赴在各自想去的路上，我們下篇文章見