Java同步框架AQS原文分析

0、引言

自J2SE1.5開始，java中的同步類（Lock，Semphore等等）都基于AbstractQueuedSynchronizer（后文簡稱AQS）。AQS提供了一種原子式管理同步狀態(tài)、阻塞和喚醒線程功能以及隊(duì)列模型的簡單框架。

本文主要是分析此框架的實(shí)現(xiàn)者Doug Lea寫的一篇介紹AQS的論文（→猛戳這里拿原文←），并沒有完全翻譯原文，所以想看原文的在上面拿原文。

1、基本功能

同步器至少要有以下兩種類型的方法acquire和release

  • acquire：至少要有一個操作能實(shí)現(xiàn)對調(diào)用線程的阻塞，直到同步器允許它進(jìn)行操作。
  • release：至少要有一個操作能用一種方式解鎖一個或者更多個已經(jīng)阻塞的線程改變同步狀態(tài)。

同時，同步器還需要支持以下幾種功能：

  • 非阻塞式的同步過程嘗試(tryLock)
  • 可選的超時機(jī)制，可以允許程序放棄等待
  • 可以通過中斷執(zhí)行取消

而為了適應(yīng)不同的同步器，同步器要支持兩種模式

  • 獨(dú)占式exclusive。要保證一次只有一個線程可以經(jīng)過阻塞點(diǎn)
  • 共享式shared?？梢栽试S多個線程阻塞點(diǎn)

2、性能要求

AQS對性能改進(jìn)的關(guān)注點(diǎn)不是主要在于減小空間的開銷和時間的開銷。
原因是：對于開發(fā)者來說，只在需要的時候構(gòu)建同步器，實(shí)在沒有必要為了這部分空間的消耗去壓縮空間。與此同時，同步器大部分情況是用在多線程的情況下，產(chǎn)生一些競爭也是可以想象到的。

AQS的性能重點(diǎn)在于可擴(kuò)展性

AQS的幾個改進(jìn)目標(biāo)：

  1. 可預(yù)見性的保證同步器的效率，甚至在其發(fā)生競爭的情形下。
  2. 減少那些已經(jīng)被允許通過阻塞點(diǎn)的線程但是沒有通過的消耗時間。

對比自旋鎖來說，自旋鎖的響應(yīng)速度很快，但是在線程競爭特別激烈的情況下，由于大量的內(nèi)存讀取，會降低其響應(yīng)的速度。

AQS的框架必須能夠提供一些監(jiān)視和檢查的基本操作，以便用戶發(fā)現(xiàn)和緩解瓶頸。例如：提供一個方式，決定多少個線程會被阻塞。

3、設(shè)計(jì)與實(shí)現(xiàn)

acquire和release操作的偽代碼可以很容易的寫出來如下：

acquire{
    while (同步狀態(tài)不允許獲取) {
        若當(dāng)前線程沒有入隊(duì)，那么就將其入隊(duì)；
        可能會阻塞當(dāng)前線程；
    }
    如果它已經(jīng)入隊(duì)了，就將其出隊(duì)
}

release {
    更新同步狀態(tài)
    if(狀態(tài)表示允許一個阻塞的線程去acquire)
       釋放一個或多個隊(duì)列中的線程
}

3.1、同步狀態(tài)State

AQS采用了int（4個字節(jié)）的變量來持有同步狀態(tài)。使用getState， setState， compareAndSetState方法來進(jìn)行狀態(tài)的獲取和更新。

以上的方法，它們依賴于volatile這個機(jī)制來進(jìn)行讀寫，compare-and-swap機(jī)制去實(shí)現(xiàn)compareAndSetState方法。（CAS操作如果不清楚的可以自行搜索相關(guān)的內(nèi)容）

AQS是一個抽象類，它的tryAcquire和tryRelease方法都需要子類去實(shí)現(xiàn)。兩個方法都支持傳入一個int類型的參數(shù)。這個參數(shù)主要用來實(shí)現(xiàn)不同子類功能的?！纠纭浚簉eentrant lock，當(dāng)在返回一個條件等待后重新去獲取鎖權(quán)限是，它會重新建立一個遞歸計(jì)數(shù)。

