Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Medium

Shortest Job First(Non-preemptive)

Author Ankit Kumar
0 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up
Operating System

Introduction

There are various CPU scheduling algorithms through which the processes are allotted CPU for their completion. The shortest job first, as the name suggests, is a scheduling algorithm in which out of many processes seeking CPU allocation, the process that has the least burst time is allocated the CPU first i.e., the priority is given to the process that requires less time to complete. This continues until all the processes get the CPU.

It is a very simple scheduling algorithm and is very easy to understand. Most questions are regarding the completion time, turnaround time, and average waiting time. Through the examples below, we will see how the shortest job first works. 

Shortest job first can be of two types.

  • Non-Preemptive: The CPU is allotted to the process until its completion.
  • Preemptive: The CPU can be deallocated for the running process for some time and again allocated to it.

(See, Preemptive and Non-Preemptive Scheduling)

We will restrict ourselves to non-preemptive shortest job first CPU scheduling in this article. The key idea is to look for the process with the least burst time (B.T.) among various processes in the ready queue and allocate the CPU to it. The examples below will help clear all the doubts regarding the same. We will also learn how to prepare a Gantt chart for the processes which helps us in various calculations.

Example 1

Given five processes with process id/ no. as P1, P2, P3, P4, P5 along with their respective arrival time (A.T.) and burst time (B.T.). We need to draw the Gantt chart and find the completion time for each process. The time is denoted in milliseconds(ms).

Process id/ no. Arrival Time(A.T.) Burst Time(B.T.)
P1 0 ms 2 ms
P2 1 ms 5 ms
P3 2 ms 3 ms
P4 3 ms 1 ms
P5 5 ms 4 ms

 

Approach

At t=0 ms,

The only process that is available in the ready queue is P1 because the arrival time for P1 is 0ms. Although the process with least burst time (B.T.) is P4( with B.T. of 1 ms) but P4 is not available at t= 0 ms. So we have to allocate CPU to P1.

 

  • The Gantt chart below shows that at t= 0ms CPU is allocated to process P1. Since we are considering the non-preemptive version of the shortest job first, the process will continue running until its completion. P1 requires 2 ms to complete.

 
Therefore in the Gantt chart, we represent P1 having been scheduled from t=0 ms till t= 2ms.

Gnatt Chart

 

  • At t= 2ms, processes P2 and P3 are available in the ready queue and are waiting for the CPU to get allocated. P1 has already completed its work.


P2 has a B.T. of 5ms and P3 has a B.T. of 3ms. As you might have guessed, now process P3 will be scheduled until its completion.

 

Below is the Gantt chart.

Gnatt Chart

P3 is scheduled from t=2ms till t=5ms.

 

  • At t= 5ms, processes P1 and P3 have completed their work. Now all other processes have arrived in the ready queue and are waiting to get scheduled. It can be clearly observed that process P5 arrives at t= 5ms, so all the processes are now available.

 

At t= 5ms, three processes are waiting to get scheduled. The B.T. of P2, P4, and P5 respectively is 5ms, 1ms, and 4ms. Among the three processes, P4 has the least B.T. of 1ms, so it will get scheduled next.

Below is the Gantt chart.

Gnatt Chart

Process P4 is allocated the CPU from t=5ms till t=6ms because it has a burst time of 1ms.

 

  • At t= 6ms, processes P1, P3, and P4 have completed their work and only P2 and P5 are left to get scheduled. P2 has a B.T. of 5ms and P5 has a B.T. of 4ms. Of the two processes, P5 has the least B.T of 4ms, so it will get scheduled next.

 

Below is the Gantt chart.

Gnatt Chart

Process P5 uses CPU till t=10ms because it has a B.T. of 4ms.

 

  • At t=10ms, we are left with only one process i.e P2 that is required to get scheduled, so we don't have to worry about the burst time. Whatever the burst time the last process is allocated to the CPU, and after its completion, all the processes have finally been scheduled.
     
  • Below is the Gantt chart.
Gnatt Chart

Process P2 gets allocated at t=10ms and completes its work at t=15ms because its burst time is 5ms.

 

This is how the shortest job first (SJF) CPU scheduling works. 

Try out the implementation of shortest job first scheduling algorithm(Non-preemptive) before moving towards the solution

ANALYSIS OF SHORTEST JOB FIRST

Consider the final Gantt chart which we just got. We can get various information such as the completion time of each process, turnaround time,  waiting time for each process, etc.

Gnatt Chart

Completion time:  It is the time at which the process finishes its execution. From the Gantt chart we can see that the completion time for process P1 is 2ms, P3 is 5ms, P4 is 6ms, P5 is 10ms and P2 is 15ms. For every process, we just have to look at the immediate right bar. The time denoted below it represents the completion time for the process.

Turn around time(T.A.T): It is the difference between completion time(C.T.) and arrival time(A.T.). The Turnaround time for all the five processes is shown in the below table.

