?

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

?

3.3 隊列

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

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

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

? ? ?一個新的節(jié)點入隊列的時候，使用下面的原子操作：

?

?

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

?

?

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

?

?

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

?

?

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

?

?

head = node;

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

?

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

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

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

?

pred.next = node;

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

?

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

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

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

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

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

?

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

?

?

一個釋放操作如下:

?

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

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

?

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

?

3.4 條件隊列

?

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

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

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

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

?

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

? ? 喚醒的操作是：

?

?

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

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

?

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

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

?

原文見第一篇的附件

?

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