3.2、阻塞

AQS沒有采用Thread.suspend和Thread.resume這兩種方式，以上兩種方式都有嚴(yán)重的安全問題，容易造成死鎖等。

AQS采用了java.util.concurrent.locks包下的LockSupport類。該類可以響應(yīng)中斷操作，可以設(shè)置超時時間等。此機(jī)制與Win32內(nèi)的“消費(fèi)事件”機(jī)制，Linux NPTL線程庫的方式類似。

3.3、核心隊(duì)列

AQS框架的核心是阻塞線程的隊(duì)列。也就是一個FIFO（先進(jìn)先出）隊(duì)列。AQS不支持基于優(yōu)先級的同步器。

AQS的鎖策略采用的CLH而不是MCS，原因是CLH要比MCS更適合處理取消和超時。

CLH隊(duì)列的入隊(duì)和出隊(duì)操作是與它的鎖操作息息相關(guān)。它有兩個原子操作更新域，head和taiil。初始化時，將指向一個虛假的節(jié)點(diǎn)。


隊(duì)列格式.png

每個節(jié)點(diǎn)的release狀態(tài)都保存在它的前驅(qū)節(jié)點(diǎn)內(nèi)，while (pred.status != RELEASED);后就可以開始自旋。若持有前驅(qū)節(jié)點(diǎn)的域，CLH鎖可以處理超時和其他形式的取消操作。

AQS對CLH機(jī)制有兩點(diǎn)修改

3.3.1、修改點(diǎn)1：增加后繼節(jié)點(diǎn)訪問域

AQS增加了節(jié)點(diǎn)node訪問其后繼節(jié)點(diǎn)的next域。由于AQS隊(duì)列是雙向隊(duì)列，所以CAS操作也沒有很好的方式對兩個方向都做到完全的原子性更新。后繼結(jié)點(diǎn)的更新就采用了
pred.next = node; 這種方式。
當(dāng)后繼結(jié)點(diǎn)可能出現(xiàn)退出的情形，AQS會通過pred域往前遍歷確定是否是真的退出了。

3.3.2、修改點(diǎn)2：采用狀態(tài)域控制阻塞

CLH采用自旋進(jìn)行線程的阻塞，AQS沒有采用這種方式，而采用之前介紹過的State字段進(jìn)行阻塞。

AQS需要控制在頭節(jié)點(diǎn)調(diào)用tryAcquire方法適合才允許通過，其他情況acquire和block都會失敗。每次只需檢查當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是不是head，這一點(diǎn)減少了CLH對內(nèi)存的讀取競爭，同時還能避免不必要的阻塞和喚醒操作。

【原因】：在調(diào)用park方法前，線程會設(shè)置一個“SIGNAL”信號，然后重新檢查同步狀態(tài)，再確定是否需要再次調(diào)用park方法。

3.3.3、修改點(diǎn)3：利用垃圾回收機(jī)制進(jìn)行節(jié)點(diǎn)存儲管理

AQS主要使用在出隊(duì)的時候置null方式回收節(jié)點(diǎn)內(nèi)存，這可以有效的避免復(fù)雜的處理和瓶頸。

這里我們可以給出更加具體的acquire方法

acquire {
    if (!tryAcquire(arg)) {
        node = 創(chuàng)建隊(duì)列并且新入隊(duì)節(jié)點(diǎn);
        pred = 節(jié)點(diǎn)的有效前驅(qū)節(jié)點(diǎn);
        while (pred 不是頭節(jié)點(diǎn) || !tryAcquire(arg)) {
            if (pred的狀態(tài)位是Signal信號)
                park();
            else
                CAS操作設(shè)置pred的Signal信號;
            pred = node節(jié)點(diǎn)的有效前驅(qū)節(jié)點(diǎn);
        }
        head = node;
    }
}

而release方法也可以得到如下：

release {
    if (tryRelease(arg) && 頭節(jié)點(diǎn)的狀態(tài)是Signal) {
        將頭節(jié)點(diǎn)的狀態(tài)設(shè)置為不是Signal;
        如果頭節(jié)點(diǎn)的后繼結(jié)點(diǎn)存在，則將其喚醒。
    }
}

