Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis – Counting – scheduling – or event timing
Reexamination Certificate
2000-09-08
2004-04-06
Butler, Dennis M. (Department: 2185)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
Counting, scheduling, or event timing
Reexamination Certificate
active
06718479
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, system, and program for maintaining timers for system operations.
2. Description of the Related Art
Computer systems include a timer for failure recovery and for those programs and algorithms that require the measurement of time. For instance, certain failures are detected after an event does not occur within a specified period. Further programs require notification of the expiration of a period of time in order to know when to take a particular action.
It is desirable to provide a timer that measures time with a fine granularity, such as in microseconds. However, with many prior art timers, the finer the granularity of the time measurements, the increase in the number of interruptions to the processor each time a clock cycle occurs. During each tick, i.e., clock cycle, the processor is interrupted and would check if any timers provided for programs have expired. The processor overhead in responding to frequent interrupts can significantly degrade processor performance. Further, if many programs require a timer, then managing a large number of timers could also significantly increase the number of interrupts to the processor caused by clock cycles for each timer. Many operating systems have timers of coarse granulatiry (milliseconds or seconds) to reduce the frequency of interrupts to the processor.
Certain prior art timers utilize a timing wheel. A timer is a data structure created by a program that is set to expire after a specified interval of time. A timing wheel is a data structure into which timers are inserted as an array of lists. An overflow wheel may be provided for timers beyond the range of the arrays in the previous wheels. A timing wheel has a slot for each time cycle, or tick. The current time pointer points to a slot that may include timers for the current time. After a tick, the processor is interrupted to increment a time pointer to the next slot in the wheel. The processor increments the current time pointer each tick until it finds a non empty slot having one or more timers, and then processes all timer events in the slot. Prior art timing wheels are described in the article entitled “Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility”, by George Varghese and Anthony Lauck, in IEEE/ACM Transactions on Networking, Vol. 5, No. 6, pgs. 824-834 (December 1997), which publication is incorporated herein by reference in its entirety.
There is a need in the art for providing improved techniques for implementing a timing wheel of timers in a manner that minimizes the number of interruptions and burdens placed on the processor.
SUMMARY OF THE PREFERRED EMBODIMENTS
To overcome the limitations in the prior art described above, preferred embodiments disclose a method, system, program, and data structures for managing timers in timing wheel data structures in a computer readable medium. Each timer is enqueued in one slot in one of multiple timing wheels. Each timing wheel includes multiple slots and each slot is associated with a time value. Each slot is capable of queuing one or more timers. Each timer indicates a timeout value at which the timer expires. A register is decremented to zero and a determination is made of a current time. A determination is further made, in response to decrementing the register to zero, of a slot having a time value that expires at the determined current time. All timers in the determined slot having a timeout value expiring at the current time are then dequeued.
In further embodiments, the decrementer is set to a time value associated with one slot including at least one timer that will expire before the time values associated with other slots including timers.
In still further embodiments, a first wheel includes one slot for each time value, and a second wheel includes slots that each include a number of time values equal to all the slots in the first wheel. Yet further, a third wheel may be provided that comprises an overflow wheel that includes slots that each include a number of time values equal to all the slots in the second wheel. The overflow wheel slots are capable of including timers having timeout values that remain in the overflow wheel more than one rotation of the overflow wheel.
Preferred embodiments provide a timing wheel implementation for queuing timers from application programs that minimizes burdens on the processor. In preferred embodiments, the processor only has to respond to specific requests, such as to add a timer, stop a timer, etc., and when a decrementer reaches zero. In preferred embodiments, the decrementer is set to a time value associated with a slot including timers that will expire before the time values associated with other slots in the timing wheels. When the decrementer reaches zero, the processor will be interrupted to process the slot including timers that are due to expire. The preferred implementations improve processor performance over prior art timers where the processor is interrupted on each tick or clock cycle to check for expired timers.
REFERENCES:
patent: 5091872 (1992-02-01), Agrawal
patent: 5297275 (1994-03-01), Thayer
patent: 5491815 (1996-02-01), Basso et al.
patent: 5768572 (1998-06-01), George et al.
patent: 5781769 (1998-07-01), Weber
patent: 5838957 (1998-11-01), Rajaraman et al.
patent: 6125404 (2000-09-01), Vaglica et al.
patent: 6360329 (2002-03-01), Kinkade
G. Varghese et al., “Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer-Facility”, IEEE/ACM Transactions on Networking, vol. 5, No. 6, Dec. 1997.
IBM, “Book E PowerPC Architecture Enhanced for Embedded Applications”, Version 0.86, May 3, 1999, Chap. 11, pp. 311-329.
LandOfFree
Method, system, program, and data structures for managing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, program, and data structures for managing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, program, and data structures for managing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240223