Embedded Files
5. Experiment
Aim: Write a program to compare various CPU Scheduling Algorithms over different Scheduling Criteria.
Theory:
Comparison of various CPU Scheduling algorithms (like FCFS, SJF, Priority, and Round Robin) over different scheduling criteria.
Average Waiting Time:
FCFS: Higher; depends on order of arrival, often suffering from “convoy effects.”
SJF: Lower; it's optimized to minimize waiting time by serving short jobs first.
Priority: Medium; depends on priorities — high-priority first, ignoring process length.
Round Robin: Medium; waiting is divided fairly amongst all.
Turnaround Time:
SJF: Small; because waiting is small, turnaround is small.
FCFS: Large; waiting accumulates.
Priority: Medium; depends on priority.
Round Robin: Medium; it's fair but not always minimum.
Flowchart
Algorithm
Step 1: Start
Step 2: Input number of processes (n).
Step 3: Input Arrival Time and Burst Time for each process.
Step 4: Perform FCFS, SJF, Priority, and Round Robin scheduling separately:
- Sort or select processes according to algorithm criteria.
- Calculate Waiting and Turnaround for each process.
Step 5: Average Waiting and Turnaround = total / n
Step 6: Display Average Waiting and Turnaround for all algorithms.
Step 7: End
Source Code :
// C++ program to compare various CPU Scheduling Algorithms over different Scheduling Criteria.
#include <iostream>
#include <algorithm>
using namespace std;
struct Process { int id, at, bt, pr, rt, wt, tat; };
bool byArrival(Process a, Process b){ return a.at < b.at; }
bool byPriority(Process a, Process b){ return a.pr < b.pr; }
bool byBurst(Process a, Process b){ return a.bt < b.bt; }
// FCFS
void FCFS(Process p[], int n) {
sort(p, p + n, byArrival);
int time = 0, total_wt = 0, total_tat = 0;
for(int i = 0; i < n; i++) {
if (time < p[i].at) time = p[i].at;
p[i].wt = time - p[i].at;
p[i].tat = p[i].wt + p[i].bt;
time += p[i].bt;
total_wt += p[i].wt;
total_tat += p[i].tat;
}
cout << "FCFS avg waiting = " << 1.0*total_wt/n;
cout << ", avg turnaround = " << 1.0*total_tat/n << endl;
}
// SJF
void SJF(Process p[], int n) {
sort(p, p + n, byArrival);
int time = 0, completed = 0, total_wt = 0, total_tat = 0;
bool done[100] = {false};
while (completed < n) {
int idx = -1;
int min = 1e9;
for(int i = 0; i < n; i++) {
if (p[i].at <= time && !done[i] && p[i].bt < min) {
min = p[i].bt;
idx = i;
}
}
if (idx == -1) { time++; continue; }
p[idx].wt = time - p[idx].at;
p[idx].tat = p[idx].wt + p[idx].bt;
time += p[idx].bt;
done[idx] = true;
total_wt += p[idx].wt;
total_tat += p[idx].tat;
completed++;
}
cout << "SJF avg waiting = " << 1.0*total_wt/n;
cout << ", avg turnaround = " << 1.0*total_tat/n << endl;
}
// Priority
void Priority(Process p[], int n) {
sort(p, p + n, byArrival);
int time = 0, completed = 0, total_wt = 0, total_tat = 0;
bool done[100] = {false};
while (completed < n) {
int idx = -1;
int maxPr = 1e9;
for(int i = 0; i < n; i++) {
if (p[i].at <= time && !done[i] && p[i].pr < maxPr) {
maxPr = p[i].pr;
idx = i;
}
}
if (idx == -1) { time++; continue; }
p[idx].wt = time - p[idx].at;
p[idx].tat = p[idx].wt + p[idx].bt;
time += p[idx].bt;
done[idx] = true;
total_wt += p[idx].wt;
total_tat += p[idx].tat;
completed++;
}
cout << "Priority avg waiting = " << 1.0*total_wt/n;
cout << ", avg turnaround = " << 1.0*total_tat/n << endl;
}
int main()
{
int n;
cout << "Enter number of processes: "; cin >> n;
Process p[n];
for(int i = 0; i < n; i++) {
p[i].id = i + 1;
cout << "Enter Arrival, Burst, Priority for P" << i + 1 << ": ";
cin >> p[i].at >> p[i].bt >> p[i].pr;
}
Process p1[n], p2[n], p3[n];
for(int i = 0; i < n; i++) p1[i] = p2[i] = p3[i] = p[i];
cout << "Comparing CPU Scheduling:" << endl;
FCFS(p, n);
SJF(p1, n);
Priority(p2, n);
}
MCQs that compare various CPU Scheduling algorithms (like FCFS, SJF, Priority, Round Robin) against different scheduling criteria (like waiting time, turnaround, fairness, context switches, CPU utilization, etc.).
1. Which algorithm minimizes average waiting time?
a) FCFS
b) SJF
c) Priority
d) Round Robin
Answer: b) SJF
2. Which algorithm avoids starvation?
a) SJF
b) Priority
c) FCFS
d) Round Robin
Answer: d) Round Robin
3. Which algorithm is Non-Preemptive?
a) SJF (Non-preemptive)
b) Priority (Non-preemptive)
c) FCFS
d) All of the above
Answer: d) All of the above
4. Which algorithm performs well in time-sharing systems?
a) FCFS
b) SJF
c) Priority
d) Round Robin
Answer: d) Round Robin
5. Higher context switches typically happen when we:
a) Have large time quantum
b) Reduce time quantum
c) Apply non-preemptive algorithm
d) Reduce number of processes
Answer: b) Reduce time quantum
6. The main criteria for choosing SJF is:
a) Arrival order
b) Smallest CPU burst
c) Higher priority
d) Large quantum
Answer: b) Smallest CPU burst
7. If two processes have the same priority in Priority scheduling, we typically resolve by:
a) Shorter job first
b) FIFO
c) Higher I/O
d) Lower process ID
Answer: b) FIFO
8. Which algorithm can suffer from convoy effects?
a) SJF
b) Priority
c) FCFS
d) Round Robin
Answer: c) FCFS
9. The main advantage of Round Robin over FCFS is:
a) Lower waiting time
b) Better fairness
c) Higher throughput
d) Less context switching
Answer: b) Better fairness
10. To minimize average waiting time, we should use:
a) FCFS
b) Priority
c) SJF
d) Round Robin
Answer: c) SJF
11. Which algorithm guarantees frequent CPU service to all?
a) Priority
b) SJF
c) Round Robin
d) FCFS
Answer: c) Round Robin
12. Which criteria will suffer if we use large time quanta in RR?
a) Fairness
b) CPU utilization
c) Response time
d) Throughput
Answer: c) Response time
13. Small time quanta in RR results in:
a) Less context switching
b) Higher context switching
c) Lower waiting
d) Higher throughput
Answer: b) Higher context switching
14. If we ignore context switching, which algorithm minimizes total waiting?
a) FCFS
b) Priority
c) SJF
d) Round Robin
Answer: c) SJF
15. If we need fairness and low response time in a multi-user OS, we typically prefer:
a) SJF
b) Priority
c) FCFS
d) Round Robin
Answer: d) Round Robin
Page updated
Report abuse