Shortest-Job-First ( SJF )

The shortest job first algorithm associates the length of the next CPU burst with each process. The CPU time is assigned to a process with the smallest next CPU burst time.

If there are two processes with the same next CPU burst time, then FCFS algorithm is applied to them. Consider an example, where the following processes arrived with CPU burst times.

ProcessCPU Burst
p16
p28
p37
p43

Now we schedule the process according to smallest next CPU burst time. The new process order is in the following figure.

Gantt Chart for Shortest Job First ( SJF )
Gantt Chart for Shortest Job First ( SJF )

The p4 has waiting time = 0 ms
The p1 has waiting time = 0 + 3 = 3 ms
The p3 has waiting time = 0 + 3 + 7 = 10 ms
The p2 has waiting time = 0 + 3 + 7 + 16 = 26 ms

The average waiting time = (0 + 3 + 10 + 26)/4 = 39/4 = 9.75 ms

Comparison with FCFS

The average waiting time for FCFS would be more than SJF.

Gantt Chart for FCFS comparing Average Waiting Time with SJF
Gantt Chart for FCFS comparing Average Waiting Time with SJF

Average waiting time using FCFS = (0 + 6 + 14 + 21) = 41/4 = 10.25 ms

The SJF reduces the average waiting time of processes, it is hard to predict the next CPU burst time. But it can be implemented at the long-term scheduler lever where users can submit the process time limit while submitting the job. The CPU scheduler can predict an approximate value of the next CPU burst from the length of previous processes.

References

  • Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
  • Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
Skip to content