What is the best algorithm to implement a simple timer library. The library should allow the following:
- Timers to be started
- Timers to be stopped
- 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
- Be Robust to timers being started / stopped while processing a timer expiry callback
- Allow timers to be started, stopped and checked quickly
- Have a small memory footprint
Regards
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.
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.
On POSIX-ish systems, you can use the timer_create/timer_settime family of functions to provide a lot of this "for free."
