In computer science, priority inversion is a scenario in scheduling in which a high-priority task is indirectly superseded by a lower-priority task, effectively inverting the assigned priorities of the tasks. This violates the priority model that high-priority tasks can only be prevented from running by higher-priority tasks. Inversion occurs when there is a resource contention with a low-priority task that is then preempted by a medium-priority task.

Formulation

Consider two tasks H and L, of high and low priority respectively, either of which can acquire exclusive use of a shared resource R. If H attempts to acquire R after L has acquired it, then H becomes blocked until L relinquishes the resource. Sharing an exclusive-use resource (R in this case) in a well-designed system typically involves L relinquishing R promptly so that H (a higher-priority task) does not stay blocked for excessive periods of time. Despite good design, however, it is possible that a third task M of medium priority becomes runnable during L ' s use of R. At this point, M being higher in priority than L, preempts L (since M does not depend on R), causing L to not be able to relinquish R promptly, in turn causing H—the highest-priority process—to be unable to run (that is, H suffers unexpected blockage indirectly caused by lower-priority tasks like M).

Consequences

In some cases, priority inversion can occur without causing immediate harm—the delayed execution of the high-priority task goes unnoticed, and eventually, the low-priority task releases the shared resource. However, there are also many situations in which priority inversion can cause serious problems. If the high-priority task is left starved of the resources, it might lead to a system malfunction or the triggering of pre-defined corrective measures, such as a watchdog timer resetting the entire system. The trouble experienced by the Mars Pathfinder lander in 1997 is a classic example of problems caused by priority inversion in realtime systems. Priority inversion can also reduce the perceived performance of the system. Low-priority tasks usually have a low priority because it is not important for them to finish promptly (for example, they might be a batch job or another non-interactive activity). Similarly, a high-priority task has a high priority because it is more likely to be subject to strict time constraints—it may be providing data to an interactive user, or acting subject to real-time response guarantees. Because priority inversion results in the execution of a lower-priority task blocking the high-priority task, it can lead to reduced system responsiveness or even the violation of response time guarantees. A similar problem called deadline interchange can occur within earliest deadline first scheduling (EDF).

Solutions

The existence of this problem has been known since the 1970s. Lampson and Redell published one of the first papers to point out the priority inversion problem. Systems such as the UNIX kernel were already addressing the problem with the splx primitive. There is no foolproof method to predict the situation. There are however many existing solutions, of which the most common ones are: