圖解AQS的設計與實現，手摸手帶你實現一把互斥鎖！

AQS是併發編程中非常重要的概念，它是juc包下的許多併發工具類，如CountdownLatch，CyclicBarrier，Semaphore 和鎖, 如ReentrantLock， ReaderWriterLock的實現基礎，提供了一個基於int狀態碼和隊列來實現的併發框架。本文將對AQS框架的 ...

AQS是併發編程中非常重要的概念，它是juc包下的許多併發工具類，如CountdownLatch，CyclicBarrier，Semaphore 和鎖, 如ReentrantLock， ReaderWriterLock的實現基礎，提供了一個基於int狀態碼和隊列來實現的併發框架。本文將對AQS框架的幾個重要組成進行簡要介紹，讀完本文你將get到以下幾個點：

AQS進行併發控制的機制是什麼
共用模式和獨占模式獲取和釋放同步狀態的詳細過程
基於AQS框架實現一個簡易的互斥鎖

一，AQS基本概念

AQS（AbstractQueuedSynchronizer）是用來構建鎖或者其他同步組件的基礎框架，它使用了一個int成員變數來表示狀態，通過內置的FIFO（first in，first out）隊列來完成資源獲取線程的排隊工作。

1.1 同步狀態

AQS中維持一個全局的int狀態碼（state），線程通過修改（加/減指定的數量）碼是否成功來決定當前線程是否成功獲取到同步狀態。

1.1 獨占or共用模式

AQS支持兩種獲取同步狀態的模式既獨占式和共用式。顧名思義，獨占式模式同一時刻只允許一個線程獲取同步狀態，而共用模式則允許多個線程同時獲取。

1.2 同步隊列

同步隊列（一個FIFO雙向隊列）是AQS的核心，用來完成同步狀態的管理，當線程獲取同步狀態失敗時，AQS會將當前線程以及等待狀態等信息構造成一個節點並加入到同步隊列，同時會阻塞當前線程。

二，獨占模式獲取與釋放狀態

獨占模式既同一時間只能由一個線程持有同步狀態。當多個線程競爭時(acquire)，獲取到同步狀態的線程會將當前線程賦值給Thread exclusiveOwnerThread屬性（AQS父類中）來標記當前狀態被線程獨占。其他線程將被構造成Node加入到同步隊列中。當線程l

2.1 獲取同步狀態

/**
 * 獲取同步狀態
 */
public final void acquire(int arg) {
    /**
     * 1. tryAcquire    嘗試獲取同步狀態; 
     * 2.1 addWaiter     如果嘗試獲取到同步狀態失敗，則加入到同步隊列中; 
     * 2.2 acquireQueued 在隊列中嘗試獲取同步狀態.
     */
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

多線程併發獲取（修改）同步狀態, 修改同步狀態成功的線程標記為擁有同步狀態

/**
 * 嘗試獲取同步狀態【子類中實現】，因為aqs基於模板模式，僅提供基於狀態和同步隊列的實 
 * 現框架，具體的實現邏輯由子類決定
 */
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // a. 嘗試修改狀態值操作執行成功
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            // b. 修改狀態值成功，記錄當前持有同步狀態的線程信息
            setExclusiveOwnerThread(current);
            return true;
        }
        // 如果當前線程已經持有同步狀態，繼續修改同步狀態【重入鎖實現原理，不理解可以先忽略】
    } else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

獲取失敗的線程，加入到同步隊列的隊尾；加入到隊列中後，如果當前節點的前驅節點為頭節點再次嘗試獲取同步狀態（下文代碼：p == head && tryAcquire(arg)）。

/**
 * 沒有獲取到同步狀態的線程加入到隊尾部
 */
private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // 嘗試用最快的方式入隊，如果入隊失敗，再走完整的入隊方法
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        // 將當前線程設置到隊尾
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 正常的入隊方法
    enq(node);
    return node;
}

/**
 * 同步隊列中節點，嘗試獲取同步狀態
 */
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);// 註意： 此處重點， 當前節點設置為頭節點，相當於頭節點出隊
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // 獲取失敗後是否進入wait
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

如果頭節點的下一個節點嘗試獲取同步狀態失敗後，會進入等待狀態；其他節點則繼續自旋。

// 偽代碼
final boolean acquireQueued(final Node node, int arg) {
    for (;;) {
        // -------獲取同步狀態失敗-------
      
        // 獲取失敗後是否進入wait
        if (shouldParkAfterFailedAcquire(p, node) &&
            parkAndCheckInterrupt())
            interrupted = true;
    }
 
}
/**
 * 當獲取同步狀態失敗後是否進入park狀態
 */
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    // 前驅節點為喚醒狀態，返回true【後面代碼暫時可以忽略】
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

獨占模式獲取同步狀態總結

2.2 釋放同步狀態

當線程執行完相應邏輯後，需要釋放同步狀態，使後繼節點有機會同步狀態（讓出資源，讓排隊的線程使用）。這時就需要調用release(int arg)方法。調用該方法後，會喚醒後繼節點。

釋放同步狀態，喚醒後繼節點

