Assignment 3: CPU Scheduling Algorithms in C

Date: 07/08/24

1. First-Come-First-Serve (FCFS) Scheduling Algorithm

FCFS is the simplest CPU scheduling algorithm, where the process that arrives first is
executed first. It operates on a FIFO basis.

Program

#include <stdio.h>
int main() {
int p[10], at[10], bt[10], ct[10], tat[10], wt[10];
int i, j, temp = 0, n;
float awt = 0, atat = 0;

// Input number of processes

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

// Input process IDs

printf("Enter the process IDs: ");
for (i = 0; i < n; i++) {
scanf("%d", &p[i]);
}

// Input arrival times

printf("Enter the arrival times: ");
for (i = 0; i < n; i++) {
scanf("%d", &at[i]); }
// Input burst times
printf("Enter the burst times: ");
for (i = 0; i < n; i++) {
scanf("%d", &bt[i]);
}

// Sort based on arrival time (Bubble Sort)

for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (at[j] > at[j + 1]) {
// Swap process ID
temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
// Swap arrival time
temp = at[j];
at[j] = at[j + 1];
at[j + 1] = temp;
// Swap burst time
temp = bt[j];
bt[j] = bt[j + 1];
bt[j + 1] = temp;
}
}
}

// Calculate completion times

ct[0] = at[0] + bt[0]; // First process
for (i = 1; i < n; i++) {
if (ct[i - 1] < at[i]) {
ct[i] = at[i] + bt[i]; // CPU idle
} else {
ct[i] = ct[i - 1] + bt[i];
 }
}

// Calculate turnaround times and waiting times

for (i = 0; i < n; i++) {
tat[i] = ct[i] - at[i]; // Turnaround Time = Completion Time - Arrival Time
wt[i] = tat[i] - bt[i]; // Waiting Time = Turnaround Time - Burst Time
atat += tat[i];
awt += wt[i];
}

// Calculate averages
atat = atat / n;
awt = awt / n;

printf("\n Process Arrival Time Burst Time Completion TAT WT ");

for (i = 0; i < n; i++) {
printf("\n| P%d %2d %2d %2d %2d %2d ",
p[i], at[i], bt[i], ct[i], tat[i], wt[i]);
}

// Average times
printf("\n\nAverage Turnaround Time: %.2f", atat);
printf("\nAverage Waiting Time: %.2f\n", awt);

return 0;
}

Output
 tanweer@Tanweer:~/CpuScheduling$ gcc FCFS.c
tanweer@Tanweer:~/CpuScheduling$ ./a.out
Enter the number of processes: 4
Enter the process IDs: 1 2 3 4
Enter the arrival times: 0 1 2 3
Enter the burst times: 7 6 4 8

Process Arrival Time Burst Time Completion TAT WT

P1 0 7 7 7 0
P2 1 6 13 12 6
P3 2 4 17 15 11
P4 3 8 25 22 14

Average Turnaround Time: 14.00

Average Waiting Time: 7.75
Date: 07/08/24

2. Shortest Job First (SJF) Scheduling Algorithm(non-preemptive)

Shortest Job First (SJF) is a CPU Scheduling algorithm in which CPU allocation is based
on burst time. The job with less burst time will get scheduled first.

