Efficient Design of High-Resolution Timekeeping in Real-Time Operating Systems

A tick-based timing subsystem derives its name by the use of a single hardware timer to trigger a periodic interrupt, whose Interrupt Service Routine (ISR) is used to perform the timekeeping operation. In this paper, we refer to this periodic timer ISR as the tick ISR. In a tick-based timing subsystem, time is kept by means of a software variable in the kernel that is incremented every time the tick ISR is executed. This variable can have different names in different kernels, here we generically call it the tick counter. A typical tick ISR period is 1 kHz, resulting in the time kept by the operating system having a 1 millisecond resolution. Operating systems expose time to applications by means of an API call allowing them to query the current value of the tick counter.

In addition to incrementing the tick counter, the tick ISR is also used to handle the wakeup of sleeping tasks. The sleeping operation is fundamental especially for real-time systems which often involve periodic tasks of different priority levels, which are implemented by alternatively performing computation and sleeping till the next period. Indeed, an important part of the timing subsystem in an operating system involves efficiently handling tasks that need to sleep either for a given amount of time, or until a specified absolute time is reached. The sleeping status of a task is typically recorded by the kernel in a flag in each Task Control Block (TCB) so that sleeping tasks become ineligible for scheduling, freeing CPU time for other tasks. The wakeup time of all sleeping tasks is recorded in a separate data structure, such as a list of sleeping tasks ordered by absolute wakeup time, and the tick ISR is also used to check whether some tasks need awakening. Awakened tasks are removed from the sleeping data structure, and their sleeping flag in the TCB is reset, making them again eligible for scheduling. Finally, current real-time operating systems are predominantly preemptive. Every time a task is scheduled, a time limit is given, after which the scheduler reconsiders its past decision, possibly running a different ready task of the same priority instead. Of course, should a higher priority task become ready at any point in time, preemption would occur immediately without waiting the time limit. This time limit is given different names in the literature, in this paper we will call it time quantum. It is the task of the scheduler to set this timeout after each scheduling decision. In tick-based timing subsystems, the expiration of the time quantum is also taken care of by the tick ISR. This is done by using a counter variable, or by having the time quantum be fixed and equal to the tick period – in this latter case the tick ISR will call the scheduler every time. A simplified implementation of a tick-based timing subsystem is reported in Appendix A, Listing 1.

The tick-based timing subsystem described so far is currently a popular choice in real-time operating systems for microcontrollers due to the combined advantages of simplicity and low overhead. However, it suffers from several shortcomings that are becoming progressively more significant due to the recent trend towards the increase in computational power of microcontrollers.

Inherent tradeoff between timing resoution and tick ISR overhead. In a tick-based timing subsystem, incrementing the tick counter is done in software as part of the tick ISR. As such, increasing the timing resolution also increases the overhead, due to the tick ISR interrupting applications and the rest of the operating system more frequently. Indeed, to keep time at 1 millisecond resolution, the tick ISR already needs to be called 1000 times per second. Should the time resolution be increased to microsecond-level or better, one million tick ISR per second or more would be required. It is clear that regardless of the amount of code optimization poured into the tick ISR code, the overhead would be unacceptably high at best, or even overload the entire CPU leaving no time to run the rest of the operating system and applications. As such, a tick-based timing subsystem is incapable of meeting high-resolution time measurement requirements. Examples of such requirements include profiling code execution [8], and timestamping network packets to implement clock synchronization algorithms in distributed systems [18].

Poor compatibility to fast periodic tasks. The time resolution of the timing subsystem also sets the minimum achievable sleep interval a task can perform, and thus the minimum period of real-time periodic tasks. While millisecond-resolution timekeeping was acceptable in the past, modern microcontrollers are increasingly high-performance. Pushed by the increasing complexity of embedded software, microcontollers with CPU clock speeds from 500MHz to 1GHz are now common [2]. It is thus no longer inconceivable to have periodic tasks with sub-millisecond periods when it benefits the application requirements. As such, tick-based timing subsystems are becoming a limitation that prevents fully unleashing the capabilities of modern microcontrollers.

Poor code portability as the tick resolution is changed. The reason why 1 millisecond is currently the de facto standard for timekeeping resolution in tick-based timing subsystems, is that it is achievable with an acceptable overhead, and keeping time in milliseconds is reasonable at the application level. While a tick-based timing subsystem could be adapted to have a different tick period, such as 200$\mu$s to support periodic tasks up to 5kHz, application code would need to be adapted to the new tick resolution, introducing a cognitive load in programmers and possibly bugs due to a sleepFor(10); no longer meaning to sleep for 10 milliseconds, but for 2 milliseconds. Adding code to the operating system to perform the time conversion from an application-meaningful time resolution – such as microseconds or nanoseconds – to the internal tick resolution would already result in the loss of the simplicity advantages of tick-based timing subsystems. Additionally it would basically already constitute the biggest change needed to upgrade to a high-resolution timing subsystem, which we’ll discuss shortly.

