# What is priority inversion and What are the various methods to overcome it?

267 views
What is priority inversion and What are the various methods to overcome it?
posted May 13, 2014

+1 vote

Priority inversion is a problematic scenario in scheduling in which a high priority task is indirectly preempted by a medium priority task effectively "inverting" the relative priorities of the two tasks.

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 unrunnable until L relinquishes the resource. The use of the shared exclusive-use resource when properly designed is such that L relinquishes R promptly enough that H's priority use is not hindered excessively. In spite of the good design of these two cooperating tasks, the surprising behavior, priority inversion, occurs when any third task M of medium priority becomes runnable during L's use of R. Once H becomes unrunnable, M is the highest priority runnable task, thus it runs and while it does L cannot relinquish R. So in this scenario, the medium priority task preempts the high priority task, resulting in a priority inversion.

Now coming to your second problem, what are the ways to overcome it, it is the solution not a problem to avoid the possible DeadLock so this question does not arise.

Priority inversion is a situation where in lower priority tasks will run blocking higher priority tasks waiting for resource (mutex). For ex: consider 3 tasks. A, B and C, A being highest priority task and C is lowest. Look at sequence of context swaps

A goes for I/O . unlocks mutex. C was ready to run. So C starts running. locks mutex B is ready to run. Swaps out C and takes mutex. A is ready to run. but A is blocked as mutex is locked by B. but B will never relinqishes the mutex as its higher priority than C.

The solution to priority inversion is Priority inheritance.

Priority Inheritance is the solution for priority inversion. whenever a high priority task request for some
resource which is locked by a low priority task, the priority of lower task is inherited to the priority of the
higher task. The instance it unlocks the resource the prioity is changed to its original value.

Another solution for this is priority ceiling where you inherit the priority of the lower task whenever a higher task is created.Even if the higher priority task does not request for the resource