Preemptive Priority Based Scheduling

Introduction

We know that various scheduling algorithms are used to assign resources to perform different tasks. One of these CPU algorithms is Priority based scheduling.

As the name itself suggests, it is related to the priority of the task to be performed.

In a nutshell, a priority is associated with each process, and the CPU is allocated to the process with the highest priority. 

Where is it used?

It is used in operating systems to perform batch processes.

Now, a natural question comes to mind – On what factors the priorities are based on?

See, the priority of a task can be decided either externally or internally. 

Some of the internal factors can be – 

• time limits  
• memory requirements of the process 
• the ratio of average I/O burst to average CPU burst.

Whereas the external factors can be – 

• importance of the task
• amount of funds allotted for computer use
• the sponsoring department of the work, etc. 

If two or more tasks have equal priority, they are executed on FCFS(first come, first serve) basis, i.e., the process that arrived first among them will be given CPU first.

How are the priorities represented?

These are generally depicted by some fixed range of numbers, like 0 to 7 or 0 to 4095. Depending on the systems, the high priority can be represented by either low numbers or by high numbers.

Note: Throughout this article, we will be considering low numbers as a high priority.

We know about the SJF(shortest job first) scheduling algorithm. An interesting point here, it is also a type of priority based scheduling algorithm in which the priority of a process is inversely proportional to the next CPU burst. It means that the process with the next smallest CPU burst will have higher priority and will be assigned CPU first and vice versa.

If you are not aware of the SJF algorithm, you can read about it here.

Types of Priority Based Scheduling

1. Non- Preemptive Scheduling 
2. Preemptive Scheduling

Non-Preemptive Scheduling

In this algorithm, if a new process of higher priority than the currently running process arrives, then the currently executing process is not disturbed. Rather, the newly arrived process is put at the head of the ready queue, i.e. according to its priority in the queue. And when the execution of the currently running process is complete, the newly arrived process will be given the CPU.

Preemptive Scheduling

It is a priority scheduling algorithm in which the CPU is preempted when a new process arrives i.e it will start executing the new process if the newly arrived process is of higher priority than the currently running process.

Now, let’s consider an example to understand this better.

Note: Burst time is the time taken by a process to complete its execution.

Now what we will do is, we will form a Gantt Chart to schedule these processes using Preemptive priority-scheduling:

In this example, we will consider the process with the lower priority number has higher priority.

Steps to make Gantt chart for scheduling are as follows – 

1. At time=0, there are two processes that arrive – P1 and P2. Priority of P1 is 1, and that of P2 is 2. So, P1 is executed first as it has a higher priority.

2. From time=1 to time=3, no new process arrives. So, the execution of P1 continues, and P2 is waiting in the queue.
3. At time=4, P1 completes its execution. So, P2 starts executing.

4. At time=5, P2 continues execution as no new process arrives.
5. At time=6, P3 arrives and its priority is 1, which is higher than the currently executing process P2 having priority 2.So, P3 is given the CPU and P2 is stopped. (as it is preemptive)

We see that the burst time of P2 is 3, and it gets executed from time=4 to time=6. So, It has completed 2 out of 3 bursts. 

Then, P3 is inserted into the chart. 

6. At time 7, no new process arrives, so we continue with P3. P2 is in the waiting queue.
7. At time= 8, no new process arrives so that we can continue with P3.
8. At time interval 10, no new process comes, so we continue with P3
9.  At time=11, P4 arrives with priority 4. P3 has a higher priority, so it continues its execution.

10. At time=12, P5 arrives. P3 has a higher priority, so it continues execution.

11.  At time=13, P3 completes execution. We have P2, P4, P5 in the ready queue. P2 and P5 have equal priority. The arrival time of P2 is before P5. So P2 starts execution.

12. At time =14, the P2 process has finished its execution. P4 and P5 are in the waiting state. P5 has the highest priority and starts execution.

13. At time =15, P5 continues execution.
14. At time= 16, P5 is finished with its execution. P4 is the only process left. It starts execution.

The burst time of P4 is 4, and P4 is the only process left, so it finishes its execution at time=20.

