priority inversion
Priority scheduling promises that a high-priority thread runs ahead of low-priority ones. Priority inversion is the unsettling situation where, because of a shared lock, a high-priority thread ends up effectively waiting behind a low-priority one — the priorities seem reversed. Imagine a VIP stuck in a restroom queue because the only stall is occupied by a junior employee, who in turn is stuck because a crowd of middle managers keeps cutting in front and never lets the junior finish. The VIP, despite top priority, waits indefinitely on the slowest person in the building.
Here is the exact mechanism with three threads: H (high priority), M (medium), and L (low). L acquires a lock and enters its critical section. H wakes up, tries to acquire the same lock, and blocks because L holds it — so far reasonable, H must wait briefly for L. But now M (which needs no lock) becomes runnable. Since M outranks L, the scheduler runs M instead of L. L cannot make progress to release the lock, so H stays blocked. As long as medium-priority work keeps arriving, M after M preempts L, L never finishes, and H — the most important thread — is starved by work less important than itself. The high-priority thread is blocked not directly by a peer but transitively, through a lock held by someone the medium threads keep preempting.
This is not academic: a famous case nearly doomed the 1997 Mars Pathfinder mission, whose lander kept resetting because a high-priority task was inverted behind a low-priority one. The standard cure is priority inheritance: while a low-priority thread holds a lock that a high-priority thread is waiting for, the low-priority thread temporarily inherits the high priority, so the medium threads can no longer preempt it. It finishes its critical section quickly, releases the lock, and reverts to its own priority; H then proceeds. (A related scheme, the priority ceiling protocol, raises the holder to a predefined ceiling.) This is exactly the kind of ownership-aware feature a real mutex can offer but a plain semaphore cannot, and it is essential in real-time systems where missing a deadline is a failure.
Mars Pathfinder (1997): a high-priority data-bus task blocked on a mutex held by a low-priority weather task, while medium-priority comms tasks kept preempting the weather task. A watchdog timer saw the high task stalled and reset the system, over and over — until engineers enabled priority inheritance.
A high task waits behind a low one via a shared lock; priority inheritance lifts the holder to break it.
The real culprit is the medium-priority threads preempting the lock holder, not the high/low pair alone. Priority inheritance fixes it; plain semaphores (no owner) cannot provide it.