Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Shortest Job First Scheduling Algorithm?
3.
Characteristics of SJF Scheduling Algorithm
4.
Algorithm of Shortest Job First Scheduling
5.
Implementation of Shortest Job First Scheduling Algorithm
5.1.
C++
6.
Types of Shortest Job First
6.1.
Non-Preemptive SJF
6.2.
C++
6.3.
Preemptive SJF
6.4.
C++
7.
Advantages of SJF
8.
Disadvantages of SJF
9.
Important Terminologies
10.
Frequently Asked Questions
10.1.
Why is shortest job first the best?
10.2.
What is the shortest job first algorithm in C++?
10.3.
What do you mean by SRTF?
10.4.
What is a real life example of SJF scheduling?
11.
Conclusion
Last Updated: Jul 3, 2024
Easy

Shortest Job First (SJF) CPU Scheduling Algorithm

Author Rhythm Jain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Shortest Job First (SJF), also known as Shortest job next (SJN) is a scheduling policy that prioritises the execution of the process with the shortest execution time among waiting processes.
This algorithm is used in many real-life scenarios for example- online delivery apps always choose to deliver the nearest order first, then after delivering the first order, it searches for the next nearest delivery location thus.

This algorithm is used significantly to optimize the processing speed of the processors. In this blog, we will discuss the algorithm in detail, read about its various aspects and implementation-

Let’s first start with understanding what the shortest job first scheduling is? When given a few processes to execute, this algorithm always chooses the process with the shortest execution time to be executed first.

There are two types of the shortest job first scheduling viz. Preemptive or non-preemptive, though we will only discuss the non-preemptive shortest job first scheduling algorithm in this blog.

What is the Shortest Job First Scheduling Algorithm?

In the shortest job first scheduling, the processor always compares the processes waiting to be executed to choose the one with the shortest burst time and again makes the comparison after the ongoing process ends. To understand it thoroughly, let’s see an example:

Shortest Job First Scheduling Algorithm

Suppose the above table shows how the processes arrive at a processor to be processed. In that case, the gantt chart below will depict how they will be processed if the processor works on the shortest job first scheduling algorithm.

Example of the shortest job first scheduling
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Characteristics of SJF Scheduling Algorithm

Characteristics of Shortest Job First (SJF) Scheduling Algorithm:

  • Optimality: SJF scheduling algorithm ensures optimal CPU utilization by selecting the shortest job first, minimizing average waiting time.
  • Non-preemptive: Typically, SJF is implemented as a non-preemptive 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 real-world 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 real-time 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++

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<noofprocess-i-1;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[i-1][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:

Non-Preemptive SJF

In non-preemptive 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++

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++

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 batch-type 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

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 a real life example of SJF scheduling?

This algorithm is used in many real-life scenarios for example: online delivery apps always choose to deliver the nearest order first, then after delivering the first order, it searches for the next nearest delivery location thus.

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 first-come-first-serve scheduling algorithm, by focusing on executing the shortest process first. 

Recommended Articles

 

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.

Previous article
Shortest Job First(Non-preemptive)
Next article
Round Robin Scheduling
Live masterclass