原文點(diǎn)擊這里

摘要

J2SE1.5 java.util.concurrent包中大部分的同步工具（locks,barriers等等）都是基于AbstractQueuedSynchronizer類(lèi)（下面簡(jiǎn)稱(chēng)AQS）構(gòu)建的。這個(gè)類(lèi)提供了通用的機(jī)制來(lái)“原子化”管理同步狀態(tài)枫笛，阻塞和喚醒線(xiàn)程以及管理同步隊(duì)列所灸。本文介紹了該類(lèi)的一些基本設(shè)計(jì)思路、實(shí)現(xiàn)管宵、用法以及一些性能方面的考量穴吹。

1.簡(jiǎn)介

J2SE1.5 引入了J.U.C包低散，提供了一系列用來(lái)支持并發(fā)操作的"同步器"桨昙。
這些"同步器"都基于一個(gè)基礎(chǔ)框架：1.包含一個(gè)同步狀態(tài)；2.提供修改和查看同步狀態(tài)的方法措左；3.提供阻塞當(dāng)前線(xiàn)程和喚醒等待線(xiàn)程的方法依痊；
這些"同步器"包括：mutex locks,read-write locks,semaphores,barriers,futures,event indicators,SynchronousQueue等.

幾乎每種類(lèi)型的"同步器"都可以用其他類(lèi)型的"同步器"來(lái)實(shí)現(xiàn)，例如怎披，semaphores可以實(shí)現(xiàn)reentrant locks,反之亦然胸嘁。但是，這么做通常比較復(fù)雜凉逛，性能也比較差性宏，不夠靈活。所以JSR166提供了一個(gè)很小但是又很全面的基礎(chǔ)類(lèi)AbstractQueuedSynchronizer状飞，提供了以上這些"同步器"需要的大部分機(jī)制的實(shí)現(xiàn)毫胜，"同步器"只需補(bǔ)充實(shí)現(xiàn)各自的特性即可。

本文剩下的部分討論下AQS的功能需求诬辈，設(shè)計(jì)和實(shí)現(xiàn)的主要思路酵使，一些簡(jiǎn)單的用法，還有一些測(cè)試用來(lái)展示它在性能方面的特征焙糟。

2.需求

2.1 功能

"同步器"提供了兩類(lèi)方法：1.至少一個(gè)acquire口渔，這個(gè)方法獲得鎖，如果”鎖“已被其他線(xiàn)程占用酬荞，則阻塞當(dāng)前線(xiàn)程直到被釋放鎖的線(xiàn)程喚醒搓劫。2.至少一個(gè)release，這個(gè)方法釋放鎖混巧，并且喚醒一個(gè)或多個(gè)等待的其他線(xiàn)程枪向。

J.U.C包沒(méi)有定義一個(gè)統(tǒng)一的API來(lái)規(guī)定這些"同步器"的方法和功能。所以它們有的是通過(guò)實(shí)現(xiàn)一個(gè)通用接口（如Lock）咧党，有些是直接實(shí)現(xiàn)了特定的功能秘蛔。所以，acquire和release在不同的"同步器"里可能會(huì)有不同的名字傍衡。例如深员，Lock.lock,Semaphore.acqure,CountDownLatch.await,和Future.get 都是與acquire類(lèi)似的方法。

但是蛙埂，J.U.C包也保持了一些一致的慣例倦畅。每種"同步器"必須支持：

• 既支持阻塞也支持非阻塞（例如： lock & tryLock）
• 提供超時(shí)機(jī)制：以便應(yīng)用可以放棄等待
• 響應(yīng)線(xiàn)程中斷：通常提供兩個(gè)類(lèi)似的acquire方法，一個(gè)支持中斷一個(gè)不支持

"同步器"既可以是獨(dú)占鎖绣的，也可以是共享鎖叠赐。例如欲账，ReentrantLock是獨(dú)占鎖，而Semaphore是共享鎖芭概。為了適用性更廣赛不，AQS必須同時(shí)支持這兩種模式的"同步器"。

J.U.C包還定義了一個(gè)接口Condition罢洲，配合ReentrantLock實(shí)現(xiàn)"monitor"風(fēng)格（即Java中的Synchronize關(guān)鍵字）的"await/signal"操作踢故。

2.2 性能

Java內(nèi)建的synchronize關(guān)鍵字一直存在性能方面的問(wèn)題，有很多文獻(xiàn)曾經(jīng)分析過(guò)這些問(wèn)題惹苗。但是這些研究主要集中在單核環(huán)境下的絕大多數(shù)時(shí)候都是單線(xiàn)程情形的最小化內(nèi)存占用和cpu時(shí)間占用殿较。而實(shí)際上這些問(wèn)題都不算問(wèn)題：1.程序員們只有在需要使用的時(shí)候才會(huì)使用鎖，所以鎖的內(nèi)存開(kāi)銷(xiāo)相對(duì)于整個(gè)應(yīng)用的內(nèi)存開(kāi)銷(xiāo)占比非常小鸽粉，壓縮內(nèi)存意并不大斜脂；2.越來(lái)越多的程序是運(yùn)行在多核多線(xiàn)程的環(huán)境下，在這種環(huán)境下資源競(jìng)爭(zhēng)是不可避免的触机。但是過(guò)去的JVM對(duì)于鎖優(yōu)化的策略主要基于沒(méi)有資源爭(zhēng)用（單核）的情形，而對(duì)其他的情形都使用難以預(yù)測(cè)的“slow path"(通過(guò)阻塞和喚醒線(xiàn)程的方式進(jìn)行同步)玷或，這對(duì)于嚴(yán)重依賴(lài)JUC的典型多線(xiàn)程服務(wù)來(lái)說(shuō)并不是一種正確的策略儡首。

（譯者注：在linux內(nèi)核中，當(dāng)一個(gè)進(jìn)程嘗試獲取一個(gè)mutex時(shí)偏友，它可能會(huì)走三種paths：

• fastpath： 無(wú)資源爭(zhēng)用（zero-contention）蔬胯，直接獲取到鎖
• midpath： 有少量資源爭(zhēng)用，采取optimistic spinning
• slowpath： 有大量資源爭(zhēng)用位他，采取block/wakeup

JVM的優(yōu)化只針對(duì)了“fastpath”氛濒，而且JVM的path只有兩種：fastpath和slowpath，沒(méi)有midpath鹅髓。其實(shí)不難理解舞竿，因?yàn)閙idpath只有在多核（是多核而非多線(xiàn)程）環(huán)境下才有效，單核環(huán)境下的spinning沒(méi)有意義窿冯，而JVM主要針對(duì)單核優(yōu)化的骗奖。Java 1.5引入了JUC,所以這篇文章所描述的是1.5之前的monitor的性能問(wèn)題，而Java 1.6之后monitor已經(jīng)不存在這些性能問(wèn)題了）

