1. 介绍

JDK1.7在并发包里面引入了这个玩意儿。根据 Doug Lea 的论文——《A Java Fork/Join Framework》而来。主要通过分而治之(把大任务分割成若干个小任务)然后合并结果这种思想来实现的线程池。有更加好的并发性能。之所以有更好的并发性能,是因为其充分利用了所有线程的工作能力,避免空闲线程,充分发挥多核并行的处理能力。这个关键是后面的working stealing算法。

此外强烈推荐下Java7中的ForkJoin并发框架初探(中)这个系列的文章,作为我这篇文章的补充阅读吧。写的很好。

PS: 本文的介绍主要以JDK1.7版本为例

2. ForkJoinPool框架原理

该框架主要依靠fork和join两个操作,一般对这两个操作的解释如下:
fork():开启一个新线程(或是重用线程池内的空闲线程),将任务交给该线程处理。
join():等待该任务的处理线程处理完毕,获得返回值。

这里很容易发现个问题,不断的fork如果是不断创建线程,岂不是要“线程数量爆炸”?事实上,ForkJoinPool用了一种work stealing的算法,避免产生大量线程。所以如果一开始设置线程池的线程数为N,实际上使用ForkJoinPool的时候也只会有4个线程。

3. work stealing(工作窃取)算法

下图演示了work stealing的基本思想。一个线程的任务通过fork()被分割成若干个小任务。下午中线程1和线程2都被分割成4个小任务。如果线程1执行完毕,那么他可以去窃取线程2的工作。当要发生线程窃取的时候,两个线程内的任务可以理解成放在一个线程自己的双端队列中。例如下图线程2中的任务被分割成若干个小任务(就WorkQueue里面的一个个小方块)放在其线程的双端队列中。线程2只从头部取任务处理,线程1窃取的时候只从尾部取任务处理。

work stealing算法的优点:利用了线程进行并行计算,减少了线程间的竞争。

work stealing算法的缺点:

  1. 如果双端队列中只有一个任务时,线程间会存在竞争。
  2. 额外的开销,例如双端队列

3.1 work stealing算法的一些约定

下面的1,2,3条看上图就可以明白。

  1. ForkJoinPool 的每个工作线程(ForkJoinWorkerThread)都维护着一个工作队列(WorkQueue),这是一个双端队列(Deque),里面存放的对象是任务(ForkJoinTask)。
  2. 每个工作线程在运行中产生新的任务(通常是因为调用了 fork())时,会放入工作队列的队尾,并且工作线程在处理自己的工作队列时,使用的是FILO(和栈一样) 方式,也就是说每次从队尾取出任务来执行。
  3. 每个工作线程在处理自己的工作队列同时,会尝试窃取一个任务(或是来自于刚刚提交到 pool 的任务,或是来自于其他工作线程的工作队列),窃取的任务位于其他线程的工作队列的队首,也就是说工作线程在窃取其他工作线程的任务时,使用的是 FIFO 方式。
  4. 在遇到 join() 时,如果需要 join 的任务尚未完成,则会先处理其他任务,并等待其完成。
  5. 在既没有自己的任务,也没有可以窃取的任务时,进入休眠。

3.2 源码解读

Java7中的ForkJoin并发框架初探(中)中说的比较详细,建议看这篇,我这里就不赘述了。

总体上就是有个ForkJoinWorkerThread对象会维护一个双端队列保存ForkJoinTask。ForkJoinTask里面的fork方法会往ForkJoinWorkerThread入队子任务,join方法会从ForkJoinWorkerThread对象中取回ForkJoinTask对象执行里面的compute方法(调用join方法本质也是执行compite方法)。

ForkJoinPool源码里面的work()里面的scan()方法描述了线程池是如何工作的。基本过程是:

  1. 线程会先执行ForkJoinWorkerThread对象内维护的任务队列中的任务,即ForkJoinWorkerThread的execTask()方法中的循环实现。通常是LIFO,即去最新的任务。也有特殊情况,这个根据变量locallyFifo的值来判断。
  2. 处理完最新的任务之后会尝试做任务窃取,尝试从其他线程中获取任务。窃取任务过程发现被别人窃取的话,可以窃取“窃取者”的任务。这个过程可以看下图。
  3. 任务窃取条件不满足时(本地工作队列里面的FJ task全部完成,并且没有任何可以被窃取FJ任务的线程了),跑到提交队列中获取提交的任务(其他非ForkJoinTask)

PS:当ForkJoinWorkerThread里面执行一个具体的ForkJoinTask时,其工作过程如下。下图描述了ForkJoinWorkerThread是如何执行一个ForkJoinTask的。第一步从调用其join()方法开始。实际使用定义好的task的时候都会继承ForkJoinTask的子类RecursiveAction或者RecursiveTask。然后调用join方法实际上是调用重写的compute方法来执行。compute方法需要自己重写。这样调用join()方法的时候等价于调用了自己的compute()方法了。

4. 什么时候用ForkJoinPool

可以参考: Java Tip: When to use ForkJoinPool vs ExecutorService

简单来说:如果你的问题能很容易分解成子问题,则比较适合ForkJoinPool。适合CPU密集型的场景。

此外官方还有一些小贴士提醒:
ForkJoinTasks should perform relatively small amounts of computation. Large tasks should be split into smaller subtasks, usually via recursive decomposition. As a very rough rule of thumb,a task should perform more than 100 and less than 10000 basic computational steps, and should avoid indefinite looping. If tasks are too big, then parallelism cannot improve throughput. If too small, then memory and internal task maintenance overhead may overwhelm processing.

5. 使用例子

Java7中的ForkJoin并发框架初探(下)中提到的错误例子,值得玩味。这个反面示例告诉我们。。一定牢记fork会把子任务放到当前线程的工作队列的末尾。

使用例子就在RecursiveAction这个类源码的注释里面有,大家可以自己看下。

此外例如JDK8里面的G1垃圾收集器的垃圾收集线程,也用了fork join pool。

6. JDK7和JDK8上ForkJoinPool设计的不同

SF上的一些回答也建议看看。
这个问题中采纳答案说明了JDK8里面对FJ不同的实现。在JDK1.7里面是有一个全局的提交队列负责接受非FJ的任务。后来发现这样设计存在瓶颈。在JDK8里面,外部提交的非FJ任务也会分配到一个本地的FJ工作队列。

详情可以查阅:
Java ForkJoinPool with non-recursive tasks, does work-stealing work?

参考资料:

  1. Java 并发编程笔记:如何使用 ForkJoinPool 以及原理
  2. Java Tip: When to use ForkJoinPool vs ExecutorService
  3. Java7中的ForkJoin并发框架初探(上)