Multilevel Feedback Queue Scheduling
Multilevel feedback queue scheduling is a CPU scheduling method that extends multilevel queues by letting a process move between queues based on its observed behavior. New processes start in the highest-priority queue with a short time quantum, and a process that uses its whole quantum is demoted, rewarding short interactive processes and pushing long CPU-heavy ones down.
Multilevel feedback queue scheduling fixes the biggest limitation of plain multilevel queue scheduling: instead of permanently assigning a process to one queue for its entire life, it lets a process move between queues dynamically, based on how it actually behaves while running. This is what "feedback" means here, the scheduler observes a process's behavior and adjusts its treatment accordingly.
The core mechanism
Typically implemented as several queues, ranked from highest priority (usually with a short time quantum, for fast interactive response) to lowest priority (usually with a longer time quantum, or even plain FCFS, for CPU-heavy batch work). A new process starts in the highest-priority queue. If it uses its entire time quantum without finishing (a signal that it's a longer, more CPU-intensive process, not a quick interactive one), it gets demoted to the next lower-priority queue. If it instead finishes or voluntarily blocks (for I/O) within its quantum, it stays at its current level or can even be promoted back up, since that behavior looks like a short, interactive process.
A worked example
Three queues: Q0 (quantum 4, highest priority), Q1 (quantum 8), Q2 (FCFS, lowest priority). A new process always starts in Q0.
Process P1 starts in Q0. It runs for its full 4-unit quantum without finishing, so it's demoted to Q1. In Q1, it runs for its full 8-unit quantum, still not finished, so it's demoted further to Q2. In Q2, it eventually gets to run via FCFS and finishes there.
Meanwhile, process P2 also starts in Q0, but only needs 3 units total. It finishes within its first quantum in Q0, so it never gets demoted at all, staying in the fast, high-priority queue for its entire (short) lifetime.
P1, which behaved like a long CPU-bound process, ended up progressively demoted to slower, lower-priority treatment. P2, which behaved like a short process, got fast treatment the whole way through, entirely automatically, based purely on observed behavior, with no need to know either process's actual total burst time in advance.
Why this is genuinely powerful
This solves the exact practical problem SJF and priority scheduling both have: they need to know (or predict) a process's characteristics in advance. Multilevel feedback queue scheduling needs no such prediction, it learns a process's apparent nature purely from how it actually behaves once running, and adapts automatically.
Where this matters in real systems
This is close to how many real, practical general-purpose OS schedulers actually approximate favoring interactive workloads without needing to predict anything in advance. Older Unix and early Windows NT schedulers used explicit multilevel feedback queue designs; even schedulers that aren't literally implemented this way, like Linux's CFS, capture a similar underlying philosophy: a process's recent behavior (how much CPU it's actually used) directly informs how it's treated going forward, without requiring any advance declaration of its needs.
What interviewers actually ask about multilevel feedback queue scheduling
- "How does multilevel feedback queue scheduling differ from plain multilevel queue scheduling?" Plain multilevel queues permanently assign a process to one queue; feedback queues let a process move between queues dynamically based on observed behavior.
- "What causes a process to be demoted to a lower-priority queue?" Using its entire time quantum without finishing, a signal that it behaves like a longer, more CPU-intensive process.
- "What's the key advantage of this approach over SJF or priority scheduling?" It doesn't require knowing or predicting a process's burst time or nature in advance, it learns this purely from observed runtime behavior.
- "Can a process move back up to a higher-priority queue?" Yes, in many designs, a process that starts behaving in a short/interactive way again (finishing quickly, blocking for I/O) can be promoted back up, not just demoted.
Key takeaways
- Multilevel feedback queue scheduling lets processes move between priority queues dynamically, based on observed behavior.
- Using a full time quantum without finishing typically demotes a process to a lower, less time-sensitive queue.
- Unlike SJF or priority scheduling, it requires no advance knowledge of a process's actual characteristics.
- Its underlying philosophy, adapt treatment based on recent observed behavior, echoes in real production schedulers like Linux's CFS.
More in Process Scheduling
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
How does multilevel feedback queue scheduling differ from plain multilevel queue scheduling?
Plain multilevel queues permanently assign a process to one queue; feedback queues let a process move between queues dynamically based on observed behavior.
What causes a process to be demoted to a lower-priority queue?
Using its entire time quantum without finishing, a signal that it behaves like a longer, more CPU-intensive process.
What's the key advantage of this approach over SJF or priority scheduling?
It doesn't require knowing or predicting a process's burst time or nature in advance, it learns this purely from observed runtime behavior.
Can a process move back up to a higher-priority queue?
Yes, in many designs, a process that starts behaving in a short/interactive way again (finishing quickly, blocking for I/O) can be promoted back up, not just demoted.