889      阿裏雲  技術社區[雲棲]

The j.u.c Synchronizer Framework翻譯(二)設計與實現

3 設計與實現

同步器背後的基本思想非常簡單。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;

為了實現上述操作，需要下麵三個基本組件的相互協作：

• 同步狀態的原子性管理；
• 線程的阻塞與解除阻塞；
• 隊列的管理；

創建一個框架分別實現這三個組件是有可能的。但是，這會讓整個框架既難用又沒效率。例如：存儲在隊列節點的信息必須與解除阻塞所需要的信息一致，而暴露出的方法的簽名必須依賴於同步狀態的特性。

同步器框架的核心決策是為這三個組件選擇一個具體實現，同時在使用方式上又有大量選項可用。這裏有意地限製了其適用範圍，但是提供了足夠的效率，使得實際上沒有理由在合適的情況下不用這個框架而去重新建造一個。

3.1 同步狀態

AQS類使用單個int（32位）來保存同步狀態，並暴露出getState、setState以及compareAndSet操作來讀取和更新這個狀態。這些方法都依賴於j.u.c.atomic包的支持，這個包提供了兼容JSR133中volatile在讀和寫上的語義，並且通過使用本地的compare-and-swap或load-linked/store-conditional指令來實現compareAndSetState，使得僅當同步狀態擁有一個期望值的時候，才會被原子地設置成新值。

將同步狀態限製為一個32位的整形是出於實踐上的考量。雖然JSR166也提供了64位long字段的原子性操作，但這些操作在很多平台上還是使用內部鎖的方式來模擬實現的，這會使同步器的性能可能不會很理想。當然，將來可能會有一個類是專門使用64位的狀態的。然而現在就引入這麼一個類到這個包裏並不是一個很好的決定（譯者注：JDK1.6中已經包含java.util.concurrent.locks.AbstractQueuedLongSynchronizer類，即使用 long 形式維護同步狀態的一個 AbstractQueuedSynchronizer 版本）。目前來說，32位的狀態對大多數應用程序都是足夠的。在j.u.c包中，隻有一個同步器類可能需要多於32位來維持狀態，那就是CyclicBarrier類，所以，它用了鎖（該包中大多數更高層次的工具亦是如此）。

基於AQS的具體實現類必須根據暴露出的狀態相關的方法定義tryAcquire和tryRelease方法，以控製acquire和release操作。當同步狀態滿足時，tryAcquire方法必須返回true，而當新的同步狀態允許後續acquire時，tryRelease方法也必須返回true。這些方法都接受一個int類型的參數用於傳遞想要的狀態。例如：可重入鎖中，當某個線程從條件等待中返回，然後重新獲取鎖時，為了重新建立循環計數的場景。很多同步器並不需要這樣一個參數，因此忽略它即可。

3.2 阻塞

在JSR166之前，阻塞線程和解除線程阻塞都是基於Java內置管程，沒有其它非基於Java內置管程的API可以用來創建同步器。唯一可以選擇的是Thread.suspend和Thread.resume，但是它們都有無法解決的競態問題，所以也沒法用：當一個非阻塞的線程在一個正準備阻塞的線程調用suspend前調用了resume，這個resume操作將不會有什麼效果。

j.u.c包有一個LockSuport類，這個類中包含了解決這個問題的方法。方法LockSupport.park阻塞當前線程除非/直到有個LockSupport.unpark方法被調用（unpark方法被提前調用也是可以的）。unpark的調用是沒有被計數的，因此在一個park調用前多次調用unpark方法隻會解除一個park操作。另外，它們作用於每個線程而不是每個同步器。一個線程在一個新的同步器上調用park操作可能會立即返回，因為在此之前可能有“剩餘的”unpark操作。但是，在缺少一個unpark操作時，下一次調用park就會阻塞。雖然可以顯式地消除這個狀態（譯者注：就是多餘的unpark調用），但並不值得這樣做。在需要的時候多次調用park會更高效。

這個簡單的機製與有些用法在某種程度上是相似的，例如Solaris-9的線程庫，WIN32中的“可消費事件”，以及Linux中的NPTL線程 庫。因此最常見的運行Java的平台上都有相對應的有效實現。（但目前Solaris和Linux上的Sun Hotspot JVM參考實現實際上是使用一個pthread的condvar來適應目前的運行時設計的）。park方法同樣支持可選的相對或絕對的超時設置，以及與JVM的Thread.interrupt結合 —— 可通過中斷來unpark一個線程。

3.3 隊列

整個框架的關鍵就是如何管理被阻塞的線程的隊列，該隊列是嚴格的FIFO隊列，因此，框架不支持基於優先級的同步。

同步隊列的最佳選擇是自身沒有使用底層鎖來構造的非阻塞數據結構，目前，業界對此很少有爭議。而其中主要有兩個選擇：一個是Mellor-Crummey和Scott鎖（MCS鎖）^[9]的變體，另一個是Craig，Landin和Hagersten鎖（CLH鎖）^[5][8][10]的 變體。一直以來，CLH鎖僅被用於自旋鎖。但是，在這個框架中，CLH鎖顯然比MCS鎖更合適。因為CLH鎖可以更容易地去實現“取消 （cancellation）”和“超時”功能，因此我們選擇了CLH鎖作為實現的基礎。但是最終的設計已經與原來的CLH鎖有較大的出入，因此下文將對 此做出解釋。

CLH隊列實際上並不那麼像隊列，因為它的入隊和出隊操作都與它的用途（即用作鎖）緊密相關。它是一個鏈表隊列，通過兩個字段head和tail來存取，這兩個字段是可原子更新的，兩者在初始化時都指向了一個空節點。

一個新的節點，node，通過一個原子操作入隊：

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

每一個節點的“釋放”狀態都保存在其前驅節點中。因此，自旋鎖的“自旋”操作就如下：

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

自旋後的出隊操作隻需將head字段指向剛剛得到鎖的節點：

head = node;

CLH鎖的優點在於其入隊和出隊操作是快速、無鎖的，以及無障礙的（即使在競爭下，某個線程總會贏得一次插入機會而能繼續執行）；且探測是否有線程正在等待也很快（隻要測試一下head是否與tail相等）；同時，“釋放”狀態是分散的（譯者注：幾乎每個節點都保存了這個狀態，當前節點保存了其後驅節點的“釋放”狀態，因此它們是分散的，不是集中於一塊的。），避免了一些不必要的內存競爭。

在原始版本的CLH鎖中，節點間甚至都沒有互相鏈接。自旋鎖中，pred變量可以是一個局部變量。然而，Scott和Scherer證明了通過在節點中顯式地維護前驅節點，CLH鎖就可以處理“超時”和各種形式的“取消”：如果一個節點的前驅節點取消了，這個節點就可以滑動去使用前麵一個節點的狀態字段。

為了將CLH隊列用於阻塞式同步器，需要做些額外的修改以提供一種高效的方式定位某個節點的後繼節點。在自旋鎖中，一個節點隻需要改變其狀態，下一次自旋中其後繼節點就能注意到這個改變，所以節點間的鏈接並不是必須的。但在阻塞式同步器中，一個節點需要顯式地喚醒（unpark）其後繼節點。

AQS隊列的節點包含一個next鏈接到它的後繼節點。但是，由於沒有針對雙向鏈表節點的類似compareAndSet的原子性無鎖插入指令，因此這個next鏈接的設置並非作為原子性插入操作的一部分，而僅是在節點被插入後簡單地賦值：

pred.next = node;

next鏈接僅是一種優化。如果通過某個節點的next字段發現其後繼結點不存在（或看似被取消了），總是可以使用pred字段從尾部開始向前遍曆來檢查是否真的有後續節點。

第二個對CLH隊列主要的修改是將每個節點都有的狀態字段用於控製阻塞而非自旋。在同步器框架中，僅在線程調用具體子類中的tryAcquire方法返回true時，隊列中的線程才能從acquire操作中返回；而單個“released”位是不夠的。但仍然需要做些控製以確保當一個活動的線程位於隊列頭部時，僅允許其調用tryAcquire；這時的acquire可能會失敗，然後（重新）阻塞。這種情況不需要讀取狀態標識，因為可以通過檢查當前節點的前驅是否為head來確定權限。與自旋鎖不同，讀取head以保證複製時不會有太多的內存競爭（ there is not enough memory contention reading head to warrant replication.）。然而，“取消”狀態必須存在於狀態字段中。

隊列節點的狀態字段也用於避免沒有必要的park和unpark調用。雖然這些方法跟阻塞原語一樣快，但在跨越Java和JVM runtime以及操作係統邊界時仍有可避免的開銷。在調用park前， 線程設置一個“喚醒（signal me）”位，然後再一次檢查同步和節點狀態。一個釋放的線程會清空其自身狀態。這樣線程就不必頻繁地嚐試阻塞，特別是在鎖相關的類中，這樣會浪費時間等待 下一個符合條件的線程去申請鎖，從而加劇其它競爭的影響。除非後繼節點設置了“喚醒”位（譯者注：源碼中為-1），否則這也可避免正在release的線程去判斷其後繼節點。這反過來也消除了這些情形：除非“喚醒”與“取消”同時發生，否則必須遍曆多個節點來處理一個似乎為null的next字段。

