Priority Scheduling Program in C

Introduction

Process scheduling is a method used in selecting processes in a specific order from the total processes available to be executed. The queue in which all the processes ready to be executed are present is called the job queue. The queue in which the process selected in a specific order by the process scheduling algorithm is present is called the ready queue.

There are different algorithms to determine the order by which the process will be selected. This order will have an impact on the performance and speed of the operating systems. These different kinds of algorithms are being used in process scheduling to increase the efficiency of process execution. The priority scheduling algorithm is one of the scheduling algorithms designed to select the process from the ready queue into the job queue based on the priority assigned to the process.

What is Priority Scheduling Algorithm?

The priority scheduling algorithm follows a method by which a priority is set to the processes available for execution, and the process is selected based on the descending order of priority into the ready queue for execution by the CPU. Several factors can be used to determine the priority value of a process. The factors include the time taken to complete execution, memory spaces required by the process, etc.

There are two types of priority scheduling algorithms. They are,

• Priority Preemptive Scheduling Algorithm
• Priority Non-preemptive Scheduling Algorithm

In the Preemptive algorithm, during the execution of a process with high priority, if there is an arrival of another process with a priority higher than the process under execution, then the process currently under execution is stopped, and the new process is allowed to execute.

In the Non-preemptive algorithm, the process with the highest priority is allowed to execute in the CPU, and if there is an arrival of another process with a priority higher than the process under execution, then the new process will have to wait until the execution of the current process is completed.

Examples of Priority Scheduling Algorithm

Let us consider the following example to understand the priority scheduling algorithm clearly.

Consider there are 3 processes A, B, and C with the burst times 5,6 and 7, respectively. The priority of the three processes is 2,1 and 3, respectively. We can consider all the processes arrive on the ready queue at time 0. All the information is expressed in the table below,

According to the non-preemptive scheduling algorithm, the process with the highest priority will be executed first, followed by the process with low priority. Therefore, the order of execution of the process will be,

We generally use a gaunt chart to express this output. The following images give the Gantt chart of the problem,

We can see from the diagram that process A will have to wait until the execution of process C is completed to start execution.

Let us now consider the same problem, with the arrival time of processes A, B, and C being 1,3,2 respectively.

When a preemptive priority scheduling algorithm is used, process A is allowed to execute at a time of 1 second, and when process C enters the ready queue at a time of 2 seconds, process A is stopped, and process C is allowed to run. This can be useful in cases where a low-priority process may occupy a large amount of time and does not allow other higher-priority processes to execute. The order of execution will be,

Process A will be executed in two phases, the first phase will execute for a time of 1 second, and the second phase will execute for the remaining time of 4 seconds. Since process B has the lowest priority, process B is executed as the last process.

From the image, we can see that process A is executed in two phases according to the preemptive priority scheduling algorithm.

Characteristics of Priority Scheduling Algorithm

The characteristics of the priority scheduling algorithm in C are,

• Every process is associated with a priority number, and processes are executed according to that priority number.
• The priority scheduling algorithm is useful for performing batch processes.
• If there are two processes with the same priority, then the first process to reach the ready queue will be allowed to execute.
• In the case of preemptive priority scheduling, if a process with a higher priority arrives during the execution of a low-priority task, the low-priority task is paused, and the new task is allowed to be executed.
• The priority that can be modified is called dynamic priority, and which can't be modified is called static priority.

Program to Implement Priority Scheduling Algorithm

The following code shows the implementation of the Priority Scheduling program in C:

In the above example, we can assume that every process arrives in the ready queue at the same time(0).

• A process in the priority scheduling program in c is represented with a structure called struct priority_scheduling.
• Waiting time represents the time the process has to wait to enter into a state of execution. Turn around time represents the total time required for a process to complete execution.
• The process is ordered based on priority by swapping the lower priority process with a higher priority process using the temp_proces variable.
• The waiting time is calculated by adding the process's burst time and the previous process's waiting time. The waiting time of the first process is always 0.
• The turnaround time is calculated by adding the burst time and waiting time of the process.
• The average turnaround time and average waiting time are calculated by dividing the total waiting and average time by the total number of processes.
• These average times can be used to estimate the efficiency of the algorithm.

Output

The output for the priority scheduling program in C is shown below,

The output depicts the same order of execution as we have seen in the example section,C --> A --> B. Since the average waiting time of the above example is very less, we can assume that the algorithm is a good fit for the input processes.

The time complexity for the priority scheduling program in c for best, worst and average time is,

• Θ(N) for best case time complexity
• Θ(N) for Average case time complexity.
• Θ(N^2) for Worst case time complexity as here we have sorted according to the priority using the selection sort algorithm. The space complexity for the priority scheduling program in C is Θ(1).

The N in the time complexity represents the number of processes.

Advantages and Disadvantages

Some of the advantages of priority scheduling are,

• The priority scheduling algorithm provides a way to assign priorities to a process based on factors such as time of execution, memory requirements, etc...
• Important processes can be assigned higher priorities to be assured of faster execution.
• The algorithm is well defined for cases where there is a limited number of processes.

Some of the disadvantages of priority scheduling are,

• There is a possibility for a process with lower priority to not get a chance of execution for a long time. This property is called starvation.
• It is harder to choose the factor based on which priorities will be assigned.
• In case of crashes or damage to the computer, the low-priority process will be lost completely because of the not scheduling of these processes.
• The resources can't be utilized in parallel using this algorithm.