并發(fā)編程——詳解 AQS CLH 鎖

從 acquire 方法開始 —— 獲取
為什么 AQS 需要一個(gè)虛擬 head 節(jié)點(diǎn)
reelase 方法如何釋放鎖
總結(jié)

前言

AQS 是 JUC 中的核心，其中封裝了資源的獲取和釋放感挥，在我們之前的并發(fā)編程之 AQS 源碼剖析文章中，我們已經(jīng)從 ReentranLock 那里分析了鎖的獲取和釋放柳爽。但我有必要再次解釋 AQS 的核心 CLH 鎖卫旱。

這里引用一下別人對(duì)于 CLH 的解釋：

CLH CLH(Craig, Landin, and Hagersten locks): 是一個(gè)自旋鎖垒玲，能確保無(wú)饑餓性唱歧，提供先來(lái)先服務(wù)的公平性朦乏。

CLH鎖也是一種基于鏈表的可擴(kuò)展锥累、高性能、公平的自旋鎖集歇，申請(qǐng)線程只在本地變量上自旋桶略，它不斷輪詢前驅(qū)的狀態(tài)，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋。

Java AQS 的設(shè)計(jì)對(duì) CLH 鎖進(jìn)行了優(yōu)化或者說變體际歼。

我們還是從代碼開始說起吧惶翻。

1. 從 acquire 方法開始 —— 獲取

acquire 方法是獲取鎖的常用方法。代碼如下：

public final void acquireQueued(int arg) {
    // 當(dāng) tryAcquire 返回 true 就說明獲取到鎖了鹅心，直接結(jié)束吕粗。
    // 反之，返回 false 的話旭愧，就需要執(zhí)行后面的方法颅筋。
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

只要子類的 tryAcquire 方法返回 false，那么就說明獲取鎖事變输枯，就需要將自己加入隊(duì)列议泵。

private Node addWaiter(Node mode) {
    // 創(chuàng)建一個(gè)獨(dú)占類型的節(jié)點(diǎn)
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    // 如果 tail 節(jié)點(diǎn)不是 null，就將新節(jié)點(diǎn)的 pred 節(jié)點(diǎn)設(shè)置為 tail 節(jié)點(diǎn)桃熄。
    // 并且將新節(jié)點(diǎn)設(shè)置成 tail 節(jié)點(diǎn)先口。
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 如果 tail 節(jié)點(diǎn)是  null，或者 CAS 設(shè)置 tail 失敗瞳收。
    // 在 enq 方法中處理
    enq(node);
    return node;
}

將自己加入了尾部碉京，并更新了 tail 節(jié)點(diǎn)。

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        // 如果 tail 是 null螟深，就創(chuàng)建一個(gè)虛擬節(jié)點(diǎn)谐宙，同時(shí)指向 head 和 tail，稱為 初始化界弧。
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {// 如果不是 null
            // 和 上個(gè)方法邏輯一樣凡蜻，將新節(jié)點(diǎn)追加到 tail 節(jié)點(diǎn)后面，并更新隊(duì)列的 tail 為新節(jié)點(diǎn)夹纫。
            // 只不過這里是死循環(huán)的咽瓷，失敗了還可以再來(lái) 。
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

enq 方法的邏輯是什么呢舰讹？當(dāng) tail 是 null（沒有初始化隊(duì)列）茅姜，就需要初始化隊(duì)列了。CAS 設(shè)置 tail 失敗月匣，也會(huì)走這里钻洒，需要在 enq 方法中循環(huán)設(shè)置 tail。直到成功锄开。

注意：這里會(huì)創(chuàng)建一個(gè)虛擬節(jié)點(diǎn)素标。

2. 為什么 AQS 需要一個(gè)虛擬 head 節(jié)點(diǎn)

為什么要?jiǎng)?chuàng)建一個(gè)虛擬節(jié)點(diǎn)呢？

事情要從 Node 類的 waitStatus 變量說起萍悴，簡(jiǎn)稱 ws头遭。每個(gè)節(jié)點(diǎn)都有一個(gè) ws 變量寓免，用于這個(gè)節(jié)點(diǎn)狀態(tài)的一些標(biāo)志。初始狀態(tài)是 0计维。如果被取消了袜香，節(jié)點(diǎn)就是 1，那么他就會(huì)被 AQS 清理鲫惶。

還有一個(gè)重要的狀態(tài)：SIGNAL —— -1蜈首，表示：當(dāng)當(dāng)前節(jié)點(diǎn)釋放鎖的時(shí)候，需要喚醒下一個(gè)節(jié)點(diǎn)欠母。

