OS Notes
Complete guide to Multilevel Feedback Queue (MLFQ) scheduling algorithm covering queue promotion and demotion, aging, gaming prevention, and how modern OS implement MLFQ concepts.
Introduction
Imagine a restaurant that initially seats everyone in the main dining area. If you eat quickly and leave, great — you were an efficient customer. But if you are still eating after 30 minutes, you get moved to a slower-service section. If you are still there after an hour, you are moved to the self-service area. The restaurant is adapting to your behavior in real time. This is the essence of the Multilevel Feedback Queue.
The Multilevel Feedback Queue (MLFQ) is the most sophisticated and widely used CPU scheduling algorithm. Unlike the basic multilevel queue where processes are permanently assigned to a queue, MLFQ allows processes to move between queues based on their actual CPU usage patterns. Processes that use too much CPU time get demoted to lower-priority queues, while processes that have waited too long get promoted to higher-priority queues.
Why MLFQ Exists
MLFQ solves two fundamental problems:
- SJF requires knowing burst times in advance — MLFQ learns process behavior by observing it
- Static multilevel queues cannot adapt — MLFQ responds to changing process behavior
The genius of MLFQ is that it approximates SJF without requiring any advance knowledge of burst times. Short interactive processes naturally stay in high-priority queues (they finish before their quantum expires), while long CPU-bound processes naturally drift to lower-priority queues.
How MLFQ Works — The Rules
Basic Rules
| Rule 1 | If Priority(A) > Priority(B), A runs (B does not) |
| Rule 2 | If Priority(A) == Priority(B), A and B run in Round Robin |
| Rule 3 | New processes enter at the highest priority queue |
| Rule 4a | If a process uses its ENTIRE time quantum, demote it (move down one queue) |
| Rule 4b | If a process gives up the CPU before quantum expires, stay at same level |
Queue Structure
| Queue 0 (Highest Priority) | Round Robin, quantum = 8ms |
| │ If process uses full 8ms | demote to Queue 1 |
| │ If process blocks for I/O before 8ms | stays in Queue 0 |
| Queue 1 (Medium Priority) | Round Robin, quantum = 16ms |
| │ If process uses full 16ms | demote to Queue 2 |
| │ If process blocks for I/O before 16ms | stays in Queue 1 |
| Queue 2 (Low Priority) | Round Robin, quantum = 32ms |
| │ If process uses full 32ms | demote to Queue 3 |
| Queue 3 (Lowest Priority) | FCFS (or very large quantum) |
Detailed Example
Consider three processes:
- P1: Interactive (short CPU bursts of 3ms between I/O)
- P2: CPU-bound (needs 40ms total CPU time)
- P3: Mixed (starts interactive, becomes CPU-bound)
Execution Trace
| Time 0 | All three enter Queue 0 (highest priority) |
| P1 runs for 3ms, does I/O | stays in Queue 0 ✓ |
| P2 runs for 8ms (full quantum) | demoted to Queue 1 ↓ |
| P3 runs for 5ms, does I/O | stays in Queue 0 ✓ |
| Time ~15 | Queue 0 has P1, P3. Queue 1 has P2. |
| P1 runs for 2ms, does I/O | stays in Queue 0 ✓ |
| P3 runs for 8ms (full quantum) | demoted to Queue 1 ↓ |
| Time ~25 | Queue 0 has P1. Queue 1 has P2, P3. |
| P1 keeps running short bursts | always in Queue 0 (fast response!) |
| P2 runs 16ms in Queue 1 | demoted to Queue 2 ↓ |
| P3 runs 16ms in Queue 1 | demoted to Queue 2 ↓ |
| Result | P1 (interactive) gets instant response time |
The Starvation Problem and Solution: Priority Boost
Without intervention, CPU-bound processes in low queues might starve if interactive processes keep the higher queues busy. The solution is periodic priority boost:
Rule 5: After some time period S, move ALL processes to the topmost queue.
This periodic reset prevents starvation and also handles processes whose behavior changes over time (a CPU-bound process that becomes interactive gets a fresh start).
Preventing Gaming
A clever process could game the system by voluntarily giving up the CPU just before its quantum expires (say, doing a tiny unnecessary I/O at 7.9ms in an 8ms quantum). It would stay in the high-priority queue forever despite being CPU-bound.
Solution: Track cumulative CPU time (allotment), not just per-quantum usage.
For example, if Queue 0's allotment is 8ms and a process does four 2ms bursts (with I/O between each), it has used 8ms total and gets demoted — even though it never used a full quantum in one go.
MLFQ in Real Operating Systems
Solaris
Solaris uses a Time Sharing (TS) scheduling class based on MLFQ with 60 priority levels. The scheduler tables define, for each priority level: the time quantum, the new priority after using the full quantum (demotion), and the new priority after sleeping (promotion).
Windows
Windows uses a simplified MLFQ concept. Threads have base priorities that can be temporarily boosted (e.g., when a window receives input focus, when I/O completes, or when a thread has been starved for 3-4 seconds).
Linux CFS
Linux's Completely Fair Scheduler is conceptually different (it uses virtual runtime rather than multiple queues) but achieves similar goals — interactive processes naturally get better response times because they accumulate less virtual runtime.
Tuning MLFQ Parameters
The administrator can tune several parameters:
| Parameter | Effect of Increase |
|---|---|
| Number of queues | Finer granularity of priority levels |
| Time quantum per queue | Fewer context switches, slower demotion |
| Boost interval (S) | Less frequent recovery from starvation |
| Time allotment | Slower demotion, more time per level |
Real-World Analogy
MLFQ is like a gym with different sections. New members start in the premium section with personal trainers (highest priority, small quantum). If you consistently use the equipment for long sessions, you get moved to the self-service section (lower priority, larger quantum). But every month (priority boost), everyone gets a free week back in the premium section. This ensures that members whose needs change (maybe they recovered from an injury and now need short sessions) get re-evaluated.
Key Takeaways
- MLFQ allows processes to move between priority queues based on observed behavior
- Short/interactive processes stay in high-priority queues (great response time)
- Long/CPU-bound processes drift to lower queues (fair but lower priority)
- Periodic priority boost prevents starvation and handles behavior changes
- Cumulative time allotment prevents gaming of the system
- MLFQ approximates SJF without requiring advance knowledge of burst times
- Nearly all modern general-purpose OS use MLFQ concepts in their schedulers
- Tunable parameters allow administrators to balance responsiveness vs throughput
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Multilevel Feedback Queue Scheduling.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, cpu, scheduling, multilevel, feedback
Related Operating Systems Topics