CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 5 of 7 · 2 min read

SRTF

In plain words: A teller with a thirty-minute customer would stop when a one-minute customer walks up, serve the short one and then resume. The analogy stops in one place: a teller loses little by stopping, while a process loses its cached data (Level 1, page 5).

Shortest remaining time first is the preemptive form of SJF. Whenever a process arrives, the scheduler compares the new process's burst with the remaining time of the running one. If the new one is shorter, it takes the processor.

Trace the page 1 workload:

  • Time 0 to 1: A runs (the only process). A has 4 units left.
  • Time 1: B arrives with 3 units, less than A's 4. B preempts A. B runs from 1 to 4.
  • Time 3: D arrives with 2 units. B has 1 unit left, so B continues.
  • Time 4: B ends. Ready: A (4 left), C (8), D (2). D runs from 4 to 6.
  • Time 6: A (4) beats C (8). A runs from 6 to 10.
  • Time 10: C runs from 10 to 18.
time:  0 1    4   6       10        18
       |A| B  | D |   A   |    C    |
Process Finish Turnaround Waiting Response
A 10 10 5 0
B 4 3 0 0
C 18 16 8 8
D 6 3 1 1

The averages are turnaround 32 ÷ 4 = 8.00, waiting 14 ÷ 4 = 3.50 and response 9 ÷ 4 = 2.25. This is the best of the three on all measures, as the table of section 5 shows. The price is that A was interrupted, so its waiting time (5) now differs from its response time (0), and the policy needs a timer decision at every arrival.

Shortest remaining time first

Shortest remaining time first (SRTF) is the preemptive form of shortest job first: whenever a process arrives, the processor goes to the process, running or ready, with the least CPU time still to run.

Example: when B arrives at time 1 with 3 units against A's remaining 4, B takes the processor at once.

Check yourself: 1. Why did B not preempt at time 3, when D arrived? 2. What is the response time of A, and why is it 0 although A waited 5? 3. When does SRTF behave exactly like SJF?