陳永青

【摘要】 隨著多核以及眾核處理器的快速發(fā)展與不斷普及，越來(lái)越多的人開(kāi)始關(guān)注面向多核的并行編程。Fork/Join框架是Java從JDK1.7版本開(kāi)始引入的一種并行編程框架，該框架可以滿足多核時(shí)代并行編程的要求。本文針對(duì)Fork/Join框架的基本思想、工作竊取機(jī)制以及如何在具體編程環(huán)境中使用Fork/Join框架進(jìn)行了詳細(xì)的介紹。

【關(guān)鍵字】 Fork/Join框 并行編程 分而治之 閾值

一、引言

當(dāng)前是多核時(shí)代的過(guò)渡期，面向多核的并行編程已經(jīng)成為了計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)。然而，大部分程序開(kāi)發(fā)人員還保留著傳統(tǒng)的串行編程習(xí)慣，而且目前的主流算法仍以串行為主。與串行編程相比，并行編程可以縮短任務(wù)執(zhí)行的時(shí)間，提高任務(wù)執(zhí)行的效率，充分發(fā)揮多核處理器的資源優(yōu)勢(shì)。因此，越來(lái)越多的人開(kāi)始關(guān)注和使用并行編程。

為了滿足多核時(shí)代并行編程的要求，Java從JDK1.7版本開(kāi)始引入Fork/Join框架，該框架是適用于多核處理器上并行編程的輕量級(jí)并行框架，可以充分的利用多核處理器的處理能力，從而更好地提高程序的性能。本文主要對(duì)Fork/Join框架進(jìn)行了研究，詳細(xì)的介紹了該框架的的編程思想、工作竊取機(jī)制以及如何使用該框架進(jìn)行編程。

二、Fork/Join框架的分治思想

Fork/Join框架的編程思想是分而治之[1]，即將一個(gè)復(fù)雜的任務(wù)遞歸分解成多個(gè)子任務(wù)并行執(zhí)行，等到所有子任務(wù)執(zhí)行完畢后再對(duì)子任務(wù)的結(jié)果進(jìn)行匯總，從而得到原始任務(wù)的結(jié)果。在使用Fork/Join框架進(jìn)行程序設(shè)計(jì)時(shí)，通常需要程序員手動(dòng)設(shè)置一個(gè)臨界值[2]（threshold）作為任務(wù)劃分的依據(jù)。當(dāng)任務(wù)的規(guī)模大于該臨界值時(shí)，F(xiàn)ork/Join框架采用遞歸的方式來(lái)分解任務(wù)，直到任務(wù)規(guī)模小于該臨界值時(shí)才停止。圖1給出了Fork/Join框架分解任務(wù)的示意圖，如圖1所示，應(yīng)用Fork/Join框架執(zhí)行任務(wù)時(shí)，通過(guò)分解操作將任務(wù)遞歸分解為多個(gè)子任務(wù)，通過(guò)合并操作將可以子任務(wù)的結(jié)果合并，從而得到原始任務(wù)的結(jié)果。

三、工作竊取算法

Fork/Join框架的核心是工作竊取算法[3]，通過(guò)該算法可以盡量使每一個(gè)線程都處于忙碌狀態(tài)，提高資源的利用率。在Fork/Join框架中，首先將任務(wù)分解為多個(gè)相互獨(dú)立的子任務(wù)，并把每一個(gè)子任務(wù)存放到一個(gè)雙端隊(duì)列中；然后為每一個(gè)雙端隊(duì)列創(chuàng)建一個(gè)單獨(dú)的線程來(lái)執(zhí)行隊(duì)列中的任務(wù)。線程在執(zhí)行本地隊(duì)列中的任務(wù)時(shí)，每次都會(huì)從隊(duì)列的頭部取出任務(wù)來(lái)執(zhí)行，當(dāng)使用fork操作產(chǎn)生新任務(wù)時(shí)，也會(huì)把新任務(wù)存放到該隊(duì)列的頭部，這就保證fork出來(lái)的新任務(wù)盡快得到執(zhí)行。最后，當(dāng)某個(gè)工作線程將自己本地隊(duì)列中的任務(wù)全部執(zhí)行完畢后，就會(huì)從其他未執(zhí)行完畢的任務(wù)隊(duì)列的尾部竊取一個(gè)任務(wù)執(zhí)行，這樣既可以減少兩個(gè)線程之間的競(jìng)爭(zhēng)，又可以節(jié)省程序的執(zhí)行時(shí)間。

四、Fork/Join框架在具體編程環(huán)境中的應(yīng)用

應(yīng)用Fork/Join框架進(jìn)行程序設(shè)計(jì)，主要依據(jù)ForkJoinTask和ForkJoinPool兩個(gè)類。其中，F(xiàn)orkJoinTask類主要負(fù)責(zé)對(duì)任務(wù)大小進(jìn)行判定、劃分任務(wù)以及將子任務(wù)分配給線程等操作；ForkJoinPool類采用線程池的方式完成任務(wù)的執(zhí)行。

4.1 ForkJoinTask

