本文如果您已經(jīng)了解一般并行編程知識(shí)。了解 Java concurrent 部分如 ExecutorService 等相關(guān)內(nèi)容。

雖說(shuō)是 Java 的 ForkJoin 并行框架。但不要太在意 Java ，當(dāng)中的思想在其他語(yǔ)言環(huán)境也是相同適用的。由于并發(fā)編程在本質(zhì)上是一樣的。就好像怎樣找到優(yōu)秀的 Ruby 程序猿？事實(shí)上要找的僅僅是一個(gè)優(yōu)秀的程序猿。

當(dāng)然，假設(shè)語(yǔ)言層面直接支持相關(guān)的語(yǔ)義會(huì)更好。

?

引言

Java? 語(yǔ)言從一開(kāi)始就支持線(xiàn)程和并發(fā)性語(yǔ)義。

Java5 添加的并發(fā)工具又攻克了一般應(yīng)用程序的并發(fā)需求。 Java6 、 Java7 又進(jìn)一步補(bǔ)充了一些內(nèi)容。原來(lái)的工具主要是粗粒度的并發(fā)。

比方每一個(gè) web 請(qǐng)求由一個(gè)工作線(xiàn)程處理，在線(xiàn)程池分配任務(wù)。

而Java 7 中新引入的 ForkJoin 能夠處理更細(xì)粒度的并行計(jì)算。

?

早期的時(shí)候都是單核 cpu 環(huán)境。假設(shè)不是多核環(huán)境下。線(xiàn)程 / 進(jìn)程并非 真正 的并行運(yùn)行，主要用來(lái)表示異步運(yùn)行效果。

單核 cpu 上，假如每一個(gè)任務(wù)全然是 cpu 密集的（沒(méi)有等待），那么這樣的偽并發(fā)并不會(huì)使計(jì)算變快。

僅僅有在真正的多核環(huán)境才干起到加速作用，而如今多核已經(jīng)普及。甚至已經(jīng)到了手機(jī)上！

介紹

ForkJoin 是適用于多核環(huán)境的輕量級(jí)并行框架。目標(biāo)是在多核系統(tǒng)下，通過(guò)并行運(yùn)算。充分利用多處理器。提高效率與加速執(zhí)行。

ForkJoin 編程范式：將問(wèn)題遞歸地分解為較小的子問(wèn)題，并行處理這些子問(wèn)題，然后合并結(jié)果，如：

if (my portion of the work is small enough) ??

? ? ?do the work directly?

else ??

? ? ?split my work into two pieces ??

? ? ?invoke the two pieces and wait for the results

?

ForkJoin 由一組工作線(xiàn)程組成。用來(lái)運(yùn)行任務(wù)。核心是 work-stealing 算法 。能夠有大量任務(wù)，但實(shí)際僅僅有少量真正的物理線(xiàn)程。默認(rèn)是機(jī)器的 cpu 數(shù)量，也可指定。非常多其他工作的算法都能夠在此基礎(chǔ)之上進(jìn)行。

盡管起初直接使用它的人可能不多，但將來(lái)會(huì)被非常多框架在底層使用，由于是如此基礎(chǔ)，所以終于 ForkJoin 可能會(huì)無(wú)處不在。

一般而言，使用者僅僅須要關(guān)心兩個(gè)方法 fork()? 和 ?join() 。它們分別表示：子任務(wù)的異步運(yùn)行和堵塞等待結(jié)果完畢。 ?

ForkJoin 框架的核心是 ForkJoinPool 類(lèi)，實(shí)現(xiàn)了 work-stealing 算法，用于運(yùn)行 ForkJoinTask 類(lèi)型的任務(wù)（也就是依照該算法調(diào)度線(xiàn)程與任務(wù)，當(dāng)然還負(fù)責(zé)解決好相關(guān)的一些其他問(wèn)題）。

?

work-stealing 算法

work-stealing? 是一種任務(wù)調(diào)度方法，由多個(gè)工作線(xiàn)程組成。每一個(gè)工作線(xiàn)程用一個(gè)雙端隊(duì)列維護(hù)一組任務(wù)。

