How to implement an asynchronous timer on a *nix system using pthreads

Question

Hi all,

I have 2 questions :

Q1) Can i implement an asynchronous timer in a single threaded application i.e i want a functionality like this.

....
Timer mytimer(5,timeOutHandler)


.... //this thread is doing some other task


...
and after 5 seconds, the timeOutHandler function is invoked.

As far as i can think this cannot be done for a single threaded application(correct me if i am wrong). I don't know if it can be done using select as the demultiplexer, but even if select could be used, the event loop would require one thread ? Isn't it ?

I also want to know whether i can implement a timer(not timeout) using select. Select only waits on set of file descriptors, but i want to have a list of timers in ascending order of their expiry timeouts and want select to tell me when the first timer expires and so on. So the question boils down to can a asynchronous timer be implemented using select/poll or some other event demultiplexer ?

Q2) Now lets come to my second question. This is my main question. Now i am using a dedicated thread for checking timeouts i.e i have a min heap of timers(expiry times) and this thread sleeps till the first timer expires and then invokes the callback. i.e code looks something like this

1. lock the mutex
2. check the time of the first timer
3. condition timed wait for that time(and wake up if some other thread inserts a timer with expiry time less than the first timer) Condition wait unlocks the lock.
4. After the condition wait ends we have the lock. So unlock it, remove the timer from the heap and invoke the callback function.
5. go to 1

I want the time complexity of such asynchronous timer. From what i see

1. Insertion is lg(n)
2. Expiry is lg(n)
3. Cancellation

:( this is what makes me dizzy ) the problem is that i have a min heap of timers according to their times and when i insert a timer i get a unique id. So when i need to cancel the timer, i need to provide this timer id and searching for this timer id in the heap would take in the worst case O(n)

Am i wrong ?

Can cancellation be done in O(lg n)

Please do take care of some multithreading issues. I would elaborate on what i mean by my previous sentence once i get some responses.

Answer 1

If you are a windows App, you can trigger a WM_TIMER message to be sent to you at some point in the future, which will work even if your app is single threaded. However, the accuracy of the timing will not be great.

If your app runs in a constant loop (like a game, rendering at 60Hz), you can simply check each time around the loop to see if triggered events need to be called.

If you want your app to basically be interrupted, your function to be called, then execution to return to where it was, then you may be out of luck.

Answer 2

If you're using C#, System.Timers.Timer will do what you want. You specify an event handler method that the timer calls when it expires, which can be in the class that you invoke the timer from. Note that when the timer calls the event handler, it will do it on a separate thread, which you need to take into account if you're updating the user interface, or use its SynchronizingObject property to run it on the UI thread.

Answer 3

It's definitely possible (and usually preferable) to implement timers using a single thread, if we can assume that the thread will be spending most of its time blocking in select().

You could check out using signal() and SIGALRM to implement the functionality under POSIX, but I'd recommend against it (Unix signals are ugly hacks, and when the signal callback function runs there is very little that you can do inside it safely, since it is running asynchronously to your app thread)

Your idea about using select()'s timeout to implement your timer functionality is a good one -- that is a very common technique and it works well. Basically you keep a list of pending/upcoming events that is sorted by timestamp, and just before you call select() you subtract the current time from the first timestamp in the list, and pass in that time-delta as the timeout value to select(). (note: if the time-delta is negative, pass in zero as the timeout value!) When select() returns, you compare the current time with the time of the first item in the list; if the current time is greater than or equal to the event time, handle the timer-event, pop the first item off the head of the list, and repeat.

As for efficiency, your big-O times will depend entirely on the data structure you use to store your ordered list of timers. If you use a priority queue (or a similar ordered tree type structure) you can have O(log N) times for all of your operations. You can even go further and store the events-list in both a hash table (keyed on the event IDs) and a linked list (sorted by time stamp), and that can give you O(1) times for all operations. O(log N) is probably sufficiently efficient though, unless you plan to have a really large number of events pending at once.

Answer 4

man pthread_cond_timedwait

man pthread_cond_signal