Operating System

Assignment - 3

Roll No : LCS2022007
Name : Aviral Katiyar
Q1.) Implementation of CPU Scheduling in C: (i) FCFS, (ii) SJF, (iii)
Shortest Remaining Time First and (iv) Priority based.

#include<stdio.h>
#include<stdlib.h>

struct Process {
int id;
int bt;
int priority; // for Priority Scheduling
};

int comparePriority(const void *a, const void *b) {

return ((struct Process*)a)->priority - ((struct
Process*)b)->priority;
}

void fcfs(int processes[], int n, int bt[]) {

int wt[n], tat[n];

wt[0] = 0;

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

wt[i] = bt[i-1] + wt[i-1];

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

tat[i] = bt[i] + wt[i];

printf("FCFS Scheduling:\n");
printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", i+1, bt[i], wt[i], tat[i]);
printf("\n");
}

void sjf(struct Process processes[], int n) {

qsort(processes, n, sizeof(struct Process), comparePriority);
 int wt[n], tat[n];

wt[0] = 0;

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

wt[i] = processes[i-1].bt + wt[i-1];

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

tat[i] = processes[i].bt + wt[i];

printf("SJF Scheduling:\n");
printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", processes[i].id,
processes[i].bt, wt[i], tat[i]);
printf("\n");
}

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

int rt[n];

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

rt[i] = bt[i];

int complete = 0, t = 0, minm = 9999, shortest = 0, finish_time;

while (complete != n) {
for (int j = 0; j < n; j++) {
if ((rt[j] > 0) && (rt[j] < minm) && (t >= processes[j])) {
minm = rt[j];
shortest = j;
}
}

rt[shortest]--;

if (rt[shortest] == 0) {
complete++;
finish_time = t + 1;
 wt[shortest] = finish_time - bt[shortest] -
processes[shortest];

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

t++;
minm = 9999;
}
}

void findTurnaroundTime(int processes[], int n, int bt[], int wt[], int

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

void srtf(int processes[], int n, int bt[]) {

int wt[n], tat[n];

findWaitingTime(processes, n, bt, wt);

findTurnaroundTime(processes, n, bt, wt, tat);

printf("SRTF Scheduling:\n");
printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", i+1, bt[i], wt[i], tat[i]);
printf("\n");
}

void priorityScheduling(struct Process processes[], int n) {

qsort(processes, n, sizeof(struct Process), comparePriority);

int wt[n], tat[n];

wt[0] = 0;

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

 wt[i] = processes[i-1].bt + wt[i-1];

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

tat[i] = processes[i].bt + wt[i];

printf("Priority Scheduling:\n");
printf("Processes Burst time Waiting time Turnaround time
Priority\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\t\t%d\n", processes[i].id,
processes[i].bt, wt[i], tat[i], processes[i].priority);
printf("\n");
}

int main() {
// FCFS
int fcfs_processes[] = { 1, 2, 3};
int fcfs_n = sizeof fcfs_processes / sizeof fcfs_processes[0];
int fcfs_burst_time[] = {6, 8, 7};

fcfs(fcfs_processes, fcfs_n, fcfs_burst_time);

// SJF
struct Process sjf_processes[] = {{1, 6, 2}, {2, 8, 1}, {3, 7, 3}, {4,
3, 2}};
int sjf_n = sizeof sjf_processes / sizeof sjf_processes[0];

sjf(sjf_processes, sjf_n);

// SRTF
int srtf_processes[] = { 1, 2, 3};
int srtf_n = sizeof srtf_processes / sizeof srtf_processes[0];
int srtf_burst_time[] = {6, 8, 7};

srtf(srtf_processes, srtf_n, srtf_burst_time);

// Priority Scheduling
struct Process priority_processes[] = {{1, 6, 2}, {2, 8, 1}, {3, 7,
3}};
 int priority_n = sizeof priority_processes / sizeof
priority_processes[0];

priorityScheduling(priority_processes, priority_n);

return 0;
}

OUTPUT:
Q2.) Implementation of CPU Scheduling in C: (i) Round Robin
(ii)Longest JobFirst (iii) Longest Remaining Time First (LRTF)

#include <stdio.h>
#include <stdlib.h>

// Function to compare burst times for sorting

int compareBT(const void *a, const void *b) {
return *((int*)b) - *((int*)a);
}

void roundRobin(int processes[], int n, int bt[], int quantum) {

int wt[n], tat[n];

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

int t = 0;
int flag;

while (1) {
flag = 0;
for (int i = 0; i < n; i++) {
if (remaining_time[i] > 0) {
flag = 1;

if (remaining_time[i] > quantum) {

t += quantum;
remaining_time[i] -= quantum;
} else {
t += remaining_time[i];
wt[i] = t - bt[i];
remaining_time[i] = 0;
}
}
}
 if (flag == 0)
break;
}

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

tat[i] = bt[i] + wt[i];

printf("Round Robin Scheduling (Quantum = %d):\n", quantum);

printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", i + 1, bt[i], wt[i], tat[i]);
printf("\n");
}

