工作窃取算法(work-stealing algorithm)是一种用于提升多线程并行处理效率的任务调度机制,其核心在于允许空闲线程从繁忙线程的任务队列中“偷取”任务来执行。在 java 中,该算法主要由 forkjoinpool 实现,旨在解决传统线程池中因任务分配不均导致的负载失衡问题。通过为每个工作线程维护一个双端队列(deque),忙碌的线程优先处理自己队列头部的任务,而空闲线程则从其他线程队列的尾部窃取任务,从而最大化 cpu 利用率。

工作窃取算法如何避免线程间锁竞争?
工作窃取算法通过为每个工作线程分配独立的 ArrayDeque 双端队列来减少锁竞争。这种设计使得线程在处理自己提交的任务时,只需操作队列头部,而在窃取任务时,则从其他线程队列的尾部进行操作。由于大多数情况下线程只访问自己的队列头部,且窃取操作发生在队列尾部,这种“头进尾出”与“尾进头出”的模式显著降低了多线程对同一队列的并发访问冲突,从而提高了吞吐量。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class WorkStealingDemo {
public static void main(String[] args) {
// 创建 ForkJoinPool,默认使用 Runtime.getRuntime().availableProcessors() 作为并行度
ForkJoinPool pool = new ForkJoinPool();
// 提交一个递归任务
MyTask task = new MyTask(100);
Integer result = pool.invoke(task);
System.out.println("计算结果: " + result);
pool.shutdown();
}
// 定义一个递归任务
static class MyTask extends RecursiveTask<Integer> {
private final int threshold = 10; // 任务拆分阈值
private final int n;
public MyTask(int n) {
this.n = n;
}
@Override
protected Integer compute() {
if (n <= threshold) {
// 当任务足够小时,直接计算
return simulateComputation(n);
} else {
// 将任务拆分为两个子任务
int mid = n / 2;
MyTask left = new MyTask(mid);
MyTask right = new MyTask(n - mid);
// 并行执行子任务
left.fork(); // 将左任务压入当前线程的 Deque 头部
right.compute(); // 右任务在当前线程直接执行
// 合并结果:如果左任务尚未完成,当前线程可能会去窃取其他任务
return left.join() + right.compute();
}
}
private int simulateComputation(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i;
}
return sum;
}
}
}
在上述代码中,fork() 方法将子任务推送到当前工作线程的双端队列头部,而 compute() 则直接在当前线程执行。当调用 join() 等待左任务结果时,如果左任务尚未完成,当前线程可以检查自己的队列是否为空。如果为空,它会尝试从其他繁忙线程的队列尾部窃取任务,从而避免空闲等待,提高整体执行效率。
使用Atmosphere构建通过WebSocket、SSE、gRPC、WebTransport、MCP、A2A和AG-UI流传输的JVM代理网关,并带有治理钩子。
立即学习“Java免费学习笔记(深入)”;
工作窃取算法在什么场景下表现最佳?
工作窃取算法在处理可递归分解的计算密集型任务时表现最佳,例如矩阵运算、大规模数据排序或树形结构遍历。这类任务的特点是能够被拆分为多个独立且规模较小的子任务,且子任务之间依赖关系较弱。当任务粒度适中(既不太大也不太小)时,工作窃取算法能充分发挥其优势。如果任务过小,频繁的任务创建和窃取开销可能抵消并行带来的收益;如果任务过大,可能导致负载不均,部分线程长时间忙碌而其他线程空闲。
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class TaskSizingDemo {
public static void main(String[] args) {
ForkJoinPool pool = new ForkJoinPool();
// 模拟一个大任务,拆分为多个小任务
LargeTask task = new LargeTask(1000000); // 任务规模较大
pool.invoke(task);
pool.shutdown();
}
static class LargeTask extends RecursiveAction {
private final int size;
private static final int THRESHOLD = 10000; // 调整阈值以优化性能
public LargeTask(int size) {
this.size = size;
}
@Override
protected void compute() {
if (size <= THRESHOLD) {
// 直接处理小规模任务
process(size);
} else {
// 拆分为两个子任务
int mid = size / 2;
LargeTask left = new LargeTask(mid);
LargeTask right = new LargeTask(size - mid);
// 并行执行
left.fork();
right.compute();
left.join();
}
}
private void process(int size) {
// 模拟实际计算逻辑
long sum = 0;
for (int i = 0; i < size; i++) {
sum += i;
}
}
}
}
在实际应用中,开发者需要根据具体任务的特性调整 threshold 参数。过小的阈值会导致过多的任务创建和上下文切换开销,而过大的阈值则可能无法充分利用多核 CPU 的并行能力。通过合理设置阈值,可以确保工作窃取算法在不同规模的输入下都能保持高效运行。
当 ForkJoinPool 中的任务出现阻塞时会发生什么?
当 ForkJoinPool 中的某个任务因等待 I/O 操作、锁竞争或其他阻塞原因而无法继续执行时,工作窃取算法可能会导致整个池的性能下降。这是因为阻塞的任务会占用其所属的工作线程,而其他空闲线程虽然可以尝试窃取任务,但如果所有任务都依赖于阻塞任务的结果,窃取操作将无法带来实质性的进展。此外,如果阻塞时间较长,可能导致线程池中的线程全部被阻塞,从而引发死锁或严重的性能瓶颈。因此,在使用 ForkJoinPool 时,应尽量避免在 compute() 方法中进行阻塞操作,或者使用非阻塞的异步处理方式。

















