| Timer.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9 import java.util.Date;
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 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 the <tt>Object.wait(long)</tt> method.
44 *
45 * <p>Implementation note: This class scales to large numbers of concurrently
46 * scheduled tasks (thousands should present no problem). Internally,
47 * it uses a binary heap to represent its task queue, so the cost to schedule
48 * a task is O(log n), where n is the number of concurrently scheduled tasks.
49 *
50 * <p>Implementation note: All constructors start a timer thread.
51 *
52 * @author Josh Bloch
53 * @version %I%, %G%
54 * @see TimerTask
55 * @see Object#wait(long)
56 * @since 1.3
57 */
58
59 public class Timer {
60 /**
61 * The timer task queue. This data structure is shared with the timer
62 * thread. The timer produces tasks, via its various schedule calls,
63 * and the timer thread consumes, executing timer tasks as appropriate,
64 * and removing them from the queue when they're obsolete.
65 */
66 private TaskQueue queue = new TaskQueue();
67
68 /**
69 * The timer thread.
70 */
71 private TimerThread thread = new TimerThread(queue);
72
73 /**
74 * This object causes the timer's task execution thread to exit
75 * gracefully when there are no live references to the Timer object and no
76 * tasks in the timer queue. It is used in preference to a finalizer on
77 * Timer as such a finalizer would be susceptible to a subclass's
78 * finalizer forgetting to call it.
79 */
80 private Object threadReaper = new Object() {
81 protected void finalize() throws Throwable {
82 synchronized(queue) {
83 thread.newTasksMayBeScheduled = false;
84 queue.notify(); // In case queue is empty.
85 }
86 }
87 };
88
89 /**
90 * This ID is used to generate thread names. (It could be replaced
91 * by an AtomicInteger as soon as they become available.)
92 */
93 private static int nextSerialNumber = 0;
94 private static synchronized int serialNumber() {
95 return nextSerialNumber++;
96 }
97
98 /**
99 * Creates a new timer. The associated thread does <i>not</i> run as
100 * a daemon.
101 *
102 * @see Thread
103 * @see #cancel()
104 */
105 public Timer() {
106 this("Timer-" + serialNumber());
107 }
108
109 /**
110 * Creates a new timer whose associated thread may be specified to
111 * run as a daemon. A daemon thread is called for if the timer will
112 * be used to schedule repeating "maintenance activities", which must
113 * be performed as long as the application is running, but should not
114 * prolong the lifetime of the application.
115 *
116 * @param isDaemon true if the associated thread should run as a daemon.
117 *
118 * @see Thread
119 * @see #cancel()
120 */
121 public Timer(boolean isDaemon) {
122 this("Timer-" + serialNumber(), isDaemon);
123 }
124
125 /**
126 * Creates a new timer whose associated thread has the specified name.
127 * The associated thread does <i>not</i> run as a daemon.
128 *
129 * @param name the name of the associated thread
130 * @throws NullPointerException if name is null
131 * @see Thread#getName()
132 * @see Thread#isDaemon()
133 * @since 1.5
134 */
135 public Timer(String name) {
136 thread.setName(name);
137 thread.start();
138 }
139
140 /**
141 * Creates a new timer whose associated thread has the specified name,
142 * and may be specified to run as a daemon.
143 *
144 * @param name the name of the associated thread
145 * @param isDaemon true if the associated thread should run as a daemon
146 * @throws NullPointerException if name is null
147 * @see Thread#getName()
148 * @see Thread#isDaemon()
149 * @since 1.5
150 */
151 public Timer(String name, boolean isDaemon) {
152 thread.setName(name);
153 thread.setDaemon(isDaemon);
154 thread.start();
155 }
156
157 /**
158 * Schedules the specified task for execution after the specified delay.
159 *
160 * @param task task to be scheduled.
161 * @param delay delay in milliseconds before task is to be executed.
162 * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
163 * <tt>delay + System.currentTimeMillis()</tt> is negative.
164 * @throws IllegalStateException if task was already scheduled or
165 * cancelled, or timer was cancelled.
166 */
167 public void schedule(TimerTask task, long delay) {
168 if (delay < 0)
169 throw new IllegalArgumentException("Negative delay.");
170 sched(task, System.currentTimeMillis()+delay, 0);
171 }
172
173 /**
174 * Schedules the specified task for execution at the specified time. If
175 * the time is in the past, the task is scheduled for immediate execution.
176 *
177 * @param task task to be scheduled.
178 * @param time time at which task is to be executed.
179 * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
180 * @throws IllegalStateException if task was already scheduled or
181 * cancelled, timer was cancelled, or timer thread terminated.
182 */
183 public void schedule(TimerTask task, Date time) {
184 sched(task, time.getTime(), 0);
185 }
186
187 /**
188 * Schedules the specified task for repeated <i>fixed-delay execution</i>,
189 * beginning after the specified delay. Subsequent executions take place
190 * at approximately regular intervals separated by the specified period.
191 *
192 * <p>In fixed-delay execution, each execution is scheduled relative to
193 * the actual execution time of the previous execution. If an execution
194 * is delayed for any reason (such as garbage collection or other
195 * background activity), subsequent executions will be delayed as well.
196 * In the long run, the frequency of execution will generally be slightly
197 * lower than the reciprocal of the specified period (assuming the system
198 * clock underlying <tt>Object.wait(long)</tt> is accurate).
199 *
200 * <p>Fixed-delay execution is appropriate for recurring activities
201 * that require "smoothness." In other words, it is appropriate for
202 * activities where it is more important to keep the frequency accurate
203 * in the short run than in the long run. This includes most animation
204 * tasks, such as blinking a cursor at regular intervals. It also includes
205 * tasks wherein regular activity is performed in response to human
206 * input, such as automatically repeating a character as long as a key
207 * is held down.
208 *
209 * @param task task to be scheduled.
210 * @param delay delay in milliseconds before task is to be executed.
211 * @param period time in milliseconds between successive task executions.
212 * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
213 * <tt>delay + System.currentTimeMillis()</tt> is negative.
214 * @throws IllegalStateException if task was already scheduled or
215 * cancelled, timer was cancelled, or timer thread terminated.
216 */
217 public void schedule(TimerTask task, long delay, long period) {
218 if (delay < 0)
219 throw new IllegalArgumentException("Negative delay.");
220 if (period <= 0)
221 throw new IllegalArgumentException("Non-positive period.");
222 sched(task, System.currentTimeMillis()+delay, -period);
223 }
224
225 /**
226 * Schedules the specified task for repeated <i>fixed-delay execution</i>,
227 * beginning at the specified time. Subsequent executions take place at
228 * approximately regular intervals, separated by the specified period.
229 *
230 * <p>In fixed-delay execution, each execution is scheduled relative to
231 * the actual execution time of the previous execution. If an execution
232 * is delayed for any reason (such as garbage collection or other
233 * background activity), subsequent executions will be delayed as well.
234 * In the long run, the frequency of execution will generally be slightly
235 * lower than the reciprocal of the specified period (assuming the system
236 * clock underlying <tt>Object.wait(long)</tt> is accurate).
237 *
238 * <p>Fixed-delay execution is appropriate for recurring activities
239 * that require "smoothness." In other words, it is appropriate for
240 * activities where it is more important to keep the frequency accurate
241 * in the short run than in the long run. This includes most animation
242 * tasks, such as blinking a cursor at regular intervals. It also includes
243 * tasks wherein regular activity is performed in response to human
244 * input, such as automatically repeating a character as long as a key
245 * is held down.
246 *
247 * @param task task to be scheduled.
248 * @param firstTime First time at which task is to be executed.
249 * @param period time in milliseconds between successive task executions.
250 * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
251 * @throws IllegalStateException if task was already scheduled or
252 * cancelled, timer was cancelled, or timer thread terminated.
253 */
254 public void schedule(TimerTask task, Date firstTime, long period) {
255 if (period <= 0)
256 throw new IllegalArgumentException("Non-positive period.");
257 sched(task, firstTime.getTime(), -period);
258 }
259
260 /**
261 * Schedules the specified task for repeated <i>fixed-rate execution</i>,
262 * beginning after the specified delay. Subsequent executions take place
263 * at approximately regular intervals, separated by the specified period.
264 *
265 * <p>In fixed-rate execution, each execution is scheduled relative to the
266 * scheduled execution time of the initial execution. If an execution is
267 * delayed for any reason (such as garbage collection or other background
268 * activity), two or more executions will occur in rapid succession to
269 * "catch up." In the long run, the frequency of execution will be
270 * exactly the reciprocal of the specified period (assuming the system
271 * clock underlying <tt>Object.wait(long)</tt> is accurate).
272 *
273 * <p>Fixed-rate execution is appropriate for recurring activities that
274 * are sensitive to <i>absolute</i> time, such as ringing a chime every
275 * hour on the hour, or running scheduled maintenance every day at a
276 * particular time. It is also appropriate for recurring activities
277 * where the total time to perform a fixed number of executions is
278 * important, such as a countdown timer that ticks once every second for
279 * ten seconds. Finally, fixed-rate execution is appropriate for
280 * scheduling multiple repeating timer tasks that must remain synchronized
281 * with respect to one another.
282 *
283 * @param task task to be scheduled.
284 * @param delay delay in milliseconds before task is to be executed.
285 * @param period time in milliseconds between successive task executions.
286 * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
287 * <tt>delay + System.currentTimeMillis()</tt> is negative.
288 * @throws IllegalStateException if task was already scheduled or
289 * cancelled, timer was cancelled, or timer thread terminated.
290 */
291 public void scheduleAtFixedRate(TimerTask task, long delay, long period) {
292 if (delay < 0)
293 throw new IllegalArgumentException("Negative delay.");
294 if (period <= 0)
295 throw new IllegalArgumentException("Non-positive period.");
296 sched(task, System.currentTimeMillis()+delay, period);
297 }
298
299 /**
300 * Schedules the specified task for repeated <i>fixed-rate execution</i>,
301 * beginning at the specified time. Subsequent executions take place at
302 * approximately regular intervals, separated by the specified period.
303 *
304 * <p>In fixed-rate execution, each execution is scheduled relative to the
305 * scheduled execution time of the initial execution. If an execution is
306 * delayed for any reason (such as garbage collection or other background
307 * activity), two or more executions will occur in rapid succession to
308 * "catch up." In the long run, the frequency of execution will be
309 * exactly the reciprocal of the specified period (assuming the system
310 * clock underlying <tt>Object.wait(long)</tt> is accurate).
311 *
312 * <p>Fixed-rate execution is appropriate for recurring activities that
313 * are sensitive to <i>absolute</i> time, such as ringing a chime every
314 * hour on the hour, or running scheduled maintenance every day at a
315 * particular time. It is also appropriate for recurring activities
316 * where the total time to perform a fixed number of executions is
317 * important, such as a countdown timer that ticks once every second for
318 * ten seconds. Finally, fixed-rate execution is appropriate for
319 * scheduling multiple repeating timer tasks that must remain synchronized
320 * with respect to one another.
321 *
322 * @param task task to be scheduled.
323 * @param firstTime First time at which task is to be executed.
324 * @param period time in milliseconds between successive task executions.
325 * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
326 * @throws IllegalStateException if task was already scheduled or
327 * cancelled, timer was cancelled, or timer thread terminated.
328 */
329 public void scheduleAtFixedRate(TimerTask task, Date firstTime,
330 long period) {
331 if (period <= 0)
332 throw new IllegalArgumentException("Non-positive period.");
333 sched(task, firstTime.getTime(), period);
334 }
335
336 /**
337 * Schedule the specified timer task for execution at the specified
338 * time with the specified period, in milliseconds. If period is
339 * positive, the task is scheduled for repeated execution; if period is
340 * zero, the task is scheduled for one-time execution. Time is specified
341 * in Date.getTime() format. This method checks timer state, task state,
342 * and initial execution time, but not period.
343 *
344 * @throws IllegalArgumentException if <tt>time()</tt> is negative.
345 * @throws IllegalStateException if task was already scheduled or
346 * cancelled, timer was cancelled, or timer thread terminated.
347 */
348 private void sched(TimerTask task, long time, long period) {
349 if (time < 0)
350 throw new IllegalArgumentException("Illegal execution time.");
351
352 synchronized(queue) {
353 if (!thread.newTasksMayBeScheduled)
354 throw new IllegalStateException("Timer already cancelled.");
355
356 synchronized(task.lock) {
357 if (task.state != TimerTask.VIRGIN)
358 throw new IllegalStateException(
359 "Task already scheduled or cancelled");
360 task.nextExecutionTime = time;
361 task.period = period;
362 task.state = TimerTask.SCHEDULED;
363 }
364
365 queue.add(task);
366 if (queue.getMin() == task)
367 queue.notify();
368 }
369 }
370
371 /**
372 * Terminates this timer, discarding any currently scheduled tasks.
373 * Does not interfere with a currently executing task (if it exists).
374 * Once a timer has been terminated, its execution thread terminates
375 * gracefully, and no more tasks may be scheduled on it.
376 *
377 * <p>Note that calling this method from within the run method of a
378 * timer task that was invoked by this timer absolutely guarantees that
379 * the ongoing task execution is the last task execution that will ever
380 * be performed by this timer.
381 *
382 * <p>This method may be called repeatedly; the second and subsequent
383 * calls have no effect.
384 */
385 public void cancel() {
386 synchronized(queue) {
387 thread.newTasksMayBeScheduled = false;
388 queue.clear();
389 queue.notify(); // In case queue was already empty.
390 }
391 }
392
393 /**
394 * Removes all cancelled tasks from this timer's task queue. <i>Calling
395 * this method has no effect on the behavior of the timer</i>, but
396 * eliminates the references to the cancelled tasks from the queue.
397 * If there are no external references to these tasks, they become
398 * eligible for garbage collection.
399 *
400 * <p>Most programs will have no need to call this method.
401 * It is designed for use by the rare application that cancels a large
402 * number of tasks. Calling this method trades time for space: the
403 * runtime of the method may be proportional to n + c log n, where n
404 * is the number of tasks in the queue and c is the number of cancelled
405 * tasks.
406 *
407 * <p>Note that it is permissible to call this method from within a
408 * a task scheduled on this timer.
409 *
410 * @return the number of tasks removed from the queue.
411 * @since 1.5
412 */
413 public int purge() {
414 int result = 0;
415
416 synchronized(queue) {
417 for (int i = queue.size(); i > 0; i--) {
418 if (queue.get(i).state == TimerTask.CANCELLED) {
419 queue.quickRemove(i);
420 result++;
421 }
422 }
423
424 if (result != 0)
425 queue.heapify();
426 }
427
428 return result;
429 }
430 }
431
432 /**
433 * This "helper class" implements the timer's task execution thread, which
434 * waits for tasks on the timer queue, executions them when they fire,
435 * reschedules repeating tasks, and removes cancelled tasks and spent
436 * non-repeating tasks from the queue.
437 */
438 class TimerThread extends Thread {
439 /**
440 * This flag is set to false by the reaper to inform us that there
441 * are no more live references to our Timer object. Once this flag
442 * is true and there are no more tasks in our queue, there is no
443 * work left for us to do, so we terminate gracefully. Note that
444 * this field is protected by queue's monitor!
445 */
446 boolean newTasksMayBeScheduled = true;
447
448 /**
449 * Our Timer's queue. We store this reference in preference to
450 * a reference to the Timer so the reference graph remains acyclic.
451 * Otherwise, the Timer would never be garbage-collected and this
452 * thread would never go away.
453 */
454 private TaskQueue queue;
455
456 TimerThread(TaskQueue queue) {
457 this.queue = queue;
458 }
459
460 public void run() {
461 try {
462 mainLoop();
463 } finally {
464 // Someone killed this Thread, behave as if Timer cancelled
465 synchronized(queue) {
466 newTasksMayBeScheduled = false;
467 queue.clear(); // Eliminate obsolete references
468 }
469 }
470 }
471
472 /**
473 * The main timer loop. (See class comment.)
474 */
475 private void mainLoop() {
476 while (true) {
477 try {
478 TimerTask task;
479 boolean taskFired;
480 synchronized(queue) {
481 // Wait for queue to become non-empty
482 while (queue.isEmpty() && newTasksMayBeScheduled)
483 queue.wait();
484 if (queue.isEmpty())
485 break; // Queue is empty and will forever remain; die
486
487 // Queue nonempty; look at first evt and do the right thing
488 long currentTime, executionTime;
489 task = queue.getMin();
490 synchronized(task.lock) {
491 if (task.state == TimerTask.CANCELLED) {
492 queue.removeMin();
493 continue; // No action required, poll queue again
494 }
495 currentTime = System.currentTimeMillis();
496 executionTime = task.nextExecutionTime;
497 if (taskFired = (executionTime<=currentTime)) {
498 if (task.period == 0) { // Non-repeating, remove
499 queue.removeMin();
500 task.state = TimerTask.EXECUTED;
501 } else { // Repeating task, reschedule
502 queue.rescheduleMin(
503 task.period<0 ? currentTime - task.period
504 : executionTime + task.period);
505 }
506 }
507 }
508 if (!taskFired) // Task hasn't yet fired; wait
509 queue.wait(executionTime - currentTime);
510 }
511 if (taskFired) // Task fired; run it, holding no locks
512 task.run();
513 } catch(InterruptedException e) {
514 }
515 }
516 }
517 }
518
519 /**
520 * This class represents a timer task queue: a priority queue of TimerTasks,
521 * ordered on nextExecutionTime. Each Timer object has one of these, which it
522 * shares with its TimerThread. Internally this class uses a heap, which
523 * offers log(n) performance for the add, removeMin and rescheduleMin
524 * operations, and constant time performance for the getMin operation.
525 */
526 class TaskQueue {
527 /**
528 * Priority queue represented as a balanced binary heap: the two children
529 * of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is
530 * ordered on the nextExecutionTime field: The TimerTask with the lowest
531 * nextExecutionTime is in queue[1] (assuming the queue is nonempty). For
532 * each node n in the heap, and each descendant of n, d,
533 * n.nextExecutionTime <= d.nextExecutionTime.
534 */
535 private TimerTask[] queue = new TimerTask[128];
536
537 /**
538 * The number of tasks in the priority queue. (The tasks are stored in
539 * queue[1] up to queue[size]).
540 */
541 private int size = 0;
542
543 /**
544 * Returns the number of tasks currently on the queue.
545 */
546 int size() {
547 return size;
548 }
549
550 /**
551 * Adds a new task to the priority queue.
552 */
553 void add(TimerTask task) {
554 // Grow backing store if necessary
555 if (size + 1 == queue.length)
556 queue = Arrays.copyOf(queue, 2*queue.length);
557
558 queue[++size] = task;
559 fixUp(size);
560 }
561
562 /**
563 * Return the "head task" of the priority queue. (The head task is an
564 * task with the lowest nextExecutionTime.)
565 */
566 TimerTask getMin() {
567 return queue[1];
568 }
569
570 /**
571 * Return the ith task in the priority queue, where i ranges from 1 (the
572 * head task, which is returned by getMin) to the number of tasks on the
573 * queue, inclusive.
574 */
575 TimerTask get(int i) {
576 return queue[i];
577 }
578
579 /**
580 * Remove the head task from the priority queue.
581 */
582 void removeMin() {
583 queue[1] = queue[size];
584 queue[size--] = null; // Drop extra reference to prevent memory leak
585 fixDown(1);
586 }
587
588 /**
589 * Removes the ith element from queue without regard for maintaining
590 * the heap invariant. Recall that queue is one-based, so
591 * 1 <= i <= size.
592 */
593 void quickRemove(int i) {
594 assert i <= size;
595
596 queue[i] = queue[size];
597 queue[size--] = null; // Drop extra ref to prevent memory leak
598 }
599
600 /**
601 * Sets the nextExecutionTime associated with the head task to the
602 * specified value, and adjusts priority queue accordingly.
603 */
604 void rescheduleMin(long newTime) {
605 queue[1].nextExecutionTime = newTime;
606 fixDown(1);
607 }
608
609 /**
610 * Returns true if the priority queue contains no elements.
611 */
612 boolean isEmpty() {
613 return size==0;
614 }
615
616 /**
617 * Removes all elements from the priority queue.
618 */
619 void clear() {
620 // Null out task references to prevent memory leak
621 for (int i=1; i<=size; i++)
622 queue[i] = null;
623
624 size = 0;
625 }
626
627 /**
628 * Establishes the heap invariant (described above) assuming the heap
629 * satisfies the invariant except possibly for the leaf-node indexed by k
630 * (which may have a nextExecutionTime less than its parent's).
631 *
632 * This method functions by "promoting" queue[k] up the hierarchy
633 * (by swapping it with its parent) repeatedly until queue[k]'s
634 * nextExecutionTime is greater than or equal to that of its parent.
635 */
636 private void fixUp(int k) {
637 while (k > 1) {
638 int j = k >> 1;
639 if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
640 break;
641 TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
642 k = j;
643 }
644 }
645
646 /**
647 * Establishes the heap invariant (described above) in the subtree
648 * rooted at k, which is assumed to satisfy the heap invariant except
649 * possibly for node k itself (which may have a nextExecutionTime greater
650 * than its children's).
651 *
652 * This method functions by "demoting" queue[k] down the hierarchy
653 * (by swapping it with its smaller child) repeatedly until queue[k]'s
654 * nextExecutionTime is less than or equal to those of its children.
655 */
656 private void fixDown(int k) {
657 int j;
658 while ((j = k << 1) <= size && j > 0) {
659 if (j < size &&
660 queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
661 j++; // j indexes smallest kid
662 if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
663 break;
664 TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
665 k = j;
666 }
667 }
668
669 /**
670 * Establishes the heap invariant (described above) in the entire tree,
671 * assuming nothing about the order of the elements prior to the call.
672 */
673 void heapify() {
674 for (int i = size/2; i >= 1; i--)
675 fixDown(i);
676 }
677 }
678