001: /*
002: *
003: *
004: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: */
026:
027: package java.util;
028:
029: import java.util.Date;
030:
031: /**
032: * A facility for threads to schedule tasks for future execution in a
033: * background thread. Tasks may be scheduled for one-time execution, or for
034: * repeated execution at regular intervals.
035: *
036: * <p>Corresponding to each <tt>Timer</tt> object is a single background
037: * thread that is used to execute all of the timer's tasks, sequentially.
038: * Timer tasks should complete quickly. If a timer task takes excessive time
039: * to complete, it "hogs" the timer's task execution thread. This can, in
040: * turn, delay the execution of subsequent tasks, which may "bunch up" and
041: * execute in rapid succession when (and if) the offending task finally
042: * completes.
043: *
044: * <p>After the last live reference to a <tt>Timer</tt> object goes away
045: * <i>and</i> all outstanding tasks have completed execution, the timer's task
046: * execution thread terminates gracefully (and becomes subject to garbage
047: * collection). However, this can take arbitrarily long to occur. By
048: * default, the task execution thread does not run as a <i>daemon thread</i>,
049: * so it is capable of keeping an application from terminating. If a caller
050: * wants to terminate a timer's task execution thread rapidly, the caller
051: * should invoke the timer's <tt>cancel</tt> method.
052: *
053: * <p>If the timer's task execution thread terminates unexpectedly, for
054: * example, because its <tt>stop</tt> method is invoked, any further
055: * attempt to schedule a task on the timer will result in an
056: * <tt>IllegalStateException</tt>, as if the timer's <tt>cancel</tt>
057: * method had been invoked.
058: *
059: * <p>This class is thread-safe: multiple threads can share a single
060: * <tt>Timer</tt> object without the need for external synchronization.
061: *
062: * <p>This class does <i>not</i> offer real-time guarantees: it schedules
063: * tasks using the <tt>Object.wait(long)</tt> method.
064: * <p>
065: * Timers function only within a single VM and are cancelled when the VM exits.
066: * When the VM is started no timers exist, they are created only by
067: * application request.
068: *
069: * @see TimerTask
070: * @see Object#wait(long)
071: * @since 1.3
072: */
073:
074: public class Timer {
075: /**
076: * The timer task queue. This data structure is shared with the timer
077: * thread. The timer produces tasks, via its various schedule calls,
078: * and the timer thread consumes, executing timer tasks as appropriate,
079: * and removing them from the queue when they're obsolete.
080: */
081: private TaskQueue queue = new TaskQueue();
082:
083: /**
084: * The timer thread.
085: */
086: private TimerThread thread;
087:
088: /**
089: * Creates a new timer. The associated thread does <i>not</i> run as
090: * a daemon thread, which may prevent an application from terminating.
091: *
092: * @see Thread
093: * @see #cancel()
094: */
095: public Timer() {
096: }
097:
098: /**
099: * Schedules the specified task for execution after the specified delay.
100: *
101: * @param task task to be scheduled.
102: * @param delay delay in milliseconds before task is to be executed.
103: * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
104: * <tt>delay + System.currentTimeMillis()</tt> is negative.
105: * @throws IllegalStateException if task was already scheduled or
106: * cancelled, or timer was cancelled.
107: */
108: public void schedule(TimerTask task, long delay) {
109: if (delay < 0)
110: throw new IllegalArgumentException("Negative delay.");
111: sched(task, System.currentTimeMillis() + delay, 0);
112: }
113:
114: /**
115: * Schedules the specified task for execution at the specified time. If
116: * the time is in the past, the task is scheduled for immediate execution.
117: *
118: * @param task task to be scheduled.
119: * @param time time at which task is to be executed.
120: * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
121: * @throws IllegalStateException if task was already scheduled or
122: * cancelled, timer was cancelled, or timer thread terminated.
123: */
124: public void schedule(TimerTask task, Date time) {
125: sched(task, time.getTime(), 0);
126: }
127:
128: /**
129: * Schedules the specified task for repeated <i>fixed-delay execution</i>,
130: * beginning after the specified delay. Subsequent executions take place
131: * at approximately regular intervals separated by the specified period.
132: *
133: * <p>In fixed-delay execution, each execution is scheduled relative to
134: * the actual execution time of the previous execution. If an execution
135: * is delayed for any reason (such as garbage collection or other
136: * background activity), subsequent executions will be delayed as well.
137: * In the long run, the frequency of execution will generally be slightly
138: * lower than the reciprocal of the specified period (assuming the system
139: * clock underlying <tt>Object.wait(long)</tt> is accurate).
140: *
141: * <p>Fixed-delay execution is appropriate for recurring activities
142: * that require "smoothness." In other words, it is appropriate for
143: * activities where it is more important to keep the frequency accurate
144: * in the short run than in the long run. This includes most animation
145: * tasks, such as blinking a cursor at regular intervals. It also includes
146: * tasks wherein regular activity is performed in response to human
147: * input, such as automatically repeating a character as long as a key
148: * is held down.
149: *
150: * @param task task to be scheduled.
151: * @param delay delay in milliseconds before task is to be executed.
152: * @param period time in milliseconds between successive task executions.
153: * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
154: * <tt>delay + System.currentTimeMillis()</tt> is negative.
155: * @throws IllegalStateException if task was already scheduled or
156: * cancelled, timer was cancelled, or timer thread terminated.
157: */
158: public void schedule(TimerTask task, long delay, long period) {
159: if (delay < 0)
160: throw new IllegalArgumentException("Negative delay.");
161: if (period <= 0)
162: throw new IllegalArgumentException("Non-positive period.");
163: sched(task, System.currentTimeMillis() + delay, -period);
164: }
165:
166: /**
167: * Schedules the specified task for repeated <i>fixed-delay execution</i>,
168: * beginning at the specified time. Subsequent executions take place at
169: * approximately regular intervals, separated by the specified period.
170: *
171: * <p>In fixed-delay execution, each execution is scheduled relative to
172: * the actual execution time of the previous execution. If an execution
173: * is delayed for any reason (such as garbage collection or other
174: * background activity), subsequent executions will be delayed as well.
175: * In the long run, the frequency of execution will generally be slightly
176: * lower than the reciprocal of the specified period (assuming the system
177: * clock underlying <tt>Object.wait(long)</tt> is accurate).
178: *
179: * <p>Fixed-delay execution is appropriate for recurring activities
180: * that require "smoothness." In other words, it is appropriate for
181: * activities where it is more important to keep the frequency accurate
182: * in the short run than in the long run. This includes most animation
183: * tasks, such as blinking a cursor at regular intervals. It also includes
184: * tasks wherein regular activity is performed in response to human
185: * input, such as automatically repeating a character as long as a key
186: * is held down.
187: *
188: * @param task task to be scheduled.
189: * @param firstTime First time at which task is to be executed.
190: * @param period time in milliseconds between successive task executions.
191: * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
192: * @throws IllegalStateException if task was already scheduled or
193: * cancelled, timer was cancelled, or timer thread terminated.
194: */
195: public void schedule(TimerTask task, Date firstTime, long period) {
196: if (period <= 0)
197: throw new IllegalArgumentException("Non-positive period.");
198: sched(task, firstTime.getTime(), -period);
199: }
200:
201: /**
202: * Schedules the specified task for repeated <i>fixed-rate execution</i>,
203: * beginning after the specified delay. Subsequent executions take place
204: * at approximately regular intervals, separated by the specified period.
205: *
206: * <p>In fixed-rate execution, each execution is scheduled relative to the
207: * scheduled execution time of the initial execution. If an execution is
208: * delayed for any reason (such as garbage collection or other background
209: * activity), two or more executions will occur in rapid succession to
210: * "catch up." In the long run, the frequency of execution will be
211: * exactly the reciprocal of the specified period (assuming the system
212: * clock underlying <tt>Object.wait(long)</tt> is accurate).
213: *
214: * <p>Fixed-rate execution is appropriate for recurring activities that
215: * are sensitive to <i>absolute</i> time, such as ringing a chime every
216: * hour on the hour, or running scheduled maintenance every day at a
217: * particular time. It is also appropriate for for recurring activities
218: * where the total time to perform a fixed number of executions is
219: * important, such as a countdown timer that ticks once every second for
220: * ten seconds. Finally, fixed-rate execution is appropriate for
221: * scheduling multiple repeating timer tasks that must remain synchronized
222: * with respect to one another.
223: *
224: * @param task task to be scheduled.
225: * @param delay delay in milliseconds before task is to be executed.
226: * @param period time in milliseconds between successive task executions.
227: * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
228: * <tt>delay + System.currentTimeMillis()</tt> is negative.
229: * @throws IllegalStateException if task was already scheduled or
230: * cancelled, timer was cancelled, or timer thread terminated.
231: */
232: public void scheduleAtFixedRate(TimerTask task, long delay,
233: long period) {
234: if (delay < 0)
235: throw new IllegalArgumentException("Negative delay.");
236: if (period <= 0)
237: throw new IllegalArgumentException("Non-positive period.");
238: sched(task, System.currentTimeMillis() + delay, period);
239: }
240:
241: /**
242: * Schedules the specified task for repeated <i>fixed-rate execution</i>,
243: * beginning at the specified time. Subsequent executions take place at
244: * approximately regular intervals, separated by the specified period.
245: *
246: * <p>In fixed-rate execution, each execution is scheduled relative to the
247: * scheduled execution time of the initial execution. If an execution is
248: * delayed for any reason (such as garbage collection or other background
249: * activity), two or more executions will occur in rapid succession to
250: * "catch up." In the long run, the frequency of execution will be
251: * exactly the reciprocal of the specified period (assuming the system
252: * clock underlying <tt>Object.wait(long)</tt> is accurate).
253: *
254: * <p>Fixed-rate execution is appropriate for recurring activities that
255: * are sensitive to <i>absolute</i> time, such as ringing a chime every
256: * hour on the hour, or running scheduled maintenance every day at a
257: * particular time. It is also appropriate for for recurring activities
258: * where the total time to perform a fixed number of executions is
259: * important, such as a countdown timer that ticks once every second for
260: * ten seconds. Finally, fixed-rate execution is appropriate for
261: * scheduling multiple repeating timer tasks that must remain synchronized
262: * with respect to one another.
263: *
264: * @param task task to be scheduled.
265: * @param firstTime First time at which task is to be executed.
266: * @param period time in milliseconds between successive task executions.
267: * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
268: * @throws IllegalStateException if task was already scheduled or
269: * cancelled, timer was cancelled, or timer thread terminated.
270: */
271: public void scheduleAtFixedRate(TimerTask task, Date firstTime,
272: long period) {
273: if (period <= 0)
274: throw new IllegalArgumentException("Non-positive period.");
275: sched(task, firstTime.getTime(), period);
276: }
277:
278: /**
279: * Schedule the specified timer task for execution at the specified
280: * time with the specified period, in milliseconds. If period is
281: * positive, the task is scheduled for repeated execution; if period is
282: * zero, the task is scheduled for one-time execution. Time is specified
283: * in Date.getTime() format. This method checks timer state, task state,
284: * and initial execution time, but not period.
285: *
286: * @param task task to be scheduled.
287: * @param time time at which task is to be executed.
288: * @param period time in milliseconds between successive task executions.
289: * @throws IllegalArgumentException if <tt>time()</tt> is negative.
290: * @throws IllegalStateException if task was already scheduled or
291: * cancelled, timer was cancelled, or timer thread terminated.
292: */
293: private void sched(TimerTask task, long time, long period) {
294: if (time < 0)
295: throw new IllegalArgumentException(
296: "Illegal execution time.");
297:
298: synchronized (queue) {
299: if (!queue.newTasksMayBeScheduled) {
300: throw new IllegalStateException(
301: "Timer already cancelled.");
302: }
303:
304: /*
305: * If the TimerThread has exited without an error
306: * it is restarted. See the commentary in TimerThread.run.
307: */
308: if (thread == null || !thread.isAlive()) {
309: thread = new TimerThread(queue);
310: thread.start();
311: }
312:
313: synchronized (task.lock) {
314: if (task.state != TimerTask.VIRGIN) {
315: throw new IllegalStateException(
316: "Task already scheduled or cancelled");
317: }
318: task.nextExecutionTime = time;
319: task.period = period;
320: task.state = TimerTask.SCHEDULED;
321: }
322:
323: queue.add(task);
324: if (queue.getMin() == task)
325: queue.notify();
326: }
327: }
328:
329: /**
330: * Terminates this timer, discarding any currently scheduled tasks.
331: * Does not interfere with a currently executing task (if it exists).
332: * Once a timer has been terminated, its execution thread terminates
333: * gracefully, and no more tasks may be scheduled on it.
334: *
335: * <p>Note that calling this method from within the run method of a
336: * timer task that was invoked by this timer absolutely guarantees that
337: * the ongoing task execution is the last task execution that will ever
338: * be performed by this timer.
339: *
340: * <p>This method may be called repeatedly; the second and subsequent
341: * calls have no effect.
342: */
343: public void cancel() {
344: synchronized (queue) {
345: queue.newTasksMayBeScheduled = false;
346: queue.clear();
347: queue.notify(); // In case queue was already empty.
348: }
349: }
350: }
351:
352: /**
353: * This "helper class" implements the timer's task execution thread, which
354: * waits for tasks on the timer queue, executions them when they fire,
355: * reschedules repeating tasks, and removes cancelled tasks and spent
356: * non-repeating tasks from the queue.
357: * <p>
358: * The thread will timeout if no TimerTasks are scheduled for it within
359: * a timeout period. When it times out the thread exits leaving
360: * the newTasksMayBeScheduled
361: * boolean true. If true and the thread is not alive it should be restarted as
362: * in the Timer.sched method above.
363: */
364: class TimerThread extends Thread {
365: /**
366: * Our Timer's queue. We store this reference in preference to
367: * a reference to the Timer so the reference graph remains acyclic.
368: * Otherwise, the Timer would never be garbage-collected and this
369: * thread would never go away.
370: */
371: private TaskQueue queue;
372:
373: /**
374: * The number of milliseconds to wait after the timer queue is empty
375: * before the thread exits. It will be restarted when the next TimerTask
376: * is inserted.
377: */
378: private static final long THREAD_TIMEOUT = 30 * 1000L;
379:
380: /**
381: * initialize the timer thread with a task queue.
382: * @param queue queue of tasks for this timer thread.
383: */
384: TimerThread(TaskQueue queue) {
385: this .queue = queue;
386: }
387:
388: /** start the main processing loop. */
389: public void run() {
390: try {
391: mainLoop();
392: /*
393: * If mainLoop returns then thread timed out with no events
394: * in the queue. The thread will quietly be restarted in sched()
395: * when the next TimerTask is queued.
396: */
397: } catch (Throwable t) {
398: // Someone killed this Thread, behave as if Timer cancelled
399: synchronized (queue) {
400: queue.newTasksMayBeScheduled = false;
401: queue.clear(); // Eliminate obsolete references
402: }
403: }
404: }
405:
406: /**
407: * The main timer loop. (See class comment.)
408: */
409: private void mainLoop() {
410: while (true) {
411: try {
412: TimerTask task;
413: boolean taskFired;
414: synchronized (queue) {
415: // Wait for queue to become non-empty
416: // But no more than timeout value.
417: while (queue.isEmpty()
418: && queue.newTasksMayBeScheduled) {
419: queue.wait(THREAD_TIMEOUT);
420: if (queue.isEmpty()) {
421: break;
422: }
423: }
424: if (queue.isEmpty())
425: break; // Queue is empty and will forever remain; die
426:
427: // Queue nonempty; look at first evt and do the right thing
428: long currentTime, executionTime;
429: task = queue.getMin();
430: synchronized (task.lock) {
431: if (task.state == TimerTask.CANCELLED) {
432: queue.removeMin();
433: continue; // No action required, poll queue again
434: }
435: currentTime = System.currentTimeMillis();
436: executionTime = task.nextExecutionTime;
437: if (taskFired = (executionTime <= currentTime)) {
438: if (task.period == 0) { // Non-repeating, remove
439: queue.removeMin();
440: task.state = TimerTask.EXECUTED;
441: } else { // Repeating task, reschedule
442: queue
443: .rescheduleMin(task.period < 0 ? currentTime
444: - task.period
445: : executionTime
446: + task.period);
447: }
448: }
449: }
450: if (!taskFired) { // Task hasn't yet fired; wait
451: queue.wait(executionTime - currentTime);
452: }
453: }
454: if (taskFired) { // Task fired; run it, holding no locks
455: try {
456: task.run();
457: } catch (Exception e) {
458: // Cancel tasks that cause exceptions
459: task.cancel();
460: }
461: }
462: } catch (InterruptedException e) {
463: }
464: }
465: }
466: }
467:
468: /**
469: * This class represents a timer task queue: a priority queue of TimerTasks,
470: * ordered on nextExecutionTime. Each Timer object has one of these, which it
471: * shares with its TimerThread. Internally this class uses a heap, which
472: * offers log(n) performance for the add, removeMin and rescheduleMin
473: * operations, and constant time performance for the getMin operation.
474: */
475: class TaskQueue {
476: /**
477: * Priority queue represented as a balanced binary heap: the two children
478: * of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is
479: * ordered on the nextExecutionTime field: The TimerTask with the lowest
480: * nextExecutionTime is in queue[1] (assuming the queue is nonempty). For
481: * each node n in the heap, and each descendant of n, d,
482: * n.nextExecutionTime <= d.nextExecutionTime.
483: */
484: private TimerTask[] queue = new TimerTask[4];
485:
486: /**
487: * The number of tasks in the priority queue. (The tasks are stored in
488: * queue[1] up to queue[size]).
489: */
490: private int size = 0;
491:
492: /**
493: * This flag is set to false by the reaper to inform us that there
494: * are no more live references to our Timer object. Once this flag
495: * is true and there are no more tasks in our queue, there is no
496: * work left for us to do, so we terminate gracefully.
497: */
498: boolean newTasksMayBeScheduled = true;
499:
500: /**
501: * Adds a new task to the priority queue.
502: * @param task to add to the current queue
503: */
504: void add(TimerTask task) {
505: // Grow backing store if necessary
506: if (++size == queue.length) {
507: TimerTask[] newQueue = new TimerTask[2 * queue.length];
508: System.arraycopy(queue, 0, newQueue, 0, size);
509: queue = newQueue;
510: }
511:
512: queue[size] = task;
513: fixUp(size);
514: }
515:
516: /**
517: * Return the "head task" of the priority queue. (The head task is an
518: * task with the lowest nextExecutionTime.)
519: * @return the minimum head task of the queue.
520: */
521: TimerTask getMin() {
522: return queue[1];
523: }
524:
525: /**
526: * Remove the head task from the priority queue.
527: */
528: void removeMin() {
529: queue[1] = queue[size];
530: queue[size--] = null; // Drop extra reference to prevent memory leak
531: fixDown(1);
532: }
533:
534: /**
535: * Sets the nextExecutionTime associated with the head task to the
536: * specified value, and adjusts priority queue accordingly.
537: * @param newTime new time to apply to head task execution.
538: */
539: void rescheduleMin(long newTime) {
540: queue[1].nextExecutionTime = newTime;
541: fixDown(1);
542: }
543:
544: /**
545: * Returns true if the priority queue contains no elements.
546: * @return true if queue is empty.
547: */
548: boolean isEmpty() {
549: return size == 0;
550: }
551:
552: /**
553: * Removes all elements from the priority queue.
554: */
555: void clear() {
556: // Null out task references to prevent memory leak
557: for (int i = 1; i <= size; i++)
558: queue[i] = null;
559:
560: size = 0;
561: }
562:
563: /**
564: * Establishes the heap invariant (described above) assuming the heap
565: * satisfies the invariant except possibly for the leaf-node indexed by k
566: * (which may have a nextExecutionTime less than its parent's).
567: *
568: * This method functions by "promoting" queue[k] up the hierarchy
569: * (by swapping it with its parent) repeatedly until queue[k]'s
570: * nextExecutionTime is greater than or equal to that of its parent.
571: * @param k index of queued task to be promoted up in the queue.
572: */
573: private void fixUp(int k) {
574: while (k > 1) {
575: int j = k >> 1;
576: if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
577: break;
578: TimerTask tmp = queue[j];
579: queue[j] = queue[k];
580: queue[k] = tmp;
581: k = j;
582: }
583: }
584:
585: /**
586: * Establishes the heap invariant (described above) in the subtree
587: * rooted at k, which is assumed to satisfy the heap invariant except
588: * possibly for node k itself (which may have a nextExecutionTime greater
589: * than its children's).
590: *
591: * This method functions by "demoting" queue[k] down the hierarchy
592: * (by swapping it with its smaller child) repeatedly until queue[k]'s
593: * nextExecutionTime is less than or equal to those of its children.
594: * @param k index of queued task to be demoted in the queue.
595: */
596: private void fixDown(int k) {
597: int j;
598: while ((j = k << 1) <= size) {
599: if (j < size
600: && queue[j].nextExecutionTime > queue[j + 1].nextExecutionTime)
601: j++; // j indexes smallest kid
602: if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
603: break;
604: TimerTask tmp = queue[j];
605: queue[j] = queue[k];
606: queue[k] = tmp;
607: k = j;
608: }
609: }
610: }
|