Efficient Timer Management
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
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.
Efficient Timer Management
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
memory), as shown in the figure. Each
CAMentry 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.
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.
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.
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.
timers are allowed (as will be the case in
protocol implementations, where most timers are used as
retransmission timers), the...