Multilevel Queue & Feedback Queue Scheduling: A Practical Guide

Imagine you're designing the CPU scheduler for a modern operating system. You have a mix of processes: some are interactive (like a text editor) that need quick response, others are batch (like video encoding) that can wait. How do you ensure fairness and efficiency? This is where Multilevel Queue (MLQ) and Multilevel Feedback Queue (MLFQ) scheduling come in.

These algorithms are not just academic—they power the schedulers in Linux, Windows, and macOS. For instance, Linux's Completely Fair Scheduler (CFS) uses a variant of MLFQ. Understanding them is crucial for systems programmers, game developers, and anyone building real-time applications.

In this tutorial, you'll learn the core concepts, see production-ready Python implementations, and discover how to debug scheduling issues. We'll cover the classic MLQ model (foreground/background queues) and the adaptive MLFQ that prevents starvation. By the end, you'll be able to implement your own scheduler or optimize existing ones.

What is Multilevel Queue Scheduling?

Multilevel Queue (MLQ) scheduling partitions the ready queue into several separate queues, each with its own scheduling algorithm. Processes are permanently assigned to a queue based on their type (e.g., foreground interactive, background batch). Each queue has a priority relative to others, and the scheduler picks processes from the highest-priority non-empty queue. Common algorithms per queue include Round Robin (RR) for interactive and First-Come-First-Serve (FCFS) for batch.

Key characteristics: - Fixed assignment: a process never moves between queues. - Multiple scheduling policies: each queue can use a different algorithm. - Priority scheduling: queues have fixed priorities, usually with preemption.

Example: - Queue 0 (highest priority): foreground processes, RR with time quantum 8ms. - Queue 1: background processes, FCFS. - Queue 2 (lowest): batch jobs, FCFS.

Advantages: Low overhead, simple to implement. Disadvantages: Starvation of low-priority queues; if a high-priority queue always has processes, lower queues never run.

import heapq
from collections import deque

class Process:
    def __init__(self, pid, burst_time, queue_id):
        self.pid = pid
        self.burst_time = burst_time
        self.queue_id = queue_id
        self.remaining_time = burst_time

class MLQScheduler:
    def __init__(self, queues):
        # queues: list of (priority, algorithm, time_quantum)
        # priority: lower number = higher priority
        self.queues = sorted(queues, key=lambda x: x[0])
        self.queue_list = [deque() for _ in range(len(queues))]
    
    def add_process(self, process):
        qid = process.queue_id
        if qid < len(self.queue_list):
            self.queue_list[qid].append(process)
    
    def schedule(self):
        time = 0
        while any(self.queue_list):
            for i, (priority, algo, quantum) in enumerate(self.queues):
                q = self.queue_list[i]
                if not q:
                    continue
                if algo == 'rr':
                    process = q.popleft()
                    run_time = min(quantum, process.remaining_time)
                    process.remaining_time -= run_time
                    time += run_time
                    print(f"Time {time}: Process {process.pid} ran for {run_time}ms")
                    if process.remaining_time > 0:
                        q.append(process)
                    else:
                        print(f"Process {process.pid} completed at time {time}")
                elif algo == 'fcfs':
                    process = q.popleft()
                    time += process.remaining_time
                    print(f"Time {time}: Process {process.pid} completed (FCFS)")
                break  # after running one process, restart from highest priority

# Example usage
if __name__ == '__main__':
    # Queue 0: RR with 8ms quantum, Queue 1: FCFS
    scheduler = MLQScheduler([(0, 'rr', 8), (1, 'fcfs', None)])
    scheduler.add_process(Process(1, 20, 0))
    scheduler.add_process(Process(2, 10, 1))
    scheduler.add_process(Process(3, 5, 0))
    scheduler.schedule()

Multilevel Feedback Queue (MLFQ) – The Adaptive Scheduler

Multilevel Feedback Queue (MLFQ) addresses MLQ's rigidity by allowing processes to move between queues. The basic idea: a process starts in the highest-priority queue. If it uses its entire time quantum without blocking (i.e., it's CPU-bound), it gets demoted to a lower-priority queue. If it blocks before using its quantum (I/O-bound), it stays or is promoted. This adapts to process behavior: interactive processes stay high, batch processes sink low.

Rules (classic MLFQ): 1. If Priority(A) > Priority(B), A runs. 2. If Priority(A) == Priority(B), A and B run in RR. 3. When a process enters the system, it's placed at the highest priority. 4. If a process uses its entire time quantum, it's demoted one level. 5. After some time period S, move all processes to the topmost queue (to prevent starvation).

Advantages: Responsive to interactive processes, prevents starvation with periodic boosts. Disadvantages: Complexity, parameter tuning (number of queues, quanta, boost period).

from collections import deque

class Process:
    def __init__(self, pid, burst_time):
        self.pid = pid
        self.burst_time = burst_time
        self.remaining_time = burst_time
        self.queue_level = 0  # start at highest priority