使用Fork/Join框架執(zhí)行任務(wù)，首先要建立一個(gè)任務(wù)類來(lái)表示程序中具體執(zhí)行的任務(wù)內(nèi)容。ForkJoinTask類提供了RecursiveAction和RecursiveTask兩個(gè)子類分別用來(lái)創(chuàng)建無(wú)返回值和有返回值的任務(wù)。程序員在創(chuàng)建任務(wù)類時(shí)，要根據(jù)該任務(wù)有無(wú)返回值選擇繼承RecursiveAction類或RecursiveTask類。當(dāng)任務(wù)類創(chuàng)建完畢后需要重寫(xiě)父類中的compute（）方法。compute（）方法中的內(nèi)容是Fork/Join框架的核心內(nèi)容，一般情況下，compute（）方法中主要包含為以下三方面內(nèi)容：

1、判定：在compute（）方法中，首先要對(duì)任務(wù)的大小以及程序中的線程個(gè)數(shù)進(jìn)行判定，在程序設(shè)計(jì)中，通常用任務(wù)中的數(shù)據(jù)大小來(lái)表示任務(wù)的規(guī)模。如果任務(wù)中的數(shù)據(jù)小于程序員設(shè)定的臨界值或程序中只有一個(gè)線程，就單線程執(zhí)行程序，不進(jìn)行任務(wù)劃分。如果任務(wù)中的數(shù)據(jù)大于臨界值，就要對(duì)數(shù)據(jù)進(jìn)行遞歸分解。

2、數(shù)據(jù)分解：根據(jù)硬件線程數(shù)對(duì)數(shù)據(jù)區(qū)間進(jìn)行等量劃分，將任務(wù)中的數(shù)據(jù)區(qū)間劃分成多個(gè)相互獨(dú)立各不相同的子數(shù)據(jù)區(qū)間。

3、數(shù)據(jù)區(qū)間的分配：當(dāng)任務(wù)中的數(shù)據(jù)區(qū)間完成劃分后，將所有的子數(shù)據(jù)區(qū)間分配給每一個(gè)線程。

此外，在Fork/Join框架中，臨界值是決定Fork/Join框架執(zhí)行時(shí)間的關(guān)鍵因素。臨界值設(shè)置過(guò)大，會(huì)

使得任務(wù)的數(shù)據(jù)區(qū)間太大，從而使程序的執(zhí)行時(shí)間相對(duì)于單線程而言并不會(huì)有明顯的提高；如果臨界值設(shè)置過(guò)小，劃分的子任務(wù)個(gè)數(shù)就會(huì)過(guò)多，程序會(huì)在子任務(wù)的管理與調(diào)度方面耗費(fèi)一定的時(shí)間，從而使程序的性能也不會(huì)有明顯提升，甚至不如順序執(zhí)行時(shí)間短。因此，程序員需要經(jīng)過(guò)大量的實(shí)驗(yàn)與對(duì)比來(lái)設(shè)定一個(gè)合適的臨界值。

4.2創(chuàng)建ForkJoinPool完成任務(wù)執(zhí)行

任務(wù)類創(chuàng)建完畢后，由ForkJoinPool類負(fù)責(zé)執(zhí)行任務(wù)。ForkJoinPool采用線程池的方式來(lái)完成任務(wù)的執(zhí)行與管理，程序員只需要將創(chuàng)建好的任務(wù)類提交給ForkJoinPool中的線程池即可，對(duì)于線程創(chuàng)建、調(diào)度、管理等操作均由ForkJoinPool提供，不需要程序員手動(dòng)編寫(xiě)。此外，F(xiàn)orkJoinPool類還提供了一系列的方法來(lái)了解線程池中線程的執(zhí)行狀態(tài)：例如getParallelism（）方法可以得到線程池中的并行程度；getStealCount（）方法可以獲得線程池中的任務(wù)竊取情況；getActiveTreadCount方法可以獲取線程池中正在執(zhí)行任務(wù)的線程個(gè)數(shù)；getPoolSize（）用來(lái)獲取線程池中創(chuàng)建的線程個(gè)數(shù)等。

五、結(jié)束語(yǔ)

本文針對(duì)JDK1.7中Fork/Join框架的相關(guān)內(nèi)容進(jìn)行了詳細(xì)的介紹，通過(guò)介紹該框架的思想與具體實(shí)現(xiàn)細(xì)節(jié)來(lái)幫助程序開(kāi)發(fā)人員更好地應(yīng)用這一框架。使用Fork/Join框架進(jìn)行程序設(shè)計(jì)，開(kāi)發(fā)人員只需要關(guān)注任務(wù)自身的特性以及設(shè)定合理的閾值，對(duì)于線程的創(chuàng)建、調(diào)度、管理等復(fù)雜的操作，可以交給框架本身來(lái)完成，不僅減少了程序員的工作量，還充分發(fā)揮了多核處理器的資源優(yōu)勢(shì)，是一種經(jīng)典的多線程開(kāi)發(fā)框架。

參 考 文 獻(xiàn)

[1] LEA D. A Java Fork/Join Framework[C]// Proceeding of the 2000 ACM Conference on Java Grande. New York： ACM， 2000： 36-43.

[2] DIG D， MARRERO J， ERNST M D. Refactoring sequential Java code for concurrency via concurrent libraries[C]// Proceeding of the 31st International Conference on Software Engineering. Washington， DC： IEEE Computer Society， 2009： 397-407.

[3] González J F. Java 7 Concurrency Cookbook[M]. Birmingham： Packt Publishing， 2012：171-205.