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


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