CPU Scheduling-Shortest Remaining Time First

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.

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:

Gantt Chart for Preemptive SJF (SRTF)
Gantt Chart for Preemptive SJF (SRTF)
Waiting time for each process = Service Time - Arrival Time

Therefore,

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.


Skip to content