所有欢策，每個(gè)節(jié)點(diǎn)在休眠前，都需要將前置節(jié)點(diǎn)的 ws 設(shè)置成 SIGNAL赏淌。否則自己永遠(yuǎn)無(wú)法被喚醒踩寇。

而為什么需要這么一個(gè) ws 呢？—— 防止重復(fù)操作猜敢。假設(shè)姑荷，當(dāng)一個(gè)節(jié)點(diǎn)已經(jīng)被釋放了盒延，而此時(shí)另一個(gè)線程不知道缩擂，再次釋放。這時(shí)候就錯(cuò)誤了添寺。

所以胯盯，需要一個(gè)變量來(lái)保證這個(gè)節(jié)點(diǎn)的狀態(tài)。而且修改這個(gè)節(jié)點(diǎn)计露，必須通過 CAS 操作保證線程安全博脑。

So，回到我們之前的問題：為什么要?jiǎng)?chuàng)建一個(gè)虛擬節(jié)點(diǎn)呢票罐？

每個(gè)節(jié)點(diǎn)都必須設(shè)置前置節(jié)點(diǎn)的 ws 狀態(tài)為 SIGNAL叉趣，所以必須要一個(gè)前置節(jié)點(diǎn)，而這個(gè)前置節(jié)點(diǎn)该押，實(shí)際上就是當(dāng)前持有鎖的節(jié)點(diǎn)疗杉。

問題在于有個(gè)邊界問題：第一個(gè)節(jié)點(diǎn)怎么辦？他是沒有前置節(jié)點(diǎn)的蚕礼。

那就創(chuàng)建一個(gè)假的烟具。

這就是為什么要?jiǎng)?chuàng)建一個(gè)虛擬節(jié)點(diǎn)的原因。

總結(jié)下來(lái)就是：每個(gè)節(jié)點(diǎn)都需要設(shè)置前置節(jié)點(diǎn)的 ws 狀態(tài)（這個(gè)狀態(tài)為是為了保證數(shù)據(jù)一致性）奠蹬，而第一個(gè)節(jié)點(diǎn)是沒有前置節(jié)點(diǎn)的朝聋，所以需要?jiǎng)?chuàng)建一個(gè)虛擬節(jié)點(diǎn)。

回到我們的 acquireQueued 方法證實(shí)一下：

// 這里返回的節(jié)點(diǎn)是新創(chuàng)建的節(jié)點(diǎn)囤躁，arg 是請(qǐng)求的數(shù)量
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            // 找上一個(gè)節(jié)點(diǎn)
            final Node p = node.predecessor();
            // 如果上一個(gè)節(jié)點(diǎn)是 head 冀痕，就嘗試獲取鎖
            // 如果 獲取成功荔睹，就將當(dāng)前節(jié)點(diǎn)設(shè)置為 head，注意 head 節(jié)點(diǎn)是永遠(yuǎn)不會(huì)喚醒的言蛇。
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // 在獲取鎖失敗后应媚，就需要阻塞了。
            // shouldParkAfterFailedAcquire ---> 檢查上一個(gè)節(jié)點(diǎn)的狀態(tài)猜极，如果是 SIGNAL 就阻塞中姜，否則就改成 SIGNAL。
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

這個(gè)方法有 2 個(gè)邏輯：

如何將自己掛起跟伏？
被喚醒之后做什么丢胚？

先回答第二個(gè)問題：被喚醒之后做什么？

嘗試拿鎖受扳，成功之后携龟，將自己設(shè)置為 head，斷開和 next 的連接勘高。

再看第二個(gè)問題：如何將自己掛起峡蟋？

注意：掛起自己之前，需要將前置節(jié)點(diǎn)的 ws 狀態(tài)設(shè)置成 SIGNAL华望，告訴他：你釋放鎖的時(shí)候記得喚醒我蕊蝗。

