Fork/Join框架是Java7提供了的一个用于并行执行任务的框架， 是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。
可以通过一段伪代码来理解ForkJoin的基本思想
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
可以了解到ForkJoin的基本思想，当任务足够小的时候直接解决它，否则将任务分割成可以独立解决的部分，小的任务解决后再将它们合并，得到大的任务结果。
image.png
所以Fork/Join框架要完成两件事情：
- 任务分割：首先Fork/Join框架需要把大的任务分割成足够小的子任务，如果子任务比较大的话还要对子任务进行继续分割
- 执行任务并合并结果：分割的子任务分别放到双端队列里，然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都放在另外一个队列里，启动一个线程从队列里取数据，然后合并这些数据。
主要角色及特点
-
ForkJoinPool：用于执行ForkJoinTask任务的执行池，不再是传统执行池 Worker+Queue 的组合模式，而是维护了一个队列数组WorkQueue，这样在提交任务和线程任务的时候大幅度的减少碰撞。 -
WorkQueue：双向列表，用于任务的有序执行，如果WorkQueue用于自己的执行线程Thread，线程默认将会从top端选取任务用来执行 - LIFO。因为只有owner的Thread才能从top端取任务，所以在设置变量时，int top; 不需要使用volatile。 -
ForkJoinWorkThread: 用于执行任务的线程，用于区别使用非ForkJoinWorkThread线程提交的task；启动一个该Thread，会自动注册一个WorkQueue到Pool，这里规定，拥有Thread的WorkQueue只能出现在WorkQueue数组的奇数位。 -
ForkJoinTask: 任务，它比传统的任务更加轻量，不再对是Runnable的子类，提供fork/join方法用于分割任务以及聚合结果。 - 工作窃取：为了充分施展并行运算，该框架实现了复杂的 worker steal算法，当任务处于等待中，thread通过一定策略不让自己挂起，充分利用资源。
工作窃取算法
所谓work-stealing算法，指的是线程在完成本线程维护队列中的任务后，可以从其他线程维护的队列中窃取任务来执行，与其说窃取，不如说是帮助其他线程干活。
线程每次从所维护队列的头部取任务执行，当队列中没有任务可执行时，该线程会去其他线程维护队列的尾部窃取任务执行。换句话说，对于本线程维护的队列，任务执行的顺序是LIFO（后进先出），窃取其他线程队列任务的执行顺序是FIFO（先进先出）。看下工作窃取示意图：
image.png