#include<stdio.h>
#include<stdlib.h>
void swap(int *x, int *y) {
int temp=*x;
*x=*y;
*y=temp;
}
void sortat(int p[], int at[], int bt[], int n) {
int i, j;
 for(i=0;i<n;i++) {
for(j=i+1;j<n;j++) { /* sort the process having less arrival*/
if(at[i]>at[j]) {
swap(&p[i], &p[j]);
swap(&at[i], &at[j]);
swap(&bt[i], &bt[j]);
}
/* if two processes have the same arrival time than sort them having less burst
time */
else if(at[i]==at[j]) {
if(bt[i]>bt[j])
swap(&p[i], &p[j]);
swap(&at[i], &at[j]);
swap(&bt[i], &bt[j]);
}
}
}
}
/* calculate turnaround time and waiting time */
void tatwt( int ct[], int at[], int bt[], int tat[], int wt[], int n) {
int i;
for(i=0;i<n;i++) {
tat[i]=ct[i]-at[i];
wt[i]=tat[i]-bt[I];
}
}
int main() {
int *p, *at, *bt, *tat, *wt, *ct, pos, i, j, min=1000, n;
float awt=0, atat=0;
printf("\nEnter the number of process: ");
scanf("%d", &n);
p=(int*)malloc(n*sizeof(int));
at=(int*)malloc(n*sizeof(int));
bt=(int*)malloc(n*sizeof(int));
ct=(int*)malloc(n*sizeof(int));
wt=(int*)malloc(n*sizeof(int));
tat=(int*)malloc(n*sizeof(int));
printf("enter the process");
for(i=0;i<n;i++) {
scanf("%d",&p[i]);
}
printf("Enter the arrival time: ");
for(i=0;i<n;i++) {
scanf("%d",&at[i]);
}
printf("Enter the burst time: ");
for(i=0;i<n;i++) {
scanf("%d",&bt[i]);
}
sortat(p, at, bt, n);
ct[0]=at[0] + bt[0];
for(i=1; i<n; i++) {
for(j=i; j<n; j++) {
if(at[j]<=ct[i-1]) {
if(bt[j]<min) {
min=bt[j];
pos=j;
}
}
}
/* when you get less burst time process, swap p, at, bt at position 2, and when getting
2nd less burst time swap at position 3rd and so on. */
 swap(&p[i], &p[pos]);
swap(&at[i], &at[pos]);
swap(&bt[i], &bt[pos]);
min=1000;
ct[i]=ct[i-1]+bt[i];
}
tatwt(ct, at, bt, tat, wt, n);
printf("\n Process Arrival Time Burst Time Completion TAT WT ");
for(i=0;i<n;i++) {
printf("\n%d\t %d\t %d\t %d\t %d\t %d",p[i], at[i], bt[i], ct[i], tat[i], wt[i]);
}
for(i=0;i<n;i++) {
atat+=tat[i];
awt+=wt[i];
}
// average turnaround time and average waiting time
atat=atat/n;
awt=awt/n;
printf("\n avg tat=%.2f and avg wt=%.2f",atat, awt);
return 0;
}
Output:
tanweer@Tanweer:~/CpuScheduling$ gcc SJF.c
tanweer@Tanweer:~/CpuScheduling$ ./a.out
Enter the number of process: 4
Enter the process: 1 2 3 4
Enter the arrival time: 0 1 3 0
Enter the burst time: 5 3 4 3

Process Arrival Time Burst Time Completion TAT WT

 4 0 3 3 3 0
2 1 3 6 5 2
3 3 4 10 7 3
1 0 5 15 15 10
avg tat=7.50 and avg wt=3.75

3. Shortest Job First (SJF) Scheduling Algorithm(Preemptive)

#include <stdio.h>
#include <limits.h>

void findWaitingTime(int n, int at[], int bt[], int wt[]) {

int remaining_bt[n], completed = 0, time = 0, min_bt = INT_MAX;
int shortest = -1, finish_time;
int check = 0;

for (int i = 0; i < n; i++)

remaining_bt[i] = bt[i];

while (completed != n) {
// Find the process with the smallest remaining burst time
for (int i = 0; i < n; i++) {
if (at[i] <= time && remaining_bt[i] > 0 && remaining_bt[i] < min_bt) {
min_bt = remaining_bt[i];
shortest = i;
check = 1;
}
}
if (check == 0) {
time++;
continue;
 }

// Reduce the remaining time for the shortest process

remaining_bt[shortest]--;
min_bt = remaining_bt[shortest];

// If the process is completed

if (remaining_bt[shortest] == 0) {
min_bt = INT_MAX;
completed++;
finish_time = time + 1;

// Calculate waiting time

wt[shortest] = finish_time - bt[shortest] - at[shortest];

if (wt[shortest] < 0)
wt[shortest] = 0;
}
time++;
}
}

void findTurnAroundTime(int n, int bt[], int wt[], int tat[]) {

for (int i = 0; i < n; i++)
tat[i] = bt[i] + wt[i];
}

void calculateAverageTimes(int n, int at[], int bt[]) {

int wt[n], tat[n];
float total_wt = 0, total_tat = 0;
 findWaitingTime(n, at, bt, wt);
findTurnAroundTime(n, bt, wt, tat);

printf("\nProcess\tAT\tBT\tWT\tTAT\n");
for (int i = 0; i < n; i++) {
total_wt += wt[i];
total_tat += tat[i];
printf("P%d\t%d\t%d\t%d\t%d\n", i + 1, at[i], bt[i], wt[i], tat[i]);
}

printf("\nAverage Waiting Time: %.2f", total_wt / n);

printf("\nAverage Turnaround Time: %.2f\n", total_tat / n);
}

int main() {
int n;
printf("Enter the number of processes: ");
scanf("%d", &n);

int at[n], bt[n];

printf("Enter the arrival times:\n");
for (int i = 0; i < n; i++) {
printf("AT for P%d: ", i + 1);
scanf("%d", &at[i]);
}

printf("Enter the burst times:\n");

for (int i = 0; i < n; i++) {
printf("BT for P%d: ", i + 1);
scanf("%d", &bt[i]);
}
 calculateAverageTimes(n, at, bt);
return 0;
}
OUTPUT
tanweer@Tanweer:~/CpuScheduling$ vim SJF2.c
tanweer@Tanweer:~/CpuScheduling$ gcc SJF2.c
tanweer@Tanweer:~/CpuScheduling$ ./a.out
Enter the number of processes: 4
Enter the arrival times:
AT for P1: 0
AT for P2: 1
AT for P3: 2
AT for P4: 3
Enter the burst times:
BT for P1: 8
BT for P2: 4
BT for P3: 9
BT for P4: 5