Fork 的時(shí)候是把任務(wù)加到隊(duì)列的頭部。而不像一般的線(xiàn)程池那樣是加到任務(wù)隊(duì)列末尾。工作線(xiàn)程選擇頭部最新的任務(wù)來(lái)運(yùn)行。當(dāng)工作線(xiàn)程沒(méi)有任務(wù)可運(yùn)行時(shí)，它會(huì)嘗試從其他線(xiàn)程的任務(wù)隊(duì)列尾部竊取一個(gè)任務(wù)運(yùn)行。假設(shè)沒(méi)有任務(wù)運(yùn)行了而且竊取其他任務(wù)失敗，那么工作線(xiàn)程停止。

這樣的方法的長(zhǎng)處是降低了爭(zhēng)用，由于工作線(xiàn)程從頭獲取任務(wù)，而竊取線(xiàn)程從尾部竊取任務(wù)。還有一個(gè)長(zhǎng)處是遞歸的分治法使得早期產(chǎn)生的是較大的任務(wù)單元。而竊取到較大任務(wù)會(huì)進(jìn)一步遞歸分解。因此也降低了尾部竊取的次數(shù)。

另外，父任務(wù)非常可能要等待子任務(wù)（ join ）。所以從隊(duì)列頭部子任務(wù)開(kāi)始運(yùn)行也是一種優(yōu)化。

總之。它會(huì)使用有限的線(xiàn)程運(yùn)行大量任務(wù)，同一時(shí)候保持各線(xiàn)程的任務(wù)都處于繁忙的運(yùn)行狀態(tài)。而盡量不讓線(xiàn)程處于等待狀態(tài)。

為了做到這點(diǎn)可能會(huì)從其他線(xiàn)程的任務(wù)隊(duì)列中竊取任務(wù)來(lái)運(yùn)行，所以叫 work-stealing 。

就像前面所說(shuō)物理線(xiàn)程不能太多，過(guò)多的話(huà)切換管理開(kāi)銷(xiāo)就會(huì)較大，還會(huì)消耗很多其它的內(nèi)存等資源，而且沒(méi)有帶來(lái)不論什么優(yōu)點(diǎn)。默認(rèn)是用 cpu數(shù)量的線(xiàn)程數(shù)，普通情況都 比較合適（比方 Runtime.getRuntime().availableProcessors() 返回處理器的數(shù)量），但詳細(xì)的數(shù)值還和任務(wù)自身的特點(diǎn)有關(guān)，能夠通過(guò)不同參數(shù)測(cè)試比較一下。而任務(wù)能夠是大量的，由每一個(gè)線(xiàn)程的工作隊(duì)列維護(hù)。

ForkJoin 是簡(jiǎn)化了一些開(kāi)發(fā)人員的工作，假設(shè)不用 ForkJoin 。最原始的方式是自己手工切分任務(wù)并分別創(chuàng)建線(xiàn)程運(yùn)行。

?

分治、并行、可伸縮的思考：

這三者 關(guān)系非常親熱。分治思想（ divide-and-conquer ）是一種簡(jiǎn)單樸素的思想。非常多問(wèn)題都能夠這樣解決。 ForkJoin 就相當(dāng)于分治法的并行版本號(hào)。 ? 分治本身僅僅是解決這個(gè)問(wèn)題的思想，既能夠順序運(yùn)行也能夠并行運(yùn)行，可是在并行環(huán)境中更加有效。由于能夠并行處理子問(wèn)題。

而在并行方面，可并行處理問(wèn)題要么是彼此全然獨(dú)立的問(wèn)題，要么是可分解單獨(dú)處理的問(wèn)題。可伸縮性又和是否能并行處理緊密相關(guān)。由于假設(shè)不能并行處理就要受到單機(jī)處理能力的限制，也就難以伸縮了。

ForkJoin 與 MapReduce 兩個(gè)并行計(jì)算框架的差別 ? ？

MapReduce 是把大數(shù)據(jù)集切分成小數(shù)據(jù)集，并行分布計(jì)算后再合并。

