Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 66 ยท CPU Scheduling

Multilevel Queue and Feedback Queue Scheduling

Learn multilevel queue and multilevel feedback queue scheduling: separate queues per process class, demotion and priority boosts, with a runnable MLFQ simulator.

So far one algorithm handled every process. But a real system runs very different kinds of work at once: a user clicking in an editor, a background backup, a system daemon. They deserve different treatment. Interactive tasks need fast responses; batch jobs need throughput. Running them all through one policy forces a compromise.

Multilevel queue (MLQ) scheduling splits the ready queue into several separate queues, each with its own policy. Multilevel feedback queue (MLFQ) scheduling goes further and lets processes move between queues based on their behavior. MLFQ is the design behind the schedulers of many real systems (classic UNIX variants, Windows, macOS), and it solves the problem of SJF (not knowing burst lengths) by learning them from observation.

Multilevel queue

Several queues Processes are sorted by type.
Own algorithm each RR for interactive, FCFS for batch.
Fixed membership A process stays in its queue.

Between queues, strict priority or time slices decide who runs.

1 / 2

Multilevel queue scheduling

Processes are permanently assigned to one queue based on a property such as type, memory need or importance. A typical layout, from highest to lowest priority:

  1. System processes
  2. Interactive processes (RR with a small quantum)
  3. Batch processes (FCFS)
  4. Student or low-priority jobs

There also has to be scheduling between the queues:

  • Fixed-priority: serve queue 1 until empty, then queue 2, and so on. A newly arriving process in a higher queue preempts a lower one. Simple, but lower queues can starve.
  • Time-slicing between queues: each queue gets a share of CPU time, for example 80% for the interactive queue (RR) and 20% for the batch queue (FCFS).

Advantage: low scheduling overhead and tailored treatment. Disadvantage: inflexible, since a process cannot change queues, and a long-running interactive-looking job can monopolize a high queue.

Multilevel feedback queue

MLFQ lets processes move between queues. The idea: separate processes by their CPU burst behavior without knowing it in advance.

A typical set of rules:

  1. A new process enters the top queue (highest priority, shortest quantum).
  2. If it uses its full quantum, it is demoted to the next lower queue (longer quantum, lower priority). CPU-bound processes sink.
  3. If it gives up the CPU early (blocks for I/O), it stays at its level (or is promoted). I/O-bound and interactive processes stay near the top.
  4. Always run the highest non-empty queue; within a queue use RR (the last queue often uses FCFS).
  5. Priority boost: every so often (say every second), move all processes to the top queue. This stops starvation and handles processes whose behavior changes (a CPU-bound phase followed by an interactive phase).

An MLFQ is defined by: the number of queues, the algorithm and quantum of each queue, when to demote or promote, how to boost, and which queue a new process starts in. It is the most general scheduler, and the most complex to tune.

flowchart TB
    new["New process"] --> Q0
    Q0["Queue 0: RR, quantum 2 (highest)"] -- "used full quantum" --> Q1
    Q1["Queue 1: RR, quantum 4"] -- "used full quantum" --> Q2
    Q2["Queue 2: FCFS (lowest)"]
    Q2 -. "priority boost" .-> Q0

Higher queues run first; CPU-hungry processes drift downward; a periodic boost lifts them back.

An MLFQ simulator

The simulator below has three queues with quanta 2, 4 and then FCFS-style (quantum 100). Processes: a long CPU-bound job, a medium job, and a short "interactive" job arriving a bit later. Watch what happens to each.

Python Multilevel feedback queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how SHORT, arriving at time 5 into the top queue, runs almost immediately while the long jobs sink to lower queues. A user-interactive process gets low latency without the scheduler ever being told how long it needs.

MLQ with fixed priority between queues

Here is a minimal multilevel queue: two queues (interactive with RR, batch with FCFS) and strict priority between them. Batch jobs only run when no interactive job is ready.

Python Two-queue MLQ

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Batch jobs start only after both interactive jobs finish. If new interactive jobs kept arriving, the batch queue would starve, which is the MLQ's main weakness.

MLQ vs. MLFQ

Multilevel queue Multilevel feedback queue
Movement between queues None Yes, by behavior
Needs to know process type Yes, at creation No, it learns
Starvation Possible Avoided by boosting or aging
Flexibility Low High
Complexity Low High to tune
Approximates A fixed class policy SJF without knowing bursts

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a pure multilevel queue, can a process move from one queue to another?

    Queue membership is fixed in MLQ. Movement between queues is what distinguishes MLFQ.
  2. 2. In a typical MLFQ, what happens to a process that uses its entire time quantum?

    Using the full quantum suggests a CPU-bound process, which sinks to lower queues.
  3. 3. Why does MLFQ use a periodic priority boost?

    Lifting all processes to the top queue gives starved jobs a turn and re-learns behavior.
  4. 4. Which description best fits the typical lowest queue in an MLFQ?

    CPU-bound jobs drift down and run with long slices when nothing more important is waiting.
  5. 5. What problem of SJF does MLFQ avoid?

    By observing behavior (quantum used or not) MLFQ approximates SJF without knowing burst times.

Summary

  • MLQ separates processes into fixed queues, each with its own policy, plus a rule between queues (strict priority or time shares).
  • MLFQ moves processes between queues: full quantum means demotion; early yield keeps high priority; boosts prevent starvation.
  • MLFQ approximates SJF without burst-time knowledge and favors interactive work.
  • It is flexible but has many parameters to tune.

Next: Starvation, Aging and the Dispatcher