Chapter 15 of 38

Multilevel Queue & Feedback Queue Scheduling

Think about the security check at an airport. There is a priority lane for crew and business-class passengers, a regular lane for everyone else, and sometimes a separate lane for families with small children. Each lane has its own line and its own pace, and staff decide which lane gets served next.

A real operating system faces the same situation. Some processes are interactive (a text editor waiting for your keystrokes), some are system services, and some are long background jobs (a video export, a backup). Treating them all with one algorithm is a poor fit. So OS designers split the ready queue into several queues.

Multilevel Queue (MLQ) scheduling divides processes into fixed classes, each with its own ready queue and its own scheduling algorithm, and then schedules between the queues. Multilevel Feedback Queue (MLFQ) scheduling also uses several queues, but lets processes move between them based on how they actually behave.

This chapter brings together everything from the previous scheduling chapters. MLQ combines Priority Scheduling (between queues) with Round Robin or FCFS (inside each queue). MLFQ goes one step further and approximates SJF without knowing any burst times. Its core idea, first used in the CTSS system in the early 1960s, still shapes many general-purpose schedulers today.


Multilevel Queue (MLQ) Scheduling

In MLQ, each process is permanently assigned to one queue when it is created, based on some property such as process type, memory size or priority.

Highest priority
   ┌──────────────────────────────┐
Q0 │ System processes    (RR)     │ → →
   ├──────────────────────────────┤
Q1 │ Interactive processes (RR)   │ → →      ┌─────┐
   ├──────────────────────────────┤   ───→   │ CPU │
Q2 │ Batch processes     (FCFS)   │ → →      └─────┘
   └──────────────────────────────┘
Lowest priority

A process never moves from one queue to another.

Each queue can use the algorithm that suits its processes:

  • Interactive (foreground) queue: Round Robin, for good response time.

  • Batch (background) queue: FCFS, because response time does not matter and FCFS has the least overhead.

Scheduling Between the Queues

Having several queues raises a new question: which queue gets the CPU? There are two common answers.

Method

How it works

Downside

Fixed-priority preemptive

A lower queue runs only when all higher queues are empty. If a process arrives in a higher queue, it preempts a running lower-queue process.

Lower queues can starve

Time slicing between queues

Each queue gets a fixed share of CPU time, for example 80% for the foreground queue (RR among its processes) and 20% for the background queue (FCFS).

Shares are fixed; high-priority work may wait while the low queue uses its slice


Example 1: Multilevel Queue

Two queues, fixed-priority preemptive between them:

  • Q0 (high priority, interactive): Round Robin with q = 2

  • Q1 (low priority, batch): FCFS

Process

Arrival Time

Burst Time

Queue

P1

0

6

Q1

P2

1

4

Q0

P3

2

3

Q0

P4

3

5

Q1

P5

11

2

Q0

One more rule is needed: when a Q1 process is preempted by a Q0 arrival, where does it go? We keep it at the head of Q1, so it resumes before other Q1 processes. That is natural for an FCFS queue, and it is also how Linux treats a preempted SCHED_FIFO thread.

Step-by-step trace

t = 0  : Q0 = []        Q1 = [P1]       → P1 runs (Q0 empty)
t = 1  : P2 arrives in Q0                → P1 preempted (rem 5, stays at head of Q1)
         Q0 = [P2]      Q1 = [P1]       → P2 runs 1-3 (quantum 2, rem 2)
t = 3  : P3 (arr 2) is in Q0, P4 (arr 3) joins Q1
         Q0 = [P3, P2]  Q1 = [P1, P4]   → P3 runs 3-5 (rem 1)
t = 5  : Q0 = [P2, P3]                   → P2 runs 5-7, done
t = 7  : Q0 = [P3]                       → P3 runs 7-8, done
t = 8  : Q0 = []        Q1 = [P1, P4]   → P1 resumes (rem 5)
t = 11 : P5 arrives in Q0                → P1 preempted (rem 2, head of Q1)
         P5 runs 11-13, done
