On Java fork / join parallel framework

Preliminary understanding of fork / join framework

Fork / join framework is a parallel task framework added to java7. It can divide tasks into small enough tasks, and then let different threads do these separated small things, and then join after completion to assemble the results of small tasks into the results of large tasks. The following picture shows the working model of this framework:

The premise of using fork / join parallel framework is that our tasks can be divided into sufficiently small tasks, and the results of large tasks can be assembled according to the results of small tasks. The simplest example is to use fork / join framework to find the maximum / minimum value in an array, and this task can be divided into many small tasks, A large task is to find the maximum / minimum value in a large array. We can split a large array into many small arrays, then solve the maximum / minimum value in each small array respectively, and then assemble the final maximum and minimum value according to the results of these tasks. The following code shows how to solve the maximum value of an array through fork / join:

You can split into small tasks by setting different thresholds. The smaller the threshold, the more small tasks.

Job theft algorithm

In the implementation of fork / join, the small tasks separated from large tasks will be distributed to different queues, and each queue will be consumed by one thread. This is to obtain the multi-threaded competition of tasks, but some threads will consume their own queues in advance. Some threads fail to consume the queue in time. At this time, the thread that has completed the task will steal the task queue of those threads that have not completed the consumption. In order to reduce thread competition, fork / join uses a dual ended queue to access small tasks. The thread assigned to this queue will always obtain a task from scratch and then execute it, Stealing threads always pull tasks from the end of the queue.

Implementation details of frok / join framework

In the above example code, we found that the fork / join task is executed through the forkjoinpool, so a core of the framework is the fork and join of the task, and then the forkjoinpool. As for the fork and join of tasks, we can imagine that they are also controlled by our own code. Therefore, to analyze fork / join, forkjoinpool is the most worth studying.

The above picture shows the class diagram of forkjoinpool, which is essentially an executor. In forkjoinpool, there are two particularly important members as follows:

Workqueues is used to save the tasks submitted to forkjoinpool. The specific execution is performed by forkjoinworkerthread, and forkjoinworkerthreadfactory can be used to produce forkjoinworkerthread. You can look at some forkjoinworkerthreads. It can be found that each forkjoinworkerthread has a pool and a workqueue, which is consistent with the above description. Each thread is assigned a task queue, and the threads executing the task queue are provided by the pool.

Let's take a look at what happens when we fork:

Looking at the above fork code, we can see that we first get the current thread, and then judge whether it is our forkjoinpool dedicated thread. If so, Cast type (down conversion) into forkjoinworkerthread, and then push the task to the queue responsible for this thread. If the current thread is not a forkjoinworkerthread type thread, the logic after else will be followed, which roughly means that first try to submit the task to the current thread. If it is unsuccessful, use the exception processing method. The underlying implementation is more complex , it doesn't have much to do with our use of fork / join. If you want to understand the specific principle, you can look at the source code.

Let's take a look at the join process:

The main call links are shown above. We found that it finally fell to the compute method we wrote in the code, that is, to execute it. Therefore, we need to know that fork is only a split task. Our tasks will be executed only when we execute join.

How to use fork / join parallel framework

The previous article first showed an example of finding the maximum value in the array, then introduced the "work stealing algorithm", and then analyzed some details of the fork / join framework. The following is what we are most concerned about. How to use the fork / join framework?

In order to use the fork / join framework, we only need to inherit the class recursivetask or recursiveaction. The former is suitable for scenarios with return values, while the latter is suitable for scenarios without return values.

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.