What is priority inversion?

Question

I heard the expression "priority inversion" in relation to the development of operating systems.

What is priority inversion?

What is the problem that he must solve, and how does he solve it?

Answer 1

Priority inversion is a problem, not a solution. A typical example is a low-priority process that receives a resource that is required by a high-priority process, and then is superseded by a medium-priority process, so the high-priority process is blocked on the resource, while the middle priority ends (in fact, it is executed using a lower priority).

A fairly well-known example was the problem that the Mars-Pathfinder marker encountered: http://www.cs.duke.edu/~carla/mars.html , this is a rather interesting read.

Answer 2

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

• tLow works, tMed and tHigh are currently locked (but not in the critical section).
• tLow enters and enters a critical section.
• tHigh unblocks and, since it is the highest priority task on the system, it starts.
• tHigh then tries to enter a critical resource, but blocks it like tLow.
• tMed unlocks and, since it is currently the task with the highest priority in the system, it starts.

tHigh cannot work until tLow issues a resource. tLow cannot work until it is locked or terminated. The priority of tasks has been inverted; tHigh, although it has the highest priority, is at the bottom of the execution chain.

In order to "solve" a priority inversion, the tLow priority must be superimposed to be at least equal to tHigh. Some of them may increase priority to the highest possible priority level. It is equally important how to raise the tLow priority level, lowers the tLow priority level at the corresponding time points. Different systems will use different approaches.

When tLow priority falls ...

• No other tasks are blocked on any of the resources that have tLow. This may be due to timeouts or resource release.
• No other tasks that increase tLow's priority level are blocked on resources that have tLow. This may be due to timeouts or resource release.
• When there are changes in which tasks are waiting for resources, remove the priority of tLow so that it matches the priority of the task with the highest priority blocked on its resource.

Method # 2 is an improvement on Method # 1 because it reduces the time that tLow has its priority level. Note that the priority level remains at the tHigh priority level during this period.

Method # 3 allows the tLow priority application to decrease in increments, if necessary, rather than in an all-or-nothing step.

Different systems will apply different methods depending on what factors they consider important.

• Memory size
• Complexity
• real-time responsiveness
• developer knowledge

Hope this helps.

Answer 3

Inversion priority task:
Consider one example: Tasks:
High priority (H)
Medium Priority (M)
Low priority (L)

and lock X, maybe semaphore_lock (X).

Scenario:
1. L starts and acquires X 2. Then H tries to access X when L has it, because of the semaphore H is sleeping.
3. M arrives, pre-empts L and starts. In fact, H and M were two processes awaiting execution, but M ran because H was waiting for a lock and could not start .
4. M ends, H cannot enter, because L has a lock, so L starts.
5. L ends, releases the lock. Now H gets the lock and executes.

H had the highest priority, but was executed after the execution of processes with a lower priority. This is a priority inversion.

Now the solution is priority inversion.
When a low priority process is running and has a lock, and if a high priority process tries to obtain a lock, the priority of the low priority process is increased to the priority of the high priority process. That is, if L is started and has a lock, when H tries to get it, the priority of L will be raised to the level H during the time L holding the lock. Therefore, M cannot pre-protect it. After L ends, H starts and acquires a lock. After executing H, M is executed, maintaining the order of priorities.

Answer 4

This is a problem , not a solution.

It describes a situation where low priority threads receive locks during their operation, high priority threads must wait for them to finish (which can take a particularly long time because they are low priority). The inversion here is that a high priority thread cannot continue until a low priority thread is executed, therefore it also has a low priority.

A common solution is that low priority threads temporarily inherit the high priority of all who are waiting for the locks they hold.

Answer 5

Suppose an application has three threads:

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

Assume that Thread 1 and Thread 3 use the same critical section code

At the beginning of the example, thread 1 and thread 2 drop or lock. Topic 3 launches and enters a critical section.

At this point, thread 2 starts, displacing thread 3, because thread 2 has a higher priority. So, stream 3 continues to own a critical sector.

Later, thread 1 starts, displacing thread 2. Thread 1 tries to enter the critical section to which thread 3 belongs, but since it belongs to another thread, thread 1 blocks, waiting for the critical section.

At this point, thread 2 starts because it has a higher priority than thread 3, and thread 1 does not work. Thread 3 never releases the critical section that thread 1 expects, as thread 2 continues to run.

Consequently, the thread with the highest priority in the system, thread 1, becomes blocked, waiting for threads with lower priority to execute.

Answer 6

[Assume low process = LP, medium process = MP, high process = HP]

LP performs a critical section. Upon entering the critical section, the LP had to get a lock on some object, say, OBJ. LP is now inside the critical section.

Meanwhile, HP is creating. Due to the higher priority, the CPU performs a context switch, and now HP executes (not the same critical section, but some other code). At some point during the execution of HP, it needs a lock on the same OBJ (it may or may not be in the same critical section), but the OBJ lock is still supported by LP, since it was previously removed during the execution of the critical section, LP cannot refuse because the process is in READY state and not in RUNNING. HP now moves to the BLOCKED / WAITING state.

