摘要：本篇我們將以的公平鎖為例來詳細看看使用獲取獨占鎖的流程。本文中的源碼基于。由于本篇我們分析的是獨占鎖，同一時刻，鎖只能被一個線程所持有。由于在整個搶鎖過程中，我們都是不響應(yīng)中斷的。

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

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

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

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

本文中的源碼基于JDK1.8 。

系列文章目錄

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

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

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

狀態(tài)：一般是一個state屬性，它基本是整個工具的核心，通常整個工具都是在設(shè)置和修改狀態(tài)，很多方法的操作都依賴于當(dāng)前狀態(tài)是什么。由于狀態(tài)是全局共享的，一般會被設(shè)置成volatile類型，以保證其修改的可見性；

隊列：隊列通常是一個等待的集合，大多數(shù)以鏈表的形式實現(xiàn)。隊列采用的是悲觀鎖的思想，表示當(dāng)前所等待的資源，狀態(tài)或者條件短時間內(nèi)可能無法滿足。因此，它會將當(dāng)前線程包裝成某種類型的數(shù)據(jù)結(jié)構(gòu)，扔到一個等待隊列中，當(dāng)一定條件滿足后，再從等待隊列中取出。

CAS: CAS操作是最輕量的并發(fā)處理，通常我們對于狀態(tài)的修改都會用到CAS操作，因為狀態(tài)可能被多個線程同時修改，CAS操作保證了同一個時刻，只有一個線程能修改成功，從而保證了線程安全，CAS操作基本是由Unsafe工具類的compareAndSwapXXX來實現(xiàn)的；CAS采用的是樂觀鎖的思想，因此常常伴隨著自旋，如果發(fā)現(xiàn)當(dāng)前無法成功地執(zhí)行CAS，則不斷重試，直到成功為止，自旋的的表現(xiàn)形式通常是一個死循環(huán)for(;;)。

上面我們已經(jīng)總結(jié)了java并發(fā)編程的套路，下面我們就以這個套路為切入點來分析AQS的實現(xiàn)。

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

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

private volatile int state; 

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

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

private transient Thread exclusiveOwnerThread; //繼承自AbstractOwnableSynchronizer

exclusiveOwnerThread屬性的值即為當(dāng)前持有鎖的線程，它就是我們在分析監(jiān)視器鎖的原理的時候所說的“鐵王座”。

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

我們前面說過，在并發(fā)編程中使用隊列通常是將當(dāng)前線程包裝成某種類型的數(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，它表示了當(dāng)前Node所代表的線程的等待鎖的狀態(tài)，在獨占鎖模式下，我們只需要關(guān)注CANCELLED SIGNAL兩種狀態(tài)即可。這里還有一個nextWaiter屬性，它在獨占鎖模式下永遠為null，僅僅起到一個標(biāo)記作用，沒有實際意義。這么一分析，這個Node類是不是就簡單了好多？<(￣︶￣)>

說完隊列中的節(jié)點，我們接著說回這個sync queue，AQS是怎么使用這個隊列的呢，既然是雙向鏈表，操縱它自然只需要一個頭結(jié)點和一個尾節(jié)點：

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

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

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

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

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

thread：表示當(dāng)前Node所代表的線程

waitStatus：表示節(jié)點所處的等待狀態(tài)，共享鎖模式下只需關(guān)注三種狀態(tài)：SIGNAL CANCELLED 初始態(tài)(0)

prev next：節(jié)點的前驅(qū)和后繼

nextWaiter：進作為標(biāo)記，值永遠為null，表示當(dāng)前處于獨占鎖模式

前面我們提到過，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方法。

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

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

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

private volatile int state; //鎖的狀態(tài)
private transient Thread exclusiveOwnerThread; // 當(dāng)前持有鎖的線程，注意這個屬性是從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;

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

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

值得注意的是, ReentrantLock有 公平鎖 和 非公平鎖 兩種實現(xiàn), 默認(rè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)，讀者可以對照以下流程圖, 就不容易被繞暈了.

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), 負(fù)責(zé)在獲取鎖失敗后調(diào)用, 將當(dāng)前請求鎖的線程包裝成Node扔到sync queue中去，并返回這個Node。

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

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

在前驅(qū)節(jié)點就是head節(jié)點的時候,繼續(xù)嘗試獲取鎖

將當(dāng)前線程掛起,使CPU不再調(diào)度它

（4）selfInterrupt

該方法由AQS實現(xiàn), 用于中斷當(dāng)前線程。由于在整個搶鎖過程中，我們都是不響應(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 獲取鎖的邏輯其實很簡單——判斷當(dāng)前鎖有沒有被占用：

如果鎖沒有被占用, 嘗試以公平的方式獲取鎖

如果鎖已經(jīng)被占用, 檢查是不是鎖重入

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

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    // 首先獲取當(dāng)前鎖的狀態(tài)
    int c = getState(); 
    
    // c=0 說明當(dāng)前鎖是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); // 將當(dāng)前線程設(shè)置為占用鎖的線程
            return true;
        }
    }
    
    // 如果 c>0 說明鎖已經(jīng)被占用了
    // 對于可重入鎖, 這個時候檢查占用鎖的線程是不是就是當(dā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;
    }
    
    // 到這里說明有人占用了鎖, 并且占用鎖的不是當(dāng)前線程, 則獲取鎖失敗
    return false;
}

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

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

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

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

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

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

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