我們這里的主要性能目標(biāo)是可擴(kuò)展性：即使在資源競(jìng)爭(zhēng)激烈的情況下醒串，也要可預(yù)測(cè)的平滑性能执桌。最理想的情形是無(wú)論有多少線(xiàn)程請(qǐng)求這個(gè)"鎖"，它們的處理時(shí)間都是常數(shù)級(jí)的芜赌。在這些目標(biāo)中有一個(gè)是要盡量減少那些可以獲得鎖但是還未完成加鎖過(guò)程的時(shí)間的總和（降低獲取鎖過(guò)程中的開(kāi)銷(xiāo)仰挣，減少鎖的總空閑時(shí)間）。當(dāng)然缠沈，這里也需要在總的CPU耗時(shí)膘壶，內(nèi)存負(fù)載以及線(xiàn)程調(diào)度的耗費(fèi)之間作出一些權(quán)衡违柏。例如，自旋鎖通诚阕担可以縮短獲取鎖的時(shí)間漱竖，但是會(huì)讓CPU空跑，也會(huì)產(chǎn)生一些內(nèi)存爭(zhēng)用畜伐，所以應(yīng)用得不多馍惹。

另外，我們需要考慮兩種不同類(lèi)型的使用場(chǎng)景玛界。第一種是大部分應(yīng)用的需求万矾，需要最大化吞吐量，而對(duì)于可能產(chǎn)生的"線(xiàn)程饑餓"可以容忍慎框。另一種是對(duì)于那些資源控制類(lèi)型的應(yīng)用良狈，需要保證每個(gè)線(xiàn)程獲取資源的公平性。沒(méi)有一種策略可以同時(shí)滿(mǎn)足這倆種互相沖突的目標(biāo)笨枯，所以AQS需要提供這兩種不同的公平性策略薪丁。

無(wú)論框架設(shè)計(jì)得多么好，在一些實(shí)際的應(yīng)用中馅精，一定會(huì)存在性能瓶頸严嗜。因此，框架需要提供方法來(lái)監(jiān)控和檢查一些基本操作洲敢，讓使用者可以發(fā)現(xiàn)并且緩解性能瓶頸漫玄。例如，至少得提供個(gè)方法讓用戶(hù)可以知道有多少線(xiàn)程在阻塞压彭。

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

"同步器"的基本思路非常簡(jiǎn)單睦优。
有一個(gè)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;

有一個(gè)release:

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

想要支持這兩個(gè)操作需要三個(gè)基本組件的配合：

• 原子地更新同步狀態(tài)
• 阻塞和喚醒線(xiàn)程
• 管理線(xiàn)程隊(duì)列

也許可以為這三個(gè)組件各創(chuàng)建一個(gè)框架，允許它們可以相互獨(dú)立壮不，但這種方案效率不高汗盘，也缺乏可行性。例如忆畅，喚醒某個(gè)線(xiàn)程依賴(lài)于隊(duì)列中該線(xiàn)程所在節(jié)點(diǎn)的狀態(tài)衡未，而開(kāi)放出來(lái)的方法（public或protected）也依賴(lài)于同步狀態(tài)。

同步框架的核心設(shè)計(jì)是為這三個(gè)組件每個(gè)選擇一個(gè)具體的實(shí)現(xiàn)家凯，同時(shí)仍允許在如何使用它們上有廣泛的選項(xiàng)缓醋。這種設(shè)計(jì)可能犧牲了一些適用性，但是能保證足夠的效率绊诲，所以當(dāng)實(shí)際使用的時(shí)候送粱，如果場(chǎng)景合適，幾乎沒(méi)有理由不用它而選擇自己實(shí)現(xiàn)一個(gè)掂之。

3.1 同步狀態(tài)

AQS用一個(gè)int值來(lái)表示同步狀態(tài)抗俄，并且開(kāi)放了getState脆丁，setState和compareAndSetState方法來(lái)獲取和更新它。這個(gè)狀態(tài)值是volatile的动雹，符合JSR133中volatile的語(yǔ)義槽卫。并且compareAndSetState基于CAS指令實(shí)現(xiàn)了該狀態(tài)的原子更新。

將狀態(tài)限定為int是個(gè)務(wù)實(shí)的決定胰蝠。JSR166也提供了對(duì)于long類(lèi)型的原子操作類(lèi)歼培，但是在很多平臺(tái)上這些操作在JVM內(nèi)部實(shí)現(xiàn)的時(shí)候有一些lock，性能會(huì)差一些茸塞。未來(lái)躲庄，有可能會(huì)提供另一個(gè)基于long型狀態(tài)值的"AQS"。但是钾虐，目前還沒(méi)有足夠的必要性去添加這個(gè)特性噪窘，在絕大部分應(yīng)用場(chǎng)景下，int已經(jīng)足夠滿(mǎn)足需求----只有一個(gè)CyclicBarrier需要更多的字節(jié)去表示狀態(tài)效扫，所以我們直接使用了其他的”鎖”來(lái)實(shí)現(xiàn)（用其他"鎖"來(lái)管理狀態(tài)倔监，而不是直接實(shí)現(xiàn)或使用AQS，J.U.C中大部分的高級(jí)API都是如此）荡短。

基于AQS的同步器實(shí)現(xiàn)類(lèi)必須實(shí)現(xiàn)兩個(gè)方法tryAcquire和tryRelease丐枉，通過(guò)使用開(kāi)放出來(lái)的狀態(tài)檢查和更新方法來(lái)實(shí)現(xiàn)acquire和release操作。如果獲取"鎖"成功掘托，tryAcquire方法必須返回true；如果成功"解鎖"籍嘹，release方法也必須返回true闪盔。這些方法都接收一個(gè)int類(lèi)型參數(shù)，用來(lái)溝通需要的狀態(tài)辱士。例如泪掀，在Reentrant Lock中，如果某個(gè)線(xiàn)程acquire成功颂碘，則它在持有"鎖"的過(guò)程中可以利用此參數(shù)一次性acquire多個(gè)或多次acquire异赫，也可以利用此參數(shù)一次性release多個(gè)或多次release。很多"同步器"實(shí)現(xiàn)不需要這個(gè)參數(shù)头岔，直接忽略即可塔拳。

3.2 阻塞和喚醒線(xiàn)程

直到JSR166，還沒(méi)有可用的Java API用來(lái)為同步器阻塞和喚醒線(xiàn)程峡竣。唯一的候選者是Thread.suspend和Thread.resume靠抑，但是他們不能解決一個(gè)問(wèn)題：如果一個(gè)活動(dòng)線(xiàn)程在suspend之前調(diào)用resume，則這次resume操作沒(méi)有任何作用适掰。

