知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# Fork/Join 框架与工作窃取 > 导读:本文从"一个能拆成子任务的大计算,用普通线程池为什么总是有线程闲着、有线程忙死"这一具体疑问出发,把分治模型与适用条件、RecursiveTask 与 RecursiveAction 的区别、fork/join/invokeAll 的语义与调用时机、工作窃取的双端队列原理、ForkJoinPool 与 commonPool 的并行度配置、以及与并行流的关系逐项讲透,最后给出适用/不适用场景和一个可运行的大数组求和示例。适合已经会用线程池、想搞懂 Fork/Join 该在什么场景下用、又该怎么正确拆任务的同学。 ## 一、先建立全局认知 ### Q:什么样的任务适合 Fork/Join?分治模型的适用条件是什么? A:结论先行——适合"一个大任务能被递归地拆成若干结构相同、彼此独立、无共享可变状态、无阻塞 IO 的小任务,再把结果合并"的场景,也就是分治(divide and conquer)。 为什么:Fork/Join(分叉/合并)的核心假设是"任务可以拆、拆出来的子任务互相独立"。只有独立,才能并行而不需要加锁;只有可拆,才能把工作量摊到多个线程;只有无阻塞 IO,才能保证工作线程都在真正干活而不是在等待。三条缺一,收益就会打折甚至变负。 分治模型可以用一张流程图概括: ```text 大任务 / \ 子任务A 子任务B / \ / \ A1 A2 B1 B2 \ / \ / A 结果 B 结果 \ / 合并 ——> 最终结果 拆到足够小(<= 阈值 threshold)时,直接串行计算,不再继续拆 ``` 判断清单(用来给自己做"能不能用 Fork/Join"的自检): - **可拆分**:有自然的递归结构,比如数组区间、树节点、集合分片; - **子任务独立**:子任务之间不写同一份可变状态,否则要么加锁(抵消并行收益),要么结果错误; - **纯计算**:以 CPU 计算为主,不做阻塞 IO、不等待网络/数据库; - **粒度可控**:能定一个合理阈值,避免拆出成千上万个微小任务,让调度开销盖过计算本身。 反例:查询一个远程接口、下载文件、加锁更新同一个计数器——这些都不满足"独立/无 IO/无共享可变状态",不适合 Fork/Join。 ### Q:Fork/Join 和普通线程池(ThreadPoolExecutor)有什么本质区别? A:结论先行——本质区别在"任务排队方式":普通线程池所有线程共享一个任务队列,Fork/Join 让每个工作线程各有一个队列并支持工作窃取,从而让"任务里再提交任务"这件事变得高效。 为什么:`ThreadPoolExecutor` 的特点是"外部提交任务、线程从同一个队列取任务",它擅长处理彼此独立的短任务,但有个天然短板——当一个正在执行的任务内部又提交子任务、并需要等子任务结果时,它无法表达"父子任务"关系,容易写成"父任务占着线程等子任务"的死等。Fork/Join 的设计目标恰好是"任务可以 fork 出子任务、并 join 等待子任务",加上每个 worker 的本地队列,让父任务 fork 出的子任务尽量在本地被消化,减少跨线程争抢。 证据/示例:两种模型的任务来源不同:  *图:共享任务队列取任务与本地队列窃取的对比* ```text ThreadPoolExecutor: 生产者 ──> [ 共享任务队列 ] ──> 线程1 / 线程2 / 线程3 (谁有空谁取) ForkJoinPool: 提交 ──> 线程1 本地队列(自己 fork 的子任务大多放这里) 线程2 本地队列 线程3 本地队列 空闲线程可去别的线程队列"窃取"任务 ``` 关键点:Fork/Join 不是要取代 `ThreadPoolExecutor`,而是处理"可递归拆分的计算任务"这一类特定问题。不适用场景:IO 密集、任务彼此完全独立且不可递归拆分——这些用普通线程池更直接。 ### Q:fork、join、invokeAll 分别在什么时候调用? A:结论先行——`fork()` 是异步提交子任务(把子任务放进当前线程队列并安排执行),`join()` 是阻塞等待子任务结果,`invokeAll()` 是"批量 fork + 等全部完成"的便捷方法,三者都只能在 ForkJoinTask 的 `compute()` 计算过程中使用(或由外部 `invoke/submit` 触发)。 逐个说明: - **`fork()`**:把当前任务异步排入队列,调用后立即返回,不阻塞。它的语义是"这个子任务交出去,稍后再 join"。你不 fork,直接调用 `compute()` 就是同步串行执行,没有并行。 - **`join()`**:等待某个已 fork 的任务完成并返回结果。它会阻塞当前线程;但在 ForkJoinPool 内阻塞时,实现会尽量让工作线程"去帮着做别的任务"(这是 Fork/Join 相对普通阻塞的巧妙之处)。注意 join 不能被中断。 - **`invokeAll(...)`**:一次性提交一批子任务并等它们全部结束。它内部帮你处理了"哪些 fork、哪个在当前线程执行"的细节,写起来更简洁。 证据/示例(三种调用方式对比): ```java import java.util.concurrent.RecursiveTask; import java.util.concurrent.ForkJoinTask; class SumTask extends RecursiveTask<Long> { private final int[] a; private final int lo, hi; SumTask(int[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; } @Override protected Long compute() { if (hi - lo <= 1000) { long s = 0; for (int i = lo; i < hi; i++) s += a[i]; return s; } int mid = (lo + hi) >>> 1; // 写法一:显式 fork + join SumTask left = new SumTask(a, lo, mid); SumTask right = new SumTask(a, mid, hi); left.fork(); // 异步提交左半 long r = right.compute(); // 当前线程同步算右半 return left.join() + r; // 等左半结果并合并 // 写法二(等价、更简洁):批量提交 // SumTask l = new SumTask(a, lo, mid); // SumTask rr = new SumTask(a, mid, hi); // ForkJoinTask.invokeAll(l, rr); // return l.join() + rr.join(); } } ``` 关键点:`fork()` 只负责提交,不负责取结果,必须配 `join()`;`compute()` 内部不能写成"两个子任务都直接调用 `compute()`",那样只是串行递归。`invokeAll` 的 fork/内联执行细节由实现决定,不同 JDK 版本可能略有差异,行为以所用版本为准。适用与不适用:`invokeAll` 适合"一批子任务同质、需要全部完成"的场合,语义清晰;如果子任务之间有依赖先后或需要部分结果先处理,就用显式 fork/join 更灵活。 ## 二、理解核心机制 ### Q:RecursiveTask 和 RecursiveAction 有什么区别? A:结论先行——`RecursiveTask<V>` 有返回值(`compute()` 返回 `V`),`RecursiveAction` 没有返回值(`compute()` 返回 void),二者都继承自 `ForkJoinTask`,选哪个取决于"子任务要不要交出结果"。 为什么:Fork/Join 用一个抽象基类 `ForkJoinTask` 统一描述"可 fork/join 的任务",再按是否需要结果分成两支。需要合并结果(求和、求最值、排序)就用 `RecursiveTask`;只是"分区并行地做某件事"(并行填充数组、并行遍历、批量处理)就用 `RecursiveAction`。 证据/示例(两种子任务类型): ```java import java.util.concurrent.RecursiveTask; import java.util.concurrent.RecursiveAction; import java.util.Arrays; // 有返回值:并行求最大值 class MaxTask extends RecursiveTask<Integer> { private final int[] a; private final int lo, hi; MaxTask(int[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; } @Override protected Integer compute() { if (hi - lo <= 1000) { int m = Integer.MIN_VALUE; for (int i = lo; i < hi; i++) m = Math.max(m, a[i]); return m; } int mid = (lo + hi) >>> 1; MaxTask left = new MaxTask(a, lo, mid); MaxTask right = new MaxTask(a, mid, hi); left.fork(); int r = right.compute(); return Math.max(left.join(), r); } } // 无返回值:并行给数组分段赋值 class FillAction extends RecursiveAction { private final int[] a; private final int lo, hi; FillAction(int[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; } @Override protected void compute() { if (hi - lo <= 1000) { Arrays.fill(a, lo, hi, 1); return; } int mid = (lo + hi) >>> 1; invokeAll(new FillAction(a, lo, mid), new FillAction(a, mid, hi)); } } ``` 关键点:`RecursiveTask<V>` 的 `join()` 返回 `V`,可以直接参与合并;`RecursiveAction` 没有 join 返回值,它的"完成"本身就是结果。注意 `ForkJoinTask` 还有第三个子类 `CountedCompleter`,适合"所有子任务完成后触发收尾动作"的场景,但日常最常用的仍是上面两个。不适用场景:如果任务需要返回值但返回值极大(比如返回整个大数组),合并和复制的开销可能盖过收益,此时更适合 `RecursiveAction` 原地写结果。 ### Q:为什么"fork 一个子任务、当前线程直接算另一个"是优化技巧? A:结论先行——因为"fork 两个然后 join 两个"会让当前线程立刻进入等待,而"fork 一个、当前线程算另一个"能让当前线程在等待前先做掉一半工作,把任务调度开销和线程空转都降下来。 为什么:假设你写成: ```text left.fork(); right.fork(); return left.join() + right.join(); ``` 那么 `left`、`right` 都只是被"安排出去",当前线程在 `left.join()` 处立刻阻塞;如果此刻池里没有空闲线程,两个子任务都还没被取走,当前线程就白等。反过来,写成: ```text left.fork(); // 把左半交出去 long rightResult = right.compute(); // 当前线程就地计算右半 return left.join() + rightResult; // 再做左半的合并 ``` 当前线程 fork 完立刻"就地干活",把右半算完;这时候左半要么已被别的空闲线程窃取算完,要么才需要真正等一小会儿。整体上线程利用率更高,任务调度次数也更少。 证据/示例(这就是上文 `SumTask` 的写法)。对应的关键点: - **只 fork 一个**,另一个用 `compute()` 同步执行,别 fork 两个再一起 join; - **先 fork 再把当前线程投入到另一半**,避免先 join 后干活; - 顺序上习惯"`left.fork()`,然后当前线程算 `right`,最后 `left.join()`";哪一半交给队列其实可调,比如按数据局部性让当前线程算访问更热的那一段。 不适用场景:如果两个子任务体量悬殊(一个巨大一个极小),把巨大的那个 fork 出去、当前线程做小的,可能让当前线程很快做完又去等待——此时应结合阈值调整,而不是机械套用。 ### Q:工作窃取(work-stealing)的双端队列是怎么工作的? A:结论先行——每个工作线程拥有一个双端队列(deque),自己的任务从"头部"入队和出队(后进先出 LIFO,做深度优先),空闲线程则从别人队列的"尾部"窃取任务(先进先出 FIFO,偷最老的),两端操作减少冲突。 为什么:如果用单一共享队列,所有线程都去抢一个队头,锁竞争与缓存行争用会很严重。让每个 worker 有本地队列后,绝大多数 fork/pop 都发生在本地,几乎无竞争;只有当某个线程把自己的活儿干完了,才去别的队列尾部"偷"点活。为什么自己从头部取、别人从尾部偷?因为在递归分治中,越晚 fork 出来的任务通常粒度越细、越"靠近自己",本地后进先出符合深度优先、利于数据局部性;而偷最老(尾部)的任务通常粒度更粗、偷一个能顶一阵,减少偷取次数。这也顺便减少了头尾两端的争用。 ASCII 示意图:  *图:Fork/Join 框架与工作窃取:双端队列 head / base* ```text Worker-1 的队列 Worker-2 的队列 ┌─────────────── head(自己 push / pop,LIFO)┐ ┌─────────────── head ┐ │ task C(新 fork,细粒度,优先自己做) │ │ task F │ │ task B │ │ task E │ │ task A(最早 fork,粗粒度) │ │ task D │ └─────────────── base(被别人窃取,FIFO)──────┘ └─────────────── base ┘ ▲ │ └──────── Worker-2 空闲时从 base 端窃取 task A ──┘ ``` 关键点:工作窃取让"负载不均"得到自平衡——忙的线程专注自己做,闲的线程主动帮忙。代价是偷取任务时要跨线程访问对方队列(会有一定同步与缓存一致性开销),所以窃取频率不能太高,这也是为什么"阈值别设太小"很重要。不适用场景:如果任务粒度过细(比如每个子任务只算几个元素),偷取与调度的管理开销会远超并行计算本身的收益。 ## 三、线程池与并行流 ### Q:ForkJoinPool 的并行度怎么配?commonPool 有什么坑? A:结论先行——`ForkJoinPool` 的并行度(parallelism)默认等于可用 CPU 核数,可用 `new ForkJoinPool(n)` 显式指定;`ForkJoinPool.commonPool()` 是全局共享的公共池,它的并行度通常是"核数 − 1",并且被所有并行流、`CompletableFuture` 默认共用,容易互相干扰。 为什么: - `ForkJoinPool(int parallelism)` 的并行度决定大致能并行的工作线程数,默认 `Runtime.getRuntime().availableProcessors()`。 - `commonPool()` 是一个 JVM 级单例,默认并行度 = `availableProcessors() - 1`(当核数大于 1 时;单核时为 1),设计上是为了给调用方线程本身也留一份计算能力的余地。它是一个懒初始化、由守护线程支撑的池,具体空闲回收行为需结合版本确认。 - 因为 `commonPool` 被"所有"没显式指定池的 `parallelStream()` 与 `CompletableFuture` 共用,一旦你在里面跑了阻塞任务(IO、等锁),就可能把公共池占满,拖慢 JVM 里其他也在用公共池的代码——这就是最常见的坑。 证据/示例(自定义池 vs 公共池;并行度调整): ```java import java.util.concurrent.ForkJoinPool; // 显式指定并行度(推荐:隔离业务,避免污染全局 commonPool) ForkJoinPool pool = new ForkJoinPool(8); long sum = pool.invoke(new SumTask(data, 0, data.length)); // 全局公共池:默认并行度约为 核数 - 1 ForkJoinPool common = ForkJoinPool.commonPool(); System.out.println(common.getParallelism()); pool.shutdown(); // 不再使用自定义池时关闭 ``` 还可以通过系统属性调整公共池并行度(启动参数): ```bash -Djava.util.concurrent.ForkJoinPool.common.parallelism=8 ``` 关键点:生产上"用自定义池隔离"是更稳的做法——业务计算走自己的 `ForkJoinPool`,不跟公共池抢资源;对阻塞型任务,更要避免丢进公共池。不适用场景:单次、轻量的并行任务,临时建一个池再销毁反而增加开销,此时用公共池也无可厚非,前提是别在里面做阻塞操作。 ### Q:万一在 Fork/Join 任务里确实遇到阻塞操作,怎么办? A:结论先行——不要在工作线程里直接阻塞;如果实在避不开,用 `ForkJoinPool.ManagedBlocker` 告诉池"我马上要阻塞",池会临时补偿一个工作线程,尽量避免并行度被阻塞任务"吃掉"。 为什么:Fork/Join 的工作线程数约等于并行度,工作窃取成立的前提是"有线程空闲、能来偷"。一旦某个工作线程被 IO 或锁阻塞,它就不再参与计算,可被偷的"空闲线程"也变少了,窃取机制救不了它。`ManagedBlocker` 提供的正是补偿机制:你实现两个方法 `isReleasable()`(现在是否已可返回)与 `block()`(真正执行阻塞),再用 `ForkJoinPool.managedBlock(blocker)` 包裹这段逻辑;池在必要时会创建/激活额外的补偿线程,让并行度尽量维持在目标水平。 证据/示例(用 ManagedBlocker 包装一次阻塞调用): ```java import java.util.concurrent.ForkJoinPool; public class BlockingWork { static class IoBlocker implements ForkJoinPool.ManagedBlocker { private boolean done = false; @Override public boolean isReleasable() { return done; } // 是否已无需再阻塞 @Override public boolean block() { doBlockingIo(); // 真正会阻塞的调用 done = true; return true; } } static void doBlockingIo() { // 例如一次远程调用 / 文件读取 } public static void main(String[] args) throws InterruptedException { ForkJoinPool.managedBlock(new IoBlocker()); } } ``` 关键点:`ManagedBlocker` 是"应急阀",不是"可以放心在 Fork/Join 里做 IO"的许可——补偿线程有数量上限,创建与调度也有代价。真正的 IO 密集任务仍应交给普通线程池(或按 JDK 版本选用虚拟线程等更合适的方案)。不适用场景:纯 CPU 计算没有阻塞,用不上它。 ### Q:并行流(parallelStream)和 ForkJoinPool 是什么关系? A:结论先行——`parallelStream()` 的底层默认就是用 `commonPool` 执行,它本质上是"把 Fork/Join 的拆任务/合并结果封装好"的语法糖;如果你想让某段并行流用自定义池,需要把它提交到自己的 `ForkJoinPool` 里执行。 为什么:并行流通过 Spliterator(可分割迭代器)把数据源切分成若干块,再用 Fork/Join 的框架并行处理、最后合并。因为默认用的是公共池,它天然继承了公共池的两个特性:并行度≈核数−1、全局共享。用于纯内存计算时很香,一旦在流里做了阻塞 IO,就会拖累整个公共池。 证据/示例(让并行流跑在自定义池里): ```java import java.util.concurrent.ForkJoinPool; import java.util.stream.IntStream; ForkJoinPool pool = new ForkJoinPool(8); try { long sum = pool.submit(() -> IntStream.range(0, 10_000_000) .parallel() .mapToLong(i -> i) // 纯计算,别在这里做 IO .sum() ).get(); System.out.println(sum); } finally { pool.shutdown(); } ``` 关键点:把并行流放进自定义池,靠的是"流在哪个线程上执行、就归属哪个线程所在的池"这一机制,所以要用 `pool.submit(...)` 包裹。预期行为是这段流的并行度受自定义池约束,不再占用公共池。不适用场景:数据量很小、或者流里带阻塞 IO、或者各元素处理耗时差异极大(`parallelStream` 的分块是自动的,你很难像手写 Fork/Join 那样控制粒度与拆分策略),这些情况下手工用 Fork/Join 反而更可控。 ## 四、适用与不适用 ### Q:哪些场景明确不适合 Fork/Join? A:结论先行——IO 密集、拆分粒度不均、以及存在共享可变状态的场景都不适合,强行套用会得到错误的并行度或错误的结果。 逐个说明: 1. **IO 密集 / 阻塞操作**:Fork/Join 的工作线程数等于并行度,一旦线程被 IO 阻塞,就没有线程去做别的任务,工作窃取也救不了(没有空闲线程可偷)。网络、数据库、磁盘 IO 应交给普通线程池。 2. **拆分粒度不均**:如果一个子任务比另一个大几个数量级,工作窃取虽然能缓解,但整体仍会被最慢的那条分支拖住(木桶效应)。分治要尽量拆得均衡。 3. **存在共享可变状态**:多个子任务同时写同一个变量/集合,会引入数据竞争。要么用不可变/局部结果最后合并,要么加锁——而加锁基本抵消了并行收益。 4. **任务本身不可拆或太小**:比如单条记录的处理、几十个元素的计算,拆出来的调度开销比计算还大。 5. **需要严格顺序**:有依赖关系的任务不能简单并行。 证据/示例(可以记为一句判据): ```text 能用 Fork/Join 的题眼: 可递归拆分 + 子任务独立 + 以 CPU 计算为主 + 有合理阈值 不能用的信号: 等网络/等数据库/等锁 + 共享可变状态 + 粒度悬殊 + 任务太小 ``` 关键点:别把 Fork/Join 当"万能加速器"。它的收益是拿"并行计算"换"调度与合并开销",只有计算量够大、拆得够均匀时才划算。是否划算必须实测,别凭直觉下结论。 ### Q:一个可运行的大数组求和示例应该怎么拆? A:结论先行——按数组区间二分,切到长度不超过阈值就串行累加,否则"fork 左半、当前线程算右半、join 左半",顶层用 `ForkJoinPool.invoke` 触发,这就是最标准的可运行范式。 为什么:数组是最容易分治的数据结构——区间拆分天然均衡、没有共享可变状态(各段只读自己的部分、各自累加局部结果)、阈值可调。求和又天然可合并(各部分和相加即总和),因此它是演示 Fork/Join 的最佳样本。 完整可运行示例: ```java import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveTask; import java.util.concurrent.ThreadLocalRandom; public class BigArraySum { // 任务计算 [lo, hi) 区间的和 static class SumTask extends RecursiveTask<Long> { private static final int THRESHOLD = 10_000; // 阈值:小于等于它就不再拆,直接串行算 private final int[] array; private final int lo, hi; SumTask(int[] array, int lo, int hi) { this.array = array; this.lo = lo; this.hi = hi; } @Override protected Long compute() { // 1. 足够小:串行求和,避免为极小块再付调度开销 if (hi - lo <= THRESHOLD) { long sum = 0L; for (int i = lo; i < hi; i++) { sum += array[i]; } return sum; } // 2. 还能拆:一分为二 int mid = lo + (hi - lo) / 2; SumTask left = new SumTask(array, lo, mid); SumTask right = new SumTask(array, mid, hi); // 3. fork 左半,当前线程就地算右半,最后合并 left.fork(); long rightResult = right.compute(); long leftResult = left.join(); return leftResult + rightResult; } } public static void main(String[] args) { int n = 32_000_000; int[] data = new int[n]; ThreadLocalRandom rnd = ThreadLocalRandom.current(); for (int i = 0; i < n; i++) { data[i] = rnd.nextInt(100); } // 用串行方式算一遍作为对照 long expected = 0L; for (int v : data) { expected += v; } // 用 ForkJoinPool 并行计算 ForkJoinPool pool = new ForkJoinPool(); // 默认并行度 = 可用核数 try { long actual = pool.invoke(new SumTask(data, 0, data.length)); System.out.println("expected = " + expected); System.out.println("actual = " + actual); System.out.println("match = " + (expected == actual)); } finally { pool.shutdown(); } } } ``` 关键点: - **阈值 THRESHOLD 是核心调参**。太小 → 任务数爆炸、调度开销大;太大 → 并行度不足、有线程闲着。要结合数据规模与机器实测来定,不存在放之四海皆准的值。 - **`mid = lo + (hi - lo) / 2`** 而不是 `(lo + hi) / 2`,避免 int 溢出(虽然数组长度通常不会到溢出量级,但这是更稳的写法)。 - **提前算一遍串行结果做对照**,是验证并行正确性的常用手段;生产里则用单元测试锁定结果。 - **`pool.shutdown()`** 放在 `finally`,自定义池用完要关,避免线程泄漏。 预期行为:`match` 为 `true`,两条路径结果一致。适用场景:大数组/大集合的求和、最值、计数等"可结合(associative)"的归约运算。不适用场景:元素处理带副作用或 IO;要素之间强依赖(如必须严格按顺序);数组很小(此时串行更快)。 补充:归并排序也是 Fork/Join 的经典课题——思路是"左右两半各自 fork 排序,join 后做一次归并",和求和的结构完全一样,区别只在"合并"这一步是 merge 而不是相加。把它当作练习,能帮你巩固"拆分—并行—合并"这套骨架。 ### Q:用同一套骨架写并行归并排序,关键差异在哪? A:结论先行——拆分逻辑与求和完全一致,唯一区别是"合并"从"相加"变成"把两个有序子数组归并成一个有序数组";同时因为排序是原地操作、没有返回值,应该用 `RecursiveAction` 而不是 `RecursiveTask`。 为什么:求和是"可结合(associative)"的归约,子结果合并就是相加;归并排序的合并更复杂——合并前左右两半必须各自有序,所以子任务返回的不是一个标量,而是"把 `[lo, mid)` 与 `[mid, hi)` 两段区间就地排好序"这一副作用。既然结果体现在数组本身,就用 `RecursiveAction`。 证据/示例(可运行的骨架): ```java import java.util.Arrays; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveAction; public class ParallelMergeSort extends RecursiveAction { private static final int THRESHOLD = 4096; private final int[] a; private final int[] tmp; // 全程复用,避免各任务重复分配 private final int lo, hi; ParallelMergeSort(int[] a, int[] tmp, int lo, int hi) { this.a = a; this.tmp = tmp; this.lo = lo; this.hi = hi; } @Override protected void compute() { if (hi - lo <= THRESHOLD) { Arrays.sort(a, lo, hi); // 小块直接串行排序 return; } int mid = lo + (hi - lo) / 2; ParallelMergeSort left = new ParallelMergeSort(a, tmp, lo, mid); ParallelMergeSort right = new ParallelMergeSort(a, tmp, mid, hi); left.fork(); // fork 左半 right.compute(); // 当前线程算右半 left.join(); // 等左半 merge(lo, mid, hi); // 两半都有序后归并 } private void merge(int lo, int mid, int hi) { System.arraycopy(a, lo, tmp, lo, hi - lo); // 先拷到临时数组再归并 int i = lo, j = mid, k = lo; while (i < mid && j < hi) { a[k++] = (tmp[i] <= tmp[j]) ? tmp[i++] : tmp[j++]; } while (i < mid) a[k++] = tmp[i++]; while (j < hi) a[k++] = tmp[j++]; } public static void main(String[] args) { int[] data = { /* 待排序数据 */ }; ForkJoinPool pool = new ForkJoinPool(); try { int[] work = data.clone(); pool.invoke(new ParallelMergeSort(work, new int[work.length], 0, work.length)); System.out.println(Arrays.toString(work)); } finally { pool.shutdown(); } } } ``` 关键点:所有子任务共享同一个 `tmp` 数组,但每个子任务只在自己负责的 `[lo, hi)` 区间内读写,区间互不重叠,因此**无需加锁**——这正是"子任务独立"的体现。反过来说,若每个任务都各自 `new int[hi - lo]`,会产生海量临时数组与 GC 压力,得不偿失。不适用场景:小数组没必要并行;`Arrays.sort` 对小块已经高度优化,让它处理叶子区间通常比自己写插入排序更省心。 ## 五、生产用法与踩坑 ### Q:生产中使用 Fork/Join 还有哪些坑? A:结论先行——阈值与并行度必须实测调优;不要在任务里阻塞或做 IO;慎用公共池;注意任务返回对象的体积;以及 join 不可中断、异常处理要到位。 逐条说明: 1. **阈值要跑出来**。同一份代码在不同数据规模、不同核数的机器上最优阈值不同,别照抄网上数字。用 JMH 等工具做基准更靠谱。 2. **任务内不要阻塞**。`join` 之外不要加 `sleep`、IO、远程调用;一旦工作线程被阻塞,并行度就"缩水"了。 3. **隔离公共池**。有阻塞风险或想控制资源时,用独立 `ForkJoinPool`,不要默认吃 `commonPool`。 4. **控制返回对象大小**。`RecursiveTask` 每次合并都要创建中间结果,如果返回的是大对象/大数组,内存与复制开销会很大;能原地写就地写。 5. **`join()` 不可中断,异常会包装**。`ForkJoinTask` 里抛出的异常在 `join()` 时可能以 `RuntimeException`/`Error` 形式重新抛出,Checked 异常则包装为 `RuntimeException`;需要捕获处理,别让异常被悄悄吞掉。 6. **递归深度与任务数量**。拆得过深会产生大量小任务,栈深与内存压力都要留意。 7. **线程数与核数**。并行度默认是核数,如果你是"核数 × 多实例部署",要意识到同一台机器上多个进程会争抢 CPU,别把并行度当成独立资源。 ### Q:并行任务嵌套会不会有问题?ForkJoinTask 和 Future 有什么不同? A:结论先行——不要在 `ForkJoinTask` 或并行流里再嵌套使用并行流,否则任务在同一池内层层派生、互相等待,行为难以预测;`ForkJoinTask` 虽然也支持 `Future` 风格的 `get()`,但它的设计重心是"在池内 fork/join",不是通用的异步结果占位符。 为什么:Fork/Join 的任务都在同一个池里被调度,嵌套并行意味着父任务 fork 出的子任务又 fork 更多任务,任务数量可能急剧膨胀;若这些任务之间还存在 join 依赖,公共池里可用工作线程可能被"占着等"的任务吃满,尤其在公共池被多个业务共用时更容易互相干扰。 ```text 反例(不推荐): 并行流 A 处理每个元素时,又调用一个 parallelStream B → 任务在同一池里层层派生、互相等待 → 与预期行为不一致,性能可能不升反降 ``` `ForkJoinTask` 与 `Future` 的差异可以简单对照: | 维度 | Future / ThreadPoolExecutor | ForkJoinTask / ForkJoinPool | | --- | --- | --- | | 主要用途 | 外部提交独立任务、取结果 | 任务内部递归派生子任务 | | 任务内派生 | 不擅长(父任务占线程等子任务) | 原生支持 fork/join | | 排队结构 | 共享队列 | 每线程本地队列 + 工作窃取 | | 结果获取 | `get()`(可超时、可中断) | `join()`(不可中断) | | 合适场景 | IO、独立短任务 | CPU 密集、可拆分的分治计算 | 关键点:把并行度控制在"单层、边界明确"是最稳的用法;确实需要多层并行时,用自定义池做隔离,或改用更清晰的异步编排(例如 `CompletableFuture` 配合显式线程池)。不适用场景:顺理成章的嵌套虽然不一定出错,但依然难以预测,能避免就避免。 ## 小结 - Fork/Join 适合"可递归拆分、子任务独立、以 CPU 计算为主、有合理阈值"的分治任务。 - `RecursiveTask<V>` 有返回值、`RecursiveAction` 无返回值;`fork()` 异步提交、`join()` 阻塞取结果、`invokeAll()` 批量提交并等待。 - 优化要点:只 fork 一个子任务,当前线程就地计算另一个,最后 join,避免 fork 两个后一起空等。 - 工作窃取靠"每个 worker 一个双端队列,自己从头部 LIFO 取、别人从尾部 FIFO 偷"来平衡负载、减少争用。 - `ForkJoinPool` 并行度默认等于核数;`commonPool` 全局共享、并行度约为核数−1,被并行流和 `CompletableFuture` 默认共用,别在里面跑阻塞任务。 - `parallelStream()` 底层走 `commonPool`,要换池就用 `pool.submit(() -> stream.parallel()...)` 包裹。 - 不适用:IO 密集、粒度不均、共享可变状态、任务过小或强顺序依赖。 - 阈值、并行度、池隔离这三件事都要结合硬件与实测,不能一概而论。 ## 思考题 1. 为什么"fork 两个再 join 两个"不如"fork 一个、当前线程算另一个"? 2. 工作窃取为什么要"自己从头部取、别人从尾部偷"?如果都从头部取会有什么问题? 3. `commonPool` 并行度为什么常常是"核数 − 1"而不是核数? 4. 如果把一段并行流改成手工 Fork/Join,你能获得哪些并行流给不了的控制力? 5. 你的一个"并行"任务变快了没有,你怎么用数据和实验来证明,而不是靠感觉?
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入