/**
 * 釋放同步狀態
 */
public final boolean release(int arg) {
    // 1. 嘗試釋放同步狀態
    if (tryRelease(arg)) {
        Node h = head;
        // 釋放成功後，執行unpark，既喚醒操作（暫時可忽略waitStatus，涉及到條件隊列）
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}     
/**
 * 嘗試釋放同步狀態，既將同步狀態減去指定的值
 * 如果state = 0，表示當前線程  獲取次數 = 釋放次數，既釋放成功，此時將持有同步狀態線程標誌為null
 */
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    // 狀態碼=0，表示釋放成功了
    if (c == 0) {
        free = true;
        // 獨占標誌設置為null
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}
/**
  * 喚醒後繼節點操作
  */
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 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);
}

後繼節點獲取同步狀態成功，頭節點出隊。需要註意的事，出隊操作是間接的，有節點獲取到同步狀態時，會將當前節點設置為head，而原本的head設置為null。

/**
 * 同步隊列中節點，嘗試獲取同步狀態（偽代碼）
 * 獲取成功後，當前節點設置為頭節點，頭節點設置為null，既頭節點出隊
 */
final boolean acquireQueued(final Node node, int arg) {
    try {
        // 自旋(死迴圈)
        for (;;) {
            if (p == head && tryAcquire(arg)) {
                // a. 操作：當前節點設置為頭節點，當前節點的前驅節點設置為null
                setHead(node);
                // b. 原始的head的next設置為null，此時原始的head已經被移出隊列
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
        }
    }
}
/**
 * a.當前節點設置為頭節點，當前節點的前驅節點設置為null
 */
private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

2.3 其他競爭情況

當同步隊列中頭節點喚醒後繼節點時，此時可能有其他線程嘗試獲取同步狀態。
假設獲取成功，將會被設置為頭節點。
頭節點後續節點獲取同步狀態失敗。

三，共用模式獲取與釋放狀態

共用模式和獨占模式最主要的區別是在支持同一時刻有多個線程同時獲取同步狀態。為了避免帶來額外的負擔，在上文中提到的同步隊列中都是用獨占模式進行講述，其實同步隊列中的節點應該是獨占和共用節點並存的。

接下來將針對共用模式狀態下獲取與釋放狀態的過程，圖文並茂得進行分析。

3.1 獲取同步狀態

首先至少要調用一次tryAcquireShared(arg)方法，如果返回值大於等於0表示獲取成功。
當獲取鎖失敗時，則創建一個共用類型的節點併進入一個同步隊列，然後進入隊列中進入自旋狀態（阻塞，喚醒兩種狀態來回切換，直到獲取到同步狀態為止）
當隊列中的等待線程被喚醒以後就重新嘗試獲取鎖資源，如果成功則喚醒後面還在等待的共用節點並把該喚醒事件傳遞下去，即會依次喚醒在該節點後面的所有共用節點，否則繼續掛起等待。

當一個同享節點獲取到同步狀態，並喚醒後面等待的共用狀態的結果如下圖所示：

/**
  * 共用模式獲取同步狀態；
  * 1. 首先至少要調用一次tryAcquireShared(arg)方法，如果返回值大於等於0表示獲取成功，直接返回結果即可
  * 2. 否則，將會加入到同步隊列中，反覆阻塞與喚醒，直到獲取同步狀態成功為止； 獲取成功後會喚醒後面還在等待的共用節點並把該喚醒事件傳遞下去，即會依次喚醒在該節點後面的所有共用節點
  */
public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

/**
  * 2. 自旋模式獲取同步狀態
  */
private void doAcquireShared(int arg) {
    // 2.1 第一次獲取失敗後，會將此線程加入到同步隊列中
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            // 如果前驅節點是頭節點，嘗試獲取同步狀態
            final Node p = node.predecessor();
            if (p == head) {
                // r > 0表示獲取同步狀態成功，並且還有共用類型節點在同步隊列中
                // r == 0 表示獲取同步狀態成功，同步隊列中沒有其他共用模式節點
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    // ！！！！ 獲取同步狀態成功後，將當前node設置為頭節點，並向後傳播，喚醒共用模式等待的節點
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

/**
 * 設置新的頭結點，並設置後面需要喚醒的節點
 */ 
private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);
    // propagate > 0 表明後面需要喚醒的共用模式節點
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
         // 如果當前節點的後繼節點是共用類型或者沒有後繼節點，則進行喚醒
         // 這裡可以理解為除非明確指明不需要喚醒（後繼等待節點是獨占類型），否則都要喚醒
        if (s == null || s.isShared())
            doReleaseShared();
    }
}
/**
 * 喚醒所有共用模式節點
 */
