Priority Scheduling - Learning Module

Loading content...

0/227

Multiple Priority Levels

Organizing Priorities into Hierarchies

Real-world systems don't just have 'high' and 'low' priority processes—they have priority hierarchies with distinct classes of work requiring different treatment. A real-time control system, an interactive editor, a background compilation, and a nightly backup represent fundamentally different workload categories that benefit from separate scheduling treatment.

Multi-level priority queuing organizes processes into priority bands, potentially applying different scheduling algorithms within each band. This approach combines the responsiveness of priority scheduling with the flexibility of specialized per-class policies.

Learning Objectives

Understand multi-level queue architectures, analyze scheduling within and across priority levels, explore feedback mechanisms for dynamic level assignment, and recognize these patterns in Linux and Windows schedulers.

Multi-Level Queue Architecture

A multi-level queue (MLQ) scheduler maintains separate ready queues for each priority level. Key design decisions include:

Queue Organization

Number of levels: Typically 3-8 for general-purpose OS; 32-256 for real-time systems
Process assignment: Fixed (based on type) or dynamic (based on behavior)
Per-queue policy: Each level may use different scheduling algorithms

Inter-Queue Scheduling

How the scheduler selects which queue to service:

Strict priority: Always service highest non-empty queue (starvation risk)
Time-sliced: Allocate CPU percentage to each level
Weighted: Higher queues get more time but not exclusively

Converting Mermaid diagram...

Typical Multi-Level Queue Configuration
Level	Process Type	Algorithm	Time Quantum	Preemption
0 (Highest)	Real-time, hardware interrupts	FIFO or fixed priority	Unlimited/None	Only by same or higher level
1	System processes, kernel threads	Round-robin	Short (5-10ms)	By level 0
2	Interactive applications	Round-robin	Medium (20-50ms)	By levels 0-1
3	Batch processing	FCFS or SJF	Long (100-200ms)	By levels 0-2
4 (Lowest)	Idle/background tasks	FCFS	Remainder	By all higher levels

Scheduling Policies Per Level

Each priority level can employ a different scheduling algorithm optimized for its workload characteristics:

Common Per-Level Policies

•Real-time levels: FIFO — Highest priority, runs to completion or block. No time-slicing overhead. Used for latency-critical tasks.
•System levels: Short-quantum RR — Kernel threads need responsiveness. Short time slices ensure quick response to system events.
•Interactive levels: Medium-quantum RR — Balance between responsiveness and context switch overhead. Nice values may differentiate within level.
•Batch levels: FCFS or SJF — Throughput matters more than response time. Longer time slices reduce overhead.
•Idle level: FCFS — Runs only when nothing else needs CPU. No urgency, so simple policy suffices.

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
"""
Multi-Level Queue Scheduler Implementation
Demonstrates different policies per priority level.
"""
from dataclasses import dataclass, field
from typing import List, Dict, Optional
from collections import deque
from enum import Enum
 
class Policy(Enum):
    FIFO = "fifo"
    RR = "round_robin"
    SJF = "shortest_job_first"
 
@dataclass
class Process:
    pid: str
    level: int  # Queue level (0 = highest priority)
    burst: int
    remaining: int = field(init=False)
    
    def __post_init__(self):
        self.remaining = self.burst
 
@dataclass
class QueueConfig:
    policy: Policy
    quantum: Optional[int] = None  # For RR
 
class MultiLevelQueueScheduler:
    def __init__(self, configs: Dict[int, QueueConfig]):
        """configs: {level: QueueConfig}"""
        self.configs = configs
        self.queues: Dict[int, deque] = {level: deque() for level in configs}
        self.time = 0
        self.timeline: List[str] = []
        
    def add_process(self, process: Process):
        self.queues[process.level].append(process)
        
    def get_next_process(self) -> Optional[Process]:
        """Select from highest non-empty queue."""
        for level in sorted(self.queues.keys()):
            if self.queues[level]:
                config = self.configs[level]
                queue = self.queues[level]
                
                if config.policy == Policy.FIFO:
                    return queue[0]  # Don't remove yet
                elif config.policy == Policy.RR:
                    return queue[0]
                elif config.policy == Policy.SJF:
                    # Return shortest job
                    shortest = min(queue, key=lambda p: p.remaining)
                    return shortest
        return None
    
    def run_quantum(self, process: Process) -> bool:
        """Run process for one quantum. Returns True if completed."""
        config = self.configs[process.level]
        quantum = config.quantum or process.remaining
        
        run_time = min(quantum, process.remaining)
        process.remaining -= run_time
        
        self.timeline.append(
            f"t={self.time}-{self.time+run_time}: {process.pid} "
            f"(Level {process.level}, {config.policy.value})"
        )
        self.time += run_time
        
        return process.remaining == 0
    
    def run_simulation(self, processes: List[Process]):
        for p in processes:
            self.add_process(p)
            
        while any(self.queues[l] for l in self.queues):
            process = self.get_next_process()
            if not process:
                break
                
            config = self.configs[process.level]
            queue = self.queues[process.level]
            
            # Remove from queue
            queue.remove(process)
            
            completed = self.run_quantum(process)
            
            if not completed and config.policy == Policy.RR:
                # Re-add to back of queue
                queue.append(process)
            elif not completed:
                # FIFO/SJF: put back at appropriate position
                queue.appendleft(process)
                
        return self.timeline
 
