1 |
/* |
2 |
* %W% %E% |
3 |
* |
4 |
* Copyright 2004 Sun Microsystems, Inc. All rights reserved. |
5 |
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
6 |
*/ |
7 |
|
8 |
package java.util; |
9 |
import java.util.concurrent.atomic.AtomicInteger; |
10 |
|
11 |
/** |
12 |
* A facility for threads to schedule tasks for future execution in a |
13 |
* background thread. Tasks may be scheduled for one-time execution, or for |
14 |
* repeated execution at regular intervals. |
15 |
* |
16 |
* <p>Corresponding to each <tt>Timer</tt> object is a single background |
17 |
* thread that is used to execute all of the timer's tasks, sequentially. |
18 |
* Timer tasks should complete quickly. If a timer task takes excessive time |
19 |
* to complete, it "hogs" the timer's task execution thread. This can, in |
20 |
* turn, delay the execution of subsequent tasks, which may "bunch up" and |
21 |
* execute in rapid succession when (and if) the offending task finally |
22 |
* completes. |
23 |
* |
24 |
* <p>After the last live reference to a <tt>Timer</tt> object goes away |
25 |
* <i>and</i> all outstanding tasks have completed execution, the timer's task |
26 |
* execution thread terminates gracefully (and becomes subject to garbage |
27 |
* collection). However, this can take arbitrarily long to occur. By |
28 |
* default, the task execution thread does not run as a <i>daemon thread</i>, |
29 |
* so it is capable of keeping an application from terminating. If a caller |
30 |
* wants to terminate a timer's task execution thread rapidly, the caller |
31 |
* should invoke the the timer's <tt>cancel</tt> method. |
32 |
* |
33 |
* <p>If the timer's task execution thread terminates unexpectedly, for |
34 |
* example, because its <tt>stop</tt> method is invoked, any further |
35 |
* attempt to schedule a task on the timer will result in an |
36 |
* <tt>IllegalStateException</tt>, as if the timer's <tt>cancel</tt> |
37 |
* method had been invoked. |
38 |
* |
39 |
* <p>This class is thread-safe: multiple threads can share a single |
40 |
* <tt>Timer</tt> object without the need for external synchronization. |
41 |
* |
42 |
* <p>This class does <i>not</i> offer real-time guarantees: it schedules |
43 |
* tasks using a timed version of the <tt>Object.wait()</tt> method. |
44 |
* |
45 |
* <p>Time values passed to the various <tt>schedule</tt> methods are subject |
46 |
* to certain limitations (none of which should represent a practical problem). |
47 |
* All relative time values (execution periods and delays) must be less than |
48 |
* 2<sup>42</sup> ms (approximately 140 years). Absolute execution times |
49 |
* must be within 2<sup>42</sup> ms of the time this class was initialized. |
50 |
* |
51 |
* <p>Implementation note: This class scales to large numbers of concurrently |
52 |
* scheduled tasks (thousands should present no problem). Internally, |
53 |
* it uses a binary heap to represent its task queue, so the cost to schedule |
54 |
* a task is O(log n), where n is the number of concurrently scheduled tasks. |
55 |
* |
56 |
* @author Josh Bloch |
57 |
* @version %I%, %G% |
58 |
* @see TimerTask |
59 |
* @see Object#wait(long) |
60 |
* @since 1.3 |
61 |
*/ |
62 |
|
63 |
public class Timer { |
64 |
|
65 |
/** |
66 |
* The timer task queue. This data structure is shared with the timer |
67 |
* thread. The timer produces tasks, via its various schedule calls, |
68 |
* and the timer thread consumes, executing timer tasks as appropriate, |
69 |
* and removing them from the queue when they're obsolete. |
70 |
*/ |
71 |
private TaskQueue queue = new TaskQueue(); |
72 |
|
73 |
/** |
74 |
* The timer thread. |
75 |
*/ |
76 |
private TimerThread thread = new TimerThread(queue); |
77 |
|
78 |
/** |
79 |
* This object causes the timer's task execution thread to exit |
80 |
* gracefully when there are no live references to the Timer object and no |
81 |
* tasks in the timer queue. It is used in preference to a finalizer on |
82 |
* Timer as such a finalizer would be susceptible to a subclass's |
83 |
* finalizer forgetting to call it. |
84 |
*/ |
85 |
private Object threadReaper = new Object() { |
86 |
protected void finalize() throws Throwable { |
87 |
synchronized(queue) { |
88 |
thread.newTasksMayBeScheduled = false; |
89 |
queue.notify(); // In case queue is empty. |
90 |
} |
91 |
} |
92 |
}; |
93 |
|
94 |
/** |
95 |
* This ID is used to generate thread names. |
96 |
*/ |
97 |
private static AtomicInteger nextSerialNumber = new AtomicInteger(0); |
98 |
private static int serialNumber() { |
99 |
return nextSerialNumber.getAndIncrement(); |
100 |
} |
101 |
|
102 |
/* |
103 |
* This class has been converted as of J2SE 1.5 to use nanosecond |
104 |
* timing resolution internally, while keeping the original |
105 |
* millisecond-based API. The following constants and functions |
106 |
* perform conversions to and from external millisecond to |
107 |
* internal nanosecond times. |
108 |
*/ |
109 |
|
110 |
static final int NANOS_PER_MILLI = 1000000; |
111 |
|
112 |
/** Scale a millisecond value to nanosecond units */ |
113 |
static long millisToNanos(long millis) { |
114 |
return millis * NANOS_PER_MILLI; |
115 |
} |
116 |
|
117 |
/** Scale a nanosecond value to millisecond units */ |
118 |
static long nanosToMillis(long nanos) { |
119 |
return nanos / NANOS_PER_MILLI; |
120 |
} |
121 |
|
122 |
/** |
123 |
* Bound on period values, delay values, and absolute times. |
124 |
*/ |
125 |
private static final long TIME_BOUND_MILLIS = 1L << 42; |
126 |
|
127 |
|
128 |
/** |
129 |
* Lower bound on legal times in Date.getTime() format. |
130 |
*/ |
131 |
private static final long MIN_MILLIS; |
132 |
|
133 |
/** |
134 |
* Upper bound on legal times in Date.getTime() format. |
135 |
*/ |
136 |
private static final long MAX_MILLIS; |
137 |
|
138 |
|
139 |
/** Origin for nanosecond times */ |
140 |
private static final long ORIGIN_NANOS; |
141 |
|
142 |
/* We need to find a common base for millis and nanos in order to |
143 |
* convert absolute time readings. So we perform initial readings |
144 |
* to find suitable origins. To improve accuracy, we sandwich a |
145 |
* millisecond reading around two nanosecond readings, and use |
146 |
* their average as matching time. |
147 |
*/ |
148 |
static { |
149 |
long nanos1 = System.nanoTime(); |
150 |
long millis = System.currentTimeMillis(); |
151 |
ORIGIN_NANOS = nanos1 + (System.nanoTime() - nanos1) / 2; |
152 |
MIN_MILLIS = millis - TIME_BOUND_MILLIS; |
153 |
MAX_MILLIS = millis + TIME_BOUND_MILLIS; |
154 |
} |
155 |
|
156 |
/** |
157 |
* Return nanosecond time relative to ORIGIN_NANOS |
158 |
*/ |
159 |
static long currentTimeNanos() { |
160 |
return System.nanoTime() - ORIGIN_NANOS; |
161 |
} |
162 |
|
163 |
/** |
164 |
* Convert absolute time represented as a date into internal |
165 |
* nanosecond-based format |
166 |
*/ |
167 |
static long dateToExecutionTime(Date time) { |
168 |
long cm = System.currentTimeMillis(); |
169 |
long cn = System.nanoTime(); |
170 |
long md = time.getTime() - cm; |
171 |
return cn - ORIGIN_NANOS + millisToNanos(md); |
172 |
} |
173 |
|
174 |
/** |
175 |
* Convert absolute time of internal form into the form used by |
176 |
* currentTimeMillis. |
177 |
*/ |
178 |
static long executionTimeToMillis(long x) { |
179 |
long cn = System.nanoTime(); |
180 |
long cm = System.currentTimeMillis(); |
181 |
long nd = cn - ORIGIN_NANOS - x; |
182 |
long round = (nd < 0)? -500000 : 500000; |
183 |
long md = nanosToMillis(nd + round); |
184 |
return cm - md; |
185 |
} |
186 |
|
187 |
/** |
188 |
* Convenience method to perform a monitor wait for the given |
189 |
* nanoseconds |
190 |
*/ |
191 |
static void waitNanos(Object x, long nanos) throws InterruptedException { |
192 |
x.wait( nanos / NANOS_PER_MILLI, |
193 |
(int) (nanos % NANOS_PER_MILLI)); |
194 |
} |
195 |
|
196 |
|
197 |
/** |
198 |
* Creates a new timer. The associated thread does <i>not</i> run as |
199 |
* a daemon. |
200 |
* |
201 |
* @see Thread |
202 |
* @see #cancel() |
203 |
*/ |
204 |
public Timer() { |
205 |
this("Timer-" + serialNumber()); |
206 |
} |
207 |
|
208 |
/** |
209 |
* Creates a new timer whose associated thread may be specified to |
210 |
* run as a daemon. A daemon thread is called for if the timer will |
211 |
* be used to schedule repeating "maintenance activities", which must |
212 |
* be performed as long as the application is running, but should not |
213 |
* prolong the lifetime of the application. |
214 |
* |
215 |
* @param isDaemon true if the associated thread should run as a daemon. |
216 |
* |
217 |
* @see Thread |
218 |
* @see #cancel() |
219 |
*/ |
220 |
public Timer(boolean isDaemon) { |
221 |
this("Timer-" + serialNumber(), isDaemon); |
222 |
} |
223 |
|
224 |
/** |
225 |
* Creates a new timer whose associated thread has the specified name. |
226 |
* The associated thread does <i>not</i> run as a daemon. |
227 |
* |
228 |
* @param name the name of the associated thread |
229 |
* @throws NullPointerException if name is null |
230 |
* @see Thread#getName() |
231 |
* @see Thread#isDaemon() |
232 |
* @since 1.5 |
233 |
*/ |
234 |
public Timer(String name) { |
235 |
thread.setName(name); |
236 |
thread.start(); |
237 |
} |
238 |
|
239 |
/** |
240 |
* Creates a new timer whose associated thread has the specified name, |
241 |
* and may be specified to run as a daemon. |
242 |
* |
243 |
* @param name the name of the associated thread |
244 |
* @param isDaemon true if the associated thread should run as a daemon |
245 |
* @throws NullPointerException if name is null |
246 |
* @see Thread#getName() |
247 |
* @see Thread#isDaemon() |
248 |
* @since 1.5 |
249 |
*/ |
250 |
public Timer(String name, boolean isDaemon) { |
251 |
thread.setName(name); |
252 |
thread.setDaemon(isDaemon); |
253 |
thread.start(); |
254 |
} |
255 |
|
256 |
/** |
257 |
* Schedules the specified task for execution after the specified delay. |
258 |
* |
259 |
* @param task task to be scheduled. |
260 |
* @param delay delay in milliseconds before task is to be executed. |
261 |
* @throws IllegalArgumentException if <tt>delay</tt> is negative or is |
262 |
* greater than or equal to 2<sup>42</sup> (approximately 140 years). |
263 |
* @throws IllegalStateException if task was already scheduled or |
264 |
* cancelled, or timer was cancelled. |
265 |
*/ |
266 |
public void schedule(TimerTask task, long delay) { |
267 |
if (delay < 0 || delay >= TIME_BOUND_MILLIS) |
268 |
throw new IllegalArgumentException("Delay out of range: " + delay); |
269 |
sched(task, currentTimeNanos() + millisToNanos(delay), 0); |
270 |
} |
271 |
|
272 |
/** |
273 |
* Schedules the specified task for execution at the specified time. If |
274 |
* the time is in the past, the task is scheduled for immediate execution. |
275 |
* |
276 |
* @param task task to be scheduled. |
277 |
* @param time time at which task is to be executed. |
278 |
* @throws IllegalArgumentException if <tt>time</tt> is not within |
279 |
* 2<sup>42</sup> ms (approximately 140 years) of the time this |
280 |
* class was initialized. |
281 |
* @throws IllegalStateException if task was already scheduled or |
282 |
* cancelled, timer was cancelled, or timer thread terminated. |
283 |
*/ |
284 |
public void schedule(TimerTask task, Date time) { |
285 |
long millis = time.getTime(); |
286 |
if (millis <= MIN_MILLIS || millis >= MAX_MILLIS) |
287 |
throw new IllegalArgumentException("Time out of range: " + time); |
288 |
sched(task, dateToExecutionTime(time), 0); |
289 |
} |
290 |
|
291 |
/** |
292 |
* Schedules the specified task for repeated <i>fixed-delay execution</i>, |
293 |
* beginning after the specified delay. Subsequent executions take place |
294 |
* at approximately regular intervals separated by the specified period. |
295 |
* |
296 |
* <p>In fixed-delay execution, each execution is scheduled relative to |
297 |
* the actual execution time of the previous execution. If an execution |
298 |
* is delayed for any reason (such as garbage collection or other |
299 |
* background activity), subsequent executions will be delayed as well. |
300 |
* In the long run, the frequency of execution will generally be slightly |
301 |
* lower than the reciprocal of the specified period (assuming the system |
302 |
* clock underlying <tt>Object.wait(long)</tt> is accurate). |
303 |
* |
304 |
* <p>Fixed-delay execution is appropriate for recurring activities |
305 |
* that require "smoothness." In other words, it is appropriate for |
306 |
* activities where it is more important to keep the frequency accurate |
307 |
* in the short run than in the long run. This includes most animation |
308 |
* tasks, such as blinking a cursor at regular intervals. It also includes |
309 |
* tasks wherein regular activity is performed in response to human |
310 |
* input, such as automatically repeating a character as long as a key |
311 |
* is held down. |
312 |
* |
313 |
* @param task task to be scheduled. |
314 |
* @param delay delay in milliseconds before task is to be executed. |
315 |
* @param period time in milliseconds between successive task executions. |
316 |
* @throws IllegalArgumentException if <tt>delay</tt> is negative or is |
317 |
* greater than or equal to 2<sup>42</sup> (approximately 140 years). |
318 |
* @throws IllegalArgumentException if <tt>period</tt> is non-positive |
319 |
* or is greater than or equal to 2<sup>42</sup>. |
320 |
* @throws IllegalStateException if task was already scheduled or |
321 |
* cancelled, timer was cancelled, or timer thread terminated. |
322 |
*/ |
323 |
public void schedule(TimerTask task, long delay, long period) { |
324 |
if (delay < 0 || delay >= TIME_BOUND_MILLIS) |
325 |
throw new IllegalArgumentException("Delay out of range: " + delay); |
326 |
if (period <= 0 || period >= TIME_BOUND_MILLIS) |
327 |
throw new IllegalArgumentException("Period out of range: "+period); |
328 |
sched(task, |
329 |
currentTimeNanos() + millisToNanos(delay), |
330 |
millisToNanos(-period)); |
331 |
} |
332 |
|
333 |
/** |
334 |
* Schedules the specified task for repeated <i>fixed-delay execution</i>, |
335 |
* beginning at the specified time. Subsequent executions take place at |
336 |
* approximately regular intervals, separated by the specified period. |
337 |
* |
338 |
* <p>In fixed-delay execution, each execution is scheduled relative to |
339 |
* the actual execution time of the previous execution. If an execution |
340 |
* is delayed for any reason (such as garbage collection or other |
341 |
* background activity), subsequent executions will be delayed as well. |
342 |
* In the long run, the frequency of execution will generally be slightly |
343 |
* lower than the reciprocal of the specified period (assuming the system |
344 |
* clock underlying <tt>Object.wait(long)</tt> is accurate). |
345 |
* |
346 |
* <p>Fixed-delay execution is appropriate for recurring activities |
347 |
* that require "smoothness." In other words, it is appropriate for |
348 |
* activities where it is more important to keep the frequency accurate |
349 |
* in the short run than in the long run. This includes most animation |
350 |
* tasks, such as blinking a cursor at regular intervals. It also includes |
351 |
* tasks wherein regular activity is performed in response to human |
352 |
* input, such as automatically repeating a character as long as a key |
353 |
* is held down. |
354 |
* |
355 |
* @param task task to be scheduled. |
356 |
* @param firstTime First time at which task is to be executed. |
357 |
* @param period time in milliseconds between successive task executions. |
358 |
* @throws IllegalArgumentException if <tt>firstTime</tt> is not within |
359 |
* 2<sup>42</sup> ms (approximately 140 years) of the time this |
360 |
* class was initialized. |
361 |
* @throws IllegalArgumentException if <tt>period</tt> is non-positive |
362 |
* or is greater than or equal to 2<sup>42</sup>. |
363 |
* @throws IllegalStateException if task was already scheduled or |
364 |
* cancelled, timer was cancelled, or timer thread terminated. |
365 |
*/ |
366 |
public void schedule(TimerTask task, Date firstTime, long period) { |
367 |
long millis = firstTime.getTime(); |
368 |
if (millis <= MIN_MILLIS || millis >= MAX_MILLIS) |
369 |
throw new IllegalArgumentException("Time out of range: " + millis); |
370 |
if (period <= 0 || period >= TIME_BOUND_MILLIS) |
371 |
throw new IllegalArgumentException("Period out of range: "+period); |
372 |
sched(task, |
373 |
dateToExecutionTime(firstTime), |
374 |
millisToNanos(-period)); |
375 |
} |
376 |
|
377 |
/** |
378 |
* Schedules the specified task for repeated <i>fixed-rate execution</i>, |
379 |
* beginning after the specified delay. Subsequent executions take place |
380 |
* at approximately regular intervals, separated by the specified period. |
381 |
* |
382 |
* <p>In fixed-rate execution, each execution is scheduled relative to the |
383 |
* scheduled execution time of the initial execution. If an execution is |
384 |
* delayed for any reason (such as garbage collection or other background |
385 |
* activity), two or more executions will occur in rapid succession to |
386 |
* "catch up." In the long run, the frequency of execution will be |
387 |
* exactly the reciprocal of the specified period (assuming the system |
388 |
* clock underlying <tt>Object.wait(long)</tt> is accurate). |
389 |
* |
390 |
* <p>Fixed-rate execution is appropriate for recurring activities that |
391 |
* are sensitive to <i>absolute</i> time, such as ringing a chime every |
392 |
* hour on the hour, or running scheduled maintenance every day at a |
393 |
* particular time. It is also appropriate for for recurring activities |
394 |
* where the total time to perform a fixed number of executions is |
395 |
* important, such as a countdown timer that ticks once every second for |
396 |
* ten seconds. Finally, fixed-rate execution is appropriate for |
397 |
* scheduling multiple repeating timer tasks that must remain synchronized |
398 |
* with respect to one another. |
399 |
* |
400 |
* @param task task to be scheduled. |
401 |
* @param delay delay in milliseconds before task is to be executed. |
402 |
* @param period time in milliseconds between successive task executions. |
403 |
* @throws IllegalArgumentException if <tt>delay</tt> is negative or is |
404 |
* greater than or equal to 2<sup>42</sup> (approximately 140 years). |
405 |
* @throws IllegalArgumentException if <tt>period</tt> is non-positive |
406 |
* or is greater than or equal to 2<sup>42</sup>. |
407 |
* @throws IllegalStateException if task was already scheduled or |
408 |
* cancelled, timer was cancelled, or timer thread terminated. |
409 |
*/ |
410 |
public void scheduleAtFixedRate(TimerTask task, long delay, long period) { |
411 |
if (delay < 0 || delay >= TIME_BOUND_MILLIS) |
412 |
throw new IllegalArgumentException("Delay out of range: " + delay); |
413 |
if (period <= 0 || period >= TIME_BOUND_MILLIS) |
414 |
throw new IllegalArgumentException("Period out of range: "+period); |
415 |
sched(task, |
416 |
currentTimeNanos() + millisToNanos(delay), |
417 |
millisToNanos(period)); |
418 |
} |
419 |
|
420 |
/** |
421 |
* Schedules the specified task for repeated <i>fixed-rate execution</i>, |
422 |
* beginning at the specified time. Subsequent executions take place at |
423 |
* approximately regular intervals, separated by the specified period. |
424 |
* |
425 |
* <p>In fixed-rate execution, each execution is scheduled relative to the |
426 |
* scheduled execution time of the initial execution. If an execution is |
427 |
* delayed for any reason (such as garbage collection or other background |
428 |
* activity), two or more executions will occur in rapid succession to |
429 |
* "catch up." In the long run, the frequency of execution will be |
430 |
* exactly the reciprocal of the specified period (assuming the system |
431 |
* clock underlying <tt>Object.wait(long)</tt> is accurate). |
432 |
* |
433 |
* <p>Fixed-rate execution is appropriate for recurring activities that |
434 |
* are sensitive to <i>absolute</i> time, such as ringing a chime every |
435 |
* hour on the hour, or running scheduled maintenance every day at a |
436 |
* particular time. It is also appropriate for for recurring activities |
437 |
* where the total time to perform a fixed number of executions is |
438 |
* important, such as a countdown timer that ticks once every second for |
439 |
* ten seconds. Finally, fixed-rate execution is appropriate for |
440 |
* scheduling multiple repeating timer tasks that must remain synchronized |
441 |
* with respect to one another. |
442 |
* |
443 |
* @param task task to be scheduled. |
444 |
* @param firstTime First time at which task is to be executed. |
445 |
* @param period time in milliseconds between successive task executions. |
446 |
* @throws IllegalArgumentException if <tt>firstTime</tt> is not within |
447 |
* 2<sup>42</sup> ms (approximately 140 years) of the time this |
448 |
* class was initialized. |
449 |
* @throws IllegalArgumentException if <tt>period</tt> is non-positive |
450 |
* or is greater than or equal to 2<sup>42</sup>. |
451 |
* @throws IllegalStateException if task was already scheduled or |
452 |
* cancelled, timer was cancelled, or timer thread terminated. |
453 |
*/ |
454 |
public void scheduleAtFixedRate(TimerTask task, Date firstTime, |
455 |
long period) { |
456 |
long millis = firstTime.getTime(); |
457 |
if (millis <= MIN_MILLIS || millis >= MAX_MILLIS) |
458 |
throw new IllegalArgumentException("Time out of range: " + millis); |
459 |
if (period <= 0) |
460 |
throw new IllegalArgumentException("Non-positive period."); |
461 |
sched(task, |
462 |
dateToExecutionTime(firstTime), |
463 |
millisToNanos(period)); |
464 |
} |
465 |
|
466 |
/** |
467 |
* Schedule the specified timer task for execution at the specified |
468 |
* time with the specified period, in milliseconds. If period is |
469 |
* positive, the task is scheduled for repeated execution; if period is |
470 |
* zero, the task is scheduled for one-time execution. Time is specified |
471 |
* in Date.getTime() format. This method checks timer state and task |
472 |
* state, but not initial execution time or period. |
473 |
* |
474 |
* @throws IllegalStateException if task was already scheduled or |
475 |
* cancelled, timer was cancelled, or timer thread terminated. |
476 |
*/ |
477 |
private void sched(TimerTask task, long time, long period) { |
478 |
synchronized(queue) { |
479 |
if (!thread.newTasksMayBeScheduled) |
480 |
throw new IllegalStateException("Timer already cancelled."); |
481 |
|
482 |
synchronized(task.lock) { |
483 |
if (task.state != TimerTask.VIRGIN) |
484 |
throw new IllegalStateException( |
485 |
"Task already scheduled or cancelled"); |
486 |
task.nextExecutionTime = time; |
487 |
task.period = period; |
488 |
task.state = TimerTask.SCHEDULED; |
489 |
} |
490 |
|
491 |
queue.add(task); |
492 |
if (queue.getMin() == task) |
493 |
queue.notify(); |
494 |
} |
495 |
} |
496 |
|
497 |
/** |
498 |
* Terminates this timer, discarding any currently scheduled tasks. |
499 |
* Does not interfere with a currently executing task (if it exists). |
500 |
* Once a timer has been terminated, its execution thread terminates |
501 |
* gracefully, and no more tasks may be scheduled on it. |
502 |
* |
503 |
* <p>Note that calling this method from within the run method of a |
504 |
* timer task that was invoked by this timer absolutely guarantees that |
505 |
* the ongoing task execution is the last task execution that will ever |
506 |
* be performed by this timer. |
507 |
* |
508 |
* <p>This method may be called repeatedly; the second and subsequent |
509 |
* calls have no effect. |
510 |
*/ |
511 |
public void cancel() { |
512 |
synchronized(queue) { |
513 |
thread.newTasksMayBeScheduled = false; |
514 |
queue.clear(); |
515 |
queue.notify(); // In case queue was already empty. |
516 |
} |
517 |
} |
518 |
|
519 |
/** |
520 |
* Removes all cancelled tasks from this timer's task queue. <i>Calling |
521 |
* this method has no effect on the behavior of the timer</i>, but |
522 |
* eliminates the references to the cancelled tasks from the queue. |
523 |
* If there are no external references to these tasks, they become |
524 |
* eligible for garbage collection. |
525 |
* |
526 |
* <p>Most programs will have no need to call this method. |
527 |
* It is designed for use by the rare application that cancels a large |
528 |
* number of of tasks. Calling this method trades time for space: the |
529 |
* runtime of the method may be proportional to n + c log n, where n |
530 |
* is the number of tasks in the queue and c is the number of cancelled |
531 |
* tasks. |
532 |
* |
533 |
* <p>Note that it is permissible to call this method from within a |
534 |
* a task scheduled on this timer. |
535 |
* |
536 |
* @return the number of tasks removed from the queue. |
537 |
* @since 1.5 |
538 |
*/ |
539 |
public int purge() { |
540 |
int result = 0; |
541 |
|
542 |
synchronized(queue) { |
543 |
for (int i = queue.size(); i > 0; i--) { |
544 |
if (queue.get(i).state == TimerTask.CANCELLED) { |
545 |
queue.quickRemove(i); |
546 |
result++; |
547 |
} |
548 |
} |
549 |
|
550 |
if (result != 0) |
551 |
queue.heapify(); |
552 |
} |
553 |
|
554 |
return result; |
555 |
} |
556 |
} |
557 |
|
558 |
/** |
559 |
* This "helper class" implements the timer's task execution thread, which |
560 |
* waits for tasks on the timer queue, executions them when they fire, |
561 |
* reschedules repeating tasks, and removes cancelled tasks and spent |
562 |
* non-repeating tasks from the queue. |
563 |
*/ |
564 |
class TimerThread extends Thread { |
565 |
/** |
566 |
* This flag is set to false by the reaper to inform us that there |
567 |
* are no more live references to our Timer object. Once this flag |
568 |
* is true and there are no more tasks in our queue, there is no |
569 |
* work left for us to do, so we terminate gracefully. Note that |
570 |
* this field is protected by queue's monitor! |
571 |
*/ |
572 |
boolean newTasksMayBeScheduled = true; |
573 |
|
574 |
/** |
575 |
* Our Timer's queue. We store this reference in preference to |
576 |
* a reference to the Timer so the reference graph remains acyclic. |
577 |
* Otherwise, the Timer would never be garbage-collected and this |
578 |
* thread would never go away. |
579 |
*/ |
580 |
private TaskQueue queue; |
581 |
|
582 |
TimerThread(TaskQueue queue) { |
583 |
this.queue = queue; |
584 |
} |
585 |
|
586 |
public void run() { |
587 |
try { |
588 |
mainLoop(); |
589 |
} finally { |
590 |
// Someone killed this Thread, behave as if Timer cancelled |
591 |
synchronized(queue) { |
592 |
newTasksMayBeScheduled = false; |
593 |
queue.clear(); // Eliminate obsolete references |
594 |
} |
595 |
} |
596 |
} |
597 |
|
598 |
/** |
599 |
* The main timer loop. (See class comment.) |
600 |
*/ |
601 |
private void mainLoop() { |
602 |
while (true) { |
603 |
try { |
604 |
TimerTask task; |
605 |
boolean taskFired; |
606 |
synchronized(queue) { |
607 |
// Wait for queue to become non-empty |
608 |
while (queue.isEmpty() && newTasksMayBeScheduled) |
609 |
queue.wait(); |
610 |
if (queue.isEmpty()) |
611 |
break; // Queue is empty and will forever remain; die |
612 |
|
613 |
// Queue nonempty; look at first evt and do the right thing |
614 |
long currentTime, executionTime, delay; |
615 |
task = queue.getMin(); |
616 |
synchronized(task.lock) { |
617 |
if (task.state == TimerTask.CANCELLED) { |
618 |
queue.removeMin(); |
619 |
continue; // No action required, poll queue again |
620 |
} |
621 |
currentTime = Timer.currentTimeNanos(); |
622 |
executionTime = task.nextExecutionTime; |
623 |
delay = executionTime - currentTime; |
624 |
if (taskFired = (delay <= 0)) { |
625 |
if (task.period == 0) { // Non-repeating, remove |
626 |
queue.removeMin(); |
627 |
task.state = TimerTask.EXECUTED; |
628 |
} else { // Repeating task, reschedule |
629 |
queue.rescheduleMin( |
630 |
task.period<0 ? currentTime - task.period |
631 |
: executionTime + task.period); |
632 |
} |
633 |
} |
634 |
} |
635 |
if (!taskFired) // Task hasn't yet fired; wait |
636 |
Timer.waitNanos(queue, delay); |
637 |
} |
638 |
if (taskFired) // Task fired; run it, holding no locks |
639 |
task.run(); |
640 |
} catch(InterruptedException e) { |
641 |
} |
642 |
} |
643 |
} |
644 |
} |
645 |
|
646 |
/** |
647 |
* This class represents a timer task queue: a priority queue of TimerTasks, |
648 |
* ordered on nextExecutionTime. Each Timer object has one of these, which it |
649 |
* shares with its TimerThread. Internally this class uses a heap, which |
650 |
* offers log(n) performance for the add, removeMin and rescheduleMin |
651 |
* operations, and constant time performance for the the getMin operation. |
652 |
*/ |
653 |
class TaskQueue { |
654 |
/** |
655 |
* Priority queue represented as a balanced binary heap: the two children |
656 |
* of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is |
657 |
* ordered on the nextExecutionTime field: The TimerTask with the lowest |
658 |
* nextExecutionTime is in queue[1] (assuming the queue is nonempty). For |
659 |
* each node n in the heap, and each descendant of n, d, |
660 |
* n.nextExecutionTime <= d.nextExecutionTime. |
661 |
*/ |
662 |
private TimerTask[] queue = new TimerTask[128]; |
663 |
|
664 |
/** |
665 |
* The number of tasks in the priority queue. (The tasks are stored in |
666 |
* queue[1] up to queue[size]). |
667 |
*/ |
668 |
private int size = 0; |
669 |
|
670 |
/** |
671 |
* Returns the number of tasks currently on the queue. |
672 |
*/ |
673 |
int size() { |
674 |
return size; |
675 |
} |
676 |
|
677 |
/** |
678 |
* Adds a new task to the priority queue. |
679 |
*/ |
680 |
void add(TimerTask task) { |
681 |
// Grow backing store if necessary |
682 |
if (++size == queue.length) { |
683 |
TimerTask[] newQueue = new TimerTask[2*queue.length]; |
684 |
System.arraycopy(queue, 0, newQueue, 0, size); |
685 |
queue = newQueue; |
686 |
} |
687 |
|
688 |
queue[size] = task; |
689 |
fixUp(size); |
690 |
} |
691 |
|
692 |
/** |
693 |
* Return the "head task" of the priority queue. (The head task is an |
694 |
* task with the lowest nextExecutionTime.) |
695 |
*/ |
696 |
TimerTask getMin() { |
697 |
return queue[1]; |
698 |
} |
699 |
|
700 |
/** |
701 |
* Return the ith task in the priority queue, where i ranges from 1 (the |
702 |
* head task, which is returned by getMin) to the number of tasks on the |
703 |
* queue, inclusive. |
704 |
*/ |
705 |
TimerTask get(int i) { |
706 |
return queue[i]; |
707 |
} |
708 |
|
709 |
/** |
710 |
* Remove the head task from the priority queue. |
711 |
*/ |
712 |
void removeMin() { |
713 |
queue[1] = queue[size]; |
714 |
queue[size--] = null; // Drop extra reference to prevent memory leak |
715 |
fixDown(1); |
716 |
} |
717 |
|
718 |
/** |
719 |
* Removes the ith element from queue without regard for maintaining |
720 |
* the heap invariant. Recall that queue is one-based, so |
721 |
* 1 <= i <= size. |
722 |
*/ |
723 |
void quickRemove(int i) { |
724 |
assert i <= size; |
725 |
|
726 |
queue[i] = queue[size]; |
727 |
queue[size--] = null; // Drop extra ref to prevent memory leak |
728 |
} |
729 |
|
730 |
/** |
731 |
* Sets the nextExecutionTime associated with the head task to the |
732 |
* specified value, and adjusts priority queue accordingly. |
733 |
*/ |
734 |
void rescheduleMin(long newTime) { |
735 |
queue[1].nextExecutionTime = newTime; |
736 |
fixDown(1); |
737 |
} |
738 |
|
739 |
/** |
740 |
* Returns true if the priority queue contains no elements. |
741 |
*/ |
742 |
boolean isEmpty() { |
743 |
return size==0; |
744 |
} |
745 |
|
746 |
/** |
747 |
* Removes all elements from the priority queue. |
748 |
*/ |
749 |
void clear() { |
750 |
// Null out task references to prevent memory leak |
751 |
for (int i=1; i<=size; i++) |
752 |
queue[i] = null; |
753 |
|
754 |
size = 0; |
755 |
} |
756 |
|
757 |
/** |
758 |
* Establishes the heap invariant (described above) assuming the heap |
759 |
* satisfies the invariant except possibly for the leaf-node indexed by k |
760 |
* (which may have a nextExecutionTime less than its parent's). |
761 |
* |
762 |
* This method functions by "promoting" queue[k] up the hierarchy |
763 |
* (by swapping it with its parent) repeatedly until queue[k]'s |
764 |
* nextExecutionTime is greater than or equal to that of its parent. |
765 |
*/ |
766 |
private void fixUp(int k) { |
767 |
while (k > 1) { |
768 |
int j = k >> 1; |
769 |
if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime) |
770 |
break; |
771 |
TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
772 |
k = j; |
773 |
} |
774 |
} |
775 |
|
776 |
/** |
777 |
* Establishes the heap invariant (described above) in the subtree |
778 |
* rooted at k, which is assumed to satisfy the heap invariant except |
779 |
* possibly for node k itself (which may have a nextExecutionTime greater |
780 |
* than its children's). |
781 |
* |
782 |
* This method functions by "demoting" queue[k] down the hierarchy |
783 |
* (by swapping it with its smaller child) repeatedly until queue[k]'s |
784 |
* nextExecutionTime is less than or equal to those of its children. |
785 |
*/ |
786 |
private void fixDown(int k) { |
787 |
int j; |
788 |
while ((j = k << 1) <= size && j > 0) { |
789 |
if (j < size && |
790 |
queue[j].nextExecutionTime > queue[j+1].nextExecutionTime) |
791 |
j++; // j indexes smallest kid |
792 |
if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime) |
793 |
break; |
794 |
TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
795 |
k = j; |
796 |
} |
797 |
} |
798 |
|
799 |
/** |
800 |
* Establishes the heap invariant (described above) in the entire tree, |
801 |
* assuming nothing about the order of the elements prior to the call. |
802 |
*/ |
803 |
void heapify() { |
804 |
for (int i = size/2; i >= 1; i--) |
805 |
fixDown(i); |
806 |
} |
807 |
} |