[JUC series] overview of fork/join framework

JUC series Fork/Join frame

Fork/Join The frame is Java A tool in the concurrency toolkit that can split a large task into many small tasks for asynchronous execution , since JDK1.7 introduce .

Fork/Join Overview class diagram

The main module

ForkJoinPool You can use the ForkJoinWorkerThread To deal with it ForkJoinTask Mission .

ForkJoinPool Only receive ForkJoinTask Mission ( In practical use , You can also receive Runnable/Callable Mission , But at real run time , These tasks will also be encapsulated into ForkJoinTask Type of task ),RecursiveTask yes ForkJoinTask Subclasses of , Is a recursive execution ForkJoinTask,RecursiveAction Is a non return value RecursiveTask,CountedCompleter After the task is completed, a custom hook function will be executed .

In practice , We usually inherit RecursiveTask 、RecursiveAction or CountedCompleter To meet our business needs , Not directly ForkJoinTask class .

Core class

Task object ：

ForkJoinTask

Thread pool for task management

ForkJoinPool

The thread that performs the task

ForkJoinWorkerThread

The core algorithm ： Divide and conquer algorithm

The core algorithm ： Job theft

work-stealing( Job theft ) Algorithm : All worker threads in the thread pool try to find and execute the submitted task , Or subtasks created by other active tasks ( If not, block and wait ). This characteristic makes ForkJoinPool When running multiple tasks that can produce subtasks , Or it is more efficient to submit many small tasks . Especially when building asynchronous models ForkJoinPool when , No need to merge (join) The event type task of is also very applicable .

stay ForkJoinPool in , Each worker thread in the thread pool (ForkJoinWorkerThread) All correspond to a task queue (WorkQueue), The worker thread prioritizes tasks from its own queue (LIFO or FIFO The order , Parameters mode decision ), And then to FIFO Randomly steal tasks from other queues in the order of .

Examples of use

RecursiveAction Use

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class SortTask extends RecursiveAction {
    
    final long[] array;
    final int low;
    final int high;
    private int THRESHOLD = 0;

    public SortTask(long[] array) {
    
        this.array = array;
        this.low = 0;
        this.high = array.length - 1;
    }

    public SortTask(long[] array, int low, int high) {
    
        this.array = array;
        this.low = low;
        this.high = high;
    }

    @Override
    protected void compute() {
    
        System.out.println("[" + new SimpleDateFormat("HH:mm:ss.SSS").format(new Date()) + "--" + Thread.currentThread().getName() + "] task is [low=" + low + ", high=" + high + "].");

        if (low < high) {
    
            int pivot = partition(array, low, high);
            SortTask left = new SortTask(array, low, pivot - 1);
            SortTask right = new SortTask(array, pivot + 1, high);
            left.fork();
            right.fork();
            left.join();
            right.join();
        }
    }

    private int partition(long[] array, int low, int high) {
    
        long x = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
    
            if (array[j] <= x) {
    
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }

    private void swap(long[] array, int i, int j) {
    
        if (i != j) {
    
            long temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    public static void main(String[] args) throws Exception {
    
        long[] array = {
    10, 0, 21, 44, 52, 30};
        SortTask sort = new SortTask(array);
        ForkJoinPool pool = new ForkJoinPool();
        pool.submit(sort);
        boolean flag = true;
        while (flag) {
    
            if (sort.isDone()) {
    
                StringBuilder a = new StringBuilder();
                for (int i = 0; i < sort.array.length; i++) {
    
                    a.append(sort.array[i]).append(" ");
                }
                System.out.println("[" + new SimpleDateFormat("HH:mm:ss.SSS").format(new Date()) + "--" + Thread.currentThread().getName() + "] a is [" + a.substring(0, a.length() - 1) + "].");
                flag = false;
            }
        }
        pool.shutdown();
    }
}

Execution results

[18:06:06.143--ForkJoinPool-1-worker-1] task is [low=0, high=5].
[18:06:06.143--ForkJoinPool-1-worker-2] task is [low=0, high=2].
[18:06:06.143--ForkJoinPool-1-worker-2] task is [low=0, high=1].
[18:06:06.143--ForkJoinPool-1-worker-2] task is [low=0, high=-1].
[18:06:06.143--ForkJoinPool-1-worker-2] task is [low=1, high=1].
[18:06:06.143--ForkJoinPool-1-worker-2] task is [low=3, high=2].
[18:06:06.159--ForkJoinPool-1-worker-2] task is [low=4, high=5].
[18:06:06.159--ForkJoinPool-1-worker-2] task is [low=4, high=3].
[18:06:06.159--ForkJoinPool-1-worker-2] task is [low=5, high=5].
[18:06:06.159--main] a is [0 10 21 30 44 52].

RecursiveTask Use

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveTask;

public class SumTask extends RecursiveTask<Long> {
    
    private static final int THRESHOLD = 10;

    private long start;

    private long end;

    public SumTask(long end) {
    
        this(0, end);
    }

    private SumTask(long start, long end) {
    
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
    
        long sum = 0;
        if ((end - start) <= THRESHOLD) {
    
            System.out.println("[" + new SimpleDateFormat("HH:mm:ss.SSS").format(new Date()) + "--" + Thread.currentThread().getName() + "] task is [" + start + "," + end + "].");

            for (long l = start; l <= end; l++) {
    
                sum += l;
            }
        } else {
    
            long mid = (start + end) >>> 1;
            SumTask left = new SumTask(start, mid);
            SumTask right = new SumTask(mid + 1, end);
            left.fork();
            right.fork();
            sum = left.join() + right.join();
        }
        return sum;
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {
    
        SumTask sumTask = new SumTask(100);
        ForkJoinPool pool = new ForkJoinPool();
        Future<Long> future = pool.submit(sumTask);
        boolean flag = true;
        while (flag) {
    
            if (future.isDone()) {
    
                System.out.println("[" + new SimpleDateFormat("HH:mm:ss.SSS").format(new Date()) + "--" + Thread.currentThread().getName() + "] sum = [" + future.get() + "].");
                flag = false;
            }
        }
        pool.shutdown();
    }
}

Execution results

[18:09:09.123--ForkJoinPool-1-worker-2] task is [26,32].
[18:09:09.123--ForkJoinPool-1-worker-0] task is [39,44].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [51,57].
[18:09:09.123--ForkJoinPool-1-worker-2] task is [33,38].
[18:09:09.123--ForkJoinPool-1-worker-1] task is [0,6].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [58,63].
[18:09:09.123--ForkJoinPool-1-worker-0] task is [45,50].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [64,69].
[18:09:09.123--ForkJoinPool-1-worker-0] task is [76,82].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [70,75].
[18:09:09.123--ForkJoinPool-1-worker-0] task is [83,88].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [89,94].
[18:09:09.123--ForkJoinPool-1-worker-0] task is [95,100].
[18:09:09.123--ForkJoinPool-1-worker-3] task is [13,19].
[18:09:09.123--ForkJoinPool-1-worker-2] task is [20,25].
[18:09:09.123--ForkJoinPool-1-worker-2] task is [7,12].
[18:09:09.123--main] sum = [5050].

---

Reference link ：https://www.pdai.tech/md/java/thread/java-thread-x-juc-executor-ForkJoinPool.html