Shortest Job First (SJF) CPU Scheduling Algorithm

Shortest Job First (SJF) CPU Scheduling Algorithm
Shortest Job First (SJF) CPU Scheduling Algorithm

Introduction

The shortest job first scheduling is an algorithm which, in simple words, means that the shortest job gets executed first. 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.

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.

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
Example of how the processes arrive at a processor

Suppose the above table shows an instance of how the processes arrive at a processor to be processed. In that case, the table 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
Example of the shortest job first scheduling

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.

Implementation of Shortest job first scheduling algorithm

#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)).

blog banner 1

The space complexity of this algorithm is O(1).

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 non-preemptive scheduling, the process will either terminate or move to the waiting state after execution begins.

Why is the shortest job first scheduling the optimal way of processing?

Shortest job first scheduling is the optimal way of processing as It increases the total number of tasks completed rapidly as it always chooses the shortest task.

Which has a better average waiting time, non-preemptive shortest job first scheduling, or first-come-first-serve scheduling?

Non-preemptive shortest job first scheduling has better average waiting times. Its throughput is more than the first-come-first-serve scheduling algorithm.

Is Priority Scheduling preemptive?

No, priority scheduling is a non-preemptive scheduling algorithm as the process with the highest priority gets executed first.

Which scheduling algorithm is best?

Round robin scheduling is the best scheduling algorithm as it distributes the processor to the processes in the most efficient manner.

Key takeaways

In this blog, we discussed the shortest job first scheduling algorithm. We learned how to decide the order in which the processes get executed, and then we wrote a program for its Implementation.

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