In this tutorial, we will learn about preemptive or non preemptive priority scheduling technique in operating system. We will see a clear explanation to this concept with different examples.
Priority scheduling is an algorithm of scheduling processes based on priority. Each process is assigned a priority. Then, Based on priority, scheduling is done. Process with highest priority is to be executed first and so on. Process with same priority are executed on First Come First Serve basis. Priority scheduling is one of the most common algorithm in Batch System.
Difference Between Preemptive and Non Preemptive Priority Scheduling
In non-preemptive priority scheduling, once all the available processes are in the ready queue, the scheduled process will run till the completion with no preemption.
In the preemptive priority scheduling, the process which is being executed can be stopped at the arrival of a high priority process.
Some Formulas used to calculate turn around time and waiting time –
Turn Around Time = Completion Time – Arrival Time
Waiting Time = Turn Around Time – Burst Time
Let us take an example to understand this scheduling:
1. Non Preemptive Priority Scheduling
Consider 4 processes P1, P2, P3 and P4 with burst time, priority and completion time as given below –
We can represent this example using GANTT chart as below –
In this example, we are considering the smallest digit as highest priority and largest digit as lowest priority. If the arrival time is not available let us assume it as 0 for all the processes. According to non-preemptive priority scheduling, process P2 has the highest priority which will execute first and completes its execution.
After this, P1 will execute and completes its execution. P4 will be picked from ready queue after P2 and finishes its execution. As we can see in the example, process P3 has lowest priority so it executes at the end and completes its execution.
2. Preemptive Priority Scheduling
Consider 7 processes P1, P2, P3, P4, P5, P6 and P7 with burst time, priority and arrival time shown as below –
We can also represent this example using GANTT chart as below –
At Arrival Time (AT) = 0, P1 process will be picked from the ready queue. P1 is going to run for 1 unit of time because next process’s arrival time is 1 as well as high priority. After that P2 is picked from ready queue and will run for 1 unit of time, similar to that of P1. Next P3 will be executed for 1 unit of time.
At AT=3, P4 will be picked from the ready queue and is going to run for 2 units of time. This is because after the execution of P4, the process P5 has the lowest priority and so it is ideal to schedule for 2 units of time. Then, P6 can be scheduled with high priority. So, it will run till completion time and finishes its execution.
Once all the process has arrived in ready queue, preemptive scheduling will behave like non- preemptive priority scheduling. P4 has highest priority in remaining process. So, P4 will execute till completion time and finishes its execution.
After P4, P7 has highest priority. So, it will be scheduled and finish its execution. Then, P5 will complete its execution. According to priority criteria, the processes completes its execution in the order P5, P3, P2 and P1.
Advantages of Priority Scheduling
2. Suitable for application with varying time and resource requirement
3. Process with high priority will execute first. It results in better response time.
Disadvantages of Priority Scheduling
1. Indefinite blocking or starvation.
2. Priority scheduling can leave some low priority waiting processes indefinitely for CPU.
3. If the system eventually crashes, then unfinished low priority process are lost.
It is a situation in which the continuous arrival of higher priority process keeps the lowest priority process always in waiting state. The waiting process will starve (in other words, the deadline of the waiting process will never meet). We can resolve the starvation problem in the priority scheduling with the help of Aging technique.
In Aging technique, the priority of every lower priority processes has to be increased after a fixed interval of time.