Embedded Files
2. Experiment
Aim: Write a program to implement SJF CPU scheduling algorithm. Theory: SJF (Shortest Job First) is a CPU scheduling algorithm where the process with the shortest burst time is selected first for execution.Types:1.Non-preemptive SJF:
Once a process starts executing, it runs till it finishes. (No interrupt by another process)
2.Preemptive SJF (also called Shortest Remaining Time First, SRTF):
If a new process with a shorter burst time arrives while another is executing, the CPU may preempt (interrupt) the current process.
Advantages:
Gives minimum average waiting time.
CPU utilization is high.
Short processes are finished quickly.
Disadvantages:
May cause starvation for long processes if short ones keep arriving.
Requires knowledge of burst time in advance.
Flowchart
Algorithm
Step 1: Start
Step 2: Input number of processes (n).
Step 3: For each process, input Arrival Time and Burst Time.
Step 4: Sort processes by Arrival Time first. If Arrival is same, then by Shortest Burst Time.
Step 5: Set current time = 0.
Step 6: Loop until all processes are finished:
a) From available processes (those arrived <= current time), select the one with minimum Burst Time.
b) If no process is available, increment current time by 1.
c) Otherwise, execute the process:
- Start process immediately.
- Update its Waiting, Turnaround and Completion.
- Update current time = current time + Burst Time of this process.
Step 7: Display the results.
Step 8: End.
Source Code :
// C++ code for SJF (Non-preemptive) CPU Scheduling Algorithm, where the number of processes is given as // // input by the user.
#include <iostream>
#include <algorithm>
using namespace std;
struct Process {
int id, at, bt, ct, tat, wt;
bool done;
};
bool compareArrival(Process a, Process b) {
return a.at < b.at;
}
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 Time for P" << i + 1 << ": ";
cin >> p[i].at;
cout << "Enter Burst Time for P" << i + 1 << ": ";
cin >> p[i].bt;
p[i].done = false;
}
sort(p, p + n, compareArrival);
int completed = 0;
int currentTime = 0;
while (completed < n) {
int idx = -1;
int minBt = 10000;
for(int i = 0; i < n; i++) {
if (!p[i].done && p[i].at <= currentTime && p[i].bt < minBt) {
minBt = p[i].bt;
idx = i;
}
}
if (idx == -1) { // no process arrived
currentTime++;
}
else {
p[idx].ct = currentTime + p[idx].bt;
p[idx].tat = p[idx].ct - p[idx].at;
p[idx].wt = p[idx].tat - p[idx].bt;
p[idx].done = true;
currentTime = p[idx].ct;
completed++;
}
}
cout << "\nPID\tAT\tBT\tCT\tTAT\tWT\n";
for(int i = 0; i < n; i++) {
cout << p[i].id << '\t' << p[i].at << '\t' << p[i].bt << '\t' << p[i].ct << '\t' << p[i].tat << '\t' << p[i].wt << '\n';
}
}
// NOTE : Program should be with output in Lab file
Multiple-Choice Question (MCQ) based on the objective of SJF:
What is the main objective of Shortest Job First (SJF) CPU scheduling?
a) To maximize CPU utilization
b) To minimize average waiting time
c) To maximize throughput
d) To minimize context switches
Answer: b) To minimize average waiting time
SJF is a __________ scheduling algorithm.
a) Preemptive
b) Non-preemptive
c) Round Robin
d) First Come First Served
Answer: b) Non-preemptive
SJF executes the process with:
a) Smallest CPU burst first
b) Largest CPU burst first
c) Earliest arrival first
d) Higher priority first
Answer: a) Smallest CPU burst first
JF performs well when:
a) Burst times are large
b) Arrival rate is high
c) Jobs are of similar length
d) CPU is under heavy load
Answer: c) Jobs are of similar length
A major drawback of SJF is:
a) It cannot minimize waiting time
b) It may cause starvation
c) It’s a FIFO algorithm
d) It’s non-deterministic
Answer: b) It may cause starvation
Starvation : situation where a process is indefinitely blocked from accessing resources due to the dominance of higher-priority tasks. This often happens in priority-based scheduling systems where lower-priority processes are repeatedly overlooked, leading to a scenario where they are unable to complete their execution.
To implement SJF effectively, the OS must know:
a) Arrival time
b) CPU burst length in advance
c) Priority
d) Deadline
Answer: b) CPU burst length in advance
SJF is optimal in the sense of:
a) Max throughput
b) Min context switches
c) Min average waiting time
d) Max CPU utilization
Answer: c) Min average waiting time
If two processes have the same burst time, SJF typically falls back to:
a) FIFO
b) Priority
c) LRU
d) Robin algorithm
Answer: a) FIFO (First Come First Served)
Page updated
Report abuse