Java Fork Join框架 (三) 設計

杜老師說 2022-01-07 16:56:53 阅读数:766

java fork join 框架

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea
譯者:Alex

Fork/Join程序可以在任何支持以下特性的框架之上運行:框架能够讓構建的子任務並行執行,並且擁有一種等待子任務運行結束的機制。然而,java.lang.Thread類(同時也包括POSIX pthreads, 這些也是Java線程所基於的基礎)對Fork/Join程序來說並不是最優的選擇:

  • Fork/Join 任務對同步和管理有簡單的和常規的需求。相對於常規的線程來說,fork/join任務所展示的計算布局將會帶來更加靈活的調度策略。例如,fork/join任務除了等待子任務外,其他情况下是不需要阻塞的。因此傳統的用於跟踪記錄阻塞線程的代價在這種情况下實際上是一種浪費。
  • 對於一個合理的基礎任務粒度來說,構建和管理一個線程的代價甚至可以比任務執行本身所花費的代價更大。盡管粒度是應該隨著應用程序在不同特定平臺上運行而做出相應調整的。但是超過線程開銷的極端粗粒度會限制並行的發揮。

簡而言之,Java標准的線程框架對fork/join程序而言太笨重了。但是既然線程構成了很多其他的並發和並行編程的基礎,完全消除這種代價或者為了這種方式而調整線程調度是不可能(或者說不切實際的)。

盡管這種思想已經存在了很長時間了,但是第一個發布的能系統解决這些問題的框架是Cilk[5]。Cilk和其他輕量級的框架是基於操作系統的基本的線程和進程機制來支持特殊用途的fork/join程序。這種策略同樣適用於Java,盡管Java線程是基於低級別的操作系統的能力來實現的。創造這樣一個輕量級的執行框架的主要優勢是能够讓fork/join程序以一種更直觀的方式編寫,進而能够在各種支持JVM的系統上運行。
fj1
FJTask框架是基於Cilk設計的一種演變。其他的類似框架有Hood[4], Filaments[8],stackthreads[10], 以及一些依賴於輕量級執行任務的相關系統。所有這些框架都采用和操作系統把線程映射到CPU上相同的方式來把任務映射到線程上。只是他們會使用fork/join程序的簡單性、常規性以及一致性來執行這種映射。盡管這些框架都能適應不能形式的並行程序,他們優化了fork/join的設計:

  • 一組工作者線程池是准備好的。每個工作線程都是標准的(“重量級”)處理存放在隊列中任務的線程(這地方指的是Thread類的子類FJTaskRunner的實例對象)。通常情况下,工作線程應該與系統的處理器數量一致。對於一些原生的框架例如說Cilk,他們首先將映射成內核線程或者是輕量級的進程,然後再在處理器上面運行。在Java中,虛擬機和操作系統需要相互結合來完成線程到處理器的映射。然後對於計算密集型的運算來說,這種映射對於操作系統來說是一種相對簡單的任務。任何合理的映射策略都會導致線程映射到不同的處理器。
  • 所有的fork/join任務都是輕量級執行類的實例,而不是線程實例。在Java中,獨立的可執行任務必須要實現Runnable接口並重寫run方法。在FJTask框架中,這些任務將作為子類繼承FJTask而不是Thread,它們都實現了Runnable接口。(對於上面兩種情况來說,一個類也可以選擇實現Runnable接口,類的實例對象既可以在任務中執行也可以在線程中執行。因為任務執行受到來自FJTask方法嚴厲規則的制約,子類化FJTask相對來說更加方便,也能够直接調用它們。)
  • 我們將采用一個特殊的隊列和調度原則來管理任務並通過工作線程來執行任務。這些機制是由任務類中提供的相關方式實現的:主要是由fork,join,isDone(一個結束狀態的標示符),和一些其他方便的方法,例如調用coInvoke來分解合並兩個或兩個以上的任務。
  • 一個簡單的控制和管理類(這裏指的是FJTaskRunnerGroup)來啟動工作線程池,並初始化執行一個由正常的線程調用所觸發的fork/join任務(就類似於Java程序中的main方法)。

作為一個給程序員演示這個框架如何運行的標准實例,這是一個計算法斐波那契函數的類。

class Fib extends FJTask { static final int threshold = 13; volatile int number; // arg/result Fib(int n) { number = n; } int getAnswer() { if (!isDone()) throw new IllegalStateException(); return number; } public void run() { int n = number; if (n <= threshold) // granularity ctl number = seqFib(n); else { Fib f1 = new Fib(n ? 1); Fib f2 = new Fib(n ? 2); coInvoke(f1, f2); number = f1.number + f2.number; } } public static void main(String[] args) { try { int groupSize = 2; // for example FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize); Fib f = new Fib(35); // for example group.invoke(f); int result = f.getAnswer(); System.out.println("Answer: " + result); } catch (InterruptedException ex) { } } int seqFib(int n) { if (n <= 1) return n; else return seqFib(n?1) + seqFib(n?2); }}

這個版本在第4節中所提到的平臺上的運行速度至少比每個任務都在Thread類中運行快30倍。在保持性能的同時這個程序仍然維持著Java多線程程序的可移植性。對程序員來說通常有兩個參數值的他們關注:

  • 對於工作線程的創建數量,通常情况下可以與平臺所擁有的處理器數量保持一致(或者更少,用於處理其他相關的任務,或者有些情况下更多,來提昇非計算密集型任務的性能)。
  • 一個粒度參數代錶了創建任務的代價會大於並行化所帶來的潜在的性能提昇的臨界點。這個參數更多的是取决於算法而不是平臺。通常在單處理器上運行良好的臨界點,在多處理器平臺上也會發揮很好的效果。作為一種附帶的效益,這種方式能够與Java虛擬機的動態編譯機制很好的結合,而這種機制在對小塊方法的優化方面相對於單塊的程序來說要好。這樣,加上數據本地化的優勢,fork/join算法的性能即使在單處理器上面的性能都較其他算法要好。

2.1Work−Stealing

Fork/jion框架的核心在於輕量級調度機制。FJTask采用了Cilk的 work-stealing 所采用的基本調度策略:

  • 每一個工作線程維護自己的調度隊列中的可運行任務。
  • 隊列以雙端隊列的形式被維護(注:deques通常讀作“decks”),不僅支持後進先出——LIFO的push和pop操作,還支持先進先出——FIFO的take操作。
  • 對於一個給定的工作線程來說,任務所產生的子任務將會被放入到工作者自己的雙端隊列中。
  • 工作線程使用後進先出——LIFO(最早的優先)的順序,通過彈出任務來處理隊列中的任務。
  • 當一個工作線程的本地沒有任務去運行的時候,它將使用先進先出——FIFO的規則嘗試隨機的從別的工作線程中拿(“偷竊”)一個任務去運行。
  • 當一個工作線程觸及了join操作,如果可能的話它將處理其他任務,直到目標任務被告知已經結束(通過isDone方法)。所有的任務都會無阻塞的完成。
  • 當一個工作線程無法再從其他線程中獲取任務和失敗處理的時候,它就會退出(通過yields, sleeps, 和/或者優先級調整,參考第3節)並經過一段時間之後再度嘗試直到所有的工作線程都被告知他們都處於空閑的狀態。在這種情况下,他們都會阻塞直到其他的任務再度被上層調用。

fj2
使用後進先出——LIFO用來處理每個工作線程的自己任務,但是使用先進先出——FIFO規則用於獲取別的任務,這是一種被廣泛使用的進行遞歸fork/join設計的一種調優手段。引用[5]討論了詳細討論了裏面的細節。

讓偷取任務的線程從隊列擁有者相反的方向進行操作會减少線程競爭。同樣體現了遞歸分治算法的大任務優先策略。因此,更早期被偷取的任務有可能會提供一個更大的單元任務,從而使得偷取線程能够在將來進行遞歸分解。

作為上述規則的一個後果,對於一些基礎的操作而言,使用相對較小粒度的任務比那些僅僅使用粗粒度劃分的任務以及那些沒有使用遞歸分解的任務的運行速度要快。盡管相關的少數任務在大多數的fork/join框架中會被其他工作線程偷取,但是創建許多組織良好的任務意味著只要有一個工作線程處於可運行的狀態,那麼這個任務就有可能被執行。

原創文章,轉載請注明: 轉載自並發編程網 – ifeve.com本文鏈接地址: Java Fork Join框架 (三) 設計

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071656530630.html