Priority Scheduling Program in C

Introduction

Priority scheduling is a type of CPU scheduling algorithm that decides which process to run next based on priority. Each process is assigned a priority, & the process with the highest priority gets scheduled first. Priority can be decided based on factors like importance, resource requirements, or how long the process has been waiting. Priority scheduling ensures that critical tasks are completed quickly while less important tasks wait until CPU time becomes available.

In this article, we'll talk about what priority scheduling is, how prioritization is determined, the different types of priority scheduling algorithms, a detailed example, the algorithm & code for implementing priority scheduling in C.

What is Priority Scheduling?

Priority scheduling is a method used by operating systems to manage how processes are handled based on their importance. Each process is assigned a priority level, usually a number. When several processes are ready to run, the operating system checks their priority levels. The process with the highest priority runs first, and others wait in line based on their priority. This way, important tasks are completed quickly, improving the efficiency of the system.

This approach can be particularly useful in environments where certain tasks need immediate attention over others, like in real-time systems where delays in critical process execution could lead to undesired outcomes.

How is the Prioritization Decided?

The prioritization of processes in priority scheduling is determined by assigning each process a priority level. The priority can be decided based on various factors depending on the system & the specific requirements. Some common criteria used to determine priority include:

Importance of the task: Critical tasks that need to be completed quickly, such as system processes or real-time applications, are often assigned higher priorities.
Resource requirements: Processes that require more system resources, like memory or I/O devices, may be given higher priority to ensure they have access to the necessary resources.
Time waiting: The longer a process has been waiting for CPU time, the higher its priority may become. This technique, known as aging, helps prevent starvation of low-priority processes.
User-defined priorities: In some systems, users or administrators can manually assign priorities to processes based on their specific needs.
Process type: Foreground processes, which interact directly with users, often have higher priority than background processes that run in the background.

The specific method used to assign priorities can vary between operating systems & scheduling algorithms. Some systems use a fixed priority scheme where each process is assigned a constant priority, while others use dynamic priorities that can change over time based on factors like aging or resource usage.

Lower numbers often represent higher priorities, meaning a process with a priority level of 1 would run before a process with a priority level of 3. However, some systems may use the opposite convention where higher numbers represent higher priorities. It’s crucial for those managing the system to understand their specific operating system's rules regarding priority levels.

Types of Priority Scheduling Algorithms

Priority scheduling can be divided into two main types: non-preemptive and preemptive. Understanding these types is crucial for implementing effective scheduling in various computing environments.

Non-preemptive Priority Scheduling

In non-preemptive priority scheduling, once a process starts executing, it runs to completion. It cannot be interrupted by another process with a higher priority. This means that the process currently using the CPU will continue to do so until it either completes its task or voluntarily relinquishes control of the CPU, typically when waiting for input or an event. Non-preemptive scheduling is simpler to implement and understand but can lead to issues like priority inversion, where a low-priority task holds a resource needed by a high-priority task.

Preemptive Priority Scheduling

Preemptive scheduling allows a process to be interrupted in the middle of its execution if a higher priority process becomes ready to run. This is more complex to implement as it requires the system to manage the state of interrupted processes so they can be resumed later. However, it is more efficient at ensuring that high-priority processes receive the CPU time they need without undue delay. It helps in scenarios where response time is critical, such as in real-time systems.

Next. we will talk about these 2 types of Scheduling in detail.

Non-preemptive Priority Scheduling Algorithm

The non-preemptive priority scheduling algorithm assigns CPU time to processes based on their priority level without interrupting a process once it starts running. This approach ensures that a process, once begun, is allowed to complete its task without being stopped for another process to take over, regardless of the priority of the incoming process.

