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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags