Priority inversion
|
|
In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has released the resource, effectively "inverting" the relative priorities of the two tasks. If some other medium priority task attempts to run in the interim, it will take precedence over both the low priority task and the high priority task.
In most 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 watch dog timer resetting the entire system. The trouble experienced by the Mars lander "Mars Pathfinder" 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 realtime response guarantees. Because priority inversion results in the execution of the low priority task blocking the high priority task, it can lead to reduced system responsiveness, or even the violation of a response time guarantees.
The existence of this problem has been known since the 1970s but there is no fool-proof method to predict the situation. There are many existing solutions. The most common ones are
In the first method, the low priority task inherits the priority of the high priority task, thus stopping the medium priority task from pre-empting the low priority task. In the second method, the shared mutex process has a characteristic (high) priority of its own, which is assigned to the task locking the mutex. This works well, provided the other high priority task that tries to access the mutex does not have a priority higher than the ceiling priority.
See also
External links
- "Introduction to Priority Inversion (http://netrino.com/Publications/Glossary/PriorityInversion.html)" by David Kalinsky and Michael Barr
- Description from FOLDOC (http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?priority+inversion)
- Citations from CiteSeer (http://citeseer.org/cs?q=priority+inversion)
- Explanation of priority inversion problem experienced by pathfinder (http://research.microsoft.com/~mbj/Mars_Pathfinder/)de:Prioritätsinversion