OSDev.org

Suppose we have only one hardware timer two timer users. The first user requests an event be delivered sometime later. Before the event is delivered to the first user, the second user requests a different event delivery.
My question is, how to setup the hardware timer so that we can deliver the two events as accurate as possible while not introduce too much performance overhead? What if we have 200 users instead of 2 users?

Thanks
-torshie

I use delta queue along with a single timer interrupt to dispatch timer events.

Something like this Blocking_Process

Most OSs have a minimum timer resolution that is equal to the period of their timer interrupt. If a thread asks for a timer to expire at a particular time, it will expire at the next timer interrupt after the real time that was requested.

You can keep all unexpired timers in a list in expiry-time order. Each interrupt, you expire all the timers that have passed their expiry time.

There are a number of clever list algorithms that allow the timer insert/delete/expire to approach O(1) without being actually O(1). I quite like the Linux timer-wheel approach. It takes advantage of the fact that many timers actually don't expire and defers the insertion 'til the last minute (or IIRC the last 256 jiffies).

Hi,

torshie wrote:Suppose we have only one hardware timer two timer users. The first user requests an event be delivered sometime later. Before the event is delivered to the first user, the second user requests a different event delivery.
My question is, how to setup the hardware timer so that we can deliver the two events as accurate as possible while not introduce too much performance overhead? What if we have 200 users instead of 2 users?

There's 2 cases. The first case is a "fixed frequency" timer, and the second is a "one shot" timer.

For "fixed frequency timer"; start with a list of events sorted by "when". The timer IRQ handler calculates the new value for "now", then checks the list for all events that have occurred. This is fairly simple (e.g. "while(first_event->time < now) { send_event(first_event); first_event = first_event->next; }" ).

For "one-shot"; start with the same list of events sorted by "when". The timer IRQ handler calculates the new value for "now" and then checks the list for all events that have occurred, the same as before. You also need code to calculate the delay needed for the next event (the time until the "soonest" event or the minimum delay time, whichever is larger) and set the timer's delay. At the end of the timer IRQ handler you'd recalculate the time until the next IRQ and set it. You also need to calculate a new timer value and reset the timer's delay if/when a new "soonest" event is inserted into the sorted list of events.

In both cases, this is only the basic idea and it's possible to do more advanced things. For example, you could use more than one sorted list (e.g. to reduce insertion times); or use a fast timer (for more accurate delays) to emulate a slower timer (that's used for less accurate delays), or...

To start with (for "fixed frequency timer") you'd want to consider power management - you don't want to take the CPU out of its sleep state 1000 times each second for no reason. With this in mind, at a minimum you'd want to consider splitting the sorted list into 2 lists (e.g. one list for events that need to occur in the next few seconds, and another list for events that need to occur after that) so that you don't need to keep the timer running at full speed when there's only one event that won't occur for a very long time.

Note: "fixed frequency" is far less precise, and probably should be avoided if possible. For example, for the PIT, with fixed frequency you'd probably set the PIT to 1000 Hz and end up with delays that have 1 ms precision. With "one shot" you can set the PIT's count to what is actually needed, and end up with delays that come close to 838 ns precision (or roughly 1000 times more precise).


Cheers,

Brendan

The simplest way to solve this is to have a sorted list with timer events. The first element being the earliest expire time.

In order to speed up insertion a red-black-tree is often used. To complicate things even further each timer event have an accuracy. Timer timeouts can this way timeout at the same time, which reduces the amount of costly wake-ups.

This is pretty much the design in Linux after the tick less kernel changes and the introduction of the HP timer.