Process Arrival: When a process arrives in the ready queue, it is assigned a priority based on the prioritization criteria discussed earlier.
Process Selection: The process with the highest priority is selected from the ready queue to be executed next. If multiple processes have the same highest priority, they are scheduled in a first-come, first-served (FCFS) manner.
Process Execution: The selected process is allocated the CPU & starts executing. It continues to run until one of the following conditions occurs:
The process completes its execution & terminates.
The process voluntarily releases control of the CPU by performing an I/O operation or waiting for an event.
Process Completion or Blocking: If the process completes its execution, it is removed from the system. If the process performs an I/O operation or waits for an event, it is moved to the corresponding waiting queue & the CPU becomes available for the next process.
Repeat: Steps 2-4 are repeated until all processes have been executed or there are no more processes in the ready queue.

The key point to note in non-preemptive priority scheduling is that once a process starts executing, it cannot be interrupted by a higher priority process. The higher priority process must wait until the currently running process completes or voluntarily releases the CPU.

Here's an example to illustrate non-preemptive priority scheduling:

In this example, the processes arrive at different times & have different priorities. The scheduling would occur as follows:

At time 0, P1 arrives & starts executing since it's the only process in the ready queue.
At time 1, P2 arrives, but P1 continues executing since it has already started & cannot be preempted.
At time 2, P3 arrives, but P1 continues executing.
At time 4, P4 arrives, but P1 continues executing.
At time 5, P1 completes, & P2 starts executing since it has the highest priority among the remaining processes.
At time 8, P2 completes, & P4 starts executing since it has a higher priority than P3.
At time 12, P4 completes, & P3 starts executing.
At time 14, P3 completes, & the scheduling is finished.
The final execution order is: P1, P2, P4, P3.

Non-preemptive priority scheduling ensures that processes run to completion based on their priority, but it may lead to the starvation of lower priority processes if higher priority processes continuously arrive.

Preemptive Priority Scheduling Algorithm

In preemptive priority scheduling, the process with the highest priority is always executed first, even if it means interrupting a currently running process. If a higher priority process arrives while a lower priority process is executing, the lower priority process is preempted & the higher priority process is given the CPU. Let's explore this algorithm in more detail:

Process Arrival: When a process arrives in the ready queue, it is assigned a priority based on the prioritization criteria.
Process Selection: The process with the highest priority is selected from the ready queue to be executed next. If multiple processes have the same highest priority, they are scheduled using a scheduling algorithm like round-robin or FCFS.
Process Execution: The selected process is allocated the CPU & starts executing. It continues to run until one of the following conditions occurs:
The process completes its execution & terminates.
A higher priority process arrives in the ready queue.
The process voluntarily releases control of the CPU by performing an I/O operation or waiting for an event.
Process Preemption: If a higher priority process arrives while a lower priority process is executing, the lower priority process is preempted. The state of the preempted process is saved, & it is moved back to the ready queue. The higher priority process is then allocated the CPU & starts executing.
Process Completion or Blocking: If the process completes its execution, it is removed from the system. If the process performs an I/O operation or waits for an event, it is moved to the corresponding waiting queue & the CPU is allocated to the next highest priority process.
Repeat: Steps 2-5 are repeated until all processes have been executed or there are no more processes in the ready queue.

The key difference between preemptive & non-preemptive priority scheduling is that in preemptive scheduling, a higher priority process can interrupt a currently running lower priority process, whereas in non-preemptive scheduling, a process runs to completion once it starts executing.

Here's an example to illustrate preemptive priority scheduling:

In this example, the processes arrive at different times & have different priorities. The scheduling would occur as follows:

At time 0, P1 arrives & starts executing since it's the only process in the ready queue.
At time 1, P2 arrives, & P1 is preempted since P2 has a higher priority. P2 starts executing.
At time 2, P3 arrives, but P2 continues executing since it has a higher priority than P3.
At time 4, P2 completes, & P1 resumes execution since it has the next highest priority.
At time 4, P4 arrives, but P1 continues executing since it has the same priority as P4 & arrived earlier.
At time 9, P1 completes, & P4 starts executing since it has a higher priority than P3.
At time 13, P4 completes, & P3 starts executing.
At time 15, P3 completes, & the scheduling is finished.