J.U.C包引入了一個(gè)LockSupport類(lèi)來(lái)解決這個(gè)問(wèn)題颂碧。LockSupport.park方法可以阻塞當(dāng)前線(xiàn)程直到LockSupport.unpark方法來(lái)喚醒它（包括虛假喚醒）荠列。unpark不會(huì)被"計(jì)數(shù)"，所以在park之前無(wú)論調(diào)用多少次unpark只能喚醒一次park（譯者注：但是有unpark狀態(tài)载城，也正是這一點(diǎn)解決了suspend和resume的問(wèn)題）肌似。另外，這倆方法都是針對(duì)線(xiàn)程而不是"同步器"的诉瓦。一個(gè)在新的"同步器"上調(diào)用了park的線(xiàn)程可能會(huì)立即返回（因?yàn)橛锌赡苤斑€有個(gè)"剩余"的unpark）川队，它的下一次park才會(huì)阻塞。雖然可以顯式地清除unpark的狀態(tài)垦搬，但是更優(yōu)雅的方法是多次調(diào)用park方法呼寸。

這種機(jī)制類(lèi)似于Solaris-9的線(xiàn)程庫(kù)，win32的“可消費(fèi)事件”和linux NPTL的線(xiàn)程庫(kù)猴贰，所以它能很好地映射到這些平臺(tái)庫(kù)上对雪，提供良好的運(yùn)行性能（但是，目前的Sun HotSpot JVM在Solaris和Linux上的實(shí)現(xiàn)實(shí)際上使用了一個(gè)pthread條件變量米绕，因?yàn)樾枰m配現(xiàn)存的運(yùn)行時(shí)設(shè)計(jì)）瑟捣。park也支持可選的相對(duì)或者絕對(duì)的超時(shí)時(shí)間，并且響應(yīng)JVM的Thread.interrupt栅干。

3.3 同步隊(duì)列

AQS的核心是對(duì)同步隊(duì)列的管理迈套，且隊(duì)列已被限定為先入先出隊(duì)列。所以碱鳞，AQS不支持基于優(yōu)先級(jí)的同步桑李。

毫無(wú)爭(zhēng)議，最適合用來(lái)做同步隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是那些不需要依賴(lài)更低級(jí)的"同步器"的窿给。所以贵白，現(xiàn)在有兩個(gè)主要的候選者：MCS 和CLH。歷史上崩泡，CLH只被用于過(guò)自旋鎖禁荒。但是，它看起來(lái)比MCS要更經(jīng)得起考驗(yàn)角撞，因?yàn)樗梢院茌p松地處理取消和超時(shí)呛伴，所以我們選擇CLH作為同步隊(duì)列的基礎(chǔ)。

CLH隊(duì)列不是一個(gè)"單純"的隊(duì)列谒所，因?yàn)樗某鲫?duì)和入隊(duì)操作都與它的作為"同步器"的功能緊密聯(lián)系热康。它是一個(gè)linked隊(duì)列，包含兩個(gè)原子更新的屬性head和tail百炬，它們一開(kāi)始都指向一個(gè)無(wú)意義的節(jié)點(diǎn)褐隆。

20181016041652.png

新的節(jié)點(diǎn)可以通過(guò)原子操作入隊(duì)：

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

當(dāng)前節(jié)點(diǎn)的release狀態(tài)由它的前置節(jié)點(diǎn)管理，所以剖踊，"鎖"的自旋如下：

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

在自旋之后的出隊(duì)操作就是簡(jiǎn)單地把head設(shè)置成當(dāng)前獲得"鎖"的節(jié)點(diǎn)即可：

head = node;

CLH最主要的優(yōu)勢(shì)在于出隊(duì)和入隊(duì)非呈快衫贬，而且沒(méi)有任何鎖的開(kāi)銷(xiāo)，也不需要阻塞線(xiàn)程（即時(shí)是在有競(jìng)爭(zhēng)的情況下歇攻，因?yàn)榭倳?huì)有一個(gè)線(xiàn)程插入成功）固惯；檢查有沒(méi)有線(xiàn)程在等待也很簡(jiǎn)單（只需要判斷head和tail是否是一樣的即可）；而且release狀態(tài)是非中心化的缴守，避免了內(nèi)存爭(zhēng)用葬毫。

在原始版本的CLH中，節(jié)點(diǎn)之間甚至沒(méi)有連接屡穗。在自旋鎖中贴捡，前置節(jié)點(diǎn)被作為一個(gè)局部變量。但是村砂，Scott和Schere發(fā)現(xiàn)通過(guò)顯式地將前置節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)連接烂斋，CLH可以處理超時(shí)或者其他形式的取消操作。因?yàn)槿绻粋€(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)被取消了础废，這個(gè)節(jié)點(diǎn)可以繼續(xù)找到"前置節(jié)點(diǎn)"的"前置節(jié)點(diǎn)"的狀態(tài)汛骂。

AQS對(duì)于CLH最主要的改動(dòng)在于提供了一個(gè)有效的方法可以使一個(gè)節(jié)點(diǎn)找到它的后繼節(jié)點(diǎn)。在自旋鎖中评腺，一個(gè)節(jié)點(diǎn)只要修改了它的狀態(tài)帘瞭，就會(huì)被它的后繼節(jié)點(diǎn)在下一次循環(huán)時(shí)注意到，所以不需要將當(dāng)前節(jié)點(diǎn)與它的后繼節(jié)點(diǎn)連接起來(lái)蒿讥；但是在阻塞的"同步器"中蝶念，一個(gè)節(jié)點(diǎn)必須顯式地喚醒（unpark）它的后繼節(jié)點(diǎn)。

AQS的節(jié)點(diǎn)有一個(gè)next屬性關(guān)聯(lián)到它的后繼節(jié)點(diǎn)芋绸。但是沒(méi)有什么技術(shù)可以"無(wú)鎖地""原子地"向雙向隊(duì)列中插入一個(gè)節(jié)點(diǎn)祸轮，所以這個(gè)屬性沒(méi)有作為原子性插入節(jié)點(diǎn)的一部分（譯者注：pred與next只需要保證一個(gè)原子更新成功即可，另一個(gè)直接賦值）侥钳；只需要在節(jié)點(diǎn)插入之后簡(jiǎn)單地賦值即可：

pred.next = node;

next連接通常只被當(dāng)做一種優(yōu)化的訪(fǎng)問(wèn)路徑。如果一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)不存在了（可能被取消了）柄错，可以通過(guò)從tail遍歷每個(gè)節(jié)點(diǎn)的pred屬性找到一個(gè)實(shí)際存在的節(jié)點(diǎn)舷夺。

第二個(gè)改動(dòng)是在每個(gè)節(jié)點(diǎn)中使用一個(gè)status屬性來(lái)控制線(xiàn)程的阻塞和喚醒，而不是一直自旋售貌。在AQS中给猾，隊(duì)列中的節(jié)點(diǎn)只有在tryAcquire返回true且acquire成功才能返回，所以?xún)H僅只有一個(gè)release位是不夠的（release狀態(tài)只能支持acquire操作颂跨，tryAcquire需要依賴(lài)其他狀態(tài)）敢伸。而且需要保證一個(gè)活動(dòng)的線(xiàn)程只有當(dāng)它在隊(duì)首的時(shí)候才可以tryAcquire，也可以通過(guò)檢查當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)是否是head來(lái)確定恒削。

    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

