Priority Scheduling Algorithm in Operating System

Priority Scheduling is a process scheduling algorithm based on priority where the scheduler selects tasks according to priority. Thus, processes with higher priority execute first followed by processes with lower priorities.

If two jobs have the same priorities then the process that should execute first is chosen on the basis of round-robin or FCFS. Which process should have what priority depends on a process’ memory requirements, time requirements, the ratio of I/O burst to CPU burst, etc.

Types of Priority Scheduling

Following are the two main types of priority scheduling:

1. Preemptive Scheduling: Tasks execute according to their priorities. In case a lower priority task is running and a higher priority task arrives in the waiting state then the lower priority task is put on hold. The higher priority task replaces it and once done executing the lower priority task resumes execution from when it was paused. This process requires special hardware like a timer.

2. Non-Preemptive Scheduling: The OS allocates the CPU to a specific process that releases the CPU either through context switching or after termination. We can use this method on various hardware platforms because unlike preemptive scheduling it doesn’t require any special hardware.

Characteristics of Priority Scheduling

• Schedules processes on the basis of priority.
• Used to perform batch processes.
• In the case of two processes with similar priorities, we use FCFS and Round-Robin to choose between them.
• A number is given to each process to indicate its priority level.
• Lower is the number assigned, higher is the priority level of a process.
• If a higher priority task arrives when a lower priority task is executing, the higher priority task replaces the one with lower priority and the
• latter is put on hold until it completes execution.

Example of Priority Scheduling

Following five processes have a unique priority, burst time, and arrival time.

Step 0: At time = 0, two processes P1 and P2 arrive. Since P1(with a burst time 4) has higher priority it executes before P2.

Step 1: At time = 1, no new process arrives and execution of P1 continues.

Step 2: At time = 2, no new process arrives, P2 is in the waiting queue, and execution of P1 continues.

Step 3: At time = 3, no new process arrives, P2 is in the waiting queue, and execution of P1 continues.

Step 4: At time = 4, P1 finishes execution, and P2 starts execution.

Step 5: At time = 5, P2 continues execution as no new process arrives.

Step 6: At time = 6, P3 arrives and since it has a higher priority of 1 the OS preempts P2. P3 starts executing.

Step 7: At time = 7, P3 continues executing as no new process arrives and P2 is on hold in the waiting queue.

Step 8: At time = 8, we continue with P3 as no new process arrives.

Step 9: At time = 9, we continue with P3 as no new process arrives.

Step 10: At time = 10, we continue with P3 as no new process arrives.

Step 11: At time = 11, P4 arrives but P3 continues executing as it has a higher priority than P4.

Step 12: At time = 12, P5 arrives but P3 continues executing as it has a higher priority.

Step 13: At time = 13, P3 is done executing. Now there are three processes P2, P4, and P5 in the ready queue. Among these two processes have higher and similar priorities. These are P2 and P5. Since the arrival time of P2 is less than that of P5, P2 starts execution.

Step 14: At time = 14, P2 completes execution. In the waiting state between P4 and P5, P5 has a higher priority so it starts executing.

Step 15: At time = 15, P5 continues executing.

Step 16: At time = 16, P5 completes execution and since P4 is the only process present in the waiting state it starts executing.

Step 17: At time = 20, no process is left for execution as P5 completes execution.

Step 18: Following is the average waiting time: Waiting Time (Wt) = Start Time (St) – Arrival Time (At) + Waiting Time for next burst

P1 = 0 – 0 = 0

P2 = 4 – 0 + 7 = 11

P3 = 6 – 6 = 0

P4 = 16 – 11 = 5

Thus, the average waiting time is: (0+11+0+5+2)/5 = 18/5 = 3.6

Advantages of priority scheduling in OS

Following are the benefits of priority scheduling method:

• Easy to use.
• Processes with higher priority execute first which saves time.
• The importance of each process is precisely defined.
• A good algorithm for applications with fluctuating time and resource requirements.

Disadvantages of priority scheduling in OS

Following are the disadvantages of priority scheduling:

• We can lose all the low-priority processes if the system crashes.
• This process can cause starvation if high-priority processes take too much CPU time. The lower priority process can also be postponed for an indefinite time.
• There is a chance that a process can’t run even when it is ready as some other process is running currently.

Aging Technique

Aging technique can help prevent starvation of a process. In this, we can increase the priority of the low-priority processes based on their waiting time. This ensures that no process waits for an indefinite time to get CPU time.

Implementing priority scheduling algorithm in C++

Following is the code to implement priority scheduling algorithm in C++:

#include<bits/stdc++.h> 
using namespace std; 
  
struct Process 
{ 
    int pid;  //process ID
    int bt;   //CPU burst time 
    int priority; //priority of the process
}; 
  
bool sortProcesses(Process a, Process b) 
{ 
    return (a.priority > b.priority); 
} 

void findWaitingTime(Process proc[], int n, 
                     int wt[]) 
{ 
    wt[0] = 0; 
  
    for (int  i = 1; i < n ; i++ ) 
        wt[i] =  proc[i-1].bt + wt[i-1] ; 
} 
  
void findTurnAroundTime( Process proc[], int n, 
                         int wt[], int tat[]) 
{
    for (int  i = 0; i < n ; i++) 
        tat[i] = proc[i].bt + wt[i]; 
} 
 
void findavgTime(Process proc[], int n) 
{ 
    int wt[n], tat[n], total_wt = 0, total_tat = 0; 
    findWaitingTime(proc, n, wt); 
  
    findTurnAroundTime(proc, n, wt, tat); 
  
    cout << "\nProcesses  "<< " Burst time  "
         << " Waiting time  " << " Turnaround time\n"; //process details
  
    for (int  i=0; i<n; i++) 
    { 
        total_wt = total_wt + wt[i]; 
        total_tat = total_tat + tat[i]; 
        cout << "   " << proc[i].pid << "\t\t"
             << proc[i].bt << "\t    " << wt[i] 
             << "\t\t  " << tat[i] <<endl; 
    } 
  
    cout << "\nAverage waiting time = "
         << (float)total_wt / (float)n; 
    cout << "\nAverage turnaround time = "
         << (float)total_tat / (float)n; 
} 
  
void priorityScheduling(Process proc[], int n) 
{ 
    sort(proc, proc + n, sortProcesses); 
  
    cout<< "Order in which processes gets executed \n"; 
    for (int  i = 0 ; i <  n; i++) 
        cout << proc[i].pid <<" " ; 
  
    findavgTime(proc, n); 
} 
  
// Driver code 
int main() 
{ 
    Process proc[] = {{1, 10, 2}, {2, 5, 0}, {3, 8, 1}}; 
    int n = sizeof proc / sizeof proc[0]; 
    priorityScheduling(proc, n); 
    return 0; 
}

Summary

Priority Scheduling is a process scheduling algorithm based on priority where the scheduler selects tasks according to priority. Processes with higher priority execute first followed by the ones with lower priority. There are two types of priority scheduling: preemptive and non-preemptive. Aging techniques can help prevent starvation.