addWaiter(Node.EXCLUSIVE)

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode); //將當(dāng)前線程包裝成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方式將當(dāng)前節(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的方式，確保當(dāng)前節(jié)點入隊。

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

等待隊列現(xiàn)在是空的，沒有線程在等待。

其他線程在當(dāng)前線程入隊的過程中率先完成了入隊，導(dǎo)致尾節(jié)點的值已經(jīng)改變了，CAS操作失敗。

在該方法中, 我們使用了死循環(huán), 即以自旋方式將節(jié)點插入隊列，如果失敗則不停的嘗試, 直到成功為止, 另外, 該方法也負(fù)責(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;
            }
        }
    }
}

這里尤其要注意的是，當(dāng)隊列為空時，我們初始化隊列并沒有使用當(dāng)前傳進來的節(jié)點，而是：
新建了一個空節(jié)點?。?！
新建了一個空節(jié)點！??！
新建了一個空節(jié)點！??！

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

這就意味著，在這個等待隊列中，頭結(jié)點是一個“啞節(jié)點”，它不代表任何等待的線程。
head節(jié)點不代表任何線程，它就是一個空節(jié)點?。?！
head節(jié)點不代表任何線程，它就是一個空節(jié)點?。?！
head節(jié)點不代表任何線程，它就是一個空節(jié)點?。?！

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

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

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

設(shè)置node的前驅(qū)節(jié)點為當(dāng)前的尾節(jié)點：node.prev = t

修改tail屬性，使它指向當(dāng)前節(jié)點

修改原來的尾節(jié)點，使它的next指向當(dāng)前節(jié)點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

final Node p = node.predecessor();
// 在當(dāng)前節(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é)點就是代表了當(dāng)前線程的Node）。
如果前驅(qū)節(jié)點就是head節(jié)點，那說明當(dāng)前線程已經(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, 如下圖所示：

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

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

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

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

此時沒有其他線程在創(chuàng)建新的頭節(jié)點——因為很明顯此時隊列并不是空的，不會執(zhí)行到創(chuàng)建頭節(jié)點的代碼

此時能執(zhí)行setHead的只有一個線程——因為要執(zhí)行到setHead, 必然是tryAcquire已經(jīng)返回了true, 而同一時刻，只有一個線程能獲取到鎖

綜上，在整個if語句內(nèi)的代碼即使不加鎖，也是線程安全的，不需要采用CAS操作。

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

從函數(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。
當(dāng)然，前面我們在創(chuàng)建節(jié)點的時候并沒有給waitStatus賦值，因此每一個節(jié)點最開始的時候waitStatus的值都被初始化為0，即不屬于上面任何一種狀態(tài)。

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

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

SIGNAL這個狀態(tài)就有點意思了，它不是表征當(dāng)前節(jié)點的狀態(tài)，而是當(dāng)前節(jié)點的下一個節(jié)點的狀態(tài)。
當(dāng)一個節(jié)點的waitStatus被置為SIGNAL，就說明它的下一個節(jié)點（即它的后繼節(jié)點）已經(jīng)被掛起了（或者馬上就要被掛起了），因此在當(dā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。

換個角度講，當(dāng)我們決定要將一個線程掛起之前，首先要確保自己的前驅(qū)節(jié)點的waitStatus為SIGNAL，這就相當(dāng)于給自己設(shè)一個鬧鐘再去睡，這個鬧鐘會在恰當(dāng)?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) {
        // 當(dāng)前節(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ù)只有在當(dāng)前節(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);
    }
}

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

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

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

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

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

AQS中用state屬性表示鎖，如果能成功將state屬性通過CAS操作從0設(shè)置成1即獲取了鎖

獲取了鎖的線程才能將exclusiveOwnerThread設(shè)置成自己

addWaiter負(fù)責(zé)將當(dāng)前等待鎖的線程包裝成Node,并成功地添加到隊列的末尾，這一點是由它調(diào)用的enq方法保證的，enq方法同時還負(fù)責(zé)在隊列為空時初始化隊列。

acquireQueued方法用于在Node成功入隊后，繼續(xù)嘗試獲取鎖（取決于Node的前驅(qū)節(jié)點是不是head），或者將線程掛起

shouldParkAfterFailedAcquire方法用于保證當(dāng)前線程的前驅(qū)節(jié)點的waitStatus屬性值為SIGNAL,從而保證了自己掛起后，前驅(qū)節(jié)點會負(fù)責(zé)在合適的時候喚醒自己。

parkAndCheckInterrupt方法用于掛起當(dāng)前線程，并檢查中斷狀態(tài)。

如果最終成功獲取了鎖，線程會從lock()方法返回，繼續(xù)往下執(zhí)行；否則，線程會阻塞等待。

(完)

下一篇: 逐行分析AQS源碼(2)——獨占鎖的釋放

查看更多系列文章：系列文章目錄