Channels ▼
RSS

Design

An embedded Single Timer Wheel



A timer wheel is an efficient timer facility that supports the typical timer features -- start a timer, stop a timer, expire a timer, and query a timer. The benefits of a timer wheel include:

  • It can support a large number of timers.
  • It supports single-shot and repeating timers.
  • It is efficent, starting and stopping a timer is on the order of 1, O(1)
  • It is scalable. The wheel size can be configured to an optimal number of timer queues.
  • It does not require hashing or sorting overhead.
  • Its memory requirements are minimumal.
  • Multiple timer wheels can be integrated into a system, each independent of the others.

The embedded Single Timer Wheel (eSTW) I present here is a timer wheel facility that can be used at task and interrupt level. The number of wheel spokes is user configured. The timer granularity is determined by the task signal or hardware interrupt source

The start timer API allows a single-shot timer and a repeating timer. When a timer is started, the user specifies the initial duration, repeating duration, the call-back function to be invoked when the timer expires and a persistent parameter that is passed to the user's call-back. The source code for this timer wheel can be downloaded from Dr. Dobb's here or from SourceForge.

Definitions

Timer Wheel is a data structure that consists of multiple queues. The unit of time between each queue is constant.

Single-Shot Timer is a timer that is started to expire one and only one time.

Spoke refers to a queue of the timer wheel.

Repeating Timer is a timer that is started to automatically restart after each expiration.

Rotation is a complete rotation around the wheel where all queues have been processed.

Granularity is the unit of timer between each spoke. Granularity is measured in time units, typically milliseconds.

—[B.B.]

The unit of time between each queue or spoke is the equal and constant. The queue scheme is a very efficient scheme to start and stop a timer. For timers that have a duration longer than the rotation time, the rotation count will be decremented when its queue is selected and left for the next rotation. This will continue until the rotation count is zero, indication that the timer has expired.

The timer wheel is optimized to support embedded timer structures, where the timer data structure is integrated into the structure it is associated with. When the timer is started, the structure is queued to the appropriate timer wheel queue.

The timer wheel tick may be driven by a task loop or by a hardware interrupt. It is possible to have multiple timer wheels in the system. One could be a general-purpose timer while another could be dedicated to a specific application.

Here is a list of APIs:


/*
* Starts a new timer.  If the timer is currently running,
* it is stopped and restarted anew
*/
extern RC_STW_t
stw_timer_start(stw_t  *stw,
           stw_tmr_t  *tmr,
            uint32_t   delay,
            uint32_t   periodic_delay,
       stw_call_back   user_cb,
               void   *parm);


/*
* stops a currently running timer
*/
extern RC_STW_t
stw_timer_stop(stw_t *stw, stw_tmr_t *tmr);


/*
* Timer Wheel tick handler which drives time for the specified wheel
*/
extern void
stw_timer_tick(stw_t *stw);

The timer wheel uses a 32-bit duration value. Table 1 provides the longest durations given different timer tick granularities.

Table 1: Timer tick granulatrities. (milliseconds per day [1000 * 60 * 60 * 24]).

The design of the timer wheel (Figure 1) consists of a number of queues or spokes that are evenly spaced in time. With each tick, the timer wheel advances in a modulo fashion to the next queue or spoke. Every active timer on the spoke is set to expire on this tick. If the timer's rotational count is non-zero, the rotational count is decremented and left on the queue for the next turn. If the rotational count is zero, the timer is expired. Expiring a timer is simply invoking the user call-back function.

Figure 1: Timer wheel design.

Timer Wheel Demo

The timer wheel demo uses a single periodic Linux alarm signal to drive the timer wheel.


   /* 
    * Install the interval timer_handler as the signal handler for SIGALRM. 
    */
   memset (&sa, 0, sizeof (sa));
   sa.sa_handler = &timer_handler;
   sigaction (SIGALRM, &sa, NULL);

This function is envoked as result of the sigalrm to drive the timer wheel:


  static void timer_handler (int signum)  
  {
      stw_system_timer_tick();  
  } 

For More Information

www.ibm.com/developerworks/aix/library/au-lowertime/

citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1519


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video