?

接上一篇：http://caoyaojun1988-163-com.iteye.com/admin/blogs/1279097

?

3.3 隊(duì)列

? ? ?框架的核心是維護(hù)阻塞線程的隊(duì)列，隊(duì)列的策略是先進(jìn)先出（FIFO），因此，該框架不支持基于優(yōu)先級(jí)的同步

? ? ? 一直以來，對(duì)于同步隊(duì)列的最合適的選擇是無阻塞的數(shù)據(jù)結(jié)構(gòu)有不小的爭(zhēng)議，這種數(shù)據(jù)結(jié)構(gòu)本身并不需要使用較低級(jí)別的鎖來構(gòu)造。其中有兩個(gè)主要的觀點(diǎn)：Mellor-Crummey與Scott的變體鎖(MCS) [9]和 Craig, Landin, 和Hagersten的變體鎖 (CLH)[5][8][10].從歷史上看，CLH鎖僅僅被用于自旋鎖，然而，在同步框架中使用它們比MCS似乎更適合，因?yàn)樗麄兏菀滋幚砣∠统瑫r(shí)，因此我們選擇它作為基礎(chǔ)。雖然最終的設(shè)計(jì)遠(yuǎn)遠(yuǎn)偏離了CLH的設(shè)計(jì)結(jié)構(gòu)；

? ? ?CLH隊(duì)列與經(jīng)典的隊(duì)列不同，其入隊(duì)和出隊(duì)操作與使用鎖是緊密聯(lián)系在一起的。它是一個(gè)鏈表，通過兩個(gè)可原子更新的節(jié)點(diǎn)頭部和尾部訪問隊(duì)列，雙方最初都指向一個(gè)虛擬節(jié)點(diǎn)；

? ? ?一個(gè)新的節(jié)點(diǎn)入隊(duì)列的時(shí)候，使用下面的原子操作：

?

?

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

?

?

? ? ?每個(gè)節(jié)點(diǎn)的釋放狀態(tài)域保存其前一個(gè)節(jié)點(diǎn)的地址。所以，一個(gè)自旋鎖（spinlock）的“自旋”的樣子如下：

?

?

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

?

?

? ? ?當(dāng)自旋簡(jiǎn)單的設(shè)置了head域指向node時(shí)，出隊(duì)列（dequeue）操作如下：

?

?

head = node;

? ? ?CLH鎖的優(yōu)勢(shì)是入隊(duì)和出隊(duì)速度快，無鎖，并暢通無阻（即使在競(jìng)爭(zhēng)的情況下，插入操的線程永遠(yuǎn)獲得執(zhí)行的權(quán)限），并且在檢測(cè)是否有線程在排隊(duì)是很快（只需要檢測(cè)頭尾是否相同）、釋放狀態(tài)是分散的，可以減少內(nèi)存沖突；

?

? ? ?CLH鎖的原始版本并不是雙向連接。自旋鎖里，PRED變量作為一個(gè)域來保存。然而， Scott 和Scherer[10]展示了，通過明確地維護(hù)節(jié)點(diǎn)里的pre域，CLH鎖是可以處理超時(shí)和其他形式的取消的。如果一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)被取消，該節(jié)點(diǎn)可以滑動(dòng)使用前一個(gè)節(jié)點(diǎn)的狀態(tài)域；

? ? ?要使用CLH隊(duì)列構(gòu)建阻塞同步器，主要的修改點(diǎn)是：一個(gè)節(jié)點(diǎn)必須提供一種有效的方式找到下一個(gè)節(jié)點(diǎn)。自旋鎖的時(shí)候，由于僅僅在它被下一個(gè)節(jié)點(diǎn)通知的時(shí)候在改變它的狀態(tài)；所以找個(gè)下一個(gè)節(jié)點(diǎn)的鏈接是不必要的；但在阻塞同步器中，一個(gè)節(jié)點(diǎn)需要明確地喚醒（unpark）它的下一個(gè)節(jié)點(diǎn)。