Waiting time(W.T.): It is the difference between turnaround time and burst time. The waiting time actually represents the time that a particular process has spent in the ready queue waiting for CPU allocation. The waiting time(W.T.) for all the five processes is shown in the table below.

The average waiting time can easily be found by adding all the waiting times of the process available and dividing it by the number of processes.

The average waiting time for the below table is = (0+9+0+2+1)/5 = 12/5= 2.4 

Process id/ no. Arrival Time(A.T.) Burst Time(B.T.) Completion time(C.T)

Turn around time(T.A.T)

(C.T. - A.T.)

Waiting time(W.T.)

(T.A.T. - B.T.)

P1 0 ms 2 ms 2ms 2-0= 2ms 2-2=0ms
P2 1 ms 5 ms 15ms 15-1= 14ms 14-5= 9ms
P3 2 ms 3 ms 5ms 5-2= 3ms 3-3 = 0ms
P4 3 ms 1 ms 6ms 6-3= 3ms 3-1= 2ms
P5 5 ms 4 ms 10ms 10-5= 5ms 5-4= 1ms

 

Implementation of the shortest job first in Java

import java.util.*;

class ShortestJobFirst {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of process: ");
        int n = sc.nextInt();

        int process[] = new int[n];
        int burstTime[] = new int[n];
        int waitingTime[] = new int[n];
        int turnAroundTime[] = new int[n];

        int i, j, total = 0, pos, temp;
        float avgWaitingTime, avgTurnAroundTime;

        System.out.println("\nEnter Burst time:");
        for (i = 0; i < n; i++) {
            System.out.print("\nProcess[" + (i + 1) + "]: ");
            burstTime[i] = sc.nextInt();
            process[i] = i + 1;
        }

        //Sorting according to burst time. In SJF process with
        // least burst time is scheduled first.
        for (i = 0; i < n; i++) {
            pos = i;
            for (j = i + 1; j < n; j++) {
                if (burstTime[j] < burstTime[pos])
                    pos = j;
            }

            temp = burstTime[i];
            burstTime[i] = burstTime[pos];
            burstTime[pos] = temp;

            temp = process[i];
            process[i] = process[pos];
            process[pos] = temp;
        }

        waitingTime[0] = 0;
//calculate waiting time for every process
        for (i = 1; i < n; i++) {
            waitingTime[i] = 0;
            for (j = 0; j < i; j++)
                waitingTime[i] += burstTime[j];
            total += waitingTime[i];
        }

//Calculating Average waiting time
        avgWaitingTime = (float) total / n;
        total = 0;

        System.out.println("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");
        for (i = 0; i < n; i++) {
            turnAroundTime[i] = burstTime[i] + waitingTime[i]; //Calculating Turnaround Time
            total += turnAroundTime[i];
            System.out.println("\n p" + process[i] + "\t\t " + burstTime[i] + "\t\t " + waitingTime[i] + "\t\t " + turnAroundTime[i]);
        }

//Calculation of Average Turnaround Time
        avgTurnAroundTime = (float) total / n;
        System.out.println("\n\nAverage Waiting Time: " + avgWaitingTime);
        System.out.println("\nAverage Turnaround Time: " + avgTurnAroundTime);

    }
}

Advantages of the shortest job first(non-preemptive)

  • The throughput is maximum in the shortest job first. Throughput is the number of processes executed in unit time. Since the process with the least burst time is executed first, more processes can be scheduled using SJF.
  • The average waiting time and average turnaround time is minimum in SJF.

 

Disadvantages of the shortest job first(non- preemptive)

  • It cannot be practically implemented because we cannot determine the burst time of a process before its execution.
  • It may cause a convoy effect. Suppose a process with a large burst time arrives first and is scheduled first. Even if there is some other process with very little burst time, it will have to wait for the previous process to finish its execution. This will lead to starvation of the other process and greatly impact the performance.

Recommended Topic, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking

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

Frequently Asked Questions

Why is the shortest job first optimal?

The shortest job first allocates CPU to the processes based on their burst time. The process with the least burst time is allocated first. Because of this, the average waiting time is minimum.

Why is it difficult to implement the shortest job first?

The shortest job first requires us to know the burst time beforehand which is not possible to determine accurately. Hence we cannot implement it.

What do you mean by non-preemptive?

By non-preemptive, we mean that once the process is in a running state, it cannot be halted in between. It will terminate only after its execution.

Can the shortest job first cause starvation?

In case a process with a large burst time arrives first, it will enter a running state because of which other processes with a small burst time may have to wait for a very long time. Therefore the shortest job first can cause starvation.

Conclusion

  • This article discussed the shortest job first(non-preemptive) CPU scheduling.
  • We discussed how to make a Gantt chart for SJF which helps us in various calculations.
  • We also discussed why SJF is optimal.
  • Despite being optimal, it may cause starvation or a convoy effect.
  • We learned how to find out the completion time, turnaround time, and waiting time for the processes.


Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!

Previous article
What is Belady's Anomaly in Operating System
Next article
Shortest Job First (SJF) CPU Scheduling Algorithm
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass