Characteristics of SJF Scheduling
Characteristics of Shortest Job First (SJF) Scheduling:

Optimality: SJF scheduling algorithm ensures optimal CPU utilization by selecting the shortest job first, minimizing average waiting time.

Nonpreemptive: Typically, SJF is implemented as a nonpreemptive scheduling algorithm, meaning once a process starts executing, it continues until completion.

Dynamic: SJF requires knowledge of the burst time of each process, making it a dynamic scheduling algorithm.

Starvation: Long processes may suffer from starvation in SJF, as shorter processes continuously arrive, causing them to wait indefinitely.

Implementation Complexity: Accurate prediction of process burst times is often challenging, leading to complexity in realworld implementations.

Variance Sensitivity: SJF can be sensitive to variance in burst times; small variations may significantly affect the overall performance of the algorithm.

Limited Applicability: SJF is not suitable for interactive or realtime systems where predictability and fairness are critical due to its inherent unpredictability and potential for process starvation.
Algorithm of Shortest Job First Scheduling
 Start with sorting all the processes based on their time of arrival at the processor.
 Then select the earliest arriving process with the shortest burst time.
 While executing the current process, all the waiting processes are pushed in the waiting queue, and when the current process ends, choose the process with the shortest burst time among the waiting processes.
Read More  Time Complexity of Sorting Algorithms
Implementation of Shortest Job First Scheduling Algorithm
C++
#include <bits/stdc++.h>
using namespace std;
//Matrix to store the values.
int matrix[20][6];
//Function to swap.
void swap(int *x, int *y)
{
int var = *x;
*x = *y;
*y = var;
}
//Function to sort the processes by the time of arrival.
void sortbyarrival(int noofprocess, int matrix[][6])
{
for( int i=0;i<noofprocess;i++)
{
for(int j=0;j<noofprocessi1;j++)
{
if(matrix[j][1]>matrix[j+1][1])
{
for(int k=0;k<5;k++)
{
swap(matrix[j][k],matrix[j+1][k]);
}
}
}
}
}
//Choosing the process with minimum burst time.
void timeofcompletion(int noofprocess, int matrix[][6])
{
int var, ctr;
matrix[0][3] = matrix[0][1] + matrix[0][2];
matrix[0][5] = matrix[0][3]  matrix[0][1];
matrix[0][4] = matrix[0][5]  matrix[0][2];
for(int i=1;i<noofprocess;i++)
{
var=matrix[i1][3];
int lower=matrix[i][2];
for(int j=i;j<noofprocess;j++)
{
if(var>= matrix[j][1]&&lower>=matrix[j][2])
{
lower=matrix[j][2];
ctr=j;
}
}
matrix[ctr][3] = var+matrix[ctr][2];
matrix[ctr][5] = matrix[ctr][3]  matrix[ctr][1];
matrix[ctr][4] = matrix[ctr][5]  matrix[ctr][2];
for(int k=0;k<6;k++)
{
swap(matrix[ctr][k],matrix[i][k]);
}
}
}
//Driver function.
int main()
{
int noofprocess=6;
matrix[0][0]=1,matrix[0][1]=2,matrix[0][2]=3;
matrix[1][0]=2,matrix[1][1]=0,matrix[1][2]=4;
matrix[2][0]=3,matrix[2][1]=4,matrix[2][2]=2;
matrix[3][0]=4,matrix[3][1]=5,matrix[3][2]=4;
matrix[4][0]=5,matrix[4][1]=6,matrix[4][2]=6;
matrix[5][0]=6,matrix[5][1]=7,matrix[5][2]=7;
sortbyarrival(noofprocess, matrix);
timeofcompletion(noofprocess, matrix);
cout<<"Process ID Arrival Time Burst Time Waiting Time Turnaround Time"<<endl;
for(int i=0; i<noofprocess; i++)
{
cout<<matrix[i][0]<<" "<<matrix[i][1]<<" "<<matrix[i][2]<<" "<<matrix[i][4]<<" "<<matrix[i][5]<<endl;
}
}
Output:
Process ID Arrival Time Burst Time Waiting Time Turnaround Time
2 0 4 0 4
3 4 2 0 2
1 2 3 4 7
4 5 4 4 8
5 6 6 7 13
6 7 7 12 19
The time complexity of this algorithm is O(N*log(N)).
The space complexity of this algorithm is O(1).
You can also read about layered structure of operating system.
Must Read: Design and Analysis of Algorithms
Types of Shortest Job First
Shortest Job First (SJF) scheduling has two main types:
NonPreemptive SJF
In nonpreemptive SJF, once a process starts executing, it continues until completion without interruption. The scheduler selects the shortest job from the ready queue and allows it to run to completion before selecting the next shortest job.
Implementation:
C++
#include <iostream>
#include <vector>
#include <algorithm>
struct Process {
int id;
int arrivalTime;
int burstTime;
};
bool compareArrivalTime(Process a, Process b) {
return a.arrivalTime < b.arrivalTime;
}
bool compareBurstTime(Process a, Process b) {
return a.burstTime < b.burstTime;
}
void sjfNonPreemptive(std::vector<Process> processes) {
std::sort(processes.begin(), processes.end(), compareArrivalTime);
int currentTime = 0;
float totalWaitingTime = 0;
for (auto process : processes) {
if (currentTime < process.arrivalTime)
currentTime = process.arrivalTime;
currentTime += process.burstTime;
totalWaitingTime += currentTime  process.arrivalTime  process.burstTime;
}
std::cout << "Average waiting time: " << totalWaitingTime / processes.size() << std::endl;
}
int main() {
std::vector<Process> processes = { {1, 0, 6}, {2, 1, 8}, {3, 2, 7}, {4, 3, 3} };
sjfNonPreemptive(processes);
return 0;
}
Output
Average waiting time: 8.75
Preemptive SJF
In preemptive SJF, a running process can be interrupted if a new process arrives with a shorter burst time. The scheduler selects the shortest remaining time job from the ready queue, preempts the currently running process if necessary, and executes the selected process.
Implementation:
C++
#include <iostream>
#include <vector>
#include <algorithm>
struct Process {
int id;
int arrivalTime;
int burstTime;
};
bool compareArrivalTime(Process a, Process b) {
return a.arrivalTime < b.arrivalTime;
}
bool compareBurstTime(Process a, Process b) {
return a.burstTime < b.burstTime;
}
void sjfPreemptive(std::vector<Process> processes) {
std::sort(processes.begin(), processes.end(), compareArrivalTime);
int currentTime = 0;
float totalWaitingTime = 0;
while (!processes.empty()) {
auto shortest = std::min_element(processes.begin(), processes.end(), compareBurstTime);
currentTime = std::max(currentTime, shortest>arrivalTime);
totalWaitingTime += currentTime  shortest>arrivalTime;
currentTime += shortest>burstTime;
processes.erase(shortest);
}
std::cout << "Average waiting time: " << totalWaitingTime / processes.size() << std::endl;
}
int main() {
std::vector<Process> processes = { {1, 0, 6}, {2, 1, 8}, {3, 2, 7}, {4, 3, 3} };
sjfPreemptive(processes);
return 0;
}
Output
Average waiting time: inf
Advantages of SJF
The advantages of Shortest Job First (SJF) Scheduling are:

