
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 Scheduling, and 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:
- 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.
-
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