摘要

在J2SE 1.5的java.util.concurrent包（下稱j.u.c包）中，大部分的同步器（例如鎖，屏障等等）都是基于AbstractQueuedSynchronizer類（下稱AQS類），這個簡單的框架而構(gòu)建的。這個框架為同步狀態(tài)的原子性管理、線程的阻塞和解除阻塞以及排隊提供了一種通用的機制。這篇論文主要描述了這個框架基本原理、設(shè)計、實現(xiàn)、用法以及性能。

1. 背景介紹

通過JCP的JSR166規(guī)范，Java的1.5版本引入了j.u.c包，這個包提供了一系列支持中等程度并發(fā)的類。這些組件是一系列的同步器（抽象數(shù)據(jù)類型(ADT)）。這些同步器主要維護著以下幾個功能：內(nèi)部同步狀態(tài)的管理(例如：表示一個鎖的狀態(tài)是獲取還是釋放)，同步狀態(tài)的更新和檢查操作，且至少有一個方法會導(dǎo)致調(diào)用線程在同步狀態(tài)被獲取時阻塞，以及在其他線程改變這個同步狀態(tài)時解除線程的阻塞。上述的這些的實際例子包括：互斥排它鎖的不同形式、讀寫鎖、信號量、屏障、Future、事件指示器以及傳送隊列等。

幾乎任一同步器都可以用來實現(xiàn)其他形式的同步器。例如，可以用可重入鎖實現(xiàn)信號量或者用信號量實現(xiàn)可重入鎖。但是，這樣做帶來的復(fù)雜性，開銷，不靈活使其至多只能是個二流工程。且缺乏吸引力。如果任何這樣的構(gòu)造方式不能在本質(zhì)上比其他形式更簡潔，那么開發(fā)者就不應(yīng)該隨意地選擇其中的某個來構(gòu)建另一個同步器。取而代之，JSR166建立了一個小框架，AQS類。這個框架為構(gòu)造同步器提供一種通用的機制，并且被j.u.c包中大部分類使用，同時很多用戶也用它來定義自己的同步器。

在這篇論文的下面部分會討論這個框架的需求、設(shè)計與實現(xiàn)背后的主要思路、示例用法，以及性能指標的一些測量。

2 需求

2.1 功能

同步器一般包含兩種方法，一種是acquire，另一種是release。acquire操作阻塞調(diào)用的線程，直到或除非同步狀態(tài)允許其繼續(xù)執(zhí)行。而release操作則是通過某種方式改變同步狀態(tài)，使得一或多個被acquire阻塞的線程繼續(xù)執(zhí)行。

j.u.c包中并沒有對同步器的API做一個統(tǒng)一的定義。因此，有一些類定義了通用的接口（如Lock），而另外一些則定義了其專有的版本。因此在不同的類中，acquire和release操作的名字和形式會各有不同。例如：Lock.lock，Semaphore.acquire，CountDownLatch.await和FutureTask.get，在這個框架里，這些方法都是acquire操作。但是，J.U.C為支持一系列常見的使用選項，在類間都有個一致約定。在有意義的情況下，每一個同步器都支持下面的操作：

• 阻塞和非阻塞（例如tryLock）同步。
• 可選的超時設(shè)置，讓調(diào)用者可以放棄等待
• 通過中斷實現(xiàn)的任務(wù)取消，通常是分為兩個版本，一個acquire可取消，而另一個不可以。

同步器的實現(xiàn)根據(jù)其狀態(tài)是否獨占而有所不同。獨占狀態(tài)的同步器，在同一時間只有一個線程可以通過阻塞點，而共享狀態(tài)的同步器可以同時有多個線程在執(zhí)行。一般鎖的實現(xiàn)類往往只維護獨占狀態(tài)，但是，例如計數(shù)信號量在數(shù)量許可的情況下，允許多個線程同時執(zhí)行。為了使框架能得到廣泛應(yīng)用，這兩種模式都要支持。

j.u.c包里還定義了Condition接口，用于支持監(jiān)控形式的await/signal操作，這些操作與獨占模式的Lock類有關(guān)，且Condition的實現(xiàn)天生就和與其關(guān)聯(lián)的Lock類緊密相關(guān)。

2.2 性能目標

Java內(nèi)置鎖（使用synchronized的方法或代碼塊）的性能問題一直以來都在被人們關(guān)注，并且已經(jīng)有一系列的文章描述其構(gòu)造（例如引文[1],[3]）。然而，大部分的研究主要關(guān)注的是在單核處理器上大部分時候使用于單線程上下文環(huán)境中時，如何盡量降低其空間（因為任何的Java對象都可以當(dāng)成是鎖）和時間的開銷。對于同步器來說這些都不是特別重要：程序員僅在需要的時候才會使用同步器，因此并不需要壓縮空間來避免浪費，并且同步器幾乎是專門用在多線程設(shè)計中（特別是在多核處理器上），在這種環(huán)境下，偶爾的競爭是在意料之中的。因此，常規(guī)的JVM鎖優(yōu)化策略主要是針對零競爭的場景，而其它場景則使用缺乏可預(yù)見性的“慢速路徑（slow paths）” ，所以常規(guī)的JVM鎖優(yōu)化策略并不適用于嚴重依賴于J.U.C包的典型多線程服務(wù)端應(yīng)用。

這里主要的性能目標是可伸縮性，即在大部分情況下，即使，或特別在同步器有競爭的情況下，穩(wěn)定地保證其效率。在理想的情況下，不管有多少線程正試圖通過同步點，通過同步點的開銷都應(yīng)該是個常量。在某一線程被允許通過同步點但還沒有通過的情況下，使其耗費的總時間最少，這是主要目標之一。然而，這也必須考慮平衡各種資源，包括總CPU時間的需求，內(nèi)存負載以及線程調(diào)度的開銷。例如：獲取自旋鎖通常比阻塞鎖所需的時間更短，但是通常也會浪費CPU時鐘周期，并且造成內(nèi)存競爭，所以使用的并不頻繁。

實現(xiàn)同步器的這些目標包含了兩種不同的使用類型。大部分應(yīng)用程序是最大化其總的吞吐量，容錯性，并且最好保證盡量減少饑餓的情況。然而，對于那些控制資源分配的程序來說，更重要是去維持多線程讀取的公平性，可以接受較差的總吞吐量。沒有任何框架可以代表用戶去決定應(yīng)該選擇哪一個方式，因此，應(yīng)該提供不同的公平策略。

無論同步器的內(nèi)部實現(xiàn)是多么的精雕細琢，它還是會在某些應(yīng)用中產(chǎn)生性能瓶頸。因此，框架必須提供相應(yīng)的監(jiān)視工具讓用戶發(fā)現(xiàn)和緩和這些瓶頸。至少需要提供一種方式來確定有多少線程被阻塞了。

3 設(shè)計與實現(xiàn)

同步器背后的基本思想非常簡單。

acquire操作如下：

while (synchronization state does not allow acquire) {
    enqueue current thread if not already queued;
    possibly block current thread;
}
dequeue current thread if it was queued;

release操作如下：

update synchronization state;
if (state may permit a blocked thread to acquire)
    unblock one or more queued threads;

為了實現(xiàn)上述操作，需要下面三個基本組件的相互協(xié)作：

• 同步狀態(tài)的原子性管理；
• 線程的阻塞與解除阻塞；
• 隊列的管理；

創(chuàng)建一個框架分別實現(xiàn)這三個組件是有可能的。但是，這會讓整個框架既難用又沒效率。例如：存儲在隊列節(jié)點的信息必須與解除阻塞所需要的信息一致，而暴露出的方法的簽名必須依賴于同步狀態(tài)的特性。

同步器框架的核心決策是為這三個組件選擇一個具體實現(xiàn)，同時在使用方式上又有大量選項可用。這里有意地限制了其適用范圍，但是提供了足夠的效率，使得實際上沒有理由在合適的情況下不用這個框架而去重新建造一個。

3.1 同步狀態(tài)

AQS類使用單個int（32位）來保存同步狀態(tài)，并暴露出getState、setState以及compareAndSet操作來讀取和更新這個狀態(tài)。這些方法都依賴于j.u.c.atomic包的支持，這個包提供了兼容JSR133中volatile在讀和寫上的語義，并且通過使用本地的compare-and-swap或load-linked/store-conditional指令來實現(xiàn)compareAndSetState，使得僅當(dāng)同步狀態(tài)擁有一個期望值的時候，才會被原子地設(shè)置成新值。

將同步狀態(tài)限制為一個32位的整形是出于實踐上的考量。雖然JSR166也提供了64位long字段的原子性操作，但這些操作在很多平臺上還是使用內(nèi)部鎖的方式來模擬實現(xiàn)的，這會使同步器的性能可能不會很理想。當(dāng)然，將來可能會有一個類是專門使用64位的狀態(tài)的。然而現(xiàn)在就引入這么一個類到這個包里并不是一個很好的決定

（譯者注：

JDK1.6中已經(jīng)包含java.util.concurrent.locks.AbstractQueuedLongSynchronizer類

即使用 long 形式維護同步狀態(tài)的一個 AbstractQueuedSynchronizer 版本）。目前來說，32位的狀態(tài)對大多數(shù)應(yīng)用程序都是足夠的。在j.u.c包中，只有一個同步器類可能需要多于32位來維持狀態(tài)，那就是CyclicBarrier類，所以，它用了鎖（該包中大多數(shù)更高層次的工具亦是如此）。

基于AQS的具體實現(xiàn)類必須根據(jù)暴露出的狀態(tài)相關(guān)的方法定義tryAcquire和tryRelease方法，以控制acquire和release操作。當(dāng)同步狀態(tài)滿足時，tryAcquire方法必須返回true，而當(dāng)新的同步狀態(tài)允許后續(xù)acquire時，tryRelease方法也必須返回true。這些方法都接受一個int類型的參數(shù)用于傳遞想要的狀態(tài)。例如：可重入鎖中，當(dāng)某個線程從條件等待中返回，然后重新獲取鎖時，為了重新建立循環(huán)計數(shù)的場景。很多同步器并不需要這樣一個參數(shù)，因此忽略它即可。

3.2 阻塞

在JSR166之前，阻塞線程和解除線程阻塞都是基于Java內(nèi)置監(jiān)視器，沒有基于Java API可以用來創(chuàng)建同步器。唯一可以選擇的是Thread.suspend和Thread.resume，但是它們都有無法解決的競態(tài)問題，所以也沒法用：當(dāng)一個非阻塞的線程在一個正準備阻塞的線程調(diào)用suspend前調(diào)用了resume，這個resume操作將不會有什么效果。

j.u.c包有一個LockSuport類，這個類中包含了解決這個問題的方法。方法LockSupport.park阻塞當(dāng)前線程除非/直到有個LockSupport.unpark方法被調(diào)用（unpark方法被提前調(diào)用也是可以的）。unpark的調(diào)用是沒有被計數(shù)的，因此在一個park調(diào)用前多次調(diào)用unpark方法只會解除一個park操作。另外，它們作用于每個線程而不是每個同步器。一個線程在一個新的同步器上調(diào)用park操作可能會立即返回，因為在此之前可能有“剩余的”unpark操作。但是，在缺少一個unpark操作時，下一次調(diào)用park就會阻塞。雖然可以顯式地消除這個狀態(tài)（譯者注：就是多余的unpark調(diào)用），但并不值得這樣做。在需要的時候多次調(diào)用park會更高效。