t = 13 : Q0 = []        Q1 = [P1, P4]   → P1 runs 13-15, done
t = 15 : Q1 = [P4]                       → P4 runs 15-20, done
|  P1  |  P2  |  P3  |  P2  |  P3  |  P1  |  P5  |  P1  |  P4  |
0      1      3      5      7      8      11     13     15     20

Process

Queue

AT

BT

CT

TAT

WT

P1

Q1

0

6

15

15

9

P2

Q0

1

4

7

6

2

P3

Q0

2

3

8

6

3

P4

Q1

3

5

20

17

12

P5

Q0

11

2

13

2

0

Average TAT = 46 / 5 = 9.2
Average WT  = 26 / 5 = 5.2
Average WT of Q0 processes (P2, P3, P5) = 5 / 3 ≈ 1.67
Average WT of Q1 processes (P1, P4)     = 21 / 2 = 10.5

The split averages tell the real story: the interactive queue waits very little, and the batch queue absorbs all the delay. That is exactly what MLQ is designed to do. But if Q0 processes kept arriving without a break, P4 would never run.

Problems With Plain MLQ

  • Starvation of lower queues under fixed-priority scheduling.

  • Inflexibility: the OS must classify every process correctly at creation time, and the classification never changes. A program that is interactive for a while and then starts heavy computation stays in the interactive queue and hurts everyone there. A batch job that becomes interactive stays stuck at the bottom.

Both problems are solved by letting processes move between queues.


Multilevel Feedback Queue (MLFQ) Scheduling

MLFQ uses the same stack of queues, but the queue a process is in is not fixed. The scheduler watches each process and moves it up or down based on its recent CPU usage. That observation is the "feedback".

The central idea:

MLFQ does not need to know how long a process will run. It learns from the past: processes that use a lot of CPU sink to lower-priority queues, and processes that use the CPU only briefly (typically interactive, I/O-bound ones) stay near the top.

The Rules of a Typical MLFQ

  1. Rule 1: A new process enters the highest-priority queue. (We give every newcomer the benefit of the doubt: maybe it is short.)

  2. Rule 2: A process in a higher queue always runs before any process in a lower queue. An arrival in a higher queue preempts a running lower-queue process.

  3. Rule 3: Processes in the same queue share the CPU in Round Robin. Lower queues usually get longer quanta, and the lowest queue often uses FCFS.

  4. Rule 4: If a process uses up its entire quantum at a level, it is demoted one level.

  5. Rule 5: If a process gives up the CPU before its quantum ends (for example, to wait for I/O), it stays at the same level.

  6. Rule 6 (priority boost): Every so often, move all processes back to the top queue. This prevents starvation and lets a process that changed behaviour be re-evaluated.

                 new process
                      ↓
Q0  (q = 4,  RR)   [ ... ]  ── uses full quantum ──┐
                                                    ↓
Q1  (q = 8,  RR)   [ ... ]  ── uses full quantum ──┐
                                                    ↓
Q2  (FCFS)         [ ... ]

Higher queue always preempts lower queue.
Periodically: boost everything back to Q0.

Why longer quanta at lower levels? Processes that reach the bottom are known to be CPU-hungry. Giving them longer slices means fewer context switches for them, and since they rarely interact with users, the longer wait between turns does not hurt anyone.

What Defines an MLFQ Scheduler?

An MLFQ is a family of schedulers, not one algorithm. A specific design is fixed by these parameters:

  • The number of queues

  • The scheduling algorithm (and quantum) for each queue

  • When to demote a process

  • When to promote a process (aging, priority boost)

  • Which queue a new process enters

This makes MLFQ the most general CPU scheduling scheme you will study, but also the most complex to tune.


Example 2: Multilevel Feedback Queue

Three queues:

  • Q0: Round Robin, q = 4 (highest priority)

  • Q1: Round Robin, q = 8

  • Q2: FCFS (lowest priority)

