brief introduction

From jdk1 At the beginning of July 7, Java provided fork / join framework for parallel execution of tasks. Its idea is to divide a large task into several small tasks, and finally summarize the results of each small task to obtain the results of this large task.

This idea is very similar to MapReduce (input -- > split -- > map -- > reduce -- > output)

There are two main steps:

Its model is roughly like this: each thread in the thread pool has its own work queue (PS: This is different from ThreadPoolExecutor. ThreadPoolExecutor is a work queue shared by all threads, and all threads take tasks from this work queue). When the tasks in their own queue are completed, a task execution will be stolen from the work queues of other threads, so as to make full use of resources.

Work stealing

Work stealing algorithm refers to a thread stealing tasks from other queues to execute. The operation flow chart of work stealing is as follows:

So why use a job theft algorithm?

If we need to do a relatively large task, we can divide the task into several independent subtasks. In order to reduce the competition between threads, we put these subtasks into different queues, and create a separate thread for each queue to execute the tasks in the queue. Threads and queues correspond one by one, For example, thread a is responsible for processing tasks in queue a. However, some threads will finish the tasks in their queue first, while there are tasks waiting to be processed in the queue corresponding to other threads. The thread that has finished its work is better to help other threads than wait, so it steals a task from the queue of other threads to execute. At this time, they will access the same queue. Therefore, in order to reduce the competition between the stolen task thread and the stolen task thread, the dual ended queue is usually used. The stolen task thread always takes the task from the head of the dual ended queue for execution, and the stolen task thread always takes the task from the tail of the dual ended queue for execution.

The advantage of work stealing algorithm is to make full use of threads for parallel computing and reduce the competition between threads. Its disadvantage is that there is still competition in some cases, such as when there is only one task in the double ended queue. It also consumes more system resources, such as creating multiple threads and multiple double ended queues.

API introduction

ForkJoinPool

An ExecutorService for running ForkJoinTasks.

A ForkJoinPool differs from other kinds of ExecutorService mainly by virtue of employing work-stealing: all threads in the pool attempt to find and execute tasks submitted to the pool and/or created by other active tasks (eventually blocking waiting for work if none exist). This enables efficient processing when most tasks spawn other subtasks (as do most ForkJoinTasks),as well as when many small tasks are submitted to the pool from external clients. Especially when setting asyncMode to true in constructors,ForkJoinPools may also be appropriate for use with event-style tasks that are never joined.

The main difference between forkjoinpool and other executorservices is that it uses "work stealing": all threads in the thread pool attempt to find and execute the tasks submitted to the thread pool. This processing is very efficient when a large number of tasks produce subtasks, or when many small tasks are submitted to the thread pool at the same time. In particular, this processing is more efficient when asyncmode is set to true in the constructor.

ForkJoinTask

Forkjointask represents the task running in forkjoinpool.

Main methods:

Subclass:

ForkJoinWorkerThread

A thread managed by a ForkJoinPool,which executes ForkJoinTasks.

Forkjoinworkerthread represents a thread executing a task in the forkjoinpool thread pool.

Class diagram

code analysis

Next, take a brief look at the key code to deepen your understanding of fork / join.

ForkJoinPool

Workqueue is an internal class in forkjoinpool. It is an encapsulation of the work queue of threads in the thread pool and supports task stealing.

What is thread task stealing? That is to say, if you eat fruit with one of your partners and your share is finished, but his share is not finished, you will secretly take some of his fruit to eat. There are sub threads that execute two tasks. Here, it should be said that there are two workqueues A and B executing tasks. When a's tasks are completed and B's tasks are not completed, a's workqueue takes part of the tail tasks from the forkjointask array of B's workqueue for execution, which can reasonably improve the operation and calculation efficiency.

submit()

You can see:

As we said earlier, each thread has a workqueue, in which there are threads executing tasks (forkjoinworkerthread owner) and tasks to be processed by this thread (forkjointask [] array). Then the newly submitted task is added to the array.

ForkJoinWorkerThread

We can clearly see from the code that forkjoinworkthread holds forkjoinpool and forkjoinpool Reference to workqueue to indicate which thread pool the thread belongs to and which work queue it is

ForkJoinTask

fork()

You can see that if forkjoinworkerthread is running, fork() will be directly added to its work queue. Otherwise, resubmit the task.

Join() and invoke()

You can see that they all wait for the calculation to complete

Graphical process

Here are two pictures

@H_ 301_ 293@

Use example

Batch send messages

Sum

Two examples in the API documentation

reference resources

http://gee.cs.oswego.edu/dl/papers/fj.pdf

聊聊并发（八）——Fork/Join框架介绍

https://www.cnblogs.com/senlinyang/p/7885964.html

https://blog.csdn.net/u012403290/article/details/70917810