Re: timer implementation

wkaras@xxxxxxxxx wrote:
I'm seeking links/suggestions about the implementation of general
purpose timers. The usage of the timers would look something like:

id = start_timer(wait_time, func_called_when_time_up);
stop_timer(id);

There would also be a function called by the system timer tick, which
would call functions passed as "func_called_when_time_up" as
appropriate. (It's assumed the calling code handles all mutual
exclusion issues that may result from the time-ùp function being
called. There would also likely be some way to pass id-specific data
to the time-up function, but I don't think that would impact the broad
outlines of the design.) I'm looking for an approach that could scale
to 100s or more timers.

So far the best approach I can think of is to keep the timers in an AVL
tree where (absolute) expiration time is the search key. The big plus
is controlled worst-case behavior. Is there an approach that has at
least O(log n) worst-case and O(1) average time for both stopping a
timer and the case where the timer runs to expiration?


This usually is done in a list where only the difference
to the next timer is stored. so when decrementing the first
timer, all timers are automatically decremented as well.

Rene
--
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net
.

Relevant Pages

  • Re: [PATCH 2/2] Char: timers cleanup
    ... Use timer macros to set function and data members and to modify ... expiration time. ... the timers are only used if the watchdog is active. ... Why should we not init them at run time but use the DEFINE_TIMER macro? ...
    (Linux-Kernel)
  • Re: timer implementation
    ... The usage of the timers would look something like: ... A priority heap works well for this, but any balanced tree can do some rebalancing on removal, so can't have Oremoval time. ... When you stop a timer, you can either adjust the tree/list at that point, or wait for the old expiration time and discard. ...
    (comp.arch.embedded)
  • timer implementation
    ... purpose timers. ... The usage of the timers would look something like: ... tree where expiration time is the search key. ...
    (comp.arch.embedded)
  • Motorola 750
    ... noticing that when I hit View Timers they did not match up. ... Timers shows 1 hour and 45 minutes or more that does not match the ... make a good way to check on usage? ... Just Passing on for info. ...
    (alt.cellular.verizon)