# Configure: Level 0 = FIFO, Level 1 = RR(10), Level 2 = SJF
configs = {
    0: QueueConfig(Policy.FIFO),
    1: QueueConfig(Policy.RR, quantum=10),
    2: QueueConfig(Policy.SJF),
}
 
processes = [
    Process("RT_Task", level=0, burst=5),
    Process("Interactive1", level=1, burst=15),
    Process("Interactive2", level=1, burst=12),
    Process("Batch_Short", level=2, burst=8),
    Process("Batch_Long", level=2, burst=20),
]
 
scheduler = MultiLevelQueueScheduler(configs)
timeline = scheduler.run_simulation(processes)
 
print("Multi-Level Queue Schedule:")
for entry in timeline:
    print(f"  {entry}")

Multi-Level Feedback Queue (MLFQ)

The Multi-Level Feedback Queue extends MLQ by allowing processes to move between queues based on their behavior. This enables the scheduler to learn process characteristics and adapt scheduling accordingly.

MLFQ Rules

New processes start at highest priority level
If a process uses its entire quantum, demote it (move to lower priority queue)
If a process blocks before quantum expires, keep it at current level (or promote)
Periodically boost all processes to highest level (prevent starvation)

MLFQ automatically categorizes processes:

CPU-bound processes quickly demote to lower levels
I/O-bound processes stay at higher levels (they block before quantum expires)
Interactive processes get priority treatment

Converting Mermaid diagram...

mlfq_scheduler.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
"""
Multi-Level Feedback Queue (MLFQ) Implementation
Processes move between queues based on CPU usage behavior.
"""
from dataclasses import dataclass, field
from typing import List, Optional
from collections import deque
 
@dataclass
class Process:
    pid: str
    bursts: List[int]  # Alternating CPU bursts (simulates I/O-bound vs CPU-bound)
    current_burst: int = 0
    burst_progress: int = 0
    queue_level: int = 0
 
class MLFQScheduler:
    def __init__(self, num_levels: int = 4, boost_interval: int = 100):
        self.num_levels = num_levels
        self.boost_interval = boost_interval
        # Quantum doubles at each level
        self.quantums = [8 * (2 ** i) for i in range(num_levels)]
        self.queues: List[deque] = [deque() for _ in range(num_levels)]
        self.time = 0
        self.log: List[str] = []
        
    def add_process(self, process: Process):
        process.queue_level = 0  # Start at highest priority
        self.queues[0].append(process)
        self.log.append(f"t={self.time}: {process.pid} arrives at Q0")
        
    def priority_boost(self):
        """Move all processes to highest priority queue."""
        self.log.append(f"t={self.time}: PRIORITY BOOST - all processes to Q0")
        for level in range(1, self.num_levels):
            while self.queues[level]:
                p = self.queues[level].popleft()
                p.queue_level = 0
                self.queues[0].append(p)
                
    def demote(self, process: Process):
        """Move process to lower priority queue."""
        if process.queue_level < self.num_levels - 1:
            old_level = process.queue_level
            process.queue_level += 1
            self.log.append(
                f"t={self.time}: {process.pid} demoted Q{old_level} -> Q{process.queue_level}"
            )
            
    def run_simulation(self, processes: List[Process], max_time: int = 200):
        for p in processes:
            self.add_process(p)
            
        while self.time < max_time:
            # Priority boost check
            if self.time > 0 and self.time % self.boost_interval == 0:
                self.priority_boost()
                
            # Find highest non-empty queue
            current_process = None
            for level in range(self.num_levels):
                if self.queues[level]:
                    current_process = self.queues[level].popleft()
                    break
                    
            if not current_process:
                self.time += 1
                continue
                
            # Get quantum for current level
            quantum = self.quantums[current_process.queue_level]
            remaining_burst = (current_process.bursts[current_process.current_burst] 
                              - current_process.burst_progress)
            
            run_time = min(quantum, remaining_burst)
            
            self.log.append(
                f"t={self.time}: {current_process.pid} runs for {run_time} "
                f"(Q{current_process.queue_level}, quantum={quantum})"
            )
            
            self.time += run_time
            current_process.burst_progress += run_time
            
            # Check if burst complete
            if current_process.burst_progress >= current_process.bursts[current_process.current_burst]:
                current_process.current_burst += 1
                current_process.burst_progress = 0
                
                if current_process.current_burst >= len(current_process.bursts):
                    self.log.append(f"t={self.time}: {current_process.pid} COMPLETED")
                    continue
                    
                # Blocked for I/O - stays at current level (or could promote)
                self.queues[current_process.queue_level].append(current_process)
            else:
                # Used full quantum without blocking - demote
                self.demote(current_process)
                self.queues[current_process.queue_level].append(current_process)
                
        return self.log
 