與自旋鎖相比池颈，這樣減少了讀取head的內(nèi)存爭(zhēng)用（只讀取一次尾序，而自旋鎖在一直循環(huán)讀取）躯砰。但是每币，取消的狀態(tài)還是需要在節(jié)點(diǎn)中維護(hù)。

隊(duì)列中節(jié)點(diǎn)的狀態(tài)還被用來(lái)避免對(duì)park和unpark不必要的調(diào)用琢歇。雖然這些方法跟線(xiàn)程的阻塞原語(yǔ)（操作系統(tǒng)級(jí)別）性能相當(dāng)兰怠，但還是不可避免地有一些橫亙?cè)贘ava代碼和JVM運(yùn)行時(shí)之間的耗費(fèi)。所以在調(diào)用park之前李茫，線(xiàn)程先設(shè)置一個(gè)signal me狀態(tài)位揭保，然后檢查一次同步狀態(tài)和節(jié)點(diǎn)狀態(tài)，最后再park魄宏。release操作會(huì)清除這個(gè)狀態(tài)位（所以秸侣，如果某個(gè)線(xiàn)程在設(shè)置signal me和park之間，持有鎖的線(xiàn)程調(diào)用了release娜庇，并且正好unpark了這個(gè)線(xiàn)程塔次，則節(jié)省了一次線(xiàn)程阻塞和喚醒的消耗）。這種做法可以避免很多不必要的阻塞名秀，尤其是對(duì)于那些耗費(fèi)了很多時(shí)間在等待下一個(gè)合適的線(xiàn)程獲得鎖的"同步器"的實(shí)現(xiàn)中（對(duì)于這類(lèi)"同步器"励负，阻塞應(yīng)該盡量避免，因?yàn)樽枞酥筘暗茫却聜€(gè)線(xiàn)程來(lái)喚醒的話(huà)可能會(huì)比較耗時(shí)）继榆。這樣還可以避免一些release操作，因?yàn)?em>release需要節(jié)點(diǎn)設(shè)置了signal狀態(tài)汁掠，所以我們可以跳過(guò)那些cancelled的節(jié)點(diǎn)略吨，除非signal和cancel同時(shí)發(fā)生了。

也許AQS與其他語(yǔ)言的CLH變種之間的最大區(qū)別是依賴(lài)?yán)厥掌鞴芾砉?jié)點(diǎn)的內(nèi)存回收考阱，這避免了一些復(fù)雜性和性能消耗翠忠。然而，雖然有GC乞榨，但是還是需要將確定不再用到的屬性置為null秽之。這個(gè)在節(jié)點(diǎn)出隊(duì)的時(shí)候顯然肯定會(huì)做到，但是吃既，對(duì)于那些已經(jīng)取消的節(jié)點(diǎn)卻仍然可以被訪(fǎng)問(wèn)到考榨，導(dǎo)致他們不能被回收（需要手動(dòng)置為null，help gc）鹦倚。

還有一些更進(jìn)一步的小優(yōu)化河质，包括將head和tail的初始化延遲到第一次有線(xiàn)程等待時(shí)。

忽略這些細(xì)節(jié)，最終對(duì)于基本的acquire（排他掀鹅，不響應(yīng)中斷散休，不超時(shí)）的大致實(shí)現(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) 
             park();
        else
             compareAndSet pred's signal bit to true;
             pred = node's effective predecessor; 
     }
     head = node;
}

release的大致實(shí)現(xiàn)：

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

雖然acquire中tryAcquire可能會(huì)循環(huán)多次，但是淫半，如果不考慮被取消的節(jié)點(diǎn)和每個(gè)平臺(tái)對(duì)于park的不同實(shí)現(xiàn)的話(huà)溃槐，acquire和release中的單個(gè)操作分?jǐn)偟矫總€(gè)線(xiàn)程中都是常量時(shí)間O(1)。

對(duì)于取消的支持主要是在park的時(shí)候需要響應(yīng)中斷和檢查超時(shí)科吭。一個(gè)由于超時(shí)或中斷被取消的線(xiàn)程會(huì)設(shè)置節(jié)點(diǎn)的狀態(tài)昏滴，并且喚醒它的后繼線(xiàn)程，所以它有可能會(huì)重置這些連接对人。因?yàn)橛斜蝗∠?jié)點(diǎn)的存在谣殊，找到有效的前置節(jié)點(diǎn)或者后繼節(jié)點(diǎn)并修改狀態(tài)可能會(huì)花費(fèi)O(n)次的遍歷（n是隊(duì)列長(zhǎng)度）。如果某個(gè)操作因?yàn)槌瑫r(shí)或中斷被取消了牺弄，通常直接返回false或者拋異常姻几，不會(huì)再去relock，所以節(jié)點(diǎn)的連接和狀態(tài)屬性可以很快重建好势告。

3.4 條件隊(duì)列

AQS提供了一個(gè)ConditionObject類(lèi)來(lái)實(shí)現(xiàn)排它鎖蛇捌，并且遵循Lock接口的API。一個(gè)鎖可以綁定任意多的條件對(duì)象（condition object）咱台，可以提供monitor風(fēng)格的await络拌，signal和signalAll操作，包括這些操作的超時(shí)版本和一些監(jiān)控和檢查的方法（詳見(jiàn)J.U.C的Lock接口）回溺。

ConditionObject類(lèi)可以用來(lái)與其他同步器配合春贸，修復(fù)一些設(shè)計(jì)缺陷。這個(gè)類(lèi)支持monitor風(fēng)格的訪(fǎng)問(wèn)遗遵，當(dāng)且僅當(dāng)當(dāng)前線(xiàn)程擁有鎖的時(shí)候萍恕。將ConditionObject與ReentrantLock結(jié)合起來(lái)可以完成與Java內(nèi)建monitor相同的操作（像Object.wait等），只是在名稱(chēng)上略有不同车要，而且還有個(gè)額外的功能：用戶(hù)可以對(duì)一個(gè)鎖聲明多個(gè)條件對(duì)象（內(nèi)建只有一個(gè)）允粤。

ConditionObject使用和"鎖"相同的隊(duì)列節(jié)點(diǎn)類(lèi)型，但是使用了單獨(dú)的條件隊(duì)列翼岁。signal操作就是將條件隊(duì)列中的節(jié)點(diǎn)轉(zhuǎn)移到"鎖"的同步隊(duì)列中维哈，而不是喚醒等待線(xiàn)程（這里不就是類(lèi)似公平鎖了嗎？性能上應(yīng)該會(huì)差很多吧登澜？不知道為什么這么做，求指教）飘庄。

基本的await操作：

create and add new node to condition 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)檫@些操作只在當(dāng)前線(xiàn)程持有"鎖"時(shí)才會(huì)發(fā)生脑蠕，所以不需要考慮線(xiàn)程同步的問(wèn)題，只需要按順序?qū)⒚總€(gè)節(jié)點(diǎn)連接起來(lái)即可（在節(jié)點(diǎn)中用一個(gè)nextWaiter屬性）。transfer操作只需要將條件隊(duì)列中的第一個(gè)節(jié)點(diǎn)轉(zhuǎn)移到它所關(guān)聯(lián)的鎖的同步隊(duì)列尾部即可谴仙。

