ForkJoinPool
是 Java 并行计算框架中的一个类,用于执行大量的小任务,并且这些任务可以相互独立地执行。它基于工作窃取算法,适用于分治(divide-and-conquer)算法。下面是一个详细的示例,展示如何使用 ForkJoinPool
来并行计算数组元素的和。
测试代码:
用 ForkJoinPool
来并行计算一个大数组的所有元素的和。这个任务可以通过分治方法进行分割,直到子任务足够小,可以直接计算。
public class ForkJoinSum extends RecursiveTask<Long> {private static final int THRESHOLD = 10_000;private final long[] array;private final int start;private final int end;public ForkJoinSum(long[] array, int start, int end) {this.array = array;this.start = start;this.end = end;}@Overrideprotected Long compute() {int length = end - start;if (length <= THRESHOLD) {long sum = 0;for (int i = start; i < end; i++) {sum += array[i];}return sum;} else {int mid = start + length / 2;ForkJoinSum leftTask = new ForkJoinSum(array, start, mid);ForkJoinSum rightTask = new ForkJoinSum(array, mid, end);// 递归分割任务leftTask.fork();rightTask.fork();// 合并结果long rightResult = rightTask.join();long leftResult = leftTask.join();return leftResult + rightResult;}}public static void main(String[] args) {long[] array = new long[20_000];for (int i = 0; i < array.length; i++) {array[i] = i;}ForkJoinPool pool = new ForkJoinPool();ForkJoinSum task = new ForkJoinSum(array, 0, array.length);long result = pool.invoke(task);System.out.println("Sum: " + result);}
}
关键代码解释:
-
RecursiveTask 类:
RecursiveTask
是一个抽象类,代表可以返回结果的任务。 -
RecursiveTask.compute() 递归任务分割:
- 检查任务的大小是否小于或等于阈值
THRESHOLD
。如果是,则直接计算数组元素的和。 - 如果任务的大小大于阈值,则将任务分割成两部分,并分别调用
fork
方法来异步执行这些子任务。
- 检查任务的大小是否小于或等于阈值
-
RecursiveTask fork 和 join 方法:
fork()
方法将子任务提交给ForkJoinPool
以便异步执行。join()
方法等待子任务完成并返回其结果。
-
ForkJoinPool 类:
ForkJoinPool
是任务执行的线程池。pool.invoke(task)
提交主任务并等待其完成。
窃取算法:
窃取算法(Work Stealing Algorithm)是一种用于并行计算的调度算法,特别适用于任务并行的环境中。它的核心思想是,当一个处理器(或线程)完成了自己的任务队列中的所有任务时,它可以从其他处理器的任务队列中“窃取”任务来执行,从而提高系统的整体利用率和性能。
工作窃取算法的基本原理
-
任务分割:
- 任务被分割成多个子任务,并分配到不同的处理器(或线程)的任务队列中。
-
本地执行:
- 每个处理器优先处理自己任务队列中的任务。
-
任务窃取:
- 如果一个处理器完成了自己任务队列中的所有任务,它就会尝试从其他处理器的任务队列中窃取任务来继续执行。
优点
- 负载均衡: 通过窃取其他处理器的任务,避免了某些处理器空闲而其他处理器过载的情况。
- 高效利用资源: 提高了系统的整体资源利用率和并行性。
工作窃取算法的应用
- ForkJoinPool: Java 中的
ForkJoinPool
就是基于工作窃取算法实现的。它适用于分治算法,可以将大任务分割成多个小任务并行执行。 - 并行框架: 许多并行计算框架和库都采用了工作窃取算法,如 Cilk 和 TBB(Intel Threading Building Blocks)。
扩展知识
1. 在 Java 中,下划线 (_
) 可以用作数字字面量中的分隔符,以提高代码的可读性。Java 7 及其以后的版本支持这种特性。下划线在数字中不影响其值,只是为了使长数字更易于阅读。
long number = 1_000_000L; // 表示一百万
int binary = 0b1010_1010; // 二进制表示,等价于 0b10101010
double pi = 3.14_15_92; // 浮点数表示,等价于 3.141592