void longestJobFirst(int processes[], int n, int bt[]) {

qsort(processes, n, sizeof(int), compareBT);

int wt[n], tat[n];

wt[0] = 0;

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

wt[i] = bt[i-1] + wt[i-1];

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

tat[i] = bt[i] + wt[i];

printf("Longest Job First Scheduling:\n");

printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", processes[i] + 1, bt[i], wt[i],
tat[i]);
printf("\n");
}
void longestRemainingTimeFirst(int processes[], int n, int bt[]) {
int wt[n], tat[n];

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

int t = 0, longest_index;

while (1) {
int longest_bt = 0;
longest_index = -1;

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

if (remaining_time[i] > longest_bt && t >= processes[i]) {
longest_bt = remaining_time[i];
longest_index = i;
}
}

if (longest_index == -1)
break;

t++;
remaining_time[longest_index]--;
}

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

tat[i] = bt[i] + wt[i];

printf("Longest Remaining Time First Scheduling:\n");

printf("Processes Burst time Waiting time Turnaround time\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\n", processes[i] + 1, bt[i], wt[i],
tat[i]);
 printf("\n");
}

int main() {
int processes[] = {0, 1, 2};
int n = sizeof processes / sizeof processes[0];
int burst_time[] = {6, 8, 7};
int quantum = 2;

// Run Round Robin

roundRobin(processes, n, burst_time, quantum);

// Run Longest Job First

longestJobFirst(processes, n, burst_time);

// Run Longest Remaining Time First

longestRemainingTimeFirst(processes, n, burst_time);

return 0;
}
OUTPUT:

Q3.) Implementation of CPU Scheduling in C: (i) Highest

Response Ratio Next (HRRN) and (ii) Multilevel Queue

#include <stdio.h>
#include <stdlib.h>

struct Process {
int id;
int arrival_time;
int burst_time;
int priority; // For Multilevel Queue
 int queue; // To represent the queue level (e.g., 0 for high
priority, 1 for medium priority, 2 for low priority)
int waiting_time;
int turnaround_time;
float response_ratio; // For HRRN
};

int compareArrivalTime(const void *a, const void *b) {

return ((struct Process*)a)->arrival_time - ((struct
Process*)b)->arrival_time;
}

int compareResponseRatio(const void *a, const void *b) {

return ((struct Process*)b)->response_ratio - ((struct
Process*)a)->response_ratio;
}

void hrrn(struct Process processes[], int n) {

qsort(processes, n, sizeof(struct Process), compareArrivalTime);

int total_waiting_time = 0;
int total_turnaround_time = 0;

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

if (i == 0) {
processes[i].waiting_time = 0;
processes[i].turnaround_time = processes[i].burst_time;
} else {
processes[i].waiting_time = processes[i - 1].turnaround_time;
processes[i].turnaround_time = processes[i].waiting_time +
processes[i].burst_time;
}

processes[i].response_ratio = (float)processes[i].turnaround_time
/ processes[i].burst_time;
total_waiting_time += processes[i].waiting_time;
total_turnaround_time += processes[i].turnaround_time;
}

qsort(processes, n, sizeof(struct Process), compareResponseRatio);

 printf("Highest Response Ratio Next (HRRN) Scheduling:\n");
printf("Processes Arrival time Burst time Waiting time
Turnaround time Response Ratio\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.2f\n", processes[i].id,
processes[i].arrival_time,
processes[i].burst_time, processes[i].waiting_time,
processes[i].turnaround_time, processes[i].response_ratio);
}

printf("Average Waiting Time: %.2f\n", (float)total_waiting_time / n);

printf("Average Turnaround Time: %.2f\n", (float)total_turnaround_time
/ n);
printf("\n");
}

void multilevelQueue(struct Process processes[], int n, int quantum1, int

quantum2) {
qsort(processes, n, sizeof(struct Process), compareArrivalTime);

int total_waiting_time = 0;
int total_turnaround_time = 0;

int time = 0;

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

if (time >= processes[i].arrival_time) {
if (processes[i].queue == 0) { // High priority queue
processes[i].waiting_time = time;
time += processes[i].burst_time;
processes[i].turnaround_time = time;
} else { // Medium and low priority queues with round-robin
scheduling
processes[i].waiting_time = time;
if (processes[i].queue == 1) {
time += quantum1;
processes[i].burst_time -= quantum1;
} else {
 time += quantum2;
processes[i].burst_time -= quantum2;
}

if (processes[i].burst_time > 0) {
processes[i].queue++;
} else {
processes[i].turnaround_time = time;
}
}

total_waiting_time += processes[i].waiting_time;
total_turnaround_time += processes[i].turnaround_time;
} else {
time = processes[i].arrival_time;
i--;
}
}

printf("Multilevel Queue Scheduling:\n");

printf("Processes Arrival time Burst time Waiting time
Turnaround time Priority Queue\n");

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

printf(" %d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", processes[i].id,
processes[i].arrival_time,
processes[i].burst_time, processes[i].waiting_time,
processes[i].turnaround_time, processes[i].queue);
}

printf("Average Waiting Time: %.2f\n", (float)total_waiting_time / n);

printf("Average Turnaround Time: %.2f\n", (float)total_turnaround_time
/ n);
printf("\n");
}

int main() {
struct Process processes[] = {{1, 0, 6, 0, 0}, {2, 2, 8, 1, 0}, {3, 4,
7, 2, 0}, {4, 6, 3, 1, 0}};
int n = sizeof processes / sizeof processes[0];
 int quantum1 = 2;
int quantum2 = 4;

hrrn(processes, n);
multilevelQueue(processes, n, quantum1, quantum2);

return 0;
}

OUTPUT: