Operating System

SJF Scheduling : Explained

Abstract

In SJF(Shortest Job First)  scheduling, the process which has the shortest burst time is scheduled first but if two processes have the same burst time then FCFS is used to break the tie. It is a non-preemptive scheduling algorithm.

Scope 

This article talks about SJF scheduling in detail.

Definition

The problem in FCFS scheduling was if there is a job that is CPU bound and it has come first and has been scheduled on CPU, the other jobs which take less time to have to wait for this long job. It decreases throughput and increases average waiting time. The idea of the shortest job first algorithm is to consider the jobs in increasing order of their CPU burst time. This algorithm is non-preemptive. Being a non-preemptive algorithm, the first process assigned to the CPU is executed till completion then the process whose burst time is minimum is assigned next to the CPU and hence it continues. 

Let’s understand the following problem :

PROCESS ARRIVAL TIME BURST TIME
        P0            0          5
        P1            1          4
        P2            2          3
        P3            3          8

The Gantt chart of the following problem is:

Final Chart

PROCESSARRIVAL TIME BURST TIMECOMPLETION TIME TURN AROUND TIMEWAITINGTIME 
        P0            0          5      5      5      0
        P1            1          4      12    11      7
        P2            2          3      8    6      3
        P3            3          8    20  17      9

* Turn around time = Completion time – Arrival time 

*Waiting time = Turn around time – Burst time 

So Average turn around time = (5+11+6+17)/4 = 39/4

And average waiting time = (0+7+3+9)/4 = 19/4

Some important points 

  • This algorithm gives a minimum average waiting time so it is an optimal algorithm.
  • It is a greedy algorithm.
  • If the shorter processes keep coming one after the other, it may cause starvation. This problem can be solved using the concept of aging. 
  • This algorithm assumes that the operating system knows the burst time of every process in the ready queue which is an impractical thing because it is not possible to guess the CPU burst time of every job or process.

Summary

SJF(Shortest Job first) is a non-preemptive algorithm. In this, the process which has the shortest CPU burst time is scheduled first. This algorithm has the minimum average time among all the scheduling algorithms.

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article