?

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

?

3.3 隊列

? ? ?框架的核心是維護阻塞線程的隊列，隊列的策略是先進先出（FIFO），因此，該框架不支持基于優先級的同步

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

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

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

?

?

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

?

?

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

?

?

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

?

?

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

?

?

head = node;

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

?

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

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

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

?

pred.next = node;

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

?

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

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

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

? ? ?當然還有一些優化調整，包括延遲初始化：CLH隊列在第一次競爭發生時才初始話所需的虛擬節點，這些詳細描述在J2SE1.5版本的源代碼的文檔里。

? ? 忽略這些細節，實現一個具有基本操作（互斥，不可中斷，超時）的一般形式是：

?

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

?

?

一個釋放操作如下:

?

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

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

?

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

?

3.4 條件隊列

?

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

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

? ? ?一個ConditionObject與同步器使用相同的內部隊列節點，但它們維護在一個單獨的條件隊列中；喚醒操作通過從條件隊列轉移到鎖隊列來實現；一個線程已經重新獲取了鎖，不需要喚醒已經喚醒的線程；

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

?

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

? ? 喚醒的操作是：

?

?

將條件隊列的第一個節點轉移到鎖隊列中；

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

?

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

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

?

原文見第一篇的附件

?

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