Shortest Remaining Time First
Chapter Forty-Nine
Syllabus topic Module 1, "CPU Scheduling - Scheduling Algorithms (... SRTF ...)"
Pages 194 to 196 of 452
In one line
Whenever a process arrives whose burst is shorter than what the running process has left, the running process is thrown off and the new one runs.
The rule
| Chooses | the ready process with the smallest remaining time |
| Preemptive | yes |
| Decision points | every arrival, and every completion |
| Ties | the running process keeps the processor, so that no switch happens for nothing |
| Also called | preemptive shortest job first |
| Starvation | possible, and worse than in Chapter forty eight |
The word is REMAINING, and that is the whole difference from Chapter forty eight. A process that has already run for 6 of its 8 units has 2 left, and it is compared on 2, not on 8. Comparing on the original burst is the commonest error in a hand worked answer.
Worked in full
Schedule: shortest remaining time first
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
| Slice | Process | From | To |
|---|---|---|---|
| 1 | P1 | 0 | 1 |
| 2 | P2 | 1 | 5 |
| 3 | P4 | 5 | 10 |
| 4 | P1 | 10 | 17 |
| 5 | P3 | 17 | 26 |
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 17 | 17 | 9 |
| P2 | 5 | 4 | 0 |
| P3 | 26 | 24 | 15 |
| P4 | 10 | 7 | 2 |
Average turnaround time: 52 / 4 = 13
Average waiting time: 26 / 4 = 6.50
Context switches: 4
Non-preemptive shortest job first on the same problem gives an average waiting time of 7.75, so preemption bought 1.25 units per process.
The decision at every instant, written out
This is the part to be able to reproduce, because it is what the marks are for.
| Time | What happened | Ready, with time remaining | Chosen | Why |
|---|---|---|---|---|
| 0 | P1 arrives | P1 has 8 | P1 | it is the only one |
| 1 | P2 arrives with 4 | P1 has 7, P2 has 4 | P2 | 4 is less than 7, so P1 is preempted |
| 2 | P3 arrives with 9 | P2 has 3, P1 has 7, P3 has 9 | P2 | 3 is still the smallest |
| 3 | P4 arrives with 5 | P2 has 2, P1 has 7, P3 has 9, P4 has 5 | P2 | 2 is still the smallest |
| 5 | P2 finishes | P1 has 7, P3 has 9, P4 has 5 | P4 | 5 is the smallest |
| 10 | P4 finishes | P1 has 7, P3 has 9 | P1 | 7 is less than 9 |
| 17 | P1 finishes | P3 has 9 | P3 | it is the only one left |
Only two things ever cause a decision: an arrival, or a completion. Nothing happens between them, so a chart of twenty units may have only five decision points, and looking only at those is what makes the method quick.
At time 2 and time 3 the arriving process did not preempt, because the running process had less left than the newcomer's whole burst. A student who preempts at every arrival gets a different and wrong chart.
Shortest Remaining Time First
Where the extra context switches come from
Compare the two shortest job algorithms on this problem.
| Shortest job first | Shortest remaining time first | |
|---|---|---|
| Average waiting | 7.75 | 6.50 |
| Average turnaround | 14.25 | 13 |
| Context switches | 3 | 4 |
Preemption bought better waiting times and cost one more switch. On a real machine that trade has to be priced with Chapter forty four's arithmetic: four switches at five microseconds is twenty microseconds, against a saving of 1.25 time units per process, and whether that is worth it depends entirely on what a time unit is.
Starvation, and why it is worse here
Chapter forty eight could starve a long process only when shorter ones kept arriving while the processor was free. Here a long process can be thrown off while it is running, over and over, and it makes no progress at all between preemptions.
P3 in the worked example waited fifteen units to do nine units of work, and it was the longest process. With a steady stream of short arrivals it would never have run.
Distinctions that carry marks
| Shortest job first | Shortest remaining time first | |
|---|---|---|
| Preemptive | no | yes |
| Compares | the whole next burst | the remaining time |
| Decides at | completions only | arrivals and completions |
| Average waiting | good | better, and optimal among preemptive algorithms |
| Switches | fewer | more |
| Starvation | possible | possible, and worse |
What it does not mean
It is not a different algorithm from shortest job first. It is the same rule applied at more moments, which is why the pair is often written as the non-preemptive and preemptive forms of one algorithm.
Preemption does not happen at every arrival. Only when the arriving process's burst is shorter than what the running one has left.
The remaining time is not recomputed by the process. The scheduler knows it: the burst it was predicted to need, minus what it has had.
Quick revision
- Shortest remaining time first is preemptive shortest job first: at every arrival and every
completion, run the ready process with the least remaining time.
- Compare on remaining time, not the original burst.
- A decision is needed only at an arrival or a completion.
- An arriving process preempts only if its burst is less than the running process's remaining
time; a tie leaves the running process alone.
- On the worked problem it gave an average waiting time of 6.50 against 7.75 for the
non-preemptive form, at the cost of one more context switch.
- Starvation is worse than in the non-preemptive form, because a long process can be thrown off
while running.
Test yourself
- State the rule. At every arrival and every completion, give the processor to the ready
Shortest Remaining Time First
process with the smallest remaining execution time, preempting the running process if necessary.
- What is compared, and what is the common mistake? The remaining time. The mistake is to
compare the original burst lengths and so to preempt or not preempt wrongly.
- When does an arriving process preempt the running one? Only when its burst is shorter than
the time the running process has left.
- How many decision points does a schedule have? One per arrival and one per completion, and
no others. 5. P1 arrives at 0 with 8, P2 at 1 with 4, P3 at 2 with 9, P4 at 3 with 5. Give the order of the slices. P1 from 0 to 1, P2 from 1 to 5, P4 from 5 to 10, P1 from 10 to 17, P3 from 17 to 26.
- Why is starvation worse here than under the non-preemptive form? A long process can be
taken off the processor part way through, over and over, so it makes no progress at all rather than merely waiting to start.
- What does preemption cost? More context switches: four rather than three on the worked
problem, each one pure overhead.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.