Lesson 5.6: Multilevel Queue Scheduling

01 Introduction

Lessons 5.2 through 5.5 examined scheduling algorithms one at a time: FCFS, SJF, SRTF, priority, and round robin. Each is a single policy with a single objective, and each is optimal for some metric and poor for others. FCFS is fair but inefficient. SJF is optimal for average waiting time but starves long jobs. Round robin is fair and predictable but has a high average waiting time. Priority scheduling is expressive but requires aging to prevent starvation.

No single algorithm satisfies all the requirements of a general-purpose system. Interactive users need bounded response time; batch jobs need high throughput; system processes need low latency; and background tasks need to make progress without interfering with any of the above. These requirements conflict, and no single policy can satisfy them all at once.

Real schedulers solve the problem by combining the classical algorithms. Multilevel queue (MLQ) scheduling partitions the ready set into several classes, each with its own queue and its own scheduling policy, and the scheduler chooses among the queues by a fixed rule. Multilevel feedback queue (MLFQ) scheduling goes further: instead of fixing a process's queue at creation, it allows the process to move between queues based on its observed behaviour. A process that uses the CPU heavily sinks to lower-priority queues; a process that blocks frequently stays high or rises. The result is a scheduler that learns the process's character and treats it accordingly — a practical approximation to SJF that does not require burst-length prediction.

This lesson covers the structure of both schedulers, the rules that govern queue movement, the design parameters that determine behaviour, and the ways in which the ideas appear in modern operating systems. It closes Unit 5 by showing how the classical algorithms studied in the previous lessons are used in practice — not as complete policies, but as components of a larger structure.

Prerequisites

This lesson builds on all of Unit 5. It assumes familiarity with FCFS, SJF, priority scheduling, and round robin, and with the metrics and criteria from Lesson 5.1. The discussion of Linux in section 4.9 also draws on the scheduling class concept introduced in Lesson 5.1 and the priority interfaces introduced in Lesson 5.4.

02 Learning objectives

By the end of this lesson you will be able to

Describe multilevel queue scheduling and the role of queue classes and per-queue policies.
Describe multilevel feedback queue scheduling and the rules that govern queue movement.
Explain how MLFQ approximates SJF without predicting burst lengths.
Analyse the design parameters of MLFQ and their effects on behaviour.
Describe how real schedulers (Linux CFS, Windows, classic UNIX) build on these ideas.

This lesson contributes to U5.4 and U5.5, and to course learning outcomes CLO1, CLO3, and CLO8.

03 Required reading

Operating System Concepts — Chapter 5, Sections 5.5 and 5.6, Multilevel Queue Scheduling and Multilevel Feedback Queue Scheduling. The standard treatment of both designs, including the classic five-queue example.
OSTEP — Chapter 8, Scheduling: The Multi-Level Feedback Queue. The clearest available treatment of MLFQ. Read it carefully: OSTEP develops the scheduler in stages, introducing each rule and then showing what problem it solves and what new problem it creates. This is the most important reading in the unit.
Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4.6, Multilevel Queues and Multilevel Feedback Queues.
Silberschatz et al. — Chapter 5, Section 5.6, Real-Time CPU Scheduling. The discussion of the O(1) scheduler and CFS in Linux, which are real-world examples of the ideas in this lesson.
Linux man pages: man 7 sched. Read the sections on the Completely Fair Scheduler and the scheduling classes carefully. The CFS scheduler is the most important real-world example of the ideas in this lesson, and the man page is the authoritative reference for it.

Reading strategy

Read OSTEP Chapter 8 first and read it carefully. It is the best short treatment of MLFQ available, and its staged presentation — introduce a rule, identify its failure mode, add a new rule — is the clearest way to understand why the design is what it is. Then read the corresponding sections of Silberschatz and Tanenbaum for the formal definitions. Finish with man 7 sched to see how the ideas appear in Linux.

04 Core content

4.1 The motivation for multilevel scheduling

The classical algorithms each optimize a single metric and neglect the others. A general-purpose system needs to satisfy several requirements at once, and they conflict:

