Intuition The big idea (WHY MLFQ exists)We want a scheduler that is good for interactive jobs (low response time) and fair to long CPU-bound jobs (good turnaround) — without knowing in advance how long each job will run.
The trick: learn each job's behaviour by watching it . If a job keeps using its whole time slice, it looks CPU-bound, so push it down. If a job gives up the CPU early (waiting for I/O / keyboard), it looks interactive, so keep it near the top.
MLFQ is adaptive priority built from a stack of round-robin queues.
A scheduler with multiple ready queues , each at a different priority level (Q0 = highest). The basic rules:
Rule 1: If Priority ( A ) > Priority ( B ) \text{Priority}(A) > \text{Priority}(B) Priority ( A ) > Priority ( B ) A A A Rule 2: If Priority ( A ) = Priority ( B ) \text{Priority}(A) = \text{Priority}(B) Priority ( A ) = Priority ( B ) Round Robin (using that level's time quantum).Rule 3: A new job enters at the highest priority (top queue) — optimistic assumption: it might be interactive/short .Rule 4 (Demotion): If a job uses up its entire time allotment at a level (whether in one go or across pieces), its priority is reduced (move down one queue).Rule 5 (Promotion / Priority Boost): After some time period S S S move ALL jobs to the topmost queue ("boost").
Lower queues usually get longer time quanta (CPU-bound jobs run rarely but in big chunks → fewer context switches).
Intuition Reasoning through the rules
Rule 3 (start at top): We don't know if a job is short. Assume it is. If we're wrong, it'll drift down naturally. Cheap to be optimistic.Rule 4 (demotion): A job that eats its whole quantum is acting CPU-bound. Demote it so it stops hogging the fast lane. This is how MLFQ approximates SJF without knowing run times.Rule 5 (boost): Without boost, two problems appear:
Starvation: too many interactive jobs at top → long jobs at bottom never run.Behaviour change: a job that was CPU-bound becomes interactive later — but it's stuck at the bottom. The boost gives it a fresh chance.
Worked example Why the "whole allotment" version of Rule 4 (not "whole single slice")Naive Rule 4: demote only if you use a full time slice with no yield.
Gaming attack: a sneaky process runs for 99 % 99\% 99% Fix: track total time used at a level (the allotment ). Once cumulative usage at that level ≥ \ge ≥ regardless of how many times it yielded . Now gaming gives no advantage.
Worked example Example 1 — A short interactive jobQueues: Q0 (quantum 8 ms, allotment 8), Q1 (q 16), Q2 (q 32). Job needs 6 ms of CPU then exits.
Step: enters Q0 (Rule 3). Why? New jobs assumed interactive.Step: runs 6 ms, finishes before quantum ends. Why no demotion? It used 6 < 8 6 < 8 6 < 8 Result: great response time. MLFQ favoured it correctly.
Worked example Example 4 — Job changes phaseA job is CPU-bound (compiles) then becomes interactive (waits on user). It got demoted to Q2 during compile.
At next boost it returns to Q0 and is treated as interactive again — correct , because its behaviour changed. Why Rule 5 also fixes this: priority should reflect recent behaviour, not ancient history.
Common mistake Steel-man the common errorsMistake A — "Demote when a single time slice is fully used."
Why it feels right: "full slice = greedy" sounds reasonable.
Why it's wrong: it's gameable (sleep just before slice end to reset). Fix: count cumulative allotment per level.
Mistake B — "Boost is just to avoid starvation."
Why it feels right: that's its most visible job.
Why incomplete: it also lets a job that changed from CPU-bound to interactive regain priority. Fix: remember both purposes.
Mistake C — "Promotion happens one queue at a time when a job waits long."
Why it feels right: symmetry with single-step demotion.
Why wrong (classic OSTEP MLFQ): the standard promotion is a global priority boost to the top , not gradual. (Some variants do age-based single-step promotion — know which one your course uses!) Fix: default = boost-to-top every S S S
Mistake D — "All queues use the same quantum."
Fix: lower queues typically have larger quanta to reduce context-switch overhead for batch jobs.
Recall Feynman: explain to a 12-year-oldImagine a line of slides at a playground, stacked tall to short. New kids start on the tallest slide (fastest fun). If a kid hogs a slide too long, the guard makes them move to a lower, slower slide . Kids who slide quick and run off to do something else stay near the top. Every few minutes the guard blows a whistle and says "everybody back to the top slide! " so nobody is stuck at the bottom forever — and a kid who used to hog but now plays nicely gets another chance up high.
Mnemonic Remember the 5 rules"New jobs Start High, Hog = Sink, Whistle = Rise."
Start High → Rule 3
Hog (use allotment) = Sink → Rule 4 (demotion)
Whistle (period S S S
What priority does a new job enter MLFQ at, and why? Highest (top queue), Rule 3 — optimistic assumption it may be short/interactive; if wrong it drifts down.
What triggers demotion in MLFQ (correct version)? When a job exhausts its total time allotment at a level (cumulative, across pieces), not just a single slice.
Why is "demote only on full single slice" a bad rule? It's gameable — a job can yield just before slice end, never "use a full slice", and starve others.
What is the priority boost (Rule 5)? Every period S, move ALL jobs back to the top queue.
Name the two problems the boost solves. (1) Starvation of low-priority jobs; (2) jobs whose behaviour changed from CPU-bound to interactive regaining priority.
Why do lower queues use larger time quanta? CPU-bound jobs run rarely but in big chunks → fewer context switches, better throughput.
Worst-case starvation bound with boost period S? Approximately S — at the next boost any job returns to the top.
How does MLFQ approximate SJF without knowing run times? By observing behaviour: jobs that consume full allotments are demoted (treated as long); short/interactive jobs stay high.
Within a single queue level, how are equal-priority jobs scheduled? Round Robin using that level's quantum (Rule 2).
Round-Robin Scheduling — used within each MLFQ level.Shortest Job First (SJF) — MLFQ approximates it without prior knowledge.Priority Scheduling — MLFQ = adaptive, multi-level priority.Starvation and Aging — boost = aging mechanism.Context Switch Overhead — motivates larger low-queue quanta.CPU-bound vs I/O-bound processes — the behaviour MLFQ detects.Time Quantum / Time Slice — tuning knob per level.
Schedule without knowing job length
Rule 3: new job starts at top
Rule 4: demote on full allotment
Interactive jobs stay high
CPU-bound jobs drift down
Lower queues get longer quanta
Intuition Hinglish mein samjhoMLFQ ka core idea simple hai: humein ek scheduler chahiye jo interactive jobs (jaise typing, clicking) ko fast response de, aur saath hi long CPU-heavy jobs ko bhi fairly chalaye — bina pehle se jaane ki kaunsa job kitna lamba hai. Iske liye MLFQ multiple queues banata hai, har queue ka apna priority level hota hai (Q0 sabse upar = sabse high priority). Naya job hamesha top queue se start hota hai (Rule 3) — optimistic assumption ki shayad ye chhota/interactive ho.
Ab observe karke seekhna: agar koi job apna pura time allotment kha jata hai (matlab CPU greedy hai), to use niche bhej dete hain (Rule 4, demotion). Important point — demotion "ek single slice full use" pe nahi, balki cumulative allotment pe hona chahiye, warna ek chalu process slice khatam hone se theek pehle thoda I/O karke system ko game kar sakta hai aur niche kabhi nahi jayega. Cumulative counting se ye cheating bandh ho jati hai.
Promotion ka sabse standard tareeka hai priority boost (Rule 5): har S time units ke baad saare jobs ko wapas top queue me utha do. Iska double fayda hai — ek to bottom wale jobs starve nahi karte, aur doosra agar koi job pehle CPU-bound tha lekin ab interactive ban gaya hai (jaise compile khatam, ab user input ka wait), to use dobara high priority mil jati hai. Worst-case starvation lagbhag S tak limited rehta hai. Lower queues me quantum bada rakhte hain taaki long jobs kam baar but bade chunks me chale aur context-switch overhead kam ho. Mnemonic yaad rakho: "Start High, Hog = Sink, Whistle = Rise."
