org.metasyntactic.thread.concurrent
Class ForkJoinTask

java.lang.Object
  |
  +--org.metasyntactic.thread.concurrent.ForkJoinTask
All Implemented Interfaces:
java.lang.Runnable
Direct Known Subclasses:
ForkJoinTask.Parallel, ForkJoinTask.Sequence, ForkJoinTask.Wrap

public abstract class ForkJoinTask
extends java.lang.Object
implements java.lang.Runnable

Abstract base class for Fork/Join Tasks.

ForkJoinTasks are lightweight, stripped-down analogs of Threads. Many ForkJoinTasks share the same pool of Java threads. This is supported by the ForkJoinTaskRunnerGroup and ForkJoinTaskRunner classes, that mainly contain methods called only internally by ForkJoinTasks. ForkJoinTasks support versions of the most common methods found in class Thread, including start(), yield() and join(). However, they don't support priorities, ThreadGroups or other bookkeeping or control methods of class Thread.

ForkJoinTasks should normally be defined by subclassing and adding a run() method. Alternatively, static inner class Wrap(Runnable r) can be used to wrap an existing Runnable object in a ForkJoinTask.

ForkJoinTaskRunnerGroup.execute(ForkJoinTask) can be used to initiate a ForkJoinTask from a non-ForkJoinTask thread. And ForkJoinTaskRunnerGroup.invoke(ForkJoinTask) can be used to initiate a ForkJoinTask and then wait for it to complete before returning. These are the only entry-points from normal threads to ForkJoinTasks. Most ForkJoinTask methods themselves may only be called from within running ForkJoinTasks. They throw ClassCastExceptions if they are not, reflecting the fact that these methods can only be executed using ForkJoinTaskRunner threads, not generic java.lang.Threads.

There are three different ways to run a ForkJoinTask, with different scheduling semantics:

The main economies of ForkJoinTasks stem from the fact that ForkJoinTasks do not support blocking operations of any kind. ForkJoinTasks should just run to completion without issuing waits or performing blocking IO. There are several styles for creating the run methods that execute as tasks, including event-style methods, and pure computational methods. Generally, the best kinds of ForkJoinTasks are those that in turn generate other ForkJoinTasks.

There is nothing actually preventing you from blocking within a ForkJoinTask, and very short waits/blocks are completely well behaved. But ForkJoinTasks are not designed to support arbitrary synchronization since there is no way to suspend and resume individual tasks once they have begun executing. ForkJoinTasks should also be finite in duration -- they should not contain infinite loops. ForkJoinTasks that might need to perform a blocking action, or hold locks for extended periods, or loop forever can instead create normal java Thread objects that will do so. ForkJoinTasks are just not designed to support these things. ForkJoinTasks may however yield() control to allow their ForkJoinTaskRunner threads to run other tasks, and may wait for other dependent tasks via join(). These are the only coordination mechanisms supported by ForkJoinTasks.

ForkJoinTasks, and the ForkJoinTaskRunners that execute them are not intrinsically robust with respect to exceptions. A ForkJoinTask that aborts via an exception does not automatically have its completion flag (isDone) set. As with ordinary Threads, an uncaught exception will normally cause its ForkJoinTaskRunner thread to die, which in turn may sometimes cause other computations being performed to hang or abort. You can of course do better by trapping exceptions inside the run methods of ForkJoinTasks.

The overhead differences between ForkJoinTasks and Threads are substantial, especially when using fork() or coInvoke(). ForkJoinTasks can be two or three orders of magnitude faster than Threads, at least when run on JVMs with high-performance garbage collection (every ForkJoinTask quickly becomes garbage) and good native thread support.

Given these overhead savings, you might be tempted to use ForkJoinTasks for everything you would use a normal Thread to do. Don't. Java Threads remain better for general purpose thread-based programming. Remember that ForkJoinTasks cannot be used for designs involving arbitrary blocking synchronization or I/O. Extending ForkJoinTasks to support such capabilities would amount to re-inventing the Thread class, and would make them less optimal in the contexts that they were designed for.

See Also:
ForkJoinTaskRunner, ForkJoinTaskRunnerGroup

Nested Class Summary
static class ForkJoinTask.Parallel
          A new Par, when executed, runs the tasks provided in the constructor in parallel using coInvoke(tasks).
static class ForkJoinTask.Sequence
          A new Sequence, when executed, invokes each task provided in the constructor, in order.
static class ForkJoinTask.Wrap
          A ForkJoinTask that holds a Runnable r, and calls r.run when executed.
 
