Multilevel Feedback Queue Scheduling

A Multilevel Feedback Queue scheduler maintains $k$ priority levels $Q_0, Q_1, \dots, Q_{k-1}$, where $Q_0$ is the highest priority. Each queue level is scheduled internally by Round-Robin (or sometimes FCFS at the lowest level), and each level $i$ has an associated time quantum $q_i$, typically increasing with depth: $q_0 < q_1 < \cdots < q_{k-1}$. The scheduler always runs a process from the highest non-empty queue; a process in $Q_i$ only runs if all queues $Q_0, \ldots, Q_{i-1}$ are empty. What distinguishes MLFQ from ordinary multilevel queue scheduling (which assigns a process to a fixed queue for its lifetime, e.g., by process type) is the feedback: a process's queue assignment changes dynamically based on its observed CPU usage pattern. This is the crucial adaptive ingredient. The two canonical feedback rules are:

• Demotion on quantum exhaustion. If a process uses its entire time quantum $q_i$ without voluntarily blocking (i.e., it is CPU-bound behavior for now), it is demoted to $Q_{i+1}$ (or stays at $Q_{k-1}$ if already at the bottom).
• Retention/promotion on voluntary yield. If a process blocks for I/O (or yields) before its quantum expires, it is treated as interactive and either kept at its current level or promoted back toward $Q_0$.

Because the rules only look at recent behavior, MLFQ never needs to know a process's total CPU burst length or future behavior — the very information that Shortest Job First scheduling requires but that real operating systems can never have in advance. This is the sense in which MLFQ learns process type through experience rather than being told it. The tradeoff is that naive demotion-only feedback is not fair on its own: it can starve long-running low-priority jobs and can be gamed by a process that deliberately gives up the CPU just before its quantum expires, remaining forever at high priority. The complete design therefore also requires a priority-boost / aging mechanism, discussed below, that periodically resets all processes to the top queue.

