Mercurial > hg > blitz_condensed
diff src/EDU/oswego/cs/dl/util/concurrent/FJTask.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/EDU/oswego/cs/dl/util/concurrent/FJTask.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,531 @@ +/* + File: Task.java + + Originally written by Doug Lea and released into the public domain. + This may be used for any purposes whatsoever without acknowledgment. + Thanks for the assistance and support of Sun Microsystems Labs, + and everyone contributing, testing, and using this code. + + History: + Date Who What + 7Jan1999 dl first release + 14jan1999 dl simplify start() semantics; + improve documentation + 18Jan1999 dl Eliminate useless time-based waits. + 7Mar1999 dl Add reset method, + add array-based composite operations + 27Apr1999 dl Rename +*/ + +package EDU.oswego.cs.dl.util.concurrent; + + +/** + * Abstract base class for Fork/Join Tasks. + * + * <p> + * 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. + * <p> + * FJTasks should normally be defined by subclassing and adding a run() method. + * Alternatively, static inner class <code>Wrap(Runnable r)</code> + * can be used to + * wrap an existing Runnable object in a FJTask. + * <p> + * <code>FJTaskRunnerGroup.execute(FJTask)</code> can be used to + * initiate a FJTask from a non-FJTask thread. + * And <code>FJTaskRunnerGroup.invoke(FJTask)</code> 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. + * <p> + * There are three different ways to run a FJTask, + * with different scheduling semantics: + * <ul> + * <li> 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. + * <li> 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. + * <li> FJTask.invoke(FJTask) just executes the run method + * of one task from within another. It is the analog of a + * direct call. + * </ul> + * <p> + * 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. + * <p> + * 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. + * <p> + * 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. + * <p> + * 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. + * <p> + * 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. + * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] + * <p> + * @see FJTaskRunner + * @see FJTaskRunnerGroup + **/ + +public abstract class FJTask implements Runnable { + + /** + * The only status information associated with FJTasks is whether + * the they are considered to have completed. + * It is set true automatically within + * FJTaskRunner methods upon completion + * of the run method, or manually via cancel. + **/ + + private volatile boolean done; // = false; + + /** + * Return the FJTaskRunner thread running the current FJTask. + * Most FJTask methods are just relays to their current + * FJTaskRunners, that perform the indicated actions. + * @exception ClassCastException if caller thread is not a + * running FJTask. + **/ + + public static FJTaskRunner getFJTaskRunner() { + return (FJTaskRunner)(Thread.currentThread()); + } + + /** + * Return the FJTaskRunnerGroup of the thread running the current FJTask. + * @exception ClassCastException if caller thread is not a + * running FJTask. + **/ + public static FJTaskRunnerGroup getFJTaskRunnerGroup() { + return getFJTaskRunner().getGroup(); + } + + + /** + * 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. + **/ + + public final boolean isDone() { return done; } + + /** + * Indicate termination. Intended only to be called by FJTaskRunner. + * FJTasks themselves should use (non-final) method + * cancel() to suppress execution. + **/ + + protected final void setDone() { done = true; } + + /** + * 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. + **/ + + public void cancel() { setDone(); } + + + /** + * 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. + **/ + + public void reset() { done = false; } + + + /** + * 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. + * @exception ClassCastException if caller thread is not + * running in a FJTaskRunner thread. + **/ + + public void start() { getFJTaskRunnerGroup().executeTask(this); } + + + /** + * 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. + * <p> + * 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. + * @exception ClassCastException if caller thread is not + * running in a FJTaskRunner thread. + **/ + + public void fork() { getFJTaskRunner().push(this); } + + /** + * Allow the current underlying FJTaskRunner thread to process other tasks. + * <p> + * 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.) + * <p> + * 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. + * + * @exception ClassCastException if caller thread is not + * running in a FJTaskRunner thread. + **/ + + public static void yield() { getFJTaskRunner().taskYield(); } + + /** + * Yield until this task isDone. + * Equivalent to <code>while(!isDone()) yield(); </code> + * @exception ClassCastException if caller thread is not + * running in a FJTaskRunner thread. + **/ + + public void join() { getFJTaskRunner().taskJoin(this); } + + /** + * 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. + **/ + + public static void invoke(FJTask t) { + if (!t.isDone()) { + t.run(); + t.setDone(); + } + } + + /** + * Fork both tasks and then wait for their completion. It behaves as: + * <pre> + * task1.fork(); task2.fork(); task2.join(); task1.join(); + * </pre> + * As a simple classic example, here is + * a class that computes the Fibonacci function: + * <pre> + * 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"); + * } + * } + * } + * </pre> + * + * @exception ClassCastException if caller thread is not + * running in a FJTaskRunner thread. + **/ + + public static void coInvoke(FJTask task1, FJTask task2) { + getFJTaskRunner().coInvoke(task1, task2); + } + + + /** + * Fork all tasks in array, and await their completion. + * Behaviorally equivalent to: + * <pre> + * for (int i = 0; i < tasks.length; ++i) tasks[i].fork(); + * for (int i = 0; i < tasks.length; ++i) tasks[i].join(); + * </pre> + **/ + + public static void coInvoke(FJTask[] tasks) { + getFJTaskRunner().coInvoke(tasks); + } + + /** + * A FJTask that holds a Runnable r, and calls r.run when executed. + * The class is a simple utilty to allow arbitrary Runnables + * to be used as FJTasks. + **/ + + public static class Wrap extends FJTask { + protected final Runnable runnable; + public Wrap(Runnable r) { runnable = r; } + public void run() { runnable.run(); } + } + + + /** + * A <code>new Seq</code>, when executed, + * invokes each task provided in the constructor, in order. + * The class is a simple utility + * that makes it easier to create composite FJTasks. + **/ + public static class Seq extends FJTask { + protected final FJTask[] tasks; + + /** + * Construct a Seq that, when executed, will process each of the + * tasks in the tasks array in order + **/ + public Seq(FJTask[] tasks) { + this.tasks = tasks; + } + + /** + * Two-task constructor, for compatibility with previous release. + **/ + public Seq(FJTask task1, FJTask task2) { + this.tasks = new FJTask[] { task1, task2 }; + } + + public void run() { + for (int i = 0; i < tasks.length; ++i) FJTask.invoke(tasks[i]); + } + } + + /** + * Construct and return a FJTask object that, when executed, will + * invoke the tasks in the tasks array in array order + **/ + + public static FJTask seq(FJTask[] tasks) { + return new Seq(tasks); + } + + /** + * A <code>new Par</code>, when executed, + * runs the tasks provided in the constructor in parallel using + * coInvoke(tasks). + * The class is a simple utility + * that makes it easier to create composite FJTasks. + **/ + public static class Par extends FJTask { + protected final FJTask[] tasks; + + /** + * Construct a Seq that, when executed, will process each of the + * tasks in the tasks array in parallel + **/ + public Par(FJTask[] tasks) { + this.tasks = tasks; + } + + /** + * Two-task constructor, for compatibility with previous release. + **/ + public Par(FJTask task1, FJTask task2) { + this.tasks = new FJTask[] { task1, task2 }; + } + + + public void run() { + FJTask.coInvoke(tasks); + } + } + + + /** + * Construct and return a FJTask object that, when executed, will + * invoke the tasks in the tasks array in parallel using coInvoke + **/ + public static FJTask par(FJTask[] tasks) { + return new Par(tasks); + } + + /** + * A <code>new Seq2(task1, task2)</code>, when executed, + * invokes task1 and then task2, in order. + * The class is a simple utility + * that makes it easier to create composite Tasks. + **/ + public static class Seq2 extends FJTask { + protected final FJTask fst; + protected final FJTask snd; + public Seq2(FJTask task1, FJTask task2) { + fst = task1; + snd = task2; + } + public void run() { + FJTask.invoke(fst); + FJTask.invoke(snd); + } + } + + /** + * Construct and return a FJTask object that, when executed, will + * invoke task1 and task2, in order + **/ + + public static FJTask seq(FJTask task1, FJTask task2) { + return new Seq2(task1, task2); + } + + /** + * A <code>new Par(task1, task2)</code>, when executed, + * runs task1 and task2 in parallel using coInvoke(task1, task2). + * The class is a simple utility + * that makes it easier to create composite Tasks. + **/ + public static class Par2 extends FJTask { + protected final FJTask fst; + protected final FJTask snd; + public Par2(FJTask task1, FJTask task2) { + fst = task1; + snd = task2; + } + public void run() { + FJTask.coInvoke(fst, snd); + } + } + + + /** + * Construct and return a FJTask object that, when executed, will + * invoke task1 and task2, in parallel + **/ + public static FJTask par(FJTask task1, FJTask task2) { + return new Par2(task1, task2); + } + +}