All processes enter Q0. Using a full quantum demotes a process one level. A higher queue preempts a lower one. (No priority boost happens in this short example.)

Process

Arrival Time

Burst Time

P1

0

17

P2

2

5

P3

4

2

P4

21

6

Step-by-step trace

t = 0  : Q0 = [P1]
         P1 runs 0-4 in Q0, uses full quantum (rem 13) → demoted to Q1
t = 4  : Q0 = [P2, P3]   Q1 = [P1]
         P2 runs 4-8 in Q0, uses full quantum (rem 1)  → demoted to Q1
t = 8  : Q0 = [P3]       Q1 = [P1, P2]
         P3 runs 8-10, needs only 2                     → done
t = 10 : Q0 = []         Q1 = [P1, P2]
         P1 runs 10-18 in Q1, uses full quantum 8 (rem 5) → demoted to Q2
t = 18 : Q1 = [P2]       Q2 = [P1]
         P2 runs 18-19, needs only 1                    → done
t = 19 : Q2 = [P1]
         P1 runs in Q2 (FCFS) from 19 ...
t = 21 : P4 arrives in Q0 → preempts P1 (rem 3, stays in Q2)
         P4 runs 21-25 in Q0, full quantum (rem 2)      → demoted to Q1
t = 25 : Q1 = [P4]       Q2 = [P1]
         P4 runs 25-27 in Q1                            → done
t = 27 : P1 runs 27-30 in Q2                            → done
|  P1  |  P2  |  P3  |  P1  |  P2  |  P1  |  P4  |  P1  |
|  Q0  |  Q0  |  Q0  |  Q1  |  Q1  |  Q2  |Q0, Q1|  Q2  |   <- queue
0      4      8      10     18     19     21     27     30

(The P4 block from 21 to 27 is two slices back to back: 21-25 in Q0 and 25-27 in Q1.)

Process

AT

BT

CT

TAT

WT

RT

Lowest queue reached

P1

0

17

30

30

13

0

Q2

P2

2

5

19

17

12

2

Q1

P3

4

2

10

6

4

4

Q0

P4

21

6

27

6

0

0

Q1

Average TAT = 59 / 4 = 14.75
Average WT  = 29 / 4 = 7.25
Average RT  = 6 / 4  = 1.5

Look at what MLFQ did without knowing any burst times:

  • The short job P3 (burst 2) finished in its very first turn, in the top queue.

  • The long job P1 (burst 17) sank to the bottom and ran in the gaps.

  • The newcomer P4 got the CPU the instant it arrived (RT = 0), because it started in the top queue.

Comparing With Other Algorithms on the Same Data

Algorithm

Avg TAT

Avg WT

Avg RT

Needs burst times?

FCFS

16.50

9.00

9.00

No

Round Robin (q = 4)

14.00

6.50

2.00

No

MLFQ (4 / 8 / FCFS)

14.75

7.25

1.50

No

SRTF

10.50

3.00

0.75

Yes

SRTF wins every column, but it cheats: it knows the future. Among the algorithms that do not, MLFQ gives the best response time here, and its job is precisely to give quick responses to short and interactive work while still finishing long jobs. Notice that MLFQ's average turnaround is slightly worse than plain RR in this small example. That is a reminder that no scheduler is best on every metric; MLFQ is tuned for responsiveness, and its advantage grows on real workloads with many short interactive bursts.


How MLFQ Treats I/O-Bound Processes

The real power of MLFQ appears with interactive programs. Consider an editor that runs for 1 ms, then waits for a keystroke, again and again, while a long compilation runs in the background:

Editor:      run 1 ms → block for I/O → run 1 ms → block → ...
             never uses a full quantum of 4 ms → Rule 5 → stays in Q0

Compiler:    uses its full quantum every time → Rule 4
             Q0 → Q1 → Q2, then runs in the gaps

Result: every time you press a key, the editor is in the highest queue
        and preempts the compiler immediately. The system feels fast.

