21. MLFQ — Multi-Level Feedback Queue

Problem it solves: approximate SJF (favor short jobs) without knowing burst times upfront — by learning process behavior over time.

Structure: multiple queues with increasing quantum sizes — e.g., Q0 (highest priority, 8ms) → Q1 (16ms) → Q2 (lowest, often FCFS, 32ms). Higher-priority queues always run first.

Core rules:

1. New process enters at the top (Q0).
2. Uses its full quantum → demoted (looks CPU-bound).
3. Yields before quantum expires → stays or promoted (looks I/O-bound/interactive).
4. After a period S, everyone is boosted back to Q0 (prevents starvation).

The cheating problem: a process can voluntarily yield just before its quantum expires to stay in a high-priority queue. Fix: track total CPU time accumulated at a level, not just per-slice, and demote once the full quantum's worth is used regardless of how it was split.

---