Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis
Reexamination Certificate
2000-06-22
2004-05-04
Lee, Thomas (Department: 2185)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
C713S502000
Reexamination Certificate
active
06732287
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the art of timer processing, and more particularly to a method for processing dynamically allocated timers in a real time operating system.
BACKGROUND OF THE INVENTION
Most real time processing applications employ dynamically allocated timers for various purposes. In communications processing applications, for example, timers are utilized to verify that messages are processed in a reasonable amount of time. Dynamically allocated timers are activated and deactivated as the need for them arises while communications and real time data are being processed.
Dynamic timers include watchdog timers as well as timers which run to completion. Watchdog timers are started, and then generally retriggered frequently before timeout. These timers may be useful for ensuring a program or other activity performs some action before the timer expires. For example, a program may activate a watchdog timer prior to calling a subroutine, and may retrigger the watchdog timer upon return from the subroutine. If the subroutine runs normally, the watchdog is retriggered before it times out. However, if the subroutine gets caught in an endless loop situation, or otherwise does not finish in a reasonable time, the timer will time out or expire. The timer may be configured to alert the program to the excessive time taken by the subroutine or to take some other remedial action.
Other timers are started, run to completion, and then are either deactivated or restarted. These timers may be used in a program to ensure that an external event has completed. As an example, it may be desirable to read a data value from an analog to digital converter every 20 milliseconds. In this situation, a timer may be employed to notify a program to perform a data read from the converter at the expiration of a 20 millisecond timer. The timer may be restarted each time it expires in order to provide a periodic signal to the program.
Dynamically allocated timers are usually based on timing signals from clocks or other system components. A timeout duration associated with a timer may be expressed in counts, which represent an integer number of such system timing signals. For example, a microprocessor or other real time processing system may include a free running hardware timer which provides a signal to an operating system or other program, every 1 millisecond. The program may execute a timer processing routine every time the free running timer provides a signal. Timers can be activated by placing an integer count value in a memory register, representing the timer duration in milliseconds. Each time the timer service routine runs, the count values for the active timers can be decremented, and when the count value reaches zero, the timer has expired or timed out. Appropriate action can then be taken.
Several methods of processing timers have heretofore been implemented in real time processing systems. Generally, the active timers are placed into an active timer list, which may include a timer number or other identifier, a timer duration count (usually expressed as an integer), and a pointer to a service routine to be processed if and when the timer expires. The list may be unsorted or may be sorted according to duration, wherein the list must be sorted each time a new timer is activated. Whether sorted or unsorted, each time the timer processing routine runs (e.g., each time the free running timer provides a signal), the timer duration count value for each timer in the list must be decremented. If any of the count values reach zero, the timers associated therewith have timed out or expired, and the service routine associated with those timers is executed.
Where the list is unsorted, each count value in the list must be interrogated every time the timer processing routine runs, to determine if any timer has timed out. Alternatively, where the list is sorted in advance (e.g., each time a timer is added to the list) according to timer duration, only the first count value must be checked each time the timer processing routine runs. If the first count value is non-zero, no timers have timed out, and the processing is complete. However, if the first timer has timed out, the next count value in the list must be tested. This continues until a non-zero value is found, at which time the timer processing routine is finished.
Timer processing involves system overhead. Such overhead includes processing time while the timer processing routine is running, as well as when timers are added, retriggered, deleted, or when timers time out. Sorted lists require less processing overhead than unsorted lists during the timer processing routine, but involve high overhead when timers are added, because the list must be resorted. Unsorted lists require somewhat less overhead when timers are added, but greater overhead during the timer processing routine. In either case, the timer processing routine must decrement each count value entry every time the timer processing routine runs, and consequently, the processing overhead increases with the number of entries in the list.
Another previous timer processing method includes maintaining a counter which is incremented each time the timer processing routine is run. When a timer is added to the list (e.g., activated), the counted value is added to the timer duration count value for the new timer, and the result is placed in the list. Each time the timer processing routine runs, each entry in the list is compared with the current counter value, and when they are equal, the timer has timed out. This method does not require decrementing timer list entries each time the timer processing routine runs, however, the overhead is increased when timers are added to the list. Thus, conventional timer processing methods generally require greater processing time as the number of active timers increases, both during the timer processing routine, and when new timers are activated. However, it is precisely when the most timers are active, that the least timer processing overhead is desired.
Dynamically allocated timers in a real time processing environment may be of many different durations. Short duration timers are generally run to completion timers, whereas medium and long duration timers are a mix of run to completion timers and watchdog type timers. Conventional timer processing methods are somewhat efficient for handling timers of a certain duration and inefficient for other duration timers. Due to the dynamic environment of most real time processing applications, it is impossible to predict the mix of short, medium, and long duration timers which may be active at any given time. For example, in communication processing systems, messages from external devices may randomly occur in large numbers at certain times. Accordingly, conventional methods are less than optimal for efficiently processing timers in many real time applications.
SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a method of processing dynamically allocated timers in a real time processing system which requires minimal system overhead in processing both run to completion and/or watchdog type timers, of a variety of durations. The invention further provides reduced overhead associated with both timer processing routines, and with activation or addition of new timers, which is achieved for large as well as small numbers of active timers. The present invention is therefore ideally suited to real time processing applications, such as communication processing systems, wherein timers of a variety of durations are dynamically allocated randomly, and sometimes in large numbers. The invention finds further utility in association with operating systems. A method for processing dynamically allocated timers is provided, having low processing overhead for the common and frequent operations while maintaining a low and fairly constant processing overhead as the number of active timers increases.
In accordance with one aspect of the invention, separate unordered timer lists are maintained ac
Laitinen Stephen
Siorek Timothy
Amin & Turocy LLP
Gerasimow Alexander M.
Lee Thomas
Rockwell Automation Technologies Inc.
Speroff R. Scott
LandOfFree
Method for processing dynamically allocated timers in a real... 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 for processing dynamically allocated timers in a real..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for processing dynamically allocated timers in a real... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3265882