? ? ?AbstractQueuedSynchronizer隊(duì)列節(jié)點(diǎn)包含指向下一個(gè)節(jié)點(diǎn)的域。但因?yàn)闆]有合適的技術(shù)可以對(duì)雙向鏈表節(jié)點(diǎn)實(shí)現(xiàn)無鎖的原子插入，即便使用compareAndSet。所以這個(gè)連接的操作并不包含在原子插入的操作里面;在插入操作后，它被簡(jiǎn)單地賦值，操作如下：

?

pred.next = node;

找到下一節(jié)點(diǎn)的路徑只是作為一個(gè)優(yōu)化的路徑。如果一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)通過next域判斷不存在（或者取消），總是從列表的尾部開始使用PRED域做反向遍歷準(zhǔn)確檢查是否真的不存在。

?

? ? ?第二個(gè)修改點(diǎn)是使用每個(gè)節(jié)點(diǎn)的狀態(tài)域來控制阻塞而不是自旋。在同步框架中，一個(gè)隊(duì)列中的線程，僅僅在它通過了一個(gè)定義在具體子類中tryAcquire方法，獲取到鎖才返回；這樣僅僅一個(gè)“釋放”位就不夠了。同時(shí)仍然需要控制，以確保活動(dòng)線程只有當(dāng)它在隊(duì)列的頭部是才能調(diào)用tryAcquire;雖然在這種情況下，它任然可能會(huì)獲取失敗，并（重新）阻塞。這個(gè)可以通過檢查當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)來確認(rèn)，而不需要查看每個(gè)節(jié)點(diǎn)的狀態(tài)標(biāo)志；與自旋鎖不同的是，讀頭節(jié)點(diǎn)操作沒有很多內(nèi)存沖突。當(dāng)然，取消狀態(tài)仍然必須保存在狀態(tài)域里面。

? ? ?隊(duì)列節(jié)點(diǎn)的狀態(tài)域也用于避免不必要的park和unpark調(diào)用。雖然他們可以避免在Java、JVM和操作系統(tǒng)之間交互開銷，比阻塞原語快。一個(gè)線程調(diào)用park之前，先設(shè)置一個(gè)“信號(hào)”位，然后調(diào)用park前再次重新檢查同步和節(jié)點(diǎn)狀態(tài)。一個(gè)釋放線程清除狀態(tài)。這樣可以減少無謂地嘗試，這些block操作的開銷是不值得的，特別是浪費(fèi)時(shí)間去與其他競(jìng)爭(zhēng)線程競(jìng)爭(zhēng)獲取鎖，同時(shí)這也避免了釋放線程確定其繼任執(zhí)行者的時(shí)間，因?yàn)槔^任者已經(jīng)設(shè)置的信號(hào)位；如果信號(hào)沒有一起被取消，就避免了必須遍歷多個(gè)節(jié)點(diǎn)，直到next域?yàn)閚ull的開銷。

? ? ?也許用于同步框架的CLH變種鎖和其他場(chǎng)景之間的主要區(qū)別是，它的垃圾回收機(jī)制通過管理節(jié)點(diǎn)的實(shí)現(xiàn)，從而避免了復(fù)雜性和開銷。然而，當(dāng)他們永遠(yuǎn)不會(huì)再用到的時(shí)候GC還負(fù)責(zé)講鏈接到的域賦值為null，通過簡(jiǎn)單的出隊(duì)列操作即可實(shí)現(xiàn)，否則，未使用的節(jié)點(diǎn)仍然可以訪問，致使他們無法收回。

? ? ?當(dāng)然還有一些優(yōu)化調(diào)整，包括延遲初始化：CLH隊(duì)列在第一次競(jìng)爭(zhēng)發(fā)生時(shí)才初始話所需的虛擬節(jié)點(diǎn)，這些詳細(xì)描述在J2SE1.5版本的源代碼的文檔里。