At the mechanism level, MLFQ scheduling is driven by a small set of rules that govern (1) which queue runs next, (2) how a process moves between queues, and (3) how starvation is prevented. A commonly cited formulation (used in OS courses to summarize the classic design, e.g. as popularized by Arpaci-Dusseau's OSTEP) states the rules as: ``` Rule 1: If Priority(A) > Priority(B), A runs (B waits). Rule 2: If Priority(A) == Priority(B), A and B run in round-robin within their shared queue. Rule 3: A new job enters at the topmost queue (highest priority). Rule 4: Once a job uses up its time quantum at a given level (regardless of how many times it has given up the CPU), its priority is reduced (it moves down one queue). Rule 5: After some time period S, move ALL jobs in the system to the topmost queue (priority boost / aging). ``` The pseudocode below implements this event-driven view precisely: the scheduler reacts to three kinds of events — a process being admitted, a process's quantum expiring, and a process blocking on I/O — plus a timer-driven periodic boost. ``` structure Process: pid queue_level // current priority level, 0 = highest remaining_quantum // time left in current dispatch last_boost_time initialize: queues[0..k-1] ← empty FIFO/round-robin lists quantum[i] ← base_quantum * growth_factor^i // e.g. 8, 16, 32, ... boost_period ← S on process ADMITTED(P): P.queue_level ← 0 P.remaining_quantum ← quantum[0] enqueue(queues[0], P) on SCHEDULE(): // called whenever CPU is free for i in 0 .. k-1: if queues[i] is not empty: P ← dequeue_front(queues[i]) dispatch(P, time_slice = P.remaining_quantum) return idle() on TIMER_EXPIRED(P): // P used its entire quantum if P.queue_level < k-1: P.queue_level ← P.queue_level + 1 // demote (Rule 4) P.remaining_quantum ← quantum[P.queue_level] enqueue(queues[P.queue_level], P) SCHEDULE() on PROCESS_BLOCKED(P, time_used): // P yields before quantum expires // Retained (or optionally promoted) — behavior-based inference: // it looks I/O-bound, so treat it kindly. P.remaining_quantum ← quantum[P.queue_level] enqueue(queues[P.queue_level], P) // re-enters at same level SCHEDULE() on IO_COMPLETE(P): enqueue(queues[P.queue_level], P) // returns to ready state SCHEDULE() on PERIODIC_BOOST_TIMER(): // fires every S time units for i in 1 .. k-1: for P in queues[i]: remove P from queues[i] P.queue_level ← 0 P.remaining_quantum ← quantum[0] enqueue(queues[0], P) SCHEDULE() ``` Two design knobs deserve attention. First, the quantum schedule $q_i$: making it grow (often doubling) with depth means that once the scheduler is fairly confident a job is CPU-bound (it has been demoted several times), it is given longer, less interrupted runs — reducing context-switch overhead for exactly the jobs that don't need fast response. Second, the boost period $S$: too small and CPU-bound jobs are constantly reset to the top, degrading into pure Round-Robin and defeating the purpose; too large and low-priority jobs can starve for unacceptably long stretches. $S$ must be tuned (or, in advanced variants, adapted) to the workload.

Time complexity of the dispatch decision. With $k$ priority levels each holding a ready queue, `SCHEDULE()` scans levels top-down until it finds a non-empty queue, so the dispatch step costs $O(k)$ in the worst case (or $O(1)$ if a bitmap of non-empty levels is maintained, since a single word can encode "which of the $k$ queues are non-empty" and the top set bit can be found in $O(1)$ on typical hardware, or $O(\log k)$ with a naive scan of set bits). Enqueue/dequeue within a level is $O(1)$ with a doubly-linked FIFO list. Demotion, promotion, and the periodic boost are each $O(1)$ per process touched, so a full boost over $n$ ready processes costs $O(n)$, performed only once every $S$ time units — amortized $O(n/S)$ per unit time, which is negligible for reasonable $S$.

Space complexity is $O(k + n)$: $O(k)$ for the queue headers/quanta table and $O(n)$ for the process control blocks distributed across queues — no extra bookkeeping beyond a queue pointer and a quantum counter per process.

Correctness (in the sense of "does it achieve its design goals") rests on three properties that must be argued separately, since MLFQ is a heuristic, not an exact optimization algorithm: 1. No process runs out of turn. By Rule 1/Rule 2, at every scheduling decision the process chosen belongs to a non-empty queue of maximal priority among non-empty queues, and ties are broken round-robin — this is a direct invariant of the `SCHEDULE()` loop scanning from level 0 upward and dispatching the first hit, so strict priority ordering across levels holds by construction. 2. Convergence toward SJF-like behavior. Consider a mostly-CPU-bound job with total burst length $B \gg q_0$. Each time it runs, it exhausts its quantum and is demoted, so after $j$ scheduling rounds (ignoring intervening I/O-bound jobs) it has received cumulative service

and sits at level $j$. Because $q_i$ increases with $i$ (commonly doubling), this sum grows geometrically, so within $O(\log(B/q_0))$ demotions the job has been serviced roughly its full burst length — meaning short jobs finish within the first one or two quanta at $Q_0$, while long jobs are quickly recognized and shunted to coarse-grained low-priority queues where they interfere least with interactive work. This mirrors Shortest Job First's optimal-average-waiting-time intuition, but MLFQ derives the "job is short" judgment empirically instead of from an oracle, which is exactly why MLFQ is implementable while pure SJF (which needs future burst lengths) is not. 3. Starvation avoidance requires the boost. Without Rule 5, an adversarial or simply unlucky mix of continuously arriving short/interactive jobs can keep $Q_0, \ldots, Q_{k-2}$ perpetually occupied, so a job that has been demoted to $Q_{k-1}$ may never be scheduled — a violation of starvation-freedom. The periodic boost restores a liveness guarantee: every ready process is guaranteed to reach $Q_0$ (and hence be scheduled within one round-robin cycle at that level) within at most $S$ time units of the last boost, since the boost is unconditional over all queues. Formally, if $T$ is the current time and the last boost was at $T_0$, every waiting process is dispatched by time $T_0 + S + O(k \cdot q_{k-1})$ in the worst case — giving a hard upper bound on waiting time that plain demotion-only feedback cannot offer.

Honest tradeoffs. MLFQ is a heuristic classifier of process behavior, not an optimizer: it can misclassify a process whose behavior changes over time (a job that is I/O-bound for a while and then becomes CPU-bound, or vice versa), and its quality depends heavily on tuned parameters ($k$, the $q_i$ sequence, and $S$) that have no universally "correct" values — they are workload-dependent. It also gives no hard timing guarantees, which is precisely the gap that dedicated Real-Time Scheduling disciplines are built to close.

Consider a 3-level MLFQ with quanta $q_0=8$, $q_1=16$, $q_2=$ ∞ (FCFS at the bottom), boost period $S=100$, and three processes arriving at $t=0$:

Trace (single-core, ties broken by arrival order/round-robin within a level):

Reading the trace. Process A, purely by behaving interactively (always blocking well before its quantum), never leaves $Q_0$ and is essentially always the next thing scheduled whenever it becomes ready — it experiences near-instant response, exactly the goal for interactive workloads. Processes B and C, by behaving CPU-bound (always exhausting their quantum), are automatically demoted after each dispatch; note C, needing only 20 ms total, finishes while still in $Q1$ (after $8+12=20$ ms of service), while B, needing 30 ms, is pushed all the way to $Q2$. This reproduces a coarse approximation of SJF (C, the shorter job, finishes before B, the longer one) even though the scheduler was never told either job's total length — it inferred relative length purely from how many quanta each one burned through. If the boost timer $S=100$ ever fires while B is still in $Q2$, B would be reset to $Q0$, guaranteeing it isn't stuck behind an endless stream of new short jobs.

The multilevel feedback queue concept traces to the earliest attempts to build time-sharing systems that served both interactive terminals and batch computation on the same machine — a problem that dominated operating systems research through the 1960s.

Variants of MLFQ, or ideas directly descended from it, appear throughout production operating systems. The classic UNIX/BSD scheduler recomputes process priority periodically from a decaying average of recent CPU usage — a continuous analogue of discrete queue demotion. Windows NT's scheduler uses dynamic priority classes with boosts for processes returning from I/O wait or from foreground-window focus changes, directly mirroring the "reward interactive behavior" principle. Solaris's Time-Share (TS) class explicitly implements a table mapping recent CPU usage to priority and quantum, which is essentially a tabulated MLFQ. Even container orchestration and cloud CPU schedulers borrow the underlying philosophy — infer job character from behavior and adapt resource allocation — when deciding how to time-slice tenants without foreknowledge of their workloads. Understanding MLFQ is also the conceptual stepping stone to Real-Time Scheduling, where systems abandon adaptive inference in favor of hard, provable deadline guarantees that no feedback-based heuristic can offer, and to more general ideas in Priority Scheduling and Round-Robin Scheduling that MLFQ generalizes and combines.

Ask the tutor: How would you redesign MLFQ's boost period to adapt automatically to changing workload mixes instead of using a fixed constant $S$?