Priority Scheduling Algorithm

January 20, 2023

Priority Scheduling

Priority Scheduling Algorithm in Operating System

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

Priority may also be of two types :

  1. Static
  2. Dynamic

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.

[table id=259 /]

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

Priority Scheduling Algorithm 1
OS dekstop gif
OS mobile gif

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

  • 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 = Completion Time – Burst Time  – Arrival TIme

  • Average Waiting Time for P1 = 3-3-0 = 0ms
  • Average Waiting Time for P2 = 10-4-0 = 6ms
  • Average Waiting Time for P3 = 6-2-0 = 4ms
  • Average Waiting Time for P4 = 4-1-0 = 3ms
  • Average Waiting Time for P5 = 13-3-0 = 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.

[table id=543 /]

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 2

Turn Around Time = Completion Time – Arrival Time

Waiting Time = Turn Around Time – Burst Time

 
  • Average Waiting Time for P1 = 3-0-3 =0
  • Average Waiting Time for P2= 18-2-5 =11
  • Average Waiting Time for P3= 7-1-4 =2
  • Average Waiting Time for P4= 13-4-2 =7
  • Average Waiting Time for P5= 27-6-9 =12
  • Average Waiting Time for P6= 11-5-4 =2
  • Average Waiting Time for P7= 37-7-10 =20

Avg Waiting Time = (0+11+2+7+12+2+20)/7 = 54/7 units = 7.714 ms

[table id=544 /]

Priority Scheduling Algorithm Preemptive

Note – Consider lower number to have higher priority.

[table id=545 /]

  • 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 Scheduling Algorithm 4
  • 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 Scheduling Algorithm 5
  • 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 Scheduling Algorithm 6-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 Scheduling Algorithm 7
  • 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 3
  1. Turnaround Time = Completion Time – Arrival Time   
  2. Waiting Time = Turn Around Time – Burst Time  
Average Waiting Time = (0+14+0+7+1+25+7)/7 = 54/7 = 7.71ms

[table id=546 /]

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
OS dekstop banner

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

4 comments on “Priority Scheduling Algorithm”