Process AT BT WT TAT
P1 0 8 9 17
P2 1 4 0 4
P3 2 9 15 24
P4 3 5 2 7

Average Waiting Time: 6.50

Average Turnaround Time: 13.00
4. Round Robin (RR) Scheduling Algorithm

A round-robin scheduling algorithm is used to schedule the process fairly for each job
in a time slot or quantum and interrupt the job if it is not completed by then the job
comes after the other job which arrives in the quantum time making these scheduling
fairly.

#include <stdio.h>
#include <stdbool.h>

void queueUpdation(int queue[], int timer, int arrival[], int n, int maxProccessIndex) {
int zeroIndex = -1;
for (int i = 0; i < n; i++) {
if (queue[i] == 0) {
zeroIndex = i;
break;
}
}
if (zeroIndex != -1) {
queue[zeroIndex] = maxProccessIndex + 1;
}
}

void queueMaintainence(int queue[], int n) {

for (int i = 0; (i < n - 1) && (queue[i + 1] != 0); i++) {
int temp = queue[i];
queue[i] = queue[i + 1];
queue[i + 1] = temp;
}
}

void checkNewArrival(int timer, int arrival[], int n, int *maxProccessIndex, int queue[]) {
if (timer <= arrival[n - 1]) {
bool newArrival = false;
for (int j = (*maxProccessIndex + 1); j < n; j++) {
 if (arrival[j] <= timer) {
if (*maxProccessIndex < j) {
*maxProccessIndex = j;
newArrival = true;
}
}
}
if (newArrival) {
queueUpdation(queue, timer, arrival, n, *maxProccessIndex);
}
}
}

int main() {
int n, tq, timer = 0, maxProccessIndex = 0;
float avgWait = 0, avgTT = 0;

printf("Enter the time quanta: ");

scanf("%d", &tq);

printf("Enter the number of processes: ");

scanf("%d", &n);

int arrival[n], burst[n], wait[n], turn[n], queue[n], temp_burst[n];

bool complete[n];

printf("Enter the arrival time of the processes: ");

for (int i = 0; i < n; i++) {
scanf("%d", &arrival[i]);
}
printf("Enter the burst time of the processes: ");
for (int i = 0; i < n; i++) {
scanf("%d", &burst[i]);
temp_burst[i] = burst[i];
}

for (int i = 0; i < n; i++) {

complete[i] = false;
queue[i] = 0;
}

while (timer < arrival[0]) {

timer++;
}
queue[0] = 1;

while (1) {
bool flag = true;
for (int i = 0; i < n; i++) {
if (temp_burst[i] != 0) {
flag = false;
break;
}
}
if (flag)
break;

for (int i = 0; (i < n) && (queue[i] != 0); i++) {

int ctr = 0;
while ((ctr < tq) && (temp_burst[queue[0] - 1] > 0)) {
temp_burst[queue[0] - 1] -= 1;
 timer += 1;
ctr++;

checkNewArrival(timer, arrival, n, &maxProccessIndex, queue);

}
if ((temp_burst[queue[0] - 1] == 0) && (complete[queue[0] - 1] == false)) {
turn[queue[0] - 1] = timer;
complete[queue[0] - 1] = true;
}

bool idle = true;

if (queue[n - 1] == 0) {
for (int k = 0; k < n && queue[k] != 0; k++) {
if (complete[queue[k] - 1] == false) {
idle = false;
}
}
} else {
idle = false;
}

if (idle) {
timer++;
checkNewArrival(timer, arrival, n, &maxProccessIndex, queue);
}
queueMaintainence(queue, n);
}
}

for (int i = 0; i < n; i++) {

turn[i] = turn[i] - arrival[i];
 wait[i] = turn[i] - burst[i];
}

printf("\nProgram No.\tArrival Time\tBurst Time\tWait 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", i + 1, arrival[i], burst[i], wait[i], turn[i]);
}

for (int i = 0; i < n; i++) {

avgWait += wait[i];
avgTT += turn[i];
}
printf("\nAverage wait time: %.2f", (avgWait / n));
printf("\nAverage Turn Around Time: %.2f\n", (avgTT / n));

return 0;
}

OUTPUT
tanweer@Tanweer:~/CpuScheduling$ gcc RR.c
tanweer@Tanweer:~/CpuScheduling$ ./a.out
Enter the time quanta: 3
Enter the number of processes: 4
Enter the arrival time of the processes: 0 1 2 3
Enter the burst time of the processes: 6 5 3 1

