Efficient Timer Algorithm

Question

What is the best algorithm to implement a simple timer library. The library should allow the following:

1. Timers to be started
2. Timers to be stopped
3. Timers to be checked whether they are still running

On Timer expiry a callback function will be called.

The timer module will allow timers to have a time resolution of Ns and the module shall be given a kick every Ns to prompt the module to check for expired timers.

Many timers may be simultaneously active.

The best algorithm needs to meet the following goals

1. Be Robust to timers being started / stopped while processing a timer expiry callback
2. Allow timers to be started, stopped and checked quickly
3. Have a small memory footprint

Regards

Answer 1

Best algorithm I have seen for timers is a timer wheel found in the research paper Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

I know in Java there is an implementation with Netty, JBoss and I am sure elsewhere too that you can use, if you are writing in Java.

Answer 2

Timers are typically best implemented in an operating system kernel, at the assembly/C level, making use of platform-specific features like APIC timers wherever possible.

You might like to look at http://lwn.net/Articles/167897/ for details on the Linux implementation, and dig through the Linux source code to see working implementations.

Answer 3

On POSIX-ish systems, you can use the timer_create/timer_settime family of functions to provide a lot of this "for free."