? ? 忽略這些細(xì)節(jié)，實(shí)現(xiàn)一個(gè)具有基本操作（互斥，不可中斷，超時(shí)）的一般形式是：

?

if (!tryAcquire(arg)) {
    node = create and enqueue new node;//創(chuàng)建一個(gè)新的節(jié)點(diǎn)，入隊(duì)列
    pred = node's effective predecessor;//pred 執(zhí)行當(dāng)前節(jié)點(diǎn)的前一個(gè)有效節(jié)點(diǎn)
    while (pred is not head node || !tryAcquire(arg)) {//當(dāng)前一個(gè)節(jié)點(diǎn)不是頭節(jié)點(diǎn)或者獲取鎖失敗
        if (pred's signal bit is set)//前一個(gè)節(jié)點(diǎn)的信號(hào)位被設(shè)置
            park();//阻塞自己
        else
            compareAndSet pred's signal bit to true;//講前一個(gè)節(jié)點(diǎn)的信號(hào)量設(shè)置位true
       pred = node's effective predecessor;//執(zhí)行當(dāng)前節(jié)點(diǎn)的前一個(gè)有效節(jié)點(diǎn)
    }
   head = node;
}

?

?

一個(gè)釋放操作如下:

?

if (tryRelease(arg) && head node's signal bit is set) {
	compareAndSet head's signal bit to false;//head節(jié)點(diǎn)信號(hào)位設(shè)置位false
	unpark head's successor, if one exists//喚醒head節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)
}

? ??循環(huán)迭代的次數(shù)，取決于tryAcquire性質(zhì)，因此，在沒有取消的情況下，獲取和釋放的時(shí)間都是O（1），跨線程的開銷，和任何花費(fèi)在基于park的OS的線程調(diào)度都可以忽略；

?

? ? ?對(duì)取消操作的支持，主要是需要在每次循環(huán)中park操作返回之后檢查中斷或超時(shí)，由于超時(shí)或中斷被取消的線程負(fù)責(zé)設(shè)置節(jié)點(diǎn)的狀態(tài)，并且unparks它的后繼者，所以它可能會(huì)重置鏈接；取消操作，可能會(huì)確定的前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)，并且重置狀態(tài)，遍歷的時(shí)間復(fù)雜度是O（N）（其中n是隊(duì)列長(zhǎng)度）。因?yàn)橐粋€(gè)線程永遠(yuǎn)不會(huì)為取消而被block，所以鏈接和狀態(tài)往往很快重新穩(wěn)定。

?

3.4 條件隊(duì)列

?

? ? ?同步框架提供了一個(gè)維護(hù)互斥同步的同步器和供Lock接口使用的ConditionObject的類。許多condition對(duì)象可能會(huì)關(guān)聯(lián)到一個(gè)鎖對(duì)象，提供經(jīng)典的基于監(jiān)視器（monitor）風(fēng)格的等待（await），、喚醒（signal）和喚醒全部（signalAll）的操作，包括超時(shí)，以及一些檢查和監(jiān)測(cè)方法，

? ? ?通過操縱一些設(shè)計(jì)決策,ConditionObject類可以有效地與其他同步操作相結(jié)合。這個(gè)類僅僅支持java風(fēng)格的監(jiān)視器訪問規(guī)則，既是僅僅當(dāng)當(dāng)前線程的鎖的條件滿足時(shí)操作才是允許的（請(qǐng)參閱[4]替代方案的討論）；因此，一個(gè)ConditionObject關(guān)聯(lián)到ReentrantLock的方式與內(nèi)置的監(jiān)視器一樣（通過Object.wait等），唯一的不同是方法名稱，額外的功能，而事實(shí)上，用戶可以在每個(gè)鎖上申明多個(gè)條件。

