Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is priority inversion?

I've heard the phrase 'priority inversion' in reference to development of operating systems.

What exactly is priority inversion?

What is the problem it's meant to solve, and how does it solve it?

like image 595
paxdiablo Avatar asked Nov 23 '10 02:11

paxdiablo


People also ask

What do you mean by priority inversion?

Priority inversion is a bug that occurs when a high priority task is indirectly preempted by a low priority task. For example, the low priority task holds a mutex that the high priority task must wait for to continue executing.

Why is priority inversion important?

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).

How priority inversion happens?

Priority inversion is a situation that can occur when a low-priority task is holding a resource such as a semaphore for which a higher-priority task is waiting. The high-priority task has effectively acquired the priority of the low-priority thread (thus the name priority inversion).

How do I fix priority inversion?

One way to solve priority inversion is to use the priority ceiling protocol, which gives each shared resource a predefined priority ceiling. When a task acquires a shared resource, the task is hoisted (has its priority temporarily raised) to the priority ceiling of that resource.


4 Answers

Imagine three (3) tasks of different priority: tLow, tMed and tHigh. tLow and tHigh access the same critical resource at different times; tMed does its own thing.

  1. tLow is running, tMed and tHigh are presently blocked (but not in critical section).
  2. tLow comes along and enters the critical section.
  3. tHigh unblocks and since it is the highest priority task in the system, it runs.
  4. tHigh then attempts to enter the critical resource but blocks as tLow is in there.
  5. tMed unblocks and since it is now the highest priority task in the system, it runs.

tHigh can not run until tLow gives up the resource. tLow can not run until tMed blocks or ends. The priority of the tasks has been inverted; tHigh though it has the highest priority is at the bottom of the execution chain.

To "solve" priority inversion, the priority of tLow must be bumped up to be at least as high as tHigh. Some may bump its priority to the highest possible priority level. Just as important as bumping up the priority level of tLow, is dropping the priority level of tLow at the appropriate time(s). Different systems will take different approaches.

When to drop the priority of tLow ...

  1. No other tasks are blocked on any of the resources that tLow has. This may be due to timeouts or the releasing of resources.
  2. No other tasks contributing to the raising the priority level of tLow are blocked on the resources that tLow has. This may be due to timeouts or the releasing of resources.
  3. When there is a change in which tasks are waiting for the resource(s), drop the priority of tLow to match the priority of the highest priority level task blocked on its resource(s).

Method #2 is an improvement over method #1 in that it shortens the length of time that tLow has had its priority level bumped. Note that its priority level stays bumped at tHigh's priority level during this period.

Method #3 allows the priority level of tLow to step down in increments if necessary instead of in one all-or-nothing step.

Different systems will implement different methods depending upon what factors they consider important.

  • memory footprint
  • complexity
  • real time responsiveness
  • developer knowledge

Hope this helps.

like image 106
Sparky Avatar answered Oct 13 '22 21:10

Sparky


Priority inversion is a problem, not a solution. The typical example is a low priority process acquiring a resource that a high priority process needs, and then being preempted by a medium priority process, so the high priority process is blocked on the resource while the medium priority one finishes (effectively being executed with a lower priority).

A rather famous example was the problem experienced by the Mars Pathfinder rover: http://www.cs.duke.edu/~carla/mars.html, it's a pretty interesting read.

like image 34
Dmitri Avatar answered Oct 13 '22 21:10

Dmitri


Suppose an application has three threads:

Thread 1 has high priority.
Thread 2 has medium priority.
Thread 3 has low priority.

Let's assume that Thread 1 and Thread 3 share the same critical section code

Thread 1 and thread 2 are sleeping or blocked at the beginning of the example. Thread 3 runs and enters a critical section.

At that moment, thread 2 starts running, preempting thread 3 because thread 2 has a higher priority. So, thread 3 continues to own a critical section.

Later, thread 1 starts running, preempting thread 2. Thread 1 tries to enter the critical section that thread 3 owns, but because it is owned by another thread, thread 1 blocks, waiting for the critical section.

At that point, thread 2 starts running because it has a higher priority than thread 3 and thread 1 is not running. Thread 3 never releases the critical section that thread 1 is waiting for because thread 2 continues to run.

Therefore, the highest-priority thread in the system, thread 1, becomes blocked waiting for lower-priority threads to run.

like image 25
Pratik Bhat Avatar answered Oct 13 '22 22:10

Pratik Bhat


It is the problem rather than the solution.

It describes the situation that when low-priority threads obtain locks during their work, high-priority threads will have to wait for them to finish (which might take especially long since they are low-priority). The inversion here is that the high-priority thread cannot continue until the low-priority thread does, so in effect it also has low priority now.

A common solution is to have the low-priority threads temporarily inherit the high priority of everyone who is waiting on locks they hold.

like image 45
Thilo Avatar answered Oct 13 '22 22:10

Thilo