Optimal Efficiency: SJF scheduling algorithm minimizes average waiting time by executing shorter jobs first, leading to optimal CPU utilization.

Improved Turnaround Time: Shorter jobs complete quickly, reducing the average turnaround time and enhancing system responsiveness.

Predictability: SJF provides predictable performance as it selects the shortest job, making it easier to estimate job completion times.

Reduced Waiting Time: Short jobs are prioritized, minimizing the waiting time for processes in the ready queue, thus enhancing overall system throughput.

Enhanced Resource Utilization: By prioritizing short jobs, SJF helps in better utilization of system resources, leading to improved system efficiency.
Disadvantages of SJF
The disadvantages of Shortest Job First (SJF) Scheduling:

Starvation: Longer jobs may suffer from starvation as they wait indefinitely behind short jobs, leading to potential delays in their execution.

Difficulty in Predicting Job Length: Accurately predicting job lengths in advance can be challenging, making it hard to implement SJF effectively in practice.

Need for Accurate Burst Time Estimation: SJF relies on precise burst time estimations, which may not always be available or accurate, impacting scheduling decisions.

Preemption Overhead: In preemptive SJF, frequent preemptions can introduce overhead and context switch costs, reducing system efficiency.

Unfairness: Preemptive SJF may prioritize short bursts excessively, potentially causing longer jobs to experience unfair treatment and increased waiting times.
Important Terminologies
As this topic belongs to the operating subject domain as well, before proceeding further, letâ€™s understand a few terminologies related to it that are used frequently in the blog
 Burst timeâ€“ It refers to the amount of time in which a process gets executed in standard conditions.
 Arrival time of a processâ€“ The time at which a process is assigned to the processor to be processed.
 Completion timeâ€“ The time at which the execution of the process ends is known as completion time.
 Turnaround timeâ€“ This is the total time the processing spends at the processor, which is equal to the difference between completion time and arrival time.
 Waiting timeâ€“ It is the difference between the time the process spends at the processor and the time it requires to be completed in a standard condition. I.e., turnaround time â€“ burst time.
For a processor to perform this kind of scheduling algorithm, it must know the burst time of the processes beforehand. And this is effective for batchtype processing, in which the waiting time is not critical for the process. This kind of processing has a high throughput because it ensures the shorter tasks are completed as early as possible.
Frequently Asked Questions
What is the preemptive shortest job first scheduling?
Preemptive shortest job first scheduling algorithm is used by processors to decide the order in which the processes assigned should get executed. Preemptive means the process can switch from the ready state to waiting for state or vice versa. In nonpreemptive scheduling, the process will either terminate or move to the waiting state after execution begins.
Why is shortest job first the best?
Shortest Job First (SJF) minimizes average waiting time by executing shorter jobs first, leading to optimal CPU utilization and improved system efficiency.
What is the shortest job first algorithm in C++?
Shortest Job First (SJF) algorithm in C++ selects the shortest job for execution, enhancing system responsiveness and reducing average waiting time.
What do you mean by SRTF?
Shortest Remaining Time First (SRTF) is a preemptive version of SJF where a running process can be preempted if a shorter job arrives.
What is the difference between SJF and SRTF?
SJF schedules the shortest job first, while SRTF is preemptive, allowing shorter jobs to interrupt longer ones, potentially reducing average waiting time even further.
Conclusion
In this blog, we discussed the program for Shortest Job First (SJF) CPU Scheduling. We have learned what SJF is and why it is used. SJF CPU Scheduling stands as a powerful algorithm in optimizing CPU utilization and reducing average waiting time. Its ability to prioritize shorter jobs ensures efficient resource allocation and enhances system responsiveness.
In this algorithm, we always choose the process with the shortest burst time and until the current process gets executed, we maintain all incoming processes in a waiting queue. Once the current process ends, we check the waiting queue for the process with the shortest execution time, and then we begin executing that process.
This algorithm is suitable for batch type processing as to decide which process must be executed first, we must know its burst time beforehand. It works more efficiently than the naive firstcomefirstserve scheduling algorithm, by focusing on executing the shortest process first. Read more about search algorithms here, Donâ€™t forget to practice similar problems on code studio as well. If you liked this blog, share it with your friends.