【時間復(fù)雜度】acquire的循環(huán)次數(shù)由tryAcquire方法的性質(zhì)決定。在不考慮線程等消耗，以及取消操作的情況下，它的時間復(fù)雜度是O(1)。在取消操作的情況下，確認(rèn)前驅(qū)和后繼結(jié)點(diǎn)后重置同步狀態(tài)需要O(n)次遍歷（n為隊(duì)列的長度）。

3.4、條件隊(duì)列

AQS中的ConditionObject提供一個能讓同步器使用的類。它既符合Lock接口，又能持有互斥的同步機(jī)制。

ConditionObject類提供了類似await，signal，signalAll操作的API。這些方法的作用與Object.wait方法是一樣的。ConditionObject使用與同步器同樣的內(nèi)部隊(duì)列，不過與同步器存儲在分開的條件隊(duì)列中。

3.4.1、基本操作流程

基本的await操作如下：

  1. 創(chuàng)建并添加新的節(jié)點(diǎn)到條件隊(duì)列中；
  2. 釋放鎖；
  3. 阻塞直到節(jié)點(diǎn)在鎖隊(duì)列中
  4. 重新獲取鎖。

基本的signal操作如下：

  1. 傳遞條件隊(duì)列的第一個節(jié)點(diǎn)到鎖隊(duì)列中

3.4.2、取消流程

上述基本操作的實(shí)現(xiàn)并不困難，而處理取消，超時和線程的中斷是實(shí)現(xiàn)的難點(diǎn)。

  • 中斷發(fā)生在await操作之前，此方法一定要拋出一個InterruptedException
  • 中斷發(fā)生在await操作之后，此方法不拋出異常，而是系統(tǒng)的中斷狀態(tài)集

條件隊(duì)列需要一個狀態(tài)位，當(dāng)出現(xiàn)Signal信號失敗，就將信號傳遞到隊(duì)列的下一個節(jié)點(diǎn)內(nèi)。而如果出現(xiàn)Cancel信號失敗，就取消傳遞操作，喚醒鎖的重新獲取操作。

4、用法

4.1、控制公平性

AQS并不保證同步器一定是公平的。tryAcquire方法是在入隊(duì)操作前的一個檢驗(yàn)，因此完全可以在入隊(duì)前，“偷取”獲取的權(quán)限。

  • 非公平的FIFO策略（獲取到鎖的順序不一定是隊(duì)列中的順序），將tryAcquire方法中每次進(jìn)入都會進(jìn)行競爭，無論當(dāng)前線程是否是隊(duì)列的頭節(jié)點(diǎn)。只要進(jìn)入的線程速度更快，那么隊(duì)列中的節(jié)點(diǎn)即使解除了阻塞，依然會重新阻塞回去。

  • 公平的FIFO策略，只需要將tryAcquire方法在當(dāng)前線程不是隊(duì)列的頭節(jié)點(diǎn)時放回失敗就行。次之的方式，只需要判斷隊(duì)列是否為空，空隊(duì)列就可以放回tryAcquire成功。

同步器的公平性設(shè)置主要是在多處理器情況下，才能發(fā)揮出其水平。多處理器往往會有更多的競爭，也就更有可能發(fā)生一個線程發(fā)現(xiàn)鎖現(xiàn)在被其他線程需要的情形。

4.2、同步器

  • ReentrantLock
  • ReentrantReadWriteLock
  • Semaphore
  • CountDownLatch
  • FutureTask(1.5以后不再使用AQS)
  • SynchronousQueue

自我總結(jié)

這里開始就不是論文中的內(nèi)容了。AQS的基本理解就在上述的文章中，后面我們再深入到AQS的源碼中看它具體的實(shí)現(xiàn)方式。

AQS的核心內(nèi)容就在于它處理阻塞和非阻塞的方式，如何用隊(duì)列實(shí)現(xiàn)不同功能的同步器，如何控制同步器的性能。

如果你對上述問題還不了解，可以再深入看看原文。

參考文章

  1. Doug Lea. The java.util.concurrent Synchronizer Framework.

如有翻譯不周到的地方，歡迎批評指正！

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容