Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis – Counting – scheduling – or event timing
Reexamination Certificate
2000-07-12
2002-03-19
Butler, Dennis M. (Department: 2787)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
Counting, scheduling, or event timing
Reexamination Certificate
active
06360329
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates in general to the timing of intervals in a computer and more specifically to a system providing an interval timing service for processes running in a computer system.
Different types of interval timers can be found in alarm clocks, egg timers, or timers in VCRs. Interval timers are used to cause an alarm or other pre-determined action to occur after a pre-specified amount of time. Within computer systems, interval timers are used in communications over networks, such as for re-transmitting a packet of communications data when a response does not arrive within the expected amount of time. Interval timers are also used in interactions with hardware devices, for error detection and handling, for detecting and handling failures within fault-tolerant systems, for pacing the rate at which displays are updated, in interactions with human beings, for dividing “CPU time” equitably among computer processes, and for a wide variety of other uses.
Some computer systems require the maintenance, or scheduling, of many events that are controlled by an interval timer or timers. Various schemes have been adopted to improve the efficiency of such timers and scheduling because the processing overhead required to update the timers and handle the events can become significant and degrade the ability of the computer to handle other tasks. An example of an approach to handling multiple timers is described in a paper by G. Varghese and T. Lauck entitled “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility,” Proceedings of the Eleventh ACM Symposium on Operating System Principles, 8-11 November 1987, Operating System Review 21 (5), ACM Press, 1987, ISBN 0-89791-242-X.
The system described by Varghese and Lauck, places emphasis on a “Timer Start” function. In accordance with Varghese and Lauck the timing method can be described by use of a hierarchy of timing wheels using “hours” “minutes” and “seconds” wheels to time delays of up to 24 hours with one-second resolution. This could be part of a larger hierarchy of timing wheels, allowing timing, for example, for up to 16 weeks.
For example, Varghese and Lauck consider the case where the current time is 10:24:30 and an interval of 50 minutes and 45 seconds is to be timed.
In the following:
curTime is the current time, or some regularly updated similar value. Since we are only interested in measuring intervals of time, curTime need not be the same as the true current time, it only needs to be advancing at the same rate. Also, it need not be directly updated by timing hardware, but it must be possible to access the timing hardware in order to learn the correct value for curTime.
timeoutValue is the specified amount of time to elapse before the timer expires.
expirationTime is the time at which the timer is to expire, if not previously canceled. That is, the timer expires when curTime becomes equal to expirationTime.
The method for Timer Start is one of first computing the expiration time, and then enqueuing (chaining) the timer on the most-significant wheel for which the expiration time differs from the current time:
curTime is
10:24:30
timeoutValue is
00:50:45
expirationTime is
11:15:15
According to this prior method, the timer will be chained on the hours wheel in slot
11
. This happens because expirationTime differs from curTime in the hours position, and the hours portion of expirationTime is 11.
Then, if the client doesn't cancel the timer, at 11:00:00 the timer will be moved to slot
15
of the minutes wheel. At 11:15:00, the timer is moved again, to slot
15
of the seconds wheel. The timer finally expires at 11:15:15 and is no longer on any slot of any timing wheel, until it's re-used to time another interval of time.
Although Varghese and Lauck describe a relatively efficient timer processing mechanism, it is desirable to provide a timer system that further reduces the processing required by a computer to operate and maintain the timers.
SUMMARY OF THE INVENTION
The present invention provides a timer system that uses less computer time than previous processes and methods, leaving more computer time available to do other work. Multiple timing wheels are maintained with slots associated with each wheel. In one embodiment, a process, event, or other item that needs to be timed is scheduled on a slot on a timing wheel according to the timeout value of the item. In another embodiment, the wheels have a maximum timeout value associated with them. The maximum timeout value is used to schedule the item. In another embodiment, the maximum timeout value for a wheel is increased to be an integral multiple of the period of the wheel before scheduling according to the maximum timeout value is performed.
REFERENCES:
patent: 5768572 (1998-06-01), George et al.
patent: 5838957 (1998-11-01), Rajaraman et al.
patent: 6115826 (2000-09-01), Kinkade
Varghese, et al., “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility,” ACM, 1987, pp. 25-38.
Butler Dennis M.
Oppenheimer Wolff & Donnelly
Sherry Leah
LandOfFree
Interval-timing facility using overbuilt hierarchical timing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interval-timing facility using overbuilt hierarchical timing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval-timing facility using overbuilt hierarchical timing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844460