Priority Scheduling Algorithm

Priority Scheduling Algorithm in Operating System

In Priority Scheduling, processes are assigned Priorities and the process with highest is executed first. Each process is assigned a priority & process is are given CPU time according to their priority.

There are two types of Priority Scheduling Algorithm.

  1. Preemptive
  2. Non Preemptive

Priority may also be of two types

  1. Static
  2. Dynamic
Priority Scheduling Types OS Operating System

Rules

In some systems, lower priority number means that higher priority (Example P1 with priority 1 and P2 with priority 4, in this case P1 will have higher priority). However, in some system its opposite, higher priority number means higher priority.

Students may get confused with this. Thus, Gate now specifically mentions which one is the highest and which one is the lowest. However, if this information is not given in exams like placement tests etc. Then lower priority number means higher priority.

This information is given incorrectly in Geeks4Geeks thus, most students solve the questions incorrectly.

  • If 2 processes have equal priorities the those process are scheduled in First Come First Serve order.
  • Priority can be defined internally or externally.
  • It can be either preemptive or non preemptive algorithm.

Preemptive vs Non Preemptive

First Come First Serve (FCFS) is a special type of priority scheduling where all processes are assigned equal process. Similarly, Shortest Job first (SJF) is also a special type in which the one having least CPU burst time is given a high priority.

As we know, Preemptive Priority Scheduling Algorithm are those algorithm where if a new process having higher priority arrives than the process currently executing , CPU stops the current executing process and executes the newly arrived higher priority process. Non Preemptive Priority Scheduling Algorithm is an algorithm where even if a higher priority process comes, if a process is already being executed, it will first finish the current process . Only then, next process will be executed.

Priority Scheduling Example 1 (Non-Preemptive)

Let’s try to understand Priority Scheduling with the help of an example (For Ease of understanding, for first example arrival time for all is 0) –

In our example consider the lowest value as the highest Priority and note we are considering non preemptive algorithm in nature thus no dynamic priority change will be there.

ProcessExecution TimePriorityArrival Time
P131 (Highest)0
P2430
P3220
P411 (Highest)0
P534 (Lowest)0

We suggest solving it on your own and not looking the solution and explanation below –

Priority Scheduling Algorithm Non Preemptive Operating System
  • Both P1 and P4 have the highest Priority(1). Thus we will use FCFS to settle clash and P1 will execute first.
  • P4 will execute once P1 is finished executing
  • P3 has priority 2 thus it will execute next.
  • Then finally P2 and P5

Average Waiting Time for processes are –

  • Average Waiting Time for P1 = 0ms
  • Average Waiting Time for P2 = 6ms
  • Average Waiting Time for P3 = 4ms
  • Average Waiting Time for P4 = 3ms
  • Average Waiting Time for P5 = 10ms

Average waiting Time for all processes = (0 + 6 + 4 + 3 +10)/5 = 4.6ms

Disadvantages

Like FCFS and SJF , a process having lower priority can be indefinite blocked or starved. To prevent this, we do aging where the priority of the process is increased as it waits in the queue. So, a process which has been in a queue for a long time will reach high priority, hence it won’t be starved.

Priority Scheduling Example 2 (Non-Preemptive)

In this example we will complicate things as the arrival time for algorithms will not be same.

Note – Consider lower number to have higher priority.

ProcessExecution Time (Burst)PriorityArrival Time
P1320
P2562
P3431
P4254
P5976
P6445
P710107

Steps –

  1. At time t = 0, there is only process that has arrived i.e. P1 so it will execute first for next 3 ms.
  2. At time t = 0, P1 is completed and there are two more processes that have arrived, P2 and P3
    1. P2 has priority 6 and P3 has 3
    2. Thus P3 will execute for next 4 ms, i.e. till t = 7 ms.
  3. At time t = 7ms all the processes have arrived.
  4. Thus, P6 with priority 4 will be next 
  5. Similarly, P4 -> P2 -> P5 and then P7

The Gantt Chart will look like –

Priority Scheduling Algorithm Example 2 Operating System
  • Turn Around Time = Completion Time – Arrival Time
  • Waiting Time = Turn Around Time – Burst Time

Avg Waiting Time = (0+11+2+7+12+2+18)/7 = 52/7 units

ProcessExecution Time (Burst)PriorityArrival TimeCompletion TimeTurnaround TimeWaiting TimeResponse Time
P13203300
P256218161113
P34317623
P4254139711
P597627211218
P644511627
P71010737301827

Priority Scheduling Algorithm Preemptive

Note – Consider lower number to have higher priority.

ProcessExecution Time (Burst)PriorityArrival Time
P1120
P2761
P3332
P4653
P5544
P615105
P78915
  • At time t = 0

Only P1 has arrived and since its only process currently even though has lowest priority it will get processing time and has burst time of 1ms.

Priority 1
  • At time t = 1

At time t = 1 P2 has arrived and no other process thus it will get processing time

  • At time t = 2

P2 is still running but, P3 has also arrived.

P3 has priority of 3 while P2 has priority of 6. Thus –

  1. P2 will stop and P3 will get execution time.
  2. P3 has execution time of 3ms in this time 3 more processes arrive namely – P4, P5 and P6. But all of them have lower priority than P3, thus these can’t preempt the process and P3 will complete its execution time.
  • Till time t = 5 P3 will run and complete its processing
Priority 2 (1)
  • At time t = 5

There are P2 (Priority = 6), P4 (Priority = 5), P5 (Priority = 4) and P6 (Priority = 10) that have arrived, out of which P5 has the highest priority as it has lowest value. Thus P5 will continue.

P5 has execution time of 5 ms. In this time P7 will have also arrived but. That also has lower priority than P5 thus P5 will continue its execution time.

  • Till time t = 10 P5 will run and complete its processing.
Priority 3 (1)
  • At time t = 10

P2 P4 and P6 have arrived and P7 which will arrive at 15 ms.

Thus P4 will run as it has lowest priority of 5 and has burst time of 6 ms.

However, at t = 15ms P7 has arrived but, still priority of P4 is higher. It will continue to run.

Priority 4 (2)
  • At time t = 16 ms

All processes have arrived, thus there is no need for any type of preemption. It will follow normal priority procedure.

Currently processes are P2, P6 and P7. P2 has lowest priority of 6 and then P7 has next of 9 and finally P6 of 10.

Thus P2 (Burst time = 7 but 1ms was served previously, so 6ms) -> P7 and P8 will run in sequence and complete the whole process.

  • At t = 45 ms process will complete.
Priority Scheduling Algorithm Preemptive 5
  1. Turnaround Time = Completion Time – Arrival Time   
  2. Waiting Time = Turn Around Time – Burst Time   
ProcessExecution Time (Burst)PriorityArrival TimeCompletion TimeTurn around TimeWaiting Time
P1120110
P2761222114
P3332530
P465316137
P55441061
P615105454025
P78915302416

Please Login/Signup to comment