7

I would like a language-agnostic description of how to implement a timers library, where the library user can start timers (possibly many active at the same time), passing callbacks that should be run when the corresponding timer completes. It should allow to stop and start timers and check if they are still running.

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.

I'm specifically looking for a solution which

  1. is robust to timers being started / stopped while processing a timer expiry callback
  2. allows timers to be started, stopped and checked quickly
  3. has a small memory footprint
Improve this question
4
  • 2
    What language should the solution be in? Commented May 15, 2009 at 8:53
  • 1
    I am more interested in the algorithm than the implementation. If it helps you to know I would most likely implement it in C. Regards Commented May 15, 2009 at 9:16
  • when you mention checking if timers are still running, do you mean on a per-timer basis? or just if any timers are still running? is a timer still "running" if it is stopped? do you need this to be thread-safe? what is "Ns"? "who" kicks the module to check for for expired timers? for what purpose? to prompt it to run callbacks for expired timers? Commented Aug 29 at 8:32
  • 1
    can you give an example of what kind of issue you want to prevent when you say "robust to timers being started / stopped..."? what would you want to be the expected behaviour if a callback tries to stop another timer that has expired but whose callback hasn't been run yet? Commented Aug 29 at 8:34

3 Answers 3

Reset to default
13

The 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 and JBoss, and I am sure elsewhere too that you can use, if you are writing in Java.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

The referenced paper discusses different timer algorithms and where they may be appropriately used. Should the link fail in the future then it may be helpful to know the title is "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
Before reading your answer, I was not aware of the NettyIO class HashedWheelTimer, but the implementation appears excellent. No pun intended: Do not reinvent the wheel!
There is also a C implementation here: 25thandclement.com/~william/projects/timeout.c.html
3

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 The high-resolution timer API for details on the Linux implementation, and dig through the Linux source code to see working implementations.

Improve this answer

Comments

1

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

Improve this answer

1 Comment

Hi Kristopher, I'll have a look at these but I am more interested in the algorithm than taking a stock library. Regards

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.