Table of contents
1.
Introduction
2.
Priority Inversion
3.
Frequently Asked Questions
3.1.
What is the difference between preemptive and non-preemptive priority scheduling?
3.2.
What is the solution to Priority Inversion?
3.3.
Which scheduler is responsible for selecting the next process to be executed by the CPU?
3.4.
What is a critical section?
3.5.
What is priority scheduling?
4.
Conclusion
Last Updated: Mar 27, 2024

Priority Inversion

Author Teesha Goyal
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Operating Systems

Introduction

Our systems have a lot of processes to run and execute. To manage this, we have a variety of algorithms such as First Come First Serve(FCFS)Shortest Job First(SJF)Round Robin (RR)Preemptive Priority Based Schedulingand Non-Preemptive Priority Based Scheduling. Some of these are preemptive, and some are non-preemptive. To learn more about CPU scheduling algorithms, go to CPU Scheduling

Also see, Process Synchronization

Priority Inversion

Priority Inversion is a problem that arises when we are working with priority scheduling in operating systems. Priority scheduling work in both preemptive and non-preemptive manner. In priority scheduling, each process is assigned a priority that determines how the processes are to be executed. In preemptive scheduling, a higher priority process can interrupt a lower priority process and take control of the CPU.

The picture is clear, but when we bring process synchronization into the picture, the situation becomes a little complicated. There are a lot of processes running on a single system, so there are times when different processes need to access the same variable and maybe make changes to it. If the processes are running concurrently, then the sequence in which the instructions are executed changes the final value of the shared variable, so to maintain consistency in our data, we introduce process synchronization. 

There are various ways to achieve process synchronization, such as Disabling interrupts, using locks or mutex, semaphores, and monitors. To understand priority inversion, let's say we are using mutex as a way of process synchronization.

The part of the process that accesses shared variables is called the critical section. When a process enters a critical section, it acquires a lock or mutex on the shared variables. When another process needs to access this shared variable, it has to wait for the previous process to come out of the critical section and release the lock. This is the working of a mutex. 

Suppose two processes are running concurrently, one with lower priority, let's call it L, and one with higher priority, let's call it H. Now, if L is running and H comes in the ready queue, L is preempted, and H takes the control and terminates, L starts running after H terminates and completes its execution. This is the ideal case. 

Let's say both L and H are running concurrently, and both need to access a common variable this time; there are two possible situations:

  1. L is running not in the CS; H arrives, preempts L, starts executing, enters CS, executes, exits CS, and terminates. Now L resumes, enters CS, executes, exits CS, and terminates.
  2. L is running in the CS, H arrives, preempts L, executes until it needs to enter CS, L gets the control back, exits CS, H resumes, enters CS, executes, exits CS, terminates, L resumes, and executes.
     

In both these cases, priority inversion doesn't occur as the processes are running in the manner that is supposed to run under the mutex method of process synchronization. The priority inversion problem occurs when the third process with medium priority M comes into the picture.

Suppose a scenario where L is running in the critical section and H is waiting for L to come out of the critical section to resume its execution. The third process with medium priority M comes in the ready queue. Now priority order is L<M<H. Note that L and H share a variable that needs access to the critical section, but M does not involve any commonly shared variable with L or H. So when M comes in the ready queue, it preempts L as the priority of M is higher than L, completes its execution and terminates, L resumes, exits CS, H resumes, completes its execution and terminates, L resumes and terminates.

Here when M preempts L and starts executing, it cannot be preempted by H even though the priority of H is higher than M because H is waiting for L to come out of CS. This leads to H waiting for M to finish its execution so that L can resume and exit the CS. This is the problem of priority inversion. 

The solution to Priority Inversion is Priority Inheritance. In the above example, with the help of priority inheritance, when L is executing, it will inherit the priority of H as H is waiting for it to come out of CS. Now M would not be able to preempt L, and the system works fine again.

Also Read About, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking

Frequently Asked Questions

What is the difference between preemptive and non-preemptive priority scheduling?

In preemptive priority scheduling, when a higher priority process comes in the ready queue, it can preempt the lower priority process and complete its execution. But in non-preemptive, processes can not be preempted or interrupted once they start executing.

What is the solution to Priority Inversion?

The solution to Priority Inversion is Priority Inheritance. In priority inheritance, we assign the priority to the process that has the highest priority among the process waiting for the lower priority complete.

Which scheduler is responsible for selecting the next process to be executed by the CPU?

The short-term scheduler selects the process that needs to be assigned to the CPU next. It is the dispatcher that actually loads the process in the main memory to be executed.

What is a critical section?

A critical section is that part of the process that accesses the shared variables. No two processes can be in the critical section at the same time that accesses the same shared variables.

What is priority scheduling?

In priority scheduling, each process is assigned a priority, and the order of execution of the process depends upon the priority assigned. Higher priority processes are executed first.

Conclusion

In this article, We have discussed the problem of Priority Inversion. We also discussed the solution of Priority Inversion, which is Priority Inheritance. To learn the operating system in detail, visit Operating System Track. I hope you would have gained a better understanding of these topics now!

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Live masterclass