這個簡單的機制與有些用法在某種程度上是相似的，例如Solaris-9的線程庫，WIN32中的“可消費事件”，以及Linux中的NPTL線程庫。因此最常見的運行Java的平臺上都有相對應(yīng)的有效實現(xiàn)。（但目前Solaris和Linux上的Sun Hotspot JVM參考實現(xiàn)實際上是使用一個pthread的condvar來適應(yīng)目前的運行時設(shè)計的）。park方法同樣支持可選的相對或絕對的超時設(shè)置，以及與JVM的Thread.interrupt結(jié)合 ，可通過中斷來unpark一個線程。

3.3 隊列

整個框架的關(guān)鍵就是如何管理被阻塞的線程的隊列，該隊列是嚴格的FIFO隊列，因此，框架不支持基于優(yōu)先級的同步。

同步隊列的最佳選擇是自身沒有使用底層鎖來構(gòu)造的非阻塞數(shù)據(jù)結(jié)構(gòu)，目前，業(yè)界對此很少有爭議。而其中主要有兩個選擇：一個是Mellor-Crummey和Scott鎖（MCS鎖）[9]的變體，另一個是Craig，Landin和Hagersten鎖（CLH鎖）[5][8][10]的變體。一直以來，CLH鎖僅被用于自旋鎖。但是，在這個框架中，CLH鎖顯然比MCS鎖更合適。因為CLH鎖可以更容易地去實現(xiàn)“取消（cancellation）”和“超時”功能，因此我們選擇了CLH鎖作為實現(xiàn)的基礎(chǔ)。但是最終的設(shè)計已經(jīng)與原來的CLH鎖有較大的出入，因此下文將對此做出解釋。

CLH隊列實際上并不那么像隊列，因為它的入隊和出隊操作都與它的用途（即用作鎖）緊密相關(guān)。它是一個鏈表隊列，通過兩個字段head和tail來存取，這兩個字段是可原子更新的，兩者在初始化時都指向了一個空節(jié)點。

一個新的節(jié)點，node，通過一個原子操作入隊：

do {
    pred = tail;
} while(!tail.compareAndSet(pred, node));

每一個節(jié)點的“釋放”狀態(tài)都保存在其前驅(qū)節(jié)點中。因此，自旋鎖的“自旋”操作就如下：

while (pred.status != RELEASED); // spin

自旋后的出隊操作只需將head字段指向剛剛得到鎖的節(jié)點：

	head = node;

CLH鎖的優(yōu)點在于其入隊和出隊操作是快速、無鎖的，以及無障礙的（即使在競爭下，某個線程總會贏得一次插入機會而能繼續(xù)執(zhí)行）；且探測是否有線程正在等待也很快（只要測試一下head是否與tail相等）；同時，“釋放”狀態(tài)是分散的（譯者注：幾乎每個節(jié)點都保存了這個狀態(tài)，當(dāng)前節(jié)點保存了其后驅(qū)節(jié)點的“釋放”狀態(tài)，因此它們是分散的，不是集中于一塊的。），避免了一些不必要的內(nèi)存競爭。

在原始版本的CLH鎖中，節(jié)點間甚至都沒有互相鏈接。自旋鎖中，pred變量可以是一個局部變量。然而，Scott和Scherer證明了通過在節(jié)點中顯式地維護前驅(qū)節(jié)點，CLH鎖就可以處理“超時”和各種形式的“取消”：如果一個節(jié)點的前驅(qū)節(jié)點取消了，這個節(jié)點就可以滑動去使用前面一個節(jié)點的狀態(tài)字段。

為了將CLH隊列用于阻塞式同步器，需要做些額外的修改以提供一種高效的方式定位某個節(jié)點的后繼節(jié)點。在自旋鎖中，一個節(jié)點只需要改變其狀態(tài)，下一次自旋中其后繼節(jié)點就能注意到這個改變，所以節(jié)點間的鏈接并不是必須的。但在阻塞式同步器中，一個節(jié)點需要顯式地喚醒（unpark）其后繼節(jié)點。

AQS隊列的節(jié)點包含一個next鏈接到它的后繼節(jié)點。但是，由于沒有針對雙向鏈表節(jié)點的類似compareAndSet的原子性無鎖插入指令，因此這個next鏈接的設(shè)置并非作為原子性插入操作的一部分，而僅是在節(jié)點被插入后簡單地賦值：

pred.next = node;

next鏈接僅是一種優(yōu)化。如果通過某個節(jié)點的next字段發(fā)現(xiàn)其后繼結(jié)點不存在（或看似被取消了），總是可以使用pred字段從尾部開始向前遍歷來檢查是否真的有后續(xù)節(jié)點。

第二個對CLH隊列主要的修改是將每個節(jié)點都有的狀態(tài)字段用于控制阻塞而非自旋。在同步器框架中，僅在線程調(diào)用具體子類中的tryAcquire方法返回true時，隊列中的線程才能從acquire操作中返回；而單個“released”位是不夠的。但仍然需要做些控制以確保當(dāng)一個活動的線程位于隊列頭部時，僅允許其調(diào)用tryAcquire；這時的acquire可能會失敗，然后（重新）阻塞。這種情況不需要讀取狀態(tài)標識，因為可以通過檢查當(dāng)前節(jié)點的前驅(qū)是否為head來確定權(quán)限。與自旋鎖不同，讀取head以保證復(fù)制時不會有太多的內(nèi)存競爭（ there is not enough memory contention reading head to warrant replication.）。然而，“取消”狀態(tài)必須存在于狀態(tài)字段中。

隊列節(jié)點的狀態(tài)字段也用于避免沒有必要的park和unpark調(diào)用。雖然這些方法跟阻塞原語一樣快，但在跨越Java和JVM runtime以及操作系統(tǒng)邊界時仍有可避免的開銷。在調(diào)用park前，線程設(shè)置一個“喚醒（signal me）”位，然后再一次檢查同步和節(jié)點狀態(tài)。一個釋放的線程會清空其自身狀態(tài)。這樣線程就不必頻繁地嘗試阻塞，特別是在鎖相關(guān)的類中，這樣會浪費時間等待下一個符合條件的線程去申請鎖，從而加劇其它競爭的影響。除非后繼節(jié)點設(shè)置了“喚醒”位（譯者注：源碼中為-1），否則這也可避免正在release的線程去判斷其后繼節(jié)點。這反過來也消除了這些情形：除非“喚醒”與“取消”同時發(fā)生，否則必須遍歷多個節(jié)點來處理一個似乎為null的next字段。

