前言

AQS（AbstractQueuedSynchronizer）是JAVA中眾多鎖以及并發(fā)工具的基礎(chǔ)，其底層采用樂觀鎖南用，大量使用了CAS操作汰寓， 并且在沖突時，采用自旋方式重試节芥，以實現(xiàn)輕量級和高效地獲取鎖。

AQS雖然被定義為抽象類逆害，但事實上它并不包含任何抽象方法头镊。這是因為AQS是被設(shè)計來支持多種用途的，如果定義抽象方法魄幕，則子類在繼承時必須要覆寫所有的抽象方法相艇，這顯然是不合理的。所以AQS將一些需要子類覆寫的方法都設(shè)計成protect方法纯陨，將其默認實現(xiàn)為拋出UnsupportedOperationException異常坛芽。如果子類使用到這些方法留储，但是沒有覆寫，則會拋出異常靡馁；如果子類沒有使用到這些方法欲鹏，則不需要做任何操作。

AQS中實現(xiàn)了鎖的獲取框架臭墨，鎖的實際獲取邏輯交由子類去實現(xiàn)，就鎖的獲取操作而言膘盖，子類必須重寫 tryAcquire方法胧弛。

本篇我們將以ReentrantLock的公平鎖為例來詳細看看使用AQS獲取獨占鎖的流程。

Java并發(fā)工具類的三板斧

在開始看AQS源碼之前侠畔，我們先來了解以下java并發(fā)工具的設(shè)計套路结缚，我把它總結(jié)成三板斧：

狀態(tài)，隊列软棺，CAS

每當我們學(xué)習(xí)一個java并發(fā)編程工具的時候红竭，我們首先要抓住這三點。

• 狀態(tài)：一般是一個state屬性喘落，它基本是整個工具的核心茵宪，通常整個工具都是在設(shè)置和修改狀態(tài)，很多方法的操作都依賴于當前狀態(tài)是什么瘦棋。由于狀態(tài)是全局共享的稀火，一般會被設(shè)置成volatile類型，以保證其修改的可見性赌朋；
• 隊列：隊列通常是一個等待的集合凰狞，大多數(shù)以鏈表的形式實現(xiàn)。隊列采用的是悲觀鎖的思想沛慢，表示當前所等待的資源赡若，狀態(tài)或者條件短時間內(nèi)可能無法滿足。因此团甲，它會將當前線程包裝成某種類型的數(shù)據(jù)結(jié)構(gòu)逾冬，扔到一個等待隊列中，當一定條件滿足后伐庭，再從等待隊列中取出粉渠。
• CAS: CAS操作是最輕量的并發(fā)處理，通常我們對于狀態(tài)的修改都會用到CAS操作圾另，因為狀態(tài)可能被多個線程同時修改霸株，CAS操作保證了同一個時刻，只有一個線程能修改成功集乔，從而保證了線程安全去件，CAS操作基本是由Unsafe工具類的compareAndSwapXXX來實現(xiàn)的坡椒；CAS采用的是樂觀鎖的思想，因此常常伴隨著自旋尤溜，如果發(fā)現(xiàn)當前無法成功地執(zhí)行CAS倔叼，則不斷重試，直到成功為止宫莱，自旋的的表現(xiàn)形式通常是一個死循環(huán)for(;;)丈攒。

AQS核心實現(xiàn)

狀態(tài)

首先是找狀態(tài)。

在AQS中授霸，狀態(tài)是由state屬性來表示的巡验，不出所料，它是volatile類型的：

private volatile int state;

該屬性的值即表示了鎖的狀態(tài)碘耳，state為0表示鎖沒有被占用显设，state大于0表示當前已經(jīng)有線程持有該鎖，這里之所以說大于0而不說等于1是因為可能存在可重入的情況辛辨。你可以把state變量當做是當前持有該鎖的線程數(shù)量捕捂。

由于本篇我們分析的是獨占鎖，同一時刻斗搞，鎖只能被一個線程所持有指攒。通過state變量是否為0，我們可以分辨當前鎖是否被占用榜旦，但光知道鎖是不是被占用是不夠的幽七，我們并不知道占用鎖的線程是哪一個。在監(jiān)視器鎖中溅呢，我們用ObjectMonitor對象的_owner屬性記錄了當前擁有監(jiān)視器鎖的線程澡屡，而在AQS中，我們將通過exclusiveOwnerThread屬性：

private transient Thread exclusiveOwnerThread; //繼承自AbstractOwnableSynchronizer

exclusiveOwnerThread屬性的值即為當前持有鎖的線程咐旧，它就是我們所說的“鐵王座”驶鹉。

隊列

接著我們來看隊列，AQS中铣墨，隊列的實現(xiàn)是一個雙向鏈表室埋，被稱為sync queue，它表示所有等待鎖的線程的集合伊约，有點類似于我們前面介紹synchronized原理的時候說的wait set姚淆。

我們前面說過，在并發(fā)編程中使用隊列通常是將當前線程包裝成某種類型的數(shù)據(jù)結(jié)構(gòu)扔到等待隊列中屡律，我們先來看看隊列中的每一個節(jié)點是怎么個結(jié)構(gòu)：

static final class Node {
    /** Marker to indicate a node is waiting in shared mode */
    static final Node SHARED = new Node();
    /** Marker to indicate a node is waiting in exclusive mode */
    static final Node EXCLUSIVE = null;

    /** waitStatus value to indicate thread has cancelled */
    static final int CANCELLED =  1;
    /** waitStatus value to indicate successor's thread needs unparking */
    static final int SIGNAL    = -1;
    /** waitStatus value to indicate thread is waiting on condition */
    static final int CONDITION = -2;
    /**
     * waitStatus value to indicate the next acquireShared should
     * unconditionally propagate
     */
    static final int PROPAGATE = -3;

    volatile int waitStatus;

    volatile Node prev;

    volatile Node next;

    volatile Thread thread;

    Node nextWaiter;

    final boolean isShared() {
        return nextWaiter == SHARED;
    }

    final Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null)
            throw new NullPointerException();
        else
            return p;
    }

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

這個結(jié)構(gòu)看起來很復(fù)雜腌逢，其實屬性只有4類：

// 節(jié)點所代表的線程
volatile Thread thread;

// 雙向鏈表，每個節(jié)點需要保存自己的前驅(qū)節(jié)點和后繼節(jié)點的引用
volatile Node prev;
volatile Node next;

// 線程所處的等待鎖的狀態(tài)超埋，初始化時搏讶，該值為0
volatile int waitStatus;
static final int CANCELLED =  1;
static final int SIGNAL    = -1;
static final int CONDITION = -2;
static final int PROPAGATE = -3;

// 該屬性用于條件隊列或者共享鎖
Node nextWaiter;

注意佳鳖，在這個Node類中也有一個狀態(tài)變量waitStatus，它表示了當前Node所代表的線程的等待鎖的狀態(tài)媒惕，在獨占鎖模式下系吩，我們只需要關(guān)注CANCELLED SIGNAL兩種狀態(tài)即可。這里還有一個nextWaiter屬性妒蔚，它在獨占鎖模式下永遠為null穿挨，僅僅起到一個標記作用，沒有實際意義面睛。
說完隊列中的節(jié)點絮蒿，我們接著說回這個sync queue，AQS是怎么使用這個隊列的呢叁鉴，既然是雙向鏈表，操縱它自然只需要一個頭結(jié)點和一個尾節(jié)點：

// 頭結(jié)點佛寿，不代表任何線程幌墓，是一個啞結(jié)點
private transient volatile Node head;

// 尾節(jié)點，每一個請求鎖的線程會加到隊尾
private transient volatile Node tail;

到這里冀泻，我們就了解到了這個sync queue的全貌：

image.png

不過這里有一點我們提前說一下常侣，在AQS中的隊列是一個CLH隊列，它的head節(jié)點永遠是一個啞結(jié)點（dummy node), 它不代表任何線程（某些情況下可以看做是代表了當前持有鎖的線程）弹渔，因此head所指向的Node的thread屬性永遠是null胳施。只有從次頭節(jié)點往后的所有節(jié)點才代表了所有等待鎖的線程。也就是說肢专，在當前線程沒有搶到鎖被包裝成Node扔到隊列中時舞肆，即使隊列是空的，它也會排在第二個博杖，我們會在它的前面新建一個dummy節(jié)點(具體的代碼我們在后面分析源碼時再詳細講)椿胯。為了便于描述，下文中我們把除去head節(jié)點的隊列稱作是等待隊列剃根，在這個隊列中的節(jié)點才代表了所有等待鎖的線程：

image.png

在繼續(xù)往下之前我們再對著上圖總結(jié)一下Node節(jié)點各個參數(shù)的含義：

• thread：表示當前Node所代表的線程
• waitStatus：表示節(jié)點所處的等待狀態(tài)哩盲，共享鎖模式下只需關(guān)注三種狀態(tài)：SIGNAL CANCELLED 初始態(tài)(0)
• prev next：節(jié)點的前驅(qū)和后繼
• nextWaiter：進作為標記，值永遠為null狈醉，表示當前處于獨占鎖模式

CAS操作

前面我們提到過廉油，CAS操作大對數(shù)是用來改變狀態(tài)的，在AQS中也不例外苗傅。我們一般在靜態(tài)代碼塊中初始化需要CAS操作的屬性的偏移量：

private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    static {
        try {
            stateOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                (Node.class.getDeclaredField("next"));

        } catch (Exception ex) { throw new Error(ex); }
    }

從這個靜態(tài)代碼塊中我們也可以看出抒线，CAS操作主要針對5個屬性，包括AQS的3個屬性state,head和tail, 以及Node對象的兩個屬性waitStatus,next金吗。說明這5個屬性基本是會被多個線程同時訪問的十兢。

定義完屬性的偏移量之后趣竣，接下來就是CAS操作本身了：

protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
private final boolean compareAndSetHead(Node update) {
    return unsafe.compareAndSwapObject(this, headOffset, null, update);
}
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}
private static final boolean compareAndSetWaitStatus(Node node, int expect,int update) {
    return unsafe.compareAndSwapInt(node, waitStatusOffset, expect, update);
}
private static final boolean compareAndSetNext(Node node, Node expect, Node update) {
    return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
}

