Priority inversion and how priority inheritance fixes it

Consider a low-priority task holding a lock that a high-priority task needs.

Model answer. Priority inversion happens when a high-priority task is forced to wait for a lower-priority task, so the effective priority order is reversed.

Three-task scenario

• Tasks H (high), M (medium) and L (low) share a mutex that only H and L use.
• L acquires the mutex and enters its critical section.
• H becomes ready, preempts L, tries to take the mutex and blocks — waiting for L is expected and short (bounded by L's critical section).
• Now M becomes ready. M does not need the mutex, but it has higher priority than L, so it preempts L.
• L cannot run to release the mutex, so H is effectively waiting for M — and for any other medium-priority tasks. The delay is unbounded. In a real-time system, H may miss its deadline and a watchdog may reset the system.

A well-known real case is NASA's Mars Pathfinder (1997), whose VxWorks-based software experienced repeated resets from this exact pattern; it was fixed by turning on priority inheritance for the affected mutex.

Priority inheritance

• When H blocks on a mutex held by L, L temporarily inherits H's priority.
• M can no longer preempt L, so L finishes its critical section quickly, releases the mutex, drops back to its own priority, and H runs.
• Blocking of H is now bounded by the length of L's critical section(s).

Priority ceiling protocol

• Each mutex is assigned a ceiling equal to the highest priority of any task that may lock it.
• A task holding the mutex runs at the ceiling priority (immediate ceiling variant), or locks are granted only if the task's priority is strictly higher than the ceilings of all mutexes currently locked by other tasks (original protocol).
• This bounds blocking to at most one critical section and also prevents deadlocks caused by nested locking.

Common mistake: calling priority inversion a deadlock. Nothing is circular — H will eventually run once M finishes; the problem is that the wait is unpredictable and unbounded.