Priority Inversion and Priority Inheritance

Priority Inversion

Minimum cast

3 tasks: high, medium, low priority

Root cause

Priority scheduling + a shared lock

Common fix

Priority inheritance

Famous incident

Mars Pathfinder, 1997

Priority inversion is what happens when a priority scheduler’s core guarantee, that the highest-priority runnable task always runs next, turns out to be violated in practice by a task the scheduler considers lower priority. The scheduler itself isn’t malfunctioning; the problem is that “runnable” and “blocked on a lock” aren’t the same thing the scheduler thinks they are, and a lock held by a low-priority task can leave a high-priority one stuck waiting regardless of what the scheduler would otherwise choose to run.

The three-task scenario

The classic case needs exactly three tasks: a low-priority task L acquires a mutex to protect some shared resource, and shortly after, a high-priority task H attempts to acquire that same mutex and blocks, since L is still holding it. So far this is ordinary, bounded blocking: H simply waits for L to finish its critical section and release the lock, which should happen soon since L is low priority and gets little CPU time to begin with. The inversion appears when a third task, M, of priority between L and H, becomes runnable during that wait: M has no interest in the mutex at all, but because M outranks L, the scheduler preempts L in M’s favor, and L, the only task actually capable of releasing the lock H is waiting on, doesn’t run again until M is done. H, nominally the highest-priority task in the system, ends up waiting on M indirectly, a task it has no relationship to and, by priority, should never be blocked behind.

Priority:  H > M > L

t0: L acquires mutex
t1: H blocks on mutex (L holds it)
t2: M becomes runnable, preempts L (M > L)
    -- H now effectively waits behind M, despite H > M --
t3: M finishes, L resumes, releases mutex
t4: H finally acquires mutex and proceeds

Without M in the picture, H’s wait is bounded by however long L’s critical section normally takes; with M repeatedly becoming runnable (or, in the worst case, an unbounded stream of same-priority tasks each briefly preempting L in turn), H’s wait has no such bound at all, which is what separates ordinary lock contention from priority inversion specifically.

Priority inheritance

Priority inheritance closes the gap by having the lock itself, rather than the scheduler, adjust the priority of whichever task currently holds it: the moment H blocks on a mutex L holds, L’s effective priority is temporarily raised to match H’s, for as long as L continues holding that mutex. With L now running at H’s priority, M can no longer preempt it, since M is no longer higher priority than the task actually holding the lock; L runs, finishes its critical section, releases the mutex, drops back to its own original priority, and H acquires the lock immediately afterward. The bound on H’s wait is restored to something close to the original case, the length of L’s critical section, rather than remaining open-ended.

void mutex_lock(struct mutex *m) {
    struct task *waiter = current_task();
    if (m->owner && waiter->priority > m->owner->priority) {
        m->owner->effective_priority = waiter->priority;
        reschedule_if_needed(m->owner);
    }
    // ... block until acquired ...
}

void mutex_unlock(struct mutex *m) {
    m->owner->effective_priority = m->owner->base_priority;
    // ... wake a waiter, release ...
}

A chain of nested locks makes this recursive rather than a single adjustment: if L itself blocks on a second mutex held by some other task while running at H’s inherited priority, that second task inherits H’s priority in turn, and so on, since otherwise the same inversion would simply reappear one lock deeper in the chain.

Costs and alternatives

Priority inheritance isn’t free: every lock acquisition now needs to check the waiter’s priority against the current holder’s and potentially propagate an adjustment, bookkeeping that a plain spinlock or mutex implementation skips entirely, and the chain-following case above can, in a pathological nested-lock design, touch a genuinely large number of tasks for a single lock operation. Priority ceiling protocols trade some of that runtime cost for a static one: every lock is assigned, in advance, a ceiling equal to the highest priority any task that might ever acquire it could have, and a task acquiring the lock immediately runs at that ceiling for the duration, whether or not a higher-priority task is actually waiting yet. This avoids the propagation bookkeeping at acquisition time, since the right priority is already known rather than discovered dynamically, at the cost of requiring every lock’s full set of potential holders to be known ahead of time, which is straightforward in a fixed-task real-time system and considerably less so in a general-purpose kernel where the same mutex might be reachable from code paths that aren’t all enumerated in advance.

Implementation notes

Priority inversion is not a hypothetical concern raised only in textbooks: the Mars Pathfinder rover’s 1997 software resets were eventually traced to exactly this scenario, a low-priority data-collection task holding a shared-bus mutex being preempted by a medium-priority communications task, starving a high-priority bus-management task long enough for a watchdog timer to conclude the system had hung and force a reset. The fix, once identified, was to enable priority inheritance on the mutex in question, uplinked as a software patch to a spacecraft already on Mars, which is as strong a demonstration as exists that this is a correctness bug with real consequences, not a theoretical corner case in a scheduling paper.

References

1. ^ L. Sha, R. Rajkumar, and J. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Transactions on Computers, 1990: the original paper defining priority inheritance and the priority ceiling protocol.
2. ^ M. Jones, “What really happened on Mars Rover Pathfinder,” The Risks Digest, 1997: the engineer-authored account of the Pathfinder priority-inversion incident and its in-flight fix.

See also

• Schedulers: the priority-based policy whose guarantee this article’s scenario violates.
• Synchronization: the mutex mechanism a low-priority task holds in the scenario above, and where a kernel’s lock implementation actually lives.