优先级反转

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: , , and . Their priorities are:

   

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

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

This is in line with their priorities.

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

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

3.1. Unbounded Inversion

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

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

This is a problem because it defeats the purpose of priorities. If it hadn’t been important to prioritize over , we wouldn’t have used a higher priority level for in the first place. Additionally, is made to wait because of an unrelated process: doesn’t use any resource that 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 gets blocked by , we temporarily increase the priority of to that of . That way, won’t take the CPU from since the new priority of is higher. As a result, completes its critical section and releases the lock with no interruption by . Afterward, we restore the old priority of :

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

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.