# Simulate: CPU-bound process demotes, I/O-bound stays high
processes = [
    # I/O-bound: short bursts, will stay in high queue
    Process("IO_Bound", bursts=[4, 4, 4, 4, 4]),
    # CPU-bound: long bursts, will demote through queues
    Process("CPU_Bound", bursts=[50, 50]),
]
 
scheduler = MLFQScheduler(num_levels=4, boost_interval=80)
log = scheduler.run_simulation(processes, max_time=150)
 
print("MLFQ Simulation:")
for entry in log:
    print(f"  {entry}")

MLFQ Gaming Prevention

A malicious process could game MLFQ by issuing spurious I/O just before quantum expiration (staying high priority while still CPU-intensive). Modern schedulers track total CPU time at each level, demoting based on accumulated usage rather than single-quantum behavior.

Real-World Implementations

Linux Priority Levels

Linux uses 140 priority levels organized into two major classes:

Linux Priority Structure
Range	Class	Policy	Characteristics
0-99	Real-time	SCHED_FIFO or SCHED_RR	Fixed priority, no aging, preempts all normal
100-139	Normal	SCHED_OTHER (CFS)	Dynamic via nice values, fair sharing

Windows Priority Architecture

Windows uses a 32-level priority system with multi-level characteristics:

Windows Priority Levels
Level Range	Class	Typical Processes	Scheduling Behavior
31-24	Real-time	Drivers, multimedia	No boosting, strict priority
23-16	High	Critical services	Minimal interaction with lower
15-1	Dynamic	Normal applications	Priority boost/decay based on behavior
0	Zero Page	Idle thread	Only runs when nothing else to do

view_priority_levels.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/bin/bash
# View process priorities across multiple levels on Linux
 
echo "=== Real-Time Processes (Priorities 0-99) ==="
ps -eo pid,cls,rtprio,ni,comm --sort=-rtprio | head -20
 
echo ""
echo "=== Normal Processes by Nice Value ==="
ps -eo pid,ni,comm --sort=ni | grep -v "\[" | head -20
 
echo ""
echo "=== Scheduling Classes Distribution ==="
ps -eo cls | sort | uniq -c | sort -rn
 
echo ""
echo "=== CFS Scheduler Info ===" 
cat /proc/sched_debug 2>/dev/null | head -50 || echo "(Requires root)"

Design Considerations

Multi-Level Queue Design Decisions

•Number of levels — Too few limits flexibility; too many increases complexity. 4-8 levels typical for general-purpose systems.
•Queue assignment — Static (by process type) or dynamic (MLFQ). Static is simpler; dynamic adapts better.
•Inter-queue scheduling — Strict priority risks starvation. Time-sliced sharing between levels provides fairness.
•Quantum progression — MLFQ typically doubles quantum at each lower level, trading responsiveness for throughput.
•Boost frequency — Too frequent boosts negate priority benefits; too rare allows starvation. Common: every few seconds.
•Process type detection — Modern systems use heuristics (sleep ratio, I/O frequency) for automatic classification.

The CFS Alternative

Linux's Completely Fair Scheduler (CFS) takes a different approach: instead of discrete levels, it uses continuous virtual runtime. All normal processes share one 'level' with nice values modulating their time share. This elegant design avoids many MLQ complexities while achieving similar fairness goals.