同步框架中使用的CLH鎖的變體與其他語言中的相比，主要區(qū)別可能是同步框架中使用的CLH鎖需要依賴垃圾回收管理節(jié)點的內(nèi)存，這就避免了一些復(fù)雜性和開銷。但是，即使依賴GC也仍然需要在確定鏈接字段不再需要時將其置為null。這往往可以與出隊操作一起完成。否則，無用的節(jié)點仍然可觸及，它們就沒法被回收。

其它一些更深入的微調(diào)，包括CLH隊列首次遇到競爭時才需要的初始空節(jié)點的延遲初始化等，都可以在J2SE1.5的版本的源代碼文檔中找到相應(yīng)的描述。

拋開這些細節(jié)，基本的acquire操作的最終實現(xiàn)的一般形式如下（互斥，非中斷，無超時）：

if(!tryAcquire(arg)) {
    node = create and enqueue new node;
    pred = node's effective predecessor;
    while (pred is not head node || !tryAcquire(arg)) {
        if (pred's signal bit is set)
            pard()
        else
            compareAndSet pred's signal bit to true;
        pred = node's effective predecessor;
    }
    head = node;
}

release操作：

if(tryRelease(arg) && head node's signal bit is set) {
    compareAndSet head's bit to false;
    unpark head's successor, if one exist
}

acquire操作的主循環(huán)次數(shù)依賴于具體實現(xiàn)類中tryAcquire的實現(xiàn)方式。另一方面，在沒有“取消”操作的情況下，每一個組件的acquire和release都是一個O(1)的操作，忽略park中發(fā)生的所有操作系統(tǒng)線程調(diào)度。

支持“取消”操作主要是要在acquire循環(huán)里的park返回時檢查中斷或超時。由超時或中斷而被取消等待的線程會設(shè)置其節(jié)點狀態(tài)，然后unpark其后繼節(jié)點。在有“取消”的情況下，判斷其前驅(qū)節(jié)點和后繼節(jié)點以及重置狀態(tài)可能需要O(n)的遍歷（n是隊列的長度）。由于“取消”操作，該線程再也不會被阻塞，節(jié)點的鏈接和狀態(tài)字段可以被快速重建。

3.4 條件隊列

AQS框架提供了一個ConditionObject類，給維護獨占同步的類以及實現(xiàn)Lock接口的類使用。一個鎖對象可以關(guān)聯(lián)任意數(shù)目的條件對象，可以提供典型的管程風(fēng)格的await、signal和signalAll操作，包括帶有超時的，以及一些檢測、監(jiān)控的方法。

通過修正一些設(shè)計決策，ConditionObject類有效地將條件（conditions）與其它同步操作結(jié)合到了一起。該類只支持Java風(fēng)格的管程訪問規(guī)則，這些規(guī)則中，僅當(dāng)當(dāng)前線程持有鎖且要操作的條件（condition）屬于該鎖時，條件操作才是合法的（一些替代操作的討論參考[4]）。這樣，一個ConditionObject關(guān)聯(lián)到一個ReentrantLock上就表現(xiàn)的跟內(nèi)置的管程（通過Object.wait等）一樣了。兩者的不同僅僅在于方法的名稱、額外的功能以及用戶可以為每個鎖聲明多個條件。

ConditionObject使用了與同步器一樣的內(nèi)部隊列節(jié)點。但是，是在一個單獨的條件隊列中維護這些節(jié)點的。signal操作是通過將節(jié)點從條件隊列轉(zhuǎn)移到鎖隊列中來實現(xiàn)的，而沒有必要在需要喚醒的線程重新獲取到鎖之前將其喚醒。

基本的await操作如下：

create and add new node to conditon queue;
release lock;
block until node is on lock queue;
re-acquire lock;

signal操作如下：

transfer the first node from condition queue to lock queue;

因為只有在持有鎖的時候才能執(zhí)行這些操作，因此他們可以使用順序鏈表隊列操作來維護條件隊列（在節(jié)點中用一個nextWaiter字段）。轉(zhuǎn)移操作僅僅把第一個節(jié)點從條件隊列中的鏈接解除，然后通過CLH插入操作將其插入到鎖隊列上。

實現(xiàn)這些操作主要復(fù)雜在，因超時或Thread.interrupt導(dǎo)致取消了條件等待時，該如何處理。“取消”和“喚醒”幾乎同時發(fā)生就會有競態(tài)問題，最終的結(jié)果遵照內(nèi)置管程相關(guān)的規(guī)范。JSR133修訂以后，就要求如果中斷發(fā)生在signal操作之前，await方法必須在重新獲取到鎖后，拋出InterruptedException。但是，如果中斷發(fā)生在signal后，await必須返回且不拋異常，同時設(shè)置線程的中斷狀態(tài)。

為了維護適當(dāng)?shù)捻樞?，隊列?jié)點狀態(tài)變量中的一個位記錄了該節(jié)點是否已經(jīng)（或正在）被轉(zhuǎn)移。“喚醒”和“取消”相關(guān)的代碼都會嘗試用compareAndSet修改這個狀態(tài)。如果某次signal操作修改失敗，就會轉(zhuǎn)移隊列中的下一個節(jié)點（如果存在的話）。如果某次“取消”操作修改失敗，就必須中止此次轉(zhuǎn)移，然后等待重新獲得鎖。后面的情況采用了一個潛在的無限的自旋等待。在節(jié)點成功的被插到鎖隊列之前，被“取消”的等待不能重新獲得鎖，所以必須自旋等待CLH隊列插入（即compareAndSet操作）被“喚醒”線程成功執(zhí)行。這里極少需要自旋，且自旋里使用Thread.yield來提示應(yīng)該調(diào)度某一其它線程，理想情況下就是執(zhí)行signal的那個線程。雖然有可能在這里為“取消”實現(xiàn)一個幫助策略以幫助插入節(jié)點，但這種情況實在太少，找不到合適的理由來增加這些開銷。在其它所有的情況下，這個基本的機制都不需要自旋或yield，因此在單處理器上保持著合理的性能。

4 用法

AQS類將上述的功能結(jié)合到一起，并且作為一種基于“模版方法模式”[6]的基類提供給同步器。子類只需定義狀態(tài)的檢查與更新相關(guān)的方法，這些方法控制著acquire和 release操作。然而，將AQS的子類作為同步器ADT并不適合，因為這個類必須提供方法在內(nèi)部控制acquire和release的規(guī)則，這些都不應(yīng)該被用戶所看到。所有java.util.concurrent包中的同步器類都聲明了一個私有的繼承了AbstractQueuedSynchronizer的內(nèi)部類，并且把所有同步方法都委托給這個內(nèi)部類。這樣各個同步器類的公開方法就可以使用適合自己的名稱。

下面是一個最簡單的Mutex類的實現(xiàn)，它使用同步狀態(tài)0表示解鎖，1表示鎖定。這個類并不需要同步方法中的參數(shù)，因此這里在調(diào)用的時候使用0作為實參，方法實現(xiàn)里將其忽略。

class Mutex {
    class Sync extends AbstractQueuedSynchronizer {
        public boolean tryAcquire(int ignore) {
            return compareAndSetState(0, 1);
        }
        public boolean tryRelease(int ignore) {
            setState(0); return true;
        }
    }
    private final Sync sync = new Sync();
    public void lock() { sync.acquire(0); }
    public void unlock() { sync.release(0); }
}

這個例子的一個更完整的版本，以及其它用法指南，可以在J2SE的文檔中找到。還可以有一些變體。如，tryAcquire可以使用一種“test-and-test-and-set”策略，即在改變狀態(tài)值前先對狀態(tài)進行校驗。

令人詫異的是，像互斥鎖這樣性能敏感的東西也打算通過委托和虛方法結(jié)合的方式來定義。然而，這正是現(xiàn)代動態(tài)編譯器一直在重點研究的面向?qū)ο笤O(shè)計結(jié)構(gòu)。編譯器擅長將這方面的開銷優(yōu)化掉，起碼會優(yōu)化頻繁調(diào)用同步器的那些代碼。

AbstractQueuedSynchronizer類也提供了一些方法用來協(xié)助策略控制。例如，基礎(chǔ)的acquire方法有可超時和可中斷的版本。雖然到目前為止，我們的討論都集中在像鎖這樣的獨占模式的同步器上，但AbstractQueuedSynchronizer類也包含另一組方法（如acquireShared），它們的不同點在于tryAcquireShared和tryReleaseShared方法能夠告知框架（通過它們的返回值）尚能接受更多的請求，最終框架會通過級聯(lián)的signal(cascading signals)喚醒多個線程。

雖然將同步器序列化（持久化存儲或傳輸）一般來說沒有太大意義，但這些類經(jīng)常會被用于構(gòu)造其它類，例如線程安全的集合，而這些集合通常是可序列化的。AbstractQueuedSynchronizer和ConditionObject類都提供了方法用于序列化同步狀態(tài)，但不會序列化潛在的被阻塞的線程，也不會序列化其它內(nèi)部暫時性的簿記（bookkeeping）變量。即使如此，在反序列化時，大部分同步器類也只僅將同步狀態(tài)重置為初始值，這與內(nèi)置鎖的隱式策略一致 —— 總是反序列化到一個解鎖狀態(tài)。這相當(dāng)于一個空操作，但仍必須顯式地支持以便final字段能夠反序列化。

4.1 公平調(diào)度的控制

盡管同步器是基于FIFO隊列的，但它們并不一定就得是公平的?？梢宰⒁獾?，在基礎(chǔ)的acquire算法（3.3節(jié)）中，tryAcquire是在入隊前被執(zhí)行的。因此一個新的acquire線程能夠“竊取”本該屬于隊列頭部第一個線程通過同步器的機會。

可闖入的FIFO策略通常會提供比其它技術(shù)更高的總吞吐率。當(dāng)一個有競爭的鎖已經(jīng)空閑，而下一個準備獲取鎖的線程又正在解除阻塞的過程中，這時就沒有線程可以獲取到這個鎖，如果使用闖入策略，則可減少這之間的時間間隔。與此同時，這種策略還可避免過分的，無效率的競爭，這種競爭是由于只允許一個（第一個）排隊的線程被喚醒然后嘗試acquire操作導(dǎo)致的。在只要求短時間持有同步器的場景中，創(chuàng)建同步器的開發(fā)者可以通過定義tryAcquire在控制權(quán)返回之前重復(fù)調(diào)用自己若干次，來進一步凸顯闖入的效果。

可闖入的FIFO同步器只有概率性的公平屬性。鎖隊列頭部一個解除了阻塞的線程擁有一次無偏向的機會（譯者注：即不會偏向隊頭的線程也不會偏向闖入的線程）來贏得與闖入的線程之間的競爭，如果競爭失敗，要么重新阻塞要么進行重試。然而，如果闖入的線程到達的速度比隊頭的線程解除阻塞快，那么在隊列中的第一個線程將很難贏得競爭，以至于幾乎總要重新阻塞，并且它的后繼節(jié)點也會一直保持阻塞。對于短暫持有的同步器來說，在隊列中第一個線程被解除阻塞期間，多處理器上很可能發(fā)生過多次闖入（譯者注：即闖入的線程的acquire操作）和release了。正如下文所提到的，最終結(jié)果就是保持一或多個線程的高進展速度的同時，仍至少在一定概率上避免了饑餓的發(fā)生。

