710
Java Fork Join 框架（三）實現
這個框架是由大約800行純Java代碼組成，主要的類是FJTaskRunner，它是java.lang.Thread的子類。FJTasks 自己僅僅維持一個關於結束狀態的布爾值，所有其他的操作都是通過當前的工作線程來代理完成的。JFTaskRunnerGroup類用於創建工作線程，維 護一些共享的狀態（例如：所有工作線程的標示符，在偷取操作時需要），同時還要協調啟動和關閉。
更多實現的細節文檔可以在util.concurrent並發包中查看。這一節隻著重討論兩類問題以及在實現這個框架的時候所形成的一些解決方案：支持高效的雙端列表操作（push, pop 和 take）， 並且當工作線程在嚐試獲取新的任務時維持偷取的協議。
3.1雙端隊列
（校注：雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在隊列的兩端進行。）
為了能夠獲得高效以及可擴展的執行任務，任務管理需要越快越好。創建、發布、和彈出（或者出現頻率很少的獲取）任務在順序編程模式中會引發程序調用開銷。更低的開銷可以使得程序員能夠構建更小粒度的任務，最終也能更好的利用並行所帶來的益處。
Java虛擬機會負責任務的內存分配。Java垃圾回收器使我們不需要再去編寫一個特殊的內存分配器去維護任務。相對於其他語言的類似框架，這個原因使我們大大降低了實現FJTasks的複雜性以及所需要的代碼數。
雙端隊列的基本結構采用了很常規的一個結構——使用一個數組（盡管是可變長的）來表示每個隊列，同時附帶兩個索引：top 索引就類似於數組中的棧指針，通過push和pop操作來改變。Base 索引隻能通過take操作來改變。鑒於FJTaskRunner操作都是無縫的綁定到雙端隊列的細節之中，（例如，fork直接調用push），所以這個 數據結構直接放在類之中，而不是作為一個單獨的組件。
但是雙端隊列的元素會被多線程並發的訪問，在缺乏足夠同步的情況下，而且單個的Java數組元素也不能聲明為volitile變量（校注：聲明成volatile的數組， 其元素並不具備volatile語意），每個數組元素實際上都是一個固定的引用，這個引用指向了一個維護著單個volitile引用的轉發對象。一開始做 出這個決定主要是考慮到Java內存模型的一致性。但是在這個級別它所需要的間接尋址被證明在一些測試過的平台上能夠提升性能。可能是因為訪問鄰近的元素 而降低了緩存爭用，這樣內存裏麵的間接尋址會更快一點。
實現雙端隊列的主要挑戰來自於同步和他的撤銷。盡管在Java虛擬機上使用經過優化過的同步工具，對於每個push和pop操作都需要獲取鎖還是讓這一切成為性能瓶頸。然後根據以下的觀察結果我們可以修改Clik中的策略，從而為我們提供一種可行的解決方案：
- Push和pop操作僅可以被工作線程的擁有者所調用。
- 對Take的操作很容易會由於偷取任務線程在某一時間對take操作加鎖而限製。（雙端隊列在必要的時間也可以禁止take操作。）這樣，控製衝突將被降低為兩個部分同步的層次。
- Pop和take操作隻有在雙端隊列為空的時候才會發生衝突，否則的話，隊列會保證他們在不同的數組元素上麵操作。
把top和base索引定義為volitile變量可以保證當隊列中元素不止一個時，pop和take操作可以在不加鎖的情況下進行。這是通過一種類似於Dekker算法來實現的。當push 預遞減到top時:
If (–top >=base)…
和take 預遞減到 base時:
If(++base < top)…
在上述每種情況下他們都通過比較兩個索引來檢查這樣是否會導致雙端隊列變成一個空隊列。一個不對稱的規則將用於防止潛在的衝突：pop會重新檢查狀 態並在獲取鎖之後繼續（對take所持有的也一樣），直到隊列真的為空才退出。而Take操作會立即退出，特別是當嚐試去獲得另外一個任務。與其他類似使 用Clik的THE協議一樣，這種不對稱性是唯一重要的改變。
使用volitile變量索引push操作在隊列沒有滿的情況下不需要同步就可以進行。如果隊列將要溢出，那麼它首先必須要獲得隊列鎖來重新設置隊列的長度。其他情況下，隻要確保top操作排在隊列數組槽盛在抑製幹涉帶之後更新。
在隨後的初始化實現中，發現有好幾種JVM並不符合Java內存模型中正確讀取寫入的volitile變量的規則。作為一個工作區，pop操作在持 有鎖的情況下重試的條件已經被調整為：如果有兩個或者更少的元素，並且take操作加了第二把鎖以確保內存屏障效果，那麼重試就會被觸發。隻要最多隻有一 個索引被擁有者線程丟失這就是滿足的，並且隻會引起輕微的性能損耗。
3.2 搶斷和閑置
在搶斷式工作框架中，工作線程對於他們所運行的程序對同步的要求一無所知。他們隻是構建、發布、彈出、獲取、管理狀態和執行任務。這種簡單的方案使 得當所有的線程都擁有很多任務需要去執行的時候，它的效率很高。然而這種方式是有代價的，當沒有足夠的工作的時候它將依賴於試探法。也就是說，在啟動一個 主任務，直到它結束，在有些fork/join算法中都使用了全麵停止的同步指針。
主要的問題在於當一個工作線程既無本地任務也不能從別的線程中搶斷任務時怎麼辦。如果程序運行在專業的多核處理器上麵，那麼可以依賴於硬件的忙等待 自旋循環的去嚐試搶斷一個任務。然而，即使這樣，嚐試搶斷還是會增加競爭，甚至會導致那些不是閑置的工作線程降低效率（由於鎖協議，3.1節中）。除此之 外，在一個更適合此框架運行的場景中，操作係統應該能夠很自信的去運行那些不相關並可運行的進程和線程。
Java中並沒有十分健壯的工作來保證這個，但是在實際中它往往是可以讓人接受的。一個搶斷失敗的線程在嚐試另外的搶斷之前會降低自己的優先級，在
嚐試搶斷之間執行Thread.yeild操作，然後將自己的狀態在FJTaskRunnerGroup中設置為不活躍的。他們會一直阻塞直到有新的主線
程。其他情況下，在進行一定的自旋次數之後，線程將進入休眠階段，他們會休眠而不是放棄搶斷。強化的休眠機製會給人造成一種需要花費很長時間去劃分任務的
假象。但是這似乎是最好的也是通用的折中方案。框架的未來版本也許會支持額外的控製方法，以便於讓程序員在感覺性能受到影響時可以重寫默認的實現。
文章轉自 並發編程網-ifeve.com
最後更新：2017-05-23 10:32:50