Java在1.7版本的API中引入了一个fork-join库，它被设计用于使用递归分治算法，如快速排序和归并排序。当使用这个库实现分治算法时，在分治步骤中会划分不同的任务，并为原始问题分配更小的子集。必须设计算法，以便这些单独的任务可以并发执行。在某些时候，分配给任务的问题的大小足够小，可以直接解决，并且不需要创建额外的任务。Java fork-join模型背后的一般递归算法如下:

Task(problem)
    if problem is small enough
        solve the problem directly
    else
        subtask1 = fork(new Task(subset of problem)
        subtask2 = fork(new Task(subset of problem)

        result1 = join(subtask1)
        result2 = join(subtask2)

        return combined results

图4.17图形化地描述了模型

现在，我们通过设计一种分治算法来说明Java的fork-join策略，该算法对整数数组中的所有元素进行求和。在API Java的1.7版本中，引入了一个新的线程池——ForkJoinPool——可以分配继承抽象基类ForkJoinTask的任务(现在我们假设它是SumTask类)。下面创建一个ForkJoin- Pool对象，并通过其invoke()方法提交初始任务:

ForkJoinPool pool = new ForkJoinPool();
// array contains the integers to be summed
int[] array = new int[SIZE];
SumTask task = new SumTask(0, SIZE - 1, array);
int sum = pool.invoke(task);

完成后，invoke()方法会返回数组的和。

SumTask类如图4.18所示-------实现使用fork-join对数组内容进行求和的分治算法。用fork()方法创建新任务，而compute()方法指定每个任务执行的计算。直到它可以直接计算分配给它的子集的总和时，方法compute()将被调用。对join()的调用会阻塞，直到任务完成，然后join()返回compute()中计算的结果。

需要注意的是，4.18中的SumTask继承自RecursiveTask。Java fork-join策略是围绕抽象基类ForkJoinTask组织的，而RecursiveTask和RecursiveAction类扩展了这个类。这两个类之间的根本区别是RecursiveTask返回一个结果(通过compute()中指定的返回值)，而RecursiveAction不会返回一个结果。图4.19中的UML类图说明了这三个类之间的关系。

要考虑的一个重要问题是如何确定问题“足够小”，可以直接解决，不再需要创建额外的任务。在SumTask中，当被求和的元素的数量小于值THRESHOLD时，就会发生这种情况，在图4.18中，我们任意地将值设置为1,000。在实践中，确定一个问题何时可以直接解决需要仔细的定时试验，因为值可以根据实现的不同而变化。

在Java的fork-join模型中，有趣的是对任务的管理，其中库构建一个工作线程池，并平衡可用工作线程之间的任务负载。在某些情况下，有数千个任务，但只有少数线程执行工作(例如，每个CPU一个单独的线程)。此外，ForkJoinPool中的每个线程都维护一个已经fork了的的任务队列，如果一个线程的队列是空的，它可以使用工作窃取算法从另一个线程的队列中窃取任务，从而平衡所有线程之间的任务工作负载。