Implementing Preemptive Priority Scheduling with Quantum or Time Slice in C

When designing a system to manage processes efficiently, preemptive priority scheduling with a time quantum is a critical technique. This method involves allocating the CPU to the highest-priority process that is ready to run, and if a process exceeds its assigned time quantum, it is preempted and placed back in the queue for continued execution. This article explores the implementation of such a scheduling algorithm using the C programming language. We will cover key concepts, provide an example C program, and discuss the implementation details.

Key Concepts

Implementing preemptive priority scheduling with a time quantum requires understanding several key concepts:

Process Structure

A process structure is used to store attributes such as the process ID, burst time (total execution time), remaining time, and priority. Here is how you can define a process structure in C:

#include stdio.h#include stdlib.h#define MAX_PROCESSES 100typedef struct {    int id;            /* Process ID */    int burst_time;    /* Total burst time */    int remaining_time; /* Remaining time */    int priority;      /* Priority of the process */} Process;

This structure will help in organizing and managing the processes effectively.

Priority Queue

A priority queue is essential for managing processes based on their priority. This can be implemented using various data structures like heaps, but for simplicity, a sorted array can be used as a priority queue.

Time Quantum

A time quantum is a fixed time slice within which a process is allowed to execute. If a process exceeds this time slice, it is preempted and moved to the end of the queue for further execution.

Example C Program Implementation

Here is a simple C program that simulates preemptive priority scheduling with a time quantum:

#include stdio.h#include stdlib.h#define MAX_PROCESSES 100typedef struct {    int id;            /* Process ID */    int burst_time;    /* Total burst time */    int remaining_time; /* Remaining time */    int priority;      /* Priority of the process */} Process;void sortProcesses(Process processes[], int n) {    // Simple sorting based on priority (higher number  higher priority)    for (int i  0; i  n - 1; i  ) {        for (int j  0; j  n - i - 1; j  ) {            if (processes[j].priority  processes[j   1].priority) {                Process temp  processes[j];                processes[j]  processes[j   1];                processes[j   1]  temp;            }        }    }}void preemptivePriorityScheduling(Process processes[], int n, int time_quantum) {    int time  0;    int completed  0;    int total_waiting_time  0;    int total_turnaround_time  0;    while (completed  n) {        sortProcesses(processes, n);        int found  0;        for (int i  0; i  n; i  ) {            if (processes[i].remaining_time  0) {                found  1; // Found a process to run                if (processes[i].remaining_time  time_quantum) {                    // Process runs for the time quantum                    time   time_quantum;                    processes[i].remaining_time - time_quantum;                } else {                    // Process finishes                    time   processes[i].remaining_time;                    processes[i].remaining_time  0;                    completed  ;                    int turnaround_time  time;                    int waiting_time  turnaround_time - processes[i].burst_time;                    total_turnaround_time   turnaround_time;                    total_waiting_time   waiting_time;                    printf("Process %d: Turnaround Time  %d, Waiting Time  %d
", processes[i].id, turnaround_time, waiting_time);                }                break; // Re-sort processes after a process finishes or runs            }        }        // If no process was found, increment time        if (!found) {            time  ;        }    }    printf("Total Waiting Time  %d
", total_waiting_time);    printf("Total Turnaround Time  %d
", total_turnaround_time);}int main() {    Process processes[MAX_PROCESSES];    int n, time_quantum;    printf("Enter the number of processes: ");    scanf("%d", n);    for (int i  0; i  n; i  ) {        processes[i].id  i   1; // Assign process ID        printf("Enter burst time for process %d: ", processes[i].id);        scanf("%d", processes[i].burst_time);        processes[i].remaining_time  processes[i].burst_time; // Initialize remaining time        printf("Enter priority for process %d: ", processes[i].id);        scanf("%d", processes[i].priority);    }    printf("Enter time quantum: ");    scanf("%d", time_quantum);    preemptivePriorityScheduling(processes, n, time_quantum);    return 0;}

This program implements a simple preemptive priority scheduling algorithm with a time quantum. Here's a quick explanation of the code:

Process Structure - A structure is defined to hold the process ID, burst time, remaining time, and priority.

Sorting by Priority - A simple bubble sort function is used to sort processes based on their priority before each round of scheduling.

Scheduling Function - The preemptivePriorityScheduling function simulates the scheduling. It checks each process in order of priority and allows it to run for a time quantum or until it finishes.

Input Handling - The main function collects process details from the user and initializes the scheduling.

Running the Program

1. Compile the program using a C compiler, e.g., gcc:

$ gcc -o scheduling scheduling.c

2. Run the program and input the number of processes, their burst times, priorities, and the time quantum:

$ ./schedulingEnter the number of processes: 5Enter burst time for process 1: 5Enter priority for process 1: 1Enter burst time for process 2: 2Enter priority for process 2: 2Enter burst time for process 3: 3Enter priority for process 3: 3Enter burst time for process 4: 1Enter priority for process 4: 4Enter burst time for process 5: 4Enter priority for process 5: 5Enter time quantum: 2

The program will then output the results of the scheduling process.

Considerations

1. This implementation uses a simple sorting algorithm for clarity but can be optimized for better performance.

2. The program assumes higher priority values indicate higher priority.

3. Be mindful of edge cases such as all processes having the same priority or zero burst times.

This implementation provides a basic understanding of how preemptive priority scheduling works in a system.