Browse Prior Art Database

Efficient Timer Management

IP.com Disclosure Number: IPCOM000120047D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 5 page(s) / 149K

Publishing Venue

IBM

Related People

Heddes, M: AUTHOR

Abstract

Disclosed are two methods to manage a large number (order of thousands) of timers. The latency of the timer primitives Start, Stop and Tick is independent of the number of outstanding timers.

This text was extracted from an ASCII text file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient Timer Management

      Disclosed are two methods to manage a large number (order
of thousands) of timers.  The latency of the timer primitives Start,
Stop and Tick is independent of the number of outstanding timers.

      The methods are both based on a

CAM

(content addressable
memory), as shown in the figure.  Each

CAM

entry manages one timer.
An entry consists of three fields: the data field which contains an
interrupt vector, a tag field which contains the absolute wakeupTime
(that is, the time at which the timer expires), and an active bit.  A
timer is started by storing its wakeupTime via multiplexer (mux) 2
and its vector in the CAM 1 and setting its active bit.  A timer is
stopped by clearing its active bit.

      For timer expiry checking it is initially assumed that
compareReg 4 ontains the same value as clockValue 5, as is the case
after a reset.  The contents of compareReg 4 is via mux 2 applied to
the CAM 1 as the search argument.  If any of the wakeupTimes
contained in the CAM 1 equals this search argument, a hit occurs and
the value of the vector appears on the data output of the CAM 1.  The
controller 6 applies this vector together with an event signal to the
user and clears the activeBit.  If no other hits occur and compareReg
4 does not equal clockValue 5 (during event generations, several
clock-ticks may have occurred), controller 6 increments compareReg 5
and the search for timer expiry starts again.
Method 1

      The scheme described above is extended to support more timers.
Each CAM entry is now used to manage an ordered timer list  (ordering
with increas ing wakeup time).  A timer list consists of
timerRecords, each record holding the status of one timer and
containing the absolute wakeupTime, event vector and two pointers (to
have the list doubly linked).  The lists can be implemented in
external memory and the list management, mainly consisting of load
and store operations in the external memory, is done by the
controller.  The wakeup time of the first timer in the list is stored
in the tag field of the CAM entry (and thus compared with the clock),
while the data field of the CAM entry contains a pointer to the
timerRecord of this timer.

      By convention, each list is used for timers with the same
length (duration).  Thus, a timer is started by appending its
timerRecord to the end of the list reserved for timers with this
length, which can be done in order 1. As a timer list is doubly
linked, a timer can be stopped in order 1.  The number of different
timer lengths is limited by the number of CAM entries, and the
maximum number of timers is limited by the amount of external memory.
Method 2

      If inaccurate timers are allowed (as will be the case in
protocol implementations, where most timers are used as
retransmission timers), the...