MLQ vs MLFQ CPU Scheduling Algorithms

CSS Optional — Paper-II, Section-A · P-II.III · Listed as a standalone topic in the CS-for-CSS book's OS chapter (asked directly in 2016, 6 marks; and again as a queue-flowchart question in 2019). The full Gantt-chart numericals for both live on [CPU Scheduling Algorithms — Deep Dive & Solved Numericals]; this page is the comparison answer itself, written the way the examiner wants it.

1. The One-Line Difference

Multilevel Queue (MLQ): a process is assigned to a queue permanently at creation — it can never move.

Multilevel Feedback Queue (MLFQ): a process can be promoted or demoted between queues at runtime based on its observed CPU behaviour.

Everything else — the strengths, the weaknesses, the starvation story — follows from that one structural difference. Open any answer with this sentence.

2. Multilevel Queue (MLQ)

The ready queue is split into several separate, permanent queues. Each queue holds one class of process and runs its own scheduling algorithm internally:

• System processes — highest priority
• Interactive (foreground) processes — typically Round Robin, since response time matters
• Interactive editing processes
• Batch (background) processes — typically FCFS, since throughput matters more than response
• Student/low-priority processes — lowest

graph TD
    A["New process"] --> B{"Classified once,
by type"}
    B --> Q0["Q0: System (highest)"]
    B --> Q1["Q1: Interactive - RR"]
    B --> Q2["Q2: Batch - FCFS (lowest)"]
    Q0 --> CPU["CPU"]
    Q1 --> CPU
    Q2 --> CPU

Scheduling between queues is done one of two ways:

1. Fixed-priority preemptive — a lower queue runs only when every higher queue is empty (the common textbook assumption, and the one that causes starvation).
2. Time-slicing between queues — each queue gets a fixed share of CPU time (e.g. 80% foreground, 20% background), which bounds starvation but is less responsive.

Key property: classification is permanent. A batch job that turns out to be short still cannot be moved up; an interactive job that turns out to be CPU-hungry still cannot be moved down.

3. Multilevel Feedback Queue (MLFQ)

Same multi-queue structure, but with feedback — the scheduler watches how each process behaves and moves it:

• All new processes enter the highest queue (Q0).
• A process that uses its full quantum without finishing is demoted one level (it is evidently CPU-bound).
• A process that voluntarily gives up the CPU for I/O before its quantum expires stays at its level (some variants promote it) — it is evidently I/O-bound and interactive.
• Lower queues get longer quanta (e.g. Q0=2, Q1=4, Q2=FCFS), so CPU-bound jobs run in fewer, longer bursts and waste less on context switching.
• Aging promotes a process that has waited too long in a lower queue back upward — this is the built-in anti-starvation mechanism MLQ lacks.

graph TD
    A["New process"] --> Q0["Q0: RR quantum=2"]
    Q0 -->|"used full quantum"| Q1["Q1: RR quantum=4"]
    Q1 -->|"used full quantum"| Q2["Q2: FCFS"]
    Q2 -->|"aging: waited too long"| Q1
    Q1 -->|"aging"| Q0
    Q0 -->|"blocks for I/O early"| Q0

Effect: short and interactive jobs finish while still near the top (excellent response time); long CPU-bound jobs sink to the bottom and run efficiently in long slices — without the scheduler ever needing to know burst times in advance. That last clause is the strongest single point you can make for MLFQ, since it is exactly what SJF/SRTF cannot do.

4. Head-to-Head Comparison (the table to reproduce in the exam)

5. Pros and Cons (if the question asks for them separately)

MLQ — advantages: low scheduling overhead; predictable, clearly separated service classes; simple to implement and reason about.

MLQ — disadvantages: inflexible; starvation of lower queues; a misclassified process is stuck for its whole lifetime; poor adaptation to changing workload.

MLFQ — advantages: adapts automatically to process behaviour; favours short and interactive jobs without knowing burst times in advance; aging prevents starvation; the most general of the scheduling schemes — it can be configured to imitate FCFS, RR or MLQ.

MLFQ — disadvantages: highest implementation complexity; performance depends heavily on parameter tuning; extra runtime overhead from monitoring and moving processes; a poorly tuned scheme can thrash processes between queues.

6. Parameters That Define an MLFQ Scheme

Worth listing if the question asks "what must be specified to define an MLFQ scheduler?":

1. The number of queues.
2. The scheduling algorithm used within each queue.
3. The method used to decide when to promote a process (the aging rule).
4. The method used to decide when to demote a process.
5. The method used to decide which queue a process enters when it needs service.

---

📐 Worked Numericals

Both algorithms are worked through full Gantt charts — MLQ with a foreground/background split, MLFQ with three queues and two demotions — on the scheduling deep-dive page:

🎯 CSS Exam Angle

This is a comparison question, so lead with the one-line structural difference (Section 1), then give the table, then close with one sentence of judgement — e.g. "MLQ suits systems with a stable, well-understood process taxonomy; MLFQ suits general-purpose systems with unpredictable workloads, which is why modern UNIX and Windows schedulers are MLFQ-derived." Examiners reward the closing judgement sentence; a bare table often caps out at half marks. If the question says "with the help of a diagram" or "draw a flow chart" (2019), the two mermaid-style queue diagrams above are what to reproduce — the arrows showing demotion and aging are the whole point of the MLFQ one.

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• Only MLFQ allows movement between queues. MLQ assignment is permanent for the process's entire lifetime. This is the single most-tested distinction and the one most often reversed.
• In MLFQ, demotion happens only when a process uses its FULL quantum without finishing — a process that blocks for I/O early is not demoted (and in some variants is promoted).
• Lower MLFQ queues get LONGER quanta, not shorter — the logic is that CPU-bound jobs should run in fewer, longer bursts to cut context-switch overhead. Many students assume the opposite.
• Aging belongs to MLFQ, not MLQ — plain MLQ has no anti-starvation mechanism at all under fixed-priority scheduling.
• MLQ is not the same as simple Priority Scheduling — priority scheduling has one queue ordered by priority number; MLQ has several physically separate queues, each possibly running a different algorithm internally.
• MLFQ does not need burst times in advance — saying it "picks the shortest job" is wrong; it infers short jobs from behaviour.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-II · Q4(b) · 6 marks

Q. What are the pros and cons of Multilevel Queue Scheduling and Multilevel Feedback Queue Scheduling?

Ans.

• Multilevel queue (MLQ): the ready queue is split into fixed queues by process type (system, interactive, batch). Each queue has its own algorithm, and queues are scheduled by fixed priority or time-slicing. A process stays in its queue permanently.
  • Pros: low scheduling overhead and different policies per type of process.
  • Cons: inflexible, and low-priority queues can starve.
• Multilevel feedback queue (MLFQ): processes can move between queues based on behaviour. CPU-hungry processes sink to lower queues, and I/O-bound or interactive ones stay high. Ageing promotes long-waiting processes.
  • Pros: adaptive, favours short and interactive jobs, avoids starvation with ageing, and needs no prior knowledge of burst times.
  • Cons: complex to design and tune (number of queues, quantum sizes, promotion and demotion rules), and it has more overhead.

2023 · Paper-II · Q5(a) · 10 marks

Q. I/O-bound programs spend more time waiting for I/O than using the processor, and processor-bound programs are the opposite. A short-term scheduler favours programs that have used little processor time in the recent past. Explain why this favours I/O-bound programs yet does not permanently deny processor time to processor-bound programs.

Ans.

• Why I/O-bound programs are favoured: they use the CPU in short bursts and then block for I/O, so their recent CPU usage is low and they get high priority. When their I/O completes they run at once, issue their next request quickly and keep the I/O devices busy (high utilisation, good response).
• Why processor-bound programs are not starved: they use their whole time slice, so their recent usage is high and their priority drops. But I/O-bound processes are blocked most of the time, so whenever no higher-priority process is ready, the CPU goes to the processor-bound one.
• Ageing and decay: recent-usage counters decay over time, so a process that waits long sees its usage fall and its priority rise again. So it eventually runs.
• Result: good interactive response and device utilisation without permanent starvation.

2026 · Paper-II · Q5 · 20 marks

Q. Modern operating systems balance efficiency and fairness while scheduling processes. Critically evaluate how multilevel feedback queues evolve process priorities over time. Discuss how this design influences CPU utilisation and starvation compared to simpler scheduling algorithms.

Ans.

• Structure: several ready queues Q0 (highest priority, small quantum, e.g. 8 ms), Q1 (larger quantum, e.g. 16 ms), …, Qn (lowest, FCFS). A process in a lower queue runs only when all higher queues are empty.
• How priorities evolve:
  • Entry: every new process starts in the top queue.
  • Demotion: if it uses its entire quantum, it is treated as CPU-bound and moved down one queue (longer quantum, lower priority).
  • Retention: if it blocks for I/O or yields before the quantum ends, it stays in (or returns to) the high queue, so interactive jobs stay responsive.
  • Promotion (ageing / priority boost): a process that waits too long, or all processes periodically, are moved up. This prevents starvation and handles a process that changes behaviour (CPU-bound to interactive).
• Effect on CPU utilisation: short and I/O-bound jobs finish quickly and keep devices busy, while long CPU-bound jobs fill the remaining CPU time at low priority with fewer context switches (larger quanta). Utilisation is high.
• Comparison with simpler algorithms:

• Starvation: simple priority scheduling can starve low-priority jobs forever. MLFQ avoids this with ageing or boosts, though pure MLFQ without them can also starve.
• Critical evaluation: MLFQ balances efficiency (responsiveness, utilisation) and fairness (no starvation), but its many parameters (number of queues, quanta, boost interval) need careful tuning, and users can exploit it. Modern systems (Windows, BSD, older Linux) use MLFQ-like designs.