EDU.oswego.cs.dl.util.concurrent
Class FJTask

java.lang.Object
  EDU.oswego.cs.dl.util.concurrent.FJTask

All Implemented Interfaces:

java.lang.Runnable

Direct Known Subclasses:

FJTask.Par, FJTask.Par2, FJTask.Seq, FJTask.Seq2, FJTask.Wrap, FJTaskRunnerGroup.InvokableFJTask

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

Abstract base class for Fork/Join Tasks.

FJTasks are lightweight, stripped-down analogs of Threads. Many FJTasks share the same pool of Java threads. This is supported by the FJTaskRunnerGroup and FJTaskRunner classes, that mainly contain methods called only internally by FJTasks. FJTasks 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.

FJTasks 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 FJTask.

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

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

• FJTask.start() (as well as FJTaskRunnerGroup.execute(FJTask)) behaves pretty much like Thread.start(). It enqueues a task to be run the next time any FJTaskRunner thread is otherwise idle. It maintains standard FIFO ordering with respect to the group of worker threads.
• FJTask.fork() (as well as the two-task spawning method, coInvoke(task1, task2), and the array version coInvoke(FJTask[] tasks)) starts a task that will be executed in procedure-call-like LIFO order if executed by the same worker thread as the one that created it, but is FIFO with respect to other tasks if it is run 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(), but can only be used when these scheduling semantics are acceptable.
• FJTask.invoke(FJTask) just executes the run method of one task from within another. It is the analog of a direct call.

The main economies of FJTasks stem from the fact that FJTasks do not support blocking operations of any kind. FJTasks 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 FJTasks are those that in turn generate other FJTasks.

There is nothing actually preventing you from blocking within a FJTask, and very short waits/blocks are completely well behaved. But FJTasks are not designed to support arbitrary synchronization since there is no way to suspend and resume individual tasks once they have begun executing. FJTasks should also be finite in duration -- they should not contain infinite loops. FJTasks 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. FJTasks are just not designed to support these things. FJTasks may however yield() control to allow their FJTaskRunner threads to run other tasks, and may wait for other dependent tasks via join(). These are the only coordination mechanisms supported by FJTasks.

FJTasks, and the FJTaskRunners that execute them are not intrinsically robust with respect to exceptions. A FJTask 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 FJTaskRunner 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 FJTasks.

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

Given these overhead savings, you might be tempted to use FJTasks for everything you would use a normal Thread to do. Don't. Java Threads remain better for general purpose thread-based programming. Remember that FJTasks cannot be used for designs involving arbitrary blocking synchronization or I/O. Extending FJTasks 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.

[ Introduction to this package. ]

See Also:

FJTaskRunner, FJTaskRunnerGroup

Nested Class Summary

static class	FJTask.Par A new Par, when executed, runs the tasks provided in the constructor in parallel using coInvoke(tasks).
static class	FJTask.Par2 A new Par(task1, task2), when executed, runs task1 and task2 in parallel using coInvoke(task1, task2).
static class	FJTask.Seq A new Seq, when executed, invokes each task provided in the constructor, in order.
static class	FJTask.Seq2 A new Seq2(task1, task2), when executed, invokes task1 and then task2, in order.
static class	FJTask.Wrap A FJTask that holds a Runnable r, and calls r.run when executed.

Constructor Summary

FJTask()

Method Summary

void	cancel() Set the termination status of this task.
static void	coInvoke(FJTask[] tasks) Fork all tasks in array, and await their completion.
static void	coInvoke(FJTask task1, FJTask task2) Fork both tasks and then wait for their completion.
void	fork() Arrange for execution of a strictly dependent task.
static FJTaskRunner	getFJTaskRunner() Return the FJTaskRunner thread running the current FJTask.
static FJTaskRunnerGroup	getFJTaskRunnerGroup() Return the FJTaskRunnerGroup of the thread running the current FJTask.
static void	invoke(FJTask 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 FJTask	par(FJTask[] tasks) Construct and return a FJTask object that, when executed, will invoke the tasks in the tasks array in parallel using coInvoke
static FJTask	par(FJTask task1, FJTask task2) Construct and return a FJTask object that, when executed, will invoke task1 and task2, in parallel
void	reset() Clear the termination status of this task.
static FJTask	seq(FJTask[] tasks) Construct and return a FJTask object that, when executed, will invoke the tasks in the tasks array in array order
static FJTask	seq(FJTask task1, FJTask task2) Construct and return a FJTask object that, when executed, will invoke task1 and task2, in order
protected void	setDone() Indicate termination.
void	start() Execute this task.
static void	yield() Allow the current underlying FJTaskRunner 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

FJTask

public FJTask()

Method Detail

getFJTaskRunner

public static FJTaskRunner getFJTaskRunner()

Return the FJTaskRunner thread running the current FJTask. Most FJTask methods are just relays to their current FJTaskRunners, that perform the indicated actions.

Throws:

java.lang.ClassCastException - if caller thread is not a running FJTask.

getFJTaskRunnerGroup

public static FJTaskRunnerGroup getFJTaskRunnerGroup()

Return the FJTaskRunnerGroup of the thread running the current FJTask.

Throws:

java.lang.ClassCastException - if caller thread is not a running FJTask.

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 FJTask has been started or is currently executing.

setDone

protected final void setDone()

Indicate termination. Intended only to be called by FJTaskRunner. FJTasks 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 FJTask 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 FJTaskRunner 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 FJTaskRunner thread.

yield

public static void yield()

Allow the current underlying FJTaskRunner 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 FJTask. Additionally, you must never hold a lock while performing a yield or join. (This is because multiple FJTasks 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 FJTask. 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 FJTasks, 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 FJTask generated by the current task, or one of its subtasks.

Throws:

java.lang.ClassCastException - if caller thread is not running in a FJTaskRunner 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 FJTaskRunner thread.

invoke

public static void invoke(FJTask 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 FJTask, but you just need to directly execute its body from within some other task.

coInvoke

public static void coInvoke(FJTask task1,
                            FJTask 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 FJTask {
 
  // 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)
      FJTaskRunnerGroup group = new FJTaskRunnerGroup(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");
    }
  }
 }
 

Throws:

java.lang.ClassCastException - if caller thread is not running in a FJTaskRunner thread.

coInvoke

public static void coInvoke(FJTask[] 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();
 

seq

public static FJTask seq(FJTask[] tasks)

Construct and return a FJTask object that, when executed, will invoke the tasks in the tasks array in array order

par

public static FJTask par(FJTask[] tasks)

Construct and return a FJTask object that, when executed, will invoke the tasks in the tasks array in parallel using coInvoke

seq

public static FJTask seq(FJTask task1,
                         FJTask task2)

Construct and return a FJTask object that, when executed, will invoke task1 and task2, in order

par

public static FJTask par(FJTask task1,
                         FJTask task2)

Construct and return a FJTask object that, when executed, will invoke task1 and task2, in parallel