Limitations on how long interrupts can be left disabled. An often overlooked problem of tick-based timing subsystem is that the tick period introduces a limitation on how long interrupts can be left disabled. Disabling interrupts is an important operation for operating system code because it constitutes the simplest way to achieve mutual exclusion between one or more code sections. However, disabling interrupts for longer than twice the tick resolution causes one or more tick ISRs to not be executed, resulting in a permament accumulation of clock offset in the notion of time for the entire operating system. Of course, attempts to lower the tick period to increase time resolution can only further exacerbate this issue.

Quantization issues approaching the tick resolution. While so far we considered that a given tick period such as 1 millisecond allows timekeeping and sleeping up to that resolution, as time intervals approach the tick resolution, quantization effects come into play resulting in time measurement errors and sleep time errors. This consideration further limits the usable time resolution to a multiple of the tick period. Interestingly, this issue also comes into play for the time quantum in scheduling, especially in implementations where the time quantum is equal to the tick period. In this case, should a preemption occur towards the end of the tick period, the newly scheduled task will only be able to use the CPU for a fraction of the expected time quantum (note that the tick ISR cannot be delayed to account for the the preemption as it must be kept strictly periodic not to let its timekeeping function accumulate clock offset). Should a code pattern arise where a task is subject to this shortened time quantum repeatedly, scheduling fairness will be impaired.

To explain the operation of a high-resolution timing subsystem, a deeper understanding of the architecture of hardware timers is required. Multiple timer architectures exist, not all of them suitable to be used in high-resolution timing subsystems. In this paper we will focus on the most common suitable architecture, that is found – often in multiple instances – in microcontrollers since it is also used for other purposes such as Pulse Width Modulation (PWM). This architecture is composed of a hardware free-running counter connected to at least one match register capable of generating interrupts, as shown in Figure 1. The free running counter is a sequential logic circuit made of flip-flops and logic gates to implement a binary counter with a fixed number of bits $n$, most typically 32 or 16 in current microcontrollers. When clocked at a system-specific frequency, often a sub-multiple of the CPU clock, the counter counts from 0 to $2^n-1$, and then rolls over and keeps counting. The timer counter is memory-mappped, meaning the kernel can read from (and in some architectures also write to) the timer counter. The match register is a memory-mapped register with a number of bits equal to the timer counter. A hardware comparator is present between the timer counter and match register, constantly comparing the two binary values. Whenever they are equal, an interrupt is fired to the CPU, resulting in the execution of the timer ISR. Additionally, the timer ISR is also called every time the timer counter rolls over to zero, and the software is given a way to differentiate between the two aforementioned events.

A high-resolution timing subsystem takes advantage of the memory-mapped timer counter to overcome the tradeoff between time resolution and ISR firing rate of tick-based systems. Indeed, at first glance, it looks like the operating system API call to query the time could simply be implemented by reading the timer counter and returning its value to applications. However, a slightly more complex implementation is usually required.

First of all, the 16 bit and even 32 bit counters found in current microcontrollers roll over too frequently to provide a monotonically increasing representation of time. Until 64 bit timers become common in microcontrollers, time needs to be kept partly in software and partly in hardware. This is usually done by having a software variable representing the upper bits of the time representation, and using the timer counter rollover interrupt to increment the software variable. The current time can then be obtained by combining the timer counter value with the software variable, using simple and efficient bitwise or bit-shift operations. Compared to a tick-based implementation, the ISR overhead for handling timer rollovers is minimal. A 16 bit timer clocked at 1MHz rolls over every 65.536 ms, enabling microsecond-level timekeeping with just $\approx 15$ interrupts per second. A 32 bit timer even allows nanosecond-resolution timestamping.

The second issue to account for, is that the frequency at which timers can be clocked is often restricted by hardware, resulting in timekeeping at inconvenient resolutions. For example, a 180MHz CPU may have a hardware timer clocked at 90MHz, resulting in a timekeeping resolution in units of 11.1 ns. To prevent these awkward resolutions from affecting application portability, a time conversion algorithm is necessary to convert the actual timer resolution to either microseconds or nanoseconds, by performing a multiplication by an appropriate scaling factor. Optimized fixed-point time conversion implemenations exist, taking around 30 clock cycles in modern microcontrollers [4].

