What is Multilevel Feedback Queue Scheduling?
Learn how multilevel feedback queue (MLFQ) scheduling works — queues, demotion, priority boosting — with an OS interview question answered.
Expected Interview Answer
Multilevel feedback queue (MLFQ) scheduling uses several ready queues ranked by priority, each with its own time quantum, and moves a process between queues based on its observed behavior, so CPU-bound tasks sink to lower-priority, longer-quantum queues while I/O-bound or interactive tasks stay near the top with short, responsive quanta.
A process starts in the highest-priority queue with the shortest time slice. If it uses the entire slice without blocking, the scheduler infers it is CPU-bound and demotes it to the next queue down, which has a longer quantum but lower priority. If instead the process blocks for I/O before its slice expires, it is judged interactive and stays at (or is promoted back to) a high-priority queue so it gets scheduled quickly next time. Lower queues are only serviced when all higher queues are empty, which naturally favors short, bursty jobs without needing to know burst lengths in advance the way Shortest-Job-First does. Because a purely priority-based scheme like this can starve processes stuck in low queues, real implementations add periodic priority boosting, which resets every process back to the top queue at intervals to guarantee forward progress and adapt to workloads that change over time.
- Approximates Shortest-Job-First without needing burst-time predictions
- Keeps interactive processes responsive via short top-queue quanta
- Adapts dynamically as a process shifts between CPU-bound and I/O-bound phases
- Priority boosting prevents starvation of long-running processes
AI Mentor Explanation
MLFQ is like a nets facility with three practice lanes: the fastest lane gives each batter a short five-minute turn, and anyone who is still swinging hard when time runs out gets moved to a slower, longer-turn lane, while anyone who finishes early and steps out gets to stay in the fast lane next time. Batters stuck in the slow lane for too long are all reset back to the fast lane at the top of the hour so nobody is permanently stuck waiting behind heavy hitters. This way the coach never has to guess in advance who needs a short knock versus a long net session — the system figures it out from behavior.
Step-by-Step Explanation
Step 1
Entry at top queue
A new or newly-ready process is placed in the highest-priority queue with the shortest time quantum.
Step 2
Behavior observed
If the process uses its full quantum without blocking, it is demoted to the next lower queue; if it blocks for I/O first, it stays high-priority.
Step 3
Lower-queue servicing
Lower-priority queues only run when all higher-priority queues are empty, and each successive queue has a longer time quantum.
Step 4
Priority boosting
At periodic intervals, every process is moved back to the top queue to prevent starvation and adapt to workload changes.
What Interviewer Expects
- A clear explanation of multiple queues with increasing time quanta
- How feedback (demotion/promotion) is determined from observed behavior
- Why priority boosting is needed to avoid starvation
- Comparison to why it approximates SJF without needing burst-time prediction
Common Mistakes
- Describing it as a single queue with variable priority instead of multiple queues
- Forgetting that lower queues only run when higher queues are empty
- Omitting priority boosting and thus ignoring the starvation risk
- Confusing MLFQ with plain multilevel queue scheduling, which has no feedback/movement between queues
Best Answer (HR Friendly)
“Multilevel feedback queue scheduling is a way for the operating system to figure out, just from watching how a task behaves, whether it is a quick interactive task or a long CPU-heavy one, and treat it accordingly. Tasks that keep needing a full time slice get pushed down to queues with longer but less frequent turns, while short, bursty tasks stay near the top and get served quickly, and everyone is periodically reset to the top so nothing gets stuck waiting forever.”
Code Example
#define NUM_QUEUES 3
int quantum[NUM_QUEUES] = { 8, 16, 32 }; /* quantum grows per lower queue */
void run_process(struct process *p) {
int slice = quantum[p->queue_level];
int used = execute_for(p, slice); /* returns time actually used */
if (used < slice) {
/* blocked for I/O before quantum expired: stays interactive */
p->queue_level = (p->queue_level > 0) ? p->queue_level - 1 : 0;
} else if (p->queue_level < NUM_QUEUES - 1) {
/* used the whole slice: demote toward CPU-bound queues */
p->queue_level++;
}
}
void periodic_priority_boost(struct process *all[], int n) {
for (int i = 0; i < n; i++) all[i]->queue_level = 0; /* prevent starvation */
}Follow-up Questions
- How does MLFQ differ from a plain multilevel queue scheduler?
- Why does priority boosting prevent starvation?
- How would you choose the time quantum for each queue level?
- How does MLFQ approximate Shortest-Job-First without knowing burst times in advance?
MCQ Practice
1. In MLFQ, a process that uses its entire time quantum without blocking is typically?
Using the full quantum signals CPU-bound behavior, so the scheduler demotes the process to a lower-priority queue with a longer time slice.
2. What problem does periodic priority boosting solve in MLFQ?
Without boosting, long CPU-bound processes could sink to the lowest queue and never get scheduled promptly again; boosting resets everyone to the top queue periodically.
3. Why is MLFQ considered an approximation of Shortest-Job-First?
MLFQ favors short, bursty jobs by observing whether a process blocks before its quantum expires, achieving an SJF-like effect without needing future knowledge of burst length.
Flash Cards
What is MLFQ scheduling? — A scheduler with multiple priority queues and increasing time quanta, where processes move between queues based on observed behavior.
What causes demotion in MLFQ? — Using the entire time quantum without blocking, signaling CPU-bound behavior.
What causes staying/promotion in MLFQ? — Blocking for I/O before the quantum expires, signaling interactive behavior.
Why is priority boosting needed? — To periodically reset all processes to the top queue and prevent starvation of long-running tasks.