同步框架中使用的CLH鎖的變體與其他語言中的相比，主要區別可能是同步框架中使用的CLH鎖需要依賴垃圾回收管理節點的內存，這就避免了一些複雜 性和開銷。但是，即使依賴GC也仍然需要在確定鏈接字段不再需要時將其置為null。這往往可以與出隊操作一起完成。否則，無用的節點仍然可觸及，它們就 沒法被回收。

其它一些更深入的微調，包括CLH隊列首次遇到競爭時才需要的初始空節點的延遲初始化等，都可以在J2SE1.5的版本的源代碼文檔中找到相應的描述。

拋開這些細節，基本的acquire操作的最終實現的一般形式如下（互斥，非中斷，無超時）：

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操作的主循環次數依賴於具體實現類中tryAcquire的實現方式。另一方麵，在沒有“取消”操作的情況下，每一個組件的acquire和release都是一個O(1)的操作，忽略park中發生的所有操作係統線程調度。

支持“取消”操作主要是要在acquire循環裏的park返回時檢查中斷或超時。由超時或中斷而被取消等待的線程會設置其節點狀態，然後unpark其後繼節點。在有“取消”的情況下，判斷其前驅節點和後繼節點以及重置狀態可能需要O(n)的遍曆（n是隊列的長度）。由於“取消”操作，該線程再也不會被阻塞，節點的鏈接和狀態字段可以被快速重建。

3.4 條件隊列

AQS框架提供了一個ConditionObject類，給維護獨占同步的類以及實現Lock接口的類使用。一個鎖對象可以關聯任意數目的條件對象，可以提供典型的管程風格的await、signal和signalAll操作，包括帶有超時的，以及一些檢測、監控的方法。

通過修正一些設計決策，ConditionObject類有效地將條件（conditions）與其它同步操作結合到了一起。該類隻支持Java風格的管程訪問規則，這些規則中，僅當當前線程持有鎖且要操作的條件（condition）屬於該鎖時，條件操作才是合法的（一些替代操作的討論參考^[4]）。這樣，一個ConditionObject關聯到一個ReentrantLock上就表現的跟內置的管程（通過Object.wait等）一樣了。兩者的不同僅僅在於方法的名稱、額外的功能以及用戶可以為每個鎖聲明多個條件。

ConditionObject使用了與同步器一樣的內部隊列節點。但是，是在一個單獨的條件隊列中維護這些節點的。signal操作是通過將節點從條件隊列轉移到鎖隊列中來實現的，而沒有必要在需要喚醒的線程重新獲取到鎖之前將其喚醒。

基本的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;

因為隻有在持有鎖的時候才能執行這些操作，因此他們可以使用順序鏈表隊列操作來維護條件隊列（在節點中用一個nextWaiter字段）。轉移操作僅僅把第一個節點從條件隊列中的鏈接解除，然後通過CLH插入操作將其插入到鎖隊列上。

實現這些操作主要複雜在，因超時或Thread.interrupt導致取消了條件等待時，該如何處理。“取消”和“喚醒”幾乎同時發生就會有競態問題，最終的結果遵照內置管程相關的規範。JSR133修訂以後，就要求如果中斷發生在signal操作之前，await方法必須在重新獲取到鎖後，拋出InterruptedException。但是，如果中斷發生在signal後，await必須返回且不拋異常，同時設置線程的中斷狀態。

為了維護適當的順序，隊列節點狀態變量中的一個位記錄了該節點是否已經（或正在）被轉移。“喚醒”和“取消”相關的代碼都會嚐試用compareAndSet修改這個狀態。如果某次signal操 作修改失敗，就會轉移隊列中的下一個節點（如果存在的話）。如果某次“取消”操作修改失敗，就必須中止此次轉移，然後等待重新獲得鎖。後麵的情況采用了一 個潛在的無限的自旋等待。在節點成功的被插到鎖隊列之前，被“取消”的等待不能重新獲得鎖，所以必須自旋等待CLH隊列插入（即compareAndSet操作）被“喚醒”線程成功執行。這裏極少需要自旋，且自旋裏使用Thread.yield來提示應該調度某一其它線程，理想情況下就是執行signal的那個線程。雖然有可能在這裏為“取消”實現一個幫助策略以幫助插入節點，但這種情況實在太少，找不到合適的理由來增加這些開銷。在其它所有的情況下，這個基本的機製都不需要自旋或yield，因此在單處理器上保持著合理的性能。

參考文獻

• [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 https://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.

文章轉自 並發編程網-ifeve.com

最後更新：2017-05-23 10:32:34

  上一篇：  Qcon2012杭州站參會分享

  下一篇：  【直擊成都雲棲大會】阿裏雲肖力：安全智能時代公共雲更靠譜