A complete high-resolution timing subsystem shall also handle the wakeup of sleeping tasks. While a tick-based system relied on the periodic nature of the tick ISR to check for tasks to wakeup, the solution for high-resolution timers makes use of the match register. The solution is as follows: every time a task goes to sleep and it is added to the sleeping data structure, the earliest task that needs to wake up needs to be found, and its wakeup time is written to the match register. As a consequence, the hardware timer will call the ISR when the specified time is reached, and the ISR code will need to perform two operations: first, it shall wake the task, and then it shall update the timer match register to the wakeup time of the next task that needs to wake up. As a result, instead of a periodic tick ISR, the high-resolution timer ISR will be triggered aperiodically, and only when a task needs to wakeup. Although for brevity we omitted some details, such as how to handle sleep times longer than the timer rollover period, the number of timer ISR executions in a high-resolution timing subsystem is in general lower than in a tick-based one. However, to set the match register a reverse time conversion operation is needed, to convert the wakeup time originally in the application-meaningful time resolution (microseconds or nanoseconds) back into the hardware timer resolution. This operation is usually more expensive, usually taking longer than 100 clock cycles [4]. The last operation that needs discussing to complete a high-resolution timing subsystem is how to handle the preemption time quantum. The most straightforward solution is to also consider this timeout when setting the timer match register, which should thus be set to the minimimum value between the earliest task wakeup and the time quantum expiration.

Summarizing, the high-resolution timing subsystem described so far uses a single hardware timer with a single match register to serve all timing needs in an operating system. A simplified implementation of such a high-resolution timing subsystem is reported in Appendix A, Listing 2. The advantages and disadvantages of this solution are essentially complementary to the ones of a tick-based system, as in return for its higher complexity and – as we will see shortly – increased context switch overhead, it solves all the shortcomings of the tick-based solution. It clearly achieves high-resolution timing with low timer ISR overhead, can support fast periodic tasks, code portability is ensured by time conversion mapping any hardware timer resolution to a convenient and portable application-level resolution, and quantization is no longer a concern on account of the increased resolution. Finally, for what concerns the maximum timespan in which interrupts can be left disabled, it is now equal to one timer rollover period, thus a much longer timespan than two ticks. With all these positive features, it stands as a research question why are tick-based timing subsystems still prevalent in microcontroller operating systems? In this paper we posit one of the reasons being that high-resolution timing subsystems – as the one just described – slow down the scheduler code and thus the time needed to perform a context switch. The need to handle the time quantum expiration requires the scheduler to interact with the timing subsystem, and in an high-resolution timing subsystem this also requires to perform time conversion operations in the scheduler, which in such a timing-critical component can add a sizable amount of overhead. As such, solutions to reduce the context switch overhead of using a high-resolution timing subsystem are expected to increase their adoption in embedded real-time operating systems.

Another significant advantage of the proposed 1+N timer architecture is its scalability towards multicore architectures. Indeed, as multicore microcontrollers become popular, extending real-time operating systems to make efficient use of the available cores is an important research topic.

It should be noted that the application-facing knowledge of time must be kept consistent across software running on multiple cores. Indeed, querying the current time should return the same value regardless of which core the software is running on, and the absolute time point when wakeups from sleep occur must be independent of which core the woken task will be run on. As such, using a single hardware timer for implementing these operations is the simplest possible way to satisfy this requirement. On the other hand, the scheduler in SMP (Symmetric Multi-Processor) operating systems is in most cases implemented as a distributed algorithm, accessing a global thread list to maximize CPU utilization. Using separate lists per-core instead would create a task partitioning problem, which is not easy to solve [9]. Each instance of the scheduler, one per core, is responsible of choosing a new thread to run only on its assigned core, although if the scheduler running on one core finds out that it is necessary to change the running thread on some other core, it may trigger a rescheduling on that core through an inter-processor interrupt. As a consequence, different tasks can begin running on separate cores at different time points, each having a different time point for their time quantum expiration. Moreover, interrupt controllers for multicore architectures let the operating system decide on which core each interrupt request should be serviced and thus on which core each ISR should run on. Finally, some architectures such as ARM provide a dedicated per-core timer called the SysTick. Although this timer hardware is unsuitable for use as a high-resolution timer (it completely lacks a match register), it can be used for handling the preemption time quantum locally on each core.

These considerations led to the design of the 1+N high-resolution timing subsystem. This approach uses a single hardware timer for timekeeping in the operating system, and N additional hardware timers (one per core) to locally call the scheduler on each core at the end of the current task time quantum. From an implementation perspective, the implementation is a straightforward extension of the one in reported in Listing 3. The operation is summarized in the right side of Figure 2. The code of timer2 is replicated N times, and the scheduler is modified to set the time quantum expiration on the timer corresponding to the core it is currently running on. Each timer dedicated to the time quantum expiration will be configured so that the timer ISR will be called on the corresponding core, thereby balancing the ISR load among cores, while the global timer for handling timekeeping and sleeping will be configured to run its ISR on a core chosen by convention, such as the first core.

We implemented the proposed timer architecture in the Miosix operating system, that was previously using a traditional single-timer high-resolution timing subsystem. The source code of the Miosix kernel is freely available under a modified GPL license at the following address: https://github.com/fedetft/miosix-kernel/tree/unstable.