Summary

Key Takeaways

•Multi-level queues organize processes into priority bands with per-level scheduling policies.
•Inter-queue scheduling determines which level services first—strict priority or time-sliced.
•MLFQ adds feedback — processes move between levels based on CPU usage behavior.
•MLFQ auto-classifies — CPU-bound processes demote; I/O-bound stay high priority.
•Priority boosts prevent starvation in MLFQ by periodically elevating all processes.
•Real systems use hybrid approaches — Linux combines real-time levels with CFS fair sharing.

Module Complete

You have completed Module 5: Priority Scheduling. You now understand priority assignment, preemptive vs non-preemptive scheduling, starvation and its prevention through aging, and multi-level priority queue architectures. These concepts form the foundation for understanding modern OS schedulers.

Multiple Priority Levels

Organizing Priorities into Hierarchies

Learning Objectives

Multi-Level Queue Architecture

A multi-level queue (MLQ) scheduler maintains separate ready queues for each priority level. Key design decisions include:

Queue Organization

Number of levels: Typically 3-8 for general-purpose OS; 32-256 for real-time systems
Process assignment: Fixed (based on type) or dynamic (based on behavior)
Per-queue policy: Each level may use different scheduling algorithms

Inter-Queue Scheduling

How the scheduler selects which queue to service:

Strict priority: Always service highest non-empty queue (starvation risk)
Time-sliced: Allocate CPU percentage to each level
Weighted: Higher queues get more time but not exclusively

Converting Mermaid diagram...

Typical Multi-Level Queue Configuration
Level	Process Type	Algorithm	Time Quantum	Preemption
0 (Highest)	Real-time, hardware interrupts	FIFO or fixed priority	Unlimited/None	Only by same or higher level
1	System processes, kernel threads	Round-robin	Short (5-10ms)	By level 0
2	Interactive applications	Round-robin	Medium (20-50ms)	By levels 0-1
3	Batch processing	FCFS or SJF	Long (100-200ms)	By levels 0-2
4 (Lowest)	Idle/background tasks	FCFS	Remainder	By all higher levels

Scheduling Policies Per Level

Each priority level can employ a different scheduling algorithm optimized for its workload characteristics:

Common Per-Level Policies

•Real-time levels: FIFO — Highest priority, runs to completion or block. No time-slicing overhead. Used for latency-critical tasks.
•System levels: Short-quantum RR — Kernel threads need responsiveness. Short time slices ensure quick response to system events.
•Interactive levels: Medium-quantum RR — Balance between responsiveness and context switch overhead. Nice values may differentiate within level.
•Batch levels: FCFS or SJF — Throughput matters more than response time. Longer time slices reduce overhead.
•Idle level: FCFS — Runs only when nothing else needs CPU. No urgency, so simple policy suffices.

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
"""
Multi-Level Queue Scheduler Implementation
Demonstrates different policies per priority level.
"""
from dataclasses import dataclass, field
from typing import List, Dict, Optional
from collections import deque
from enum import Enum
 
class Policy(Enum):
    FIFO = "fifo"
    RR = "round_robin"
    SJF = "shortest_job_first"
 
@dataclass
class Process:
    pid: str
    level: int  # Queue level (0 = highest priority)
    burst: int
    remaining: int = field(init=False)
    
    def __post_init__(self):
        self.remaining = self.burst
 
@dataclass
class QueueConfig:
    policy: Policy
    quantum: Optional[int] = None  # For RR
 
class MultiLevelQueueScheduler:
    def __init__(self, configs: Dict[int, QueueConfig]):
        """configs: {level: QueueConfig}"""
        self.configs = configs
        self.queues: Dict[int, deque] = {level: deque() for level in configs}
        self.time = 0
        self.timeline: List[str] = []
        
    def add_process(self, process: Process):
        self.queues[process.level].append(process)
        
    def get_next_process(self) -> Optional[Process]:
        """Select from highest non-empty queue."""
        for level in sorted(self.queues.keys()):
            if self.queues[level]:
                config = self.configs[level]
                queue = self.queues[level]
                
                if config.policy == Policy.FIFO:
                    return queue[0]  # Don't remove yet
                elif config.policy == Policy.RR:
                    return queue[0]
                elif config.policy == Policy.SJF:
                    # Return shortest job
                    shortest = min(queue, key=lambda p: p.remaining)
                    return shortest
        return None
    
    def run_quantum(self, process: Process) -> bool:
        """Run process for one quantum. Returns True if completed."""
        config = self.configs[process.level]
        quantum = config.quantum or process.remaining
        
        run_time = min(quantum, process.remaining)
        process.remaining -= run_time
        
        self.timeline.append(
            f"t={self.time}-{self.time+run_time}: {process.pid} "
            f"(Level {process.level}, {config.policy.value})"
        )
        self.time += run_time
        
        return process.remaining == 0
    
    def run_simulation(self, processes: List[Process]):
        for p in processes:
            self.add_process(p)
            
        while any(self.queues[l] for l in self.queues):
            process = self.get_next_process()
            if not process:
                break
                
            config = self.configs[process.level]
            queue = self.queues[process.level]
            
            # Remove from queue
            queue.remove(process)
            
            completed = self.run_quantum(process)
            
            if not completed and config.policy == Policy.RR:
                # Re-add to back of queue
                queue.append(process)
            elif not completed:
                # FIFO/SJF: put back at appropriate position
                queue.appendleft(process)
                
        return self.timeline
 
