Priority Inversion and Inheritance

Priority inversion is when a high-priority task waits on a resource held by a low-priority one; inheritance protocols bound how long that wait can last.

The Problem

Priority inversion occurs when a high-priority task is blocked because a lower-priority task holds a shared resource it needs. That alone is bounded and acceptable. The danger is unbounded priority inversion: a medium-priority task, unrelated to the resource, preempts the low-priority holder, so the holder cannot finish and release the lock, and the high-priority task waits indefinitely on the medium task's schedule.

A Famous Failure

The 1997 Mars Pathfinder mission suffered repeated resets in flight from exactly this pattern: a high-priority bus-management task blocked on a mutex held by a low-priority task, while medium-priority communication tasks kept the holder from running, tripping a watchdog. The fix was to enable priority inheritance on the mutex.

Priority Inheritance

Under the priority-inheritance protocol, when a high-priority task blocks on a resource, the task holding that resource temporarily inherits the higher priority. This lets the holder run, finish its critical section, and release the resource promptly. Once it releases, it returns to its base priority. Inheritance bounds the blocking to the length of the critical sections, not the schedules of unrelated tasks.

Priority Ceiling

The priority-ceiling protocol goes further: each resource is assigned a ceiling equal to the highest priority of any task that can use it, and a task can lock a resource only if its priority exceeds the ceilings of all currently locked resources. This prevents deadlock and limits each task to being blocked by at most one critical section, giving a tighter, more analyzable bound.

Consequences for Analysis

Blocking must be included in schedulability analysis. Response-time calculations add a blocking term for each task equal to the worst critical section it can be forced to wait on. Keeping critical sections short and using a bounding protocol are therefore both correctness requirements and inputs to the timing proof.