Shortest Remaining Time First (SRTF) scheduling, explained

Shortest Remaining Time First works like SJF, with one difference: it can interrupt the running process. Whenever a new process arrives, the scheduler compares the new burst time with the time the running process still has left.

If the newcomer needs less, it takes the CPU straight away. This is called preemption.

How it works

• At every arrival, look at all waiting processes and the one that is running.
• Pick the process with the least time left. Ties go to the earlier arrival, and a tie never makes the running process switch.
• Run it until it finishes or until the next process arrives, whichever comes first.
• Then choose again.

A small example

Four processes, A to D:

Arrival times: 0 2 4 5
Burst times:   7 4 1 4

With SRTF, A starts, but B arrives at time 2 and needs less than what A has left, so B takes over. C then takes over from B, and so on. The average waiting time is:

3.0 time units

This is lower than FCFS (4.75) and SJF (4.0) on the same processes.

What to know about its cost

• It gives the lowest possible average waiting time for this kind of problem.
• It switches between processes more often, which costs time in a real system.
• It still needs to know the burst times.

Where it works well

• Excellent average waiting time.
• Short jobs are served very quickly, even when they arrive late.

Where it struggles

• Long processes can starve.
• More context switches than non-preemptive algorithms.

Try it yourself

Open the CPU Scheduling experiment, enter the processes from this post, choose Shortest Remaining Time First and step through the Gantt chart. Watch for the moments when the running process is interrupted. Then try the other algorithms on the same processes and compare the averages.

Open the CPU Scheduling experiment