ForkJoin 是將一個(gè)問(wèn)題遞歸分解成子問(wèn)題。再將子問(wèn)題并行運(yùn)算后合并結(jié)果。

二者共同點(diǎn)：都是用于運(yùn)行并行任務(wù)的。基本思想都是把問(wèn)題分解為一個(gè)個(gè)子問(wèn)題分別計(jì)算，再合并結(jié)果。應(yīng)該說(shuō)并行計(jì)算都是這樣的思想，彼此獨(dú)立的或可分解的。 從名字上看 Fork 和 Map 都有切分的意思。 Join 和 Reduce 都有合并的意思。比較類(lèi)似。

差別：

1 ）環(huán)境差異。分布式 ?vs? 單機(jī)多核： ForkJoin 設(shè)計(jì)初衷針對(duì)單機(jī)多核（處理器數(shù)量非常多的情況）。 MapReduce 一開(kāi)始就明白是針對(duì)非常多機(jī)器組成的集群環(huán)境的。也就是說(shuō)一個(gè)是想充分利用多處理器，而還有一個(gè)是想充分利用非常多機(jī)器做分布式計(jì)算。這是兩種不同的的應(yīng)用場(chǎng)景。有非常多差異，因此在細(xì)的編程模式方面有非常多不同。

2 ）編程差異： MapReduce 通常是：做較大粒度的切分，一開(kāi)始就先切分好任務(wù)然后再運(yùn)行，而且彼此間在最后合并之前不須要通信。這樣可伸縮性更好，適合解決巨大的問(wèn)題，但限制也很多其它。 ForkJoin 能夠是較小粒度的切分，任務(wù)自己知道該怎樣切分自己，遞歸地切分到一組合適大小的子任務(wù)來(lái)運(yùn)行。由于是一個(gè) JVM 內(nèi)，所以彼此間通信是非常easy的。更像是傳統(tǒng)編程方式。

ForkJoin 框架基本結(jié)構(gòu) ：

ForkJoinPool 本身實(shí)現(xiàn)了 ExecutorService 接口，負(fù)責(zé)調(diào)度運(yùn)行 ForkJoinTask 。

ForkJoinTask 是提交給 ForkJoinPool? 運(yùn)行的任務(wù)，本身也實(shí)現(xiàn)了 Future? 接口。

?

ForkJoinTask 有兩個(gè)子類(lèi) RecursiveAction 和 RecursiveTask 。

? RecursiveAction? 沒(méi)有返回值（僅僅需 fork ）； RecursiveTask 有返回值（須要合并）。

類(lèi)似于 Runnable 和 ?Callable 一樣。沒(méi)有返回值一般意味著全部子任務(wù)都運(yùn)行完了就可以，中間的子任務(wù)不須要 join 了。事實(shí)上要不要返回值都能夠?qū)崿F(xiàn)。有返回值能夠直接合并。沒(méi)有返回值能夠把結(jié)果保存在共享的數(shù)據(jù)上。

?

而我們要做的是實(shí)現(xiàn)自己要完畢的任務(wù)，僅僅須要繼承其一，并覆蓋抽象方法 compute() 。在這種方法中實(shí)現(xiàn)自己的任務(wù)，遞歸分解任務(wù)。

?

ForkJoinPool 與一般的 ExecutorService 實(shí)現(xiàn)的區(qū)別 ？

ForkJoin 實(shí)現(xiàn)了 ExecutorService 接口，這個(gè)接口就是用來(lái)把任務(wù)交給線(xiàn)程池中的工作線(xiàn)程去運(yùn)行。 ForkJoin 也是一個(gè) ExecutorService ，但差別在于 ForkJoin 使用了 work-stealing 算法，見(jiàn)前面的介紹。

普通的線(xiàn)程池是按 FIFO 的方式運(yùn)行，而 ForkJoin 優(yōu)先運(yùn)行（由其他任務(wù)）后創(chuàng)建子任務(wù)。

