Priority inversion is a failure mode that arises in priority-based preemptive scheduling, the kind used in real-time operating systems. Tasks are assigned priorities, and the scheduler is supposed to run the highest-priority ready task. Priority inversion occurs when a high-priority task is forced to wait for a lower-priority task, inverting the intended ordering. It happens because tasks must sometimes share resources, such as data structures or devices, that are protected by a lock or semaphore so only one task uses them at a time.
The foundational technical treatment is “Priority Inheritance Protocols: An Approach to Real-Time Synchronization” by Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky, published in IEEE Transactions on Computers, volume 39, number 9, in September 1990. The paper analyzes the problem rigorously and proposes protocols with provable bounds on the resulting delay, making it the standard reference for the concept.
The danger is not merely that some inversion occurs, which is unavoidable when resources are shared, but that the inversion can become unbounded. Consider a low-priority task that acquires a lock needed by a high-priority task. While the high-priority task waits, a medium-priority task that does not need the lock can preempt the low-priority task and run for an arbitrarily long time. The low-priority task cannot proceed to release the lock, so the high-priority task is blocked, in effect, for as long as the medium-priority work lasts. The high-priority task has been pushed below the medium-priority task it should have dominated.
Sha, Rajkumar, and Lehoczky describe two remedies. The basic priority inheritance protocol has a task that holds a lock temporarily inherit the priority of the highest-priority task blocked on that lock. The low-priority lock holder is thus boosted above the medium-priority interlopers, runs, and releases the lock promptly, after which it drops back to its own priority. This bounds the blocking but does not by itself prevent deadlocks or chained blocking. The priority ceiling protocol assigns each lock a ceiling equal to the priority of the highest task that can ever request it, and uses that ceiling to further restrict when locks may be acquired. The paper proves that the ceiling protocol limits a task’s worst-case blocking to at most the duration of a single critical section of a lower-priority task and also prevents deadlock.
These results matter because real-time systems must guarantee that deadlines are met, and a schedulability analysis is only sound if the worst-case blocking each task can suffer is bounded. Unbounded priority inversion breaks that guarantee. The protocols turn an open-ended risk into a quantity an engineer can compute and design around, which is why they were quickly adopted in real-time operating systems and standards.
The most famous illustration of the hazard is the Mars Pathfinder lander, which repeatedly reset itself in 1997 because a high-priority task was blocked by a low-priority task holding a mutex while medium-priority tasks ran. The fix was to enable priority inheritance on the relevant mutex, exactly the basic protocol described in the 1990 paper (see mars-pathfinder-priority-inversion). Priority inversion is closely related to other concurrency hazards such as race conditions, in that all stem from the subtle interaction of independently scheduled tasks over shared state (see concurrency).