class MLFQScheduler:
    def __init__(self, num_queues, time_quanta, boost_interval):
        self.num_queues = num_queues
        self.time_quanta = time_quanta  # list of quanta per level
        self.boost_interval = boost_interval
        self.queues = [deque() for _ in range(num_queues)]
        self.current_time = 0
        self.last_boost_time = 0
    
    def add_process(self, process):
        self.queues[0].append(process)
    
    def _boost(self):
        for q in range(1, self.num_queues):
            while self.queues[q]:
                p = self.queues[q].popleft()
                p.queue_level = 0
                self.queues[0].append(p)
        self.last_boost_time = self.current_time
    
    def schedule(self):
        while any(self.queues):
            # Check for boost
            if self.current_time - self.last_boost_time >= self.boost_interval:
                self._boost()
            
            # Find highest priority non-empty queue
            for level in range(self.num_queues):
                if self.queues[level]:
                    process = self.queues[level].popleft()
                    quantum = self.time_quanta[level]
                    run_time = min(quantum, process.remaining_time)
                    process.remaining_time -= run_time
                    self.current_time += run_time
                    print(f"Time {self.current_time}: Process {process.pid} ran for {run_time}ms at level {level}")
                    if process.remaining_time == 0:
                        print(f"Process {process.pid} completed")
                    else:
                        # Demote if used full quantum
                        if run_time == quantum:
                            new_level = min(level + 1, self.num_queues - 1)
                            process.queue_level = new_level
                            self.queues[new_level].append(process)
                        else:
                            # Did not use full quantum, stay at same level
                            self.queues[level].append(process)
                    break  # after one process, restart from top

# Example usage
if __name__ == '__main__':
    scheduler = MLFQScheduler(num_queues=3, time_quanta=[8, 16, 32], boost_interval=100)
    scheduler.add_process(Process(1, 30))
    scheduler.add_process(Process(2, 10))
    scheduler.add_process(Process(3, 5))
    scheduler.schedule()

Comparison: MLQ vs MLFQ

Both algorithms aim to balance responsiveness and throughput, but they differ in flexibility and complexity.

MLQ: - Fixed queue assignment. - Simple implementation. - Starvation possible. - Used in specialized systems (e.g., real-time).

MLFQ: - Dynamic queue movement. - More complex. - Prevents starvation with boosting. - Used in general-purpose OS.

When to use which? - Use MLQ if process behavior is known and static (e.g., embedded systems). - Use MLFQ for general-purpose workloads with mixed interactive and batch processes.

Implementing MLFQ in Production: Pitfalls and Best Practices

Implementing MLFQ in a real OS or application requires careful consideration:

1. Choosing time quanta: Too small causes high context switch overhead; too large causes unresponsiveness. Rule of thumb: highest priority quantum = 1-10ms, increase by factor of 2-4 per level.
2. Boost interval: Too frequent boosts defeat the purpose of feedback; too rare causes starvation. Typical values: 100-200ms.
3. I/O-bound vs CPU-bound detection: A process that blocks before using its quantum is likely I/O-bound. In MLFQ, such processes should stay or be promoted. In our implementation, we kept them at the same level, but some variants promote them.
4. Starvation of low-priority queues: Even with boosts, if CPU-bound processes keep getting demoted, they may never get CPU. Solution: implement aging (increase priority of waiting processes over time).
5. Overhead: Each context switch and queue manipulation adds overhead. Use efficient data structures (e.g., linked lists for queues).

Best practices: - Profile your workload to set initial parameters. - Monitor queue lengths and wait times. - Use adaptive algorithms that adjust quanta based on load.

class MLFQWithAging(MLFQScheduler):
    def __init__(self, num_queues, time_quanta, boost_interval, aging_threshold):
        super().__init__(num_queues, time_quanta, boost_interval)
        self.aging_threshold = aging_threshold  # time in ms after which a process is promoted
        self.wait_times = {}  # pid -> time spent waiting
    
    def schedule(self):
        # Override to add aging
        while any(self.queues):
            # Update wait times for all processes in queues
            for level in range(self.num_queues):
                for p in self.queues[level]:
                    self.wait_times[p.pid] = self.wait_times.get(p.pid, 0) + 1  # assume 1ms per iteration
                    if self.wait_times[p.pid] >= self.aging_threshold:
                        # Promote to higher priority
                        self.queues[level].remove(p)
                        new_level = max(0, level - 1)
                        p.queue_level = new_level
                        self.queues[new_level].append(p)
                        self.wait_times[p.pid] = 0
            # Continue with normal scheduling
            # ... (same as MLFQScheduler.schedule)
            break  # placeholder

Real-World Examples: Linux, Windows, macOS

Linux: The Completely Fair Scheduler (CFS) is not a pure MLFQ but uses a red-black tree of processes sorted by virtual runtime (vruntime). It aims to give each process a fair share of CPU. However, it incorporates priority (nice values) and supports real-time scheduling policies (SCHED_FIFO, SCHED_RR) which are essentially MLQ.

Windows: Uses a multilevel feedback queue with 32 priority levels. Processes start at a base priority and can be boosted temporarily for I/O completion. The scheduler uses round-robin within each level.

macOS: Uses a hybrid of MLFQ and CFS. It has multiple priority bands (normal, system, real-time) with feedback.

Key takeaway: Most modern OS schedulers are variants of MLFQ, demonstrating its effectiveness.

When to Use MLQ vs MLFQ: A Decision Guide

Use MLQ when: - Process types are known and fixed (e.g., foreground/background). - You need deterministic behavior. - Overhead must be minimal. - System is specialized (e.g., embedded, real-time).

Use MLFQ when: - Workload is mixed and unpredictable. - You need to prevent starvation. - Responsiveness is critical. - You can afford some overhead.

Trade-offs: - MLQ: simpler, but may require manual tuning and can starve. - MLFQ: more complex, but adapts automatically.

Example scenarios: - A video game console: MLQ (foreground game, background downloads). - A web server: MLFQ (handle many short requests and occasional long ones).