實(shí)現(xiàn)這些操作最復(fù)雜的部分是處理超時(shí)和中斷引起的等待取消迂求。一個(gè)取消操作如果與signal操作發(fā)生的時(shí)間非常接近的話(huà)，可能會(huì)產(chǎn)生競(jìng)爭(zhēng)晃跺，它們的競(jìng)爭(zhēng)結(jié)果符合Java內(nèi)建monitor的規(guī)范揩局。JSR133修訂版中規(guī)定，如果中斷發(fā)生在signal之前掀虎，那么await方法必須在被喚醒時(shí)拋出InterruptedException凌盯；如果中斷發(fā)生在signal之后，那么await必須無(wú)異常地返回烹玉，但是需要設(shè)置它的線(xiàn)程中斷狀態(tài)驰怎。

為了保證合適的處理順序，節(jié)點(diǎn)有一個(gè)”transferred“狀態(tài)（或者正在被transfer）（waitStatus里沒(méi)有詳細(xì)指出來(lái)二打，看代碼應(yīng)該是直接用初始狀態(tài)0代替了）县忌。signal和cancel都會(huì)去CAS這個(gè)狀態(tài)。如果signal失敗了（cancel先發(fā)生）继效，則它會(huì)繼續(xù)signal下一個(gè)節(jié)點(diǎn)（如果有的話(huà)）症杏；如果cancel失敗（signal先發(fā)生）瑞信，則放棄這次cancel厉颤，重新去獲取鎖（如果是超時(shí)引起的cancel，顯然喧伞，因?yàn)?em>signal在超時(shí)之前走芋，所以超時(shí)不成立；如果是中斷的話(huà)潘鲫，中斷狀態(tài)被設(shè)置就可以了（更底層的代碼已經(jīng)處理過(guò)了）翁逞，如上節(jié)所述）。后者可能會(huì)自旋很久：只有在signal過(guò)程完成之后溉仑，"cancelled"的節(jié)點(diǎn)才可以去重新請(qǐng)求鎖挖函。這種情況很少，而且使用了Thread.yield讓出取消節(jié)點(diǎn)的線(xiàn)程的CPU時(shí)間片浊竟，最理想的情況是正好被signal的節(jié)點(diǎn)的線(xiàn)程輪轉(zhuǎn)到怨喘，那么顯然自旋很快就會(huì)結(jié)束。雖然可以實(shí)現(xiàn)一些策略來(lái)幫助解決取消節(jié)點(diǎn)的自旋振定，但是這種情形太少見(jiàn)了必怜，沒(méi)有多大意義，反而會(huì)增加些額外的消耗后频。在其他任何情形下梳庆，都不會(huì)有自旋或yield暖途，所以在單核的情況下能夠保證不錯(cuò)的性能。

（這里看了下代碼膏执，詳細(xì)解釋一下驻售。首先對(duì)比一下lock和condition的實(shí)現(xiàn)。lock對(duì)應(yīng)acquire和release更米，condition對(duì)應(yīng)await和signal欺栗。acquire和await都有不響應(yīng)中斷（準(zhǔn)確地說(shuō)只是不拋異常，還是會(huì)喚醒并設(shè)置中斷狀態(tài)）和超時(shí)征峦、只響應(yīng)中斷（拋異常迟几，下同）、同時(shí)響應(yīng)中斷和超時(shí)三種版本眶痰，功能也基本相似瘤旨。但是release的實(shí)現(xiàn)與signal的實(shí)現(xiàn)有所不同，release直接喚醒等待線(xiàn)程竖伯，如果將要喚醒的節(jié)點(diǎn)因?yàn)槌瑫r(shí)或中斷取消了或正在取消存哲，其實(shí)線(xiàn)程已經(jīng)是運(yùn)行狀態(tài)了，可以忽略這次release七婴；而signal有個(gè)transfer階段祟偷，將需要signal的節(jié)點(diǎn)轉(zhuǎn)移到Lock的同步隊(duì)列中，而await可能會(huì)發(fā)生的cancel（超時(shí)和中斷）也有一個(gè)transfer階段（也是轉(zhuǎn)移節(jié)點(diǎn)到同步隊(duì)列）打厘，這兩個(gè)transfer顯然會(huì)產(chǎn)生競(jìng)爭(zhēng)（如上節(jié)所述）修肠，所以不能像release那樣直接忽略就可以了（ParkSupport.unpark一個(gè)活動(dòng)的線(xiàn)程會(huì)立即返回，但是可能會(huì)導(dǎo)致下次的park被抵消掉户盯，所以park需要自旋（見(jiàn)3.2））嵌施。

4. 使用

AQS類(lèi)將上述的功能結(jié)合在一起并用"模板模式"作為所有"同步器"的基礎(chǔ)類(lèi)。子類(lèi)只需要實(shí)現(xiàn)狀態(tài)的檢查和更新操作來(lái)控制acquire和release即可莽鸭。但是吗伤，這些子類(lèi)不會(huì)直接繼承AQS，因?yàn)锳QS類(lèi)有一些公開(kāi)的方法硫眨，這些方法用來(lái)控制acquire和release的策略足淆，不能直接暴露給普通用戶(hù)。所以J.U.C中的"同步器"都聲明了一個(gè)繼承AQS的內(nèi)部類(lèi)礁阁，"同步器"的功能用這個(gè)內(nèi)部類(lèi)來(lái)代理巧号。這樣不僅對(duì)用戶(hù)屏蔽掉了復(fù)雜的實(shí)現(xiàn)細(xì)節(jié)，而且還可以根據(jù)需要定義任意名稱(chēng)姥闭、任意功能的方法丹鸿。

例如，下面是個(gè)最小的Mutex類(lèi)棚品，用狀態(tài)是否為0來(lái)控制鎖的狀態(tài)卜高。

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); }

完整版本的Mutex例子和用法可以在J2SE文檔中找到弥姻，當(dāng)然可能會(huì)有一些變化。例如掺涛，tryAcquire可能會(huì)使用"test-and-test-and-set"來(lái)更新?tīng)顟B(tài)懂更。

你可能會(huì)有些驚訝一個(gè)性能敏感的"同步器"竟然會(huì)用"代理"和"虛方法"的組合方式來(lái)實(shí)現(xiàn)（代碼比較繁瑣）岗仑。但實(shí)際上，這些都是現(xiàn)代動(dòng)態(tài)編譯器長(zhǎng)時(shí)間聚焦的面向?qū)ο缶幊痰姆椒ň娉啤Ｋ麄兩瞄L(zhǎng)于優(yōu)化并消弭掉這些性能損耗伞广，尤其在這些被頻繁使用的"同步器"上拣帽。

