陳永青

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

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

一、引言

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

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

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

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

三、工作竊取算法

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

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

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

4.1 ForkJoinTask

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

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

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

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

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

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

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

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

五、結(jié)束語

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

參 考 文 獻

[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.