Shortest Job First(Non-preemptive)

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

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.

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

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.

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.

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.

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.

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 

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);

    }
}

You can also try this code with Online Java Compiler

Run Code

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