對(duì)于大部分 會(huì) 產(chǎn)生子任務(wù)的 任務(wù) 模式， ForkJoin 的處理 實(shí)現(xiàn) 會(huì)非常高效。假設(shè)設(shè)置了異步模式， ? ForkJoin 也可能適合運(yùn)行事件類(lèi)型（不須要 join ）的任務(wù)。

影響 ForkJoin 加速效果的因素

理想效果是核越多加速效果越好。

可是并行不一定更快，參數(shù)不正確還可能更慢：

1） ?? 并發(fā)數(shù)，即線(xiàn)程數(shù)。通常是可用的 cpu 數(shù)，默認(rèn)就是這個(gè)，一般表現(xiàn)非常好。

2） ?? 任務(wù)切分的粒度。假設(shè)切分粒度等于總?cè)蝿?wù)量，一個(gè)任務(wù)運(yùn)行，就相當(dāng)于單線(xiàn)程順序運(yùn)行。每一個(gè)任務(wù)運(yùn)行的計(jì)算量。太大的話(huà)加速效果有限。不能發(fā)揮到最好。相反，太小的話(huà)，消耗在任務(wù)管理的成本占了主要部分。導(dǎo)致還不如順序運(yùn)行的快。 ?

須要適當(dāng)平衡二者。由于還和任務(wù)本身的特定有關(guān)。所以能夠做個(gè)基準(zhǔn)測(cè)試比較一下。

而總的運(yùn)行時(shí)間還與任務(wù)的規(guī)模有關(guān)。

任務(wù)粒度應(yīng)該適中，多大合適？好像在什么地方上看到說(shuō)：經(jīng)驗(yàn)上單個(gè)任務(wù)為 100-10000 個(gè)基本指令，當(dāng)然還和任務(wù)本身的特定有關(guān)。

?

個(gè)人感覺(jué)多核 cpu 僅僅適用于解決計(jì)算密集型應(yīng)用，由于實(shí)際問(wèn)題可能 IO 等其它方面的瓶頸，多核也還是無(wú)法充分利用的。

? ?

使用 ForkJoin 的步驟：

ForkJoin 框架替我們完畢了一些工作，那么我們使用時(shí)還要完畢哪些工作：

1） ?? 怎樣運(yùn)行單個(gè)任務(wù)。假設(shè)僅僅切分出一個(gè)任務(wù)運(yùn)行，就相當(dāng)于單線(xiàn)程順序運(yùn)行。

2） ?? 怎樣遞歸地切分任務(wù)（以及任務(wù)切分后是否須要合并結(jié)果）

3） ?? 切分粒度多少合適（最小任務(wù)單元）

這些詳細(xì)表如今：繼承 ForkJoinTask 的一個(gè)子類(lèi)。并實(shí)現(xiàn)抽象方法 compute() 。

在這種方法中實(shí)現(xiàn)自己的任務(wù)，遞歸分解任務(wù)。

?

這些準(zhǔn)備好之后就能夠啟動(dòng)了：創(chuàng)建一個(gè)表示所有任務(wù)的 ForkJoinTask 對(duì)象，創(chuàng)建一個(gè) ForkJoinPool 的實(shí)例。把 task 作為參數(shù)運(yùn)行 ForkJoinPool 的 invoke 方法。

?

在 ForkJoin 任務(wù)外部運(yùn)行總?cè)蝿?wù)： execute 異步運(yùn)行任務(wù)。沒(méi)有返回結(jié)果 void ； invoke 運(yùn)行任務(wù)并等待返回結(jié)果。結(jié)果是特定類(lèi)型。 submit 運(yùn)行一個(gè)任務(wù)，返回 ForkJoinTask （實(shí)際上是作為 Future 對(duì)象返回）。一般應(yīng)該在外部使用 invoke 調(diào)用運(yùn)行總?cè)蝿?wù)。

而 execute 和 submit 僅僅是為了實(shí)現(xiàn) ExecutorService 規(guī)定的相關(guān)語(yǔ)義， invoke 是 ForkJoin 中特有的。

?

