This article refers to your Batman, the author of CSDN Usage and principle of ForkJoinPool thread pool He Zhihu author Readily Articles Use and precautions of Fork/Join framework with high concurrency.

• ForkJoinPool is mainly used to implement the divide and conquer algorithm, especially the recursive functions called after divide and conquer, such as quick sort.
• ForkJoinPool is most suitable for computing intensive tasks. If I/O, inter thread synchronization, sleep() and other situations will cause thread blocking for a long time, it is best to use ManagedBlocker together.

1. Examples

Calculate the cumulative sum from 1 to 100000:

package ecnu.cn;

import java.util.concurrent.*;

public class SumTask extends RecursiveTask<Long> {
    private int start, end;

    public static void main(String[] args) {
        SumTask sumTask = new SumTask(1, 100000);
        ForkJoinPool pool = new ForkJoinPool();
        Future<Long> result = pool.submit(sumTask);
        try {
            System.out.println(result.get());;
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public SumTask(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        Long sum = 0L;
        if (end - start < 10) {
            for (int i = start; i <= end; i++) {
                sum += i;
            }
        } else {
            int middle = (start + end) / 2;
            SumTask taskLeft = new SumTask(start, middle);
            SumTask taskRight = new SumTask(middle + 1, end);
            // Execute subtasks
            taskLeft.fork();
            taskRight.fork();
            // Wait for the end of task execution
            Long leftResult = taskLeft.join();
            Long rightResult = taskRight.join();
            sum = leftResult + rightResult;
        }
        return sum;
    }
}

2. fork and join, submit and invoke, recursive task and recursive action

(1) When each thread executes

• fork(): start a new thread (or reuse the idle thread in the thread pool) and hand over the task to the thread for processing.
• join(): wait for the processing thread of the task to finish processing and obtain the return value.

You can also add

taskLeft.fork();
taskRight.fork();

Replace with:

invokeAll(leftTask, rightTask);

The difference between the two is that for the Fork/Join mode, if the number of threads in the Pool is fixed, calling the fork method of the subtask is equivalent to a dividing the work to B first, and then when a doesn't work as a supervisor, B completes the task assigned by A. So the above pattern is equivalent to wasting a thread. Then, if invokeAll is used, it is equivalent to that after a divides the work to B, both a and B complete the work. This can make better use of the thread Pool and shorten the execution time. So it is better to use invokeAll.

(2) When forkjoinpool is submitted

• submit(): execute asynchronously. It will be blocked only when Future calls get.
• invoke(): synchronous execution. After calling, you need to wait for the task to complete before executing the following code.

(3) Class on inheritance

• Recursive task: applicable to the case with return value.
• RecursiveAction: applicable to the case of no return value.

3. Principle

When creating a thread, each fork() does not always generate a new thread, and each join() does not necessarily cause thread blocking. Instead, a more complex algorithm, work stealing, is adopted. Its process is as follows:

• Each work thread of ForkJoinPool maintains a work queue, which is a Deque. The object stored in it is ForkJoinTask.
• When each worker thread generates a new task during operation (usually because fork() is called), it will be placed at the end of the work queue, and the worker thread uses LIFO mode when processing its own work queue, that is, it takes out the task from the end of the queue every time.
• While processing its own work queue, each worker thread will try to steal a task (either from the task just submitted to the pool or from the work queue of other worker threads). The stolen task is located at the head of the work queue of other threads, that is to say, when the worker thread steals the tasks of other worker threads, it uses FIFO mode.
• When a join() is encountered, if the task to be joined has not been completed, it will process other tasks first and wait for them to complete.
• When there are neither their own tasks nor tasks that can be stolen, they enter sleep.