The final execution order is: P1 (partially), P2, P1 (remaining), P4, P3.

Preemptive priority scheduling ensures that the highest priority processes are executed as soon as possible, but it can lead to the starvation of lower priority processes if higher priority processes constantly arrive & preempt them.

Dry Run Example of Priority Scheduling Algorithm

To better understand how priority scheduling works, let's go through a dry run example step by step. We'll use the following set of processes with their arrival times, burst times, & priorities:

We'll assume that the scheduling is preemptive, meaning that a higher priority process can interrupt a currently running process.

Step 1

At time 0, P1 arrives & starts executing since it's the only process in the ready queue.

Step 2

At time 1, P2 arrives, & P1 is preempted since P2 has a higher priority. P2 starts executing.

Step 3

At time 2, P3 arrives, but P2 continues executing since it has a higher priority than P3.

Step 4

At time 3, P2 completes, & P1 resumes execution since it has the next highest priority.

Step 5

At time 4, P4 arrives, but P1 continues executing since it has the same priority as P4 & was preempted earlier.

Step 6

At time 7, P1 completes, & P4 starts executing since it has a higher priority than P3.

Step 7

At time 8, P4 completes, & P3 starts executing since it's the only remaining process.

Step 8

At time 11, P3 completes, & the scheduling is finished.

The final Gantt chart for the scheduling would look like this:

As we can see from the Gantt chart, the processes are scheduled based on their priorities, with higher priority processes preempting lower priority ones. P1 starts executing first but is preempted by P2. Once P2 completes, P1 resumes execution until P4 arrives. Since P4 has the same priority as P1, P1 continues executing until it completes. Finally, P3 executes until completion.

This dry run example demonstrates how preemptive priority scheduling works in practice, with processes being scheduled based on their priorities & higher priority processes interrupting lower priority ones.

Algorithm of Priority Scheduling Program in C

To implement priority scheduling in a program, we follow a specific sequence of operations. This algorithm is crucial for setting up priority-based task handling in systems programming. Let's explore the basic algorithm used for creating a priority scheduling program in C.

Steps of the Algorithm

Define Process Structure: First, define a structure to hold the necessary process details such as process ID, burst time, priority, waiting time, and turnaround time.
Input Process Details: Gather the number of processes and their respective details (burst time and priority) from the user.
Sorting Processes by Priority: Arrange the processes based on their priority. If implementing non-preemptive scheduling, sort them once based on their arrival time and priority; for preemptive, continuously check and reorder as new processes arrive or as conditions change.
Calculate Waiting Time: For each process, calculate the waiting time. This is the total time the process has been in the system before it gets the CPU.
Calculate Turnaround Time: For each process, determine the turnaround time, which is the total time from when the process arrives to when it completes.
Execute Processes: According to the scheduling (preemptive or non-preemptive), execute the processes. In non-preemptive, each process runs to completion once it starts. In preemptive, monitor if a higher priority process arrives and preempt accordingly.
Output Results: Display the results, showing the process ID along with its waiting time and turnaround time.

This algorithm ensures that each process is handled according to its urgency and importance, reflecting the principles of priority scheduling.

Program Code of Priority Scheduling in C

Here is a simple example of how to implement a priority scheduling program in C. This code snippet will demonstrate non-preemptive priority scheduling, where processes are executed according to their priority without interruption once they start running.

C

#include <stdio.h>

// Define the maximum number of processes
#define MAX 50

typedef struct {
    int process_id, arrival_time, burst_time, priority;
    int waiting_time, turnaround_time;
} Process;

// Function to sort processes by priority
void sortProcessesByPriority(Process proc[], int n) {
    Process temp;
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(proc[j].priority > proc[j + 1].priority) {
                temp = proc[j];
                proc[j] = proc[j + 1];
                proc[j + 1] = temp;
            }
        }
    }
}

