然后，我們重點(diǎn)關(guān)注的是enq過(guò)程。

// 將新的節(jié)點(diǎn)插入到等待隊(duì)列的尾部。如果等待隊(duì)列不存在，一定要對(duì)其初始化
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { 
            // 隊(duì)列為空情況下，CAS操作將頭節(jié)點(diǎn)進(jìn)行更新，將頭節(jié)點(diǎn)設(shè)置為空節(jié)點(diǎn)。
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            // 尾節(jié)點(diǎn)存在的情況下，代表AQS等待隊(duì)列已經(jīng)初始化完成。
            // 與addWaiter一樣，先將新增節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)鏈接到尾節(jié)點(diǎn)
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                // 當(dāng)更新尾節(jié)點(diǎn)成功后，就將原尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)連接為新增的節(jié)點(diǎn)
                t.next = node;
                return t;
            }
        }
    }
}

AQS中對(duì)鎖隊(duì)列的初始化過(guò)程并不是在類(lèi)建立的時(shí)候初始化，而是第一次有線程開(kāi)始獲取同步資源時(shí)。它初始化時(shí)將頭節(jié)點(diǎn)設(shè)定為一個(gè)空的Node節(jié)點(diǎn)，新增的節(jié)點(diǎn)都添加在頭節(jié)點(diǎn)后的后繼節(jié)點(diǎn)中。

Q2：為什么要初始化成一個(gè)空節(jié)點(diǎn)作為頭節(jié)點(diǎn)？

這個(gè)與后面文章的內(nèi)容acquireQueue方法中入隊(duì)操作有關(guān)。Q1問(wèn)題提到了AQS借用了CLH的思想，也就是不斷對(duì)前驅(qū)節(jié)點(diǎn)的狀態(tài)進(jìn)行訪問(wèn)。那么在判斷是否可以獲取資源時(shí)，也需要再次訪問(wèn)前驅(qū)節(jié)點(diǎn)。如果初始化的時(shí)候不將頭節(jié)點(diǎn)賦值為空節(jié)點(diǎn)，那么前驅(qū)節(jié)點(diǎn)為null，這個(gè)與不是初始化階段的隊(duì)列情況不同，勢(shì)必會(huì)復(fù)雜后面的流程。這也是AQS的簡(jiǎn)單優(yōu)化之一。

AQS的初始化結(jié)構(gòu).png

新增線程節(jié)點(diǎn)的AQS結(jié)構(gòu)圖.png

3.1.3、acquireQueued

在將新的線程節(jié)點(diǎn)入隊(duì)后，這個(gè)方法將會(huì)執(zhí)行阻塞，并根據(jù)當(dāng)前線程信息更新隊(duì)列。它采用一個(gè)循環(huán)去處理隊(duì)列中的信息，只有隊(duì)列中獲取節(jié)點(diǎn)成功才能從循環(huán)中彈出。

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            // 獲取節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
            final Node p = node.predecessor();
            // 該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是頭節(jié)點(diǎn)，就嘗試去獲取一下許可
            // 當(dāng)獲取許可成功后，就可以將頭節(jié)點(diǎn)設(shè)置為當(dāng)前的節(jié)點(diǎn)
            // 并將后繼節(jié)點(diǎn)置空，重置狀態(tài)
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // 當(dāng)獲取許可失敗后，會(huì)判斷需不需要對(duì)線程進(jìn)行阻塞
            if (shouldParkAfterFailedAcquire(p, node) &&
                  parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        // 如果執(zhí)行過(guò)程中出現(xiàn)了了錯(cuò)誤，或者中斷后，就會(huì)對(duì)數(shù)據(jù)進(jìn)行處理，完成銷(xiāo)毀的過(guò)程。
        if (failed)
            cancelAcquire(node);
    }
}

這里的核心在于兩個(gè)if語(yǔ)句的內(nèi)容:

1. 第一個(gè)if語(yǔ)句主要實(shí)現(xiàn)對(duì)前驅(qū)節(jié)點(diǎn)的判定，只有是頭節(jié)點(diǎn)才會(huì)再次嘗試能否拿到資源的許可訪問(wèn)權(quán)。當(dāng)拿到了許可權(quán)后，也就是持有獨(dú)占權(quán)，那么就會(huì)將頭節(jié)點(diǎn)更新為當(dāng)前的線程節(jié)點(diǎn)。返回的狀態(tài)為interrupted狀態(tài)。
2. 第二個(gè)if語(yǔ)句是前驅(qū)節(jié)點(diǎn)不是頭節(jié)點(diǎn)或者在許可獲取失敗后，對(duì)線程節(jié)點(diǎn)的狀態(tài)進(jìn)行更新，并對(duì)合適的線程進(jìn)行阻塞操作。

3.1.4、shouldParkAfterFailedAcquire

