Introduction
Multilevel queue scheduling partitions the ready queue into several separate queues based on some fixed process property, such as whether a process is interactive (foreground) or batch (background). Each queue can use its own scheduling algorithm, and the queues themselves are scheduled relative to each other, typically with fixed priority or a proportional CPU-share. This differs from the algorithms studied so far because it operates one level up: it decides which queue gets attention, and each queue independently decides which of its own processes runs.
Cricket analogy: Selectors split players into separate pools — international squad versus domestic reserves — each pool using its own selection criteria, while a higher-level board decides how much attention the international pool gets versus reserves, mirroring multilevel queue scheduling.
Algorithm
/* A simple two-queue multilevel queue: foreground (interactive, Round
* Robin) always has strict priority over background (batch, FCFS). */
typedef enum { FOREGROUND, BACKGROUND } queue_class_t;
queue_class_t classify(process_t *p) {
return p->is_interactive ? FOREGROUND : BACKGROUND;
}
process_t *schedule_multilevel(queue_t *fg_queue, queue_t *bg_queue) {
if (!queue_empty(fg_queue))
return round_robin_pick(fg_queue); /* foreground always wins */
if (!queue_empty(bg_queue))
return fcfs_pick(bg_queue); /* background runs only when fg idle */
return NULL; /* CPU idle */
}
/* Multilevel FEEDBACK queue: processes can MOVE between queues based on
* observed behavior (e.g. using up a full quantum implies CPU-bound). */
void feedback_demote(process_t *p, int used_full_quantum) {
if (used_full_quantum && p->queue_level < MAX_LEVEL - 1) {
p->queue_level++; /* push CPU-bound processes to a lower-priority,
longer-quantum queue */
}
}Explanation
A plain multilevel queue is a fixed-priority scheme: a process is assigned to one queue for its entire lifetime (e.g. by process type), and if a strictly higher-priority queue (like foreground) always has work, a lower-priority queue (like background) can starve completely, since it only runs when all higher queues are empty. A multilevel feedback queue (MLFQ) fixes this rigidity by letting processes move between queues based on observed behavior: a process that uses its entire quantum (indicating it is CPU-bound) is demoted to a lower-priority queue with a longer quantum, while a process that blocks for I/O quickly (indicating it is interactive) can be kept in or promoted to a higher-priority queue with a short quantum for fast response. MLFQ queues typically also apply aging or periodic priority boosts to prevent the starvation that a rigid multilevel queue would otherwise suffer.
Cricket analogy: If the senior international squad always gets net time whenever available, domestic reserve players might never bat at all (starvation); a smarter academy instead watches behavior — promoting form players up and demoting out-of-form ones — like MLFQ's adaptive movement between queues.
Example
/*
* Fixed multilevel queue example: Foreground queue (RR, quantum 2) has
* strict priority over Background queue (FCFS). Foreground processes
* F1(0,4), F2(1,3); Background process B1(0,10).
*
* Because foreground always preempts background when non-empty:
* |F1|F2|F1|F2|-------B1-------|
* 0 2 4 6 7 17
*
* B1 does not start until BOTH foreground processes finish (t=7), even
* though B1 arrived at t=0 -- this is the starvation risk of fixed
* multilevel queues if foreground work keeps arriving.
*
* Contrast with MLFQ: if B1 had instead started in a high-priority queue
* and used a full quantum without blocking, it would be DEMOTED to a
* lower queue after its first slice rather than being frozen out
* completely -- and a periodic priority boost would eventually return it
* to the top queue so it cannot starve forever.
*/
Analysis
In the fixed multilevel queue trace, F1 and F2 finish by t=7 (F1 completes at 6, F2 completes at 7), and only then does B1 begin, finishing at 17. B1's waiting time is 7 (it was ready at 0 but did not start until 7), even though its own burst is 10 and no other background process competed with it — all of that delay came from strict foreground priority. If foreground processes kept arriving indefinitely, B1 could wait forever: this is exactly the starvation scenario that a rigid, fixed-priority multilevel queue permits, since a lower queue only runs when every higher queue is completely empty. A multilevel feedback queue avoids this permanent lockout by demoting long-running processes to lower queues after they consume full quanta, and by periodically boosting all processes back to the top queue, guaranteeing every process gets CPU time within a bounded window.
Cricket analogy: In a rigid net-session order, the international squad (foreground) always bats before reserves (background), so a reserve batter waiting since the start might not touch a bat for hours purely due to seniority; a rotating academy schedule that periodically resets priority prevents this permanent shutout.
Key Takeaways
- A multilevel queue splits the ready queue into separate queues by a fixed process attribute (e.g. foreground vs background), each with its own algorithm.
- In a fixed multilevel queue, a strictly higher-priority queue can starve a lower-priority queue indefinitely if it never goes empty.
- A multilevel feedback queue (MLFQ) allows processes to move between queues based on observed CPU/I/O behavior, rather than a fixed classification.
- MLFQ demotes CPU-bound processes (that use a full quantum) to lower, longer-quantum queues, and favors I/O-bound/interactive processes with short quanta at the top.
- Periodic priority boosts in MLFQ move all processes back to the top queue, preventing the permanent starvation that a plain multilevel queue is vulnerable to.
- In the worked example, background process B1 waited 7 time units purely due to fixed foreground priority, illustrating the starvation risk directly.
Practice what you learned
1. What distinguishes a multilevel queue from a multilevel feedback queue?
2. In the worked example, why does B1 (background) wait until t=7 to start?
3. What triggers demotion of a process to a lower-priority queue in a multilevel feedback queue?
4. What mechanism in MLFQ prevents processes in low-priority queues from starving forever?
5. Which scenario is a classic use case for a fixed multilevel queue's foreground/background split?
Was this page helpful?
You May Also Like
Priority and Round Robin Scheduling
Priority scheduling with starvation and aging, and Round Robin with a fully worked quantum-based Gantt chart.
Scheduling Algorithms Overview
How the CPU scheduler picks the next ready process, the metrics used to judge it, and the family of algorithms available.
FCFS and SJF Scheduling
First-Come-First-Served and Shortest-Job-First scheduling, worked through Gantt charts with exact waiting/turnaround-time math.