ForkJoinPool 探索

Posted on

介绍

“分而治之“是理清思路和解决问题的一个重要的方法。大到系统架构对功能模块的拆分，小到归并排序的实现，无一不在散发着分而治之的思想。在实现分而治之的算法的时候，我们通常使用递归的方法。递归相当于把大的任务拆成多个小的任务，然后大任务等待多个小的子任务执行完成后，合并子任务的结果。一般来说，父任务依赖与子任务的执行结果，子任务与子任务之间没有依赖关系。因此子任务之间可以并发执行来提升性能。于是ForkJoinPool提供了一个并发处理“分而治之”的框架，让我们能以类似于递归的编程方式获得并发执行的能力。

使用

分而治之代码典型的形式如下：

1
2
3
4
5
6
7
8
9
10
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
    }
}

计算斐波那契数：

1
2
3
4
5
6
7
8
9
10
11
12
Class Fibonacci extends RecursiveTask<Integer> {
   final int n;
   Fibonacci(int n) { this.n = n; }
   Integer compute() {
     if (n <= 1)
       return n;
     Fibonacci f1 = new Fibonacci(n - 1);
     f1.fork();
     Fibonacci f2 = new Fibonacci(n - 2);
     return f2.compute() + f1.join();
   }
}

原理

ForkJoinPool的核心在于其轻量级的调度机制，采用了Cilk的work-stealing的基本调度策略：

  • 每个工作线程维持一个任务队列
  • 任务队列以双端队列的形式维护，不仅支持先进后出的push和pop操作，还支持先进先出的take操作
  • 由父任务fork出来的子任务被push到运行该父任务的工作线程对应的任务队列中
  • 工作线程以先进后出的方式处理pop自己任务队列中的任务（优先处理最年轻的任务）
  • 当任务队列中没有任务时，工作线程尝试随机从其他任务队列中窃取任务
  • 当工作线程没有任务可以执行，且窃取不到任务时，它会“退出”（yiled、sleep、优先级调整），经过一段时间后再次尝试。除非其他所有的线程也都没有任务可以执行，这种情况下它们会一直阻塞直到有新的任务从上层添加进来

一个简单的实现：

参考资料：

  • A Java Fork/Join Framework