Now MP enters and executes its own code. MP does not require OBJ locking, so it continues to work normally. HP waits for the LP to release the lock, and LP waits for the MP to complete execution so that the LP can return to the RUNNING state (.. and execute and release the lock). Only after the LP has released the lock does HP return to READY (and then go to RUNNING, previously omitting low priority tasks.)

Thus, this means that until the MP ends, the LP will not be able to execute and therefore HP will not be able to execute. Thus, it seems that HP is waiting for MP, even if they are not connected directly through any OBJ locks. → Priority inversion.

Priority Inversion Solution Priority Inheritance -

increase the priority of process (A) to the maximum priority of any other process that expects any resource on which A has a resource lock.

Answer 7

Priority inversion is a process in which a process with a lower priority gets the resource needed for a process with a higher priority, which prevents a process of a higher priority before releasing the resource.

for example: FileA must be accessible by Proc1 and Proc2. Proc 1 has higher priority than Proc2, but Proc2 first opens FileA.

Usually, Proc1 starts, maybe 10 times more often than Proc2, but it cannot do anything because Proc2 holds the file.

So what happens is that Proc1 is locked until Proc2 exits with FileA, in fact, their priorities are “inverted”, while Proc2 contains a FileA descriptor.

Regarding the “solution to the problem,” priority inversion is itself a problem if it continues to occur. In the worst case (most operating systems will not allow this) if Proc2 is not allowed to run until Proc1. This will lock the system, because Proc1 will receive the assigned processor time, and Proc2 will never receive the processor time, so the file will never be released.

Answer 8

Priority inversion arises as such: Given the processes H, M, and L, where names indicate high, medium, and low priorities, only H and L have a common resource.

Let's say L first gets the resource and starts working. Since H also needs this resource, it enters the waiting queue. M does not transfer the resource and can start working, therefore, it does. When L is interrupted by any means, M assumes the current state, as it has a higher priority, and it works the moment the interrupt occurs. Although H has a higher priority than M because it is in the waiting queue, it cannot receive a resource, implying a lower priority than even M. After the end, ML will again take the processor, making H wait all the time.

Answer 9

Priority inversion can be avoided if a blocked thread with a high priority transfers its high priority to a downstream that is held on the resource.

Answer 10

The scheduling task arises when a process with a higher priority must read or modify kernel data that is currently accessed by a process with a lower priority, or a chain of processes with a lower priority. Since kernel data is typically protected by a lock, a higher-priority process will have to wait for a lower priority to complete with the resource. The situation is complicated if a process with a lower priority is supplanted in favor of another process with a higher priority. As an example, suppose we have three processes: L, M, and H, whose priorities follow the order L <M <H. Suppose that process H requires a resource R, which process L is currently accessing. Typically, process H will wait for L to work using resource R. However, now suppose that process M becomes controllable, thereby crowding out process L. Indirectly, a process with a lower priority process M has an effect on how long process H has to wait until L will not give up resource R. This problem is known as inver Priority Ia. It is found only in systems with more than two priorities, so one solution is to have only two priorities. However, this is inefficient for most general purpose operating systems. Typically, these systems solve the problem by implementing a priority-inheritance protocol. According to this protocol, all processes that access the resources required by a higher-priority process inherit a higher priority until they are completed with the resources in question. When they are completed, their priorities return to their original values. In the above example, the priority-inheritance protocol will allow process L to temporarily inherit the priority of process H, thereby preventing process M from crowding out its execution. When process L quits using resource R, it will give up its inherited priority from H and take its original priority. Since resource R will now be available, the H-not M-process will work as follows. Reference: ABRAHAM SILBERSCHATZ

Answer 11

Consider a system with two processes H with high priority and L with low priority. The planning rules are such that H starts whenever it is in a ready state due to its high priority. At some point, with L in its critical area, H becomes ready to start (for example, an I / O operation is completed). H now starts waiting, but since L never planned while H running, L never gets a chance to exit the critical section. So, H loops forever.

This situation is called Priority Inversion . Because a higher priority process expects a lower priority process.

Answer 12

Let me make it very simple and clear. (This answer is based on the answers above, but is presented in a clear way).

Let's say there is a resource R and 3 processes. L , M , H where p(L) < p(M) < p(H) (where p(X) is the priority of X ).

Let's say

• L starts execution of the first, and catch - on R (exclusive access to R )
• H arrives later and also wants exclusive access to R , and since L holds it, H must wait.
• M appears after H and does not need R And since M has everything he wants to accomplish, he makes L quit because he has a high priority over L But H cannot do this, since he has a resource blocked by L , which he needs to execute.

Now, making the problem clearer, in fact, M must wait for H to complete as p(H) > p(M) , which did not happen, and this in itself is a problem. If many processes, such as M , enter and prevent L executing and releasing lock H , it will never be executed. What could be dangerous in temporary critical applications

And for solutions, see the answers above :)