# Configure: Level 0 = FIFO, Level 1 = RR(10), Level 2 = SJF
configs = {
    0: QueueConfig(Policy.FIFO),
    1: QueueConfig(Policy.RR, quantum=10),
    2: QueueConfig(Policy.SJF),
}
 
processes = [
    Process("RT_Task", level=0, burst=5),
    Process("Interactive1", level=1, burst=15),
    Process("Interactive2", level=1, burst=12),
    Process("Batch_Short", level=2, burst=8),
    Process("Batch_Long", level=2, burst=20),
]
 
scheduler = MultiLevelQueueScheduler(configs)
timeline = scheduler.run_simulation(processes)
 
print("Multi-Level Queue Schedule:")
for entry in timeline:
    print(f"  {entry}")

Multi-Level Feedback Queue (MLFQ)

MLFQ Rules

New processes start at highest priority level
If a process uses its entire quantum, demote it (move to lower priority queue)
If a process blocks before quantum expires, keep it at current level (or promote)
Periodically boost all processes to highest level (prevent starvation)

MLFQ automatically categorizes processes:

CPU-bound processes quickly demote to lower levels
I/O-bound processes stay at higher levels (they block before quantum expires)
Interactive processes get priority treatment

Converting Mermaid diagram...

mlfq_scheduler.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
"""
Multi-Level Feedback Queue (MLFQ) Implementation
Processes move between queues based on CPU usage behavior.
"""
from dataclasses import dataclass, field
from typing import List, Optional
from collections import deque
 
@dataclass
class Process:
    pid: str
    bursts: List[int]  # Alternating CPU bursts (simulates I/O-bound vs CPU-bound)
    current_burst: int = 0
    burst_progress: int = 0
    queue_level: int = 0
 
class MLFQScheduler:
    def __init__(self, num_levels: int = 4, boost_interval: int = 100):
        self.num_levels = num_levels
        self.boost_interval = boost_interval
        # Quantum doubles at each level
        self.quantums = [8 * (2 ** i) for i in range(num_levels)]
        self.queues: List[deque] = [deque() for _ in range(num_levels)]
        self.time = 0
        self.log: List[str] = []
        
    def add_process(self, process: Process):
        process.queue_level = 0  # Start at highest priority
        self.queues[0].append(process)
        self.log.append(f"t={self.time}: {process.pid} arrives at Q0")
        
    def priority_boost(self):
        """Move all processes to highest priority queue."""
        self.log.append(f"t={self.time}: PRIORITY BOOST - all processes to Q0")
        for level in range(1, self.num_levels):
            while self.queues[level]:
                p = self.queues[level].popleft()
                p.queue_level = 0
                self.queues[0].append(p)
                
    def demote(self, process: Process):
        """Move process to lower priority queue."""
        if process.queue_level < self.num_levels - 1:
            old_level = process.queue_level
            process.queue_level += 1
            self.log.append(
                f"t={self.time}: {process.pid} demoted Q{old_level} -> Q{process.queue_level}"
            )
            
    def run_simulation(self, processes: List[Process], max_time: int = 200):
        for p in processes:
            self.add_process(p)
            
        while self.time < max_time:
            # Priority boost check
            if self.time > 0 and self.time % self.boost_interval == 0:
                self.priority_boost()
                
            # Find highest non-empty queue
            current_process = None
            for level in range(self.num_levels):
                if self.queues[level]:
                    current_process = self.queues[level].popleft()
                    break
                    
            if not current_process:
                self.time += 1
                continue
                
            # Get quantum for current level
            quantum = self.quantums[current_process.queue_level]
            remaining_burst = (current_process.bursts[current_process.current_burst] 
                              - current_process.burst_progress)
            
            run_time = min(quantum, remaining_burst)
            
            self.log.append(
                f"t={self.time}: {current_process.pid} runs for {run_time} "
                f"(Q{current_process.queue_level}, quantum={quantum})"
            )
            
            self.time += run_time
            current_process.burst_progress += run_time
            
            # Check if burst complete
            if current_process.burst_progress >= current_process.bursts[current_process.current_burst]:
                current_process.current_burst += 1
                current_process.burst_progress = 0
                
                if current_process.current_burst >= len(current_process.bursts):
                    self.log.append(f"t={self.time}: {current_process.pid} COMPLETED")
                    continue
                    
                # Blocked for I/O - stays at current level (or could promote)
                self.queues[current_process.queue_level].append(current_process)
            else:
                # Used full quantum without blocking - demote
                self.demote(current_process)
                self.queues[current_process.queue_level].append(current_process)
                
        return self.log
 