在線程不是頭節(jié)點(diǎn)或者許可獲取失敗后，會(huì)調(diào)用此方法。

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    // 只有SIGNAL狀態(tài)才能阻塞線程
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {
        do {
            // 向隊(duì)列的前驅(qū)節(jié)點(diǎn)找,一直到找到一個(gè)狀態(tài)碼小于0的,也就是非CANCEL狀態(tài)的
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
            // 把找到節(jié)點(diǎn)后繼節(jié)點(diǎn)鏈接到當(dāng)前節(jié)點(diǎn)
            pred.next = node;
    } else {
        // 如果前驅(qū)節(jié)點(diǎn)的狀態(tài)是小于0的，CAS方式將前驅(qū)節(jié)點(diǎn)的狀態(tài)更新為SIGNAL。同時(shí)不對(duì)線程阻塞
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

這個(gè)函數(shù)是整個(gè)循環(huán)中處理信號(hào)狀態(tài)的唯一方法。信號(hào)是什么？也就是我們?cè)贜ode章節(jié)提到的waitStatus狀態(tài)。

waitStatus狀態(tài)初始化的值是0。如代碼中描述的，waitStatus只有前驅(qū)節(jié)點(diǎn)是SIGNAL狀態(tài)才會(huì)將當(dāng)前的線程阻塞住。其他情況下，waitStatus為非正數(shù)時(shí)，就會(huì)將前驅(qū)節(jié)點(diǎn)的狀態(tài)更新為SIGNAL。而狀態(tài)為正數(shù)時(shí)，代表節(jié)點(diǎn)被取消了，就會(huì)不斷向前尋找，直到找到未被取消的節(jié)點(diǎn)。取消的節(jié)點(diǎn)通通會(huì)被垃圾回收機(jī)制處理掉。

【舉個(gè)栗子！就是一個(gè)栗子】這樣理解起來(lái)可能還是比較困難，我們可以試想一個(gè)情形，兩個(gè)線程依次爭(zhēng)奪獨(dú)占權(quán)，線程A先獲得了獨(dú)占權(quán)，獲得后的AQS等待隊(duì)列的狀態(tài)是如下圖所示

線程A獲得了獨(dú)占權(quán)后的等待隊(duì)列結(jié)構(gòu).png

在線程A釋放獨(dú)占權(quán)之前，線程B也發(fā)起了獨(dú)占權(quán)的爭(zhēng)奪。于是，按照之前的過(guò)程分析，在獲取占有權(quán)失敗后，會(huì)調(diào)用addWaiter方法，線程B的節(jié)點(diǎn)會(huì)被添加到等待隊(duì)列中。添加后的結(jié)構(gòu)就如下圖所示

addWaiter后的等待隊(duì)列結(jié)構(gòu).png

由于線程A一直沒(méi)釋放占有權(quán)，那么線程B就會(huì)進(jìn)入到shouldParkAfterFailedAcquire方法內(nèi)，而線程B的前驅(qū)節(jié)點(diǎn)就是線程A，而線程A節(jié)點(diǎn)的waitStatus是0，那就將它的狀態(tài)更新為SIGNAL。它會(huì)返回到acquireQueue的死循環(huán)中再次進(jìn)行占有權(quán)的獲取，當(dāng)然如果再次沒(méi)有獲取成功，也會(huì)進(jìn)入此方法，此次它的前驅(qū)節(jié)點(diǎn)線程A的waitStatus已經(jīng)更新為SIGNAL。返回true。

shouldParkAfterFailedAcquire后的AQS等待隊(duì)列結(jié)構(gòu).png

Q3：為什么需要SIGNAL信號(hào)才阻塞線程呢？

其實(shí)只是為了在線程park阻塞和解除阻塞的次數(shù)不那么頻繁，減少了不必要的線程阻塞切換時(shí)間。SIGNAL設(shè)置后，只有確定SIGNAL信號(hào)的線程才會(huì)阻塞。

3.1.5、parkAndCheckInterrupt

這個(gè)方法很簡(jiǎn)單，就是使用LockSupport.park對(duì)線程進(jìn)行了阻塞，返回線程是否被中斷的狀態(tài)。LockSupport的細(xì)節(jié)不做解釋?zhuān)?jiǎn)單來(lái)說(shuō)，它主要是用來(lái)解決Thread.suspend這種方法會(huì)產(chǎn)生死鎖的問(wèn)題，同時(shí)能夠?qū)€程進(jìn)行阻塞，核心是由native方法進(jìn)行處理。有想深究的可以自行Google哈。

3.2、release操作

與acquire相對(duì)的方法也就是釋放占有權(quán)的release方法。

3.2.1、release

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

相比之下，release方法涉及的步驟相對(duì)來(lái)說(shuō)簡(jiǎn)單一些。與acquire方法類(lèi)似，release也有一個(gè)tryRelease方法，是子類(lèi)去實(shí)現(xiàn)具體功能。

具體步驟：

1. 調(diào)用子類(lèi)的tryRelease方法。
2. 成功返回后，判斷頭節(jié)點(diǎn)是否存在和頭節(jié)點(diǎn)的狀態(tài)
3. 若頭節(jié)點(diǎn)存在，且頭節(jié)點(diǎn)的waitStatus狀態(tài)是非0，也就說(shuō)明AQS不是初始化階段
4. 將后繼節(jié)點(diǎn)的線程喚醒

