1. Introduction

In this tutorial, we’ll cover priority inversion in process scheduling and how to avoid it.

2. Priority Inversion

Priority inversion can happen in preemptive priority-driven scheduling of processes. Here, all processes have priorities, and the goal is to give precedence to those ranked higher.

That means that no process should wait for another with a lower priority to be completed. Yet, that’s precisely what happens in priority inversion: a less important process can block a more important one.

If the inversion is unbounded, this can lead to unpredictable and undesired behavior since the point of priorities is to guarantee that prioritized processes don’t starve or wait too long.

3. Examples

Let’s say we have three processes: A, B, and C. Their priorities are:

    \[priority(A) < priority(B) < priority(C)\]

Additionally, A and C use the same resource in their critical sections, which B doesn’t use.

If A isn’t executing its critical section, and C gets ready to run, A will be pre-empted to make room for C,  and if B gets ready while C is running, it will have to wait:

No inversion

This is in line with their priorities.

However,  if it’s running its critical section, A can block C:

Short inversion

This is a form of the priority inversion we can tolerate if A can complete its critical section fast.

3.1. Unbounded Inversion

If B gets ready while C is blocked, we get an unbounded priority inversion. Since B doesn’t use the same resource as A, it’s ready to run immediately, so A gets pre-empted because it has a lower priority, and B takes control of the CPU.

However, C can’t take the CPU from B since the required resource is locked by A. So, although C has a higher priority, it’s waiting for B as if it’s the other way around:

Unbounded priority inversion

This is a problem because it defeats the purpose of priorities. If it hadn’t been important to prioritize C over B, we wouldn’t have used a higher priority level for C in the first place. Additionally, C is made to wait because of an unrelated process: B doesn’t use any resource that C needs but can make it wait indefinitely.

4. Priority Inheritance

There are several ways of avoiding this problem. We’ll explain the strategy called priority inheritance.

In it, the process holding a lock over a resource inherits the priority of the highest-priority process waiting for that resource. We apply this rule only if the process with a lock has a lower priority than those waiting and only until it releases the lock.

So, once C gets blocked by A, we temporarily increase the priority of A to that of C. That way, B won’t take the CPU from A since the new priority of A is higher. As a result, A completes its critical section and releases the lock with no interruption by B. Afterward, we restore the old priority of A:

Priority inherinatce

When A releases the CPU, C can take it over since its priority is higher than that of B.

5. Conclusion

In this article, we explained priority inversion. It happens when a process with a higher priority waits for a process with a lower one. We can solve this problem with priority inheritance.

Inline Feedbacks
View all comments