Think about the security check at an airport. There is a priority lane for crew and business-class passengers, a regular lane for everyone else, and sometimes a separate lane for families with small children. Each lane has its own line and its own pace, and staff decide which lane gets served next.
A real operating system faces the same situation. Some processes are interactive (a text editor waiting for your keystrokes), some are system services, and some are long background jobs (a video export, a backup). Treating them all with one algorithm is a poor fit. So OS designers split the ready queue into several queues.
Multilevel Queue (MLQ) scheduling divides processes into fixed classes, each with its own ready queue and its own scheduling algorithm, and then schedules between the queues. Multilevel Feedback Queue (MLFQ) scheduling also uses several queues, but lets processes move between them based on how they actually behave.
This chapter brings together everything from the previous scheduling chapters. MLQ combines Priority Scheduling (between queues) with Round Robin or FCFS (inside each queue). MLFQ goes one step further and approximates SJF without knowing any burst times. Its core idea, first used in the CTSS system in the early 1960s, still shapes many general-purpose schedulers today.
Multilevel Queue (MLQ) Scheduling
In MLQ, each process is permanently assigned to one queue when it is created, based on some property such as process type, memory size or priority.
Highest priority
┌──────────────────────────────┐
Q0 │ System processes (RR) │ → →
├──────────────────────────────┤
Q1 │ Interactive processes (RR) │ → → ┌─────┐
├──────────────────────────────┤ ───→ │ CPU │
Q2 │ Batch processes (FCFS) │ → → └─────┘
└──────────────────────────────┘
Lowest priority
A process never moves from one queue to another.
Each queue can use the algorithm that suits its processes:
Interactive (foreground) queue: Round Robin, for good response time.
Batch (background) queue: FCFS, because response time does not matter and FCFS has the least overhead.
Scheduling Between the Queues
Having several queues raises a new question: which queue gets the CPU? There are two common answers.
Method | How it works | Downside |
|---|---|---|
Fixed-priority preemptive | A lower queue runs only when all higher queues are empty. If a process arrives in a higher queue, it preempts a running lower-queue process. | Lower queues can starve |
Time slicing between queues | Each queue gets a fixed share of CPU time, for example 80% for the foreground queue (RR among its processes) and 20% for the background queue (FCFS). | Shares are fixed; high-priority work may wait while the low queue uses its slice |
Example 1: Multilevel Queue
Two queues, fixed-priority preemptive between them:
Q0 (high priority, interactive): Round Robin with
q = 2Q1 (low priority, batch): FCFS
Process | Arrival Time | Burst Time | Queue |
|---|---|---|---|
P1 | 0 | 6 | Q1 |
P2 | 1 | 4 | Q0 |
P3 | 2 | 3 | Q0 |
P4 | 3 | 5 | Q1 |
P5 | 11 | 2 | Q0 |
One more rule is needed: when a Q1 process is preempted by a Q0 arrival, where does it go? We keep it at the head of Q1, so it resumes before other Q1 processes. That is natural for an FCFS queue, and it is also how Linux treats a preempted SCHED_FIFO thread.
Step-by-step trace
t = 0 : Q0 = [] Q1 = [P1] → P1 runs (Q0 empty)
t = 1 : P2 arrives in Q0 → P1 preempted (rem 5, stays at head of Q1)
Q0 = [P2] Q1 = [P1] → P2 runs 1-3 (quantum 2, rem 2)
t = 3 : P3 (arr 2) is in Q0, P4 (arr 3) joins Q1
Q0 = [P3, P2] Q1 = [P1, P4] → P3 runs 3-5 (rem 1)
t = 5 : Q0 = [P2, P3] → P2 runs 5-7, done
t = 7 : Q0 = [P3] → P3 runs 7-8, done
t = 8 : Q0 = [] Q1 = [P1, P4] → P1 resumes (rem 5)
t = 11 : P5 arrives in Q0 → P1 preempted (rem 2, head of Q1)
P5 runs 11-13, done
t = 13 : Q0 = [] Q1 = [P1, P4] → P1 runs 13-15, done
t = 15 : Q1 = [P4] → P4 runs 15-20, done
| P1 | P2 | P3 | P2 | P3 | P1 | P5 | P1 | P4 |
0 1 3 5 7 8 11 13 15 20
Process | Queue | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|---|
P1 | Q1 | 0 | 6 | 15 | 15 | 9 |
P2 | Q0 | 1 | 4 | 7 | 6 | 2 |
P3 | Q0 | 2 | 3 | 8 | 6 | 3 |
P4 | Q1 | 3 | 5 | 20 | 17 | 12 |
P5 | Q0 | 11 | 2 | 13 | 2 | 0 |
Average TAT = 46 / 5 = 9.2
Average WT = 26 / 5 = 5.2
Average WT of Q0 processes (P2, P3, P5) = 5 / 3 ≈ 1.67
Average WT of Q1 processes (P1, P4) = 21 / 2 = 10.5
The split averages tell the real story: the interactive queue waits very little, and the batch queue absorbs all the delay. That is exactly what MLQ is designed to do. But if Q0 processes kept arriving without a break, P4 would never run.
Problems With Plain MLQ
Starvation of lower queues under fixed-priority scheduling.
Inflexibility: the OS must classify every process correctly at creation time, and the classification never changes. A program that is interactive for a while and then starts heavy computation stays in the interactive queue and hurts everyone there. A batch job that becomes interactive stays stuck at the bottom.
Both problems are solved by letting processes move between queues.
Multilevel Feedback Queue (MLFQ) Scheduling
MLFQ uses the same stack of queues, but the queue a process is in is not fixed. The scheduler watches each process and moves it up or down based on its recent CPU usage. That observation is the "feedback".
The central idea:
MLFQ does not need to know how long a process will run. It learns from the past: processes that use a lot of CPU sink to lower-priority queues, and processes that use the CPU only briefly (typically interactive, I/O-bound ones) stay near the top.
The Rules of a Typical MLFQ
Rule 1: A new process enters the highest-priority queue. (We give every newcomer the benefit of the doubt: maybe it is short.)
Rule 2: A process in a higher queue always runs before any process in a lower queue. An arrival in a higher queue preempts a running lower-queue process.
Rule 3: Processes in the same queue share the CPU in Round Robin. Lower queues usually get longer quanta, and the lowest queue often uses FCFS.
Rule 4: If a process uses up its entire quantum at a level, it is demoted one level.
Rule 5: If a process gives up the CPU before its quantum ends (for example, to wait for I/O), it stays at the same level.
Rule 6 (priority boost): Every so often, move all processes back to the top queue. This prevents starvation and lets a process that changed behaviour be re-evaluated.
new process
↓
Q0 (q = 4, RR) [ ... ] ── uses full quantum ──┐
↓
Q1 (q = 8, RR) [ ... ] ── uses full quantum ──┐
↓
Q2 (FCFS) [ ... ]
Higher queue always preempts lower queue.
Periodically: boost everything back to Q0.
Why longer quanta at lower levels? Processes that reach the bottom are known to be CPU-hungry. Giving them longer slices means fewer context switches for them, and since they rarely interact with users, the longer wait between turns does not hurt anyone.
What Defines an MLFQ Scheduler?
An MLFQ is a family of schedulers, not one algorithm. A specific design is fixed by these parameters:
The number of queues
The scheduling algorithm (and quantum) for each queue
When to demote a process
When to promote a process (aging, priority boost)
Which queue a new process enters
This makes MLFQ the most general CPU scheduling scheme you will study, but also the most complex to tune.
Example 2: Multilevel Feedback Queue
Three queues:
Q0: Round Robin,
q = 4(highest priority)Q1: Round Robin,
q = 8Q2: FCFS (lowest priority)
All processes enter Q0. Using a full quantum demotes a process one level. A higher queue preempts a lower one. (No priority boost happens in this short example.)
Process | Arrival Time | Burst Time |
|---|---|---|
P1 | 0 | 17 |
P2 | 2 | 5 |
P3 | 4 | 2 |
P4 | 21 | 6 |
Step-by-step trace
t = 0 : Q0 = [P1]
P1 runs 0-4 in Q0, uses full quantum (rem 13) → demoted to Q1
t = 4 : Q0 = [P2, P3] Q1 = [P1]
P2 runs 4-8 in Q0, uses full quantum (rem 1) → demoted to Q1
t = 8 : Q0 = [P3] Q1 = [P1, P2]
P3 runs 8-10, needs only 2 → done
t = 10 : Q0 = [] Q1 = [P1, P2]
P1 runs 10-18 in Q1, uses full quantum 8 (rem 5) → demoted to Q2
t = 18 : Q1 = [P2] Q2 = [P1]
P2 runs 18-19, needs only 1 → done
t = 19 : Q2 = [P1]
P1 runs in Q2 (FCFS) from 19 ...
t = 21 : P4 arrives in Q0 → preempts P1 (rem 3, stays in Q2)
P4 runs 21-25 in Q0, full quantum (rem 2) → demoted to Q1
t = 25 : Q1 = [P4] Q2 = [P1]
P4 runs 25-27 in Q1 → done
t = 27 : P1 runs 27-30 in Q2 → done
| P1 | P2 | P3 | P1 | P2 | P1 | P4 | P1 |
| Q0 | Q0 | Q0 | Q1 | Q1 | Q2 |Q0, Q1| Q2 | <- queue
0 4 8 10 18 19 21 27 30
(The P4 block from 21 to 27 is two slices back to back: 21-25 in Q0 and 25-27 in Q1.)
Process | AT | BT | CT | TAT | WT | RT | Lowest queue reached |
|---|---|---|---|---|---|---|---|
P1 | 0 | 17 | 30 | 30 | 13 | 0 | Q2 |
P2 | 2 | 5 | 19 | 17 | 12 | 2 | Q1 |
P3 | 4 | 2 | 10 | 6 | 4 | 4 | Q0 |
P4 | 21 | 6 | 27 | 6 | 0 | 0 | Q1 |
Average TAT = 59 / 4 = 14.75
Average WT = 29 / 4 = 7.25
Average RT = 6 / 4 = 1.5
Look at what MLFQ did without knowing any burst times:
The short job P3 (burst 2) finished in its very first turn, in the top queue.
The long job P1 (burst 17) sank to the bottom and ran in the gaps.
The newcomer P4 got the CPU the instant it arrived (RT = 0), because it started in the top queue.
Comparing With Other Algorithms on the Same Data
Algorithm | Avg TAT | Avg WT | Avg RT | Needs burst times? |
|---|---|---|---|---|
FCFS | 16.50 | 9.00 | 9.00 | No |
Round Robin (q = 4) | 14.00 | 6.50 | 2.00 | No |
MLFQ (4 / 8 / FCFS) | 14.75 | 7.25 | 1.50 | No |
SRTF | 10.50 | 3.00 | 0.75 | Yes |
SRTF wins every column, but it cheats: it knows the future. Among the algorithms that do not, MLFQ gives the best response time here, and its job is precisely to give quick responses to short and interactive work while still finishing long jobs. Notice that MLFQ's average turnaround is slightly worse than plain RR in this small example. That is a reminder that no scheduler is best on every metric; MLFQ is tuned for responsiveness, and its advantage grows on real workloads with many short interactive bursts.
How MLFQ Treats I/O-Bound Processes
The real power of MLFQ appears with interactive programs. Consider an editor that runs for 1 ms, then waits for a keystroke, again and again, while a long compilation runs in the background:
Editor: run 1 ms → block for I/O → run 1 ms → block → ...
never uses a full quantum of 4 ms → Rule 5 → stays in Q0
Compiler: uses its full quantum every time → Rule 4
Q0 → Q1 → Q2, then runs in the gaps
Result: every time you press a key, the editor is in the highest queue
and preempts the compiler immediately. The system feels fast.
MLFQ has effectively approximated SJF for CPU bursts: short bursts get top priority, long ones get pushed down, and it learned this purely from observation.
Problems MLFQ Must Handle
1. Starvation
If there are always enough interactive processes in the top queues, a CPU-bound process in the bottom queue may never run. The priority boost (Rule 6) fixes this: every S time units, all processes return to the top queue, so even a bottom-queue process gets regular turns.
Choosing S is a balancing act. Too long, and long jobs starve for a while. Too short, and interactive processes lose their advantage because everyone is constantly boosted to the top. This is a form of the aging you saw in Priority Scheduling.
2. A Process That Changes Behaviour
A program might compute heavily at startup and later become interactive (or the reverse). Without boosts, it would stay in a low queue forever. Periodic boosting gives it a chance to prove itself again. Some designs also promote a process that has waited too long in a low queue.
3. Gaming the Scheduler
A clever (or malicious) program can exploit Rule 5. If it always does a tiny, useless I/O just before its quantum ends, it never uses a "full" quantum and stays in the top queue forever, taking almost all the CPU.
Quantum = 4 ms
Gaming process: run 3.9 ms → fake I/O → run 3.9 ms → fake I/O → ...
Never demoted. Gets nearly 100% of the CPU at top priority.
The fix is better accounting: track the total CPU time a process has used at its current level, across all its turns. Once that total reaches the level's allotment, demote it, no matter how many times it gave up the CPU early. With this rule, splitting CPU usage into small pieces no longer helps.
MLQ vs MLFQ
Feature | Multilevel Queue | Multilevel Feedback Queue |
|---|---|---|
Process moves between queues? | No, assigned once | Yes, based on CPU usage |
Classification | By type, fixed at creation | Learned from behaviour |
Starvation | Possible for lower queues | Prevented by priority boost / aging |
Overhead | Lower | Higher (tracking usage, moving processes) |
Flexibility | Low | High, but many parameters to tune |
Approximates SJF? | No | Yes, without knowing burst times |
Typical use | Separating clearly different classes (real-time vs normal) | General-purpose time-sharing schedulers |
Multilevel Ideas in Real Operating Systems
Real schedulers rarely match the textbook versions exactly, but the ideas from this chapter show up everywhere:
Linux scheduling classes form a multilevel queue. In order of precedence: the stop class (internal),
SCHED_DEADLINE, real-time (SCHED_FIFO/SCHED_RR, priorities 1 to 99), then normal tasks (SCHED_OTHER,SCHED_BATCH,SCHED_IDLE). A runnable task in a higher class always runs first, which is fixed-priority MLQ between classes. Within normal tasks, Linux used an MLFQ-like "O(1)" scheduler with interactivity heuristics in early 2.6 kernels, replaced it with the Completely Fair Scheduler (CFS) in 2.6.23 (2007), and since 6.6 (2023) uses EEVDF. Since 6.12 (2024), the sched_ext class even lets administrators load their own scheduling policies written as BPF programs.Windows uses 32 priority levels (0 to 31). Levels 16 to 31 are the real-time range, and levels 1 to 15 are the variable range, where the OS temporarily boosts a thread's priority, for example after it completes I/O or when its window is in the foreground, and lets the boost decay as the thread uses CPU. That is MLFQ-style feedback.
Solaris, macOS and the BSDs also adjust priorities dynamically based on CPU usage and sleeping, giving interactive threads higher priority and shorter waits. Classic Solaris uses a dispatch table where lower priorities get longer time quanta, exactly like Rule 3.
So when you study MLFQ, you are studying the core idea behind the desktop and phone you are using right now.
Summary of All Scheduling Algorithms
This table pulls together the scheduling chapters from FCFS Scheduling to this one:
Algorithm | Preemptive? | Selection rule | Starvation? | Main strength | Main weakness |
|---|---|---|---|---|---|
FCFS | No | Earliest arrival | No | Simple, low overhead | Convoy effect |
SJF | No | Shortest next burst | Yes | Optimal avg WT (all arrive together) | Burst times unknown |
SRTF | Yes | Shortest remaining time | Yes | Optimal avg WT in general | Burst times unknown, more switches |
Priority | Either | Highest priority | Yes (fix: aging) | Important work first | Starvation, priority inversion |
Round Robin | Yes (timer) | Next in circular queue | No | Fair, good response time | Switch overhead, quantum-sensitive |
Multilevel Queue | Usually | Highest non-empty queue, then that queue's algorithm | Yes (fixed priority) | Different policies for different classes | Rigid classification |
MLFQ | Yes | Highest non-empty queue; queues adjust by behaviour | No (with boost) | Approximates SJF without knowing bursts | Complex to tune, can be gamed without proper accounting |
Common Mistakes
Mixing up MLQ and MLFQ. The one-word difference is "movement": MLQ processes never move between queues; MLFQ processes do.
Forgetting cross-queue preemption. In Example 2, P4 arriving in Q0 at time 21 immediately preempts P1 in Q2.
Demoting a process that finished within its quantum. P3 needed 2 units in a 4-unit quantum; it simply completes. Demotion only happens when the full quantum is used and work remains.
Resetting the remaining time after a demotion. P1 enters Q1 with 13 units left, not 17.
Giving a preempted lower-queue process a fresh full quantum without saying so. When a process is preempted by a higher queue, state whether it keeps its used quantum. It matters in RR queues.
Assuming lower queues have shorter quanta. It is usually the opposite: lower queues hold CPU-bound processes and get longer quanta.
Interview Questions
What is the difference between multilevel queue and multilevel feedback queue scheduling?
In MLQ, a process is assigned to one queue permanently. In MLFQ, a process can move between queues based on its CPU usage, which lets the scheduler adapt to the process's actual behaviour.
Why does a new process enter the highest-priority queue in MLFQ?
The scheduler does not know how long it will run, so it assumes it might be short. If it is, it finishes quickly with good response time. If it is not, it gets demoted.
How does MLFQ approximate SJF?
Processes with short CPU bursts finish or block before their quantum expires and stay in high queues, while long CPU-bound processes use full quanta and sink. So short bursts effectively get higher priority, without knowing burst lengths in advance.
How does MLFQ prevent starvation?
With a periodic priority boost (or aging): after some time, all processes are moved back to the top queue, so low-queue processes get CPU time again.
How can a process game an MLFQ scheduler, and how is it prevented?
By issuing a tiny I/O just before its quantum ends so it never gets demoted. It is prevented by tracking total CPU time used at a level across all turns and demoting once that allotment is used.
Why do lower queues get longer quanta?
Processes there are CPU-bound and non-interactive. Longer quanta reduce context switches for them, and their response time matters less.
What are the parameters that define an MLFQ scheduler?
The number of queues, the scheduling algorithm and quantum of each queue, the rules for demotion and promotion, and which queue a new process enters.
The Main Idea
Multilevel Queue scheduling splits processes into fixed classes, each with its own queue and algorithm, and schedules between queues by priority or time share. Multilevel Feedback Queue scheduling lets processes move between those queues based on their behaviour.
New process → top queue
↓
Run highest non-empty queue (RR inside, longer quantum lower down)
↓
Used full quantum? → move down
Gave up CPU early? → stay
↓
Every so often → boost everyone to the top
Key facts:
MLQ → fixed queues, no movement, lower queues may starve
MLFQ → movement by feedback, approximates SJF, no burst knowledge needed
Fixes → priority boost (starvation), total-time accounting (gaming)
Real → Linux scheduling classes, Windows priority boosts, Solaris dispatch tables
MLFQ learns from the past to predict the future: it rewards processes that use the CPU briefly and gently pushes CPU-hungry ones aside, giving fast response without needing to know anything in advance.
This completes CPU scheduling. So far, we have assumed that processes run independently. In reality, processes and threads often share data, and when the scheduler can switch between them at any moment, strange bugs appear. The next chapter, Process Synchronization & Race Conditions, explains why.