# Simulate: CPU-bound process demotes, I/O-bound stays high
processes = [
    # I/O-bound: short bursts, will stay in high queue
    Process("IO_Bound", bursts=[4, 4, 4, 4, 4]),
    # CPU-bound: long bursts, will demote through queues
    Process("CPU_Bound", bursts=[50, 50]),
]
 
scheduler = MLFQScheduler(num_levels=4, boost_interval=80)
log = scheduler.run_simulation(processes, max_time=150)
 
print("MLFQ Simulation:")
for entry in log:
    print(f"  {entry}")

MLFQ Gaming Prevention

Real-World Implementations

Linux Priority Levels

Linux uses 140 priority levels organized into two major classes:

Linux Priority Structure
Range	Class	Policy	Characteristics
0-99	Real-time	SCHED_FIFO or SCHED_RR	Fixed priority, no aging, preempts all normal
100-139	Normal	SCHED_OTHER (CFS)	Dynamic via nice values, fair sharing

Windows Priority Architecture

Windows uses a 32-level priority system with multi-level characteristics:

Windows Priority Levels
Level Range	Class	Typical Processes	Scheduling Behavior
31-24	Real-time	Drivers, multimedia	No boosting, strict priority
23-16	High	Critical services	Minimal interaction with lower
15-1	Dynamic	Normal applications	Priority boost/decay based on behavior
0	Zero Page	Idle thread	Only runs when nothing else to do

view_priority_levels.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/bin/bash
# View process priorities across multiple levels on Linux
 
echo "=== Real-Time Processes (Priorities 0-99) ==="
ps -eo pid,cls,rtprio,ni,comm --sort=-rtprio | head -20
 
echo ""
echo "=== Normal Processes by Nice Value ==="
ps -eo pid,ni,comm --sort=ni | grep -v "\[" | head -20
 
echo ""
echo "=== Scheduling Classes Distribution ==="
ps -eo cls | sort | uniq -c | sort -rn
 
echo ""
echo "=== CFS Scheduler Info ===" 
cat /proc/sched_debug 2>/dev/null | head -50 || echo "(Requires root)"

Design Considerations

Multi-Level Queue Design Decisions

•Number of levels — Too few limits flexibility; too many increases complexity. 4-8 levels typical for general-purpose systems.
•Queue assignment — Static (by process type) or dynamic (MLFQ). Static is simpler; dynamic adapts better.
•Inter-queue scheduling — Strict priority risks starvation. Time-sliced sharing between levels provides fairness.
•Quantum progression — MLFQ typically doubles quantum at each lower level, trading responsiveness for throughput.
•Boost frequency — Too frequent boosts negate priority benefits; too rare allows starvation. Common: every few seconds.
•Process type detection — Modern systems use heuristics (sleep ratio, I/O frequency) for automatic classification.

The CFS Alternative

Summary

Key Takeaways

•Multi-level queues organize processes into priority bands with per-level scheduling policies.
•Inter-queue scheduling determines which level services first—strict priority or time-sliced.
•MLFQ adds feedback — processes move between levels based on CPU usage behavior.
•MLFQ auto-classifies — CPU-bound processes demote; I/O-bound stay high priority.
•Priority boosts prevent starvation in MLFQ by periodically elevating all processes.
•Real systems use hybrid approaches — Linux combines real-time levels with CFS fair sharing.

Module Complete