摘要

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

1. 背景介紹

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

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

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

2 需求

2.1 功能

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

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

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

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

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

2.2 性能目標(biāo)

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

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

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

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

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

同步器背后的基本思想非常簡(jiǎ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;

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

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

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

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

3.1 同步狀態(tài)

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

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

（譯者注：

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

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

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

3.2 阻塞

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

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

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

3.3 隊(duì)列

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

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

CLH隊(duì)列實(shí)際上并不那么像隊(duì)列，因?yàn)樗娜腙?duì)和出隊(duì)操作都與它的用途（即用作鎖）緊密相關(guān)。它是一個(gè)鏈表隊(duì)列，通過(guò)兩個(gè)字段head和tail來(lái)存取，這兩個(gè)字段是可原子更新的，兩者在初始化時(shí)都指向了一個(gè)空節(jié)點(diǎn)。

一個(gè)新的節(jié)點(diǎn)，node，通過(guò)一個(gè)原子操作入隊(duì)：

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

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

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

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

	head = node;

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

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

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

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

pred.next = node;

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

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

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

同步框架中使用的CLH鎖的變體與其他語(yǔ)言中的相比，主要區(qū)別可能是同步框架中使用的CLH鎖需要依賴(lài)?yán)厥展芾砉?jié)點(diǎn)的內(nèi)存，這就避免了一些復(fù)雜性和開(kāi)銷(xiāo)。但是，即使依賴(lài)GC也仍然需要在確定鏈接字段不再需要時(shí)將其置為null。這往往可以與出隊(duì)操作一起完成。否則，無(wú)用的節(jié)點(diǎn)仍然可觸及，它們就沒(méi)法被回收。

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

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

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ù)依賴(lài)于具體實(shí)現(xiàn)類(lèi)中tryAcquire的實(shí)現(xiàn)方式。另一方面，在沒(méi)有“取消”操作的情況下，每一個(gè)組件的acquire和release都是一個(gè)O(1)的操作，忽略park中發(fā)生的所有操作系統(tǒng)線(xiàn)程調(diào)度。

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

3.4 條件隊(duì)列

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

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

ConditionObject使用了與同步器一樣的內(nèi)部隊(duì)列節(jié)點(diǎn)。但是，是在一個(gè)單獨(dú)的條件隊(duì)列中維護(hù)這些節(jié)點(diǎn)的。signal操作是通過(guò)將節(jié)點(diǎn)從條件隊(duì)列轉(zhuǎn)移到鎖隊(duì)列中來(lái)實(shí)現(xiàn)的，而沒(méi)有必要在需要喚醒的線(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;

因?yàn)橹挥性诔钟墟i的時(shí)候才能執(zhí)行這些操作，因此他們可以使用順序鏈表隊(duì)列操作來(lái)維護(hù)條件隊(duì)列（在節(jié)點(diǎn)中用一個(gè)nextWaiter字段）。轉(zhuǎn)移操作僅僅把第一個(gè)節(jié)點(diǎn)從條件隊(duì)列中的鏈接解除，然后通過(guò)CLH插入操作將其插入到鎖隊(duì)列上。

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

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

4 用法

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

下面是一個(gè)最簡(jiǎn)單的Mutex類(lèi)的實(shí)現(xiàn)，它使用同步狀態(tài)0表示解鎖，1表示鎖定。這個(gè)類(lèi)并不需要同步方法中的參數(shù)，因此這里在調(diào)用的時(shí)候使用0作為實(shí)參，方法實(shí)現(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); }
}

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

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

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

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

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

盡管同步器是基于FIFO隊(duì)列的，但它們并不一定就得是公平的。可以注意到，在基礎(chǔ)的acquire算法（3.3節(jié)）中，tryAcquire是在入隊(duì)前被執(zhí)行的。因此一個(gè)新的acquire線(xiàn)程能夠“竊取”本該屬于隊(duì)列頭部第一個(gè)線(xiàn)程通過(guò)同步器的機(jī)會(huì)。

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

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

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

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

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

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

4.2 同步器

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

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

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

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

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

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

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

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

5 性能

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

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

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

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

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

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

表1 測(cè)試的平臺(tái)

5.1 開(kāi)銷(xiāo)

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

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

表2 無(wú)競(jìng)爭(zhēng)時(shí)的單鎖開(kāi)銷(xiāo)（單位：納秒）

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

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

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

表格3 飽和時(shí)的單鎖開(kāi)銷(xiāo)（單位：納秒）

5.2 吞吐量

大部分同步器都是用于無(wú)競(jìng)爭(zhēng)和極大競(jìng)爭(zhēng)之間的。這可以用實(shí)驗(yàn)在兩個(gè)方面進(jìn)行檢查，通過(guò)修改固定個(gè)線(xiàn)程的競(jìng)爭(zhēng)概率，和/或通過(guò)往擁有固定競(jìng)爭(zhēng)概率的線(xiàn)程集合里增加更多的線(xiàn)程。為了說(shuō)明這些影響，測(cè)試運(yùn)行在不同的競(jìng)爭(zhēng)概率和不同的線(xiàn)程數(shù)目下，都用的是可重入鎖。附圖使用了一個(gè)slowdown度量標(biāo)準(zhǔn)。

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

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

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

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

6 總結(jié)

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

參考文獻(xiàn)

• [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框架原文翻譯的詳細(xì)內(nèi)容，更多關(guān)于AQS框架原文翻譯的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論