【這里重點(diǎn)注意一下】：waitStatus狀態(tài)是0，代表這個(gè)節(jié)點(diǎn)的狀態(tài)還未更新，因此AQS沒(méi)有將后繼節(jié)點(diǎn)進(jìn)行阻塞，這個(gè)時(shí)候就不能去做unpark的操作。

3.2.2、unparkSuccessor

在成功獲取到子類(lèi)的release認(rèn)可后， 會(huì)進(jìn)行喚醒過(guò)程，對(duì)該節(jié)點(diǎn)的后繼節(jié)點(diǎn)進(jìn)行喚醒。
unparkSuccessor方法不僅僅要處理release的解除阻塞操作，同時(shí)需要對(duì)cancel的進(jìn)行區(qū)分。核心內(nèi)容在于對(duì)Cancel狀態(tài)的處理。

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    // 如果當(dāng)前節(jié)點(diǎn)的狀態(tài)小于0，將狀態(tài)更新為0，重置一下
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    // 后繼節(jié)點(diǎn)不存在或者后繼節(jié)點(diǎn)的waitStatus大于0（也就是被取消的狀態(tài)）
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        // 置后繼節(jié)點(diǎn)為null，
        // 若當(dāng)前節(jié)點(diǎn)發(fā)生了取消操作，重新從尾部開(kāi)始遍歷，找到?jīng)]有標(biāo)記為取消的節(jié)點(diǎn)進(jìn)行阻塞操作
        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);
}

3.3、cancelAcquire

在整個(gè)acquire的過(guò)程中，如果發(fā)生超時(shí)，線程發(fā)起了中斷操作，那么就會(huì)發(fā)起cancel方法，將線程的信息情況。具體見(jiàn)代碼

private void cancelAcquire(Node node) {
    ...
    node.thread = null;

    // 跳過(guò)所有取消了的前驅(qū)節(jié)點(diǎn)
    Node pred = node.prev;
    while (pred.waitStatus > 0)
        node.prev = pred = pred.prev;

    Node predNext = pred.next;
    // 不采用 CAS方式進(jìn)行寫(xiě)操作
    node.waitStatus = Node.CANCELLED;

    // 如果此節(jié)點(diǎn)已經(jīng)是隊(duì)尾，就將自己CAS刪除。
    if (node == tail && compareAndSetTail(node, pred)) {
        compareAndSetNext(pred, predNext, null);
    } else {
        // 如果后繼節(jié)點(diǎn)需要信號(hào)SIGNAL，就自己前驅(qū)結(jié)點(diǎn)重新鏈接。
        // 否則將線程喚醒，進(jìn)行propagate過(guò)程
        int ws;
        if (pred != head &&
            ((ws = pred.waitStatus) == Node.SIGNAL ||
             (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
            pred.thread != null) {
            Node next = node.next;
            if (next != null && next.waitStatus <= 0)
                compareAndSetNext(pred, predNext, next);
        } else {
            unparkSuccessor(node);
        }
        node.next = node; 
    }
}

cancelAcquire的方法這里進(jìn)行了一些不同情況下的取消操作。

1. 取消的節(jié)點(diǎn)是隊(duì)尾節(jié)點(diǎn)tail。那么直接將pred的next和當(dāng)前節(jié)點(diǎn)的prev全部置null。重新設(shè)置一下tail節(jié)點(diǎn)。
2. 取消的節(jié)點(diǎn)是隊(duì)列中的一個(gè)節(jié)點(diǎn)，并且不是head頭節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)。那么也很容易理解，就是將pred的next和當(dāng)前節(jié)點(diǎn)的next進(jìn)行一個(gè)鏈接。那么有一個(gè)疑問(wèn)，代碼中只將next節(jié)點(diǎn)鏈接了，prev的節(jié)點(diǎn)如何連接。這里的prev是由其它線程做的，由于當(dāng)前節(jié)點(diǎn)已經(jīng)是CANCEL狀態(tài)，其他線程在進(jìn)行競(jìng)爭(zhēng)時(shí)，都會(huì)遍歷前驅(qū)節(jié)點(diǎn)，重新鏈接前驅(qū)節(jié)點(diǎn)完成prev的鏈接。
3. 取消的節(jié)點(diǎn)是隊(duì)列頭節(jié)點(diǎn)head的直接后繼節(jié)點(diǎn)。那么如果取消的節(jié)點(diǎn)后繼節(jié)點(diǎn)是存在的，可以直接喚醒后繼節(jié)點(diǎn)。

小結(jié)

本文只是分析了獨(dú)占式模式，第二篇將分析共享式的AQS的情況。

參考文章

1. JAVA并發(fā)編程學(xué)習(xí)筆記之CLH隊(duì)列鎖
2. A Hierarchical CLH Queue Lock(CLH原理原文)

如有問(wèn)題，歡迎批評(píng)指正！