ForkJoin Framework In Java — Part — 3.3( Task Submission In Queue and Polling)

In this article we are going to continue with fork join framework and we are going to understand how a task submitted to fork join framework is handled.

Submission In FJ pool

Queue Selection

when a task is submitted to pool, it is randomly associated with one of the serveral available submission queue , this allocation is done on the basis of hashing using threadLocalRandomProbe which give us a hash that helps in selecting a queue in a manner that it reduces contention & improves load balancing

To understand this :

each thread has a probe ( a integer value)

and for assigning the queue fj uses the logic

queueIndex = probe & ( queueCount — 1)

so for ex if there are 16 queues

queue Index calculation

Advantages of using ThreadLocalRandomProbe :

• inexpensive to access
• can be rehashed if collisions become excessive
• avoid repeated calls to random number generators

this design allow the queue selection to be O(1) , lock free and well distributed.

Task Processing

once there is a task in the submission queue , the idle worker start picking task and if the task needs to be divided then it is divided into subtasks and then put into the task queue .

How to decide task needs to be divided or not ?

it is not decided by ForkJoin or the Worker thread it depends on the task itself

Here if one worker becomes idle it can steal from some other worker task queue to enhance throughput . finally once all task are done, the result is returned.

Example Case :

Consider a Merge Sort Task is Submitted to FJ

merge sort in Fork Join Pool

Step By Step Manner

1. Task is submitted to Fork Join Pool
2. Queue is decided based on the probe logic , spin lock is taken to put the task into the submission queue.
3. idle worker picks the task and put it into its own local task queue

the worker scans for work in this manner : own queue > submission queue

4. worker start executing the task, it decides if it need to be split as per the task.

left.fork() -> push it into the queue -> start computing the right

5. task stealing : if some worker is idle then it steals task from the other worker queue , for each subtask above steps are repeated untill single unit result can be obtained

6.once all subtask are completed then results are joined and it is returned

this completes this part of fork join pool , now we have a clear understanding of how task submission to result flow work. next we will deep dive more into the management part of the fork join pool we will study how workers are created on the go , how they are invoked , how scanning and joining task work internally.

Thanks for Reading !!