Real-time scheduling

Why it matters

For most software, a slow response is just slow. For an airbag controller, a drone's flight loop, a pacemaker, an audio pipeline or a trading system's market-data handler, a late answer is a wrong answer. Real-time scheduling is the discipline of guaranteeing deadlines, and its ideas, especially bounding worst-case latency and the famous inversion bug that nearly lost a Mars mission, are useful well beyond embedded systems.

The idea

A real-time task has a deadline. In hard real-time, missing a deadline is a system failure (brakes, flight control). In soft real-time, misses degrade quality but are tolerable if rare (video frames, audio glitches, game frames). Real-time scheduling is not about being fast on average; it is about being predictable in the worst case.

Most real-time work is periodic: a task with period T needs at most C of CPU (its worst-case execution time) every T and must finish before the next period begins.

Two classic algorithms

	Rate-monotonic (RMS)	Earliest deadline first (EDF)
Rule	Fixed ranking: shorter period ranks higher, forever	Dynamic: whichever task's deadline is soonest runs
Schedulable if total utilisation…	is at most n(2^(1/n) − 1): about 83% for 2 tasks, falling toward 69% for many (a sufficient bound)	is at most 100% on one core
Implementation	Simple; fits fixed-rank hardware and RTOS schedulers	Needs a deadline-ordered queue; slightly more overhead
Under overload	Lower-ranked tasks miss predictably; important ones keep running	Misses can cascade unpredictably across tasks
Typical use	Most embedded and safety-critical systems	Systems wanting full utilisation; Linux SCHED_DEADLINE

Utilisation is the sum of C/T over all tasks. A set with tasks using 20 ms every 100 ms and 30 ms every 150 ms has utilisation 0.2 + 0.2 = 0.4, comfortably schedulable under either algorithm. The analysis only holds if the worst-case execution times are true worst cases, which is why real-time systems avoid unbounded loops, dynamic memory allocation in hot paths, and caches whose behaviour cannot be bounded.

Inversion, and how Pathfinder was saved

A high-urgency task can be blocked by a low-urgency one through a shared lock, and if a medium-urgency task preempts the low one while it holds the lock, the high task waits on the medium task indefinitely. This is priority inversion. In 1997 it caused repeated resets on NASA's Mars Pathfinder lander: a low-ranked meteorological task held a bus lock, medium-ranked communication tasks kept it from running, and the high-ranked bus manager missed its deadline, triggering a watchdog reset.

The standard fix is priority inheritance: while a low task holds a lock that a high task wants, it temporarily runs at the high task's rank, finishes its critical section quickly and releases the lock. Pathfinder's engineers enabled inheritance on that lock by uploading a patch to Mars. The related ceiling protocol gives a lock a fixed rank equal to the most urgent task that ever uses it, which also prevents deadlock among those tasks.

Real-time on Linux

Linux offers real-time scheduling classes alongside the normal one: SCHED_FIFO (fixed rank, runs until it blocks or a higher one is runnable), SCHED_RR (the same with time slices among equals) and SCHED_DEADLINE (EDF with admission control: the kernel refuses a task whose runtime, deadline and period would make the set unschedulable). The PREEMPT_RT work, merged into mainline in 2024, makes nearly all kernel code preemptible so worst-case latencies drop from milliseconds to tens of microseconds. Even so, Linux is a soft real-time platform for most uses; hard real-time systems usually run a dedicated RTOS (FreeRTOS, Zephyr, QNX, VxWorks) or isolate cores from Linux entirely.

Lessons for ordinary systems

Worst-case thinking applies to latency-sensitive services: bound the work per request, avoid allocations and locks on the hot path, isolate cores for the critical thread, and treat lock holders as a latency risk. Inversion shows up in thread pools too, when a high-urgency request waits on a lock held by a low-urgency background job.

Trade-offs

Real-time guarantees cost utilisation (RMS may leave a third of the CPU idle), flexibility (bounded, analysable code) and throughput (preemptible kernels do more bookkeeping). EDF uses the CPU fully and fails less gracefully under overload. Inheritance protocols prevent inversion at the cost of more complex locking.

In an interview

Real-time questions are rare outside embedded roles, but the inversion story is a strong answer to "tell me about a subtle concurrency bug": explain the three tasks, the lock, the watchdog reset, and the inheritance fix, then connect it to a modern case such as a request handler waiting on a lock held by a deprioritised batch thread.