SJF left us hanging: B and C arrive just after A starts, and politely wait 90 seconds anyway. The fix needs the machinery from chapter 6 — the timer interrupt and context switch — plus the will to use it.
7.5 Shortest Time-to-Completion First (STCF)
Relax assumption 3 (run to completion). When a new job enters the system, the STCF stcf Shortest Time-to-Completion First (preemptive SJF) — on each arrival, run whichever job has least time left. defined in ch. 7 — open in glossary scheduler (a.k.a. Preemptive Shortest Job First) determines which of the remaining jobs — new job included — has the least time left, and runs that one:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 100 | 120 | 0 |
| B | 10 | 10 | 10 | 0 |
| C | 10 | 10 | 20 | 10 |
| average | 50.00 | 3.33 | ||
When B and C arrive at t=10, STCF compares time-remaining (A: 90, B: 10, C: 10) and preempts A. Average turnaround: (120 + 10 + 20)/3 = 50 — flip back to SJF to see 103.33 again.
Average turnaround: 50 seconds, down from SJF’s 103.33. And as before, under the current assumptions, STCF is provably optimal — if SJF is optimal when everyone arrives together, preempting for shorter arrivals is the natural extension.
7.6 A New Metric: Response Time
If jobs’ lengths were known and the CPU were all that mattered, STCF would be the answer — and for early batch systems, it nearly was. Then came time sharing: users at terminals, demanding interactivity. A new metric was born — response time response time T_firstrun − T_arrival — the interactivity metric born with time sharing. defined in ch. 7 — open in glossary , the time from arrival to first being scheduled:
(The book’s definition is the best case — it assumes the job produces a response the instant it starts.) For Figure 7.5’s schedule: A responds at 0, B at 0, C at 10 — average 3.33. Not bad. But make three jobs arrive together and STCF-family schedulers turn ugly: the third job waits for the entirety of the first two. Imagine typing at a terminal and waiting 10 seconds for a keystroke to echo because someone else got scheduled first.
7.7 Round Robin
Enter Round-Robin round robin Run each job for a time slice, then switch to the next in the queue — great response time, nearly pessimal turnaround. defined in ch. 7 — open in glossary (RR): run a job for a time slice time slice The quantum a job runs before round robin switches (a multiple of the timer-interrupt period). defined in ch. 7 — open in glossary (the scheduling quantum — a multiple of the timer-interrupt period), then switch to the next job in the run queue, cycling until all are done. “Time-slicing.” Fight it out:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 5 | 5 | 0 |
| B | 0 | 5 | 10 | 5 |
| C | 0 | 5 | 15 | 10 |
| average | 10.00 | 5.00 | ||
SJF: response times 0, 5, 10 (avg 5) — C stares at a frozen terminal for 10 seconds. Switch to RR (quantum 1): responses 0, 1, 2 (avg 1) — but turnaround jumps from 10 to 14. Now raise the quantum and watch response degrade back toward SJF.
The numbers tell the whole story of this chapter:
- Response: RR (quantum 1) averages 1; SJF averages 5. RR wins interactivity, hands down.
- Turnaround: RR averages 14; SJF averages 10. RR is, in the book’s phrase, nearly pessimal — often worse than plain FIFO — because it deliberately stretches every job as long as possible, finishing nothing early. Turnaround only cares about finishing.
That’s an inherent trade-off, not an engineering failure: any fair policy that divides the CPU evenly on small timescales must do poorly on turnaround; be unfair (run short jobs to completion) and response time pays instead. You can’t have your cake and eat it too.
Tip: Amortization can reduce costs
The quantum length is RR’s critical knob. Shorter = more responsive — but each switch costs. With a 1 ms context-switch cost and a 10 ms slice, ~10% of all time is switching overhead; stretch the slice to 100 ms and overhead falls under 1%. That is amortization amortization Reducing a fixed cost by incurring it less often — e.g., longer time slices dilute context-switch overhead. defined in ch. 7 — open in glossary : incur the fixed cost less often. Pick a slice long enough to amortize switching, short enough to stay responsive. (And the true switch cost isn’t just registers: programs build up state in CPU caches, TLBs, and branch predictors — all flushed and refilled on a switch.)7.8 Incorporating I/O
Relax assumption 4 — all real programs do I/O (a program with no input always produces the same output; one with no output is the tree falling in the forest). When a running job issues an I/O it becomes blocked (chapter 4’s third state), so the scheduler should run someone else; and when the I/O completes, an interrupt raises another decision.
Example: A and B each need 50 ms of CPU, but A issues a disk I/O (10 ms) after every 10 ms of computing, while B just computes. Treating A as one 50-ms lump wastes the machine:
Figure 7.8: no overlap. A’s five bursts each strand the CPU for 10 ms; B waits for all of it.
The common approach: treat each 10-ms CPU burst as an independent sub-job. Then STCF’s choice is natural — a 10-ms burst of A beats 50-ms B; when A blocks, B runs; when A’s I/O completes, its next burst preempts B again:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 50 | 90 | 0 |
| B | 0 | 50 | 100 | 10 |
| average | 95.00 | 5.00 | ||
A's 10ms bursts always beat B's big remaining chunk, so A runs, blocks on the disk, and B fills the gap — every gap. Everything finishes by t=100 instead of 140, because CPU and disk work concurrently.
Overlap is the win: the CPU computes for one process while the disk serves another (a tip the book generalizes: overlap operations whenever possible — disk I/O, remote messages — and utilization rises). Treating bursts as jobs also means “interactive” processes run frequently, while CPU-hungry ones soak up the leftovers.
7.9 No More Oracle
One assumption stands: that the scheduler knows each job’s length — the worst assumption of all. In a general-purpose OS the kernel knows almost nothing about the future. So: how to build a scheduler that behaves like SJF/STCF without a priori knowledge, and folds in RR’s response-time goodness?
7.10 Summary
Two scheduler families: run-the-shortest-remaining (SJF/STCF — optimal turnaround, terrible response) and alternate-everyone (RR — great response, nearly-pessimal turnaround); each is bad exactly where the other is good, plus a workable way to fold in I/O. The missing piece — seeing the future — turns out to have a beautiful answer: use the recent past to predict it. That scheduler, the multi-level feedback queue, is the next chapter.
Homework: scheduler.py
This chapter’s simulator runs FIFO, SJF, and RR over job lists and reports response, turnaround, and wait times — the same experiments as this page’s widgets, plus questions worth doing by hand first: when does SJF tie FIFO on turnaround? When does SJF tie RR on response? What’s RR’s worst-case response time for N jobs and quantum q? Get it at ostep-homework.Check yourself
1.B (10s) arrives at t=10 while A (90s remaining) is running. What does STCF do that SJF cannot?
2.Three 5-second jobs arrive together. Under SJF, what is C's response time — and why did time-sharing systems care?
3.With a 1 ms context-switch cost, why not set RR's quantum to 1 ms for the best possible response time?
4.Why is RR called 'nearly pessimal' for turnaround — often worse than plain FIFO?
5.In Figure 7.9, A (10 ms bursts + 10 ms I/Os) and B (50 ms pure CPU) both finish by t=100 instead of 140. What made the difference?