23.3 The Fork/Join Framework
To harness the benefits of multicore architectures, the Fork/Join Framework in the java.util.concurrent package provides support for parallel programming that allows computations to run in parallel on multiple processors. In this section we provide an introduction to this framework which is also the basis of parallel streams (§16.9, p. 1009), but it is also worth exploring further in its own right.
The Fork/Join Framework is specially suited for problems that can be solved by the divide-and-conquer problem-solving paradigm. This technique is prominent in processing data in large arrays and collections—for example, in designing sorting and searching algorithms. The main step in a divide-and-conquer algorithm is to divide the task repeatedly into subtasks of the same type until the task size is smaller than a given threshold, such that a subtask can be solved directly. A simplified divide-and-conquer algorithm to solve a problem is presented below. When the task can be solved directly, this is called the base case. Otherwise, the algorithm proceeds with dividing the task into subtasks, solving each subtask recursively, and combining the results from each subtask, all the time the idea being that each subtask gets smaller and moves toward the base case. Solving a subtask recursively is referred to as forking, and combing the results of subtasks is referred to as joining, hence the name Fork/Join Framework.
if (taskSize < threshold)
solve task directly // Base case
else {
divide task into subtasks // Divide
solve each subtask recursively // Conquer
combine results from each subtask // Combine
}
Each subtask is solved by invocation of the divide-and-conquer algorithm recursively. The subtasks are candidates for parallel processing. The Fork/Join Framework facilitates both the management of threads and the use of available processors for parallel processing of subtasks.
Abstract classes shown in Table 23.3 can be extended to define tasks. The abstract classes RecursiveAction and RecursiveTask<V> provide the abstract method compute() that defines the computation of the task. This method emulates the divide-and-conquer paradigm.
There are different ways to fork a subtask. One convenient way is to use the overloaded invokeAll() static method of the ForkJoinTask<V> class. This static method initiates the execution of the tasks and awaits their completion, returning any results, if necessary.
The overall execution of tasks is managed by the specialized executor service, Fork-JoinPool, shown in Figure 23.1. It is used analogous to the executors encountered in the Executor Framework. The initial task can be submitted to the fork-join pool by calling the invoke() method that commences the performing of the task.