timer queue – a way to handle multiple timers using one thread

This post introduces a general way to handle multiple timers using one thread using C. K.R.K.C. -daveti

1. what is timer?

The essence of timer is eventually a thread (either Python or Java threads are actually mapped and executed as threads in the OS). For UNIX/Linux, timer is usually created by POSIX Thread lib (pthread). Almost all the multi-thread applications nowadays have timers. Even though the simplest timer may be just sleeping a long time before it wakes up, timers in general, are used so widely that we may ignore the fact that there is timer. The famous example would be the modern time sharing OS, which are based on interrupt, which is timer (either from hardware or software).

2. how to create a timer?

Take a UNIX/Linux system for example. The standard way to create a timer is actually calling pthread_create a new thread. The job of this thread is kind of stupid – sleep some time at first, then wake up to check if it is time for ‘lunch’; if not, sleep again – (my dreamed way of life:) For sure, most of the timers should have much more complicated work to do once the timer expires.

3. how about if we need thousands of timers?

Though the application which needs thousands of timers may sound impractical, there may be that much timers running on a powerful server’s OS providing the support for different applications. As we mentioned before, timer is eventually a thread in the OS. The problem is how many timer can we create on a system. Apparently, the number is not infinity. When you run ‘ulimit -a’ under UNIX/Linux, you will find the max number for running threads supported by this system. Then what if the number of timer are reaching the max number supported by OS? The answer is a lot of timers may fail to wake up timely.

4. engineering way – multiple timers using one thread!

The way to handle the case above is to using timer queue – a queue used to hold all the timers and a thread running and checking if there is any timer expires. Nothing new or fancy here as the method has been widely accepted and widely used by engineers. Detailed implementation could be found here – https://github.com/daveti/tq

5. what is the issue here?

The ridiculous thing of Computer Science (from my understanding) is that Computer/CPU is so precise but our way of using Computer/CPU is so greedy that all we could guarantee is being ‘almost’ instead of ‘precise’. This is the truth for timer sharing OS but real-time OS/system has another story for this. Anyway, my point is we may not guarantee this one-thread timers work as we expect. The tricky thing is the sleeping time of the thread (s) VS. the time of going thru the queues and doing the corresponding work (d) VS. the timers within the timer queue (t). You can imagine mathematical analysis for the 3 variables (I am not gonna do it:) In a word, to make it ‘almost’ work, you have to figure out the right settings for the 3 variables. The good thing here is ‘almost’ is fairly good enough~

About daveti

Interested in kernel hacking, compilers, machine learning and guitars.
This entry was posted in Programming and tagged , , , . Bookmark the permalink.

3 Responses to timer queue – a way to handle multiple timers using one thread

  1. Dexter says:

    I see a lot of interesting posts on your page. You have to spend a lot of time writing, i know how to save you a lot of time,
    there is a tool that creates unique, google friendly articles in couple
    of seconds, just search in google – laranita’s free content source

  2. Marion says:

    It’s hard to find your website in google. I found it on 16
    spot, you should build quality backlinks , it will help you
    to get more visitors. I know how to help you, just type in google – k2 seo tricks

  3. Santiago says:

    I read a lot of interesting articles here. Probably you spend a lot
    of time writing, i know how to save you a lot of time, there is an online tool that creates unique, SEO friendly articles
    in seconds, just type in google – laranitas free content source

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s