JDK8原始碼分析——併發庫核心AbstractQueuedSynchronizer的實現思路

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

原創作品未經作者同意嚴禁私自轉載,或私自修改後據為自有。違者將追究法律責任

Ⅰ. AQS簡介

AbstractQueuedSynchronizer是JDK併發包的核心類,大多數併發工具實現如CountDownLatchSemaphoreReentrantLock等等在內部都持有AQS的子類,也就是說它們的功能都是在AQS的基礎上實現的。

這個類由併發專家Doug Lea編寫,關於這個同步器他還寫了一篇專門的文章講述它的設計
The java.util.concurrent Synchronizer Framework

Ⅱ. 基本設計

AQS是以FIFO佇列為基礎的多執行緒同步器。當執行緒未能成功獲得許可時(許可數量用盡)就會加入內部的FIFO佇列中等待,直到有其他執行緒釋放了許可
這個佇列實際上是一個CLH鎖,並且做了些必要的改進以達到以下目標

  1. 處於park狀態的執行緒可以被佇列前驅喚醒
  2. 處理佇列節點中執行緒取消等待的情況
  3. CLH一般用於自旋,而AQS的設計原則是儘可能減少執行緒自旋節約資源

還有很重要的一點,AQS提供了兩種同步模式——獨佔共享獨佔就是一次只能有一個執行緒獲得許可,而共享則是可以有多個執行緒獲得許可。例如WriteLock是獨佔的,ReadLock是共享的

本文只關注於AQS的核心實現,如果讀者在閱讀過程中發現不理解的概念或名詞,還請自行搜尋相關資料。

Ⅲ. FIFO佇列

首先請大家一定明確一個概念:執行緒只會在未能成功獲得許可的情況下才會入佇列,就比如對一個Lock物件作Lock.lock()操作,
如果這個鎖已經被別的執行緒持有了,即許可用完了,那麼當前執行緒才會進入佇列等待。

AQS裡,佇列的節點用內部類Node表示,它的結構如下

    static final class Node {
        volatile int waitStatus;    // 當前節點的狀態
        volatile Node prev;         // 前驅節點
        volatile Node next;         // 後繼節點
        volatile Thread thread;     // 當前等待執行緒
        Node nextWaiter;            // 用於Condition.await()
        
        final Node predecessor() {...}
        final boolean isShared() {...}
    }

下面這張圖展示了多個執行緒等待獲得許可的情況

我們來看看Node類的核心waitStatus欄位,這個欄位表達的含義很豐富,所以很難用寥寥幾句概括它,不同的值反映了AQS不同的行為模式

waitStatus取值表示含義特別說明
1Cancelled當前執行緒已經取消等待N/A
0初始狀態當執行緒新建立一個Node物件時,這個欄位處於起始狀態N/A
-1Signal當前執行緒在取消等待或者獲得許可時,必須對第一個非Cancel狀態的後繼節點執行Unpark操作用於AQS的獨佔模式
-2Condition表示當前執行緒在Condition物件上等待N/A
-3Propagate當前執行緒在取消等待或者獲得許可時,必須將許可還有機會獲得的資訊通知後繼的節點,這個資訊會儘可能地向後”冒泡”用於AQS的共享模式

我們來聊一下什麼是parkunpark,大家都知道Thread.sleep()的作用是讓當前執行緒睡眠,而LockSupport.park()則更進一步,按照它的註釋說明,這個方法的作用是將當前執行緒移出執行緒排程器
也就是說執行了park方法,當前執行緒會立刻停止,不再執行後續程式碼,即使你呼叫interrupt()也無法將其”喚醒”,因為它已經不在執行緒排程器中了。
如果需要讓這個執行緒回到排程器中,需要使用LockSupport.unpark(thread)方法。

現在讓我們忘記這些看不懂的東西吧,跟著我從原始的鎖實現開始,一步步完善它,最後相信你會明白這一節說的是什麼。

Ⅳ. 原始的鎖實現——CLH鎖

我們先從最簡單的鎖實現開始,話不多說,一圖勝千言

節點資料結構如下

    /* 節點結構 */
    class Node {
        Node prev;
        boolean isAvailable;
    }

