Chapter 7 ended with an impossible-sounding demand: SJF-like turnaround and RR-like response, with zero advance knowledge of job lengths. The answer is one of the most famous schedulers ever built — the Multi-Level Feedback Queue mlfq Multi-Level Feedback Queue — priority queues + observed behavior: assume every job short, demote CPU-grinders, boost everyone periodically; approximates SJF without an oracle. defined in ch. 8 — open in glossary , first described by Corbató et al. in 1962 for the Compatible Time-Sharing System (CTSS); that work (plus Multics) earned Corbató the Turing Award, and refined MLFQs run inside BSD derivatives, Solaris, and Windows to this day.
The Crux: How To Schedule Without Perfect Knowledge?
How can we design a scheduler that minimizes response time for interactive jobs while also minimizing turnaround time, without a priori knowledge of job length?Tip: Learn from history
MLFQ is a system that uses the past to predict the future — like hardware branch predictors and caching algorithms. Such approaches work when behavior has phases and is therefore predictable; but beware — learned predictions can be wrong, and drive a system to decisions worse than knowing nothing at all.8.1 MLFQ: Basic Rules
MLFQ keeps a number of distinct queues, each with a priority level; a ready job sits on exactly one of them. Higher queue runs first; ties share via round robin:
THE RULES SO FAR
- Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
- Rule 2: If Priority(A) = Priority(B), A & B run in round robin.
The heart of MLFQ is that priority is not fixed — it varies with observed behavior. Relinquish the CPU constantly while waiting for keyboard input? You look interactive; priority stays high. Grind the CPU for long stretches? Priority sinks. History becomes prediction:
Figure 8.1: a snapshot of the queues. The static picture is exactly what MLFQ is not about — everything interesting is in how jobs move between queues over time.
8.2 Attempt #1: How To Change Priority
Remember the workload mix: short interactive jobs that relinquish the CPU often, and long CPU-bound jobs where response time doesn’t matter. First attempt at priority adjustment:
ATTEMPT #1
- Rule 3: When a job enters the system, it is placed at the highest priority (topmost queue).
- Rule 4a: If a job uses up an entire time slice while running, its priority is reduced (down one queue).
- Rule 4b: If a job gives up the CPU before the slice is up, it stays at the same level.
Example 1 — a single long-running job descends and settles:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 200 | 200 | 0 |
| average | 200.00 | 0.00 | ||
The job enters at the top (Q2), burns a full 10 ms slice there (Rule 4a: demoted), another at Q1, and settles at Q0 for the rest of its 200 ms. A CPU-grinder proves itself long, and sinks.
Example 2 — along came a short job. Here is the SJF approximation in action. Since MLFQ can’t know whether a job is short, it assumes it might be (top priority on entry). Truly short jobs finish before sinking; long ones prove themselves long and drift down:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 180 | 200 | 0 |
| B | 100 | 20 | 20 | 0 |
| average | 110.00 | 0.00 | ||
A has sunk to Q0 by the time B arrives at t=100. B enters at Q2 (Rule 3), instantly preempts A (Rule 1), and — being only 20 ms — completes within two slices, never reaching the bottom. A then resumes. Try making B longer: it stops being "short" and sinks like A did.
Example 3 — what about I/O? Rule 4b’s purpose: an interactive job doing constant I/O (keyboard, mouse) gives up the CPU early, and is not penalized:
| job | arrival | runtime | turnaround | response |
|---|---|---|---|---|
| A | 0 | 160 | 177 | 0 |
| B | 0 | 18 | 181 | 10 |
| average | 179.00 | 5.00 | ||
B computes 1 ms, issues an I/O, and repeats — always releasing the CPU before its slice expires, so Rule 4b keeps it at Q2 forever. A grinds away at Q0 during every one of B's I/Os. Interactive feel for B, progress for A.
Problems with our current MLFQ
It looks good — long jobs share the CPU, short and I/O-bound jobs run promptly. But attempt #1 has serious flaws (the book invites you to think deviously first):
- Starvation starvation A job receiving no CPU time at all because others perpetually outrank it — the failure mode the priority boost prevents. defined in ch. 8 — open in glossary : with “too many” interactive jobs at the top, long-running jobs at the bottom get zero CPU. They starve.
- Gaming the scheduler gaming Tricking the scheduler into more than a fair share — e.g., issuing a throwaway I/O at 99% of the slice to stay high-priority. defined in ch. 8 — open in glossary : run for 99% of your slice, then issue a throwaway I/O. Rule 4b keeps you at top priority with ~99% of the CPU — a near-monopoly, by design(!).
- Behavior change: a CPU-bound job that becomes interactive is stranded at the bottom; nothing in the rules lets it climb back up.
Tip: Scheduling must be secure from attack
A scheduling policy might not look like a security concern — but in a modern datacenter, where strangers share CPUs, memory, networks, and storage, a policy that can be gamed lets one user harm everyone else. Scheduling policy is part of a system’s security, and must be built accordingly. (The next section’s fixes are exactly that.)Two fixes coming: a periodic priority boost for starvation and phase changes, and honest accounting for the gamers.
Check yourself
1.MLFQ must deliver SJF-like turnaround without knowing job lengths. What replaces the missing oracle?
2.In Figure 8.3, B (20 ms) arrives at t=100 while A grinds at Q0. Why does B run immediately, and why does it never reach Q0?
3.What is Rule 4b's intent — and its dark side?
4.Predict: ten I/O-happy interactive jobs churn at Q2 indefinitely. What happens to a long-running job at Q0 under attempt #1?