MLFQ has effectively approximated SJF for CPU bursts: short bursts get top priority, long ones get pushed down, and it learned this purely from observation.


Problems MLFQ Must Handle

1. Starvation

If there are always enough interactive processes in the top queues, a CPU-bound process in the bottom queue may never run. The priority boost (Rule 6) fixes this: every S time units, all processes return to the top queue, so even a bottom-queue process gets regular turns.

Choosing S is a balancing act. Too long, and long jobs starve for a while. Too short, and interactive processes lose their advantage because everyone is constantly boosted to the top. This is a form of the aging you saw in Priority Scheduling.

2. A Process That Changes Behaviour

A program might compute heavily at startup and later become interactive (or the reverse). Without boosts, it would stay in a low queue forever. Periodic boosting gives it a chance to prove itself again. Some designs also promote a process that has waited too long in a low queue.

3. Gaming the Scheduler

A clever (or malicious) program can exploit Rule 5. If it always does a tiny, useless I/O just before its quantum ends, it never uses a "full" quantum and stays in the top queue forever, taking almost all the CPU.

Quantum = 4 ms
Gaming process: run 3.9 ms → fake I/O → run 3.9 ms → fake I/O → ...
Never demoted. Gets nearly 100% of the CPU at top priority.

The fix is better accounting: track the total CPU time a process has used at its current level, across all its turns. Once that total reaches the level's allotment, demote it, no matter how many times it gave up the CPU early. With this rule, splitting CPU usage into small pieces no longer helps.


MLQ vs MLFQ

Feature

Multilevel Queue

Multilevel Feedback Queue

Process moves between queues?

No, assigned once

Yes, based on CPU usage

Classification

By type, fixed at creation

Learned from behaviour

Starvation

Possible for lower queues

Prevented by priority boost / aging

Overhead

Lower

Higher (tracking usage, moving processes)

Flexibility

Low

High, but many parameters to tune

Approximates SJF?

No

Yes, without knowing burst times

Typical use

Separating clearly different classes (real-time vs normal)

General-purpose time-sharing schedulers


Multilevel Ideas in Real Operating Systems

Real schedulers rarely match the textbook versions exactly, but the ideas from this chapter show up everywhere:

  • Linux scheduling classes form a multilevel queue. In order of precedence: the stop class (internal), SCHED_DEADLINE, real-time (SCHED_FIFO / SCHED_RR, priorities 1 to 99), then normal tasks (SCHED_OTHER, SCHED_BATCH, SCHED_IDLE). A runnable task in a higher class always runs first, which is fixed-priority MLQ between classes. Within normal tasks, Linux used an MLFQ-like "O(1)" scheduler with interactivity heuristics in early 2.6 kernels, replaced it with the Completely Fair Scheduler (CFS) in 2.6.23 (2007), and since 6.6 (2023) uses EEVDF. Since 6.12 (2024), the sched_ext class even lets administrators load their own scheduling policies written as BPF programs.

  • Windows uses 32 priority levels (0 to 31). Levels 16 to 31 are the real-time range, and levels 1 to 15 are the variable range, where the OS temporarily boosts a thread's priority, for example after it completes I/O or when its window is in the foreground, and lets the boost decay as the thread uses CPU. That is MLFQ-style feedback.

  • Solaris, macOS and the BSDs also adjust priorities dynamically based on CPU usage and sleeping, giving interactive threads higher priority and shorter waits. Classic Solaris uses a dispatch table where lower priorities get longer time quanta, exactly like Rule 3.

So when you study MLFQ, you are studying the core idea behind the desktop and phone you are using right now.


Summary of All Scheduling Algorithms

This table pulls together the scheduling chapters from FCFS Scheduling to this one:

Algorithm

Preemptive?

Selection rule

Starvation?

Main strength

Main weakness

FCFS

No

Earliest arrival

No

Simple, low overhead

Convoy effect

SJF

No

Shortest next burst

Yes

Optimal avg WT (all arrive together)

Burst times unknown

SRTF

Yes

Shortest remaining time

