Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink

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 ARTICLES Securing the Java Core Petascale Tools and Genomic Evolution Legal Compliance: Open Source and Quality Assurance SEI, Army Team Up on Software Testing Nozzle: Counteracting Memory Exploits		TOP 5 ARTICLES No Top Articles.