Operating SystemsCPU Scheduling

Round Robin & Multi-Level Queue Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

3 / 5

Multi-Level Queue Scheduling

When One Queue Isn't Enough

Consider an airport with a single security checkpoint where business executives, families with children, military personnel, and budget travelers all stand in the same line. The result? Frustration for those with tight connections, inefficiency for those who need extra screening time, and a one-size-fits-all process that fits no one perfectly.

Airports solved this with multiple queues: priority lanes for first class, family lanes, TSA PreCheck, and standard lanes. Each queue has different processing assumptions and different throughput characteristics.

Operating systems face the same challenge. A single Round Robin queue treats all processes identically—but processes are not identical. System daemons, real-time audio processing, interactive text editing, and background batch compilation have fundamentally different requirements. Multi-Level Queue (MLQ) scheduling addresses this by partitioning processes into distinct queues, each with its own scheduling policy optimized for its process class.

What You Will Master

By the end of this page, you will understand: the motivation for queue partitioning, the architecture of multi-level queue systems, queue priority and inter-queue scheduling policies, the assignment of processes to queues, the strengths and limitations of static MLQ, and implementations in real operating systems.

Motivation for Multi-Level Queues

Pure Round Robin's fundamental limitation is that it treats all processes as equals. While this guarantees fairness, it ignores the reality that processes have vastly different characteristics and requirements.

Process Classification by Behavior:

Process Types and Their Scheduling Needs
Process Type	Characteristics	Scheduling Needs	Examples
Real-time	Strict timing deadlines, predictable bursts	Guaranteed CPU access, minimal latency	Audio/video playback, sensor polling
System/Kernel	Critical for OS operation, typically short bursts	High priority, fast response	Device drivers, kernel threads
Interactive	User-facing, short bursts between I/O	Low latency, responsive	Text editors, browsers, shells
Batch	CPU-intensive, can tolerate delays	High throughput, latency unimportant	Compilers, simulations, backups
Idle/Background	Run only when nothing else needs CPU	Lowest priority, opportunistic	Indexing, updates, maintenance

The Scheduling Policy Mismatch:

Each process type benefits from different scheduling approaches:

Real-time: Needs priority-based preemptive scheduling with deadline awareness
Interactive: Benefits from small time quanta for responsiveness
Batch: Benefits from large time quanta for throughput

A single policy cannot optimize for all. Round Robin with Q=10ms is too small for batch efficiency but potentially too large for real-time deadlines.

The Multi-Level Queue Solution:

MLQ addresses this by:

Partitioning processes into multiple queues based on type/priority
Applying different policies to each queue (e.g., FCFS, RR with different quanta)
Scheduling between queues using priority or time-slicing

This allows the scheduler to simultaneously optimize for responsiveness (high-priority queues), throughput (low-priority queues), and guaranteed access (real-time queues).

Division of Labor

Think of MLQ as specialization. Instead of one general-purpose queue trying to serve everyone, specialized queues serve specialized needs. This is the same principle that makes specialized hospital wards (ER, ICU, general care) more effective than a single undifferentiated ward.

Multi-Level Queue Architecture

A Multi-Level Queue scheduler maintains multiple ready queues, organized in a priority hierarchy. The fundamental architecture consists of:

1. Queue Hierarchy: Queues are arranged by priority, typically with smaller numbers indicating higher priority:

Queue 0: Real-time processes (highest priority)
Queue 1: System processes
Queue 2: Interactive processes
Queue 3: Batch processes
Queue 4: Idle processes (lowest priority)

2. Per-Queue Scheduling Policy: Each queue has its own internal scheduling algorithm:

Real-time queue: Priority scheduling with preemption
Interactive queue: Round Robin with small quantum (10ms)
Batch queue: FCFS or Round Robin with large quantum (100ms)

3. Inter-Queue Scheduling: A policy determines how CPU time is allocated among queues:

Fixed priority: Higher queues always preempt lower
Time-slicing: Each queue gets a percentage of CPU time

Converting Mermaid diagram...

multi_level_queue.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from collections import deque
from dataclasses import dataclass
from enum import IntEnum
from typing import List, Optional, Tuple
 
class QueuePriority(IntEnum):
    REAL_TIME = 0
    SYSTEM = 1
    INTERACTIVE = 2
    BATCH = 3
    IDLE = 4
 
@dataclass
class Process:
    pid: int
    name: str
    priority: QueuePriority
    burst_time: int
    remaining_time: int
    arrival_time: int
    completion_time: int = 0
 
@dataclass 
class MLQConfig:
    """Configuration for a single queue in the MLQ."""
    priority: QueuePriority
    name: str
    algorithm: str  # "RR" or "FCFS"
    quantum: int    # Time quantum for RR (ignored for FCFS)
    time_slice_pct: float  # Percentage of CPU for time-slicing mode
 
class MultiLevelQueueScheduler:
    """
    Multi-Level Queue Scheduler with configurable queues
    and inter-queue scheduling policies.
    """
    
    def __init__(
        self, 
        queue_configs: List[MLQConfig],
        inter_queue_policy: str = "fixed_priority"  # or "time_slicing"
    ):
        self.queues = {cfg.priority: deque() for cfg in queue_configs}
        self.configs = {cfg.priority: cfg for cfg in queue_configs}
        self.inter_queue_policy = inter_queue_policy
        self.current_time = 0
        self.execution_log = []
        
    def add_process(self, process: Process):
        """Add a process to its designated queue."""
        if process.priority in self.queues:
            self.queues[process.priority].append(process)
            self.execution_log.append(
                f"[{self.current_time:4d}] P{process.pid} ({process.name}) "
                f"added to {self.configs[process.priority].name}"
            )
    
    def get_highest_priority_queue(self) -> Optional[QueuePriority]:
        """Find the highest priority non-empty queue."""
        for priority in sorted(self.queues.keys()):
            if self.queues[priority]:
                return priority
        return None
    
    def schedule_fixed_priority(self) -> Tuple[List[Process], List[str]]:
        """
        Fixed priority inter-queue scheduling.
        Higher priority queues always get CPU first.
        Lower queues execute only when higher are empty.
        """
        completed = []
        
        while True:
            priority = self.get_highest_priority_queue()
            if priority is None:
                break
            
            config = self.configs[priority]
            queue = self.queues[priority]
            process = queue.popleft()
            
            # Determine execution time based on queue's algorithm
            if config.algorithm == "FCFS":
                exec_time = process.remaining_time
            else:  # RR
                exec_time = min(config.quantum, process.remaining_time)
            
            self.execution_log.append(
                f"[{self.current_time:4d}-{self.current_time + exec_time:4d}] "
                f"P{process.pid} executes from {config.name} ({exec_time}ms)"
            )
            
            process.remaining_time -= exec_time
            self.current_time += exec_time
            
            if process.remaining_time > 0:
                # Re-queue at tail
                queue.append(process)
            else:
                process.completion_time = self.current_time
                completed.append(process)
                self.execution_log.append(
                    f"        P{process.pid} completed"
                )
        
        return completed, self.execution_log
 
 
