多线程之线程池-forkjoinpool

ForkJoin Pool

Fork: Split task into smaller task

Join: Get Result from immediate subtasks

binary searcy example

1. split array and determine the mid element
2. check if key equals to mid element, If yes, return
3. If element less that mid, recursive search in left half of array
4. If element greater than mid, recurisive search in right half of array
5. Unless element is found, keep step 3 and step 4
6. if array size is 1 and key not euqal to the only element, Return NOT FOUND.

code

import java.util.Arrays;
import java.util.concurrent.RecursiveTask;

public class ForkJoinSearcher extends RecursiveTask {

  int[] arr;
  int key;

  public ForkJoinSearcher(int[] arr, int key) {
    this.arr = arr;
    this.key = key;
  }


  @Override
  protected Object compute() {
    int mid = (0 + arr.length) / 2;
    System.out.println(Thread.currentThread().getName() + " says : After split the arry length is :: "+ arr.length + " Midpoint is " + mid);

    if (arr[mid] == key) {
      System.out.println(" FOUND !!!!!!!!!");
      return true;
    } else if (mid == 1 || mid == arr.length) {
      System.out.println("NOT FOUND !!!!!!!!!");
      return false;
    } else if (key < arr[mid]) {
      System.out.println(Thread.currentThread().getName() + " says :: Doing Left-search");
      int[] left = Arrays.copyOfRange(arr, 0, mid);
      ForkJoinSearcher forkTask = new ForkJoinSearcher(left, key);
      forkTask.fork();
      return forkTask.join();
    } else if (key > arr[mid]) {
      System.out.println(Thread.currentThread().getName() + " says :: Doing Right-search");
      int[] right = Arrays.copyOfRange(arr, mid, arr.length);
      ForkJoinSearcher forkTask = new ForkJoinSearcher(right, key);
      forkTask.fork();
      return forkTask.join();
    }
    return false;
  }

}

import java.util.concurrent.ForkJoinPool;

public class BinarySearch {

  public static void searchUsingFJP(int[] input, int key) {
    ForkJoinPool forkJoinPool = new ForkJoinPool(2);
    ForkJoinSearcher searcher = new ForkJoinSearcher(input, key);
    boolean res = (boolean) forkJoinPool.invoke(searcher);
    System.out.println(" Element ::" + key +" has been found in array? :: " + res );
  }


  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4 ,5, 6, 7, 9 ,10, 20};
    BinarySearch.searchUsingFJP(arr, 3);
  }
}

work stealing

Worker thread can only execute one task at a time, but ForkJoinPool doesn't create separate thread for every single task, instead thread in the pool has it's own double-ended queue (dequeue) which stores tasks.

By default, work thread get taks from head of its own dequeue, when it's empty, the thread takes task from the tail of dequeu of other busy thread or from global entry queue.