001: /*
002: File: Task.java
003:
004: Originally written by Doug Lea and released into the public domain.
005: This may be used for any purposes whatsoever without acknowledgment.
006: Thanks for the assistance and support of Sun Microsystems Labs,
007: and everyone contributing, testing, and using this code.
008:
009: History:
010: Date Who What
011: 7Jan1999 dl first release
012: 14jan1999 dl simplify start() semantics;
013: improve documentation
014: 18Jan1999 dl Eliminate useless time-based waits.
015: 7Mar1999 dl Add reset method,
016: add array-based composite operations
017: 27Apr1999 dl Rename
018: */
019:
020: package EDU.oswego.cs.dl.util.concurrent;
021:
022: /**
023: * Abstract base class for Fork/Join Tasks.
024: *
025: * <p>
026: * FJTasks are lightweight, stripped-down analogs of Threads.
027: * Many FJTasks share the same pool of Java threads. This is
028: * supported by the FJTaskRunnerGroup and FJTaskRunner classes, that
029: * mainly contain
030: * methods called only internally by FJTasks.
031: * FJTasks support versions of the most common methods found in class Thread,
032: * including start(), yield() and join(). However, they
033: * don't support priorities, ThreadGroups or other bookkeeping
034: * or control methods of class Thread.
035: * <p>
036: * FJTasks should normally be defined by subclassing and adding a run() method.
037: * Alternatively, static inner class <code>Wrap(Runnable r)</code>
038: * can be used to
039: * wrap an existing Runnable object in a FJTask.
040: * <p>
041: * <code>FJTaskRunnerGroup.execute(FJTask)</code> can be used to
042: * initiate a FJTask from a non-FJTask thread.
043: * And <code>FJTaskRunnerGroup.invoke(FJTask)</code> can be used to initiate
044: * a FJTask and then wait for it to complete before returning.
045: * These are the only entry-points from normal threads to FJTasks.
046: * Most FJTask methods themselves may only be called from within running FJTasks.
047: * They throw ClassCastExceptions if they are not,
048: * reflecting the fact that these methods
049: * can only be executed using FJTaskRunner threads, not generic
050: * java.lang.Threads.
051: * <p>
052: * There are three different ways to run a FJTask,
053: * with different scheduling semantics:
054: * <ul>
055: * <li> FJTask.start() (as well as FJTaskRunnerGroup.execute(FJTask))
056: * behaves pretty much like Thread.start(). It enqueues a task to be
057: * run the next time any FJTaskRunner thread is otherwise idle.
058: * It maintains standard FIFO ordering with respect to
059: * the group of worker threads.
060: * <li> FJTask.fork() (as well as the two-task spawning method,
061: * coInvoke(task1, task2), and the array version
062: * coInvoke(FJTask[] tasks)) starts a task
063: * that will be executed in
064: * procedure-call-like LIFO order if executed by the
065: * same worker thread as the one that created it, but is FIFO
066: * with respect to other tasks if it is run by
067: * other worker threads. That is, earlier-forked
068: * tasks are preferred to later-forked tasks by other idle workers.
069: * Fork() is noticeably faster than start(), but can only be
070: * used when these scheduling semantics are acceptable.
071: * <li> FJTask.invoke(FJTask) just executes the run method
072: * of one task from within another. It is the analog of a
073: * direct call.
074: * </ul>
075: * <p>
076: * The main economies of FJTasks stem from the fact that
077: * FJTasks do not support blocking operations of any kind.
078: * FJTasks should just run to completion without
079: * issuing waits or performing blocking IO.
080: * There are several styles for creating the run methods that
081: * execute as tasks, including
082: * event-style methods, and pure computational methods.
083: * Generally, the best kinds of FJTasks are those that in turn
084: * generate other FJTasks.
085: * <p>
086: * There is nothing actually
087: * preventing you from blocking within a FJTask, and very short waits/blocks are
088: * completely well behaved. But FJTasks are not designed
089: * to support arbitrary synchronization
090: * since there is no way to suspend and resume individual tasks
091: * once they have begun executing. FJTasks should also be finite
092: * in duration -- they should not contain infinite loops.
093: * FJTasks that might need to perform a blocking
094: * action, or hold locks for extended periods, or
095: * loop forever can instead create normal
096: * java Thread objects that will do so. FJTasks are just not
097: * designed to support these things.
098: * FJTasks may however yield() control to allow their FJTaskRunner threads
099: * to run other tasks,
100: * and may wait for other dependent tasks via join(). These
101: * are the only coordination mechanisms supported by FJTasks.
102: * <p>
103: * FJTasks, and the FJTaskRunners that execute them are not
104: * intrinsically robust with respect to exceptions.
105: * A FJTask that aborts via an exception does not automatically
106: * have its completion flag (isDone) set.
107: * As with ordinary Threads, an uncaught exception will normally cause
108: * its FJTaskRunner thread to die, which in turn may sometimes
109: * cause other computations being performed to hang or abort.
110: * You can of course
111: * do better by trapping exceptions inside the run methods of FJTasks.
112: * <p>
113: * The overhead differences between FJTasks and Threads are substantial,
114: * especially when using fork() or coInvoke().
115: * FJTasks can be two or three orders of magnitude faster than Threads,
116: * at least when run on JVMs with high-performance garbage collection
117: * (every FJTask quickly becomes garbage) and good native thread support.
118: * <p>
119: * Given these overhead savings, you might be tempted to use FJTasks for
120: * everything you would use a normal Thread to do. Don't. Java Threads
121: * remain better for general purpose thread-based programming. Remember
122: * that FJTasks cannot be used for designs involving arbitrary blocking
123: * synchronization or I/O. Extending FJTasks to support such capabilities
124: * would amount to re-inventing the Thread class, and would make them
125: * less optimal in the contexts that they were designed for.
126: * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
127: * <p>
128: * @see FJTaskRunner
129: * @see FJTaskRunnerGroup
130: **/
131:
132: public abstract class FJTask implements Runnable {
133:
134: /**
135: * The only status information associated with FJTasks is whether
136: * the they are considered to have completed.
137: * It is set true automatically within
138: * FJTaskRunner methods upon completion
139: * of the run method, or manually via cancel.
140: **/
141:
142: private volatile boolean done; // = false;
143:
144: /**
145: * Return the FJTaskRunner thread running the current FJTask.
146: * Most FJTask methods are just relays to their current
147: * FJTaskRunners, that perform the indicated actions.
148: * @exception ClassCastException if caller thread is not a
149: * running FJTask.
150: **/
151:
152: public static FJTaskRunner getFJTaskRunner() {
153: return (FJTaskRunner) (Thread.currentThread());
154: }
155:
156: /**
157: * Return the FJTaskRunnerGroup of the thread running the current FJTask.
158: * @exception ClassCastException if caller thread is not a
159: * running FJTask.
160: **/
161: public static FJTaskRunnerGroup getFJTaskRunnerGroup() {
162: return getFJTaskRunner().getGroup();
163: }
164:
165: /**
166: * Return true if current task has terminated or been cancelled.
167: * The method is a simple analog of the Thread.isAlive()
168: * method. However, it reports true only when the task has terminated
169: * or has been cancelled. It does not distinguish these two cases.
170: * And there is no way to determine whether a FJTask has been started
171: * or is currently executing.
172: **/
173:
174: public final boolean isDone() {
175: return done;
176: }
177:
178: /**
179: * Indicate termination. Intended only to be called by FJTaskRunner.
180: * FJTasks themselves should use (non-final) method
181: * cancel() to suppress execution.
182: **/
183:
184: protected final void setDone() {
185: done = true;
186: }
187:
188: /**
189: * Set the termination status of this task. This simple-minded
190: * analog of Thread.interrupt
191: * causes the task not to execute if it has not already been started.
192: * Cancelling a running FJTask
193: * has no effect unless the run method itself uses isDone()
194: * to probe cancellation and take appropriate action.
195: * Individual run() methods may sense status and
196: * act accordingly, normally by returning early.
197: **/
198:
199: public void cancel() {
200: setDone();
201: }
202:
203: /**
204: * Clear the termination status of this task.
205: * This method is intended to be used
206: * only as a means to allow task objects to be recycled. It should
207: * be called only when you are sure that the previous
208: * execution of this task has terminated and, if applicable, has
209: * been joined by all other waiting tasks. Usage in any other
210: * context is a very bad idea.
211: **/
212:
213: public void reset() {
214: done = false;
215: }
216:
217: /**
218: * Execute this task. This method merely places the task in a
219: * group-wide scheduling queue.
220: * It will be run
221: * the next time any TaskRunner thread is otherwise idle.
222: * This scheduling maintains FIFO ordering of started tasks
223: * with respect to
224: * the group of worker threads.
225: * @exception ClassCastException if caller thread is not
226: * running in a FJTaskRunner thread.
227: **/
228:
229: public void start() {
230: getFJTaskRunnerGroup().executeTask(this );
231: }
232:
233: /**
234: * Arrange for execution of a strictly dependent task.
235: * The task that will be executed in
236: * procedure-call-like LIFO order if executed by the
237: * same worker thread, but is FIFO with respect to other tasks
238: * forked by this thread when taken by other worker threads.
239: * That is, earlier-forked
240: * tasks are preferred to later-forked tasks by other idle workers.
241: * <p>
242: * Fork() is noticeably
243: * faster than start(). However, it may only
244: * be used for strictly dependent tasks -- generally, those that
245: * could logically be issued as straight method calls without
246: * changing the logic of the program.
247: * The method is optimized for use in parallel fork/join designs
248: * in which the thread that issues one or more forks
249: * cannot continue until at least some of the forked
250: * threads terminate and are joined.
251: * @exception ClassCastException if caller thread is not
252: * running in a FJTaskRunner thread.
253: **/
254:
255: public void fork() {
256: getFJTaskRunner().push(this );
257: }
258:
259: /**
260: * Allow the current underlying FJTaskRunner thread to process other tasks.
261: * <p>
262: * Spinloops based on yield() are well behaved so long
263: * as the event or condition being waited for is produced via another
264: * FJTask. Additionally, you must never hold a lock
265: * while performing a yield or join. (This is because
266: * multiple FJTasks can be run by the same Thread during
267: * a yield. Since java locks are held per-thread, the lock would not
268: * maintain the conceptual exclusion you have in mind.)
269: * <p>
270: * Otherwise, spinloops using
271: * yield are the main construction of choice when a task must wait
272: * for a condition that it is sure will eventually occur because it
273: * is being produced by some other FJTask. The most common
274: * such condition is built-in: join() repeatedly yields until a task
275: * has terminated after producing some needed results. You can also
276: * use yield to wait for callbacks from other FJTasks, to wait for
277: * status flags to be set, and so on. However, in all these cases,
278: * you should be confident that the condition being waited for will
279: * occur, essentially always because it is produced by
280: * a FJTask generated by the current task, or one of its subtasks.
281: *
282: * @exception ClassCastException if caller thread is not
283: * running in a FJTaskRunner thread.
284: **/
285:
286: public static void yield() {
287: getFJTaskRunner().taskYield();
288: }
289:
290: /**
291: * Yield until this task isDone.
292: * Equivalent to <code>while(!isDone()) yield(); </code>
293: * @exception ClassCastException if caller thread is not
294: * running in a FJTaskRunner thread.
295: **/
296:
297: public void join() {
298: getFJTaskRunner().taskJoin(this );
299: }
300:
301: /**
302: * Immediately execute task t by calling its run method. Has no
303: * effect if t has already been run or has been cancelled.
304: * It is equivalent to calling t.run except that it
305: * deals with completion status, so should always be used
306: * instead of directly calling run.
307: * The method can be useful
308: * when a computation has been packaged as a FJTask, but you just need to
309: * directly execute its body from within some other task.
310: **/
311:
312: public static void invoke(FJTask t) {
313: if (!t.isDone()) {
314: t.run();
315: t.setDone();
316: }
317: }
318:
319: /**
320: * Fork both tasks and then wait for their completion. It behaves as:
321: * <pre>
322: * task1.fork(); task2.fork(); task2.join(); task1.join();
323: * </pre>
324: * As a simple classic example, here is
325: * a class that computes the Fibonacci function:
326: * <pre>
327: * public class Fib extends FJTask {
328: *
329: * // Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); for n> 1
330: * // fibonacci(0) = 0;
331: * // fibonacci(1) = 1.
332: *
333: * // Value to compute fibonacci function for.
334: * // It is replaced with the answer when computed.
335: * private volatile int number;
336: *
337: * public Fib(int n) { number = n; }
338: *
339: * public int getAnswer() {
340: * if (!isDone()) throw new Error("Not yet computed");
341: * return number;
342: * }
343: *
344: * public void run() {
345: * int n = number;
346: * if (n > 1) {
347: * Fib f1 = new Fib(n - 1);
348: * Fib f2 = new Fib(n - 2);
349: *
350: * coInvoke(f1, f2); // run these in parallel
351: *
352: * // we know f1 and f2 are computed, so just directly access numbers
353: * number = f1.number + f2.number;
354: * }
355: * }
356: *
357: * public static void main(String[] args) { // sample driver
358: * try {
359: * int groupSize = 2; // 2 worker threads
360: * int num = 35; // compute fib(35)
361: * FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
362: * Fib f = new Fib(num);
363: * group.invoke(f);
364: * int result = f.getAnswer();
365: * System.out.println(" Answer: " + result);
366: * }
367: * catch (InterruptedException ex) {
368: * System.out.println("Interrupted");
369: * }
370: * }
371: * }
372: * </pre>
373: *
374: * @exception ClassCastException if caller thread is not
375: * running in a FJTaskRunner thread.
376: **/
377:
378: public static void coInvoke(FJTask task1, FJTask task2) {
379: getFJTaskRunner().coInvoke(task1, task2);
380: }
381:
382: /**
383: * Fork all tasks in array, and await their completion.
384: * Behaviorally equivalent to:
385: * <pre>
386: * for (int i = 0; i < tasks.length; ++i) tasks[i].fork();
387: * for (int i = 0; i < tasks.length; ++i) tasks[i].join();
388: * </pre>
389: **/
390:
391: public static void coInvoke(FJTask[] tasks) {
392: getFJTaskRunner().coInvoke(tasks);
393: }
394:
395: /**
396: * A FJTask that holds a Runnable r, and calls r.run when executed.
397: * The class is a simple utilty to allow arbitrary Runnables
398: * to be used as FJTasks.
399: **/
400:
401: public static class Wrap extends FJTask {
402: protected final Runnable runnable;
403:
404: public Wrap(Runnable r) {
405: runnable = r;
406: }
407:
408: public void run() {
409: runnable.run();
410: }
411: }
412:
413: /**
414: * A <code>new Seq</code>, when executed,
415: * invokes each task provided in the constructor, in order.
416: * The class is a simple utility
417: * that makes it easier to create composite FJTasks.
418: **/
419: public static class Seq extends FJTask {
420: protected final FJTask[] tasks;
421:
422: /**
423: * Construct a Seq that, when executed, will process each of the
424: * tasks in the tasks array in order
425: **/
426: public Seq(FJTask[] tasks) {
427: this .tasks = tasks;
428: }
429:
430: /**
431: * Two-task constructor, for compatibility with previous release.
432: **/
433: public Seq(FJTask task1, FJTask task2) {
434: this .tasks = new FJTask[] { task1, task2 };
435: }
436:
437: public void run() {
438: for (int i = 0; i < tasks.length; ++i)
439: FJTask.invoke(tasks[i]);
440: }
441: }
442:
443: /**
444: * Construct and return a FJTask object that, when executed, will
445: * invoke the tasks in the tasks array in array order
446: **/
447:
448: public static FJTask seq(FJTask[] tasks) {
449: return new Seq(tasks);
450: }
451:
452: /**
453: * A <code>new Par</code>, when executed,
454: * runs the tasks provided in the constructor in parallel using
455: * coInvoke(tasks).
456: * The class is a simple utility
457: * that makes it easier to create composite FJTasks.
458: **/
459: public static class Par extends FJTask {
460: protected final FJTask[] tasks;
461:
462: /**
463: * Construct a Seq that, when executed, will process each of the
464: * tasks in the tasks array in parallel
465: **/
466: public Par(FJTask[] tasks) {
467: this .tasks = tasks;
468: }
469:
470: /**
471: * Two-task constructor, for compatibility with previous release.
472: **/
473: public Par(FJTask task1, FJTask task2) {
474: this .tasks = new FJTask[] { task1, task2 };
475: }
476:
477: public void run() {
478: FJTask.coInvoke(tasks);
479: }
480: }
481:
482: /**
483: * Construct and return a FJTask object that, when executed, will
484: * invoke the tasks in the tasks array in parallel using coInvoke
485: **/
486: public static FJTask par(FJTask[] tasks) {
487: return new Par(tasks);
488: }
489:
490: /**
491: * A <code>new Seq2(task1, task2)</code>, when executed,
492: * invokes task1 and then task2, in order.
493: * The class is a simple utility
494: * that makes it easier to create composite Tasks.
495: **/
496: public static class Seq2 extends FJTask {
497: protected final FJTask fst;
498: protected final FJTask snd;
499:
500: public Seq2(FJTask task1, FJTask task2) {
501: fst = task1;
502: snd = task2;
503: }
504:
505: public void run() {
506: FJTask.invoke(fst);
507: FJTask.invoke(snd);
508: }
509: }
510:
511: /**
512: * Construct and return a FJTask object that, when executed, will
513: * invoke task1 and task2, in order
514: **/
515:
516: public static FJTask seq(FJTask task1, FJTask task2) {
517: return new Seq2(task1, task2);
518: }
519:
520: /**
521: * A <code>new Par(task1, task2)</code>, when executed,
522: * runs task1 and task2 in parallel using coInvoke(task1, task2).
523: * The class is a simple utility
524: * that makes it easier to create composite Tasks.
525: **/
526: public static class Par2 extends FJTask {
527: protected final FJTask fst;
528: protected final FJTask snd;
529:
530: public Par2(FJTask task1, FJTask task2) {
531: fst = task1;
532: snd = task2;
533: }
534:
535: public void run() {
536: FJTask.coInvoke(fst, snd);
537: }
538: }
539:
540: /**
541: * Construct and return a FJTask object that, when executed, will
542: * invoke task1 and task2, in parallel
543: **/
544: public static FJTask par(FJTask task1, FJTask task2) {
545: return new Par2(task1, task2);
546: }
547:
548: }
|