Multi-level feedback queue (MLFQ) — promotion, demotion rules

4.2.11 · Coding › Operating Systems

WHAT it is

Neeche waali queues mein aam taur par zyada lambe time quanta hote hain (CPU-bound jobs kam baar chalti hain par bade chunks mein → kam context switches).

WHY each rule exists (HOW it solves a problem)

Figure — Multi-level feedback queue (MLFQ) — promotion, demotion rules

A small "formula" for behaviour (derive, don't memorize)

Worked Examples

Common mistake Steel-man the common errors

Mistake A — "Jab ek single time slice poora use ho jaaye tab demote karo." Kyun sahi lagta hai: "full slice = greedy" reasonable lagta hai. Kyun galat hai: yeh gameable hai (slice end se thoda pehle sleep lo reset ke liye). Fix: cumulative allotment per level count karo.

Mistake B — "Boost sirf starvation se bachne ke liye hai." Kyun sahi lagta hai: yeh iska sabse visible kaam hai. Kyun incomplete hai: yeh woh job bhi lete hai jo CPU-bound se interactive mein badal gayi thi, taaki woh priority regain kar sake. Fix: dono purposes yaad rakho.

Mistake C — "Promotion ek queue at a time hoti hai jab job zyada der wait kare." Kyun sahi lagta hai: single-step demotion ke saath symmetry. Kyun galat hai (classic OSTEP MLFQ): standard promotion ek global priority boost to the top hai, gradual nahi. (Kuch variants age-based single-step promotion karte hain — dekho kaun sa aapke course mein hai!) Fix: default = har $S$ mein boost-to-top.

Mistake D — "Saari queues same quantum use karti hain." Fix: lower queues mein typically zyada bade quanta hote hain taaki batch jobs ke liye context-switch overhead kam ho.

Recall Feynman: explain to a 12-year-old

Socho ek playground mein slides ki line hai, tall se short tak stack ki hui. Naaye bachche sabse unchi slide par shuru karte hain (sabse zyada masti). Agar koi bachcha slide zyada der tak occupy karta hai, toh guard use neeche, dheemi slide par bhej deta hai. Jo bachche jaldi slide karte hain aur kuch aur karne bhaag jaate hain woh top ke paas rehte hain. Har kuch minutes mein guard seeti bajaata hai aur kehta hai "sab top slide par wapas!" taaki koi bottom par stuck na rahe — aur jo bachcha pehle hog karta tha par ab ache se khel raha hai use upar dobara chance milta hai.

Flashcards

Nayi job MLFQ mein kis priority par enter karti hai, aur kyun?

Sabse zyada (top queue), Rule 3 — optimistic assumption ki yeh short/interactive ho sakti hai; agar galat hue toh neeche drift kar jaayegi.

MLFQ mein demotion kya trigger karta hai (correct version)?

Jab koi job ek level par apna total time allotment exhaust kar le (cumulative, tukdon mein), na ki sirf ek slice.

"Sirf ek poori single slice par demote karo" ek buri rule kyun hai?

Yeh gameable hai — koi job slice end se pehle yield kar sakti hai, kabhi "poora slice use" nahi karti, aur doosron ko starve karti hai.

Priority boost (Rule 5) kya hai?

Har period S mein, SAARI jobs ko top queue par wapas move karo.

Boost jo do problems solve karta hai unke naam batao.

(1) Low-priority jobs ka starvation; (2) jin jobs ka behaviour CPU-bound se interactive mein badal gaya unka priority regain karna.

Lower queues larger time quanta kyun use karti hain?

CPU-bound jobs kam baar chalti hain par bade chunks mein → kam context switches, better throughput.

Boost period S ke saath worst-case starvation bound kya hai?

Approximately S — agle boost par koi bhi job top par wapas aa jaati hai.

MLFQ run times jaane bina SJF ko kaise approximate karta hai?

Behaviour observe karke: jo jobs poore allotments consume karti hain unhe demote kiya jaata hai (long maani jaati hain); short/interactive jobs upar rehti hain.

Ek single queue level ke andar, equal-priority jobs ko kaise schedule kiya jaata hai?

Us level ke quantum ka use karke Round Robin (Rule 2).

Connections

Round-Robin Scheduling — har MLFQ level ke andar use hota hai.
Shortest Job First (SJF) — MLFQ bina prior knowledge ke ise approximate karta hai.
Priority Scheduling — MLFQ = adaptive, multi-level priority.
Starvation and Aging — boost = aging mechanism.
Context Switch Overhead — lower-queue ke bade quanta ki wajah.
CPU-bound vs I/O-bound processes — woh behaviour jo MLFQ detect karta hai.
Time Quantum / Time Slice — har level par tuning knob.