Turnaround Time = Completion Time - Arrival Time   
Waiting Time = Turnaround Time - Burst Time  
Average waiting time = 
(Sum of waiting time of all processes)/(Number of Processes)

This chart contains the calculated Completion time, Turnaround time and Waiting time for all the processes using the formula mentioned above  – 

P1 = 0 - 0 = 0
P2 =4 - 0 + 7 =11
P3= 6-6=0
P4= 16-11=5
P5=14-12 = 2
Average Waiting time = (0+11+0+5+2)/5 = 18/5= 3.6

C++ Implementation

// C++ Implementation of Preemptive Priority Scheduling
#include <iostream>
using namespace std;
int main()
{
    int n = 5; //number of processes to be scheduled
    int arrivalTime[n] = {0, 0, 6, 11, 12};
    int burstTime[n] = {4, 3, 7, 4, 2};
    int priority[n + 1] = {1, 2, 1, 3, 2};
    int x[n];

    int waitingTime[n], turnaroundTime[n], completionTime[n];
    int i, j, smallest, count = 0, time; // count -> number of processes completed
    double avg = 0, tt = 0, end;

    for (i = 0; i < n; i++)
        x[i] = burstTime[i];

    priority[n] = 10000;

    for (time = 0; count != n; time++)
    {
        smallest = n;
        for (i = 0; i < n; i++)
        {
            if (arrivalTime[i] <= time && priority[i] < priority[smallest] && burstTime[i] > 0)
                smallest = i;
        }
        burstTime[smallest]--;
        if (burstTime[smallest] == 0)
        {
            count++;
            end = time + 1;
            completionTime[smallest] = end;
            waitingTime[smallest] = end - arrivalTime[smallest] - x[smallest];
            turnaroundTime[smallest] = end - arrivalTime[smallest];
        }
    }
    cout << "Process"
        << "\t  "
        << "burst-time"
        << "\t "
        << "arrival-time"
        << "\t "
        << "waiting-time"
        << "\t"
        << "turnaround-time"
        << "\t "
        << "completion-time"
        << "\t"
        << "Priority" << endl;
    for (i = 0; i < n; i++)
    {
        cout << "p" << i + 1 << "\t\t" << x[i] << "\t\t" << arrivalTime[i] << "\t\t" << waitingTime[i] << "\t\t" << turnaroundTime[i] << "\t\t" << completionTime[i] << "\t\t" << priority[i] << endl;
        avg = avg + waitingTime[i];
        tt = tt + turnaroundTime[i];
    }
    cout << "\n\nAverage waiting time time = " << avg / n;
    cout << "  Average turnaround time time = " << tt / n << endl;
}

Output 

Process   burst-time     arrival-time    waiting-time   turnaround-time  completion-time        Priority
p1              4               0               0               4               4               1
p2              3               0               11              14              14              2
p3              7               6               0               7               13              1
p4              4               11              5               9               20              3
p5              2               12              2               4               16              2


Average waiting time time = 3.6  Average turnaround time time = 7.6

Advantages of Priority Based Scheduling

• Processes having higher priority need not wait for a longer time due to other processes running.
• The relative importance of processes can be defined.
• The applications in which the requirements of time and resources fluctuate are useful.

Disadvantages of Priority Based Scheduling

• One of the major problems with this algorithm is indefinite blocking or starvation.
• A process that is ready to run but waiting for the CPU can be considered blocked.
• This algorithm may leave some low priority processes to wait indefinitely.
• All the low priority tasks may get lost when the system crashes eventually.

Frequently Asked Questions

Key Takeaways

In this article, we learned about the priority based scheduling algorithm, its advantages, disadvantages, and implementation in C++. This article also discussed the types of Priority based scheduling algorithms, namely Preemptive and  Non-Preemptive. 

You can learn more about the various scheduling algorithms in operating systems like FCFS, SJF and many more interesting concepts related to operation systems here. Practising problems also helps to gain a clearer picture of the concepts. So, Do Practice questions from CodeStudio and check your understanding.

By: Yukti Kumari