浅析JDK1.7中的Fork/Join框架

【摘要】 随着多核以及众核处理器的快速发展与不断普及，越来越多的人开始关注面向多核的并行编程。Fork/Join框架是Java从JDK1.7版本开始引入的一种并行编程框架，该框架可以满足多核时代并行编程的要求。本文针对Fork/Join框架的基本思想、工作窃取机制以及如何在具体编程环境中使用Fork/Join框架进行了详细的介绍。

【关键字】 Fork/Join框 并行编程 分而治之 阈值

一、引言

当前是多核时代的过渡期，面向多核的并行编程已经成为了计算机领域的研究热点。然而，大部分程序开发人员还保留着传统的串行编程习惯，而且目前的主流算法仍以串行为主。与串行编程相比，并行编程可以缩短任务执行的时间，提高任务执行的效率，充分发挥多核处理器的资源优势。因此，越来越多的人开始关注和使用并行编程。

为了满足多核时代并行编程的要求，Java从JDK1.7版本开始引入Fork/Join框架，该框架是适用于多核处理器上并行编程的轻量级并行框架，可以充分的利用多核处理器的处理能力，从而更好地提高程序的性能。本文主要对Fork/Join框架进行了研究，详细的介绍了该框架的的编程思想、工作窃取机制以及如何使用该框架进行编程。

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

Fork/Join框架的编程思想是分而治之[1]，即将一个复杂的任务递归分解成多个子任务并行执行，等到所有子任务执行完毕后再对子任务的结果进行汇总，从而得到原始任务的结果。在使用Fork/Join框架进行程序设计时，通常需要程序员手动设置一个临界值[2]（threshold）作为任务划分的依据。当任务的规模大于该临界值时，Fork/Join框架采用递归的方式来分解任务，直到任务规模小于该临界值时才停止。图1给出了Fork/Join框架分解任务的示意图，如图1所示，应用Fork/Join框架执行任务时，通过分解操作将任务递归分解为多个子任务，通过合并操作将可以子任务的结果合并，从而得到原始任务的结果。

三、工作窃取算法

Fork/Join框架的核心是工作窃取算法[3]，通过该算法可以尽量使每一个线程都处于忙碌状态，提高资源的利用率。在Fork/Join框架中，首先将任务分解为多个相互独立的子任务，并把每一个子任务存放到一个双端队列中；然后为每一个双端队列创建一个单独的线程来执行队列中的任务。线程在执行本地队列中的任务时，每次都会从队列的头部取出任务来执行，当使用fork操作产生新任务时，也会把新任务存放到该队列的头部，这就保证fork出来的新任务尽快得到执行。最后，当某个工作线程将自己本地队列中的任务全部执行完毕后，就会从其他未执行完毕的任务队列的尾部窃取一个任务执行，这样既可以减少两个线程之间的竞争，又可以节省程序的执行时间。

四、Fork/Join框架在具体编程环境中的应用

应用Fork/Join框架进行程序设计，主要依据ForkJoinTask和ForkJoinPool两个类。其中，ForkJoinTask类主要负责对任务大小进行判定、划分任务以及将子任务分配给线程等操作；ForkJoinPool类采用线程池的方式完成任务的执行。

4.1 ForkJoinTask

使用Fork/Join框架执行任务，首先要建立一个任务类来表示程序中具体执行的任务内容。ForkJoinTask类提供了RecursiveAction和RecursiveTask两个子类分别用来创建无返回值和有返回值的任务。程序员在创建任务类时，要根据该任务有无返回值选择继承RecursiveAction类或RecursiveTask类。当任务类创建完毕后需要重写父类中的compute（）方法。compute（）方法中的内容是Fork/Join框架的核心内容，一般情况下，compute（）方法中主要包含为以下三方面内容：

1、判定：在compute（）方法中，首先要对任务的大小以及程序中的线程个数进行判定，在程序设计中，通常用任务中的数据大小来表示任务的规模。如果任务中的数据小于程序员设定的临界值或程序中只有一个线程，就单线程执行程序，不进行任务划分。如果任务中的数据大于临界值，就要对数据进行递归分解。

2、数据分解：根据硬件线程数对数据区间进行等量划分，将任务中的数据区间划分成多个相互独立各不相同的子数据区间。

3、数据区间的分配：当任务中的数据区间完成划分后，将所有的子数据区间分配给每一个线程。

此外，在Fork/Join框架中，临界值是决定Fork/Join框架执行时间的关键因素。临界值设置过大，会

使得任务的数据区间太大，从而使程序的执行时间相对于单线程而言并不会有明显的提高；如果临界值设置过小，划分的子任务个数就会过多，程序会在子任务的管理与调度方面耗费一定的时间，从而使程序的性能也不会有明显提升，甚至不如顺序执行时间短。因此，程序员需要经过大量的实验与对比来设定一个合适的临界值。

4.2创建ForkJoinPool完成任务执行

任务类创建完毕后，由ForkJoinPool类负责执行任务。ForkJoinPool采用线程池的方式来完成任务的执行与管理，程序员只需要将创建好的任务类提交给ForkJoinPool中的线程池即可，对于线程创建、调度、管理等操作均由ForkJoinPool提供，不需要程序员手动编写。此外，ForkJoinPool类还提供了一系列的方法来了解线程池中线程的执行状态：例如getParallelism（）方法可以得到线程池中的并行程度；getStealCount（）方法可以获得线程池中的任务窃取情况；getActiveTreadCount方法可以获取线程池中正在执行任务的线程个数；getPoolSize（）用来获取线程池中创建的线程个数等。

五、结束语

本文针对JDK1.7中Fork/Join框架的相关内容进行了详细的介绍，通过介绍该框架的思想与具体实现细节来帮助程序开发人员更好地应用这一框架。使用Fork/Join框架进行程序设计，开发人员只需要关注任务自身的特性以及设定合理的阈值，对于线程的创建、调度、管理等复杂的操作，可以交给框架本身来完成，不仅减少了程序员的工作量，还充分发挥了多核处理器的资源优势，是一种经典的多线程开发框架。

参 考 文 献

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