3.4Priority inversion and deadlock

The intuition that "a higher-priority task always runs before a lower-priority one" can break down once resource sharing enters the picture. Priority inversion is the classic phenomenon in which this intuition fails—it is famously known from a real spacecraft fault. An embedded designer needs to understand, at the mechanism level, why this happens, and to correctly distinguish between the two remedies: priority inheritance and priority ceiling.

3.4.1The mechanism of priority inversion

• Priority inversion is the phenomenon in which, while high-priority task H is blocked waiting to acquire a mutex (or lock) held by low-priority task L, a medium-priority task M—lower than H but higher than L—preempts L, so that H ends up effectively waiting longer than it should, blocked by M. The essence of the problem is that, in principle, only L should be able to block H, yet M ends up blocking H indirectly.
• What makes this especially dangerous is when the inversion continues indefinitely (unbounded priority inversion). If a stream of medium-priority tasks keep preempting L one after another, H's wait time has no theoretical upper bound, which directly leads to H missing its deadline.

3.4.2Priority inheritance and priority ceiling

• Priority inheritance is a protocol in which, the instant high-priority task H blocks waiting for a lock, the priority of the low-priority task L that holds the lock is temporarily raised to H's level. This prevents medium-priority task M from preempting L, so L can promptly release the lock to H. Once L releases the lock, its priority reverts to its original level.
• Priority ceiling assigns each lock, in advance, a ceiling priority—the priority of the highest-priority task that could ever acquire it—and, the instant a task acquires a lock, immediately raises that task's priority to the lock's ceiling. Because the priority is raised proactively at acquisition time rather than reactively at contention time, it prevents chains of blocking earlier than priority inheritance does, and it also has a deadlock-avoidance effect when multiple locks are involved (the more elaborate ceiling protocols specifically prevent cyclic lock-acquisition orderings).
• The core difference: priority inheritance raises L's priority only after blocking actually occurs (a reactive response), whereas priority ceiling raises it proactively at the moment the lock is acquired (a preemptive response). Because of this, priority ceiling is more effective at preventing chains of blocking and at avoiding deadlock, but it comes with the added upfront cost of designing ceiling values (working out the ceiling priority for every lock in advance).

Suppose an embedded system runs high-priority task H (emergency-stop decision, hard deadline), medium-priority task M (sending communication logs), and low-priority task L (reading configuration values, accessing a shared EEPROM under a mutex). At some point, while L holds the mutex and is reading the EEPROM, H tries to acquire that same mutex and blocks. Without any countermeasure, M then wakes up and preempts L; L cannot resume until M's processing (sending communication logs, taking tens of milliseconds) finishes, so H ends up waiting not just for L's work but also for M's—this is priority inversion, and it risks H missing its deadline. Implementing priority inheritance fixes this: the instant H blocks, L's priority is raised to H's level, so M can no longer preempt L; L quickly finishes the EEPROM read and releases the mutex, letting H resume almost immediately. However, if this system has multiple locks—say, an EEPROM-access mutex plus a separate shared-buffer mutex—each contended by a different set of tasks, priority inheritance alone can still leave complex chains of blocking arising from the interplay between "the set of tasks waiting on lock A" and "the set waiting on lock B." In that case, the appropriate choice is priority ceiling: assign each lock, in advance, a ceiling equal to the priority of the highest-priority task that could ever acquire it, and raise the acquiring task's priority to that ceiling the instant it acquires the lock—this also prevents cyclic waiting caused by lock-acquisition ordering (one contributor to deadlock). The core design judgment in this section is: priority inheritance suffices to prevent a single, isolated inversion on one lock, but priority ceiling is the right choice when multiple locks interact in complex ways and deadlock avoidance is also required.

3.4.3Conditions for deadlock and avoidance

• Deadlock occurs when all of the following four conditions hold simultaneously: (1) mutual exclusion (a resource can be used by only one task at a time), (2) hold and wait (a task holds a resource while waiting for another), (3) no preemption (a resource cannot be taken away until the holding task voluntarily releases it), and (4) circular wait (task A waits for a resource held by B, B waits for one held by C, ..., and the chain eventually loops back to A).
• Representative avoidance strategies: enforcing a consistent resource-acquisition order (if every task is required to acquire resource A before B, circular wait can never arise in principle); acquisition with a timeout (give up after a set time, release any held resources, and retry); and the priority ceiling protocol (as noted above, which also helps prevent cyclic acquisition ordering across multiple locks). The theoretical basis for these countermeasures is that breaking even just one of the four conditions makes deadlock impossible.

3.4.4Section summary

• Priority inversion is the phenomenon where a medium-priority task preempting a low-priority one can indefinitely extend a high-priority task's wait
• Priority inheritance is a reactive fix after blocking occurs; priority ceiling is a proactive fix at lock-acquisition time that also aids deadlock avoidance
• Deadlock requires all four conditions—mutual exclusion, hold-and-wait, no preemption, and circular wait—and breaking any one prevents it