Multi-Level Feedback Queue

Intuition

A scheduler answers one concrete question again and again: when the CPU is free, which runnable process should run next? The answer is not just about speed. A desktop should feel responsive when an interactive job wakes up from I/O. A batch job should still make progress. A fair policy should avoid letting one long CPU burst monopolize the machine.

This lesson visualizes that question with a small fixed workload. Process cards move between the ready queue, the CPU, I/O wait, and the completed lane. CPU and I/O can progress during the same clock interval, so the lesson shows I/O countdown beats while another process runs. The Gantt ribbon at the bottom records the execution history, but the main teaching surface is the decision itself: what is ready, what policy rule applies, and why the chosen process moves next.

How It Works

Round Robin uses one FIFO ready queue. When a process arrives, it joins the tail. The scheduler dispatches the head. The process runs until either its CPU burst finishes or its quantum expires. If the quantum expires and the process still has CPU work left, it rotates to the tail. This gives every ready process repeated chances to run.

MLFQ, or multilevel feedback queue, uses several ready queues. In this lesson, Q0 has the shortest quantum and highest priority. Q1 and Q2 run later but receive longer quanta. A process that uses an entire quantum looks CPU-bound, so it moves down. A process that blocks for I/O looks interactive, so this simplified model returns it to Q0 when I/O completes. A periodic boost lifts waiting jobs back to Q0 so low-priority work cannot starve forever.

Step By Step

The default workload contains four processes. P1 arrives at tick 0 with CPU, then I/O, then more CPU. P2 arrives at tick 1 with one CPU burst. P3 arrives at tick 2, later blocks for I/O, then returns. P4 arrives at tick 4.

With Round Robin and quantum 3, P1 starts first. When P2 and P3 arrive, they join the ready queue but do not interrupt P1. When P1 uses its quantum and still has CPU left, it rotates to the tail. The Gantt ribbon shows short slices alternating between processes. If a process finishes a CPU burst and has I/O next, it leaves the CPU and waits. While another process runs, that waiting card keeps counting down in the I/O lane; when I/O completes, it re-enters the ready queue.

Switch to MLFQ and the same workload teaches a different rule. New work starts in Q0. Jobs that consume a full Q0 quantum move down to Q1. Interactive jobs that block for I/O return to Q0, so they can be dispatched quickly when they become runnable again. The visual contrast is the point: Round Robin treats all ready work as one line, while MLFQ uses recent behavior as a priority signal. On the final beat, the metrics table summarizes wait time, turnaround time, and response time so the policy tradeoff is visible instead of hidden in the Gantt chart.

Complexity

For this teaching trace, every event is generated once and queue operations are treated as constant time. If E is the number of arrivals, I/O completions, boosts, and scheduling decisions, and S is the number of CPU slices, the trace is O(E + S). A production kernel has many additional costs: timer interrupts, accounting, runqueue data structures, CPU affinity, locks, and multi-core coordination.

Edge Cases

A CPU burst can end exactly when the quantum expires. The lesson treats burst completion as the more important event: the process either starts I/O or completes instead of being requeued as unfinished work.

The CPU can be idle even when work exists in the future. If no process is ready but a future arrival or I/O completion is pending, the Gantt ribbon shows an IDLE block and the clock jumps to the next event.

In MLFQ, a boost can change the next dispatch decision. The lesson shows the boost as its own beat because starvation prevention is not a side effect; it is part of the policy.

Common Mistakes

Do not read the Gantt chart as the policy. The Gantt chart is the result. The policy is the rule that produced the next slice.

Do not assume Round Robin improves total completion time. It improves fairness and responsiveness under a fixed quantum, but context switching and workload shape matter.

Do not treat MLFQ priorities as moral judgments about processes. They are guesses based on recent behavior: used the full quantum means probably CPU-bound; blocked for I/O means probably interactive.

A Note on Simplification

This is an explainer, not a kernel implementation. It uses one CPU, integer ticks, fixed bursts, and no real interrupt latency, context-switch overhead, locks, CPU affinity, priority inheritance, niceness, cgroups, or production fairness accounting. Real operating systems combine scheduler policy with hardware timers, per-core runqueues, workload history, and many safety constraints. The simplified model is useful because it isolates the core decision: which runnable process gets the CPU next, and why.