Shortest Job First (SJF) CPU Scheduling Algorithm

 

Shortest Job First Scheduling (SJF):

It links with each process the length of the latter’s next CPU burst. When the CPU is free, it is assigned to the process of the ready queue which has smallest next CPU burst. If two processes have the same length, FCFS scheduling is used to break the tie.

 

SJF scheduling algorithm is used frequently in long term scheduling. This algorithm may be either preemptive or non-preemptive. A preemptive SJF algorithm will preempt the currently executing process, whereas a non- preemptive SJF algorithm will allow the currently running process to finish its CPU burst. Consider the following set of processes with burst time in milliseconds:

Process	Burst time
P1	3
P2	6
P3	4
P4	2

Arrival time of the process is 0 and the processes arrive in the order of P1, P2, P3 and P4. The Gantt chart, waiting time and turnaround time are as follows:

 

Gantt chart:

Waiting time:

Process	Waiting time
P1	2
P2	9
P3	5
P4	0

 

 Turnaround time:

 It is the sum of burst time + waiting time of each process.

 

Process	Turnaround time
P1	3 + 2 = 5
P2	6 + 9 = 15
P3	4 + 5 = 9
P4	2 + 0 = 2

 

SJF algorithm is an optimal algorithm. It gives the minimum average waiting time for a given set of processes. However, SJF algorithm cannot be implemented at the level of short-term CPU scheduling as there is no way to know the length of the next CPU burst.