Real-time systems: EDF, rate monotonic and response time
Periodic tasks, the utilisation condition proved, optimal EDF, the Liu and Layland bound, response time analysis with an example, priority inversion and inheritance, RTOS.
In a real-time system a correct but late result is wrong: a car’s brake command, a motor controller, a pacemaker must respond within a deadline. What counts is not average speed, but the worst-case guarantee. In this lesson we look at the periodic task model, EDF scheduling with the proof of the necessary condition, rate monotonic priority with its bound and exact response time analysis worked through an example, priority inversion and real-time operating systems.
The periodic task model
We distinguish hard systems, where missing a deadline is a failure (flight control, airbags), and soft ones, where only quality degrades (video playback). Many control tasks are periodic (Digital Control lesson on implementation): task 
is released every 
, requires at most 
of computation (the worst-case execution time) and must finish before the next release. Its utilisation factor is 
, and the total utilisation 
.
Earliest deadline first
The EDF (earliest deadline first) algorithm runs at each instant the ready task with the nearest deadline, with preemption.
Theorem. On one processor, a set of periodic tasks with deadline equal to period is schedulable by any algorithm only if 
; with EDF the condition is also sufficient.
Proof of necessity. Consider the interval 
, where 
is the least common multiple of the periods. Task is released 
times and requires in all 
of computation, which must be done within . The total demand is 
, and the processor offers at most : we need 
, i.e. . ∎
Sufficiency for EDF (Liu and Layland, 1973) is proved by showing that, if a deadline were missed, in the preceding interval the processor would always have been busy with tasks with no later deadlines, and their demand would exceed the length of the interval, i.e. 
. EDF is therefore optimal: it uses the processor up to 100 %.
Rate monotonic priority and response time
Many systems use fixed priorities instead, simpler and more predictable under overload: with the rate monotonic rule (RMS) the task with the shortest period has the highest priority. Liu and Layland proved that RMS guarantees the deadlines if
![\[ U \le n\left(2^{1/n} - 1\right) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-e15564ac5f32edc6ebfb13338a7988dd_l3.png "Rendered by QuickLaTeX.com")
where 
is the number of tasks: 0.83 for two, 0.78 for three, tending to 
. The condition is only sufficient; for an exact answer the worst-case response time is computed, which occurs when all tasks are released together. For task 
, with higher-priority tasks 
:
![\[ R_i = C_i + \sum_{j}\left\lceil\frac{R_i}{T_j}\right\rceil C_j \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-5bca40fbeedd58f9e9bb0696127bdf0a_l3.png "Rendered by QuickLaTeX.com")
because during 
each higher-priority task is released 
times and each time interrupts it for 
. The equation is solved by iteration starting from 
, until the value stops changing; the task meets its deadline if 
.
Example. Three tasks 
: 
, 
, 
, with 
, above the 0.78 bound: the sufficient test is inconclusive. Response time of 
: start from 
; then 
; then 
; then 
; then 
; then 
, stable. 
: the set is schedulable, as the figure shows.
Priority inversion
A high-priority task H waits for a lock held by a low-priority task L. If meanwhile a medium-priority task M is released, which does not use the lock, M preempts L, and H stays blocked for the whole duration of M: a less important task indirectly delays the most important one, for an unbounded time if there are many medium tasks. This is priority inversion. In 1997 the Mars Pathfinder probe kept resetting for this reason, until the priority inheritance option was enabled from Earth: while L holds a lock requested by H, L temporarily inherits H’s priority, M cannot preempt it, and H’s blocking lasts at most as long as L’s critical section. The priority ceiling protocol does more, and also prevents deadlocks between locks.
Real-time operating systems
A real-time operating system (RTOS) offers preemptive priority schedulers, small and above all bounded interrupt latencies, synchronisation tools with priority inheritance and predictable memory allocation. On microcontrollers very small kernels such as FreeRTOS or Zephyr are used, a few kilobytes in size; in larger systems Linux with the PREEMPT_RT extensions, which make almost the whole kernel preemptible and bring worst-case latencies down to tens of microseconds. The worst-case execution time must be measured or computed with analysis tools, taking caches and interrupts into account: it is often the hardest part of the design.
