Mercurial > hg > blitz_condensed
comparison 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 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
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 < tasks.length; ++i) tasks[i].fork(); | |
377 * for (int i = 0; i < 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 } |