如前面所說，最終CAS操作調(diào)用的還是Unsafe類的compareAndSwapXXX方法旱物。

最后就是自旋了遥缕，這一點就沒有什么好說的了，我們在后面源碼分析的時候再詳細講宵呛。

AQS核心屬性

前面我們以java并發(fā)編程工具類的“三板斧”為切入點分析了AQS的狀態(tài)单匣，隊列和CAS操作，對這個工具類有了初步的認識宝穗。接下來户秤，我們就要開始進入源碼分析了。在進入正式的分析之前逮矛，我們先來總結(jié)下AQS核心屬性：

（1）鎖相關(guān)的屬性有兩個：

private volatile int state; //鎖的狀態(tài)
private transient Thread exclusiveOwnerThread; // 當前持有鎖的線程鸡号，注意這個屬性是從AbstractOwnableSynchronizer繼承而來

（2）sync queue相關(guān)的屬性有兩個：

private transient volatile Node head; // 隊頭，為dummy node
private transient volatile Node tail; // 隊尾须鼎，新入隊的節(jié)點

（3）隊列中的Node中需要關(guān)注的屬性有三組：

// 節(jié)點所代表的線程
volatile Thread thread;

// 雙向鏈表鲸伴，每個節(jié)點需要保存自己的前驅(qū)節(jié)點和后繼節(jié)點的引用
volatile Node prev;
volatile Node next;

// 線程所處的等待鎖的狀態(tài)，初始化時晋控，該值為0
volatile int waitStatus;
static final int CANCELLED =  1;
static final int SIGNAL    = -1;

拎了這些屬性后汞窗，我們下面分析源碼就容易很多了。

FairSync in ReentrantLock

前面已經(jīng)提到, AQS大多數(shù)情況下都是通過繼承來使用的, 子類通過覆寫 tryAcquire來實現(xiàn)自己的獲取鎖的邏輯赡译，我們這里以ReentrantLock為例來說明鎖的獲取流程仲吏。

值得注意的是, ReentrantLock有 公平鎖 和 非公平鎖 兩種實現(xiàn), 默認實現(xiàn)為非公平鎖, 這體現(xiàn)在它的構(gòu)造函數(shù)中:

public class ReentrantLock implements Lock, java.io.Serializable {
    /** Synchronizer providing all implementation mechanics */
    private final Sync sync;
    
    /**
     * Base of synchronization control for this lock. Subclassed
     * into fair and nonfair versions below. Uses AQS state to
     * represent the number of holds on the lock.
     */
    abstract static class Sync extends AbstractQueuedSynchronizer {
        ...
    }
    
    /**
     * Sync object for non-fair locks
     */
    static final class NonfairSync extends Sync{
        ...
    }
    
    /**
     * Sync object for fair locks
     */
    static final class FairSync extends Sync {
        ...
    }
    
    /**
     * Creates an instance of {@code ReentrantLock}.
     * This is equivalent to using {@code ReentrantLock(false)}.
     */
    public ReentrantLock() {
        sync = new NonfairSync();
    }

    /**
     * Creates an instance of {@code ReentrantLock} with the
     * given fairness policy.
     *
     * @param fair {@code true} if this lock should use a fair ordering policy
     */
    public ReentrantLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
    }
    
    // 獲取鎖
    public void lock() {
        sync.lock();
    }
    
    ...
}

可以看出, FairSync 繼承自 Sync, 而Sync繼承自 AQS, ReentrantLock獲取鎖的邏輯是直接調(diào)用了FairSync 或者 NonfairSync的邏輯.

好了, ReentrantLock 就簡單說到這里, 以后我們有機會再詳細講, 這里直接以 FairLock 為例, 來逐行分析鎖的獲取:

static final class FairSync extends Sync {
    private static final long serialVersionUID = -3000897897090466540L;
    //獲取鎖
    final void lock() {
        acquire(1);
    }
    ...
}

lock 方法調(diào)用的 acquire方法來自父類AQS。

這里首先給出完整的獲取鎖的流程圖, 再逐行分析代碼, 因為看源碼的時候, 代碼會在函數(shù)或者循環(huán)中來回跳轉(zhuǎn)蝌焚，讀者可以對照以下流程圖, 就不容易被繞暈了.

image.png

acquire

acquire 定義在AQS類中裹唆，描述了獲取鎖的流程

public final void acquire(int arg) {
    if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

可以看出, 該方法中涉及了四個方法的調(diào)用:

（1）tryAcquire(arg)

該方法由繼承AQS的子類實現(xiàn), 為獲取鎖的具體邏輯。

（2）addWaiter(Node mode)

該方法由AQS實現(xiàn), 負責(zé)在獲取鎖失敗后調(diào)用, 將當前請求鎖的線程包裝成Node扔到sync queue中去综看，并返回這個Node品腹。

（3）acquireQueued(final Node node, int arg)

該方法由AQS實現(xiàn),這個方法比較復(fù)雜, 主要對上面剛加入隊列的Node不斷嘗試以下兩種操作之一:

• 在前驅(qū)節(jié)點就是head節(jié)點的時候,繼續(xù)嘗試獲取鎖
• 將當前線程掛起,使CPU不再調(diào)度它

（4）selfInterrupt

該方法由AQS實現(xiàn), 用于中斷當前線程。由于在整個搶鎖過程中红碑，我們都是不響應(yīng)中斷的舞吭。那如果在搶鎖的過程中發(fā)生了中斷怎么辦呢，總不能假裝沒看見呀析珊。AQS的做法簡單的記錄有沒有有發(fā)生過中斷羡鸥，如果返回的時候發(fā)現(xiàn)曾經(jīng)發(fā)生過中斷，則在退出acquire方法之前忠寻，就調(diào)用selfInterrupt自我中斷一下惧浴，就好像將這個發(fā)生在搶鎖過程中的中斷“推遲”到搶鎖結(jié)束以后再發(fā)生一樣。

從上面的簡單介紹中可以看出奕剃，除了獲取鎖的邏輯 tryAcquire(arg)由子類實現(xiàn)外, 其余方法均由AQS實現(xiàn)衷旅。

接下來我們重點來看 FairSync 所實現(xiàn)的獲取鎖的邏輯:

tryAcquire

tryAcquire 獲取鎖的邏輯其實很簡單——判斷當前鎖有沒有被占用：

1.如果鎖沒有被占用, 嘗試以公平的方式獲取鎖
2.如果鎖已經(jīng)被占用, 檢查是不是鎖重入

獲取鎖成功返回true, 失敗則返回false

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    // 首先獲取當前鎖的狀態(tài)
    int c = getState(); 
    
    // c=0 說明當前鎖是avaiable的, 沒有被任何線程占用, 可以嘗試獲取
    // 因為是實現(xiàn)公平鎖, 所以在搶占之前首先看看隊列中有沒有排在自己前面的Node
    // 如果沒有人在排隊, 則通過CAS方式獲取鎖, 就可以直接退出了
    if (c == 0) {
        if (!hasQueuedPredecessors() 
        /* 為了閱讀方便, hasQueuedPredecessors源碼就直接貼在這里了, 這個方法的本質(zhì)實際上是檢測自己是不是head節(jié)點的后繼節(jié)點捐腿，即處在阻塞隊列第一位的節(jié)點
            public final boolean hasQueuedPredecessors() {
                Node t = tail; 
                Node h = head;
                Node s;
                return h != t && ((s = h.next) == null || s.thread != Thread.currentThread());
            }
        */
        && compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current); // 將當前線程設(shè)置為占用鎖的線程
            return true;
        }
    }
    
    // 如果 c>0 說明鎖已經(jīng)被占用了
    // 對于可重入鎖, 這個時候檢查占用鎖的線程是不是就是當前線程,是的話,說明已經(jīng)拿到了鎖, 直接重入就行
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        /* setState方法如下：
        protected final void setState(int newState) {
            state = newState;
        }
        */
        return true;
    }
    
    // 到這里說明有人占用了鎖, 并且占用鎖的不是當前線程, 則獲取鎖失敗
    return false;
}

從這里可以看出，獲取鎖其實主要就是干一件事：

將state的狀態(tài)通過CAS操作由0改寫成1

由于是CAS操作柿顶，必然是只有一個線程能執(zhí)行成功茄袖。則執(zhí)行成功的線程即獲取了鎖，在這之后嘁锯，才有權(quán)利將exclusiveOwnerThread的值設(shè)成自己宪祥，從而“坐上鐵王座”。
另外對于可重入鎖家乘，如果當前線程已經(jīng)是獲取了鎖的線程了蝗羊，它還要注意增加鎖的重入次數(shù)。

值得一提的是仁锯，這里修改state狀態(tài)的操作耀找，一個用了CAS方法compareAndSetState，一個用了普通的setState方法业崖。這是因為用CAS操作時涯呻，當前線程還沒有獲得鎖，所以可能存在多線程同時在競爭鎖的情況腻要；而調(diào)用setState方法時，是在當前線程已經(jīng)是持有鎖的情況下涝登，因此對state的修改是安全的雄家，只需要普通的方法就可以了。

因此胀滚，在多線程條件下看源碼時趟济，我們一定要時刻在心中問自己：

這段代碼是否是線程安全的？同一時刻是否可能有多個線程在執(zhí)行這行代碼?

addWaiter

如果執(zhí)行到此方法, 說明前面嘗試獲取鎖的tryAcquire已經(jīng)失敗了, 既然獲取鎖已經(jīng)失敗了, 就要將當前線程包裝成Node咽笼，加到等待鎖的隊列中去, 因為是FIFO隊列, 所以自然是直接加在隊尾顷编。
方法調(diào)用為：

addWaiter(Node.EXCLUSIVE)

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode); //將當前線程包裝成Node
    // 這里我們用注釋的形式把Node的構(gòu)造函數(shù)貼出來
    // 因為傳入的mode值為Node.EXCLUSIVE，所以節(jié)點的nextWaiter屬性被設(shè)為null
    /*
        static final Node EXCLUSIVE = null;
        
        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }
    */
    Node pred = tail;
    // 如果隊列不為空, 則用CAS方式將當前節(jié)點設(shè)為尾節(jié)點
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    
    // 代碼會執(zhí)行到這里, 只有兩種情況:
    //    1. 隊列為空
    //    2. CAS失敗
    // 注意, 這里是并發(fā)條件下, 所以什么都有可能發(fā)生, 尤其注意CAS失敗后也會來到這里
    enq(node); //將節(jié)點插入隊列
    return node;
}

