--- title: "Multi-Level Feedback Queue" description: "Round-robin, priority queues, I/O, and aging boost" source: https://vizlearn.app/cs/os/mlfq-scheduling access: premium (interactive player requires Lifetime; this doc is free) --- # Multi-Level Feedback Queue The multi-level feedback queue (MLFQ) is a CPU scheduling policy that ranks processes by observed behavior instead of declared priority. Every job starts in the highest-priority queue, drops a level each time it burns a full time quantum, and returns to the top when it blocks for I/O — so the scheduler learns which jobs are interactive without being told. Picture a help desk with an express window. Everyone walks up to the express line first. If your problem takes longer than the clerk's patience, you get sent to a slower line with a more patient clerk. Step away to fetch a missing document and you rejoin the express line when you return — quick, cooperative visitors stay fast. And every twelve minutes the manager walks the slow lines back to the front so nobody is forgotten. That desk is MLFQ, and this lesson runs it head-to-head against plain Round Robin on the same four-process workload, so you can watch the same jobs produce two different schedules. ## How Multi-Level Feedback Queue Works The player opens in MLFQ mode: the single ready shelf is split into three queues — Q0 with a 2-tick quantum, Q1 with 4, Q2 with 8 — and the scheduler always runs the head of the highest non-empty one. The rules, exactly as this model runs them: 1. Always run the head of the highest non-empty queue. Shorter quantum up top, longer below. 2. New arrivals enter Q0. 3. A job that consumes its full quantum and still has CPU work is demoted one level. Using the whole slice is the tell of a CPU-bound job. 4. A job that blocks for I/O before its quantum runs out is not demoted; when the I/O completes, this simplified model returns it to Q0. Yielding the CPU is the tell of an interactive job. 5. If a higher-priority job becomes ready while a lower-priority one is running, the runner is preempted and goes back to the tail of its own queue. 6. Every 12 ticks a priority boost lifts every *ready* job in Q1 and Q2 back to Q0. The currently running job is not lifted — though the freshly boosted crowd usually preempts it a beat later. Switch the policy to Round Robin for the baseline MLFQ is built on: one FIFO ready queue, a fixed quantum of 3 ticks. New work joins the tail, the head gets the CPU, and a job whose quantum expires with CPU work left rotates back to the tail. Round Robin is MLFQ with exactly one queue — the control case that isolates what the feedback machinery actually buys. One more contract worth knowing, because it decides ties: when several things land on the same clock tick, the trace resolves arrivals first, then I/O completions, then the boost — and only then applies preemption or requeue. Same-tick arrivals therefore line up ahead of a job whose quantum just expired. ## Multi-Level Feedback Queue Step by Step The workload: P1 arrives at t=0 needing 5 CPU ticks, then 4 ticks of I/O, then 3 more CPU. P2 arrives at t=1 with a single 4-tick burst. P3 arrives at t=2 with 2 CPU, 3 I/O, 4 CPU. P4 arrives at t=4 with one 3-tick burst. **MLFQ, quanta 2/4/8, boost every 12** — the default run. The opening is a parade of demotions: P1 runs 0–2, burns its Q0 quantum, and drops to Q1 — P3, arriving exactly at t=2, slots into Q0 ahead of it. P2 runs 2–4, demoted. P3 runs 4–6, but it *finishes* its 2-tick burst rather than expiring, so it leaves for I/O (until t=9) with its reputation intact. P4 runs 6–8, demoted. Q0 is now empty, so P1 finally runs from Q1 at t=8 — for exactly one tick. P3's I/O completes at t=9, re-enters Q0, and preempts P1 straight back to Q1's tail. The express window opens and the slow line waits. P3 runs 9–11, burns a full Q0 quantum this time, and is demoted like everyone else. P2 gets one Q1 tick at 11–12 before the boost fires at t=12: P4, P1, and P3 — all parked in Q1 — lift back to Q0, and P2, running but unlifted, is preempted into Q1. Then Q0 drains in arrival order: P4 runs 12–13 and completes (turnaround 9), P1 runs 13–15 — its burst ends exactly as the quantum does, so it goes to I/O rather than down a level — P3 runs 15–17 and completes (turnaround 15). P2 finally finishes 17–18 from Q1 (turnaround 17). The CPU sits idle 18–19 while P1's I/O drains, then P1 runs 19–21 from Q0, demotes once more, and finishes 21–22 from Q1. Turnaround 22, finish line t=22. **Round Robin, quantum 3** — toggle the policy to compare. P1 runs t=0–3 while P2 and P3 arrive and queue behind it. When P1's quantum expires at t=3, the queue already reads P2, P3, P1 — same-tick arrivals go in ahead of the requeued job. P2 runs 3–6 (P4 arrives at t=4) and expires with one tick left. P3 runs 6–8, finishes its first burst, and leaves for I/O until t=11. P1 runs 8–10, completes its 5-tick burst, and blocks on I/O until t=14. P4 runs 10–13 and completes — P3 rejoins the queue mid-slice at t=11. P2 runs 13–14 and completes; P1's I/O finishes at the same tick. From there the survivors alternate: P3 runs 14–17 and expires one tick short, P1 runs 17–20 and completes, P3 mops up 20–21. The CPU is never idle; the schedule ends at t=21. Turnarounds: P1 = 20, P2 = 13, P3 = 19, P4 = 9. Response times: 0, 2, 4, 6. On screen, each process keeps one identity color from arrival to the done lane; the card the current beat is about wears a halo ring while bystanders fade back. The CPU slot shows a quantum meter draining in real time, demotions physically drop a card one shelf, the t=12 boost lifts three cards at once, and the Gantt ribbon at the bottom records every slice — windowed to recent ticks during playback, then shown in full on the final beat next to the metrics table. ## Why MLFQ Doesn't Need to Know Burst Times With all jobs available together and known bursts, shortest-first order minimizes average turnaround; staggered arrivals need a more careful claim. In practice, future CPU-burst lengths must be estimated. MLFQ's answer is to price CPU time and read the receipts. Burn a full quantum, you pay with a demotion; yield for I/O, you keep your spot at the express window. Recent behavior becomes a working estimate of the next burst, no clairvoyance required. The two runs above are the experiment. Response times go from 0, 2, 4, 6 under Round Robin to 0, 1, 2, 2 under MLFQ — the short Q0 quantum means every newcomer touches the CPU almost immediately. The bill lands on the CPU-hungry job: P1's turnaround grows from 20 to 22, because the changed priorities, preemptions, and I/O timing delay its completion. P1 is demoted twice in this trace, not after every interruption. And the t=12 boost is the confession that learned priorities can be wrong forever: without periodic amnesty, a demoted job behind a stream of interactive ones could starve indefinitely. After watching, you should be able to defend this sentence: MLFQ buys interactive response time by taxing whoever spent CPU recently, and the boost caps how long that tax can compound. ## Edge Cases - **Burst ends exactly at the quantum boundary.** Completion outranks expiry: P1 at t=15 has both its burst and its Q0 quantum hit zero, and it goes to I/O instead of down a level. P4 completes at t=13 before using its full Q0 quantum, so it also leaves rather than requeues. - **Same-tick arrival vs. expiry.** Arrivals are admitted before the expired job is requeued — P3 lands in Q0 ahead of P1 at t=2 in MLFQ, and the Round Robin queue reads P2, P3, P1 at t=3. - **The boost skips the running job.** At t=12, P2 holds the CPU in Q1 and gets no lift; it is preempted by the boosted Q0 crowd and resumes from Q1 five ticks later. - **Idle is a real schedule entry.** From t=18 to 19 nothing is runnable while P1's I/O drains; the Gantt shows an IDLE block and the clock jumps to the next event rather than ticking through nothing. ## Common Mistakes - Reading the Gantt chart as the policy. The ribbon is the *output*; the policy is the rule that chose each next slice, which is why the animation spends its beats on decisions, not on the ribbon. - Thinking I/O gets a job demoted. It is the opposite: blocking before the quantum expires is exactly how a job avoids demotion. That asymmetry is the whole feedback mechanism. - Expecting MLFQ to win on every metric. It sharpened response times here while making P1's turnaround worse and finishing the whole workload a tick later than Round Robin. Schedulers trade; they do not dominate. - Forgetting preemption. Reaching the head of a queue guarantees nothing — P1 at t=9 ran one tick before higher-priority work took the CPU back. - Treating queue levels as judgments about a process. They are guesses from recent behavior, and the boost exists because guesses go stale. ## A Note on Simplification The model isolates one question: which runnable process gets the CPU next, and why? To keep that question visible it uses one CPU, integer ticks, fixed bursts, I/O always returning to Q0, and no context-switch cost, interrupt latency, locks, affinity, niceness, or production fairness accounting. Real schedulers add all of that on top. The feedback idea is still the same: price recent CPU use, reward blocking for I/O, and periodically forgive stale guesses.