在 ForkJoinTask 內(nèi)部遞歸運(yùn)行的過(guò)程中： fork 是異步運(yùn)行。 invoke 是等待任務(wù)運(yùn)行完畢。

?

詳細(xì)實(shí)例：

多看看詳細(xì)演示樣例比較好。

1） ?? 合并排序演示樣例：

合并排序是常見(jiàn)的排序算法之中的一個(gè)。

演示樣例實(shí)現(xiàn)了對(duì)一個(gè)整數(shù)數(shù)組的合并排序。同一時(shí)候還演示了不同并發(fā)數(shù)（線(xiàn)程數(shù)）與不同數(shù)組大小的組合測(cè)試。

代碼在 <jdk_ home>/sample/ForkJoin/? 中。

?

2） ?? 把圖片模糊處理演示樣例：

一個(gè)圖片能夠被表示為一個(gè) m*n 大小的整數(shù)數(shù)組，當(dāng)中每一個(gè)整數(shù)表示一個(gè)像素（的顏色）。模糊處理之后的圖像還是一個(gè)相同大小的整數(shù)數(shù)組。處理過(guò)程是把原來(lái)的每一個(gè)像素與周?chē)袼氐念伾笃骄稻涂梢浴?

假設(shè)順序運(yùn)行就是從頭到尾對(duì)每一個(gè)像素運(yùn)行一次計(jì)算得到目標(biāo)像素，由于每一個(gè)像素的計(jì)算是獨(dú)立的，所以能夠把這個(gè)整數(shù)數(shù)組切分成一塊一塊的子數(shù)組（即子任務(wù)）分別運(yùn)行。任務(wù)不適合切分的過(guò)小。所以設(shè)定了一個(gè)常數(shù)閾值 10000 ，大小小于 10000 的子數(shù)組就直接運(yùn)行，否則對(duì)半切分為兩個(gè)子數(shù)組的任務(wù)分別運(yùn)行。 文章 ? 源碼

? ? ?? 在我自己的機(jī)器上 i3 處理器 ? （i3， 4cpu ），并行確實(shí)快了不少。

?

其他的比如：求最大值 max 、平均值 avg 、求和 sum 等聚合函數(shù)都是能夠分解計(jì)算的。

演示樣例中都是對(duì)數(shù)組的處理。比較常見(jiàn)的是對(duì)數(shù)組、集合進(jìn)行并行地處理操作。但也不限于此。 ??

網(wǎng)上有一些 Fibonacci? 的演示樣例。但這些演示樣例并不適合展示 ForkJoin 。

?

Doug Lea 與 JSR-166

說(shuō)到 Java 并發(fā)編程，就不能不說(shuō)到 Doug Lea 與 JSR-166 。 Doug Lea 是并發(fā)編程方面的專(zhuān)家。紐約州立大學(xué)奧斯威戈分校的計(jì)算機(jī)教授。曾是 JCP 運(yùn)行委員。是 JSR-166 的 leader 。

JSR-166 就是負(fù)責(zé)向 Java 語(yǔ)言中加入并發(fā)編程工具的，即我們見(jiàn)到的 java.util.concurrent 包（及子包）。還是《 ?Concurrent Programming in Java Design Principles and Patterns 》一書(shū)的作者，是這方面最早的書(shū)。

他還是知名的內(nèi)存分配方法 dlmalloc 的作者，這是 C 語(yǔ)言中的動(dòng)態(tài)內(nèi)存分配函數(shù) malloc 的一種普遍使用的實(shí)現(xiàn)。

? ?

參考資料：

• Java api? 及前面提到的兩個(gè)自帶演示樣例。
• A Java Fork/Join Framework ? （ pdf ）
• Java 理論與實(shí)踐: 應(yīng)用 fork-join 框架
• Java 理論與實(shí)踐: 應(yīng)用 fork-join 框架，第 2 部分
• JDK 7 中的 Fork/Join 模式
• Java Fork/Join for Parallel Programming
• Fork-Join Development in Java? SE
• Java Fork/Join + Groovy
• InfoQ 上 ForkJoin 相關(guān)文章

? 其他并行框架：

• Akka ?
• GPars ?