CPU Scheduling is a crucial process in operating systems that determines which process runs on the CPU at any given time.
The main goal is to maximize CPU utilization and throughput.
Key Terms in CPU Scheduling
- Arrival Time: When a process enters the ready queue
- Burst Time: Time required for process execution
- Completion Time: When a process finishes execution
- Turnaround Time: Completion Time – Arrival Time
- Waiting Time: Turnaround Time – Burst Time
Table of Content
Table of Contents
Scheduling Algorithms
First Come First Serve (FCFS)
#include<stdio.h>
void main()
{
int bt[20], wt[20], i, n;
float wtavg;
printf("\nEnter the number of processes -- ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("\nEnter Burst Time for Process %d -- ", i);
scanf("%d", &bt[i]);
}
wt[0] = wtavg = 0; // First process has zero waiting time
// Calculating waiting time for each process
for(i = 1; i < n; i++)
{
wt[i] = wt[i-1] + bt[i-1]; // Waiting time = Previous waiting time + Previous burst time
wtavg += wt[i]; // Accumulate total waiting time
}
// Display process number, burst time, and waiting time
printf("\t PROCESS \tBURST TIME \t WAITING TIME\n");
for(i = 0; i < n; i++)
{
printf("\n\t P%d \t\t %d \t\t %d", i, bt[i], wt[i]);
}
printf("\nAverage Waiting Time -- %f", wtavg/n); // Calculating average waiting time
}
Explanation:
Array Initialization: Two arrays
bt[]andwt[]are used:bt[]stores the burst times of the processes.wt[]stores the waiting times for each process.
User Input: The program prompts the user to enter the number of processes (
n). For each process, the user inputs the burst time, which is stored in thebt[]array.Initial Waiting Time:
- The waiting time for the first process (
wt[0]) is initialized to0because the first process starts immediately without waiting.
- The waiting time for the first process (
Waiting Time Calculation:
- For every subsequent process, the waiting time is calculated as the sum of the waiting time of the previous process and its burst time:
wt[i] = wt[i-1] + bt[i-1]
- This ensures that each process waits for the burst time of all previous processes before it starts execution.
- For every subsequent process, the waiting time is calculated as the sum of the waiting time of the previous process and its burst time:
Average Waiting Time:
- The total waiting time is accumulated into
wtavg, and at the end of the loop, the program calculates the average waiting time by dividing the total waiting time by the number of processes (n).
- The total waiting time is accumulated into
Output:
- The program prints a table displaying each process’s burst time and waiting time.
- It also prints the average waiting time.
Shortest Job First (SJF)
Shortest Job First (SJF) is a non-preemptive scheduling algorithm where the process with the shortest burst time is executed first. This minimizes the average waiting time for all processes but may cause starvation for longer processes if many short processes keep arriving.
#include <stdio.h>
int main()
{
// Matrix for storing Process Id, Burst Time and Waiting Time.
int A[4][3] = {
{1, 6, 0}, // Process 1 with burst time 6
{2, 8, 0}, // Process 2 with burst time 8
{3, 7, 0}, // Process 3 with burst time 7
{4, 3, 0} // Process 4 with burst time 3
};
int i, j, n = 4, index, temp;
// Sorting process according to their Burst Time.
for (i = 0; i < n; i++) {
index = i;
for (j = i + 1; j < n; j++)
if (A[j][1] < A[index][1])
index = j;
// Swapping burst times
temp = A[i][1];
A[i][1] = A[index][1];
A[index][1] = temp;
// Swapping process IDs
temp = A[i][0];
A[i][0] = A[index][0];
A[index][0] = temp;
}
A[0][2] = 0; // First process has zero waiting time
// Calculation of Waiting Times
for (i = 1; i < n; i++) {
A[i][2] = 0;
for (j = 0; j < i; j++)
A[i][2] += A[j][1];
}
// Printing the results
printf("P BT WT\n");
for (i = 0; i < n; i++) {
printf("P%d %d %d\n", A[i][0], A[i][1], A[i][2]);
}
return 0;
}
Explanation
Matrix Initialization: The program uses a 2D array
A[4][3], where each row represents a process. The columns store:- Process ID (column 0)
- Burst time (column 1)
- Waiting time (column 2)
Static Burst Times: Four processes are predefined with burst times
{6, 8, 7, 3}. These burst times represent how long each process will take to execute.Sorting by Burst Time: The program sorts the processes based on their burst times using a simple selection sort. This ensures that the process with the shortest burst time is executed first.
Waiting Time Calculation: After sorting, the waiting time for each process is computed. The waiting time of a process is the sum of the burst times of all previous processes. The first process has zero waiting time since it executes immediately.
Output: The program prints each process ID, its burst time, and the calculated waiting time in a tabular format. This shows the order of execution and how long each process waits before starting.
Round Robin (RR)
In Round Robin Scheduling, each process is given a specific amount of time, called a quantum, to run. When a process starts, it runs for that set time. If it doesn’t finish during its quantum, it gets paused, and the next process begins.
For example, let’s say we have three processes: A, B, and C. First, A will run for its quantum. Whether it’s finished or not, once A’s time is up, process B will start running for its quantum. Then process C will run.
After all the processes have had their turn, process A will run again. This cycle keeps repeating until all processes are complete.