private void doReleaseShared() {
        for (;;) {
            // 喚醒操作由頭結點開始，註意這裡的頭節點已經是上面新設置的頭結點了
            // 其實就是喚醒上面新獲取到共用鎖的節點的後繼節點
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                // 表示後繼節點需要被喚醒
                if (ws == Node.SIGNAL) {
                    //這裡需要控制併發，因為入口有setHeadAndPropagate跟release兩個，避免兩次unpark
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;      
                    //執行喚醒操作      
                    unparkSuccessor(h);
                }
                //如果後繼節點暫時不需要喚醒，則把當前節點狀態設置為PROPAGATE確保以後可以傳遞下去
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                
            }
            // 如果頭結點沒有發生變化，表示設置完成，退出迴圈
            // 如果頭結點發生變化，比如說其他線程獲取到了鎖，為了使自己的喚醒動作可以傳遞，必須進行重試
            if (h == head)                   
                break;
        }
    }

最後，獲取到同步狀態的線程執行完畢，同步隊列中只有一個獨占節點：

3.2 釋放同步狀態

釋放同步狀態後，同步隊列的變化過程和共用節點獲取到同步狀態後的變化過程一致，此處不再進行贅述。

/**
 * 釋放同步狀態，如果釋放成功，喚醒後面等待的節點
 *
 */
public final boolean releaseShared(int arg) {
    // 1. 嘗試釋放同步狀態
    if (tryReleaseShared(arg)) {
         // 2. 釋放成功後，喚醒後續等待共用節點
         doReleaseShared();
        return true;
    }
    return false;
}

四，基於AQS實現互斥鎖

讀到此處，大部分人應該還比較懵逼，似懂非懂。接下來筆者將通過AQS實現一個互斥鎖帶你打開AQS的正確打開姿勢。

多線程環境count += 1可能會存在問題，詳情可以看在併發編程bug的來源中介紹的三大原因。正如大多數人都知道的，我們通常可以使用synchronized關鍵字進行同步，接下來我們就基於AQS自定義一個互斥鎖來完成相同的功能。

4.1 代碼實現

/**
 * 自定義互斥鎖
 *
 * @author cruder
 * @time 2019/11/29 23:23
 */
public class MutexLock {

    private static final Sync STATE_HOLDER = new Sync();

    /**
     * 通過Sync內部類來持有同步狀態， 當狀態為1表示鎖被持有，0表示鎖處於空閑狀態
     */
    private static class Sync extends AbstractQueuedSynchronizer {

        /**
         * 是否被獨占， 有兩種表示方式
         *  1. 可以根據狀態，state=1表示鎖被占用，0表示空閑
         *  2. 可以根據當前獨占鎖的線程來判斷，即getExclusiveOwnerThread()!=null 表示被獨占
         */
        @Override
        protected boolean isHeldExclusively() {
            return getExclusiveOwnerThread() != null;
        }

        /**
         * 嘗試獲取鎖，將狀態從0修改為1，操作成功則將當前線程設置為當前獨占鎖的線程
         */
        @Override
        protected boolean tryAcquire(int arg) {
            if (compareAndSetState(0, 1)) {
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }

        /**
         * 釋放鎖，將狀態修改為0
         */
        @Override
        protected boolean tryRelease(int arg) {
            if (getState() == 0) {
                throw new UnsupportedOperationException();
            }
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }

    }

    /**
     * 下麵的實現Lock介面需要重寫的方法，基本是就是調用內部內Sync的方法
     */
    public void lock() {
        STATE_HOLDER.acquire(1);
    }

    public void unlock() {
        STATE_HOLDER.release(1);
    }
}

4.2 鎖的測試

我們定義一個計數器類，裡面定義了2個不同的計數方法，其中一個使用互斥鎖進行同步。開啟10個線程併發執行，每個線程計數10000次，然後對比統計結果與預期的100，000是否相符。

package myLock;

import java.util.concurrent.*;

/**
 * 自定義鎖測試
 *
 * @author liqiang
 * @time 2019/11/29 12:39
 */
public class MyLockTest {

    public static void main(String[] args) throws InterruptedException {
        int threadNum = 10;
        int countPerThread = 10000;
        // 線程池創建的正確姿勢
        ThreadPoolExecutor threadPool = new ThreadPoolExecutor(threadNum, threadNum, 1000, TimeUnit.SECONDS, new ArrayBlockingQueue<>(10), new ThreadPoolExecutor.AbortPolicy());
        CountDownLatch countDownLatch = new CountDownLatch(threadNum);
        Counter counter = new Counter();
        Counter counterUnsafe = new Counter();

        for (int i = 0; i < threadNum; i++) {
            threadPool.submit(() -> {
                for (int j = 0; j < countPerThread; j++) {
                    counter.getAndIncrement();
                    counterUnsafe.getAndIncrementUnSfae();
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        System.out.printf("%s 個線程，每個線程累加了 %s 次，執行結果：safeCounter = %s, unsafeCounter = %s ", threadNum, countPerThread, counter.get(), counterUnsafe.get());
        threadPool.shutdownNow();
    }

}

class Counter {
    private MutexLock mutexLock;
    private volatile int count;

    Counter() {
        this.mutexLock = new MutexLock();
    }

    int get() {
        return count;
    }

    int getAndIncrement() {
        mutexLock.lock();
        count++;
        mutexLock.unlock();
        return count;
    }

    int getAndIncrementUnSfae() {
        count++;
        return count;
    }
}

1575039419566