Constructor Summary
ForkJoinTask()
           
 
Method Summary
 void cancel()
          Set the termination status of this task.
static void coInvoke(ForkJoinTask[] tasks)
          Fork all tasks in array, and await their completion.
static void coInvoke(ForkJoinTask task1, ForkJoinTask task2)
          Fork both tasks and then wait for their completion.
 void fork()
          Arrange for execution of a strictly dependent task.
static ForkJoinTaskRunner getForkJoinTaskRunner()
          Return the ForkJoinTaskRunner thread running the current ForkJoinTask.
static ForkJoinTaskRunnerGroup getForkJoinTaskRunnerGroup()
          Return the ForkJoinTaskRunnerGroup of the thread running the current ForkJoinTask.
static void invoke(ForkJoinTask t)
          Immediately execute task t by calling its run method.
 boolean isDone()
          Return true if current task has terminated or been cancelled.
 void join()
          Yield until this task isDone.
static ForkJoinTask parallel(ForkJoinTask[] tasks)
          Construct and return a ForkJoinTask object that, when executed, will invoke the tasks in the tasks array in parallel using coInvoke
 void reset()
          Clear the termination status of this task.
static ForkJoinTask sequence(ForkJoinTask[] tasks)
          Construct and return a ForkJoinTask object that, when executed, will invoke the tasks in the tasks array in array order
protected  void setDone()
          Indicate termination.
 void start()
          Execute this task.
static void yield()
          Allow the current underlying ForkJoinTaskRunner thread to process other tasks.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface java.lang.Runnable
run
 

Constructor Detail

ForkJoinTask

public ForkJoinTask()
Method Detail

getForkJoinTaskRunner

public static ForkJoinTaskRunner getForkJoinTaskRunner()
Return the ForkJoinTaskRunner thread running the current ForkJoinTask. Most ForkJoinTask methods are just relays to their current ForkJoinTaskRunners, that perform the indicated actions.

Returns:
The fork join task runner running the current fork join task
Throws:
java.lang.ClassCastException - if caller thread is not a running ForkJoinTask.

getForkJoinTaskRunnerGroup

public static ForkJoinTaskRunnerGroup getForkJoinTaskRunnerGroup()
Return the ForkJoinTaskRunnerGroup of the thread running the current ForkJoinTask.

Returns:
The ForkJoinTaskRunnerGroup of the thread running the current ForkJoinTask
Throws:
java.lang.ClassCastException - if caller thread is not a running ForkJoinTask.

isDone

public final boolean isDone()
Return true if current task has terminated or been cancelled. The method is a simple analog of the Thread.isAlive() method. However, it reports true only when the task has terminated or has been cancelled. It does not distinguish these two cases. And there is no way to determine whether a ForkJoinTask has been started or is currently executing.

Returns:
true if and only if the current task has terminated or been cancelled

setDone

protected final void setDone()
Indicate termination. Intended only to be called by ForkJoinTaskRunner. ForkJoinTasks themselves should use (non-final) method cancel() to suppress execution.


cancel

public void cancel()
Set the termination status of this task. This simple-minded analog of Thread.interrupt causes the task not to execute if it has not already been started. Cancelling a running ForkJoinTask has no effect unless the run method itself uses isDone() to probe cancellation and take appropriate action. Individual run() methods may sense status and act accordingly, normally by returning early.


reset

public void reset()
Clear the termination status of this task. This method is intended to be used only as a means to allow task objects to be recycled. It should be called only when you are sure that the previous execution of this task has terminated and, if applicable, has been joined by all other waiting tasks. Usage in any other context is a very bad idea.


start

public void start()
Execute this task. This method merely places the task in a group-wide scheduling queue. It will be run the next time any TaskRunner thread is otherwise idle. This scheduling maintains FIFO ordering of started tasks with respect to the group of worker threads.

Throws:
java.lang.ClassCastException - if caller thread is not running in a ForkJoinTaskRunner thread.

fork

public void fork()
Arrange for execution of a strictly dependent task. The task that will be executed in procedure-call-like LIFO order if executed by the same worker thread, but is FIFO with respect to other tasks forked by this thread when taken by other worker threads. That is, earlier-forked tasks are preferred to later-forked tasks by other idle workers.

Fork() is noticeably faster than start(). However, it may only be used for strictly dependent tasks -- generally, those that could logically be issued as straight method calls without changing the logic of the program. The method is optimized for use in parallel fork/join designs in which the thread that issues one or more forks cannot continue until at least some of the forked threads terminate and are joined.