每個節點的執行緒在等待鎖和釋放鎖時分別執行的程式碼如下

    /* 入隊操作 */
    public void enque(Node node) {
        for (;;) {
            Node t = tail;
            node.prev = t;
            if (CAS(tail, t, node))
                return;
        }
    }
    
    /* 獲取鎖操作 */
    public Node lock() {
        //建立節點插入佇列尾部
        Node node = new Node();
        enque(node);
        
        // 當prev.isAvailable是false時,表示前驅執行緒正在佔用鎖
        while (!node.prev.isAvailable) {
        }
        return node;
    }
    
    /* 釋放鎖操作 */
    public void unlock(Node node) {
        node.isAvailable = true;
    }

結構上,CLH節點與前面的Node節點最大區別在於CLH沒有next引用,只有一個prev前驅引用。
實現上,CLH中每個節點的執行緒都在自旋

這就造成了四個問題

  1. CLH的執行緒都在自旋,浪費了很多CPU資源,並且浪費的程度與佇列中執行緒數量成正比
  2. CLH無法清除無用的節點,不具備伸縮性,在高併發情況下很快就會因為FIFO佇列太長導致OOM
  3. 如果CLH中某個節點的執行緒不想繼續等待,希望退出佇列,以CLH的資料結構無法滿足
  4. CLH的設計只考慮了獨佔模式,即一次只能有一個執行緒獲得許可,無法用於共享模式

其實這些問題的本質都在於CLH沒有提供操作後繼節點的途徑

如果讀者不能理解為什麼會有上面這四個問題,還請配合圖示仔細考察CLH的實現

Ⅴ. 從減少自旋開始

首先要解決的當然是減少浪費CPU的問題了。要做到這個就意味著,執行緒需要使用park操作,而這進一步意味著必須有其他執行緒對其作unpark操作。
根據CLH的實現,這個其他執行緒就是前驅執行緒。所以我們改進節點的資料結構,為每個節點都增加一個next引用,為了能對後繼執行緒執行unpark,還需要一個thread引用

    /* 節點結構 */
    class Node {
        Node prev;
        Node next;
        Thread thread;
        boolean isAvailable;
    }

對應的操作當然也需要改進

    /* 入隊操作 */
    public void enque(Node node) {
        for (;;) {
            Node t = tail;
            node.prev = t;
            if (CAS(tail, t, node)) {
                t.next = node;
                return;
            }
        }
    }
    
    /* 獲取鎖操作 */
    public Node lock() {
        Node node = new Node(Thread.currentThread());
        enque(node);
        
        while (!node.prev.isAvailable)
            LockSupport.park(this);
        return node;
    }
    
    /* 釋放鎖操作 */
    public void unlock(Node node) {
        node.isAvailable = true;
        if (node.next != null)
            LockSupport.unpark(node.next.thread);
    }

用圖說話就是這樣

Ⅵ. GC的吶喊——清除無用的節點

顯而易見,按照上面這張圖的做法,如果處於高併發的環境中,這個佇列分分鐘就要爆炸了。我已經能聽到垃圾收集器在罵我傻X了,額,我承認我是的,因為這樣的設計根本不能用於真實環境。
所以接下來我們要將已經釋放鎖的節點移出佇列,然後把這些節點狠狠塞到垃圾收集器那張讓人憎惡,哦不,可愛的大嘴裡,最好再給他一大耳刮子


大家第一個想到的應該就是雙向連結串列的刪除操作,不過讓人欣慰的是,我們只需要在佇列中的第一個節點上施加刪除操作就可以了,因為不需要考慮併發,程式碼簡單得令人髮指

    /* 清除無用的節點 */
    public void setHead(Node node) {
        head = node;
        node.prev.next = null;
        node.prev = null;
        node.thread = null;
    }

當然釋放鎖的步驟得更新一下

    /* 釋放鎖操作 */
    public void unlock(Node node) {
        node.isAvailable = true;
        setHead(node);
        if (node.next != null)
            LockSupport.unpark(node.next.thread);
    }

配合圖解,味道更佳

Ⅶ. 煩躁!老子不想再等了!

最近有許多執行緒跑到我的辦公室對我破口大罵,就差掀我桌子了。他們一致認為我設計的CLH鎖太特麼爛了,因為他們一旦進佇列了,就必須等到前驅釋放鎖才能繼續他們的工作。
“你個損塞,懂不懂使用者體驗?!” “日他的前驅,拿了鎖啥事不幹,在那死迴圈呢?!都一個小時了,海賊王都完結了還沒好!哪個傻X設計的鎖!”
為了避免長時間等待鎖,執行緒們召開第88屆Thread代表大會,會議上代表們一致認為我需要提供一個可以中途退出等待的機制。
說實話,這個可不是個簡單的任務,但是面對代表們人手一把的40米大刀,我好像沒有第二條路了。


超時等待很好實現,LockSupport.parkNanos()提供了相應的功能,然而超時之後怎麼把自己從佇列中移除是個難題,因為這個時候你得考慮其他節點也會併發退出的情況。
我們先來看這段程式碼

    /* 退出等待 */
    public void cancelAcquire(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
        node.thread = null;
    }

這是個標準的連結串列刪除操作,但是這段程式碼沒法用在併發退出的情形下。因為這四個步驟不是原子的,在步驟間隙沒法確定其他節點會做什麼操作。比如下面這樣,假設A和B兩個節點都要退出等待,那麼就會…


最後我們發現佇列已經被破壞了,上圖只是眾多情況中的一種,想要憑腦力找出所有的潛在併發場景幾乎是不可能的,至少對我來說是這樣,畢竟我的腦袋不太靈光,只能以單核模式緩慢執行。
所以,下面的問題就是,怎樣保證在併發退出的情況下,還能正確保持佇列的完整性。這個時候我的心裡已經開始在嘀咕了:真的存在這樣的方法麼?不行啊怎麼想都沒法做到唉!40米大刀我能跑得過麼?

仔細思考下,想要依靠連結串列刪除操作完成併發退出是不可行的,因為這裡沒有可以利用CAS進行原子隔離的操作空間。
為了能讓併發情況可控,我們需要減少退出操作所涉及的引用,所以我們先嚐試在退出時只操作一個方向的引用,因為佇列末尾的節點next是空,所以我們為了避免null判斷,退出時操作前驅的next引用

    /* 退出等待 */
    public void cancelAcquire(Node node) {
        Node pred = node.prev;
        Node prevNext = pred.next;
        Node next = node.next;
        CASNext(prevNode, prevNext, next);
    }

似乎已經沒法繼續降低退出操作所涉及的引用了,畢竟本質上就是把節點從連結串列中移除,怎麼也得操作到前驅的next引用和當前節點的next引用。
即便是這樣,還是會出現併發下有節點不能正確退出,不過這是顯而易見的結果 —— 每個節點設定前驅next引用的過程都是相互獨立的,根本無法保證先後順序。
所以現在我們可以做一個推理,如果真的存在一個方法能夠實現併發退出,那麼這個方法肯定不能僅靠更改引用,還必須有其他措施來使得節點能識別出已退出的節點。

    /* 退出等待 */
    public void cancelAcquire(Node ndoe) {
        Node pred = node.prev;
        while (pred.status == cancelled)
            node.prev = pred = pred.prev; /* 假設Head的status不為Cancelled */
        Node predNext = pred.next;
        Node next = node.next;
        
        node.status = Cancelled;
        
        if (pred.status != Cancelled) {
            if (next == null || next.status != Cancelled)
                CASNext(pred, predNext, next); /* 假設這步失敗了,說明有後續節點搶先完成了退出,這時候本節點已經被跳過了 */
        }
        node.next = null;
        node.thread = null;
    }

這個方法很有意思,它在node.status = Cancelled之後,作了一個雙向檢查,這樣就可以保證,相鄰兩個節點併發退出時,到node.status = Cancelled程式碼之後,其中一個必然能檢測到另一個處於Cancelled狀態。再仔細分析,我們驚喜地發現,這個方法保證了連續的一串節點併發退出時,必定能有

1. 全部節點`status = Cancelled`
2. 在下次後續節點退出時,會直接跳過`status = Cancelled`節點

不過這裡就有個問題,非Cancelled節點的next引用可能指向了一個處於Cancelled的無用節點,unpark操作就無法對正確的等待執行緒施行。
所以需要一個方法從Tail向前尋找離當前節點最近的非Cancelled節點

    /* unpark非退出後繼執行緒 */
    public void unparkSuccessor(Node node) {
        Node next = node.next;
        if (next == null || next.status == Cancelled) {
            next = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.status != Cancelled)
                    next = t;
        }
        if (next != null)
            LockSupport.unpark(next);
    }

Ⅷ. 累了,不更了

以上就是AQS獨佔模式的基本實現思路,當然我應該對第四個問題,怎麼實現共享模式進行分析,不過基於以下幾個原因

1. 高Sir我累了
2. Gao sir is tired
3. 共享模式的基本思路跟獨佔是一樣的

加上這篇文章在草稿箱也快兩個禮拜了,我也不想再畫圖了,就這樣發表吧,大家好好閱讀原始碼,很多細節我都省略了,有問題評論下方交流。

相關文章

開發語言 最新文章