可見剑刑，每一個處于獨占鎖模式下的節(jié)點媳纬，它的nextWaiter一定是null。
在這個方法中施掏，我們首先會嘗試直接入隊钮惠，但是因為目前是在并發(fā)條件下，所以有可能同一時刻七芭，有多個線程都在嘗試入隊素挽，導(dǎo)致compareAndSetTail(pred, node)操作失敗——因為有可能其他線程已經(jīng)成為了新的尾節(jié)點，導(dǎo)致尾節(jié)點不再是我們之前看到的那個pred了狸驳。

如果入隊失敗了预明，接下來我們就需要調(diào)用enq(node)方法缩赛，在該方法中我們將通過自旋+CAS的方式，確保當前節(jié)點入隊撰糠。

enq

能執(zhí)行到這個方法酥馍，說明當前線程獲取鎖已經(jīng)失敗了，我們已經(jīng)把它包裝成一個Node,準備把它扔到等待隊列中去窗慎，但是在這一步又失敗了物喷。這個失敗的原因可能是以下兩種之一：

1.等待隊列現(xiàn)在是空的，沒有線程在等待遮斥。
2.其他線程在當前線程入隊的過程中率先完成了入隊峦失，導(dǎo)致尾節(jié)點的值已經(jīng)改變了，CAS操作失敗术吗。

在該方法中, 我們使用了死循環(huán), 即以自旋方式將節(jié)點插入隊列尉辑，如果失敗則不停的嘗試, 直到成功為止, 另外, 該方法也負責(zé)在隊列為空時, 初始化隊列，這也說明较屿，隊列是延時初始化的(lazily initialized)：

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        // 如果是空隊列, 首先進行初始化
        // 這里也可以看出, 隊列不是在構(gòu)造的時候初始化的, 而是延遲到需要用的時候再初始化, 以提升性能
        if (t == null) { 
            // 注意隧魄，初始化時使用new Node()方法新建了一個dummy節(jié)點
            if (compareAndSetHead(new Node()))
                tail = head; // 這里僅僅是將尾節(jié)點指向dummy節(jié)點，并沒有返回
        } else {
        // 到這里說明隊列已經(jīng)不是空的了, 這個時候再繼續(xù)嘗試將節(jié)點加到隊尾
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

這里尤其要注意的是隘蝎，當隊列為空時购啄，我們初始化隊列并沒有使用當前傳進來的節(jié)點，而是：
新建了一個空節(jié)點Ｖ雒础Ｊê！
新建了一個空節(jié)點Ｂ瘛＜钙！
新建了一個空節(jié)點１馈Ｓ承病！

在新建完空的頭節(jié)點之后，我們并沒有立即返回，而是將尾節(jié)點指向當前的頭節(jié)點厕氨，然后進入下一輪循環(huán)抛蚁。
在下一輪循環(huán)中，尾節(jié)點已經(jīng)不為null了，此時再將我們包裝了當前線程的Node加到這個空節(jié)點后面。

這就意味著，在這個等待隊列中娱据，頭結(jié)點是一個“啞節(jié)點”，它不代表任何等待的線程。
head節(jié)點不代表任何線程中剩，它就是一個空節(jié)點＜纱！结啼！
head節(jié)點不代表任何線程掠剑，它就是一個空節(jié)點！＝祭ⅰ朴译！
head節(jié)點不代表任何線程，它就是一個空節(jié)點Ｊ籼Ｃ呤佟！

尾分叉

在繼續(xù)往下之前焦蘑，我們先分析enq方法中一個比較有趣的現(xiàn)象盯拱，我把它叫做尾分叉。我們著重看將當前節(jié)點設(shè)置成尾節(jié)點的操作：

} else {
// 到這里說明隊列已經(jīng)不是空的了, 這個時候再繼續(xù)嘗試將節(jié)點加到隊尾
    node.prev = t;
    if (compareAndSetTail(t, node)) {
        t.next = node;
        return t;
    }
}

與將大象放到冰箱里需要三步一樣例嘱，將一個節(jié)點node添加到sync queue的末尾也需要三步：

1.設(shè)置node的前驅(qū)節(jié)點為當前的尾節(jié)點：node.prev = t
2.修改tail屬性狡逢，使它指向當前節(jié)點
3.修改原來的尾節(jié)點，使它的next指向當前節(jié)點

image.png

但是需要注意的拼卵，這里的三步并不是一個原子操作奢浑，第一步很容易成功；而第二步由于是一個CAS操作腋腮，在并發(fā)條件下有可能失敗殷费，第三步只有在第二步成功的條件下才執(zhí)行。這里的CAS保證了同一時刻只有一個節(jié)點能成為尾節(jié)點低葫，其他節(jié)點將失敗，失敗后將回到for循環(huán)中繼續(xù)重試仍律。

所以嘿悬，當有大量的線程在同時入隊的時候，同一時刻水泉，只有一個線程能完整地完成這三步善涨，而其他線程只能完成第一步，于是就出現(xiàn)了尾分叉：

