Re: timer implementation


Jonathan Kirwan wrote:
On 14 Aug 2006 15:21:13 -0700, 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?

Without getting into exactly why you want to do all this, especially
the question about 'why' considering that you are sweeping a lot of
important details under the rug of "calling code handles all mutual
exclusion issues" and obviously aren't then thinking clearly about
this, there is a short answer you may be able to like: delta queues.

Usually, your timer tick is pre-emptive. (In your case, I can assume
you are asking this without having an existing O/S, since an O/S
usually provides this service even if it does little else.) Since
it's pre-emptive and the test happens as often as your tick takes
place, the usual desire (at expense of other desires) is to make the
testing for whether or not to launch a function call (or process) as
fast as possible. Timer events eat up available CPU, so that is
usually an important consideration. A lookup tree is not as fast as
can be done, in that regard.

If you choose a means to insert into your queue in this method:

: void qnodeptr_t (qinsertd)( queueptr_t queue, qnodeptr_t node, qsleepkey_t key )
: /* --------------------------------------------------------------------------
: Link the given node into the given queue, as a delta-key entry. Here, the
: key is a time delay. The first entry in the queue has the least time to
: remaining to wait.
:
: As the list of processes are scanned from first to last, the time value of
: nodes earlier in the queue are subtracted from the current, desired delay.
: In this way, the current delay being tracked only holds the time remaining
: after the earlier processes have exhausted their time delays. Once the
: right insertion point is found, the remaining time left on this current
: delay value then used as the key for the entry to be inserted. So at this
: point, the node is inserted and the time value for the next entry which
: then follows it is updated.
: */
: {
: auto qnodeptr_t prv, nxt;
: auto qsleepkey_t nxtkey;
:
: prv= qheadptr( queue );
: for ( nxt= qnext( prv ); (nxtkey= qsleepkey( nxt )) < key; prv= nxt, nxt= qnext( nxt ) )
: key -= nxtkey;
: if ( nxt != qtailptr( queue ) )
: qsetsleepkey( nxt, nxtkey - key );
: qsetsleepkey( node, key );
: qsetprev( node, prv );
: qsetnext( node, nxt );
: qsetprev( nxt, node );
: qsetnext( prv, node );
:
: return node;
: }

I'm not expecting you to know all the details, but just to see some
real code that actually does the job with a delta queue so that you
can work through any failures on my part to adequately describe it.

But with this method, your timer tick does NOT need to look at all the
various things waiting for time, but instead only the top entry. As
you count down the time on that entry, and since all the other entries
are relative to it, you also count down all the rest of them, too.
When you get to the point where the top entry counter goes to zero,
you run it and also any following ones that also have zero-key values
(they are to be run at the same moment, if so.)

Hope that helps,
Jon
Jon

The concern I have with this approach is that starting a timer has
time complexity O(n) worst-case, whereas the AVL tree approach
has O(log n) worst-case.

.

Relevant Pages

  • Re: Do I need a RTOS?
    ... You pointed out the basic idea of having a regular timer (you ... exists and that delta queue insertion is already implemented [to be ... insertdq(SetPinHigh, 150); ... entry from the queue and executes the function. ...
    (comp.arch.embedded)
  • Re: VB6 Application Overwhelmed by Rapid User Interaction
    ... entry the application behaves fine. ... store the new row index in a queue, you could use a timer to read ... the queue and display the data. ... The timer could be set at a rate that will not overwhelm the system, ...
    (microsoft.public.vb.winapi)
  • Re: timer implementation
    ... timer and the case where the timer runs to expiration? ... your timer tick is pre-emptive. ... Link the given node into the given queue, as a delta-key entry. ... The insertion time usually isn't the critical side of it, ...
    (comp.arch.embedded)
  • Re: VB6 Application Overwhelmed by Rapid User Interaction
    ... entry the application behaves fine. ... store the new row index in a queue, you could use a timer to read ... the queue and display the data. ... A similar approach is to disable and reenable a timer when a row is selected, then in the timer event, just get the latest row. ...
    (microsoft.public.vb.winapi)
  • Re: How to make time limited function?
    ... I have no experience with delimited continuations, ... If your timer hasn't expired yet you can go on to start ... [If you don't have timers you can calculate the abort time on entry ... When the timer expires, ...
    (comp.lang.lisp)