Throws:
java.lang.ClassCastException - if caller thread is not running in a ForkJoinTaskRunner thread.

yield

public static void yield()
Allow the current underlying ForkJoinTaskRunner thread to process other tasks.

Spinloops based on yield() are well behaved so long as the event or condition being waited for is produced via another ForkJoinTask. Additionally, you must never hold a lock while performing a yield or join. (This is because multiple ForkJoinTasks can be run by the same Thread during a yield. Since java locks are held per-thread, the lock would not maintain the conceptual exclusion you have in mind.)

Otherwise, spinloops using yield are the main construction of choice when a task must wait for a condition that it is sure will eventually occur because it is being produced by some other ForkJoinTask. The most common such condition is built-in: join() repeatedly yields until a task has terminated after producing some needed results. You can also use yield to wait for callbacks from other ForkJoinTasks, to wait for status flags to be set, and so on. However, in all these cases, you should be confident that the condition being waited for will occur, essentially always because it is produced by a ForkJoinTask generated by the current task, or one of its subtasks.

Throws:
java.lang.ClassCastException - if caller thread is not running in a ForkJoinTaskRunner thread.

join

public void join()
Yield until this task isDone. Equivalent to while(!isDone()) yield();

Throws:
java.lang.ClassCastException - if caller thread is not running in a ForkJoinTaskRunner thread.

invoke

public static void invoke(ForkJoinTask t)
Immediately execute task t by calling its run method. Has no effect if t has already been run or has been cancelled. It is equivalent to calling t.run except that it deals with completion status, so should always be used instead of directly calling run. The method can be useful when a computation has been packaged as a ForkJoinTask, but you just need to directly execute its body from within some other task.

Parameters:
t - The task to invoke

coInvoke

public static void coInvoke(ForkJoinTask task1,
                            ForkJoinTask task2)
Fork both tasks and then wait for their completion. It behaves as:
 task1.fork(); task2.fork(); task2.join(); task1.join();
 
As a simple classic example, here is a class that computes the Fibonacci function:
 public class Fib extends ForkJoinTask {
 
  // Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);  for n> 1
  //		  fibonacci(0) = 0;
  //		  fibonacci(1) = 1.
 
  // Value to compute fibonacci function for.
  // It is replaced with the answer when computed.
  private volatile int number;
 
  public Fib(int n) { number = n; }
 
  public int getAnswer() {
	if (!isDone()) throw new Error("Not yet computed");
	return number;
  }
 
  public void run() {
	int n = number;
	if (n > 1) {
	  Fib f1 = new Fib(n - 1);
	  Fib f2 = new Fib(n - 2);
 
	  coInvoke(f1, f2); // run these in parallel
 
	  // we know f1 and f2 are computed, so just directly access numbers
	  number = f1.number + f2.number;
	}
  }
 
  public static void main(String[] args) { // sample driver
	try {
	  int groupSize = 2;	// 2 worker threads
	  int num = 35;		 // compute fib(35)
	  ForkJoinTaskRunnerGroup group = new ForkJoinTaskRunnerGroup(groupSize);
	  Fib f = new Fib(num);
	  group.invoke(f);
	  int result = f.getAnswer();
	  System.out.println(" Answer: " + result);
	}
	catch (InterruptedException ex) {
	  System.out.println("Interrupted");
	}
  }
 }
 

Parameters:
task1 -
task2 -
Throws:
java.lang.ClassCastException - if caller thread is not running in a ForkJoinTaskRunner thread.

coInvoke

public static void coInvoke(ForkJoinTask[] tasks)
Fork all tasks in array, and await their completion. Behaviorally equivalent to:
 for (int i = 0; i < tasks.length; ++i) tasks[i].fork();
 for (int i = 0; i < tasks.length; ++i) tasks[i].join();
 

Parameters:
tasks -

sequence

public static ForkJoinTask sequence(ForkJoinTask[] tasks)
Construct and return a ForkJoinTask object that, when executed, will invoke the tasks in the tasks array in array order

Parameters:
tasks - The tasks to make a new ForkJoinTask out of
Returns:
A new ForkJoinTask that will invoke all the tasks in 'tasks'

parallel

public static ForkJoinTask parallel(ForkJoinTask[] tasks)
Construct and return a ForkJoinTask object that, when executed, will invoke the tasks in the tasks array in parallel using coInvoke

Parameters:
tasks - The tasks to make a new ForkJoinTask out of
Returns:
A new ForkJoinTask that will invoke all the tasks in 'tasks'