AQS類(lèi)還提供了很多方法可以幫助各種"同步器"控制同步策略。例如嚼锄，它同時(shí)支持了不響應(yīng)中斷（準(zhǔn)確地說(shuō)只是不拋異常减拭，還是會(huì)喚醒并設(shè)置中斷狀態(tài)）和超時(shí)、只響應(yīng)中斷（拋異常区丑，下同）拧粪、同時(shí)響應(yīng)中斷和超時(shí)三種版本的acquire方法。還有沧侥，雖然討論到現(xiàn)在的一直是排他鎖可霎，但是AQS同樣包含了一系列支持共享鎖的方法（如acquireShared和releaseShared），它們使得可以允許多個(gè)線(xiàn)程acquire宴杀，并且可以級(jí)聯(lián)地喚醒多個(gè)等待的線(xiàn)程癣朗。

雖然通常不會(huì)直接序列化一個(gè)"同步器"，但是在配合構(gòu)成其他類(lèi)例如線(xiàn)程安全的集合類(lèi)的時(shí)候旺罢，序列化是很有必要的旷余。AQS類(lèi)和ConditionObject類(lèi)提供了一些方法序列化"同步器"的狀態(tài)，但是沒(méi)有序列化阻塞的線(xiàn)程或者其他的一些瞬時(shí)狀態(tài)扁达。實(shí)際上正卧，大部分的"同步器"反序列化的時(shí)候都是重置狀態(tài)到初始值，這與內(nèi)建monitor的反序列化策略一致：總是反序列化到未鎖的狀態(tài)罩驻。

4.1 公平性

盡管AQS是基于先進(jìn)先出隊(duì)列的穗酥，但并不一定是公平的。在acquire入同步隊(duì)列之前會(huì)先tryAcquire惠遏。所以如果恰好在解鎖的過(guò)程中有一個(gè)線(xiàn)程tryAcquire砾跃，則會(huì)“竊取”這次加鎖的機(jī)會(huì)。

這種策略叫做"barging FIFO"节吮，通吵楦撸可以提供更高的吞吐量。它主要利用了"解鎖過(guò)程"這一段時(shí)間透绩，在這期間允許其他線(xiàn)程"竊取"鎖翘骂，無(wú)需入隊(duì)出隊(duì)壁熄，從而減少了整體的入隊(duì)出隊(duì)時(shí)間。這種策略在每個(gè)線(xiàn)程只需要短暫地持有"鎖"的應(yīng)用中尤其有效碳竟，相反地草丧，如果每個(gè)線(xiàn)程需要持有很長(zhǎng)時(shí)間的"鎖"，這種策略則會(huì)造成很多"解鎖"失敗的情況莹桅，可能會(huì)起負(fù)面作用昌执。一個(gè)簡(jiǎn)單的衡量方法是看平均"解鎖時(shí)間"與平均"持鎖時(shí)間"的比例，如果大于1的話(huà)這種策略效果顯著诈泼。不過(guò)這種策略也會(huì)產(chǎn)生一個(gè)問(wèn)題懂拾，如果新線(xiàn)程進(jìn)入的頻率太快，則可能會(huì)造成同步隊(duì)列的head節(jié)點(diǎn)陷入"unpark-acquire failed-park"循環(huán)中铐达，永遠(yuǎn)拿不到鎖岖赋，造成“饑餓”。在多核環(huán)境下瓮孙，這種"短暫持有鎖"的場(chǎng)景中唐断，解鎖期間出現(xiàn)多次"竊取"和release是很平常的。而即使是在那些非常耗時(shí)的IO操作的"鎖"中衷畦，實(shí)際上也沒(méi)有辦法完全避免"竊取"和"饑餓"栗涂。（但是，在多核環(huán)境下祈争，"barging"的策略顯然可以更高效地利用CPU斤程，不至于讓一個(gè)核在解鎖的過(guò)程中，其他核只能干等待（假設(shè)沒(méi)有其他應(yīng)用的情況下））

20181016041723.png

當(dāng)需要嚴(yán)格控制公平性的時(shí)候菩混，處理起來(lái)反而簡(jiǎn)單一些忿墅。程序員可以定義tryAcquire方法，如果當(dāng)前線(xiàn)程恰好是head節(jié)點(diǎn)中的線(xiàn)程才可以acquire沮峡，這樣就避免了其他線(xiàn)程來(lái)"竊取"鎖疚脐。

另一種更快的、更寬松的變種是當(dāng)隊(duì)列（暫時(shí)）是空的時(shí)候tryAcquire也可以成功邢疙。這種情況下棍弄，很多線(xiàn)程會(huì)同時(shí)遇到空隊(duì)列，并且去同時(shí)acquire疟游，通常它們中至少有一個(gè)不用出隊(duì)入隊(duì)呼畸。J.U.C中的所有"同步器"在公平模式下都是采用這種策略。

雖然"公平鎖"在實(shí)踐中看起來(lái)很有用颁虐，但其實(shí)也沒(méi)有辦法徹底保證公平蛮原，因?yàn)镴LS并沒(méi)有提供線(xiàn)程調(diào)度層面的保證。例如另绩，盡管使用一個(gè)嚴(yán)格公平的”鎖“儒陨，但是如果沒(méi)有互相阻塞的話(huà)花嘶，JVM也可以簡(jiǎn)單地順序執(zhí)行一個(gè)線(xiàn)程集合。（譯者注：我猜作者想說(shuō)的是：如果沒(méi)有阻塞的話(huà)蹦漠，請(qǐng)求公平鎖的線(xiàn)程的運(yùn)行順序其實(shí)是由JVM決定的（因?yàn)闆](méi)有入等待隊(duì)列）椭员，而JVM執(zhí)行順序是不確定的，有可能后請(qǐng)求的線(xiàn)程反而先執(zhí)行了笛园，從這個(gè)角度看并不“公平”）
在實(shí)踐中拆撼，單核環(huán)境下，這些線(xiàn)程都按時(shí)間片執(zhí)行喘沿，如果某個(gè)線(xiàn)程持有一個(gè)排它鎖，它將會(huì)被暫時(shí)切換回來(lái)竭贩，只是為了釋放鎖并且這個(gè)時(shí)候才知道是否有其他線(xiàn)程在請(qǐng)求鎖蚜印，因此線(xiàn)程調(diào)度實(shí)際上進(jìn)一步增加了鎖的”空閑“時(shí)間。（譯者注：類(lèi)似之前討論的”解鎖“時(shí)間留量，這里是調(diào)度時(shí)間窄赋，當(dāng)其他線(xiàn)程去請(qǐng)求鎖的時(shí)候，實(shí)際上可能持有鎖的線(xiàn)程已經(jīng)完成所需的操作楼熄，不再需要持有鎖忆绰，但是因?yàn)闆](méi)有調(diào)度到它，就使得其他線(xiàn)程還需要去阻塞）
鎖的公平性設(shè)置在多核的環(huán)境下影響更大可岂，因?yàn)槎嗪酥g的交互比較多错敢，從而更容易“barging”，而公平鎖禁用了“barging”缕粹，性能影響更大稚茅。