Yes

Optimal avg WT in general

Burst times unknown, more switches

Priority

Either

Highest priority

Yes (fix: aging)

Important work first

Starvation, priority inversion

Round Robin

Yes (timer)

Next in circular queue

No

Fair, good response time

Switch overhead, quantum-sensitive

Multilevel Queue

Usually

Highest non-empty queue, then that queue's algorithm

Yes (fixed priority)

Different policies for different classes

Rigid classification

MLFQ

Yes

Highest non-empty queue; queues adjust by behaviour

No (with boost)

Approximates SJF without knowing bursts

Complex to tune, can be gamed without proper accounting


Common Mistakes

  • Mixing up MLQ and MLFQ. The one-word difference is "movement": MLQ processes never move between queues; MLFQ processes do.

  • Forgetting cross-queue preemption. In Example 2, P4 arriving in Q0 at time 21 immediately preempts P1 in Q2.

  • Demoting a process that finished within its quantum. P3 needed 2 units in a 4-unit quantum; it simply completes. Demotion only happens when the full quantum is used and work remains.

  • Resetting the remaining time after a demotion. P1 enters Q1 with 13 units left, not 17.

  • Giving a preempted lower-queue process a fresh full quantum without saying so. When a process is preempted by a higher queue, state whether it keeps its used quantum. It matters in RR queues.

  • Assuming lower queues have shorter quanta. It is usually the opposite: lower queues hold CPU-bound processes and get longer quanta.


Interview Questions

What is the difference between multilevel queue and multilevel feedback queue scheduling?

In MLQ, a process is assigned to one queue permanently. In MLFQ, a process can move between queues based on its CPU usage, which lets the scheduler adapt to the process's actual behaviour.

Why does a new process enter the highest-priority queue in MLFQ?

The scheduler does not know how long it will run, so it assumes it might be short. If it is, it finishes quickly with good response time. If it is not, it gets demoted.

How does MLFQ approximate SJF?

Processes with short CPU bursts finish or block before their quantum expires and stay in high queues, while long CPU-bound processes use full quanta and sink. So short bursts effectively get higher priority, without knowing burst lengths in advance.

How does MLFQ prevent starvation?

With a periodic priority boost (or aging): after some time, all processes are moved back to the top queue, so low-queue processes get CPU time again.

How can a process game an MLFQ scheduler, and how is it prevented?

By issuing a tiny I/O just before its quantum ends so it never gets demoted. It is prevented by tracking total CPU time used at a level across all turns and demoting once that allotment is used.

Why do lower queues get longer quanta?

Processes there are CPU-bound and non-interactive. Longer quanta reduce context switches for them, and their response time matters less.

What are the parameters that define an MLFQ scheduler?

The number of queues, the scheduling algorithm and quantum of each queue, the rules for demotion and promotion, and which queue a new process enters.


The Main Idea

Multilevel Queue scheduling splits processes into fixed classes, each with its own queue and algorithm, and schedules between queues by priority or time share. Multilevel Feedback Queue scheduling lets processes move between those queues based on their behaviour.

New process → top queue
      ↓
Run highest non-empty queue (RR inside, longer quantum lower down)
      ↓
Used full quantum? → move down
Gave up CPU early? → stay
      ↓
Every so often → boost everyone to the top

Key facts:

MLQ   → fixed queues, no movement, lower queues may starve
MLFQ  → movement by feedback, approximates SJF, no burst knowledge needed
Fixes → priority boost (starvation), total-time accounting (gaming)
Real  → Linux scheduling classes, Windows priority boosts, Solaris dispatch tables

MLFQ learns from the past to predict the future: it rewards processes that use the CPU briefly and gently pushes CPU-hungry ones aside, giving fast response without needing to know anything in advance.

This completes CPU scheduling. So far, we have assumed that processes run independently. In reality, processes and threads often share data, and when the scheduler can switch between them at any moment, strange bugs appear. The next chapter, Process Synchronization & Race Conditions, explains why.