淺析JSR-166y中Fork/Join框架的應(yīng)用

摘要：多線(xiàn)程開(kāi)發(fā)技術(shù)可以有效利用計(jì)算資源，而Fork/Join框架是一種經(jīng)典的多線(xiàn)程開(kāi)發(fā)框，能夠幫助開(kāi)發(fā)人員處理線(xiàn)程調(diào)度問(wèn)題。文章從JDK各個(gè)版本對(duì)并行編程的支持著手，介紹了未來(lái)JSR-166y中引入的Fork/Join框架及其應(yīng)用方法，并給出Java實(shí)現(xiàn)代碼。

關(guān)鍵字：線(xiàn)程模型 任務(wù)分解 并行 調(diào)度

0 引言

JDK從1.0版本開(kāi)始提供java.lang.Thread類(lèi)支持并行編程，其主要功能是初始化和管理線(xiàn)程，開(kāi)發(fā)人員使用它可以將寶貴的精力集中于業(yè)務(wù)邏輯而不必關(guān)心底層實(shí)現(xiàn)。為了解決并行編程帶來(lái)的數(shù)據(jù)不一致性問(wèn)題，JDK中引入了synchronized和volatile關(guān)鍵字，它們以各自的形式實(shí)現(xiàn)不同程度的內(nèi)存同步。隨后，JDK5.0版本引入JSR-166中Doug Lea提供的并行框架，實(shí)現(xiàn)了鎖機(jī)制和原子操作；JDK6.0版本中引入JSR-166x中的并發(fā)Collections框架；未來(lái)的JDK7.0版本中將引入JSR-166y中的Fork/Join框架，可以實(shí)現(xiàn)更細(xì)粒度的并行運(yùn)算。

1 Fork/Join框架簡(jiǎn)介

Doug Lea在論文《Fork/Join Parallelism in Java》中，首次把Fork/Join的概念引入到Java中。其基本思想是，將一個(gè)原始任務(wù)分解為多個(gè)子任務(wù)，將后者分?jǐn)偟蕉鄠€(gè)線(xiàn)程中執(zhí)行并得到結(jié)果，匯總這些結(jié)果得到原始任務(wù)的結(jié)果。在分解的過(guò)程中，如果子任務(wù)的規(guī)模還不足以直接執(zhí)行，則對(duì)子任務(wù)繼續(xù)分解，直到所有子任務(wù)都適合在目標(biāo)平臺(tái)直接求解為止。圖1所示為Fork/Join框架的原理示意圖。

將適合求解的子任務(wù)分配到多路系統(tǒng)或多核心系統(tǒng)的獨(dú)立計(jì)算單元中運(yùn)算，則可以充分利用計(jì)算資源。具體應(yīng)用過(guò)程中，軟件設(shè)計(jì)人員只需要關(guān)心任務(wù)分解、求解以及匯總結(jié)果的方法，線(xiàn)程調(diào)度、傳遞中間結(jié)果等基礎(chǔ)工作由Fork/Join框架完成。

2 應(yīng)用Fork/Join框架

當(dāng)前共有兩種方法獲得JSR-166y的代碼，一種是從Concurrency JSR-166 Interest Site網(wǎng)站下載JSR-166y的源代碼，并確保使用JDK6.0的最新版本；另一種是使用JDK7.0版本，它包含JSR-166y的二進(jìn)制代碼。

Fork/Join框架中最常用到RecursiveTask類(lèi)、ForkJoinPool類(lèi)和Future接口，它們被放置在java.util.concurrent包內(nèi)，分別用于表示任務(wù)、建立線(xiàn)程池和獲取結(jié)果。以下以計(jì)算斐波那契數(shù)列的特定項(xiàng)為例說(shuō)明Fork/Join框架的使用方法，需要指出的是，具體算法能夠較好地說(shuō)明問(wèn)題，但不是最優(yōu)算法，不具備實(shí)用性。

2.1 描述任務(wù)

通過(guò)繼承RecursiveTask類(lèi)描述任務(wù)。該類(lèi)在設(shè)計(jì)的過(guò)程中使用了泛型，可以兼容任何返回類(lèi)型的任務(wù)；抽象方法compute()表示任務(wù)的分解、求解、匯總結(jié)果和返回結(jié)果，是框架中和具體任務(wù)聯(lián)系最緊密的方法。具體代碼如下：

