ForkJoin Framework

ForkJoin framework, problems or tasks are recursively broken down into sub-tasks. Tasks are solved with the help of worker threads provided by a thread pool. Each worker thread will have sub-tasks it's responsible for. These are stored in double-ended queues (deques). When a worker thread's deque is empty, it means that all the sub-tasks have been popped off and completed.

Divide and Conquer Approach:

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
    }
}

The heart of a fork/join framework lies in its lightweight scheduling mechanics. It's Work Stealing:

  • Work stealing was introduced in Java with the aim of reducing contention in multi-threaded applications.
  • The key concept in the ForkJoinPool is the "work-stealing" algorithm. Each thread in the pool has its own deque (double-ended queue) to which tasks are added. When a thread finishes its tasks, it can "steal" tasks from the deque of another idle thread, allowing for efficient workload distribution and load balancing. This feature makes ForkJoinPool particularly suitable for scenarios where some subtasks may take longer than others, as it helps ensure that idle threads are always kept busy.
  • Baeldung - Guide to Work Stealing in Java
  • DZone - Diving Into Java 8's newWorkStealingPools

Create Work Stealing Thread Pool:

Execute ForkJoinTasks in a ForkJoinPool:

  • Understanding Java Fork-Join Framework with Examples
  • <T> T invoke(ForkJoinTask<T> task): executes the specified task and returns its result upon completion. This call is synchronous, meaning that the calling thread waits until this method returns. For a resultless task (RecursiveAction), the type parameter Tis Void.
  • void execute(ForkJoinTask<?> task): executes the specified task asynchronously - the calling code doesn’t wait for the task’s completion - it continues to run.

Alternatively, you can execute a ForkJoinTask by calling its own methods fork() or invoke(). In this case, the common pool will be used automatically, if the task is not already running within a ForkJoinPool. A noteworthy point: ForkJoinPool uses daemon threads that are terminated when all user threads are terminated. That means you don’t have to explicitly shutdown a ForkJoinPool (though it is possible). In the case of common pool, calling shutdown() has no effect because the pool is always available for use.

Threads in ForkJoinPool are daemon. You don’t have to explicitly shutdown the pool.

RecursiveAction and RecursiveTask:

References