Program No. Arrival Time Burst Time Wait Time Turn Around Time
1 0 6 7 13
2 1 5 9 14
3 2 3 4 7
4 3 1 6 7
 Average wait time: 6.50
Average Turn Around Time: 10.25

5. Priority Scheduling Algorithm

Priority scheduling is a non-preemptive algorithm and one of the most common

scheduling algorithms in batch systems. Each process is assigned first arrival time (less
arrival time process first) if two processes have same arrival time, then compare to
priorities (highest process first). Also, if two processes have same priority then compare
to process number (less process number first). This process is repeated while all
process get executed.
#include <stdio.h>
#include <stdlib.h>

// Structure to hold process information

struct process {
int at, bt, pr, pno;
};

struct process proc[50];

int totalprocess; // Total number of processes

// Comparator function for sorting based on arrival time and priority

int comp(const void *a, const void *b) {
struct process *procA = (struct process *)a;
struct process *procB = (struct process *)b;

if (procA->at == procB->at) {
return procA->pr - procB->pr; // Sort by priority if arrival times are the same
} else {
return procA->at - procB->at; // Otherwise, sort by arrival time
}
}

// Function to calculate waiting time

void get_wt_time(int wt[]) {
int service[50];

// Initializing the service and waiting time arrays

service[0] = proc[0].at;
wt[0] = 0;

for (int i = 1; i < totalprocess; i++) {

service[i] = proc[i - 1].bt + service[i - 1];
wt[i] = service[i] - proc[i].at;

// If waiting time is negative, set it to 0

if (wt[i] < 0) {
wt[i] = 0;
}
}
}

// Function to calculate turnaround time

void get_tat_time(int tat[], int wt[]) {
for (int i = 0; i < totalprocess; i++) {
tat[i] = proc[i].bt + wt[i];
}
}

// Function to calculate Gantt chart and print details

void findgc() {
int wt[50], tat[50];
 double wavg = 0, tavg = 0;

// Calculate waiting and turnaround times

get_wt_time(wt);
get_tat_time(tat, wt);

int stime[50], ctime[50];

stime[0] = proc[0].at;
ctime[0] = stime[0] + tat[0];

// Calculate start time and completion time

for (int i = 1; i < totalprocess; i++) {
stime[i] = ctime[i - 1];
ctime[i] = stime[i] + tat[i] - wt[i];
}

printf("Process_no\tStart_time\tComplete_time\tTurn_Around_Time\tWaiting_Time\n");

// Display process details

for (int i = 0; i < totalprocess; i++) {
wavg += wt[i];
tavg += tat[i];
printf("%d\t\t%d\t\t%d\t\t%d\t\t\t%d\n",
proc[i].pno, stime[i], ctime[i], tat[i], wt[i]);
}

// Display average waiting time and turnaround time

printf("Average waiting time is : %.2f\n", wavg / (float)totalprocess);
printf("Average turnaround time : %.2f\n", tavg / (float)totalprocess);
}
int main() {
// Input number of processes
printf("Enter the total number of processes: ");
scanf("%d", &totalprocess);

// Input process numbers

printf("Enter the process numbers: ");
for (int i = 0; i < totalprocess; i++) {
scanf("%d", &proc[i].pno);
}

// Input arrival times

printf("Enter the arrival times of the processes: ");
for (int i = 0; i < totalprocess; i++) {
scanf("%d", &proc[i].at);
}

// Input burst times

printf("Enter the burst times of the processes: ");
for (int i = 0; i < totalprocess; i++) {
scanf("%d", &proc[i].bt);
}

// Input priorities
printf("Enter the priorities of the processes: ");
for (int i = 0; i < totalprocess; i++) {
scanf("%d", &proc[i].pr);
}

// Sort processes based on arrival time and priority

 qsort(proc, totalprocess, sizeof(struct process), comp);

// Find Gantt chart and display details

findgc();

return 0;
}

OUTPUT

tanweer@Tanweer:~/CpuScheduling$ gcc PRS.c

tanweer@Tanweer:~/CpuScheduling$ gcc PRS.c
tanweer@Tanweer:~/CpuScheduling$ ./a.out
Enter the total number of processes: 5
Enter the process numbers: 1 2 3 4 5
Enter the arrival times of the processes: 1 2 3 4 5
Enter the burst times of the processes: 3 5 1 7 4
Enter the priorities of the processes: 3 4 1 7 8
Process_no Start_time Complete_time Turn_Around_Time Waiting_Time
1 1 4 3 0
2 4 9 7 2
3 9 10 7 6
4 10 17 13 6
5 17 21 16 12
Average waiting time is : 5.20
Average turnaround time : 9.20