The shortest job first (SJF) algorithm is preemptive or non-preemptive. You have learned about the non-preemptive SJF in the previous article. In this article, you will learn about preemptive SJF, also called the shortest remaining time first scheduling algorithm.
Preemptive SJF
A new process arrives at the ready queue while an old process is executing in the CPU. The new process may have a smaller CPU burst than the remaining burst time of the old process.
A preemptive SJF algorithm will preempt the old process and allow the new process to run. However, the non-preemptive process will continue with the old process until it releases the CPU.
Example:
Consider following processes scheduled according to preemptive SJF:
| Process | Arrival Time | Burst Time |
| p1 | 0 | 8 |
| p2 | 1 | 4 |
| p3 | 2 | 9 |
| p4 | 3 | 5 |
The new process order of execution is given in following figure:
Waiting time for each process = Service Time - Arrival TimeTherefore,
Waiting time for p1 = 10 – 1 = 9
Waiting time for p2 = 1 – 1 = 0
Waiting time for p3 = 17 – 2 = 15
Waiting time for p4 = 5 – 3 = 2
Average Waiting Time = (9 + 0 + 15 + 2)/4 = 26/4 = 6.5 milliseconds.
If we schedule according to non-preemptive scheduling of the same set of processes then:
Average Waiting Time = 7.75 milliseconds.
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.