class Fibonacci extends RecursiveTask {

final int n，threshold=20;

Fibonacci(int n) { this.n = n; }

protected Integer compute() {

if (n <= threshold)

return compute(n);

Fibonacci f1 = new Fibonacci(n - 1);

f1.fork();

Fibonacci f2 = new Fibonacci(n - 2);

return f2.compute() + f1.join();

}

public static int compute(int n){

if (n <= 1)

return n;

return compute(n-1)+compute(n-2);

}

}

代碼中使用到的fork()方法和join()方法由RecursiveTask的父類(lèi)ForkJoinTask類(lèi)實(shí)現(xiàn)，fork()方法用于將子任務(wù)添加到隊(duì)列中等待異步執(zhí)行；join()方法用于阻塞當(dāng)前任務(wù)等待子任務(wù)返回結(jié)果。返回語(yǔ)句同時(shí)實(shí)現(xiàn)了匯總子任務(wù)結(jié)果并返回。

2.2 建立線(xiàn)程池并提交任務(wù)

使用ForkJoinPool類(lèi)建立線(xiàn)程池，該類(lèi)默認(rèn)建立與機(jī)器可用線(xiàn)程數(shù)相等的線(xiàn)程池，也可以向構(gòu)造函數(shù)手動(dòng)傳遞線(xiàn)程數(shù)量。代碼如下：

ForkJoinPool fjp=new ForkJoinPool();

2.3 獲取結(jié)果

最后，使用Future實(shí)例獲取結(jié)果。在此，以計(jì)算第50項(xiàng)斐波那契數(shù)為例編寫(xiě)代碼如下：

ForkJoinTask fjt = new Fibonacci(50);

Future future = fjp.submit(fjt);

Integer result=future.get();

代碼中使用到的submit()方法由ForkJoinPool類(lèi)實(shí)現(xiàn)，用于提交任務(wù)并返回結(jié)果。同時(shí)，該類(lèi)還提供其它方法控制線(xiàn)程池，如shutdown()方法用于阻止ForkJoinPool實(shí)例接受新任務(wù)；shutdownNow()方法用于停止所有任務(wù)；awaitTermination()方法用于阻塞當(dāng)前線(xiàn)程直到ForkJoinPool實(shí)例中所有任務(wù)執(zhí)行結(jié)束。

3 結(jié)束語(yǔ)

從以上代碼中可以看出，使用JSR-166y中實(shí)現(xiàn)的Fork/Join框架，開(kāi)發(fā)人員只需要專(zhuān)注于待處理任務(wù)自身的邏輯特點(diǎn)，而不需要了解底層硬件和操作系統(tǒng)特性，也不需要編寫(xiě)線(xiàn)程調(diào)度的代碼，這些任務(wù)都由框架自身完成，有效地降低了開(kāi)發(fā)人員的工作量，又最大化利用了計(jì)算資源，不失為一種經(jīng)典的多線(xiàn)程開(kāi)發(fā)框架。

參考文獻(xiàn)：

[1]劉振英，方濱興，姜譽(yù)，張毅，趙宏.一個(gè)調(diào)度Fork-Join任務(wù)圖的新算法.北京：軟件學(xué)報(bào).2002，4.

[2]陳華平，黃劉生，安虹，陳國(guó)良.并行分布計(jì)算中的任務(wù)調(diào)度及其分類(lèi).重慶：計(jì)算機(jī)科學(xué)，2001，1.

[3]盧超，盧炎生，毛澄映.一種并發(fā)Java程序控制流模型.武漢：華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）.2008，1.

[4]張建軍，李慶華，瞿勇.基于任務(wù)復(fù)制的調(diào)度算法.北京：計(jì)算機(jī)工程與設(shè)計(jì)，2009，8.

[5]張建軍，楊峰，紀(jì)祥鯤.同構(gòu)環(huán)境中Join任務(wù)圖的一個(gè)調(diào)度算法.上海：計(jì)算機(jī)應(yīng)用與軟件.2010，7.

[6]殷國(guó)富，羅陽(yáng)，龍紅能，成爾京.并行設(shè)計(jì)子任務(wù)調(diào)度的遺傳算法原理與實(shí)現(xiàn)方法.北京：計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2004，8.

[7]蔣衛(wèi)民，張建軍.一個(gè)有效的Join任務(wù)圖的調(diào)度算法.武漢：計(jì)算機(jī)與數(shù)字工程.2011，4.

[8]鐘求喜，謝濤，陳火旺.任務(wù)分配與調(diào)度的共同進(jìn)化方法.北京：計(jì)算機(jī)學(xué)報(bào).2001，03.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文