Real-time operating systems
With a utilization of 95 %, three tasks can miss a deadline with fixed priorities and meet them all with EDF. The difference is not the power of the processor but the order in which they are served.
01Real time does not mean fast
A system is real-time when the correctness of a result also depends on when it is delivered. An airbag controller that computes perfectly but 50 ms late has failed. What matters is not the average speed but the worst case: the guarantee that every task finishes before its deadline, always. A distinction is made between hard systems, where missing a deadline is a failure (brakes, pacemakers, flight control), and soft ones, where it only degrades quality (audio, video).
When an embedded system has many activities with different deadlines, the main loop with interrupts becomes hard to analyze. A real-time operating system (RTOS) organizes the program into independent tasks and decides at each moment which one to run, with predictable rules. The general concepts of processes and scheduling were covered in operating systems, in Computer Science II.
02Tasks, states and context switching
Each task is a function that runs as if it had the processor to itself, with its own stack. The kernel keeps for each one a control block with its priority, its state and its stack pointer. A task is running, ready waiting for the processor, blocked waiting for an event or a time, or suspended. The context switch saves the registers of the task going out and loads those of the one coming in; on a Cortex-M it takes about a microsecond.
The scheduler runs on every tick of the system clock (typically every 1 ms) and every time a task blocks or an event unblocks another. In a preemptive RTOS, if a task of higher priority than the running one is unblocked, it takes the processor away immediately.
03Scheduling and analysis
For periodic tasks, with period \( T_i \), worst-case execution time \( C_i \) and a deadline equal to the period, there are two classic policies. Rate-monotonic (RM) scheduling gives a higher fixed priority to the task with the shorter period. Earliest deadline first (EDF) chooses at each moment the task whose deadline expires soonest. Both have a utilization-based schedulability test:
Between 0.78 and 1, RM may or may not succeed. It is decided by response-time analysis, which computes the worst-case time of each task by adding the interference from the higher-priority ones, and is solved by iterating until the value no longer changes:
Three tasks with periods 5, 8 and 20, with a deadline equal to the period, on one processor. You choose the execution time of each one and the scheduler. The diagram shows one complete hyperperiod (40 units): the marks indicate the activations and the red cross, a missed deadline.
04Synchronization and communication
| Mechanism | What it is for |
|---|---|
| Binary semaphore | Having an interrupt wake up a task: the interrupt gives the semaphore and the task, blocked on it, does the long work |
| Counting semaphore | Keeping count of resources or pending events |
| Mutex | Mutual exclusion over a shared resource, with priority inheritance |
| Message queue | Passing data between tasks without sharing variables |
| Event flags | Waiting for a combination of conditions |
The classic trap is priority inversion. A low-priority task takes a resource; a high-priority one requests it and blocks; and a medium-priority one, which does not use the resource, preempts the low one and delays it indefinitely, with the high one waiting behind. The solution is priority inheritance: the task holding the mutex inherits the priority of the one waiting for it. In 1997, the Mars Pathfinder probe kept resetting on Mars because of this problem, and it was fixed remotely by enabling priority inheritance in its operating system.
05Real-time operating systems in use
| RTOS | Characteristics |
|---|---|
| FreeRTOS | The most widespread on microcontrollers; a kernel of a few kilobytes, MIT license |
| Zephyr | A Linux Foundation project with integrated drivers and network stacks |
| ThreadX | Certified for safety applications; now open source under the Eclipse Foundation |
| VxWorks | Commercial, in avionics, defense and space missions |
| RTEMS | Free, widely used in satellites and scientific instruments |
06In the lab
Create three periodic tasks on a microcontroller, each with a pin that goes high at the start and low at the end. Measure the response times with a logic analyzer and compare them with the analysis.
Handle a pushbutton with an interrupt that only gives a semaphore, and process the event in a task. Measure the latency between the edge and the start of the task.
Set up the three-task scenario with a binary semaphore and observe the delay of the high-priority task. Repeat with a mutex with priority inheritance.
07Common mistakes
- Measuring the average time instead of the worst case. The analysis uses the worst-case \( C_i \), with empty caches and all the longest branches.
- Using a binary semaphore where a mutex is needed. Without priority inheritance, the inversion appears.
- Stacks that are too small. Each task has its own; an overflow corrupts another’s memory and fails unpredictably.
- Calling blocking functions from an interrupt. Interrupts only use the special RTOS versions, which do not block.
08Self-assessment
What is the value of the Liu and Layland bound for two tasks?
\( 2(\sqrt{2} - 1) \approx 0.83 \).
Tasks (C, T) = (1, 4) and (2, 6). What is the response time of the second one with RM?
\( R = 2 + \lceil R/4 \rceil \cdot 1 \): starting at 2 gives 3, and with 3 gives 3. It responds in 3, before its period of 6.
A set has a utilization of 0.95. Is it schedulable with EDF? And with RM?
With EDF yes, because it does not exceed 1. With RM the bound does not tell: you have to do the response-time analysis.
What is priority inheritance?
That the task holding a mutex temporarily takes the priority of the highest-priority task waiting for it, so that no intermediate task delays it.
09Further reading
- Giorgio C. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. 3rd ed., Springer, 2011. The reference on real-time scheduling: RM, EDF, response analysis and resource protocols.
- Jane W. S. Liu. Real-Time Systems. Prentice Hall, 2000. The complete theoretical treatment of real-time systems.
- Richard Barry. Mastering the FreeRTOS Real Time Kernel. Real Time Engineers Ltd., 2016. The practical guide by the author of FreeRTOS: tasks, queues, semaphores and interrupts with examples.