// Function to calculate waiting time and turnaround time
void calculateTimes(Process proc[], int n) {
    proc[0].waiting_time = 0; // first process has no waiting time
    proc[0].turnaround_time = proc[0].burst_time;

    for(int i = 1; i < n; i++) {
        proc[i].waiting_time = proc[i - 1].waiting_time + proc[i - 1].burst_time;
        proc[i].turnaround_time = proc[i].waiting_time + proc[i].burst_time;
    }
}

// Function to display the processes along with all details
void displayProcesses(Process proc[], int n) {
    printf("Process ID\tPriority\tBurst Time\tWaiting Time\tTurnaround Time\n");
    for(int i = 0; i < n; i++) {
        printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", proc[i].process_id, proc[i].priority, proc[i].burst_time, proc[i].waiting_time, proc[i].turnaround_time);
    }
}

int main() {
    int n;
    Process proc[MAX];

    // Input number of processes
    printf("Enter total number of processes: ");
    scanf("%d", &n);

    // Input process details
    for(int i = 0; i < n; i++) {
        printf("Enter Process ID, Priority, Burst Time: ");
        scanf("%d %d %d", &proc[i].process_id, &proc[i].priority, &proc[i].burst_time);
        proc[i].arrival_time = 0; // Assuming all processes arrive at time 0
    }

    // Sort processes by priority
    sortProcessesByPriority(proc, n);
    
    // Calculate waiting time and turnaround time
    calculateTimes(proc, n);

    // Display processes along with all calculated times
    displayProcesses(proc, n);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Explanation

Structure Definition: We define a structure Process to hold each process's information.
Sorting Function: Processes are sorted by priority using a simple bubble sort.
Time Calculation: We calculate waiting and turnaround times based on the sorted order.
Display Function: Finally, the details of each process are printed.

Advantages of Priority Scheduling Program in C

Efficient Resource Utilization: Ensures that high-priority tasks are executed first, optimizing system performance.
Flexibility: Allows assigning priorities based on task importance, making it suitable for real-time systems.
Reduced Waiting Time: High-priority processes experience minimal delay, improving responsiveness.
Customizable Priority Levels: Priority levels can be dynamically adjusted based on system requirements.
Preemptive Option: In preemptive mode, it interrupts low-priority tasks to accommodate more critical ones.

Disadvantages of Priority Scheduling Program in C

Starvation of Low-Priority Processes: Low-priority tasks may never execute if high-priority tasks dominate.
Complex Implementation: Managing and assigning priorities requires additional logic and overhead.
Risk of Priority Inversion: Lower-priority processes may block higher-priority ones due to resource contention.
Unfair Scheduling: May lead to unfair distribution of CPU time, especially in non-preemptive systems.
Increased Overhead: Frequent context switching in preemptive scheduling can reduce efficiency.

Frequently Asked Questions

What happens if two processes have the same priority?

When two processes have the same priority, the system will schedule them based on their arrival time or may treat them on a first-come, first-served basis. This approach helps in fair handling of processes with equal priority.

Can priority scheduling lead to starvation?

Yes, priority scheduling can lead to a situation called starvation, where lower priority processes may never execute if high-priority processes keep entering the system. To mitigate this, some systems use aging techniques, where a process's priority is gradually increased the longer it waits.

Is priority scheduling suitable for all types of systems?

Priority scheduling is particularly useful in real-time and embedded systems where certain tasks must be prioritized due to their critical nature. However, for general-purpose computing, a combination of different scheduling methods might be more effective to ensure fairness and efficiency.

Conclusion

In this article, we have learned about priority scheduling, a fundamental concept in operating systems used to manage process execution based on priority. We explored what priority scheduling is, how priorities are decided, and discussed the two main types of priority scheduling algorithms: non-preemptive and preemptive. We also provided a practical dry run example to illustrate how these algorithms function in real scenarios and included a detailed C program to demonstrate non-preemptive priority scheduling.