具體邏輯在 shouldParkAfterFailedAcquire 方法中：

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    //  如果他的上一個(gè)節(jié)點(diǎn)的 ws 是 SIGNAL，他就需要阻塞赖舟。
    if (ws == Node.SIGNAL)
        // 阻塞
        return true;
    // 前任被取消蓬戚。 跳過前任并重試。
    if (ws > 0) {
        do {
            // 將前任的前任 賦值給 當(dāng)前的前任
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        // 將前任的前任的 next 賦值為 當(dāng)前節(jié)點(diǎn)
        pred.next = node;
    } else { 
        // 如果沒有取消 || 0 || CONDITION || PROPAGATE宾抓，那么就將前任的 ws 設(shè)置成 SIGNAL.
        // 為什么必須是 SIGNAL 呢子漩？
        // 答：希望自己的上一個(gè)節(jié)點(diǎn)在釋放鎖的時(shí)候，通知自己（讓自己獲取鎖）
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    // 重來(lái)
    return false;
}

該方法的主要邏輯就是將前置節(jié)點(diǎn)的狀態(tài)修改成 SIGNAL石洗。其中如果前置節(jié)點(diǎn)被取消了幢泼，就跳過他。

那么肯定讲衫，在前置節(jié)點(diǎn)釋放鎖的時(shí)候缕棵，肯定會(huì)喚醒這個(gè)節(jié)點(diǎn)〗谷耍看看釋放的邏輯吧挥吵。

3. reelase 方法如何釋放鎖

先來(lái)一波代碼:

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        // 所有的節(jié)點(diǎn)在將自己掛起之前，都會(huì)將前置節(jié)點(diǎn)設(shè)置成 SIGNAL花椭，希望前置節(jié)點(diǎn)釋放的時(shí)候忽匈，喚醒自己。
        // 如果前置節(jié)點(diǎn)是 0 矿辽，說明前置節(jié)點(diǎn)已經(jīng)釋放過了丹允。不能重復(fù)釋放了郭厌，后面將會(huì)看到釋放后會(huì)將 ws 修改成0.
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

從這個(gè)方法的判斷就可以看出，head 必須不等于 0雕蔽。為什么呢折柠？當(dāng)一個(gè)節(jié)點(diǎn)嘗試掛起自己之前，都會(huì)將前置節(jié)點(diǎn)設(shè)置成 SIGNAL -1批狐，就算是第一個(gè)加入隊(duì)列的節(jié)點(diǎn)扇售，在獲取鎖失敗后，也會(huì)將虛擬節(jié)點(diǎn)設(shè)置的 ws 設(shè)置成 SIGNAL嚣艇。

而這個(gè)判斷也是防止多線程重復(fù)釋放承冰。

那么肯定，在釋放鎖之后食零，肯定會(huì)將 ws 狀態(tài)設(shè)置成 0困乒。防止重復(fù)操作。

代碼如下：

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        // 將 head 節(jié)點(diǎn)的 ws 改成 0贰谣，清除信號(hào)娜搂。表示，他已經(jīng)釋放過了吱抚。不能重復(fù)釋放百宇。
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    // 如果 next 是 null，或者 next 被取消了频伤。就從 tail 開始向上找節(jié)點(diǎn)恳谎。
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 從尾部開始芝此，向前尋找未被取消的節(jié)點(diǎn)憋肖，直到這個(gè)節(jié)點(diǎn)是 null，或者是 head婚苹。
        // 也就是說岸更，如果 head 的 next 是 null，那么就從尾部開始尋找膊升，直到不是 null 為止怎炊，找到這個(gè) head 就不管了。
        // 如果是 head 的 next 不是 null廓译，但是被取消了评肆，那這個(gè)節(jié)點(diǎn)也會(huì)被略過。
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    // 喚醒 head.next 這個(gè)節(jié)點(diǎn)非区。
    // 通常這個(gè)節(jié)點(diǎn)是 head 的 next瓜挽。
    // 但如果 head.next 被取消了，就會(huì)從尾部開始找征绸。
    if (s != null)
        LockSupport.unpark(s.thread);
}

如果 ws 小于 0久橙，我們假設(shè)是 SIGNAL俄占，就修改成 0. 證實(shí)了我們的想法。

如果他的 next 是 null淆衷，說明 next 取消了缸榄，那么就從尾部開始向上尋找（不從尾部也沒辦法）。當(dāng)然找的過程中祝拯，也跳過了失效的節(jié)點(diǎn)甚带。

最后，喚醒他佳头。

喚醒之后的邏輯是什么樣子的還記得嗎欲低？

復(fù)習(xí)一下：拿鎖，設(shè)置自己為 head畜晰，斷開前任 head 和自己的連接砾莱。

4. 總結(jié)

AQS 使用的 CLH 鎖，需要一個(gè)虛擬 head 節(jié)點(diǎn)凄鼻，這個(gè)節(jié)點(diǎn)的作用是防止重復(fù)釋放鎖腊瑟。當(dāng)?shù)谝粋€(gè)進(jìn)入隊(duì)列的節(jié)點(diǎn)沒有前置節(jié)點(diǎn)的時(shí)候，就會(huì)創(chuàng)建一個(gè)虛擬的块蚌。

來(lái)一幅圖嘗試解釋 AQS 吧：

新增節(jié)點(diǎn)時(shí)

image.png
更新 tail

image.png

喚醒節(jié)點(diǎn)時(shí)闰非，之前的 head 取消了