當(dāng)有更高的公平性需求時，實現(xiàn)起來也很簡單。如果需要嚴格的公平性，程序員可以把tryAcquire方法定義為，若當(dāng)前線程不是隊列的頭節(jié)點（可通過getFirstQueuedThread方法檢查，這是框架提供的為數(shù)不多的幾個檢測方法之一），則立即失敗（返回false）。

一個更快，但非嚴格公平的變體可以這樣做，若隊列為空（判斷的瞬間），仍然允許tryAcquire執(zhí)行成功。在這種情況下，多個線程同時遇到一個空隊列時可能會去競爭以使自己第一個獲得鎖，這樣，通常至少有一個線程是無需入隊列的。java.util.concurrent包中所有支持公平模式的同步器都采用了這種策略。

盡管公平性設(shè)置在實踐中很有用，但是它們并沒有保障，因為Java Language Specification沒有提供這樣的調(diào)度保證。例如：即使是嚴格公平的同步器，如果一組線程永遠不需要阻塞來達到互相等待，那么JVM可能會決定純粹以順序方式運行它們。在實際中，單處理器上，在搶占式上下文切換之前，這樣的線程有可能是各自運行了一段時間。如果這樣一個線程正持有某個互斥鎖，它將很快會被切換回來，僅是為了釋放其持有的鎖，然后會繼續(xù)阻塞，因為它知道有另外一個線程需要這把鎖，這更增加了同步器可用但沒有線程能來獲取之間的間隔。同步器公平性設(shè)置在多處理器上的影響可能會更大，因為在這種環(huán)境下會產(chǎn)生更多的交錯，因此一個線程就會有更多的機會發(fā)現(xiàn)鎖被另一個線程請求。

在高競爭下，當(dāng)保護的是短暫持有鎖的代碼體時，盡管性能可能會較差，但公平鎖仍然能有效地工作。例如，當(dāng)公平性鎖保護的是相對長的代碼體和/或有著相對長的鎖間(inter-lock)間隔，在這種情況下，闖入只能帶來很小的性能優(yōu)勢，但卻可能會大大增加無限等待的風(fēng)險。同步器框架將這些工程決策留給用戶來確定。

4.2 同步器

下面是java.util.concurrent包中同步器定義方式的概述：

ReentrantLock類使用AQS同步狀態(tài)來保存鎖（重復(fù)）持有的次數(shù)。當(dāng)鎖被一個線程獲取時，ReentrantLock也會記錄下當(dāng)前獲得鎖的線程標識，以便檢查是否是重復(fù)獲取，以及當(dāng)錯誤的線程（譯者注：如果線程不是鎖的持有者，在此線程中執(zhí)行該鎖的unlock操作就是非法的）試圖進行解鎖操作時檢測是否存在非法狀態(tài)異常。ReentrantLock也使用了AQS提供的ConditionObject，還向外暴露了其它監(jiān)控和監(jiān)測相關(guān)的方法。ReentrantLock通過在內(nèi)部聲明兩個不同的AbstractQueuedSynchronizer實現(xiàn)類（提供公平模式的那個禁用了闖入策略）來實現(xiàn)可選的公平模式，在創(chuàng)建ReentrantLock實例的時候根據(jù)設(shè)置（譯者注：即ReentrantLock構(gòu)造方法中的fair參數(shù)）使用相應(yīng)的AbstractQueuedSynchronizer實現(xiàn)類。

ReentrantReadWriteLock類使用AQS同步狀態(tài)中的16位來保存寫鎖持有的次數(shù)，剩下的16位用來保存讀鎖的持有次數(shù)。WriteLock的構(gòu)建方式同ReentrantLock。ReadLock則通過使用acquireShared方法來支持同時允許多個讀線程。

Semaphore類（計數(shù)信號量）使用AQS同步狀態(tài)來保存信號量的當(dāng)前計數(shù)。它里面定義的acquireShared方法會減少計數(shù)，或當(dāng)計數(shù)為非正值時阻塞線程；tryRelease方法會增加計數(shù)，可能在計數(shù)為正值時還要解除線程的阻塞。

CountDownLatch類使用AQS同步狀態(tài)來表示計數(shù)。當(dāng)該計數(shù)為0時，所有的acquire操作（譯者注：acquire操作是從aqs的角度說的，對應(yīng)到CountDownLatch中就是await方法）才能通過。

FutureTask類使用AQS同步狀態(tài)來表示某個異步計算任務(wù)的運行狀態(tài)（初始化、運行中、被取消和完成）。設(shè)置（譯者注：FutureTask的set方法）或取消（譯者注：FutureTask的cancel方法）一個FutureTask時會調(diào)用AQS的release操作，等待計算結(jié)果的線程的阻塞解除是通過AQS的acquire操作實現(xiàn)的。

SynchronousQueues類（一種CSP（Communicating Sequential Processes）形式的傳遞）使用了內(nèi)部的等待節(jié)點，這些節(jié)點可以用于協(xié)調(diào)生產(chǎn)者和消費者。同時，它使用AQS同步狀態(tài)來控制當(dāng)某個消費者消費當(dāng)前一項時，允許一個生產(chǎn)者繼續(xù)生產(chǎn)，反之亦然。

java.util.concurrent包的使用者當(dāng)然也可以為自定義的應(yīng)用定義自己的同步器。例如，那些曾考慮到過的，但沒有采納進這個包的同步器包括提供WIN32事件各種風(fēng)格的語義類，二元信號量，集中管理的鎖以及基于樹的屏障。

5 性能

雖然AQS框架除了支持互斥鎖外，還支持其它形式的同步方式，但鎖的性能是最容易測量和比較的。即使如此，也還存在許多不同的測量方式。這里的實驗主要是設(shè)計來展示鎖的開銷和吞吐量。

在每個測試中，所有線程都重復(fù)的更新一個偽隨機數(shù)，該隨機數(shù)由nextRandom(int seed)方法計算：

int t = (seed % 127773) * 16807 - (seed / 127773) * 2836;
return (t > 0) ? t : t + 0x7fffffff;

在每次迭代中，線程以概率S在一個互斥鎖下更新共享的生成器，否則（譯者注：概率為1-S）更新其自己局部的生成器，此時是不需要鎖的。如此，鎖占用區(qū)域的耗時是短暫的，這就使線程持有鎖期間被搶占時的外界干擾降到了最小。這個函數(shù)的隨機性主要是為了兩個目的：確定是否需要使用鎖（這個生成器足以應(yīng)付這里的需求），以及使循環(huán)中的代碼不可能被輕易地優(yōu)化掉。

這里比較了四種鎖：內(nèi)置鎖，用的是synchronized塊；互斥鎖，用的是像第四節(jié)例子中的那樣簡單的Mutex類；可重入鎖，用的是ReentrantLock；以及公平鎖，用的是ReentrantLock的公平模式。所有測試都運行在J2SE1.5 JDK build46（大致與beta2相同）的server模式下。在收集測試數(shù)據(jù)前，測試程序先運行20次非競爭的測試，以排除JVM“預(yù)熱”（譯者注：更多關(guān)于“預(yù)熱”的內(nèi)容，參見：Java 理論與實踐: 動態(tài)編譯與性能測量）過程的影響。除了公平模式下的測試只跑了一百萬次迭代，其它每個線程中的測試都運行了一千萬次迭代。

該測試運行在四個X86機器和四個UltraSparc機器上。所有X86機器都運行的是RedHat基于NPTL 2.4內(nèi)核和庫的Linux系統(tǒng)。所有的UltraSparc機器都運行的是Solaris-9。測試時所有系統(tǒng)的負載都很輕。根據(jù)該測試的特征，并不要求系統(tǒng)完全空閑（譯者注：即測試時操作系統(tǒng)上有其它較輕的負載也不會影響本次測試的結(jié)果。）。“4P”這個名字反映出雙核超線程的Xeon更像是4路機器，而不是2路機器。這里沒有將測試數(shù)據(jù)規(guī)范化。如下所示，同步的相對開銷與處理器的數(shù)量、類型、速度之間不具備簡單的關(guān)系。

表1 測試的平臺

5.1 開銷

無競爭情況下的開銷是通過僅運行一個線程，將概率S為1時的每次迭代時間減去概率S為0（訪問共享內(nèi)存的概率為0）時的每次迭代時間得到的（譯者注：這里的“概率S”即前文提到的“概率S”，概率為0時是沒有鎖操作的，概率為1時是每次都有鎖操作，因此將概率為1時的耗時減去概率為0時的耗時就是整個鎖操作的開銷。）。表2以納秒為單位顯示了非競爭場景下每次鎖操作的開銷。Mutex類最接近于框架的基本耗時，可重入鎖的額外開銷是記錄當(dāng)前所有者線程和錯誤檢查的耗時，對于公平鎖來說還包含開始時檢查隊列是否為空的耗時。

表格2也展示與內(nèi)置鎖的“快速路徑（fast path）”對比，tryAcquire的耗時。這里的差異主要反映出了各鎖和機器中使用的不同的原子指令以及內(nèi)存屏障的耗時。在多處理器上，這些指令常常是完全優(yōu)于所有其它指令的。內(nèi)置鎖和同步器類之間的主要差別，顯然是由于Hotspot鎖在鎖定和解鎖時都使用了一次compareAndSet，而同步器的acquire操作使用了一次compareAndSet，但release操作用的是一次volatile寫（即，多處理器上的一次內(nèi)存屏障以及所有處理器上的重排序限制）。每個鎖的絕對的和相對耗時因機器的不同而不同。

表2 無競爭時的單鎖開銷（單位：納秒）

 從另一個極端看，表3展示了概率S為1，運行256個并發(fā)線程時產(chǎn)生了大規(guī)模的鎖競爭下每個鎖的開銷。在完全飽和的情況下，可闖入的FIFO鎖比內(nèi)置鎖的開銷少了一個數(shù)量級（也就是更大的吞吐量），比公平鎖更是少了兩個數(shù)量級。這表現(xiàn)出即使有著極大的競爭，在維持線程進展方面可闖入FIFO策略的效率。

表3也說明了即使在內(nèi)部開銷比較低的情況下，公平鎖的性能也完全是由上下文切換的時間所決定的。列出的時間大致上都與各平臺上線程阻塞和解除線程阻塞的時間相稱。

此外，后面增加的一個實驗（僅使用機器4P）表明，對于這里用到的短暫持有的鎖，公平參數(shù)的設(shè)置在總差異中的影響很小。這里將線程終止時間間的差異記錄成一個粗粒度的離散量數(shù)。在4P的機器上，公平鎖的時間度量的標準差平均為0.7%，可重入鎖平均為6.0%。作為對比，為模擬一個長時間持有鎖的場景，測試中使每個線程在持有鎖的情況下計算了16K次隨機數(shù)。這時，總運行時間幾乎是相同的（公平鎖：9.79s，可重入鎖：9.72s）。公平模式下的差異依然很小，標準差平均為0.1%，而可重入鎖上升到了平均29.5%。

表格3 飽和時的單鎖開銷（單位：納秒）

5.2 吞吐量

大部分同步器都是用于無競爭和極大競爭之間的。這可以用實驗在兩個方面進行檢查，通過修改固定個線程的競爭概率，和/或通過往擁有固定競爭概率的線程集合里增加更多的線程。為了說明這些影響，測試運行在不同的競爭概率和不同的線程數(shù)目下，都用的是可重入鎖。附圖使用了一個slowdown度量標準。

這里，t是總運行時間，b是一個線程在沒有競爭或同步下的基線時間，n是線程數(shù)，p是處理器數(shù)，S是共享訪問的比例（譯者注：即前面的競爭概率S）。計算結(jié)果是實際執(zhí)行時間與理想執(zhí)行時間（通常是無法得到的）的比率，理想執(zhí)行時間是通過使用Amdahl’s法則計算出來的。理想時間模擬了一次沒有同步開銷，沒有因鎖爭用而導(dǎo)致線程阻塞的執(zhí)行過程。即使這樣，在很低的競爭下，相比理想時間，有一些測試結(jié)果卻表現(xiàn)出了很小的速度增長，大概是由于基線和測試之間的優(yōu)化、流水線等方面有著輕微的差別。

圖中用以2為底的對數(shù)為比例進行了縮放。例如，值為1表示實際時間是理想時間的兩倍，4表示慢16倍。使用對數(shù)就不需要依賴一個隨意的基線時間（這里指的是計算隨機數(shù)的時間），因此，基于不同底數(shù)計算的結(jié)果表現(xiàn)出的趨勢應(yīng)該是類似的。這些測試使用的競爭概率從1/128（標識為“0.008”）到1，以2的冪為步長，線程的數(shù)量從1到1024，以2的冪的一半為步長。

在單處理器（1P和1U）上，性能隨著競爭的上升而下降，但不會隨著線程數(shù)的增加而下降。多處理器在遭遇競爭時，性能下降的更快。根據(jù)多處理器相關(guān)的圖表顯示，開始出現(xiàn)的峰值處雖然只有幾個線程的競爭，但相對性能通常卻最差。這反映出了一個性能的過渡區(qū)域，在這里闖入的線程和被喚醒的線程都準備獲取鎖，這會讓它們頻繁的迫使對方阻塞。在大部分時候，過渡區(qū)域后面會緊接著一個平滑區(qū)域，因為此時幾乎沒有空閑的鎖，所以會與單處理器上順序執(zhí)行的模式差不多；在多處理器機器上會較早進入平滑區(qū)域。例如，請注意，在滿競爭（標識為“1.000”）下這些值表示，在處理器越少的機器上，會有更糟糕的相對速度下降。

根據(jù)這些結(jié)果，可以針對阻塞（park/unpark）做進一步調(diào)優(yōu)以減少上下文切換和相關(guān)的開銷，這會給本框架帶來小但顯著的提升。此外，在多處理器上為短時間持有的但高競爭的鎖采用某種形式的適應(yīng)性自旋，可以避免這里看到的一些波動，這對同步器類大有裨益。雖然在跨不同上下文時適應(yīng)性自旋很難很好的工作，但可以使用本框架為遇到這類使用配置的特定應(yīng)用構(gòu)建一個自定義形式的鎖。

6 總結(jié)

本文撰寫之時，java.util.concurrent包中的同步器框架還太新所以還不能在實踐中使用。因此在J2SE 1.5最終版本發(fā)布之前都很難看到其大范圍的使用，并且，它的設(shè)計，API實現(xiàn)以及性能肯定還有無法預(yù)料的后果。但是，此時，這個框架明顯能勝任其基本的目標，即為創(chuàng)建新的同步器提供一個高效的基礎(chǔ)。

7 致謝

Thanks to Dave Dice for countless ideas and advice during the development of this framework, to Mark Moir and Michael Scott for urging consideration of CLH queues, to David Holmes for critiquing early versions of the code and API, to Victor Luchangco and Bill Scherer for reviewing previous incarnations of the source code, and to the other members of the JSR166 Expert Group (Joe Bowbeer, Josh Bloch, Brian Goetz, David Holmes, and Tim Peierls) as well as Bill Pugh, for helping with design and specifications and commenting on drafts of this paper. Portions of this work were made possible by a DARPA PCES grant, NSF grant EIA-0080206 (for access to the 24way Sparc) and a Sun Collaborative Research Grant.

參考文獻

• [1] Agesen, O., D. Detlefs, A. Garthwaite, R. Knippel, Y. S.Ramakrishna, and D. White. An Efficient Meta-lock for Implementing Ubiquitous Synchronization. ACM OOPSLA Proceedings, 1999.
• [2] Andrews, G. Concurrent Programming. Wiley, 1991.
• [3] Bacon, D. Thin Locks: Featherweight Synchronization for Java. ACM PLDI Proceedings, 1998.
• [4] Buhr, P. M. Fortier, and M. Coffin. Monitor Classification,ACM Computing Surveys, March 1995.
• [5] Craig, T. S. Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02,Department of Computer Science, University of Washington, Feb. 1993.
• [6] Gamma, E., R. Helm, R. Johnson, and J. Vlissides. Design Patterns, Addison Wesley, 1996.
• [7] Holmes, D. Synchronisation Rings, PhD Thesis, Macquarie University, 1999.
• [8] Magnussen, P., A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. 8th Intl. Parallel Processing Symposium, Cancun, Mexico, Apr. 1994.
• [9] Mellor-Crummey, J.M., and M. L. Scott. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Trans. on Computer Systems,February 1991
• [10] M. L. Scott and W N. Scherer III. Scalable Queue-Based Spin Locks with Timeout. 8th ACM Symp. on Principles and Practice of Parallel Programming, Snowbird, UT, June 2001.
• [11] Sun Microsystems. Multithreading in the Solaris Operating Environment. White paper available at http://wwws.sun.com/software/solaris/whitepapers.html 2002.
• [12] Zhang, H., S. Liang, and L. Bak. Monitor Conversion in a Multithreaded Computer System. United States Patent 6,691,304. 2004.

原文《The java.util.concurrent Synchronizer Framework》

作者：Doug Lea

以上就是java并發(fā)包JUC同步器框架AQS框架原文翻譯的詳細內(nèi)容，更多關(guān)于AQS框架原文翻譯的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論