Fork/Join解读
概念
Fork/Join 是 JDK 1.7 加入的新的线程池实现，它体现的是一种分治思想，适用于能够进行任务拆分的 cpu 密集型 运算
所谓的任务拆分，是将一个大任务拆分为算法上相同的小任务，直至不能拆分可以直接求解。跟递归相关的一些计 算，如归并排序、斐波那契数列、都可以用分治思想进行求解
Fork/Join 在分治的基础上加入了多线程，可以把每个任务的分解和合并交给不同的线程来完成，进一步提升了运 算效率
Fork/Join 默认会创建与 cpu 核心数大小相同的线程池
关键点
Fork/Join（分而治之）是一种并行计算模型，用于解决递归性的、可以被分解为更小子任务的问题。它是 Java 7 引入的一个特性，并在 Java.util.concurrent 包中提供了相应的类来支持。
Fork/Join 模型基于以下两个关键操作：
- Fork（分解）：将一个大任务分解为若干个小任务，并把这些小任务放入工作队列中，等待被执行。
- Join（合并）：对小任务的执行结果进行合并，得到大任务的最终结果。
Fork/Join 模型的核心思想是递归地将问题划分为更小的子问题，直到子问题足够简单，可以直接求解。然后通过合并子问题的结果，最终得到原始问题的解。
在 Java 中，Fork/Join 模型的实现主要依赖于以下两个类：
- ForkJoinPool：是线程池的实现，用于管理任务的执行。它允许创建一个工作线程组，每个线程都有自己的工作队列。任务会被分发给空闲的工作线程执行，如果一个线程的工作队列为空，它可以从其他线程的队列中窃取任务来执行。
- RecursiveTask 和 RecursiveAction：这两个抽象类是用来表示可分解的任务的。RecursiveTask 用于返回结果的任务，而 RecursiveAction 则用于不返回结果的任务。我们需要继承这些类，并实现 compute() 方法来执行任务划分和合并操作。
典型的使用场景包括在计算密集型任务中，例如大规模数据处理、图像处理、并行排序等。
Fork/Join 模型利用任务的递归分解和合并，能够充分利用多核处理器的性能，并提供了一种简洁高效的并行计算方式。
使用
提交给 Fork/Join 线程池的任务需要继承 RecursiveTask（有返回值）或 RecursiveAction（没有返回值），例如下 面定义了一个对 1~n 之间的整数求和的任务
class AddTask extends RecursiveTask<Integer> {
int n;
public AddTask(int n) {
this.n = n;
}
@Override
public String toString() {
return "{" + n + '}';
}
@Override
protected Integer compute() {
// 如果 n 已经为 1，可以求得结果了
if (n == 1) {
System.out.println("join()"+n);
return n;
}
// 将任务进行拆分(fork)
AddTask t1 = new AddTask(n - 1);
t1.fork();
System.out.println("fork()"+n+" "+ t1);
// 合并(join)结果
int result = n + t1.join();
System.out.println("join()"+n+"+"+t1+"="+result );
return result;
}
}然后提交给 ForkJoinPool 来执行
public class Test {
public static void main(String[] args) {
ForkJoinPool pool = new ForkJoinPool(4);
System.out.println(pool.invoke(new AddTask(5)));
}
}输出
fork()3 {2} fork()5 {4} fork()2 {1} fork()4 {3} join()1 join()2+{1}=3 join()3+{2}=6 join()4+{3}=10 join()5+{4}=15 15
用图来表示
改进
class AddTask3 extends RecursiveTask<Integer> {
int begin;
int end;
public AddTask3(int begin, int end) {
this.begin = begin;
this.end = end;
}
@Override
public String toString() {
return "{" + begin + "," + end + '}';
}
@Override
protected Integer compute() {
// 5, 5
if (begin == end) {
log.debug("join() {}", begin);
return begin;
}
// 4, 5
if (end - begin == 1) {
log.debug("join() {} + {} = {}", begin, end, end + begin);
return end + begin;
}
// 1 5
int mid = (end + begin) / 2;
// 3
AddTask3 t1 = new AddTask3(begin, mid);
// 1,3
t1.fork();
AddTask3 t2 = new AddTask3(mid + 1, end);
// 4,5
t2.fork();
log.debug("fork() {} + {} = ?", t1, t2);
int result = t1.join() + t2.join();
log.debug("join() {} + {} = {}", t1, t2, result);
return result;
}
}然后提交给 ForkJoinPool 来执行
public static void main(String[] args) {
ForkJoinPool pool = new ForkJoinPool(4);
System.out.println(pool.invoke(new AddTask3(1, 10)));
}结果
[ForkJoinPool-1-worker-0] - join() 1 + 2 = 3 [ForkJoinPool-1-worker-3] - join() 4 + 5 = 9 [ForkJoinPool-1-worker-0] - join() 3 [ForkJoinPool-1-worker-1] - fork() {1,3} + {4,5} = ? [ForkJoinPool-1-worker-2] - fork() {1,2} + {3,3} = ? [ForkJoinPool-1-worker-2] - join() {1,2} + {3,3} = 6 [ForkJoinPool-1-worker-1] - join() {1,3} + {4,5} = 15 15
用图来表示
