Why preemption does not solve priority inversion?

Question

I would like to know why preemption does not solve priority inversion problem?
If we have preemptive kernel. Then why priority inversion problem does not get solved?

Answer 1

Ok, let's say we have two processes. Let's also assume that the process which has lower priority gets a lock. When the higher-priority process becomes ready, it preempts the other process. If the higher-priority process needs that lock, it can't get it due to the other process which has lower priority. That means, lower-priority process blocks the higher-priority one. It prevents higher-priority process from running. This is called "Priority Inversion".

Obviously, preemption is not a solution for priority inversion. The solution is "Priority Inheritance". It means that we should temporarily increase the process's priority whenever it acquires a lock that is also needed by a higher-priority process. It should be the highest-priority process among the other processes which might want the same lock.

Answer 2

Let 3 threads A, B, C with respective priority High, Medium, Low.

C gets the processor and take a lock L. Then B is waken up by some events and preempts C. Now A is waken up and get the processor by preempting B. A wants the lock L, but fails because L is already owned by C. A gets preempted because of lock unavailability and gives back the processor to B. We have to wait for B to complete, which will eventually ends up in giving back the processor to C. C will complete and release the lock, which will finally wake up A.

This is a priority inversion because B runs whereas we have a thread A in the system with a higher priority waiting for completion of a lower priority thread (C in this case).

By the way, the solution is priority inheritance.

Answer 3

Preemption means taking away the processor so that a task no longer runs.

This is not enough, because the low priority task holds a resource which the high priority task needs.

Now if the resource could just be taken away (a different kind of "preemption") then this would indeed solve the priority inversion. But this is usually not possible, because the half-finished action of the low priority task would lead to inconsistencies.

Answer 4

Suppose you have 3 processes:

• A - high priority
• B - normal priority
• C - low priority

and also that A and C both uses, say, the same file (this could be any shared resource) whose usage must be synchronized.

Now suppose neither A and B are ready to run, and C runs and obtains the lock to use the file. While C was holding the lock to the file, A gets ready to run, and the operating system preempts C, and runs A. A executes to the point it is also in need of the file, and when it tries to obtain the lock, it is blocked because C is holding the lock. If in mean time B got ready to run, it will be executed instead of A because A is not ready to run. In order for A to be ready, the file lock must be released by C, and C won't run and release the lock because higher priority process B is running. Thus A is waiting for C whose in turn is waiting for B. Just preempting B in this situation would do no good, because A is not ready, and won't be unless C runs, and C can not run because the just preempted higher priority B is ready to run.

Answer 5

From Wiki

Consider,

L --> Low Priority Task
H --> High Priority Task
M --> Medium Priority Task
R --> Resource

Step 1: L acquires R
Step 2: H Requests R(Currently in use with L. so H will wait for L to relinquish R.)
Step 3: M Arrives(M is a non-blocked Task. i.e It does not requires R)
Step 4: L is preempted by M.(so L can't relinquish R. Due to this, H can't run.)

After M finished it's execution, L will relinquishes R. After that only H can continue. In the scenario above, a task with medium priority(M) ran before a task with high priority(H).

This is the actual priority inversion scenario in preemptive kernel.

Answer 6

priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks.

Consider there is a task L, with low priority. This task requires resource R. Consider that L is running and it acquires resource R. Now, there is another task H, with high priority. This task also requires resource R. Consider H starts after L has acquired resource R. Now H has to wait until L relinquishes resource R. Everything works as expected up to this point, but problems arise when a new task M (which does not use R) starts with medium priority during this time. Since R is still in use (by L), H cannot run. Since M is the highest priority unblocked task, it will be scheduled before L. Since L has been preempted by M, L cannot relinquish R. So M will run till it is finished, then L will run - at least up to a point where it can relinquish R - and then H will run. Thus, in the scenario above, a task with medium priority ran before a task with high priority, effectively giving us a priority inversion.