# Example: Create and run MLQ scheduler
if __name__ == "__main__":
    # Configure queues
    configs = [
        MLQConfig(QueuePriority.REAL_TIME, "Real-Time Queue", "RR", 5, 0.40),
        MLQConfig(QueuePriority.SYSTEM, "System Queue", "RR", 8, 0.25),
        MLQConfig(QueuePriority.INTERACTIVE, "Interactive Queue", "RR", 10, 0.20),
        MLQConfig(QueuePriority.BATCH, "Batch Queue", "RR", 50, 0.10),
        MLQConfig(QueuePriority.IDLE, "Idle Queue", "FCFS", 0, 0.05),
    ]
    
    scheduler = MultiLevelQueueScheduler(configs, "fixed_priority")
    
    # Add processes
    processes = [
        Process(1, "audio_player", QueuePriority.REAL_TIME, 15, 15, 0),
        Process(2, "kernel_thread", QueuePriority.SYSTEM, 10, 10, 0),
        Process(3, "bash_shell", QueuePriority.INTERACTIVE, 20, 20, 0),
        Process(4, "gcc_compile", QueuePriority.BATCH, 100, 100, 0),
        Process(5, "backup_job", QueuePriority.IDLE, 50, 50, 0),
    ]
    
    for p in processes:
        scheduler.add_process(p)
    
    completed, log = scheduler.schedule_fixed_priority()
    
    print("=" * 60)
    print("Multi-Level Queue Scheduling (Fixed Priority)")
    print("=" * 60)
    
    for entry in log:
        print(entry)
    
    print("
" + "-" * 60)
    print(f"{'PID':^5} {'Name':^15} {'Queue':^15} {'Completion':^12}")
    print("-" * 60)
    
    for p in completed:
        print(f"{p.pid:^5} {p.name:^15} "
              f"{QueuePriority(p.priority).name:^15} {p.completion_time:^12}")

Inter-Queue Scheduling Policies

A critical design decision in MLQ is how to allocate CPU time among the queues themselves. Two primary approaches exist:

Approach 1: Fixed Priority Scheduling (Absolute Priority)

Queues are served in strict priority order. A process from a lower-priority queue only executes when all higher-priority queues are empty.

Mechanics:

Scheduler always selects from the highest-priority non-empty queue
If a higher-priority process becomes ready, it preempts the current process
Lower-priority queues may starve if higher-priority queues are always busy

Advantages:

Simple to implement and reason about
Guarantees real-time and system processes get immediate attention
Clear priority semantics

Disadvantages:

Starvation risk: Batch and idle processes may never run under heavy interactive load
No throughput guarantees for lower-priority work

Approach 2: Time-Slice Scheduling (Proportional Share)

Each queue receives a guaranteed percentage of CPU time. The scheduler cycles among queues, giving each its allocated share.

Example allocation:

Real-time: 40% of CPU (4ms out of every 10ms)
System: 25% of CPU
Interactive: 20% of CPU
Batch: 10% of CPU
Idle: 5% of CPU

Mechanics:

Scheduler divides time into scheduling periods (e.g., 100ms)
Within each period, each queue receives its allocated time
Within the queue's time slice, its internal policy (RR/FCFS) runs
If a queue is empty during its slice, time goes to lower queues or is idle

Advantages:

Prevents starvation—every queue makes progress
Predictable throughput for all priority levels
Tunable balance between responsiveness and throughput

Disadvantages:

More complex implementation
Less responsive to priority—real-time may wait for its slice
May not match natural workload patterns

Comparison of Inter-Queue Scheduling Policies
Aspect	Fixed Priority	Time-Slicing
Implementation	Simple	Moderate complexity
Starvation Risk	High for low-priority	None (guaranteed shares)
Real-time Support	Excellent (immediate access)	Good (within share)
Throughput Control	Unpredictable for lower queues	Predictable allocation
Responsiveness	Optimal for high-priority	May delay high-priority
Fairness	Priority-based only	Both priority and share
Use Case	Real-time dominant systems	Mixed workload servers

Hybrid Approaches

Many real systems use hybrid approaches. For example: fixed priority between real-time and non-real-time queues (real-time always preempts), but time-slicing among non-real-time queues (interactive, batch, idle share the remaining time proportionally). This combines guaranteed real-time response with fair sharing of non-critical work.

Process Queue Assignment

A crucial aspect of MLQ is determining which queue a process belongs to. In static MLQ (as opposed to MLFQ, covered next), processes are assigned to queues when created and do not move between queues for the duration of their execution.

Assignment Methods:

1. Explicit Class Specification: The process explicitly declares its scheduling class:

Unix nice value maps to priority/queue
POSIX real-time scheduling policies (SCHED_FIFO, SCHED_RR, SCHED_OTHER)
Windows priority classes (REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS, etc.)

2. Inheritance from Parent: Child processes inherit the scheduling class of their parent:

Shell spawns processes at interactive priority
System daemons spawn children at system priority
Can be overridden by explicit specification

3. User/Group Based: Assignment based on user identity or group membership:

Root/Administrator processes get system priority
Guest users get lower priority
Service accounts get specific priorities

4. Process Type Heuristics: Based on executable characteristics:

GUI applications → interactive queue
Background services → batch queue
Kernel threads → system queue

Queue Assignment in Major Operating Systems
OS	Assignment Mechanism	User Control
Linux	nice values (-20 to +19), scheduling policies	nice, renice, chrt commands
Windows	Priority classes (6 levels), thread priorities (7 levels)	Task Manager, SetPriorityClass API
macOS	QoS classes (User Interactive, Utility, Background, etc.)	dispatch_queue_attr API
FreeBSD	Nice values, SCHED_FIFO/RR for real-time	rtprio, idprio commands
Solaris	Fair share scheduler classes, projects	priocntl, prctl commands

queue_assignment.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* Linux example: Setting scheduling class and priority */
 
#include <sched.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdio.h>
 
/* Set process to real-time FIFO scheduling with priority 50 */
int set_realtime_priority(void) {
    struct sched_param param;
    param.sched_priority = 50;  /* Range: 1-99 for real-time */
    
    if (sched_setscheduler(0, SCHED_FIFO, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    printf("Set to SCHED_FIFO with priority %d
", param.sched_priority);
    return 0;
}
 
/* Set process to batch scheduling (throughput-oriented) */
int set_batch_priority(void) {
    struct sched_param param;
    param.sched_priority = 0;  /* Must be 0 for SCHED_BATCH */
    
    if (sched_setscheduler(0, SCHED_BATCH, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    /* Also set nice value to indicate low priority */
    if (setpriority(PRIO_PROCESS, 0, 19) == -1) {
        perror("setpriority failed");
        return -1;
    }
    
    printf("Set to SCHED_BATCH with nice 19
");
    return 0;
}
 
/* Set process to idle scheduling (only runs when system is idle) */
int set_idle_priority(void) {
    struct sched_param param;
    param.sched_priority = 0;
    
    if (sched_setscheduler(0, SCHED_IDLE, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    printf("Set to SCHED_IDLE
");
    return 0;
}
 
/* Query current scheduling policy and priority */
void print_scheduling_info(void) {
    int policy = sched_getscheduler(0);
    struct sched_param param;
    sched_getparam(0, &param);
    
    const char* policy_name;
    switch (policy) {
        case SCHED_OTHER: policy_name = "SCHED_OTHER (CFS)"; break;
        case SCHED_FIFO:  policy_name = "SCHED_FIFO";        break;
        case SCHED_RR:    policy_name = "SCHED_RR";          break;
        case SCHED_BATCH: policy_name = "SCHED_BATCH";       break;
        case SCHED_IDLE:  policy_name = "SCHED_IDLE";        break;
        default:          policy_name = "Unknown";           break;
    }
    
    printf("Policy: %s, Priority: %d, Nice: %d
",
           policy_name, param.sched_priority,
           getpriority(PRIO_PROCESS, 0));
}

Static Assignment Limitations

Static queue assignment assumes we know a process's behavior at creation time. But what if an 'interactive' process becomes CPU-bound during compilation? Or a 'batch' process needs quick user interaction? Static MLQ cannot adapt—leading to the Multi-Level Feedback Queue (MLFQ) innovation covered next.

Example MLQ Configuration

Let's examine a detailed example of an MLQ configuration for a general-purpose Unix-like system.

Queue Structure:

Example 5-Level MLQ Configuration
Queue	Priority	Scheduling	Quantum	Preemptible	Typical Processes
Real-Time FIFO	0	FCFS (non-preemptive)	∞	No	Kernel interrupt handlers
Real-Time RR	1	Round Robin	5ms	By higher only	Audio/video processing
Interactive	2	Round Robin	10ms	By higher	Shells, editors, browsers
Batch	3	Round Robin	100ms	By higher	Compilers, scientific apps
Idle	4	FCFS	∞	By all	Index builders, updates

Scenario Walkthrough:

Consider these processes in the system:

PID	Name	Queue	Burst Time
1	audio_daemon	Real-Time RR	20ms (periodic)
2	kernel_logger	Real-Time FIFO	5ms
3	vim_editor	Interactive	30ms
4	gcc_compiler	Batch	500ms
5	spotlight_index	Idle	1000ms

Execution with Fixed Priority:

Time 0-5:    kernel_logger runs to completion (RT FIFO, Q=∞)
Time 5-10:   audio_daemon runs (RT RR, Q=5ms)
Time 10-15:  audio_daemon continues (2nd quantum)
Time 15-20:  audio_daemon continues (3rd quantum)  
Time 20-25:  audio_daemon continues (4th quantum, completes)
Time 25-35:  vim_editor runs (Interactive, Q=10ms)
Time 35-45:  vim_editor continues (completes 30ms total at 55)
...
Time 55-155: gcc_compiler runs (Batch, Q=100ms)
...
Time 555:    spotlight starts (was waiting 555ms!)

Observation: The idle-priority spotlight_index must wait for ALL higher-priority work to complete. Under sustained interactive load, it might never run—classic starvation.

Mitigating Starvation

Production systems mitigate starvation through: (1) aging mechanisms that boost starving processes, (2) time-slice guarantees for each queue, or (3) MLFQ which dynamically adjusts priority. Pure static MLQ with fixed priority is rarely used in isolation.

MLQ in Real Operating Systems

Modern operating systems implement variations of MLQ, typically combined with additional mechanisms to address starvation concerns.

Linux Scheduling Architecture:

Linux uses a two-tier multi-level queue structure:

Tier 1: Scheduling Classes (Priority Order)

SCHED_DEADLINE - Earliest Deadline First for deadline-guaranteed tasks
SCHED_FIFO - Real-time FCFS (run-to-completion)
SCHED_RR - Real-time Round Robin
SCHED_OTHER - Default, managed by CFS (Completely Fair Scheduler)
SCHED_BATCH - Batch processing (throughput-oriented CFS variant)
SCHED_IDLE - Runs only when system otherwise idle

Tier 2: Within SCHED_OTHER CFS manages fair time allocation among normal processes using virtual runtime. Nice values (-20 to +19) adjust the share of CPU time a process receives, but all SCHED_OTHER processes share the same queue.

Key Points:

Real-time classes have absolute priority over normal classes
Within real-time, FIFO and RR processes are ordered by static priority (1-99)
SCHED_OTHER processes never preempt real-time

Operating System Scheduling Architectures
OS	Queue Levels	Real-Time Support	Inter-Queue Policy
Linux	6 scheduling classes	SCHED_DEADLINE, SCHED_FIFO, SCHED_RR	Fixed priority by class, CFS within normal
Windows	32 priority levels in 6 classes	Real-time priority class (16-31)	Fixed priority with dynamic boost
macOS/iOS	4 QoS classes + real-time	Mach real-time threads	QoS-based resource allocation
FreeBSD	4 scheduling classes	SCHED_FIFO, SCHED_RR	ULE scheduler with interactivity scoring
Solaris	6 scheduling classes	Real-time, system classes	Configurable dispatcher table

Windows Scheduling Architecture:

Windows uses a 32-level priority system:

Levels 16-31: Real-time priority class (requires admin privileges)
Levels 1-15: Dynamic priority class (normal applications)
Level 0: System idle thread only

Within dynamic priority:

Base priority set by priority class (Normal, High, Above Normal, etc.)
Thread priority is base ± relative priority (Lowest to Highest)
Dynamic boosting: Interactive and I/O-completing threads get temporary priority boosts

Windows Foreground Boost: The foreground window's process receives a quantum boost (3× normal) to improve interactive responsiveness. This is a form of heuristic-based queue promotion.

macOS QoS (Quality of Service):

macOS uses semantic QoS classes rather than numeric priorities:

User Interactive - UI updates, animations
User Initiated - User-triggered tasks expecting immediate results
Utility - Long-running tasks with progress UI
Background - Tasks user doesn't directly see

The system maps QoS to scheduling parameters, adjusting priority and timer coalescing based on power state (plugged in vs. battery).

The Evolution Beyond Static MLQ

Notice how all production systems add mechanisms beyond static MLQ: Linux's CFS for fairness within normal class, Windows' dynamic boosting for interactivity, macOS's QoS semantics. Pure static MLQ is a conceptual foundation, but real systems augment it extensively.

Advantages and Limitations

Advantages of MLQ

•Differentiated Service: Different process types get appropriate treatment. Real-time gets guaranteed access; batch gets efficient throughput.
•Per-Queue Optimization: Each queue can use the algorithm best suited to its processes (RR for interactive, FCFS for batch).
•Low Overhead: Simple queue selection based on priority—O(1) to find highest-priority non-empty queue.
•Predictable for Real-Time: High-priority queues have guaranteed preemption rights, enabling real-time guarantees.
•Clear Policy Semantics: Priority levels have intuitive meaning; easy to reason about system behavior.

Limitations of MLQ

•Starvation Risk: With fixed priority, low-priority queues may never execute under sustained high-priority load.
•Static Classification: Processes are assigned at creation; behavior changes aren't accommodated.
•Manual Tuning Required: Administrators must configure queue policies; poor configuration degrades performance.
•No Adaptive Behavior: System cannot learn that an 'interactive' process became CPU-bound.
•Configuration Complexity: Multiple queues with different parameters create many tuning knobs.

The Core Limitation:

MLQ assumes we know, at process creation time, what category the process belongs to and that this classification remains valid throughout execution. This assumption is often wrong:

A text editor is interactive while typing but CPU-bound during syntax highlighting
A web browser is interactive when scrolling but batch-like when loading pages
A compiler is batch during compilation but interactive when printing errors

The question becomes: Can the scheduler learn process behavior and adjust classification dynamically?

This question leads directly to the Multi-Level Feedback Queue (MLFQ)—the subject of our next page.

MLQ as Building Block

Despite its limitations, MLQ remains valuable as a foundation. MLFQ builds upon MLQ by adding dynamic queue transitions. Even sophisticated schedulers like Linux CFS use MLQ concepts for separating real-time from normal processes. Understanding static MLQ is prerequisite to understanding modern dynamic schedulers.

Summary: Multi-Level Queue Scheduling

We have thoroughly explored Multi-Level Queue scheduling—the architecture that addresses Round Robin's one-size-fits-all limitation by partitioning processes into specialized queues.

Key Takeaways

•Problem Addressed: Single-queue RR cannot optimize for processes with fundamentally different needs (real-time, interactive, batch).
•Core Architecture: Multiple ready queues arranged by priority, each with its own scheduling algorithm (FCFS, RR) and parameters (quantum).
•Inter-Queue Scheduling: Fixed priority (higher queues always preempt) or time-slicing (each queue gets a guaranteed CPU share).
•Process Assignment: Static, based on explicit specification, inheritance, or heuristics. Processes do not move between queues.
•Starvation Concern: Fixed priority inter-queue scheduling can starve low-priority queues under sustained high-priority load.
•Real-World Usage: All major OSes use MLQ concepts—Linux scheduling classes, Windows priority levels, macOS QoS classes.
•Limitation: Static classification doesn't accommodate processes whose behavior changes during execution.
•Evolution: MLFQ extends MLQ with dynamic queue transitions based on observed behavior.

Looking Ahead:

The next page introduces the Multi-Level Feedback Queue (MLFQ)—the ingenious extension of MLQ that solves the static classification problem by dynamically adjusting process priority based on observed CPU usage patterns. MLFQ represents one of the most important scheduling innovations in operating system history.

Page Complete

You now possess comprehensive understanding of Multi-Level Queue scheduling—its architecture, policies, real-world implementations, and limitations. This foundation prepares you for mastering MLFQ, the dynamic scheduler that builds upon these concepts.

3 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Round Robin & Multi-Level Queue Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

3 / 5

Multi-Level Queue Scheduling

When One Queue Isn't Enough

What You Will Master

Motivation for Multi-Level Queues

Process Classification by Behavior:

Process Types and Their Scheduling Needs
Process Type	Characteristics	Scheduling Needs	Examples
Real-time	Strict timing deadlines, predictable bursts	Guaranteed CPU access, minimal latency	Audio/video playback, sensor polling
System/Kernel	Critical for OS operation, typically short bursts	High priority, fast response	Device drivers, kernel threads
Interactive	User-facing, short bursts between I/O	Low latency, responsive	Text editors, browsers, shells
Batch	CPU-intensive, can tolerate delays	High throughput, latency unimportant	Compilers, simulations, backups
Idle/Background	Run only when nothing else needs CPU	Lowest priority, opportunistic	Indexing, updates, maintenance

The Scheduling Policy Mismatch:

Each process type benefits from different scheduling approaches:

Real-time: Needs priority-based preemptive scheduling with deadline awareness
Interactive: Benefits from small time quanta for responsiveness
Batch: Benefits from large time quanta for throughput

A single policy cannot optimize for all. Round Robin with Q=10ms is too small for batch efficiency but potentially too large for real-time deadlines.

The Multi-Level Queue Solution:

MLQ addresses this by:

Partitioning processes into multiple queues based on type/priority
Applying different policies to each queue (e.g., FCFS, RR with different quanta)
Scheduling between queues using priority or time-slicing

This allows the scheduler to simultaneously optimize for responsiveness (high-priority queues), throughput (low-priority queues), and guaranteed access (real-time queues).

Division of Labor

Multi-Level Queue Architecture

A Multi-Level Queue scheduler maintains multiple ready queues, organized in a priority hierarchy. The fundamental architecture consists of:

1. Queue Hierarchy: Queues are arranged by priority, typically with smaller numbers indicating higher priority:

Queue 0: Real-time processes (highest priority)
Queue 1: System processes
Queue 2: Interactive processes
Queue 3: Batch processes
Queue 4: Idle processes (lowest priority)

2. Per-Queue Scheduling Policy: Each queue has its own internal scheduling algorithm:

Real-time queue: Priority scheduling with preemption
Interactive queue: Round Robin with small quantum (10ms)
Batch queue: FCFS or Round Robin with large quantum (100ms)

3. Inter-Queue Scheduling: A policy determines how CPU time is allocated among queues:

Fixed priority: Higher queues always preempt lower
Time-slicing: Each queue gets a percentage of CPU time

Converting Mermaid diagram...

multi_level_queue.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from collections import deque
from dataclasses import dataclass
from enum import IntEnum
from typing import List, Optional, Tuple
 
class QueuePriority(IntEnum):
    REAL_TIME = 0
    SYSTEM = 1
    INTERACTIVE = 2
    BATCH = 3
    IDLE = 4
 
@dataclass
class Process:
    pid: int
    name: str
    priority: QueuePriority
    burst_time: int
    remaining_time: int
    arrival_time: int
    completion_time: int = 0
 
@dataclass 
class MLQConfig:
    """Configuration for a single queue in the MLQ."""
    priority: QueuePriority
    name: str
    algorithm: str  # "RR" or "FCFS"
    quantum: int    # Time quantum for RR (ignored for FCFS)
    time_slice_pct: float  # Percentage of CPU for time-slicing mode
 
class MultiLevelQueueScheduler:
    """
    Multi-Level Queue Scheduler with configurable queues
    and inter-queue scheduling policies.
    """
    
    def __init__(
        self, 
        queue_configs: List[MLQConfig],
        inter_queue_policy: str = "fixed_priority"  # or "time_slicing"
    ):
        self.queues = {cfg.priority: deque() for cfg in queue_configs}
        self.configs = {cfg.priority: cfg for cfg in queue_configs}
        self.inter_queue_policy = inter_queue_policy
        self.current_time = 0
        self.execution_log = []
        
    def add_process(self, process: Process):
        """Add a process to its designated queue."""
        if process.priority in self.queues:
            self.queues[process.priority].append(process)
            self.execution_log.append(
                f"[{self.current_time:4d}] P{process.pid} ({process.name}) "
                f"added to {self.configs[process.priority].name}"
            )
    
    def get_highest_priority_queue(self) -> Optional[QueuePriority]:
        """Find the highest priority non-empty queue."""
        for priority in sorted(self.queues.keys()):
            if self.queues[priority]:
                return priority
        return None
    
    def schedule_fixed_priority(self) -> Tuple[List[Process], List[str]]:
        """
        Fixed priority inter-queue scheduling.
        Higher priority queues always get CPU first.
        Lower queues execute only when higher are empty.
        """
        completed = []
        
        while True:
            priority = self.get_highest_priority_queue()
            if priority is None:
                break
            
            config = self.configs[priority]
            queue = self.queues[priority]
            process = queue.popleft()
            
            # Determine execution time based on queue's algorithm
            if config.algorithm == "FCFS":
                exec_time = process.remaining_time
            else:  # RR
                exec_time = min(config.quantum, process.remaining_time)
            
            self.execution_log.append(
                f"[{self.current_time:4d}-{self.current_time + exec_time:4d}] "
                f"P{process.pid} executes from {config.name} ({exec_time}ms)"
            )
            
            process.remaining_time -= exec_time
            self.current_time += exec_time
            
            if process.remaining_time > 0:
                # Re-queue at tail
                queue.append(process)
            else:
                process.completion_time = self.current_time
                completed.append(process)
                self.execution_log.append(
                    f"        P{process.pid} completed"
                )
        
        return completed, self.execution_log
 
 
# Example: Create and run MLQ scheduler
if __name__ == "__main__":
    # Configure queues
    configs = [
        MLQConfig(QueuePriority.REAL_TIME, "Real-Time Queue", "RR", 5, 0.40),
        MLQConfig(QueuePriority.SYSTEM, "System Queue", "RR", 8, 0.25),
        MLQConfig(QueuePriority.INTERACTIVE, "Interactive Queue", "RR", 10, 0.20),
        MLQConfig(QueuePriority.BATCH, "Batch Queue", "RR", 50, 0.10),
        MLQConfig(QueuePriority.IDLE, "Idle Queue", "FCFS", 0, 0.05),
    ]
    
    scheduler = MultiLevelQueueScheduler(configs, "fixed_priority")
    
    # Add processes
    processes = [
        Process(1, "audio_player", QueuePriority.REAL_TIME, 15, 15, 0),
        Process(2, "kernel_thread", QueuePriority.SYSTEM, 10, 10, 0),
        Process(3, "bash_shell", QueuePriority.INTERACTIVE, 20, 20, 0),
        Process(4, "gcc_compile", QueuePriority.BATCH, 100, 100, 0),
        Process(5, "backup_job", QueuePriority.IDLE, 50, 50, 0),
    ]
    
    for p in processes:
        scheduler.add_process(p)
    
    completed, log = scheduler.schedule_fixed_priority()
    
    print("=" * 60)
    print("Multi-Level Queue Scheduling (Fixed Priority)")
    print("=" * 60)
    
    for entry in log:
        print(entry)
    
    print("
" + "-" * 60)
    print(f"{'PID':^5} {'Name':^15} {'Queue':^15} {'Completion':^12}")
    print("-" * 60)
    
    for p in completed:
        print(f"{p.pid:^5} {p.name:^15} "
              f"{QueuePriority(p.priority).name:^15} {p.completion_time:^12}")

Inter-Queue Scheduling Policies

A critical design decision in MLQ is how to allocate CPU time among the queues themselves. Two primary approaches exist:

Approach 1: Fixed Priority Scheduling (Absolute Priority)

Queues are served in strict priority order. A process from a lower-priority queue only executes when all higher-priority queues are empty.

Mechanics:

Scheduler always selects from the highest-priority non-empty queue
If a higher-priority process becomes ready, it preempts the current process
Lower-priority queues may starve if higher-priority queues are always busy

Advantages:

Simple to implement and reason about
Guarantees real-time and system processes get immediate attention
Clear priority semantics

Disadvantages:

Starvation risk: Batch and idle processes may never run under heavy interactive load
No throughput guarantees for lower-priority work

Approach 2: Time-Slice Scheduling (Proportional Share)

Each queue receives a guaranteed percentage of CPU time. The scheduler cycles among queues, giving each its allocated share.

Example allocation:

Real-time: 40% of CPU (4ms out of every 10ms)
System: 25% of CPU
Interactive: 20% of CPU
Batch: 10% of CPU
Idle: 5% of CPU

Mechanics:

Scheduler divides time into scheduling periods (e.g., 100ms)
Within each period, each queue receives its allocated time
Within the queue's time slice, its internal policy (RR/FCFS) runs
If a queue is empty during its slice, time goes to lower queues or is idle

Advantages:

Prevents starvation—every queue makes progress
Predictable throughput for all priority levels
Tunable balance between responsiveness and throughput

Disadvantages:

More complex implementation
Less responsive to priority—real-time may wait for its slice
May not match natural workload patterns

Comparison of Inter-Queue Scheduling Policies
Aspect	Fixed Priority	Time-Slicing
Implementation	Simple	Moderate complexity
Starvation Risk	High for low-priority	None (guaranteed shares)
Real-time Support	Excellent (immediate access)	Good (within share)
Throughput Control	Unpredictable for lower queues	Predictable allocation
Responsiveness	Optimal for high-priority	May delay high-priority
Fairness	Priority-based only	Both priority and share
Use Case	Real-time dominant systems	Mixed workload servers

Hybrid Approaches

Process Queue Assignment

Assignment Methods:

1. Explicit Class Specification: The process explicitly declares its scheduling class:

Unix nice value maps to priority/queue
POSIX real-time scheduling policies (SCHED_FIFO, SCHED_RR, SCHED_OTHER)
Windows priority classes (REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS, etc.)

2. Inheritance from Parent: Child processes inherit the scheduling class of their parent:

Shell spawns processes at interactive priority
System daemons spawn children at system priority
Can be overridden by explicit specification

3. User/Group Based: Assignment based on user identity or group membership:

Root/Administrator processes get system priority
Guest users get lower priority
Service accounts get specific priorities

4. Process Type Heuristics: Based on executable characteristics:

GUI applications → interactive queue
Background services → batch queue
Kernel threads → system queue

Queue Assignment in Major Operating Systems
OS	Assignment Mechanism	User Control
Linux	nice values (-20 to +19), scheduling policies	nice, renice, chrt commands
Windows	Priority classes (6 levels), thread priorities (7 levels)	Task Manager, SetPriorityClass API
macOS	QoS classes (User Interactive, Utility, Background, etc.)	dispatch_queue_attr API
FreeBSD	Nice values, SCHED_FIFO/RR for real-time	rtprio, idprio commands
Solaris	Fair share scheduler classes, projects	priocntl, prctl commands

queue_assignment.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* Linux example: Setting scheduling class and priority */
 
#include <sched.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdio.h>
 
/* Set process to real-time FIFO scheduling with priority 50 */
int set_realtime_priority(void) {
    struct sched_param param;
    param.sched_priority = 50;  /* Range: 1-99 for real-time */
    
    if (sched_setscheduler(0, SCHED_FIFO, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    printf("Set to SCHED_FIFO with priority %d
", param.sched_priority);
    return 0;
}
 
/* Set process to batch scheduling (throughput-oriented) */
int set_batch_priority(void) {
    struct sched_param param;
    param.sched_priority = 0;  /* Must be 0 for SCHED_BATCH */
    
    if (sched_setscheduler(0, SCHED_BATCH, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    /* Also set nice value to indicate low priority */
    if (setpriority(PRIO_PROCESS, 0, 19) == -1) {
        perror("setpriority failed");
        return -1;
    }
    
    printf("Set to SCHED_BATCH with nice 19
");
    return 0;
}
 
/* Set process to idle scheduling (only runs when system is idle) */
int set_idle_priority(void) {
    struct sched_param param;
    param.sched_priority = 0;
    
    if (sched_setscheduler(0, SCHED_IDLE, &param) == -1) {
        perror("sched_setscheduler failed");
        return -1;
    }
    
    printf("Set to SCHED_IDLE
");
    return 0;
}
 
/* Query current scheduling policy and priority */
void print_scheduling_info(void) {
    int policy = sched_getscheduler(0);
    struct sched_param param;
    sched_getparam(0, &param);
    
    const char* policy_name;
    switch (policy) {
        case SCHED_OTHER: policy_name = "SCHED_OTHER (CFS)"; break;
        case SCHED_FIFO:  policy_name = "SCHED_FIFO";        break;
        case SCHED_RR:    policy_name = "SCHED_RR";          break;
        case SCHED_BATCH: policy_name = "SCHED_BATCH";       break;
        case SCHED_IDLE:  policy_name = "SCHED_IDLE";        break;
        default:          policy_name = "Unknown";           break;
    }
    
    printf("Policy: %s, Priority: %d, Nice: %d
",
           policy_name, param.sched_priority,
           getpriority(PRIO_PROCESS, 0));
}

Static Assignment Limitations

Example MLQ Configuration

Let's examine a detailed example of an MLQ configuration for a general-purpose Unix-like system.

Queue Structure:

Example 5-Level MLQ Configuration
Queue	Priority	Scheduling	Quantum	Preemptible	Typical Processes
Real-Time FIFO	0	FCFS (non-preemptive)	∞	No	Kernel interrupt handlers
Real-Time RR	1	Round Robin	5ms	By higher only	Audio/video processing
Interactive	2	Round Robin	10ms	By higher	Shells, editors, browsers
Batch	3	Round Robin	100ms	By higher	Compilers, scientific apps
Idle	4	FCFS	∞	By all	Index builders, updates

Scenario Walkthrough:

Consider these processes in the system:

PID	Name	Queue	Burst Time
1	audio_daemon	Real-Time RR	20ms (periodic)
2	kernel_logger	Real-Time FIFO	5ms
3	vim_editor	Interactive	30ms
4	gcc_compiler	Batch	500ms
5	spotlight_index	Idle	1000ms

Execution with Fixed Priority:

Time 0-5:    kernel_logger runs to completion (RT FIFO, Q=∞)
Time 5-10:   audio_daemon runs (RT RR, Q=5ms)
Time 10-15:  audio_daemon continues (2nd quantum)
Time 15-20:  audio_daemon continues (3rd quantum)  
Time 20-25:  audio_daemon continues (4th quantum, completes)
Time 25-35:  vim_editor runs (Interactive, Q=10ms)
Time 35-45:  vim_editor continues (completes 30ms total at 55)
...
Time 55-155: gcc_compiler runs (Batch, Q=100ms)
...
Time 555:    spotlight starts (was waiting 555ms!)

Observation: The idle-priority spotlight_index must wait for ALL higher-priority work to complete. Under sustained interactive load, it might never run—classic starvation.

Mitigating Starvation

MLQ in Real Operating Systems

Modern operating systems implement variations of MLQ, typically combined with additional mechanisms to address starvation concerns.

Linux Scheduling Architecture:

Linux uses a two-tier multi-level queue structure:

Tier 1: Scheduling Classes (Priority Order)

SCHED_DEADLINE - Earliest Deadline First for deadline-guaranteed tasks
SCHED_FIFO - Real-time FCFS (run-to-completion)
SCHED_RR - Real-time Round Robin
SCHED_OTHER - Default, managed by CFS (Completely Fair Scheduler)
SCHED_BATCH - Batch processing (throughput-oriented CFS variant)
SCHED_IDLE - Runs only when system otherwise idle

Key Points:

Real-time classes have absolute priority over normal classes
Within real-time, FIFO and RR processes are ordered by static priority (1-99)
SCHED_OTHER processes never preempt real-time

Operating System Scheduling Architectures
OS	Queue Levels	Real-Time Support	Inter-Queue Policy
Linux	6 scheduling classes	SCHED_DEADLINE, SCHED_FIFO, SCHED_RR	Fixed priority by class, CFS within normal
Windows	32 priority levels in 6 classes	Real-time priority class (16-31)	Fixed priority with dynamic boost
macOS/iOS	4 QoS classes + real-time	Mach real-time threads	QoS-based resource allocation
FreeBSD	4 scheduling classes	SCHED_FIFO, SCHED_RR	ULE scheduler with interactivity scoring
Solaris	6 scheduling classes	Real-time, system classes	Configurable dispatcher table

Windows Scheduling Architecture:

Windows uses a 32-level priority system:

Levels 16-31: Real-time priority class (requires admin privileges)
Levels 1-15: Dynamic priority class (normal applications)
Level 0: System idle thread only

Within dynamic priority:

Base priority set by priority class (Normal, High, Above Normal, etc.)
Thread priority is base ± relative priority (Lowest to Highest)
Dynamic boosting: Interactive and I/O-completing threads get temporary priority boosts

Windows Foreground Boost: The foreground window's process receives a quantum boost (3× normal) to improve interactive responsiveness. This is a form of heuristic-based queue promotion.

macOS QoS (Quality of Service):

macOS uses semantic QoS classes rather than numeric priorities:

User Interactive - UI updates, animations
User Initiated - User-triggered tasks expecting immediate results
Utility - Long-running tasks with progress UI
Background - Tasks user doesn't directly see

The system maps QoS to scheduling parameters, adjusting priority and timer coalescing based on power state (plugged in vs. battery).

The Evolution Beyond Static MLQ

Advantages and Limitations

Advantages of MLQ

•Differentiated Service: Different process types get appropriate treatment. Real-time gets guaranteed access; batch gets efficient throughput.
•Per-Queue Optimization: Each queue can use the algorithm best suited to its processes (RR for interactive, FCFS for batch).
•Low Overhead: Simple queue selection based on priority—O(1) to find highest-priority non-empty queue.
•Predictable for Real-Time: High-priority queues have guaranteed preemption rights, enabling real-time guarantees.
•Clear Policy Semantics: Priority levels have intuitive meaning; easy to reason about system behavior.

Limitations of MLQ

•Starvation Risk: With fixed priority, low-priority queues may never execute under sustained high-priority load.
•Static Classification: Processes are assigned at creation; behavior changes aren't accommodated.
•Manual Tuning Required: Administrators must configure queue policies; poor configuration degrades performance.
•No Adaptive Behavior: System cannot learn that an 'interactive' process became CPU-bound.
•Configuration Complexity: Multiple queues with different parameters create many tuning knobs.

The Core Limitation:

MLQ assumes we know, at process creation time, what category the process belongs to and that this classification remains valid throughout execution. This assumption is often wrong:

A text editor is interactive while typing but CPU-bound during syntax highlighting
A web browser is interactive when scrolling but batch-like when loading pages
A compiler is batch during compilation but interactive when printing errors

The question becomes: Can the scheduler learn process behavior and adjust classification dynamically?

This question leads directly to the Multi-Level Feedback Queue (MLFQ)—the subject of our next page.

MLQ as Building Block

Summary: Multi-Level Queue Scheduling

We have thoroughly explored Multi-Level Queue scheduling—the architecture that addresses Round Robin's one-size-fits-all limitation by partitioning processes into specialized queues.

Key Takeaways

•Problem Addressed: Single-queue RR cannot optimize for processes with fundamentally different needs (real-time, interactive, batch).
•Core Architecture: Multiple ready queues arranged by priority, each with its own scheduling algorithm (FCFS, RR) and parameters (quantum).
•Inter-Queue Scheduling: Fixed priority (higher queues always preempt) or time-slicing (each queue gets a guaranteed CPU share).
•Process Assignment: Static, based on explicit specification, inheritance, or heuristics. Processes do not move between queues.
•Starvation Concern: Fixed priority inter-queue scheduling can starve low-priority queues under sustained high-priority load.
•Real-World Usage: All major OSes use MLQ concepts—Linux scheduling classes, Windows priority levels, macOS QoS classes.
•Limitation: Static classification doesn't accommodate processes whose behavior changes during execution.
•Evolution: MLFQ extends MLQ with dynamic queue transitions based on observed behavior.

Looking Ahead:

Page Complete

3 / 5