Firm Timer Implementation – Georgia Tech – Advanced Operating Systems

Firm Timer Implementation – Georgia Tech – Advanced Operating Systems


As you know, in Linux they use the term task to signify a schedulable entity. And so, we’re using T1, T2, T3, to mean tasks, which are schedulable entities. And the timer-q data structure, what it contains is the tasks and the expiry time for that particular task. And the tasks are ordered in this Timer-q data structure maintained by the kernel, sorted by the expiry time. So task T1 is the earliest task to go off. Because it has the earliest expiry time. T2 is next, with an expiry time of 12. T3 with an expiry time of 15 and so on. So this is the way the kernel is maintaining the data structure to know when a particular task’s expiry time is up for processing the event associated with that particular task. The basis for firm timer implementation is the availability of APIC hardware. APIC is advanced programmable interrupt controller, which is implemented on chip in modern CPU starting from Intel Pentium onwards, and the firm timer implementation in TS-Linux takes advantage of the APIC hardware. The good news is with the APIC timer hardware, re-programming a one shot timer takes only a few cycles. So there is not a significant overhead to re-programming a one shot timer on modern CPUs because of the availability of the APIC hardware. So if the task that is at the head of the queue, that had it’s timer event go off, if it has to be reprogrammed, all that we need to do is execute a few instructions in modern processes to reprogram that one shot timer to go off at the next one shot interval. When the APIC timer expires, the interrupt handler will go through this timer-q data structures and look for tasks whose timers have expired. Some of these tasks may be periodic tasks, some of these tasks may have been programmed to deal with the APIC timer event. So, associated with each entry in this timer queue data structure is the callback handler for dealing with that particular event. And those callback handlers are going to be called by the interrupt handler upon the expiry of the APIC timer. The expired timers are going to be removed from those timer queue data structures. If the entry corresponds to a periodic timer, then the handler will re enqueue that particular task in the timer queue data structure after updating its expiry field for the next periodic event for that task. If it is a one shot timer that this task was using. In that case, the interrupt handler will reprogramme that task for the next one short event. The way the APIC timer hardware works is by setting a value into register which is decremented at each memory bus cycle until it reaches zero. At which point it’ll generate an interrupt. Now given a 100 megahertz memory bus, for instance, on modern CPUs, a one short timer has a theoretical accuracy of ten nanoseconds. However, in practice, the time needed to feel the timer interrupt is significantly higher. And that becomes the limiting factor in the granularity that you can get with one shot timers implemented using the APIC hardware. But the important point is that APIC hardware allows you to implement very fine grained timers in modern processes. And as I already mentioned, by choosing an appropriate overshoot parameter in reprogramming the epic timer. We can eliminate the need for fielding one shot interrupts, because of soft timers going off within that overshoot period. Another optimization that we can do, in the firm time at implementation, is looking at the distance between one shot events. For instance, in this picture I’m showing you, the long distance between two one shot events. There is a one shot event happening here. There is a one shot timer event happening here. Another one shot timer event happening here. And if you have such a long distance, it is possible that there may be several periodic timer events that may be going off within this long distance. So this suggests that if periodic events are going to go off, and if it is close enough to a one shot timer that would have gone off, why not take advantage of that? So what we want to do is dispatch a one shot event at a preceding periodic event. The key thing for time sensitivity is not missing the timer event. If you’re going to process it a little bit sooner, that’s okay. So that’s exactly what is happening here. Just as in the case of the overshoot parameter being used in combing one shot to the soft timer. What we’re doing here is, because periodic timers are going to interrupt anyhow and if the kernel notices that there is a one shot event that is coming up fairly soon, then it can simply dispatch that one shot event at the preceding periodic timer event that is any how accepting the processor. And once you do that, then you can reprogram this one shot event to go off at the next expiry point for that one shot event. So basically, what we’re doing when we have a long distance between one shot events, is to use a preceding periodic timer event, so that we can both avoid the overhead of dealing with this one shot event. And also the cost of reprogramming it. Or in other words, we completely eliminate using one shot events for situations where the distance between the one shot events is so big that we can simply use the periodic event instead of the one shot event. And the reasons for doing that are twofold. One is, periodic event data structures are much more efficient than the kernel, they’re order of one data structures. Whereas, the one shot event programming data structures in the kernel. Tends to be order of log n, where n is the number of active timers. So as an optimization, if the one shot events happen at fairly long distances. That there are several periodic events that are going to happen anyhow within that. We will simply use the periodic timers instead of the one shot timer. So to summarize, the firm timer implementation. The first point is that the APIC hardware allows reprogramming one shot timers in few cycles. And secondly, by choosing the appropriate overshoot distance, we can eliminate the need for fielding the one shot timer interrupts if soft timers go off within that overshoot period. And third, if the distance between one shot timers is really long, then instead of using one shot timers, we will simply use periodic timers and dispatch the one shot event at the preceding periodic timer event. Those are the ideas that are enshrined in the firm timer implementation in TS-Linux, that essentially combines the advantages of one shot timer with soft timers with periodic timers. So this should give you a feel for how TS-Linux, by a clever implementation, reduces the timer latency, the first component of the latency from the point of event happening to event activation.