前言
本篇是多线程系列中的一篇，咱们在从前的一篇文章中回忆了线程池的主要知识
Java多线程根底–线程的创立与线程池办理
过去了很长时刻，咱们简略概要一下：
- 规划目的：简化线程的运用，办理与复用，避免直接操作线程
- 怎么运用线程池
- 规划完成与源码细节
本篇咱们延续下去，回忆 Fork&Join。主要内容如下：
- 运用场景和留意事项
- 规划原理
- 示例代码演示运用办法以及和线程池简略对比
全文总结
内容为根底部分，简略拾遗的读者扫一眼总结即可，若均已掌握，没必要糟蹋时刻阅读细节
- ForkJoinPool是线程池的补充，并不是替代。线程池一般用于处理 独立的 恳求、使命
- 适合完成 “分治” 类算法，尤其是分治后递归调用的函数
- 适用于核算密集型，假如是I/O密集型，或许线程间同步等造成长时刻堵塞时，可合作ManagedBlocker运用
- Work Stealing（作业盗取）机制 和 双端行列，现已了解规划细节便不需求再看下去了
怎么运用
本章十分的根底，现已掌握怎么运用，但没有考虑过Fork&Join规划思路的读者，能够跳动到 原理
咱们选择一道简略题 核算斐波那契数 ,并运用递归算法求解。
斐波那契数 （通常用 F(n) 表明）构成的序列称为 斐波那契数列 。该数列由 0 和 1 开端，后边的每一项数字都是前面两项数字的和。也便是：
F(0) = 0，F(1) = 1
F(n) = F(n – 1) + F(n – 2)，其间 n > 1
给定 n ，请核算 F(n) 。
来历：力扣（LeetCode）
Fork&Join 完成
如题，咱们需求界说核算使命，这将经过继承 ForkJoinTask 完成，当核算使命不可分（或许没有必要分解）时，自行处理成果回来，不然分解使命。
static class Fibonacci extends RecursiveTask<Long> {
final int n;
public Fibonacci(int n) {
this.n = n;
}
@Override
protected Long compute() {
System.out.println("compute fib(" + n + "), in thread:" + Thread.currentThread().getName());
if (n <= 1) {
return (long) n;
}
Fibonacci f1 = new Fibonacci(n - 1);
f1.fork();
Fibonacci f2 = new Fibonacci(n - 2);
f2.fork();
return f2.join() + f1.join();
}
}
咱们经过 fork() 将子使命丢入使命行列，并经过 join() 得到核算后的成果。
接下来看一看运用ForkJoinPool履行使命：
咱们界说一个最大作业线程数为4的ForkJoinPool，并核算 Fib(5) 的成果。可依照CPU中心数取最大作业线程数
留意，由于没有针对核算进程做任何优化，并且运用了输出，不要核算过大的值折腾电脑
class Demo {
public static void main(String[] args) {
ForkJoinPool forkJoinPool = new ForkJoinPool(4);
Fibonacci fib = new Fibonacci(5);
Long result = forkJoinPool.invoke(fib);
System.out.println(result);
}
}
经过 invoke(ForkJoinTask<T> task) 能够在当时线程堵塞式获取核算成果。
经过 execute(ForkJoinTask<?> task) 能够进行异步处理，由于 class ForkJoinTask<V> implements Future<V>，
运用办法和Future共同，复习链接
能够看到，递归进程中有许多的重复,但这源于算法本身，
当递归算法本身会使得子使命发生重复核算或许重复使命时，应当考虑处理中心成果缓存，削减不必要的使命，能够削减重复核算和GC压力。
假如移除控制台输出，一般能够测验下核算第40个，不主张再核算你更靠后的值。
compute fib(5), in thread:ForkJoinPool-1-worker-1
compute fib(3), in thread:ForkJoinPool-1-worker-1
compute fib(1), in thread:ForkJoinPool-1-worker-1
compute fib(2), in thread:ForkJoinPool-1-worker-3
compute fib(0), in thread:ForkJoinPool-1-worker-3
compute fib(1), in thread:ForkJoinPool-1-worker-0
compute fib(4), in thread:ForkJoinPool-1-worker-2
compute fib(2), in thread:ForkJoinPool-1-worker-2
compute fib(0), in thread:ForkJoinPool-1-worker-2
compute fib(1), in thread:ForkJoinPool-1-worker-2
compute fib(3), in thread:ForkJoinPool-1-worker-2
compute fib(1), in thread:ForkJoinPool-1-worker-2
compute fib(2), in thread:ForkJoinPool-1-worker-0
compute fib(0), in thread:ForkJoinPool-1-worker-0
compute fib(1), in thread:ForkJoinPool-1-worker-3
5
原理
实际上，关于Java ForkJoin规划原理的分析，均源自其开发者 Doug Lea 的论文 A Java Fork/Join Framework 以及结合源码打开讨论。
时刻充裕的读者能够看一看论文原文，接下来咱们节选论文重要内容进行理解。
分治算法的中心思路
以伪代码描绘分治的思维如下，当问题满意小（无需再拆分）时，直接处理，不然拆分问题，处理并汇总成果
Result solve(Problem problem){
if(problem is small){
directly solve problem
}else{
split problem into independent parts
fork new subtasks to solve each part
join all subtasks
compose result from subresults
}
}
分治+并行的中心要求
中心要求:结构能够让构建的子使命并行履行，并且拥有一种等候子使命运转结束的机制。
不难理解这一要求。
让咱们考虑一下，线程池+Future是不是满意这一要求？
很显然，线程池满意这个要求，但线程池的部分战略，甚至Thread的许多中心规划，关于 Fork/Join思路 而言是剩余（过剩）的。
哪些是过剩的
包括这几个方面的过剩：
- Thread本身盯梢记载堵塞的手段
- 线程池对线程的办理
- 线程池对使命的办理
首要， 在同步和办理方面，Fork/Join使命只有简略的和常规的需求。例如，Fork/Join使命除了等候子使命履行成果，其他情况下不需求堵塞。 因而传统的用于盯梢记载堵塞线程的价值，是一种过剩。
但这种过剩不会为了Fork/Join而推翻重建
其次，关于合理的根底使命粒度而言，构建和办理一个线程的价值，或许比履行使命花费的价值更大。线程池对线程的多种办理手段，大多是不必要的。
再者，Fork&Join 是处理同一个使命的子使命，它更像是一组 “事务”，只介意最终成果，不然就全部取消并丢弃。 而线程池是面向独立的使命，并且采用了BlockingQueue暂存使命，以保证并发时高效且准确。这些关于Fork&Join 而言，都是没有必要的。
FJTask结构思路图示
注:论文从开端就以 “FJTask结构” 指代了Java中即将完成的Fork&Join结构，以 “FJTask” 指代一个可由分治处理的使命
很朴素的思路，让使命得到拆分，并被指派到适宜的作业线程中履行，汇总出成果。
work-stealing
上文中咱们现已提及，线程池关于使命的办理机制关于 FJTask结构 而言是过剩的。除此之外，Fork&Join倾向于 “大使命优先” 去盗取使命。
这也是Java API文档中提到的，ForkJoinPool和线程池最大的不同（究竟中心线程数和最大线程数共同的线程池，办理线程是类似的）
all threads in the pool attempt to find and execute tasks submitted to the pool and/or created by other active tasks (eventually blocking waiting for work if none exist).
This enables efficient processing when most tasks spawn other subtasks (as do most ForkJoinTasks), as well as when many small tasks are submitted to the pool from external clients.
Especially when setting asyncMode to true in constructors, ForkJoinPools may also be appropriate for use with event-style tasks that are never joined.
依照该规划思路，先让每一个作业线程拥有自己的使命行列，这样在办理办法上才有减负的空间。
参阅CILK的规划，给FJTask结构制定如下的使命办理战略
- 每一个作业线程保护本身调度行列中的可运转使命
- 行列以双端行列的方式被保护，支撑后进先出:LIFO的push和pop操作; 和先进先出:FIFO的take操作
- 作业线程将使命所发生的子使命，放入到作业线程本身的双端行列中
- 处理行列中的使命时，作业线程运用后进先出（LIFO）的战略，递归
- 当一个作业线程，没有本地使命可运转时，它将测验盗取其他作业线程的使命。此时依照先进先出(FIFO)的战略，即大使命优先。
- 当一个作业线程触及了join操作，它将测验处理其他使命，直到方针使命被告知现已结束（经过isDone办法）。一切的使命都会无堵塞的完成。
当一个作业线程，没有本地使命可运转，且无法从其他线程中获取使命时，它就会退出（经过yield、sleep和/或许优先级调整）并经过一段时刻之后再度测验直到一切的作业线程都被告知他们都处于空闲的状况。在这种情况下，他们都会堵塞直到其他的使命再度被上层调用。
其间的1-5条，均在下图中得到体现。
椭圆代表了作业线程，它内部保护一个双端行列，经过Pushing 放入使命，经过Popping弹出使命履行，并或许被其他作业者从另一端盗取使命
作者按：源码部分本篇不打开，主张没有读过源码的读者，花点时刻泛读一二
ManagedBlocker
这是 ForkJoinPool中采用的，为使命供给扩展办理并行数的接口。
在FJTask中，咱们期望充沛的发挥多核CPU的核算性能，它被规划的擅长核算，但遇到会堵塞的使命时，CPU则会被糟蹋。
往往在或许会堵塞的使命中，咱们期望能添加线程来处理使命，而不是单纯的堵塞等候。
public static interface ManagedBlocker {
boolean block() throws InterruptedException;
boolean isReleasable();
}
完成并调用：ForkJoinPool#managedBlock。
isReleasable(): 假如不需求堵塞，则回来 true;
block(): 或许堵塞当时线程，例如等候锁定或条件, 假如没有额定的堵塞必要，回来true。
关于创立补偿线程的细节，不再打开。
