Practical: 09
Title : Implementation of CPU scheduling using the FCFS Algorithm, SJF Algorithm, and Round Robin Algorithm, Priority Algorithm
—----------------------------------------------------------------------------------------------------------------------------
Implementing CPU scheduling algorithms like FCFS (First-Come, First-Served), SJF (Shortest Job First), Round Robin, and Priority Scheduling can be a great way to understand how operating systems manage process execution.
1. First-Come, First-Served (FCFS) Algorithm
The FCFS algorithm schedules processes in the order they arrive in the ready queue. It's straightforward but not optimal for minimizing waiting time or turnaround time.
Function FCFS_Scheduling(processes):
# processes is a list of tuples (process_id, arrival_time, burst_time)
Initialize waiting_time array to 0 for all processes
Initialize turnaround_time array to 0 for all processes
Set total_waiting_time to 0
Set total_turnaround_time to 0
Sort processes by arrival_time
for i from 1 to number of processes:
if i is 1:
# First process, waiting time is zero
waiting_time[i] = 0
else:
# Calculate waiting time as the sum of burst times of all previous processes
waiting_time[i] = waiting_time[i-1] + burst_time[i-1]
# Calculate turnaround time
turnaround_time[i] = waiting_time[i] + burst_time[i]
# Update total waiting time and turnaround time
total_waiting_time += waiting_time[i]
total_turnaround_time += turnaround_time[i]
# Calculate average waiting time and turnaround time
avg_waiting_time = total_waiting_time / number of processes
avg_turnaround_time = total_turnaround_time / number of processes
return avg_waiting_time, avg_turnaround_time
Code:
#include <stdio.h>
// Function to calculate the waiting and turnaround time
void calculateWaitingTimeAndTurnaroundTime(int processes[], int n, int burstTime[], int waitingTime[], int turnaroundTime[]) {
waitingTime[0] = 0; // Waiting time for the first process is 0
// Calculate waiting time for each process
for (int i = 1; i < n; i++) {
waitingTime[i] = burstTime[i - 1] + waitingTime[i - 1];
}
// Calculate turnaround time for each process
for (int i = 0; i < n; i++) {
turnaroundTime[i] = burstTime[i] + waitingTime[i];
}
}
// Function to calculate average waiting time and turnaround time
void calculateAverageTime(int processes[], int n, int burstTime[]) {
int waitingTime[n], turnaroundTime[n];
int totalWaitingTime = 0, totalTurnaroundTime = 0;
// Calculate waiting and turnaround time for each process
calculateWaitingTimeAndTurnaroundTime(processes, n, burstTime, waitingTime, turnaroundTime);
printf("Processes Burst Time Waiting Time Turnaround Time\n");
// Display individual process statistics and calculate total waiting and turnaround time
for (int i = 0; i < n; i++) {
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
printf("%d %d %d %d\n", processes[i], burstTime[i], waitingTime[i], turnaroundTime[i]);
}
// Calculate average waiting and turnaround time
float avgWaitingTime = (float)totalWaitingTime / (float)n;
float avgTurnaroundTime = (float)totalTurnaroundTime / (float)n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
}
int main() {
int processes[] = {1, 2, 3, 4};
int n = sizeof(processes) / sizeof(processes[0]);
int burstTime[] = {4, 3, 7, 2};
// Call the function to calculate and display average time
calculateAverageTime(processes, n, burstTime);
return 0;
}
2. Shortest Job First (SJF) Algorithm
The SJF algorithm selects the process with the shortest burst time from the ready queue. It can be either preemptive or non-preemptive.
Function SJF_Scheduling(processes):
# processes is a list of tuples (process_id, burst_time)
Initialize waiting_time array to 0 for all processes
Initialize turnaround_time array to 0 for all processes
Set total_waiting_time to 0
Set total_turnaround_time to 0
Sort processes by burst_time
for i from 1 to number of processes:
if i is 1:
# First process, waiting time is zero
waiting_time[i] = 0
else:
# Calculate waiting time as the sum of burst times of all previous processes
waiting_time[i] = waiting_time[i-1] + burst_time[i-1]
# Calculate turnaround time
turnaround_time[i] = waiting_time[i] + burst_time[i]
# Update total waiting time and turnaround time
total_waiting_time += waiting_time[i]
total_turnaround_time += turnaround_time[i]
# Calculate average waiting time and turnaround time
avg_waiting_time = total_waiting_time / number of processes
avg_turnaround_time = total_turnaround_time / number of processes
return avg_waiting_time, avg_turnaround_time
Code:
#include <stdio.h>
// Function to calculate waiting and turnaround time
void calculateWaitingTimeAndTurnaroundTime(int processes[], int n, int burstTime[], int waitingTime[], int turnaroundTime[]) {
waitingTime[0] = 0; // Waiting time for the first process is 0
// Calculate waiting time for each process
for (int i = 1; i < n; i++) {
waitingTime[i] = burstTime[i - 1] + waitingTime[i - 1];
}
// Calculate turnaround time for each process
for (int i = 0; i < n; i++) {
turnaroundTime[i] = burstTime[i] + waitingTime[i];
}
}
// Function to calculate average waiting time and turnaround time
void calculateAverageTime(int processes[], int n, int burstTime[]) {
int waitingTime[n], turnaroundTime[n];
int totalWaitingTime = 0, totalTurnaroundTime = 0;
// Calculate waiting and turnaround time for each process
calculateWaitingTimeAndTurnaroundTime(processes, n, burstTime, waitingTime, turnaroundTime);
printf("Processes Burst Time Waiting Time Turnaround Time\n");
// Display individual process statistics and calculate total waiting and turnaround time
for (int i = 0; i < n; i++) {
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
printf("%d %d %d %d\n", processes[i], burstTime[i], waitingTime[i], turnaroundTime[i]);
}
// Calculate average waiting and turnaround time
float avgWaitingTime = (float)totalWaitingTime / (float)n;
float avgTurnaroundTime = (float)totalTurnaroundTime / (float)n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
}
// Function to sort processes by burst time using bubble sort
void sortByBurstTime(int processes[], int n, int burstTime[]) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (burstTime[j] > burstTime[j + 1]) {
// Swap burst time
int temp = burstTime[j];
burstTime[j] = burstTime[j + 1];
burstTime[j + 1] = temp;
// Swap processes
int tempProcess = processes[j];
processes[j] = processes[j + 1];
processes[j + 1] = tempProcess;
}
}
}
}
int main() {
int processes[] = {1, 2, 3, 4};
int n = sizeof(processes) / sizeof(processes[0]);
int burstTime[] = {4, 3, 7, 2};
// Sort processes by burst time
sortByBurstTime(processes, n, burstTime);
// Call the function to calculate and display average time
calculateAverageTime(processes, n, burstTime);
return 0;
}
3. Round Robin (RR) Algorithm
The Round Robin algorithm assigns a fixed time quantum to each process in the ready queue and cycles through them until all processes are complete.
Function Round_Robin_Scheduling(processes, time_quantum):
# processes is a list of tuples (process_id, burst_time)
# time_quantum is the fixed time slice for each process
Initialize remaining_time array with burst_time of each process
Initialize waiting_time array to 0 for all processes
Initialize turnaround_time array to 0 for all processes
Set time to 0
while True:
done = True
for i from 1 to number of processes:
if remaining_time[i] > 0:
done = False
if remaining_time[i] > time_quantum:
# Process still has time left after quantum
time += time_quantum
remaining_time[i] -= time_quantum
else:
# Process can finish within the quantum
time += remaining_time[i]
waiting_time[i] = time - burst_time[i]
remaining_time[i] = 0
if done:
break
for i from 1 to number of processes:
# Calculate turnaround time
turnaround_time[i] = waiting_time[i] + burst_time[i]
# Calculate average waiting time and turnaround time
avg_waiting_time = sum of waiting_time / number of processes
avg_turnaround_time = sum of turnaround_time / number of processes
return avg_waiting_time, avg_turnaround_time
CODE:
#include <stdio.h>
// Function to calculate waiting time for all processes
void calculateWaitingTime(int processes[], int n, int burstTime[], int waitingTime[], int timeQuantum) {
int remainingTime[n];
for (int i = 0; i < n; i++) {
remainingTime[i] = burstTime[i]; // Initialize remaining time for each process
}
int time = 0; // Current time
while (1) {
int done = 1;
for (int i = 0; i < n; i++) {
if (remainingTime[i] > 0) {
done = 0; // There is a pending process
if (remainingTime[i] > timeQuantum) {
time += timeQuantum;
remainingTime[i] -= timeQuantum;
} else {
time += remainingTime[i];
waitingTime[i] = time - burstTime[i];
remainingTime[i] = 0;
}
}
}
if (done == 1) {
break;
}
}
}
// Function to calculate turnaround time for all processes
void calculateTurnaroundTime(int processes[], int n, int burstTime[], int waitingTime[], int turnaroundTime[]) {
for (int i = 0; i < n; i++) {
turnaroundTime[i] = burstTime[i] + waitingTime[i];
}
}
4. Priority Scheduling Algorithm
The Priority Scheduling algorithm assigns each process a priority and schedules processes based on their priority. Lower priority numbers indicate higher priority.
Function Priority_Scheduling(processes):
# processes is a list of tuples (process_id, burst_time, priority)
Initialize waiting_time array to 0 for all processes
Initialize turnaround_time array to 0 for all processes
Set total_waiting_time to 0
Set total_turnaround_time to 0
Sort processes by priority
for i from 1 to number of processes:
if i is 1:
# First process, waiting time is zero
waiting_time[i] = 0
else:
# Calculate waiting time as the sum of burst times of all previous processes
waiting_time[i] = waiting_time[i-1] + burst_time[i-1]
# Calculate turnaround time
turnaround_time[i] = waiting_time[i] + burst_time[i]
# Update total waiting time and turnaround time
total_waiting_time += waiting_time[i]
total_turnaround_time += turnaround_time[i]
# Calculate average waiting time and turnaround time
avg_waiting_time = total_waiting_time / number of processes
avg_turnaround_time = total_turnaround_time / number of processes
return avg_waiting_time, avg_turnaround_time
CODE :
#include <stdio.h>
// Function to calculate waiting time and turnaround time
void calculateWaitingTimeAndTurnaroundTime(int processes[], int n, int burstTime[], int waitingTime[], int turnaroundTime[]) {
waitingTime[0] = 0; // Waiting time for the first process is 0
// Calculate waiting time for each process
for (int i = 1; i < n; i++) {
waitingTime[i] = burstTime[i - 1] + waitingTime[i - 1];
}
// Calculate turnaround time for each process
for (int i = 0; i < n; i++) {
turnaroundTime[i] = burstTime[i] + waitingTime[i];
}
}
// Function to calculate average waiting time and turnaround time
void calculateAverageTime(int processes[], int n, int burstTime[]) {
int waitingTime[n], turnaroundTime[n];
int totalWaitingTime = 0, totalTurnaroundTime = 0;
// Calculate waiting and turnaround time for each process
calculateWaitingTimeAndTurnaroundTime(processes, n, burstTime, waitingTime, turnaroundTime);
printf("Processes Burst Time Waiting Time Turnaround Time\n");
// Display individual process statistics and calculate total waiting and turnaround time
for (int i = 0; i < n; i++) {
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
printf("%d %d %d %d\n", processes[i], burstTime[i], waitingTime[i], turnaroundTime[i]);
}
// Calculate average waiting and turnaround time
float avgWaitingTime = (float)totalWaitingTime / (float)n;
float avgTurnaroundTime = (float)totalTurnaroundTime / (float)n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
}
// Function to sort processes by priority using bubble sort
void sortByPriority(int processes[], int n, int burstTime[], int priority[]) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (priority[j] > priority[j + 1]) {
// Swap burst time
int temp = burstTime[j];
burstTime[j] = burstTime[j + 1];
burstTime[j + 1] = temp;
// Swap priority
int tempPriority = priority[j];
priority[j] = priority[j + 1];
priority[j + 1] = tempPriority;
// Swap processes
int tempProcess = processes[j];
processes[j] = processes[j + 1];
processes[j + 1] = tempProcess;
}
}
}
}
int main() {
int processes[] = {1, 2, 3, 4};
int n = sizeof(processes) / sizeof(processes[0]);
int burstTime[] = {4, 3, 7, 2};
int priority[] = {2, 1, 4, 3}; // Lower number indicates higher priority
// Sort processes by priority
sortByPriority(processes, n, burstTime, priority);
// Call the function to calculate and display average time
calculateAverageTime(processes, n, burstTime);
return 0;
}
No comments:
Post a Comment