? ? ?一個(gè)ConditionObject與同步器使用相同的內(nèi)部隊(duì)列節(jié)點(diǎn)，但它們維護(hù)在一個(gè)單獨(dú)的條件隊(duì)列中；喚醒操作通過從條件隊(duì)列轉(zhuǎn)移到鎖隊(duì)列來實(shí)現(xiàn)；一個(gè)線程已經(jīng)重新獲取了鎖，不需要喚醒已經(jīng)喚醒的線程；

? ? ?基本等待（await）操作是：

?

create and add new node to condition queue;//新建一個(gè)node，添加到條件隊(duì)列中
release lock;//釋放鎖
block until node is on lock queue; //阻塞直到node轉(zhuǎn)移到鎖隊(duì)列上
re-acquire lock; //重新獲取鎖

? ? 喚醒的操作是：

?

?

將條件隊(duì)列的第一個(gè)節(jié)點(diǎn)轉(zhuǎn)移到鎖隊(duì)列中；

? ? ?因?yàn)檫@些操作只有持有鎖的時(shí)候才允許，因此可以使用有序鏈表隊(duì)列（使用節(jié)點(diǎn)的nextWaiter域）維護(hù)條件隊(duì)列；轉(zhuǎn)移操作簡(jiǎn)單取出條件隊(duì)列中的第一個(gè)節(jié)點(diǎn)，然后使用CLH的插入操作添加到鎖隊(duì)列；

?

? ? ?實(shí)現(xiàn)這些操作最復(fù)雜的地方在于處理因?yàn)閍wait操作超時(shí)或Thread.interrupt而引起的取消操作。取消操作和喚醒幾乎在同時(shí)發(fā)生，產(chǎn)生一個(gè)競(jìng)爭(zhēng)，其結(jié)果符合內(nèi)置監(jiān)視器的規(guī)范；在修訂JSR133的時(shí)候，要求如果一個(gè)中斷信號(hào)在喚醒之前發(fā)生，那么等待的方法必須重新獲取鎖后，拋出InterruptedException。但是如果一個(gè)中斷信號(hào)在喚醒之后，則該方法必須返回，不拋出異常，同時(shí)線程設(shè)置為中斷狀態(tài)。

? ? ?為了維持正常的順序，隊(duì)列中的節(jié)點(diǎn)有一個(gè)狀態(tài)域記錄節(jié)點(diǎn)是否已經(jīng)轉(zhuǎn)移（或者已經(jīng)在執(zhí)行中）。喚醒和取消都使用compareAndSet來嘗試更新狀態(tài)。如果一個(gè)喚醒操作競(jìng)爭(zhēng)失敗，如果存在下一個(gè)節(jié)點(diǎn)，將轉(zhuǎn)移隊(duì)列中的下一個(gè)節(jié)點(diǎn)。如果取消操作競(jìng)爭(zhēng)失敗，就必須中止轉(zhuǎn)移，然后等待重新獲取鎖。后一種情況，可能引入了一個(gè)無限自旋。直到一個(gè)節(jié)點(diǎn)已成功轉(zhuǎn)移到鎖隊(duì)列中，否則一個(gè)被取消的等待不能重新開始獲取鎖，所以必須自旋等待被喚醒的線程在CLH隊(duì)列上執(zhí)行compareAndSet類型的插入成功。在這里的自旋是罕見的，通過Thread.yield暗示一個(gè)理想喚醒的線程調(diào)度執(zhí)行。雖然這里可以為取消插入節(jié)點(diǎn)實(shí)現(xiàn)一個(gè)幫助策略，但是這種場(chǎng)景是非常罕見，并且意味著增加開銷。在其他所有的場(chǎng)景下，所有的基本機(jī)制，都不會(huì)使用自旋或yields，來保持合理的單處理器的性能。

?

原文見第一篇的附件

?

下一篇：http://caoyaojun1988-163-com.iteye.com/admin/blogs/1302936