computer science//real-time computing//real-time scheduling
Real-time scheduling is the policy, and the analysis behind it, that decides which of several tasks a processor runs at each moment so that every task meets its deadline, and it is what lets an autopilot run its IMU filter, attitude loop, estimator, position loop and logger on one microcontroller with a proof that none will be late. A scheduler on a desktop aims at fairness and average responsiveness; a real-time scheduler aims at guarantees.
Real-time scheduling is the policy, and the analysis behind it, that decides which of several tasks a processor runs at each moment so that every task meets its deadline, and it is what lets an autopilot run its IMU filter, attitude loop, estimator, position loop and logger on one microcontroller with a proof that none will be late. A scheduler on a desktop aims at fairness and average responsiveness; a real-time scheduler aims at guarantees.
Its central quantity is CPU utilization, the share of the processor the periodic tasks claim:
U=∑i=1nCiTi,U=\sum_{i=1}^{n}\frac{C_i}{T_i},U=i=1∑nTiCi,
with CiC_iCi the worst-case execution time and TiT_iTi the period of task iii. Above 1 no policy can meet every deadline; below 1 whether one can depends on the policy and on how the periods interact.
Three policies cover practice. A cyclic executive fixes offline what runs in each slot of a repeating table, trivially verifiable and usual in avionics. Rate-monotonic scheduling gives fixed priorities, shortest period first, the standard on an RTOS. Earliest deadline first reorders priorities at run time by nearest deadline and can use the whole processor, at the price of uglier behaviour when overloaded.
The tests come in two strengths. A utilization bound (Liu and Layland's for rate-monotonic) is quick and sufficient; response-time analysis is exact and computes each task's worst response, including the time stolen by more urgent tasks, to compare with its deadline.
Every test is only as good as the execution times fed into it, which is why the worst-case execution time is measured or bounded with care, and why blocking on shared resources must be bounded too (priority inversion).
Slack is not waste. A budget at 30 % utilization covers interrupts, bursts and the feature someone will add next month; utilization plays the role of the load ρ\rhoρ in queueing theory, where waiting explodes as it approaches 1.