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.
Gantt Chart for SJF
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.
| Process | CPU Burst |
| p1 | 6 |
| p2 | 8 |
| p3 | 7 |
| p4 | 3 |
Now we schedule the process according to smallest next CPU burst time. The new process order is in the following figure.
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.
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.