盡管在"短暫持鎖"和競(jìng)爭(zhēng)激烈的場(chǎng)景中，公平鎖的性能可能比較差平斩，但是在其他場(chǎng)景下亚享，表現(xiàn)得都不錯(cuò)。例如绘面，在"長(zhǎng)期持鎖"的場(chǎng)景中欺税，"barging FIFO"幾乎沒(méi)有性能優(yōu)勢(shì)，反而會(huì)增加"饑餓"的風(fēng)險(xiǎn)揭璃，而公平鎖則無(wú)此虞晚凿。用戶(hù)可以根據(jù)具體場(chǎng)景選擇適合的"同步器"類(lèi)型。

4.2 鎖

這里是J.U.C中所有"同步器"的概覽塘辅。

ReentrantLock類(lèi)使用同步狀態(tài)記錄lock次數(shù)（遞歸）晃虫。當(dāng)鎖被acquired，它也會(huì)記錄當(dāng)前持有鎖的線(xiàn)程的id扣墩，用來(lái)檢查遞歸調(diào)用哲银，或者請(qǐng)求解鎖的線(xiàn)程是否與當(dāng)前線(xiàn)程一致扛吞。這個(gè)類(lèi)還提供了ConditionObject類(lèi)和一些檢查和更新鎖狀態(tài)的方法。這個(gè)類(lèi)也提供兩種類(lèi)似的鎖--公平和非公平的荆责。

ReentrantReadWriteLock類(lèi)使用同步狀態(tài)的16位記錄讀鎖的狀態(tài)滥比，剩下的16位記錄寫(xiě)鎖的狀態(tài)。它的實(shí)現(xiàn)與ReentrantLock類(lèi)基本一致做院。ReadLock類(lèi)使用acquireShared方法支持多個(gè)讀者盲泛。

Semaphore類(lèi)使用同步狀態(tài)記錄一個(gè)計(jì)數(shù)。它定義了acquireShared方法去減少這個(gè)計(jì)數(shù)键耕，或者當(dāng)計(jì)數(shù)非正時(shí)寺滚，阻塞當(dāng)前線(xiàn)程；tryRelease方法增加計(jì)數(shù)屈雄，如果計(jì)數(shù)為正村视，則可能解鎖當(dāng)前線(xiàn)程。

CountDownLatch類(lèi)使用同步狀態(tài)記錄一個(gè)計(jì)數(shù)酒奶，當(dāng)計(jì)數(shù)為0時(shí)所有等待線(xiàn)程acquire成功蚁孔。

FutureTask類(lèi)使用同步狀態(tài)表示Future的運(yùn)行狀態(tài)。用release設(shè)置或者取消future惋嚎，用acquire喚醒等待future值的線(xiàn)程杠氢。

SynchronousQueue類(lèi)使用內(nèi)建的"等待節(jié)點(diǎn)"匹配生產(chǎn)者和消費(fèi)者。它使用同步狀態(tài)允許一個(gè)生產(chǎn)者在一個(gè)消費(fèi)者消費(fèi)了一個(gè)item之后繼續(xù)生產(chǎn)下一個(gè)item另伍，反之亦然鼻百。

用戶(hù)當(dāng)然也可以根據(jù)J.U.C的類(lèi)實(shí)現(xiàn)自定義的鎖。例如质况，很多曾經(jīng)被考慮過(guò)但是沒(méi)有被采納進(jìn)J.U.C的類(lèi)愕宋，它們提供了與 WIN32 events, binary latches, centrally managed locks, and tree-based barriers 類(lèi)似的語(yǔ)義和功能。

5.性能

雖然除排他鎖之外结榄，J.U.C也提供了很多其他風(fēng)格的"同步器",但是"排他鎖"的性能是最容易衡量和對(duì)比的中贝。有很多方法都可以衡量"排他鎖"的性能。下面的實(shí)驗(yàn)揭示了"排他鎖"的耗時(shí)和吞吐量臼朗。

在每個(gè)測(cè)試中邻寿，每個(gè)線(xiàn)程都重復(fù)地去更新一個(gè)nextRandom(int seed)產(chǎn)生的偽隨機(jī)數(shù)：

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

在線(xiàn)程的每個(gè)更新循環(huán)中，線(xiàn)程有S的概率去更新一個(gè)加了排它鎖的共享的值视哑，或者更新一個(gè)無(wú)鎖的局部變量（1-S）绣否。這樣會(huì)使得需要加鎖的代碼塊很小，盡量減少無(wú)關(guān)的影響（譬如線(xiàn)程正持有鎖挡毅，但是被其他線(xiàn)程搶占了CPU）蒜撮。這個(gè)隨機(jī)數(shù)方法提供了兩個(gè)功能：1.可以用來(lái)決定是否需要加鎖；2.可以使得循環(huán)的代碼不會(huì)被JVM優(yōu)化。

該實(shí)驗(yàn)會(huì)比較四種鎖：內(nèi)建monitor（用synchronized關(guān)鍵字）段磨；Mutex（使用簡(jiǎn)單的Mutex類(lèi)取逾，就像前面提到的那樣）；Reentrant（使用ReentrantLock類(lèi)）苹支；和Fair（使用ReentrantLock類(lèi)的公平模式）砾隅。所有的測(cè)試基于J2SE 1.5 JDK 的 build46 版本（與beta2版本幾乎完全相同）的"server"模式。測(cè)試程序會(huì)在正式收集數(shù)據(jù)前零競(jìng)爭(zhēng)地運(yùn)行20次债蜜，消除"熱身"的影響晴埂。除了公平模式只會(huì)循環(huán)一百萬(wàn)次以外，其他測(cè)試中每個(gè)線(xiàn)程都會(huì)循環(huán)一千萬(wàn)次寻定。

測(cè)試程序跑在四個(gè)x86的機(jī)器和四個(gè)UltraSparc的機(jī)器上儒洛。所有x86機(jī)器都運(yùn)行基于RedHat NPTL-based 2.4內(nèi)核的Linux系統(tǒng)。所有的UltraSparc機(jī)器都運(yùn)行Solaris-9系統(tǒng)狼速。所有系統(tǒng)在測(cè)試時(shí)都沒(méi)有其他負(fù)載晶丘。"4P"的意思是支持超頻，可以將雙核的機(jī)器表現(xiàn)得像四核一樣唐含。這里沒(méi)有試圖去統(tǒng)一這些機(jī)器配置。因?yàn)橹饕吹氖窍鄬?duì)耗時(shí)沫浆。

20181016041745.png

5.1 耗時(shí)

零競(jìng)爭(zhēng)的耗時(shí)只用一個(gè)線(xiàn)程去測(cè)量（避免任何競(jìng)爭(zhēng)）捷枯，用S1（S=1，下同）的耗時(shí)減去S0的耗時(shí)专执。表2展示了這些數(shù)據(jù)淮捆。Mutex類(lèi)的S0與S1的差距是最小的。ReentrantLoc的額外耗時(shí)在于需要記錄當(dāng)前線(xiàn)程和錯(cuò)誤檢查本股，公平模式的額外耗時(shí)在于檢查隊(duì)列是否為空攀痊。

表2也展示了tryAcquire和內(nèi)建monitor的"fast-path"之間的耗時(shí)對(duì)比。這里的區(qū)別主要反映了不同機(jī)器上不同鎖使用的原子操作指令和內(nèi)存屏障的耗時(shí)拄显。在多核環(huán)境下苟径，這些指令（的耗時(shí)）會(huì)顯著多于其他指令。內(nèi)建monitor與其他鎖之間的區(qū)別主要是內(nèi)建monitor在加鎖和解鎖的時(shí)候都使用CAS躬审，而基于AQS的其他鎖只在加鎖時(shí)CAS棘街，而在release時(shí)使用volatile來(lái)保證狀態(tài)的可見(jiàn)性即可。它們的相對(duì)和絕對(duì)耗時(shí)在不同的機(jī)器上可能會(huì)有不同承边。

20181016041811.png

表3展示了在另一個(gè)極端（S1遭殉，256個(gè)同步線(xiàn)程）的情況下，每次加鎖的時(shí)間博助。在這種充分競(jìng)爭(zhēng)的情況下险污，"barging-FIFO"比內(nèi)建monitor大約少了一個(gè)數(shù)量級(jí)的耗時(shí)（而且吞吐量也更高）比公平鎖少了兩個(gè)數(shù)量級(jí)的耗時(shí)。這顯示了在競(jìng)爭(zhēng)激烈的環(huán)境下"barging-FIFO"仍然可以提供相對(duì)高效的處理性能富岳。

20181016041829.png

表3還顯示了雖然線(xiàn)程切換只需要很少的內(nèi)部耗時(shí)蛔糯，但是在公平鎖中卻幾乎完全決定了鎖的性能拯腮。列出的（公平鎖的）耗時(shí)與不同平臺(tái)上的阻塞線(xiàn)程和喚醒線(xiàn)程耗時(shí)成正比。而且渤闷，后續(xù)的實(shí)驗(yàn)（只在4P上做的）還發(fā)現(xiàn)在"短暫持鎖"的情況下疾瓮，公平鎖的整體耗時(shí)波動(dòng)性很小。每個(gè)線(xiàn)程的運(yùn)行時(shí)間被記錄下來(lái)作為一個(gè)粗略的衡量波動(dòng)性的變量飒箭。在"4P"上公平鎖的標(biāo)準(zhǔn)差與平均值的比值為0.7%狼电，而ReentrantLock是6.0%。作為對(duì)比弦蹂，模擬下"長(zhǎng)期持鎖"的情況肩碟，每個(gè)線(xiàn)程在持鎖過(guò)程中生成16k個(gè)隨機(jī)數(shù)⊥勾唬總的來(lái)說(shuō)運(yùn)行時(shí)間沒(méi)什么差別（公平模式9.79s削祈，非公平模式9.72s）。公平模式的波動(dòng)性還是很小脑漫，標(biāo)準(zhǔn)差與平均值的比值為0.1%髓抑，而非公平模式是29.5%。

5.2 吞吐量

大部分的"同步器"使用場(chǎng)景都是在零競(jìng)爭(zhēng)與飽和競(jìng)爭(zhēng)之間變化的优幸《峙模可以在兩個(gè)維度上去測(cè)試：1.保持線(xiàn)程集合不變，調(diào)整線(xiàn)程的同步概率S网杆；2.保持同步概率不變羹饰，調(diào)整線(xiàn)程集合。為了量化這些影響碳却，我們用ReentrantLock做了很多不同同步概率S或不同線(xiàn)程集合的測(cè)試队秩。下面的圖表用了一個(gè)slowdown指標(biāo)：

20181016041800.png

t是總的執(zhí)行時(shí)間，b是沒(méi)有競(jìng)爭(zhēng)或者同步的基線(xiàn)昼浦，n是線(xiàn)程數(shù)馍资。p是核數(shù)，S是同步概率关噪。slowdown值是觀測(cè)到的執(zhí)行時(shí)間與用Amdahl定律計(jì)算出的對(duì)于執(zhí)行串行和并行組合任務(wù)的理想執(zhí)行時(shí)間的比值（沒(méi)有同步耗費(fèi)迷帜，線(xiàn)程阻塞等）。但是色洞，在非常低的競(jìng)爭(zhēng)下戏锹，有一些任務(wù)結(jié)果表現(xiàn)得比最理想的狀態(tài)還要好一點(diǎn)，可能是因?yàn)樨灤┗€(xiàn)與測(cè)試的一些優(yōu)化手段火诸，管道等锦针。

這些圖取的是原始值的對(duì)數(shù)值（以2為底）。使用的同步概率從1/128（0.008）到1，線(xiàn)程數(shù)從1到1024奈搜。

通常來(lái)說(shuō)悉盆，在單核環(huán)境下，性能隨著競(jìng)爭(zhēng)的加劇而不是線(xiàn)程數(shù)的增加而下降馋吗。多核環(huán)境下焕盟，性能隨競(jìng)爭(zhēng)加劇下降得會(huì)更快。多核環(huán)境下的性能圖表顯示宏粤，性能會(huì)很快到達(dá)一個(gè)頂峰脚翘，雖然只有很少的線(xiàn)程在競(jìng)爭(zhēng)。這反映了一個(gè)過(guò)渡的性能區(qū)域绍哎，在這個(gè)區(qū)域內(nèi)来农，"barging"和"signal"有相同的機(jī)會(huì)獲取到鎖，因此頻繁地互相阻塞崇堰。在大部分情況下沃于，這之后是個(gè)比較平滑的曲線(xiàn)，因?yàn)?鎖"基本上都不可用了海诲，造成類(lèi)似于單核的串行運(yùn)行繁莹，在多核的機(jī)器上到這一節(jié)點(diǎn)要晚一點(diǎn)。還可以看到特幔，例子中競(jìng)爭(zhēng)飽和的性能圖表顯示出在更少的處理器的環(huán)境下相對(duì)更低的slowdown值蒋困。

從實(shí)驗(yàn)結(jié)果可以看出，如果可以?xún)?yōu)化park/unpark操作敬辣，使耗費(fèi)在線(xiàn)程切換上的時(shí)間減少的話(huà)，應(yīng)該可以提高框架的性能零院。而且溉跃，如果可以?xún)?yōu)化多核環(huán)境中"短暫持鎖"且競(jìng)爭(zhēng)激烈場(chǎng)景下的行為，盡可能避免失敗的話(huà)告抄，也能提供一定的性能提升撰茎。雖然適配不同場(chǎng)景下的"自旋"是非常困難的，但是用戶(hù)可以根據(jù)不同場(chǎng)景利用J.U.C來(lái)構(gòu)建自定義的鎖打洼，從而解決特定的問(wèn)題龄糊。

20181016041745.png

20181016042639.png

20181016041857.png

20181016041917.png

20181016041939.png

20181016042002.png

20181016042014.png

20181016042030.png

20181016042042.png