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?


Assuming you have a fixed tick on which you will dispatch timer events,
a slightly different (and more-or-less O(1)) approach is to store your
timers in buckets (using a simple linked list for each bucket), the
bucket being selected based on when the timer fires.

Start with 128 buckets of one tick each. These are the highest
resolution items, and on each tick you just fire all the events in the
next bucket. If you set a timer that fires within the next 128 ticks,
that's all there's to it. Next you have a set of 128 buckets, each
covering 64 ticks. These are all longer timers than in the first set.
Once every 64 ticks, you grab the next bucket from the second tier, and
redistribute all of the items in to the first tier buckets, where
you'll eventually dispatch them.

You repeat that out to the longest intervals you want to time, with
subsequent tiers of buckets covering 4096, 256K, 16M, 1G... ticks each.
Seven tiers of buckets and 1ms ticks covers you for 250+ years, and
timers longer than a couple of years would actually get moved six times
in their lifetime.

Each timer is processed exactly once if it's set to expire in the next
128 ticks, longer timers are also copied once for each tier of buckets
their from the first (aka lg(ticks)/6). Adding timers into the first
tier is a simply range check and a divide by 128 to find the bucket and
an add into the linked list. Into higher tiers the range check is a
bit more complex, but it still just a basic indexing operation to
determine where it goes.

Obviously there's nothing magic about 64 as a factor. Smaller
buckets will reduce the number of list heads, but increase the number
of moves.

FWIW, the work per timer is effectively O(log t), where t is the
duration of the timer, and is not dependant on the number of timers at
all. Since that's always going to be a very small number, it's
effectively O(1).

.

Relevant Pages

  • Re: [ANNOUNCE] ktimers subsystem
    ... >> is to demonstrate the future use of ktimers and the simple extensibility ... >> for the impelemtation of high resolution timers. ... independent of timer ticks, ... jiffies. ...
    (Linux-Kernel)
  • Re: incorrect usleep/select delays with HZ > 2500
    ... Returned value meets or exceeds requested time. ... those have to be divorced from ticks. ... Even when other timers are available?). ... timing needs such as protocol timeouts and sleeps. ...
    (freebsd-stable)
  • Re: timer implementation
    ... The usage of the timers would look something like: ... Start with 128 buckets of one tick each. ... If you set a timer that fires within the next 128 ticks, ... Once every 64 ticks, you grab the next bucket from the second tier, and ...
    (comp.arch.embedded)
  • Re: PROBLEM: high load average when idle
    ... happen when the timers get rounded: ... LT> calculated every LOAD_FREQ ticks. ... LT> Anders - does this idiotic patch make a difference for you? ... I can easily imagine that the rounding code tends to try to ...
    (Linux-Kernel)