image.png

注意草则，這里第三步是在第二步執(zhí)行成功后才執(zhí)行的钢拧，這就意味著，有可能即使我們已經(jīng)完成了第二步炕横，將新的節(jié)點設(shè)置成了尾節(jié)點源内，此時原來舊的尾節(jié)點的next值可能還是null(因為還沒有來的及執(zhí)行第三步)，所以如果此時有線程恰巧從頭節(jié)點開始向后遍歷整個鏈表份殿，則它是遍歷不到新加進來的尾節(jié)點的膜钓，但是這顯然是不合理的嗽交，因為現(xiàn)在的tail已經(jīng)指向了新的尾節(jié)點。
另一方面颂斜，當我們完成了第二步之后夫壁，第一步一定是完成了的，所以如果我們從尾節(jié)點開始向前遍歷沃疮，已經(jīng)可以遍歷到所有的節(jié)點盒让。這也就是為什么我們在AQS相關(guān)的源碼中，有時候常常會出現(xiàn)從尾節(jié)點開始逆向遍歷鏈表——因為一個節(jié)點要能入隊司蔬，則它的prev屬性一定是有值的邑茄，但是它的next屬性可能暫時還沒有值。

至于那些“分叉”的入隊失敗的其他節(jié)點葱她，在下一輪的循環(huán)中撩扒，它們的prev屬性會重新指向新的尾節(jié)點，繼續(xù)嘗試新的CAS操作吨些，最終搓谆，所有節(jié)點都會通過自旋不斷的嘗試入隊，直到成功為止豪墅。

addWaiter總結(jié)

至此泉手，我們就完成了addWaiter(Node.EXCLUSIVE)方法的完整的分析，該方法并不涉及到任何關(guān)于鎖的操作偶器，它就是解決了并發(fā)條件下的節(jié)點入隊問題斩萌。具體來說就是該方法保證了將當前線程包裝成Node節(jié)點加入到等待隊列的隊尾，如果隊列為空屏轰，則會新建一個啞節(jié)點作為頭節(jié)點颊郎，再將當前節(jié)點接在頭節(jié)點的后面。

addWaiter(Node.EXCLUSIVE)方法最終返回了代表了當前線程的Node節(jié)點霎苗，在返回的那一刻姆吭，這個節(jié)點必然是當時的sync queue的尾節(jié)點。

不過值得注意的是唁盏，enq方法也是有返回值（雖然這里我們并沒有使用它的返回值）内狸，但是它返回的是node節(jié)點的前驅(qū)節(jié)點，這個返回值雖然在addWaiter方法中并沒有使用厘擂，但是在其他地方會被用到昆淡。

我們再回到獲取鎖的邏輯中：

public final void acquire(int arg) {
    if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

當addWaiter(Node.EXCLUSIVE)執(zhí)行完畢后，節(jié)點現(xiàn)在已經(jīng)被成功添加到sync queue中了刽严，接下來將執(zhí)行acquireQueued方法昂灵。

acquireQueued

該方法是最復(fù)雜的一個方法, 也是最難啃的骨頭, 看代碼之前首先簡單的說明幾點:

(1) 能執(zhí)行到該方法, 說明addWaiter 方法已經(jīng)成功將包裝了當前Thread的節(jié)點添加到了等待隊列的隊尾
(2) 該方法中將再次嘗試去獲取鎖
(3) 在再次嘗試獲取鎖失敗后, 判斷是否需要把當前線程掛起

為什么前面獲取鎖失敗了, 這里還要再次嘗試獲取鎖呢?
首先, 這里再次嘗試獲取鎖是基于一定的條件的,即:

當前節(jié)點的前驅(qū)節(jié)點就是HEAD節(jié)點

因為我們知道，head節(jié)點就是個啞節(jié)點，它不代表任何線程倔既，或者代表了持有鎖的線程恕曲，如果當前節(jié)點的前驅(qū)節(jié)點就是head節(jié)點，那就說明當前節(jié)點已經(jīng)是排在整個等待隊列最前面的了渤涌。

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            // 在當前節(jié)點的前驅(qū)就是HEAD節(jié)點時, 再次嘗試獲取鎖
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            //在獲取鎖失敗后, 判斷是否需要把當前線程掛起
            if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

注意佩谣，這里又來了個自旋操作，我們一段段來看：

final Node p = node.predecessor();
// 在當前節(jié)點的前驅(qū)就是HEAD節(jié)點時, 再次嘗試獲取鎖
if (p == head && tryAcquire(arg)) {
    setHead(node);
    p.next = null; // help GC
    failed = false;
    return interrupted;
}

首先我們獲取尾節(jié)點的前驅(qū)節(jié)點（因為上一步中返回的就是尾節(jié)點实蓬，并且這個節(jié)點就是代表了當前線程的Node）茸俭。
如果前驅(qū)節(jié)點就是head節(jié)點，那說明當前線程已經(jīng)排在了隊列的最前面安皱，所以這里我們再試著去獲取鎖调鬓。如果這一次獲取成功了，即tryAcquire方法返回了true, 則我們將進入if代碼塊酌伊，調(diào)用setHead方法：

private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

這個方法將head指向傳進來的node,并且將node的thread和prev屬性置為null, 如下圖所示：

image.png

可以看出腾窝，這個方法的本質(zhì)是丟棄原來的head，將head指向已經(jīng)獲得了鎖的node居砖。但是接著又將該node的thread屬性置為null了虹脯，這某種意義上導(dǎo)致了這個新的head節(jié)點又成為了一個啞節(jié)點，它不代表任何線程奏候。為什么要這樣做呢循集，因為在tryAcquire調(diào)用成功后，exclusiveOwnerThread屬性就已經(jīng)記錄了當前獲取鎖的線程了蔗草，此處沒有必要再記錄咒彤。這某種程度上就是將當前線程從等待隊列里面拿出來了，是一個變相的出隊操作咒精。

還有另外一個特點是镶柱，這個setHead方法只是個普通方法，并沒有像之前enq方法中那樣采用compareAndSetHead方法模叙，這是為什么呢奸例？ 同我們之前分析setState方法一樣：

因為這里不會產(chǎn)生競爭！

在enq方法中向楼，當我們設(shè)置頭節(jié)點的時候，是新建一個啞節(jié)點并將它作為頭節(jié)點谐区，這個時候湖蜕，可能多個線程都在執(zhí)行這一步，因此我們需要通過CAS操作保證只有一個線程能成功宋列。
在acquireQueued方法里昭抒，由于我們在調(diào)用到setHead的時，已經(jīng)通過tryAcquire方法獲得了鎖，這意味著：

1.此時沒有其他線程在創(chuàng)建新的頭節(jié)點——因為很明顯此時隊列并不是空的灭返，不會執(zhí)行到創(chuàng)建頭節(jié)點的代碼
2.此時能執(zhí)行setHead的只有一個線程——因為要執(zhí)行到setHead, 必然是tryAcquire已經(jīng)返回了true, 而同一時刻盗迟，只有一個線程能獲取到鎖
綜上，在整個if語句內(nèi)的代碼即使不加鎖熙含，也是線程安全的罚缕，不需要采用CAS操作。

接下來我們再來看看另一種情況怎静，即p == head && tryAcquire(arg)返回了false邮弹，此時我們需要判斷是否需要將當前線程掛起：

shouldParkAfterFailedAcquire

從函數(shù)名也可以看出, 該方法用于決定在獲取鎖失敗后, 是否將線程掛起.

決定的依據(jù)就是前驅(qū)節(jié)點的waitStatus值。

（有沒發(fā)現(xiàn)一直到現(xiàn)在蚓聘，前面的分析中我們都沒有用到waitStatus的值腌乡，終于在這里要用到了）

我們先來回顧一下waitStatus有哪些狀態(tài)值：

static final int CANCELLED =  1;
static final int SIGNAL    = -1;
static final int CONDITION = -2;
static final int PROPAGATE = -3;

一共有四種狀態(tài)，但是我們在開篇的時候就說過夜牡，在獨占鎖鎖的獲取操作中与纽，我們只用到了其中的兩個——CANCELLED和SIGNAL。
當然塘装，前面我們在創(chuàng)建節(jié)點的時候并沒有給waitStatus賦值急迂，因此每一個節(jié)點最開始的時候waitStatus的值都被初始化為0，即不屬于上面任何一種狀態(tài)氢哮。

那么CANCELLED和SIGNAL代表什么意思呢袋毙？

CANCELLED狀態(tài)很好理解，它表示Node所代表的當前線程已經(jīng)取消了排隊冗尤，即放棄獲取鎖了听盖。

SIGNAL這個狀態(tài)就有點意思了，它不是表征當前節(jié)點的狀態(tài)裂七，而是當前節(jié)點的下一個節(jié)點的狀態(tài)皆看。
當一個節(jié)點的waitStatus被置為SIGNAL，就說明它的下一個節(jié)點（即它的后繼節(jié)點）已經(jīng)被掛起了（或者馬上就要被掛起了）背零，因此在當前節(jié)點釋放了鎖或者放棄獲取鎖時腰吟，如果它的waitStatus屬性為SIGNAL，它還要完成一個額外的操作——喚醒它的后繼節(jié)點徙瓶。

有意思的是毛雇，SIGNAL這個狀態(tài)的設(shè)置常常不是節(jié)點自己給自己設(shè)的，而是后繼節(jié)點設(shè)置的侦镇，這里給大家打個比方：

比如說出去吃飯灵疮，在人多的時候經(jīng)常要排隊取號，你取到了8號壳繁，前面還有7個人在等著進去震捣，你就和排在你前面的7號講“哥們荔棉，我現(xiàn)在排在你后面，隊伍這么長蒿赢，估計一時半會兒也輪不到我润樱，我去那邊打個盹，一會輪到你進去了(release)或者你不想等了(cancel), 麻煩你都叫醒我”羡棵，說完壹若，你就把他的waitStatus值設(shè)成了SIGNAL。

換個角度講晾腔，當我們決定要將一個線程掛起之前舌稀，首先要確保自己的前驅(qū)節(jié)點的waitStatus為SIGNAL，這就相當于給自己設(shè)一個鬧鐘再去睡灼擂，這個鬧鐘會在恰當?shù)臅r候叫醒自己壁查，否則，如果一直沒有人來叫醒自己剔应，自己可能就一直睡到天荒地老了睡腿。

