Free lesson · Operating Systems
Multi Level Feedback Queue
The Scheduler That Actually Runs Your Computer
Every scheduling algorithm you have learned so far has a fatal flaw. FCFS produces convoys. SJF requires knowing the future. Round Robin ignores priority. Priority scheduling causes starvation. Each algorithm optimizes for one thing and fails at everything else.
The Multi-Level Feedback Queue (MLFQ) solves this by combining the best ideas from all previous algorithms into a single, adaptive system. MLFQ is not just a textbook concept - it is the foundation of the schedulers used by real operating systems. Linux's Completely Fair Scheduler (CFS), Windows' scheduler, and macOS's scheduler are all descendants of MLFQ ideas. When an interviewer asks "how does scheduling actually work in practice?", MLFQ is the answer they want.
MLFQ achieves two seemingly contradictory goals: it gives interactive processes excellent response time (like Round Robin with a small quantum) while giving CPU-bound processes high throughput (like FCFS with long runs). It does this without knowing anything about the processes in advance - it learns each process's behavior by observing how it uses its time quantum, and it adapts accordingly.
The Core Idea: Multiple Queues with Different Priorities
MLFQ maintains several ready queues, each with a different priority level. Higher-priority queues are served before lower-priority ones. Within each queue, processes are scheduled using Round Robin with a time quantum specific to that queue. The key innovation is that processes move between queues based on their behavior.
graph TD
subgraph MLFQ["Multi-Level Feedback Queue"]
Q0["Queue 0 (Highest Priority)<br/>────<br/>Quantum: 8 ms<br/>Round Robin"]
Q1["Queue 1 (Medium Priority)<br/>────<br/>Quantum: 16 ms<br/>Round Robin"]
Q2["Queue 2 (Lowest Priority)<br/>────<br/>Quantum: 32 ms<br/>FCFS or Round Robin"]
end
Q0 -->|"Process uses full quantum<br/>(CPU-bound behavior)"| Q1
Q1 -->|"Process uses full quantum<br/>(still CPU-bound)"| Q2
Q2 -->|"Periodic boost<br/>(prevent starvation)"| Q0
Q0 -->|"Process blocks before<br/>quantum expires<br/>(I/O-bound behavior)"| Q0_STAY["Stays in Queue 0"]
This diagram shows a Multi-Level Feedback Queue with three priority levels. Queue 0 has the highest priority with an 8ms quantum. Queue 1 has medium priority with a 16ms quantum. Queue 2 has the lowest priority with a 32ms quantum. When a process uses its full quantum in Queue 0, it is demoted to Queue 1. If it uses its full quantum in Queue 1, it is demoted to Queue 2. Periodically, all processes are boosted back to Queue 0 to prevent starvation. If a process blocks before its quantum expires (I/O-bound behavior), it stays in Queue 0.
The Five Rules of MLFQ
MLFQ operates according to five rules that define its behavior:
Rule 1: If Priority(A) > Priority(B), A runs. Higher-priority processes are always scheduled before lower-priority ones. A process in Queue 0 runs before any process in Queue 1, which runs before any process in Queue 2.
Rule 2: If Priority(A) = Priority(B), A and B run in Round Robin. Within the same priority queue, processes share the CPU using Round Robin with that queue's time quantum.
Rule 3: New processes start at the highest priority (Queue 0). When a process is created, it enters Queue 0. The scheduler gives every process the benefit of the doubt - it assumes the process is interactive until proven otherwise.
Rule 4: If a process uses its entire time quantum, it is demoted. A process that runs for its full quantum without blocking is exhibiting CPU-bound behavior. The scheduler responds by moving it to the next lower-priority queue. The process gets a longer quantum in the lower queue (so it can make progress without constant preemption) but at lower priority (so it does not block interactive processes).
Rule 5: After a fixed time period, all processes are boosted to the highest queue. This is the starvation prevention mechanism. Periodically (every S milliseconds, where S is a tunable parameter), every process in every queue is moved back to Queue 0. This ensures that no process stays at low priority forever. The boost period S is a tradeoff: too short and CPU-bound processes keep getting boosted and interfering with interactive processes; too long and starved processes wait a long time.
How MLFQ Adapts to Process Behavior
The genius of MLFQ is that it learns what each process needs by watching how it uses the CPU, rather than requiring advance knowledge.
An interactive process (text editor, web server) runs briefly (a few milliseconds of CPU to process a keystroke or an HTTP request), then blocks on I/O (waiting for the next keystroke or network packet). Because it never uses its full quantum, it stays in Queue 0 - the highest priority. It gets excellent response time because it is always in the highest-priority queue.
A CPU-bound process (compilation, video encoding) runs for its entire quantum without blocking. After using its full quantum in Queue 0, it is demoted to Queue 1. After using its full quantum in Queue 1, it is demoted to Queue 2. Eventually, it settles at the lowest priority. But Queue 2 has the longest quantum - 32 ms or more - so the CPU-bound process can make substantial progress on each turn without excessive context switching. It gets lower priority but higher throughput per turn.
A process that changes behavior - say, a process that starts as CPU-bound (loading data) and then becomes interactive (responding to user queries) - automatically adjusts. When it was CPU-bound, it got demoted. When it starts blocking before its quantum expires (interactive behavior), it stays at its current queue. At the next periodic boost, it returns to Queue 0 and stays there as long as it continues to behave interactively.
This adaptive behavior is what makes MLFQ practical. The scheduler does not need a configuration file telling it which processes are interactive and which are CPU-bound. It figures it out from behavior and adjusts dynamically.
Gaming the Scheduler
A naive implementation of MLFQ has a vulnerability: a clever process can game the scheduler to get more than its fair share of CPU time. If a process knows the quantum is 8 ms, it can run for 7.9 ms of computation, then issue a trivial I/O operation (like reading one byte from /dev/null) to appear I/O-bound. The scheduler sees the process blocking before its quantum expires and keeps it in Queue 0 - the highest priority. The process gets the benefits of high priority (fast scheduling) while doing mostly CPU-bound work.
This gaming attack is the reason Rule 4 in modern MLFQ implementations tracks total CPU time used at a priority level, not just whether the process used its quantum in a single run. If a process accumulates 8 ms of total CPU time in Queue 0 across multiple runs (even if each individual run was less than 8 ms), it is demoted. This closes the gaming loophole by measuring aggregate behavior rather than per-quantum behavior.
Gaming is not just a theoretical concern. In multi-tenant cloud environments where CPU time is a shared resource, a tenant who games the scheduler can steal CPU time from other tenants. This is why cloud providers like AWS and Google Cloud use cgroup-based CPU limits in addition to scheduler-level priorities - the cgroup enforces a hard ceiling on CPU time regardless of scheduler behavior.
Tuning MLFQ Parameters
MLFQ has several parameters that affect its behavior, and understanding these parameters helps you discuss scheduling in system design interviews:
Number of queues. More queues provide finer-grained priority separation but increase complexity. Most practical implementations use 3-5 queues. Too few queues do not separate interactive from CPU-bound effectively. Too many queues add overhead without meaningful benefit.
Time quantum per queue. Each queue typically has a quantum that is 2x the queue above it (e.g., 8ms, 16ms, 32ms, 64ms). This geometric progression means CPU-bound processes at the lowest queue get long quanta, minimizing context switch overhead. The bottom queue may use FCFS (infinite quantum) for pure batch work.
Boost period (S). The interval at which all processes return to Queue 0. A typical value is 1 second. Too short and CPU-bound processes constantly return to high priority, interfering with interactive responsiveness. Too long and starved processes wait an unacceptable time.
Demotion threshold. How much CPU time at a priority level triggers demotion. Usually set equal to the queue's time quantum. The aggregate-time variant (preventing gaming) tracks total CPU usage across multiple quanta.
sequenceDiagram
participant INTERACTIVE as Interactive Process<br/>(text editor)
participant CPU_BOUND as CPU-Bound Process<br/>(compiler)
participant Q0 as Queue 0
participant Q1 as Queue 1
participant Q2 as Queue 2
Note over INTERACTIVE: Arrives → Queue 0
Note over CPU_BOUND: Arrives → Queue 0
Q0->>INTERACTIVE: Run (8ms quantum)
INTERACTIVE->>Q0: Blocks after 2ms (I/O)<br/>Stays in Queue 0 ✓
Q0->>CPU_BOUND: Run (8ms quantum)
CPU_BOUND->>Q1: Uses full 8ms<br/>Demoted to Queue 1 ↓
Q0->>INTERACTIVE: Run again (8ms quantum)
INTERACTIVE->>Q0: Blocks after 3ms<br/>Stays in Queue 0 ✓
Q1->>CPU_BOUND: Run (16ms quantum)
CPU_BOUND->>Q2: Uses full 16ms<br/>Demoted to Queue 2 ↓
Note over INTERACTIVE: Always responsive<br/>(stays in high queue)
Note over CPU_BOUND: Gets long quanta<br/>(makes progress in low queue)
This sequence diagram shows how MLFQ treats interactive and CPU-bound processes differently. Both start in Queue 0. The interactive process uses only 2-3ms of its 8ms quantum before blocking on I/O, so it stays in Queue 0 and gets excellent response time. The CPU-bound process uses its full 8ms quantum and is demoted to Queue 1. It then uses its full 16ms quantum in Queue 1 and is demoted to Queue 2. The interactive process stays responsive at high priority while the CPU-bound process settles at low priority with long quanta for throughput.
Interview: "How does the MLFQ scheduler work?"
"MLFQ uses multiple priority queues, each with a different time quantum. New processes start at the highest priority. If a process uses its full quantum (CPU-bound behavior), it is demoted to a lower-priority queue with a longer quantum. If it blocks before the quantum expires (I/O-bound behavior), it stays at the same priority level.
This automatically separates interactive processes (which stay at high priority because they use the CPU briefly) from CPU-bound processes (which settle at low priority but get longer quanta for throughput). Periodic boosting moves all processes back to the highest queue to prevent starvation.
The result is a scheduler that provides good response time for interactive tasks and good throughput for batch tasks, without requiring advance knowledge of process behavior. It is the conceptual basis for the schedulers in Linux, Windows, and macOS."
Linux's Completely Fair Scheduler (CFS)
The Completely Fair Scheduler (CFS) has been Linux's default scheduler since kernel version 2.6.23 (2007). It is a direct descendant of MLFQ ideas, but it replaces the discrete priority queues with a continuous fairness model.
CFS's core idea is simple: every process should get an equal share of CPU time proportional to its weight (which is derived from its nice value). CFS tracks a metric called virtual runtime (vruntime) for each process - a measure of how much CPU time the process has received, normalized by its weight. The process with the lowest vruntime (the one that has received the least CPU time relative to its fair share) is always selected to run next.
CFS uses a red-black tree (a self-balancing binary search tree) to maintain processes sorted by vruntime. Selecting the next process is O(log n) - finding the leftmost node in the tree. Inserting a process back into the tree after it runs is also O(log n). This is more expensive than a simple FIFO queue (O(1)) but much more fair and adaptive.
CFS does not use fixed time quanta. Instead, it calculates a target latency - the total time within which every runnable process should get at least one turn. If there are 10 runnable processes and the target latency is 20 ms, each process gets roughly 2 ms per turn. If there are 100 runnable processes, each gets 0.2 ms - but CFS enforces a minimum granularity (typically 0.75 ms) to prevent excessive context switching.
Note: Founder Insight - Nikhil Joshi (Google, L5 SWE, Distributed Systems)
"Scheduling is not just theory - it directly affects production latency. At Google, we tune CFS parameters for latency-sensitive services like Spanner and Bigtable. The default CFS target latency is 6 ms with a minimum granularity of 0.75 ms. For services with strict P99 latency SLAs, we sometimes reduce the target latency to push scheduling decisions faster - but this increases context switch overhead, so there is a measurable tradeoff.
One thing that surprised me early on: tail latency spikes in our services were sometimes caused not by our code, but by CFS scheduling decisions. A garbage collection thread in a colocated JVM service would consume its entire time slice, delaying our latency-sensitive threads by a few milliseconds - enough to blow our P99 SLA. We fixed it by using cgroups to isolate CPU time for our service, effectively giving it its own scheduling domain. Understanding CFS was essential for diagnosing the issue."
How CFS Handles Nice Values
CFS uses nice values (-20 to +19) to weight processes differently. A process with a lower nice value (higher priority) accumulates vruntime more slowly, which means it stays near the front of the tree longer and gets more CPU time. The mapping is exponential: each nice level changes the weight by approximately 1.25x. A process at nice -1 gets about 1.25x the CPU time of a process at nice 0, and a process at nice -20 gets about 88x the CPU time of a process at nice +19.
This weighting system provides a continuous priority mechanism without the discrete queues and hard boundaries of classical MLFQ. It avoids starvation entirely because every process accumulates vruntime - even the lowest-priority process will eventually have the lowest vruntime and be selected to run.
MLFQ vs CFS: The Conceptual Connection
Classical MLFQ and Linux's CFS solve the same problem - balancing response time and throughput for mixed workloads - but they use different mechanisms:
| Feature | Classical MLFQ | Linux CFS |
|---|---|---|
| Structure | Discrete priority queues | Single red-black tree sorted by vruntime |
| Priority mechanism | Queue level (higher queue = higher priority) | vruntime (lower vruntime = runs next) |
| Time quantum | Fixed per queue level | Dynamic based on number of runnable processes |
| Starvation prevention | Periodic boost to top queue | Guaranteed by vruntime - all processes accumulate it |
| Behavior detection | Explicit: use full quantum → demote | Implicit: CPU-bound processes accumulate vruntime faster |
| Complexity | Simple to understand and implement | More complex but more precise |
Both achieve the same outcome: interactive processes (short CPU bursts, frequent I/O) get excellent response time, and CPU-bound processes get fair throughput.
Exercise: Starter: Given an MLFQ with three queues (Q0: quantum=4ms, Q1: quantum=8ms, Q2: quantum=16ms) and a process with a CPU burst of 30ms, trace the process through the queues. How long does it spend in each queue? How many context switches occur? What is the total time from start to finish (assuming no other processes)?
Intermediate: Now add a second process - an interactive process that arrives at time 2ms, runs for 1ms, blocks for 5ms, then runs for 1ms again. Trace both processes through the MLFQ. How does the scheduler ensure the interactive process gets good response time while the CPU-bound process still makes progress?
Advanced: Research Linux's CFS in more detail. How does CFS handle a scenario with one CPU-bound process (nice 0) and one I/O-bound process (nice 0)? The I/O-bound process runs for 1ms then blocks for 10ms repeatedly. What are their respective vruntimes after 100ms of wall clock time? Which process is always selected when both are runnable? How does this achieve the same effect as MLFQ's queue demotion?