System processes (the kernel's own threads, device drivers, and interrupt handlers) need low latency and must not be delayed by user work.
Interactive processes (shells, editors, GUIs) need bounded response time so that the user does not perceive the system as sluggish.
Batch processes (compilations, simulations, machine-learning training) need high throughput and are insensitive to response time.
Background processes (indexing, backups, software updates) should consume only the CPU time that nobody else wants.

No single policy can satisfy all four. FCFS treats them all equally and gives the system processes no priority. Round robin gives equal shares but wastes CPU time on context switches and cannot distinguish a critical system thread from a background indexer. SJF gives short jobs priority but cannot tell a short interactive keystroke from a short batch computation.

The solution is to partition the ready set into classes and to use a different policy for each class. The scheduler becomes a two-level structure: a top-level policy that chooses among the classes, and a per-class policy that chooses within a class. This is the structure of multilevel queue scheduling.

4.2 Multilevel queue scheduling

In multilevel queue (MLQ) scheduling, the ready queue is partitioned into several separate queues, each with its own scheduling policy. Each process is assigned permanently to one queue at creation, based on some property of the process: its type, its priority, its memory requirements, or its owner.

The classic example, from Silberschatz, partitions the ready set into five queues:

System processes — highest priority, runs first.
Interactive processes — round robin, bounded quantum.
Interactive editing processes — round robin, larger quantum.
Batch processes — FCFS.
Student processes — lowest priority, FCFS.

Figure 5.6 — Multilevel queue scheduling with five queue levels. Each level has its own policy; the scheduler selects from the highest-priority non-empty queue. A process is assigned to one queue at creation and never moves, which is the main limitation of the design.

The scheduler must also decide how to allocate CPU time among the queues. Two common approaches are:

Fixed priority preemptive. The scheduler always selects from the highest-priority non-empty queue. A process in queue 2 runs only when queue 1 is empty. A process in queue 5 runs only when queues 1–4 are all empty. This gives absolute precedence to higher-priority queues, but it can starve lower-priority queues indefinitely.
Time-slicing among queues. Each queue receives a fixed fraction of the CPU time, and within its share the queue's own policy is used. For example, queue 1 might receive 50 percent of the CPU, queue 2 25 percent, and queues 3–5 the remaining 25 percent. This prevents starvation but complicates the design and can waste CPU time if a queue has no ready processes.

4.3 The limitation of fixed assignment

The critical weakness of MLQ is that a process is assigned to exactly one queue and never moves. If the initial assignment is wrong, the process is treated wrongly for its entire lifetime. Consider:

A process that starts as CPU-bound but becomes interactive — for example, a compiler that spends its first seconds parsing and its later seconds waiting on file I/O — is stuck in the batch queue even after it becomes interactive.
A process that starts interactive but becomes CPU-bound — a text editor that begins a long search — remains in the interactive queue and consumes the responsive time slice that was meant for genuinely interactive work.
A process whose character cannot be known at creation — almost every process — is assigned on the basis of a guess. The scheduler has no way to correct the guess.

These limitations motivate multilevel feedback queue scheduling, which allows processes to move between queues based on their observed behaviour.

4.4 Multilevel feedback queue scheduling

In multilevel feedback queue (MLFQ) scheduling, the ready queue is partitioned into several queues with different priorities, and processes move between them based on their behaviour. The scheduler observes how each process uses the CPU and adjusts its queue accordingly.

The design is defined by a set of rules. The rules in the classic formulation (as presented in OSTEP) are:

The MLFQ rules
Rule	Statement
Rule 1	If Priority(A) > Priority(B), A runs (B does not).
Rule 2	If Priority(A) = Priority(B), A and B run in round-robin order using the quantum of their queue.
Rule 3	When a job enters the system, it is placed at the highest priority (the topmost queue).
Rule 4a	If a job uses up its entire time allotment at a level, its priority is reduced (it moves down one queue).
Rule 4b	If a job gives up the CPU before its time allotment expires (by blocking on I/O), it stays at the same priority level.
Rule 5	After some time period S, move all the jobs in the system to the topmost queue.

The first two rules establish the basic priority structure: higher-priority queues run first, and within a queue, round robin is used. Rule 3 ensures that every new job starts at the top, which gives it a chance to prove itself interactive before being demoted. Rule 4a penalizes CPU-bound behaviour: a job that uses its full quantum is demoted. Rule 4b rewards I/O-bound behaviour: a job that blocks before its quantum expires retains its priority. Rule 5 is the anti-starvation mechanism: periodically, all jobs are promoted to the top, giving every job a chance to be treated as interactive.

Figure 5.6b — Multilevel feedback queue with promotion and demotion. New jobs enter the top queue. Jobs that use their full quantum are demoted; jobs that block early stay at their level. A periodic priority boost promotes all jobs back to the top, preventing starvation and adapting to changes in a job's behaviour.

4.5 How MLFQ approximates SJF

The key insight of MLFQ is that it does not need to know a process's burst length in advance. It infers the process's character from its behaviour and treats it accordingly. The inference works because of a statistical property of real workloads: most short jobs are I/O-bound, and most long jobs are CPU-bound.

A short job typically issues an I/O request before its quantum expires. Under Rule 4b it stays at the top, and it completes quickly. Its response time is bounded by the top queue's quantum, which is small.
A long job typically uses its full quantum. Under Rule 4a it is demoted, and it eventually settles into a lower queue. Its response time is longer, but it is a long job, so this is acceptable.
A job whose character changes — for example, an interactive job that begins a long computation — is initially at the top, is demoted when it uses full quanta, and is promoted back to the top by the next priority boost. Its behaviour is tracked continuously.

The result is a scheduler that gives short jobs and I/O-bound jobs the responsiveness of round robin in a small quantum, and gives long jobs and CPU-bound jobs the throughput of a larger quantum, without ever knowing in advance which is which. It is the closest practical approximation to SJF, and it is the design used by the classic UNIX schedulers, Windows, and many real-time systems.

4.6 The design parameters of MLFQ

An MLFQ scheduler is defined by a small set of parameters. Different choices produce very different behaviours, and the design must be tuned to the workload.

Design parameters of MLFQ
Parameter	Description	Effect
Number of queues	How many priority levels the scheduler maintains.	More levels give finer discrimination; fewer are simpler to implement and tune.
Quantum per queue	The time slice used within each queue.	Higher-priority queues usually have smaller quanta, to keep response time low; lower-priority queues have larger quanta, to amortize context-switch overhead.
Demotion rule	When a process moves to a lower queue.	Using the full quantum is the classic rule; a variant uses a threshold on total CPU time consumed.
Promotion rule	When a process moves to a higher queue.	Blocking before the quantum expires keeps a process at its level; a separate boost rule periodically moves everything to the top.
Boost interval	How often the priority boost runs.	Too short and CPU-bound jobs never sink; too long and starvation becomes possible.
Admission policy	Which queue a new process enters.	Entering at the top gives every process a chance to prove itself; entering at a lower queue is simpler but less adaptive.

The parameter values in a real scheduler are the result of extensive measurement and tuning. The Solaris time-sharing scheduler, for example, uses 60 queues with quanta ranging from 20 ms at the top to 200 ms at the bottom, with a boost interval of about 1 second. The parameters are chosen to match the workload of a general-purpose time-sharing system: a mix of interactive and batch jobs on a machine with a small number of cores.

4.7 Gaming the scheduler

Because MLFQ uses observable behaviour as a proxy for the process's true character, a process can manipulate its priority by manipulating its observable behaviour. The classic attack is for a CPU-bound process to issue a short I/O request just before its quantum expires, so that it appears to be I/O-bound and stays at the top of the scheduler. The process then monopolizes the responsive queue without actually being responsive.

Several countermeasures are used in practice:

Better accounting. Instead of rewarding a single block, the scheduler tracks the total CPU time the process has consumed. A process that has consumed more than a threshold is demoted regardless of its block pattern.
Per-queue accounting. The scheduler limits the total CPU time a process can consume at each priority level, so that a process cannot spend an arbitrary amount of time at the top by blocking repeatedly.
Randomized quanta. The Solaris scheduler uses slightly different quanta for each process at the same priority level, making it harder for a process to time its I/O to the quantum boundary.

The gaming problem is a general one in scheduler design: any policy that rewards observable behaviour can be gamed by a process that produces the rewarded behaviour. The countermeasures are always a trade-off between robustness and simplicity.

4.8 MLFQ versus MLQ

The two designs differ in one essential respect: whether a process can move between queues.

Property	MLQ	MLFQ
Queue assignment	Fixed at creation	Dynamic, based on behaviour
Adaptivity	None	High — responds to changes in behaviour
Starvation risk	High for low-priority queues	Low — priority boost prevents it
Implementation complexity	Low	Moderate — must track behaviour and run the boost
Approximation to SJF	None	Good — short jobs stay high, long jobs sink
Gaming risk	Low	High — behaviour is the input to the policy
Typical use	Simple systems, real-time classes with fixed priorities	General-purpose time-sharing, interactive systems

4.9 Real-world examples

The ideas of multilevel scheduling appear in every major general-purpose operating system. The details differ, but the structure is recognizably the same.

Classic UNIX. The original UNIX scheduler used a multilevel feedback queue with about 32 priority levels. A process's priority was recomputed every second based on its recent CPU usage, and processes that used more CPU were demoted. The design was refined over the years into the multilevel-feedback scheduler used in Solaris and the BSDs.
Linux O(1) scheduler. The scheduler used in Linux from 2.6.0 to 2.6.22 maintained two arrays of runqueues — active and expired — with 140 priority levels each. Interactive processes were identified by a heuristic based on their sleep time and were kept in the active array; CPU-bound processes were demoted to the expired array. The design was a direct application of the MLFQ idea.
Linux CFS. The current Linux scheduler replaced the O(1) scheduler in 2.6.23. CFS is not an MLFQ in the classical sense; it uses a single runqueue with a red-black tree ordered by virtual runtime. But its objective — give every task a fair share of the CPU proportional to its weight, and prefer tasks that have received less CPU time — is the same objective that motivated MLFQ. The virtual runtime is the equivalent of the MLFQ priority: a task that has received less CPU time has a smaller virtual runtime and runs sooner.
Windows. The Windows thread scheduler uses a multilevel queue with 32 priority levels. Most threads use dynamic priorities: a thread that is CPU-bound has its priority lowered, and a thread that blocks on I/O has its priority raised. The behaviour is an MLFQ in all but name.
Solaris. The Solaris time-sharing scheduler is a classic MLFQ with 60 priority levels and a periodic priority boost. The design is documented in detail in the Solaris internals literature and is a useful reference for the classical formulation.
macOS. The Mach-based scheduler in macOS uses a multilevel feedback design with priorities derived from the thread's QoS class and its observed behaviour. The structure is the same as the classical MLFQ, with modern terminology.

CFS as a fair-share scheduler

Linux CFS is worth understanding in detail, because it represents a different approach to the same problem. CFS does not maintain multiple queues; it maintains a single runqueue ordered by vruntime, the virtual runtime a task has accumulated. The task with the smallest vruntime runs next. A task's vruntime advances at a rate inversely proportional to its weight, so a high-weight (high- priority) task's vruntime advances slowly and it runs more often. The effect is the same as MLFQ — every task receives a fair share proportional to its weight — but the mechanism is different and the behaviour is easier to analyse formally.

4.10 Common misconceptions

"MLQ and MLFQ are the same thing."

They differ in one essential respect: whether a process can move between queues. MLQ assigns a process to a queue permanently; MLFQ moves it based on its observed behaviour.

"MLFQ needs to know burst lengths."

No — this is the whole point. MLFQ infers a process's character from its behaviour. A process that uses its full quantum is treated as CPU-bound; a process that blocks early is treated as I/O-bound.

"Higher priority always means a smaller quantum."

Usually, but not always. The quantum is chosen to balance response time and overhead. In some systems, the top queue has a small quantum to keep response time low, and in others it has a larger one to reduce the number of switches.

"MLFQ guarantees no starvation."

Only if the priority boost is enabled and runs often enough. Without the boost, a long CPU-bound process can sink to the bottom and stay there indefinitely.

"MLFQ is a solved design."

New hardware (many-core, heterogeneous cores, NUMA) and new workloads (latency-sensitive services, ML training) continue to force re-examination. The design parameters of a modern scheduler are quite different from those of the 1970s.

"Gaming the scheduler is a theoretical concern."

It is a practical concern in any system where a process can be written to exploit the scheduler's heuristics. The countermeasures — better accounting, randomized quanta — are deployed in production systems.

05 Worked example

The following example traces an MLFQ schedule for a small workload, showing how processes move between queues based on their behaviour, and how the resulting schedule approximates SJF.

MLFQ with three queues

The scheduler has three queues with the following parameters:

Queue	Priority	Quantum	Policy
Q0	Highest	2	Round robin
Q1	Medium	4	Round robin
Q2	Lowest	8	Round robin

All processes enter at Q0. A process that uses its full quantum is demoted one level. A process that blocks before its quantum expires stays at its level. The boost interval is 20 time units; no boost occurs during this example.

The workload consists of three processes, all arriving at time 0:

Process	Total CPU	Behaviour
A	3	Short — runs 1 unit, blocks on I/O for 2, runs 2 more.
B	6	Medium — runs 3 units, blocks on I/O for 1, runs 3 more.
C	12	CPU-bound — runs continuously with no I/O.

The trace. All three enter Q0 at time 0. The scheduler runs Q0 in round-robin order, with a quantum of 2.

Time  Event
0     A, B, C enter Q0. Queue: A, B, C.
0–1   A runs 1 unit, then blocks on I/O (1 of 2 needed). A stays at Q0.
1–3   B runs 2 units (full quantum). B is demoted to Q1.
3–5   C runs 2 units (full quantum). C is demoted to Q1.
5–6   A resumes from I/O with 1 more unit to wait; it runs 2 units
      (2 of 2 needed), and completes at 7.
7     B is the only process in Q1. B runs.
7–8   B runs 1 unit, then blocks on I/O (1 of 1 needed). B stays at Q1.
8     C is the only ready process. C is in Q1. C runs.
8–12  C runs 4 units (full quantum). C is demoted to Q2.
12–13 B resumes from I/O with 3 units remaining; it runs 1 unit in Q1
      and then is the only ready process, so it continues.
13    No other ready processes. C is at Q2. B continues in Q1.
13–16 B runs 3 units and completes at 16.
16–24 C resumes at Q2, runs 8 units (full quantum), still has 0 left,
      completes at 24.

The Gantt chart:

| A |  B  |  C  | A | B |    C    |  B  |        C        |
0   1     3     5   7   8        12    16               24

Process	Arrival	CPU total	Start	Completion	Turnaround	Waiting	Response
A	0	3	0	7	7	4	0
B	0	6	1	16	16	10	1
C	0	12	3	24	24	12	3
Average					15.67	8.67	1.33

What happened. Process A, the shortest and most I/O-bound, stayed at Q0 for its entire life because it blocked before its quantum expired. It completed at time 7 with a response time of 0. Process B, which blocks once but uses more CPU, was demoted to Q1 but stayed there. Process C, the CPU-bound process, was demoted to Q2 and stayed there, running with the largest quantum. The schedule gives the short, I/O-bound process the best service, the medium process intermediate service, and the long CPU-bound process the lowest priority — exactly the pattern that approximates SJF.

Comparison to SJF and round robin

For reference, the same workload under pure SJF (with known burst lengths) and under pure round robin with a quantum of 2:

Metric	SJF	RR (q=2)	MLFQ
Average turnaround	9.0	17.0	15.67
Average waiting	1.5	10.0	8.67
Average response	1.0	2.0	1.33

MLFQ is better than round robin on every metric — it discriminates between the short and long jobs — but worse than SJF, which has the advantage of knowing the burst lengths in advance. MLFQ's advantage is that it achieves most of SJF's benefit without requiring information that a real system does not have.

Adding a priority boost

The example above assumes no priority boost during the run. If a boost occurred at time 10, all processes would return to Q0. C, which had been demoted to Q2, would re-enter at Q0 and receive a fresh 2-unit quantum before being demoted again. A, already completed, would be unaffected; B, still running, would also return to Q0. The effect is to give C a chance to be treated as interactive, at the cost of a small delay to B. Over many boost intervals, the schedule approaches a fair share of the CPU among long-running processes, while short processes continue to receive fast service.

The gaming problem in this example

Suppose C wanted to avoid being demoted to Q2. It could issue a short I/O request just before each quantum expired, appearing to be I/O-bound. Under Rule 4b, it would stay at Q0 and would consume most of the CPU at the highest priority, without actually being responsive. This is the gaming problem. A better accounting rule — tracking total CPU time consumed at each level rather than the block pattern — would defeat the attack.

06 Interactive activity

Activity · implement and explore MLFQ

This activity extends the round-robin simulator from Lesson 5.5 to MLFQ and explores the behaviour of the scheduler under different parameter choices. It closes the interactive work of Unit 5. Work through the steps in your course VM.

Implement a basic MLFQ simulator. Modify the round-robin simulator to implement MLFQ with three queues. Each process has a current queue level; the scheduler selects from the highest-priority non-empty queue. A process that uses its full quantum is demoted; a process that blocks or terminates before the quantum expires stays at its level.
```
struct proc {
    int pid;
    int arrival;
    int burst;       /* total CPU needed */
    int remaining;   /* CPU still needed */
    int queue;       /* current queue level, 0, 1, 2 */
    int start;       /* first time scheduled */
    int completion;  /* time of termination */
};

/* Queues: 0 = highest priority, 2 = lowest.
   Quantum per queue: q[0]=2, q[1]=4, q[2]=8. */
```
Run the simulator on the worked-example workload and verify the numbers match the table.
Add a priority boost. Modify the simulator to run a boost every S time units. On a boost, all processes in the system move to Q0, regardless of their current level. Re-run the worked-example workload with S = 10 and S = 20. How do the metrics change? What happens if S is very small (e.g. S = 4)? If S is very large?
Vary the number of queues. Modify the simulator to support 2, 3, 4, or 5 queues. Run the same workload with each and compare the metrics. Does adding more queues always improve the schedule? At what point do the returns diminish?
Vary the quanta. Change the quantum at each queue level — for example, doubling them, or using q = 4, 4, 4 at all levels. Run the workload and compare the metrics. What is the effect of using the same quantum at every level?
Demonstrate SJF approximation. Construct a workload with five processes of very different burst lengths (say 2, 4, 8, 16, 32 units), all arriving at time 0 and all CPU-bound. Run MLFQ, SJF, and round robin on the workload and compare the average turnaround times. How close is MLFQ to SJF? How much better is it than round robin?
Demonstrate the gaming attack. Modify the workload so that a CPU-bound process occasionally blocks for a very short time just before its quantum expires. Observe whether the process stays at the top queue. Then modify the demotion rule to account for total CPU time consumed at each level, and observe whether the attack still works.
Inspect the Linux scheduler. Use /proc/<pid>/sched to inspect the scheduling state of a running process.
```
yes > /dev/null &
PID=$!
cat /proc/$PID/sched | head -40
kill $PID
```
Look for the fields that report the process's virtual runtime, its total CPU time, and its scheduling policy. Compare these to the concepts in this lesson — the virtual runtime is CFS's equivalent of the MLFQ priority, and the total CPU time is the quantity the scheduler tracks to decide whether the process is CPU-bound.
Compare two workload types. Run two CPU-bound processes and one I/O-bound process simultaneously. Use pidstat -t 1 to observe each process's CPU usage. Which process receives more CPU time? Which receives more context switches? Relate the observation to the MLFQ design: the I/O-bound process should be treated as interactive and given a small quantum, while the CPU-bound ones are given longer quanta. Does the observed behaviour match?

Reflect: MLFQ is the closest practical approximation to SJF, but it requires the designer to choose many parameters — number of queues, quanta, demotion rule, boost interval — and the choices determine the scheduler's behaviour. Which parameter would you expect to be most important for an interactive workload? For a batch workload? For a mixed workload? How would you decide whether to add a fourth queue?

07 Knowledge check

Check your understanding

Question 1

Describe multilevel queue scheduling. What is the essential difference between MLQ and MLFQ? What is the main limitation of MLQ?

Show answer

Multilevel queue (MLQ) scheduling partitions the ready set into several separate queues, each with its own scheduling policy. A process is assigned to exactly one queue at creation and never moves between queues. The scheduler selects from the highest-priority non-empty queue. The essential difference between MLQ and MLFQ is that in MLFQ a process can move between queues based on its observed behaviour. In MLQ the assignment is permanent; in MLFQ it is dynamic. The main limitation of MLQ is that a wrong initial assignment cannot be corrected. A process that starts CPU-bound and becomes interactive, or vice versa, is treated wrongly for its entire lifetime. MLQ also does not prevent starvation of low-priority queues if the priority boost is absent or the queues are serviced in strict priority order.

Question 2

State the five MLFQ rules. Explain what each rule accomplishes and what problem it would create if it were absent.

Show answer

The five MLFQ rules are:

If Priority(A) > Priority(B), A runs. This establishes the priority structure: higher-priority queues run first. Without it, MLFQ would not be able to distinguish interactive from CPU-bound behaviour.
If Priority(A) = Priority(B), A and B run in round-robin order. This provides fairness within a queue. Without it, processes at the same level would have no defined order, and the scheduler would be non-deterministic.
When a job enters the system, it is placed at the top. This gives every new job a chance to prove itself interactive. Without it, a job would be assigned to a queue without any evidence about its behaviour.
Rule 4a: If a job uses its full quantum, its priority is reduced. Rule 4b: If a job gives up the CPU before its quantum expires, it stays at the same level. These two rules are the feedback mechanism: they demote CPU-bound jobs and keep I/O-bound jobs near the top. Without them, MLFQ would not adapt to a job's behaviour and would degenerate into MLQ.
After a time period S, move all jobs to the top. This is the anti-starvation rule. Without it, a CPU-bound job that has sunk to the bottom could stay there indefinitely, and a job whose behaviour changes from CPU-bound to interactive would never be reclassified.

Question 3

Explain how MLFQ approximates SJF without ever knowing a process's burst length in advance. What statistical property of real workloads makes the approximation work?

Show answer

MLFQ approximates SJF by using observable behaviour as a proxy for a process's character. A process that blocks before its quantum expires is inferred to be I/O-bound and short; it stays at the top queue and completes quickly with a small quantum. A process that uses its full quantum is inferred to be CPU-bound and long; it is demoted and eventually runs with a large quantum at a lower priority. The approximation works because of a statistical property of real workloads: most short jobs are I/O-bound, and most long jobs are CPU-bound. This is not a logical truth — it is an empirical regularity — but it holds well enough on typical time-sharing workloads that the approximation captures most of SJF's benefit. Without this property, the inference from behaviour to burst length would not be reliable, and MLFQ would not be a good approximation. This is why MLFQ performs well on general-purpose workloads and poorly on workloads where the correlation does not hold.

Question 4

What is the gaming problem in MLFQ? Describe the classic attack and two countermeasures.

Show answer

The gaming problem is that a process can manipulate its observable behaviour to influence the scheduler's decisions. The classic attack is for a CPU-bound process to issue a short I/O request just before its quantum expires, so that it appears to be I/O-bound. Under Rule 4b, it stays at the top queue and consumes most of the CPU at the highest priority, without actually being interactive. Two countermeasures: (1) Better accounting — instead of rewarding a single block, the scheduler tracks the total CPU time the process has consumed at each priority level and demotes it when the total exceeds a threshold, regardless of its block pattern. This defeats the attack because the process's total CPU consumption reveals its true character. (2) Randomized quanta — the scheduler uses slightly different quanta for different processes at the same level, making it harder for a process to time its I/O to the quantum boundary. The Solaris scheduler uses this approach. Both countermeasures are trade-offs between robustness and simplicity.

Question 5

Linux CFS is not an MLFQ in the classical sense. How does its design differ, and how does it achieve the same objective?

Show answer

Linux CFS does not maintain multiple queues with different priorities. It maintains a single runqueue ordered by vruntime, the virtual runtime a task has accumulated. The task with the smallest vruntime runs next. A task's vruntime advances at a rate inversely proportional to its weight, so a high-weight (high- priority) task's vruntime advances slowly and it runs more often. The effect is the same as an MLFQ: every task receives a fair share of the CPU proportional to its weight, and a task that has received less CPU time runs sooner. CFS achieves this with a different mechanism — a red-black tree ordered by virtual runtime rather than a set of queues — and the behaviour is easier to analyse formally. The weight of a task is derived from its nice value, so the user-space interface is the same as for a classical scheduler. The CFS design is a fair-share scheduler, which is a related but distinct concept from the priority-based MLFQ: CFS aims for proportional fairness, while MLFQ aims for responsiveness based on inferred job character.

08 Unit discussion

Discussion prompt

This lesson closes Unit 5. The five scheduling algorithms we have studied — FCFS, SJF, SRTF, priority, round robin — were each developed to solve a specific problem, and each has been used in real systems at some point. But none of them is used in its pure form in a modern general-purpose operating system. Instead, real schedulers combine them: MLFQ uses round robin within each queue and priority across queues; CFS uses a fair-share objective; Windows uses dynamic priorities derived from observed behaviour.

What does this tell us about the relationship between theoretical scheduling algorithms and practical schedulers? Is the theory useless because no one uses it directly? Or does the theory provide a vocabulary and a set of building blocks that practical schedulers combine in ways the theory does not anticipate?

Consider also the question of evaluation. The classical algorithms are evaluated on synthetic metrics — average waiting time, average turnaround time — computed on small workloads with known burst lengths. Real schedulers are evaluated on user-perceived responsiveness, on throughput under realistic workloads, and on their robustness to adversarial behaviour. Are these the same kind of evaluation? If not, what does the classical analysis actually tell us?

Post your response to the Unit 5 discussion forum and reply to at least two classmates. This closes Unit 5 and prepares you for the midterm examination. Supports CLO1, CLO3, and CLO8.

09 Practice exercise

This final exercise of Unit 5 consolidates the whole unit and prepares you for Lab 4 and the midterm examination. Aim to spend 90–120 minutes on it.

Trace MLFQ by hand. A scheduler has three queues: Q0 (quantum 2), Q1 (quantum 4), Q2 (quantum 8). All processes enter at Q0. A process that uses its full quantum is demoted; a process that blocks stays at its level. The boost interval is 30 time units. Trace the following workload, giving the Gantt chart, the completion times, and the metrics for each process.

Process	Arrival	CPU total	Behaviour
A	0	4	Runs 1 unit, blocks 3, runs 3 more.
B	0	10	Runs 4 units, blocks 2, runs 6 more.
C	0	16	CPU-bound, no I/O.
D	5	6	Runs 2 units, blocks 4, runs 4 more.

Compare MLFQ to the classical algorithms. For the workload in question 1, compute the metrics under FCFS, SJF (with known burst lengths), SRTF, and round robin with q = 4. Present all five results (including MLFQ) in a single table. Which algorithm gives the best average turnaround? Which gives the best maximum response? How does MLFQ compare to each?
Design an MLFQ for a specific workload. Suppose you are designing the scheduler for a university's shared computing cluster. The workload consists of: (a) interactive login sessions used by students to check their grades; (b) short batch jobs submitted by coursework; (c) long batch jobs submitted by research groups; (d) system maintenance jobs that should run only when nothing else is running. Design an MLFQ that meets all four requirements. Specify the number of queues, the quantum at each level, the demotion rule, the promotion rule, and the boost interval. Justify each choice.
Implement and test the gaming attack. Using the simulator from the interactive activity, modify a CPU-bound process to issue a short block just before its quantum expires. Measure the process's CPU share with and without the attack. Then implement the total-CPU-time accounting countermeasure and measure again. How much does the attack gain the attacker, and how much does the countermeasure reduce the gain?
Measure the Linux scheduler. Run a mix of CPU-bound and I/O-bound processes simultaneously and use pidstat -t 1 to measure the CPU time and context switches each one receives. Compare the observed behaviour to what you would predict from the MLFQ rules. Does Linux's observed behaviour match the MLFQ model? Where does it differ, and why?
```
yes > /dev/null &         # CPU-bound
while true; do cat /etc/hostname > /dev/null; done &  # I/O-bound
sleep 20
pidstat -t 1 5
kill %1 %2
```
Compare the four families of algorithms. Write a one-page summary comparing FCFS, SJF/SRTF, priority, and round robin across all seven criteria from Lesson 5.1. Use a table with the algorithms as rows and the criteria as columns, and fill in a one-word assessment (excellent, good, moderate, poor) for each cell. Then write a paragraph explaining which family is best suited to which type of workload.
Read man 7 sched in full. Read the entire man page and list every scheduling policy and every tunable parameter it mentions. For each policy, write a one-sentence description of the workload it is intended for. For each parameter, write a one-sentence description of what it controls. This gives you a complete map of the Linux scheduling interface as it exists today.
Reflect on the unit. In your own words, describe the single most important idea you have learned in Unit 5 — the one that changed how you think about scheduling — and explain why it matters. Then identify one question about scheduling that the unit has left unanswered, and suggest how you would go about answering it.

10 Summary

Multilevel queue (MLQ) scheduling partitions the ready set into several queues, each with its own scheduling policy. A process is assigned to one queue at creation and never moves.
The scheduler selects from the highest-priority non-empty queue. The allocation of CPU time among queues can be strict priority (which risks starvation) or time-sliced (which prevents it).
The limitation of MLQ is that a wrong initial assignment cannot be corrected. This motivates the dynamic assignment of MLFQ.
Multilevel feedback queue (MLFQ) scheduling moves processes between queues based on their observed behaviour. A process that uses its full quantum is demoted; a process that blocks early stays at its level; a periodic priority boost prevents starvation.
MLFQ approximates SJF without knowing burst lengths. It relies on the statistical property that short jobs are usually I/O-bound and long jobs are usually CPU-bound. The inference from behaviour to burst length is the central idea.
The design parameters of MLFQ are the number of queues, the quantum per queue, the demotion rule, the promotion rule, the boost interval, and the admission policy. The choice of parameters determines the scheduler's behaviour and must be tuned to the workload.
The gaming problem arises because MLFQ rewards observable behaviour. A CPU-bound process can issue a short I/O just before its quantum expires to appear interactive. Countermeasures include better accounting and randomized quanta.
Real schedulers are built on MLFQ ideas. Classic UNIX, Solaris, and the Linux O(1) scheduler are direct MLFQ implementations. Windows uses a multilevel queue with dynamic priorities. macOS uses a Mach-based MLFQ.
Linux CFS is a fair-share scheduler that achieves the same objective as MLFQ with a different mechanism: a single runqueue ordered by virtual runtime. Every task receives a share of the CPU proportional to its weight.
The classical algorithms of Unit 5 — FCFS, SJF, SRTF, priority, and round robin — are not used in their pure forms in modern systems. They are the building blocks from which real schedulers are constructed.

Unit 5 complete

This closes the scheduling unit. You now have the full set of classical scheduling algorithms, the criteria against which they are judged, and the hybrid designs that real systems use. Unit 6 turns to synchronization: the mechanisms that make concurrent processes and threads correct, including locks, semaphores, monitors, and condition variables. The scheduling ideas from this unit reappear there — for example, in the interaction between priority scheduling and lock protocols, and in the use of blocking primitives that move a process from the ready queue to a wait queue.

11 References

Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 8. Available online at ostep.org.
Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.5 and 5.6.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.4.6.
Love, R. Linux Kernel Development, 3rd ed., Chapter 4, Process Scheduling. The authoritative treatment of the Linux O(1) scheduler and its replacement by CFS.
Linux man-pages: man 7 sched.
Solaris Internals documentation, Scheduling Classes. The classic reference for the Solaris time-sharing scheduler.
Russinovich, M., Solomon, D. A., & Ionescu, A. Windows Internals, 7th ed., Chapter 4, Threads. The reference for the Windows thread scheduler.
Bouron, L., Chelius, G., & Fleury, E. Fairness and Quantization in Multilevel Feedback Queues. A technical analysis of the design parameters of MLFQ.