When late is the same as wrong

An airbag controller that computes the right answer 50ms late has failed completely. Real time systems are judged on deadlines rather than on throughput.

Hard and soft

Hard real time: missing a deadline is a system failure. Anti lock brakes, pacemakers, industrial control. These are usually not running Linux.

Soft real time: missing occasionally degrades quality. Video playback, audio, games. A dropped frame is bad, not catastrophic.

The engineering difference is that hard real time systems are designed for the worst case, not the average. A function whose average is 1ms and worst case is 40ms is unusable, however good the average.

Scheduling for deadlines

Rate monotonic: fixed priorities, shorter period gets higher priority. Provably optimal among fixed priority schemes, and it can guarantee all deadlines are met if total CPU utilisation stays under about 69 percent for many tasks.

That number surprises people. A third of the machine is deliberately left idle to guarantee the timing.

Earliest deadline first: priorities change, whatever is due soonest runs next. Can use up to 100 percent utilisation, and degrades badly when overloaded, because everything misses together.

Priority inversion

A high priority task waits on a lock held by a low priority task. That is normal and brief. It becomes a failure when a medium priority task preempts the low priority one:

low  holds the lock, is running
med  becomes runnable, preempts low
high needs the lock, blocks behind low
             ...low never runs, so high never runs...

High priority is now blocked by medium priority work it should outrank, and indefinitely.

This is not hypothetical. The Mars Pathfinder rover kept resetting on the surface in 1997 for exactly this reason, and the fix was uploaded from Earth.

The fix

Priority inheritance: while a low priority task holds a lock a high priority task wants, it temporarily inherits the high priority. It finishes quickly, releases the lock, and returns to its own priority. Medium priority work can no longer get in the way.

Priority ceiling: each lock carries the priority of the highest task that might take it, and anyone holding it runs at that level.