理解了CANCELLED和SIGNAL這兩個狀態(tài)的含義后，我們再來看看shouldParkAfterFailedAcquire是怎么用的：

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus; // 獲得前驅(qū)節(jié)點的ws
    if (ws == Node.SIGNAL)
        // 前驅(qū)節(jié)點的狀態(tài)已經(jīng)是SIGNAL了峻贮，說明鬧鐘已經(jīng)設(shè)了席怪，可以直接睡了
        return true;
    if (ws > 0) {
        // 當前節(jié)點的 ws > 0, 則為 Node.CANCELLED 說明前驅(qū)節(jié)點已經(jīng)取消了等待鎖(由于超時或者中斷等原因)
        // 既然前驅(qū)節(jié)點不等了, 那就繼續(xù)往前找, 直到找到一個還在等待鎖的節(jié)點
        // 然后我們跨過這些不等待鎖的節(jié)點, 直接排在等待鎖的節(jié)點的后面 (是不是很開心!!!)
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        // 前驅(qū)節(jié)點的狀態(tài)既不是SIGNAL，也不是CANCELLED
        // 用CAS設(shè)置前驅(qū)節(jié)點的ws為 Node.SIGNAL纤控，給自己定一個鬧鐘
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

可以看出挂捻，shouldParkAfterFailedAcquire所做的事情無外乎：

• 如果為前驅(qū)節(jié)點的waitStatus值為 Node.SIGNAL 則直接返回 true
• 如果為前驅(qū)節(jié)點的waitStatus值為 Node.CANCELLED(ws > 0), 則跳過那些節(jié)點, 重新尋找正常等待中的前驅(qū)節(jié)點，然后排在它后面船万，返回false
• 其他情況, 將前驅(qū)節(jié)點的狀態(tài)改為 Node.SIGNAL, 返回false
  注意了刻撒，這個函數(shù)只有在當前節(jié)點的前驅(qū)節(jié)點的waitStatus狀態(tài)本身就是SIGNAL的時候才會返回true, 其他時候都會返回false, 我們再回到這個方法的調(diào)用處：

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;
            }
            // 我們在這里！在這里９⒌肌声怔！在這里！２丈搿醋火！
            // 我們在這里！在這里Ｏ渎馈芥驳！在這里！２绺摺兆旬！
            // 我們在這里！在這里Ｑ挪伞爵憎！在這里！；楣稀宝鼓！
            if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

可以看出，當shouldParkAfterFailedAcquire返回false后巴刻，會繼續(xù)回到循環(huán)中再次嘗試獲取鎖——這是因為此時我們的前驅(qū)節(jié)點可能已經(jīng)變了（搞不好前驅(qū)節(jié)點就變成head節(jié)點了呢）愚铡。

當shouldParkAfterFailedAcquire返回true，即當前節(jié)點的前驅(qū)節(jié)點的waitStatus狀態(tài)已經(jīng)設(shè)為SIGNAL后胡陪，我們就可以安心的將當前線程掛起了沥寥，此時我們將調(diào)用parkAndCheckInterrupt：

parkAndCheckInterrupt

到這個函數(shù)已經(jīng)是最后一步了, 就是將線程掛起, 等待被喚醒

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this); // 線程被掛起，停在這里不再往下執(zhí)行了
    return Thread.interrupted();
}

注意柠座！LockSupport.park(this)執(zhí)行完成后線程就被掛起了邑雅，除非其他線程unpark了當前線程，或者當前線程被中斷了妈经，否則代碼是不會再往下執(zhí)行的淮野，后面的Thread.interrupted()也不會被執(zhí)行，那后面這個Thread.interrupted()是干什么用的呢吹泡？ 我們下一篇再講骤星。

總結(jié)

1.AQS中用state屬性表示鎖，如果能成功將state屬性通過CAS操作從0設(shè)置成1即獲取了鎖
2.獲取了鎖的線程才能將exclusiveOwnerThread設(shè)置成自己
3.addWaiter負責(zé)將當前等待鎖的線程包裝成Node,并成功地添加到隊列的末尾爆哑，這一點是由它調(diào)用的enq方法保證的洞难，enq方法同時還負責(zé)在隊列為空時初始化隊列。
4.acquireQueued方法用于在Node成功入隊后揭朝，繼續(xù)嘗試獲取鎖（取決于Node的前驅(qū)節(jié)點是不是head）队贱，或者將線程掛起
5.shouldParkAfterFailedAcquire方法用于保證當前線程的前驅(qū)節(jié)點的waitStatus屬性值為SIGNAL,從而保證了自己掛起后，前驅(qū)節(jié)點會負責(zé)在合適的時候喚醒自己萝勤。
6.parkAndCheckInterrupt方法用于掛起當前線程露筒，并檢查中斷狀態(tài)。
7.如果最終成功獲取了鎖敌卓，線程會從lock()方法返回慎式，繼續(xù)往下執(zhí)行；否則趟径，線程會阻塞等待瘪吏。

本文中的源碼基于JDK1.8