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 org.logicalcobwebs.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() {
177         return done;
178     }
179 
180     /**
181      * Indicate termination. Intended only to be called by FJTaskRunner.
182      * FJTasks themselves should use (non-final) method
183      * cancel() to suppress execution.
184      **/
185 
186     protected final void setDone() {
187         done = true;
188     }
189 
190     /**
191      * Set the termination status of this task. This simple-minded
192      * analog of Thread.interrupt
193      * causes the task not to execute if it has not already been started.
194      * Cancelling a running FJTask
195      * has no effect unless the run method itself uses isDone()
196      * to probe cancellation and take appropriate action.
197      * Individual run() methods may sense status and
198      * act accordingly, normally by returning early.
199      **/
200 
201     public void cancel() {
202         setDone();
203     }
204 
205 
206     /**
207      * Clear the termination status of this task.
208      * This method is intended to be used
209      * only as a means to allow task objects to be recycled. It should
210      * be called only when you are sure that the previous
211      * execution of this task has terminated and, if applicable, has
212      * been joined by all other waiting tasks. Usage in any other
213      * context is a very bad idea.
214      **/
215 
216     public void reset() {
217         done = false;
218     }
219 
220 
221     /**
222      * Execute this task. This method merely places the task in a
223      * group-wide scheduling queue.
224      * It will be run
225      * the next time any TaskRunner thread is otherwise idle.
226      * This scheduling  maintains FIFO ordering of started tasks
227      * with respect to
228      * the group of worker threads.
229      * @exception ClassCastException if caller thread is not
230      * running in a FJTaskRunner thread.
231      **/
232 
233     public void start() {
234         getFJTaskRunnerGroup().executeTask(this);
235     }
236 
237 
238     /**
239      * Arrange for execution of a strictly dependent task.
240      * The task that will be executed in
241      * procedure-call-like LIFO order if executed by the
242      * same worker thread, but is FIFO with respect to other tasks
243      * forked by this thread when taken by other worker threads.
244      * That is, earlier-forked
245      * tasks are preferred to later-forked tasks by other idle workers.
246      * <p>
247      * Fork() is noticeably
248      * faster than start(). However, it may only
249      * be used for strictly dependent tasks -- generally, those that
250      * could logically be issued as straight method calls without
251      * changing the logic of the program.
252      * The method is optimized for use in parallel fork/join designs
253      * in which the thread that issues one or more forks
254      * cannot continue until at least some of the forked
255      * threads terminate and are joined.
256      * @exception ClassCastException if caller thread is not
257      * running in a FJTaskRunner thread.
258      **/
259 
260     public void fork() {
261         getFJTaskRunner().push(this);
262     }
263 
264     /**
265      * Allow the current underlying FJTaskRunner thread to process other tasks.
266      * <p>
267      * Spinloops based on yield() are well behaved so long
268      * as the event or condition being waited for is produced via another
269      * FJTask. Additionally, you must never hold a lock
270      * while performing a yield or join. (This is because
271      * multiple FJTasks can be run by the same Thread during
272      * a yield. Since java locks are held per-thread, the lock would not
273      * maintain the conceptual exclusion you have in mind.)
274      * <p>
275      * Otherwise, spinloops using
276      * yield are the main construction of choice when a task must wait
277      * for a condition that it is sure will eventually occur because it
278      * is being produced by some other FJTask.  The most common
279      * such condition is built-in: join() repeatedly yields until a task
280      * has terminated after producing some needed results. You can also
281      * use yield to wait for callbacks from other FJTasks, to wait for
282      * status flags to be set, and so on. However, in all these cases,
283      * you should be confident that the condition being waited for will
284      * occur, essentially always because it is produced by
285      * a FJTask generated by the current task, or one of its subtasks.
286      *
287      * @exception ClassCastException if caller thread is not
288      * running in a FJTaskRunner thread.
289      **/
290 
291     public static void yield() {
292         getFJTaskRunner().taskYield();
293     }
294 
295     /**
296      * Yield until this task isDone.
297      * Equivalent to <code>while(!isDone()) yield(); </code>
298      * @exception ClassCastException if caller thread is not
299      * running in a FJTaskRunner thread.
300      **/
301 
302     public void join() {
303         getFJTaskRunner().taskJoin(this);
304     }
305 
306     /**
307      * Immediately execute task t by calling its run method. Has no
308      * effect if t has already been run or has been cancelled.
309      * It is equivalent to  calling t.run except that it
310      * deals with completion status, so should always be used
311      * instead of directly calling run.
312      * The method can be useful
313      * when a computation has been packaged as a FJTask, but you just need to
314      * directly execute its body from within some other task.
315      **/
316 
317     public static void invoke(FJTask t) {
318         if (!t.isDone()) {
319             t.run();
320             t.setDone();
321         }
322     }
323 
324     /**
325      * Fork both tasks and then wait for their completion. It behaves as:
326      * <pre>
327      * task1.fork(); task2.fork(); task2.join(); task1.join();
328      * </pre>
329      * As a simple classic example, here is
330      * a class that computes the Fibonacci function:
331      * <pre>
332      * public class Fib extends FJTask {
333      *
334      *  // Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);  for n> 1
335      *  //          fibonacci(0) = 0;
336      *  //          fibonacci(1) = 1.
337      *
338      *  // Value to compute fibonacci function for.
339      *  // It is replaced with the answer when computed.
340      *  private volatile int number;
341      *
342      *  public Fib(int n) { number = n; }
343      *
344      *  public int getAnswer() {
345      *    if (!isDone()) throw new Error("Not yet computed");
346      *    return number;
347      *  }
348      *
349      *  public void run() {
350      *    int n = number;
351      *    if (n > 1) {
352      *      Fib f1 = new Fib(n - 1);
353      *      Fib f2 = new Fib(n - 2);
354      *
355      *      coInvoke(f1, f2); // run these in parallel
356      *
357      *      // we know f1 and f2 are computed, so just directly access numbers
358      *      number = f1.number + f2.number;
359      *    }
360      *  }
361      *
362      *  public static void main(String[] args) { // sample driver
363      *    try {
364      *      int groupSize = 2;    // 2 worker threads
365      *      int num = 35;         // compute fib(35)
366      *      FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
367      *      Fib f = new Fib(num);
368      *      group.invoke(f);
369      *      int result = f.getAnswer();
370      *      System.out.println(" Answer: " + result);
371      *    }
372      *    catch (InterruptedException ex) {
373      *      System.out.println("Interrupted");
374      *    }
375      *  }
376      * }
377      * </pre>
378      *
379      * @exception ClassCastException if caller thread is not
380      * running in a FJTaskRunner thread.
381      **/
382 
383     public static void coInvoke(FJTask task1, FJTask task2) {
384         getFJTaskRunner().coInvoke(task1, task2);
385     }
386 
387 
388     /**
389      * Fork all tasks in array, and await their completion.
390      * Behaviorally equivalent to:
391      * <pre>
392      * for (int i = 0; i &lt; tasks.length; ++i) tasks[i].fork();
393      * for (int i = 0; i &lt; tasks.length; ++i) tasks[i].join();
394      * </pre>
395      **/
396 
397     public static void coInvoke(FJTask[] tasks) {
398         getFJTaskRunner().coInvoke(tasks);
399     }
400 
401     /**
402      * A FJTask that holds a Runnable r, and calls r.run when executed.
403      * The class is a simple utilty to allow arbitrary Runnables
404      * to be used as FJTasks.
405      **/
406 
407     public static class Wrap extends FJTask {
408         protected final Runnable   runnable;
409 
410         public Wrap(Runnable   r) {
411             runnable = r;
412         }
413 
414         public void run() {
415             runnable.run();
416         }
417     }
418 
419 
420     /**
421      * A  <code>new Seq</code>, when executed,
422      * invokes each task provided in the constructor,  in order.
423      * The class is a simple utility
424      * that makes it easier to create composite FJTasks.
425      **/
426     public static class Seq extends FJTask {
427         protected final FJTask[] tasks;
428 
429         /**
430          * Construct a Seq that, when executed, will process each of the
431          * tasks in the tasks array in order
432          **/
433         public Seq(FJTask[] tasks) {
434             this.tasks = tasks;
435         }
436 
437         /**
438          * Two-task constructor, for compatibility with previous release.
439          **/
440         public Seq(FJTask task1, FJTask task2) {
441             this.tasks = new FJTask[]{task1, task2};
442         }
443 
444         public void run() {
445             for (int i = 0; i < tasks.length; ++i) FJTask.invoke(tasks[i]);
446         }
447     }
448 
449     /**
450      * Construct and return a FJTask object that, when executed, will
451      * invoke the tasks in the tasks array in array order
452      **/
453 
454     public static FJTask seq(FJTask[] tasks) {
455         return new Seq(tasks);
456     }
457 
458     /**
459      * A <code>new Par</code>, when executed,
460      * runs the tasks provided in the constructor in parallel using
461      * coInvoke(tasks).
462      * The class is a simple utility
463      * that makes it easier to create composite FJTasks.
464      **/
465     public static class Par extends FJTask {
466         protected final FJTask[] tasks;
467 
468         /**
469          * Construct a Seq that, when executed, will process each of the
470          * tasks in the tasks array in parallel
471          **/
472         public Par(FJTask[] tasks) {
473             this.tasks = tasks;
474         }
475 
476         /**
477          * Two-task constructor, for compatibility with previous release.
478          **/
479         public Par(FJTask task1, FJTask task2) {
480             this.tasks = new FJTask[]{task1, task2};
481         }
482 
483 
484         public void run() {
485             FJTask.coInvoke(tasks);
486         }
487     }
488 
489 
490     /**
491      * Construct and return a FJTask object that, when executed, will
492      * invoke the tasks in the tasks array in parallel using coInvoke
493      **/
494     public static FJTask par(FJTask[] tasks) {
495         return new Par(tasks);
496     }
497 
498     /**
499      * A  <code>new Seq2(task1, task2)</code>, when executed,
500      * invokes task1 and then task2, in order.
501      * The class is a simple utility
502      * that makes it easier to create composite Tasks.
503      **/
504     public static class Seq2 extends FJTask {
505         protected final FJTask fst;
506         protected final FJTask snd;
507 
508         public Seq2(FJTask task1, FJTask task2) {
509             fst = task1;
510             snd = task2;
511         }
512 
513         public void run() {
514             FJTask.invoke(fst);
515             FJTask.invoke(snd);
516         }
517     }
518 
519     /**
520      * Construct and return a FJTask object that, when executed, will
521      * invoke task1 and task2, in order
522      **/
523 
524     public static FJTask seq(FJTask task1, FJTask task2) {
525         return new Seq2(task1, task2);
526     }
527 
528     /**
529      * A <code>new Par(task1, task2)</code>, when executed,
530      * runs task1 and task2 in parallel using coInvoke(task1, task2).
531      * The class is a simple utility
532      * that makes it easier to create composite Tasks.
533      **/
534     public static class Par2 extends FJTask {
535         protected final FJTask fst;
536         protected final FJTask snd;
537 
538         public Par2(FJTask task1, FJTask task2) {
539             fst = task1;
540             snd = task2;
541         }
542 
543         public void run() {
544             FJTask.coInvoke(fst, snd);
545         }
546     }
547 
548 
549     /**
550      * Construct and return a FJTask object that, when executed, will
551      * invoke task1 and task2, in parallel
552      **/
553     public static FJTask par(FJTask task1, FJTask task2) {
554         return new Par2(task1, task2);
555     }
556 
557 }
558
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags