Case Study 2: How Operating Systems Use Queues

Contributors

Case Study 2: How Operating Systems Use Queues

Process Scheduling and I/O Queues

Right now, your computer is running dozens — perhaps hundreds — of processes simultaneously: a web browser with multiple tabs, a music player, a code editor, system services, background updates. But most computers have only a handful of CPU cores. How does your operating system create the illusion of everything running at once? The answer lies in one of the oldest and most important applications of the queue data structure: process scheduling.

The Problem: One CPU, Many Processes

Imagine a restaurant with a single chef. Orders arrive from multiple tables, each requiring different preparation times. The chef can only cook one dish at a time. How should the restaurant decide which order to prepare next?

This is exactly the problem an operating system faces. The CPU is the chef. Processes (running programs) are the orders. The operating system is the manager who decides what gets cooked when.

The simplest approach: First-Come, First-Served (FCFS) — process tasks in the order they arrive. This is a queue.

Simulating FCFS Scheduling

Let's simulate a basic process scheduler using our Queue class:

from collections import deque


class Queue:
    """A First-In, First-Out (FIFO) data structure."""

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)


class Process:
    """Represents a process waiting to use the CPU."""

    def __init__(self, name: str, burst_time: int, arrival_time: int = 0):
        self.name = name
        self.burst_time = burst_time       # CPU time needed (ms)
        self.arrival_time = arrival_time   # when the process arrived
        self.start_time: int | None = None
        self.finish_time: int | None = None

    @property
    def wait_time(self) -> int | None:
        if self.start_time is None:
            return None
        return self.start_time - self.arrival_time

    @property
    def turnaround_time(self) -> int | None:
        if self.finish_time is None:
            return None
        return self.finish_time - self.arrival_time

    def __repr__(self) -> str:
        return f"Process('{self.name}', burst={self.burst_time}ms)"


def fcfs_schedule(processes: list[Process]) -> None:
    """Simulate First-Come, First-Served scheduling."""
    ready_queue = Queue()
    for p in processes:
        ready_queue.enqueue(p)

    current_time = 0
    print(f"{'Process':<12} {'Arrival':>8} {'Burst':>6} "
          f"{'Start':>6} {'Finish':>7} {'Wait':>6} {'Turnaround':>11}")
    print("-" * 62)

    while not ready_queue.is_empty():
        process = ready_queue.dequeue()

        # If the process arrived after current_time, CPU was idle
        if process.arrival_time > current_time:
            current_time = process.arrival_time

        process.start_time = current_time
        process.finish_time = current_time + process.burst_time
        current_time = process.finish_time

        print(f"{process.name:<12} {process.arrival_time:>8} "
              f"{process.burst_time:>6} {process.start_time:>6} "
              f"{process.finish_time:>7} {process.wait_time:>6} "
              f"{process.turnaround_time:>11}")

    # Summary statistics
    total_wait = sum(p.wait_time for p in processes)
    total_turnaround = sum(p.turnaround_time for p in processes)
    n = len(processes)
    print(f"\nAverage wait time:       {total_wait / n:.1f}ms")
    print(f"Average turnaround time: {total_turnaround / n:.1f}ms")


# Simulate!
processes = [
    Process("Chrome",    10, arrival_time=0),
    Process("VS Code",    4, arrival_time=1),
    Process("Spotify",    2, arrival_time=2),
    Process("Terminal",   1, arrival_time=3),
    Process("Slack",      5, arrival_time=4),
]

print("=== First-Come, First-Served (FCFS) Scheduling ===\n")
fcfs_schedule(processes)

# Expected output:
# === First-Come, First-Served (FCFS) Scheduling ===
#
# Process       Arrival  Burst  Start  Finish   Wait  Turnaround
# --------------------------------------------------------------
# Chrome              0     10      0      10      0          10
# VS Code             1      4     10      14      9          13
# Spotify             2      2     14      16     12          14
# Terminal            3      1     16      17     13          14
# Slack               4      5     17      22     13          18
#
# Average wait time:       9.4ms
# Average turnaround time: 13.8ms

The Problem with FCFS

Look at the results above. Chrome takes 10ms and goes first. Every other process waits 10ms just because Chrome arrived first. Terminal only needs 1ms of CPU time but waits 13ms. This is called the convoy effect — short processes get stuck behind long ones.

It's like being at the grocery store with one item, stuck behind someone with a full cart. Frustrating — and inefficient.

Most modern operating systems use a variation of Round Robin (RR) scheduling. Each process gets a fixed time slice (called a quantum or time slice). If a process doesn't finish in its quantum, it goes back to the end of the queue.

def round_robin_schedule(processes: list[Process],
                         quantum: int) -> None:
    """Simulate Round Robin scheduling with a given time quantum."""
    ready_queue = Queue()
    remaining: dict[str, int] = {}

    for p in processes:
        ready_queue.enqueue(p)
        remaining[p.name] = p.burst_time

    current_time = 0
    execution_log: list[tuple[str, int, int]] = []
    completed: dict[str, int] = {}

    while not ready_queue.is_empty():
        process = ready_queue.dequeue()

        if process.arrival_time > current_time:
            current_time = process.arrival_time

        if process.start_time is None:
            process.start_time = current_time

        # Execute for at most `quantum` ms
        run_time = min(quantum, remaining[process.name])
        execution_log.append((process.name, current_time,
                              current_time + run_time))
        current_time += run_time
        remaining[process.name] -= run_time

        if remaining[process.name] == 0:
            # Process is done
            process.finish_time = current_time
            completed[process.name] = current_time
        else:
            # Process needs more time — back to the queue
            ready_queue.enqueue(process)

    # Print execution timeline
    print(f"Time quantum: {quantum}ms\n")
    print("Execution timeline:")
    for name, start, end in execution_log:
        bar = "#" * (end - start)
        print(f"  [{start:>3}-{end:>3}] {name:<12} {bar}")

    # Print summary
    print(f"\n{'Process':<12} {'Burst':>6} {'Finish':>7} "
          f"{'Wait':>6} {'Turnaround':>11}")
    print("-" * 48)

    total_wait = 0
    total_turnaround = 0
    for p in processes:
        wait = p.finish_time - p.arrival_time - p.burst_time
        turnaround = p.finish_time - p.arrival_time
        total_wait += wait
        total_turnaround += turnaround
        print(f"{p.name:<12} {p.burst_time:>6} {p.finish_time:>7} "
              f"{wait:>6} {turnaround:>11}")

    n = len(processes)
    print(f"\nAverage wait time:       {total_wait / n:.1f}ms")
    print(f"Average turnaround time: {total_turnaround / n:.1f}ms")


# Reset processes
processes_rr = [
    Process("Chrome",    10, arrival_time=0),
    Process("VS Code",    4, arrival_time=0),
    Process("Spotify",    2, arrival_time=0),
    Process("Terminal",   1, arrival_time=0),
    Process("Slack",      5, arrival_time=0),
]

print("\n=== Round Robin Scheduling ===\n")
round_robin_schedule(processes_rr, quantum=3)

# Expected output:
# === Round Robin Scheduling ===
#
# Time quantum: 3ms
#
# Execution timeline:
#   [  0-  3] Chrome       ###
#   [  3-  6] VS Code      ###
#   [  6-  8] Spotify      ##
#   [  8-  9] Terminal     #
#   [  9- 12] Slack        ###
#   [ 12- 15] Chrome       ###
#   [ 15- 16] VS Code      #
#   [ 16- 18] Slack        ##
#   [ 18- 22] Chrome       ####
#
# Process       Burst  Finish   Wait  Turnaround
# ------------------------------------------------
# Chrome           10      22     12          22
# VS Code           4      16     12          16
# Spotify           2       8      6           8
# Terminal          1       9      8           9
# Slack             5      18     13          18
#
# Average wait time:       10.2ms
# Average turnaround time: 14.6ms

Comparing the Two Approaches

Metric	FCFS	Round Robin (q=3)
Avg wait time	9.4ms	10.2ms
Avg turnaround time	13.8ms	14.6ms
Fairness	Low — long jobs block short ones	High — everyone gets regular turns
Responsiveness	Low — short jobs may wait a long time	High — every process runs within one quantum

Round Robin's average times are slightly worse in this example, but that misses the point. In an interactive system (like your desktop), responsiveness matters more than average completion time. You want Spotify to keep playing music, your terminal to respond to keystrokes, and your browser to stay interactive — all at the same time. Round Robin achieves this by giving each process a fair share of CPU time.

I/O Queues: The Other Kind of Waiting

Process scheduling isn't the only place operating systems use queues. I/O queues manage access to shared hardware resources:

Disk I/O queue: When multiple processes want to read from or write to the hard drive, requests are queued. The disk controller processes them one at a time (or optimizes their order to minimize seek time).
Network I/O queue: Outgoing network packets are queued in a buffer. If packets arrive faster than the network can send them, the queue fills up and eventually drops packets — this is what causes "network congestion."
Print queue: When you print from multiple applications, the print spooler queues documents and sends them to the printer one at a time. This is why you sometimes see "3 documents waiting" in your print dialog.

Here's a simplified I/O queue simulation:

class IORequest:
    """Represents a request to read/write a file."""

    def __init__(self, process: str, operation: str,
                 filename: str, size_kb: int):
        self.process = process
        self.operation = operation   # "read" or "write"
        self.filename = filename
        self.size_kb = size_kb

    def __repr__(self) -> str:
        return (f"{self.process}: {self.operation} "
                f"'{self.filename}' ({self.size_kb}KB)")


def simulate_io_queue(requests: list[IORequest],
                      bandwidth_kb_per_ms: int = 10) -> None:
    """Simulate an I/O queue processing disk requests."""
    io_queue = Queue()
    for req in requests:
        io_queue.enqueue(req)

    current_time = 0
    print(f"Disk bandwidth: {bandwidth_kb_per_ms} KB/ms\n")
    print(f"{'Time':>6}  {'Process':<12} {'Op':<6} "
          f"{'File':<20} {'Size':>6} {'Duration':>9}")
    print("-" * 67)

    while not io_queue.is_empty():
        req = io_queue.dequeue()
        duration = req.size_kb // bandwidth_kb_per_ms
        if duration == 0:
            duration = 1   # minimum 1ms

        print(f"{current_time:>5}ms  {req.process:<12} "
              f"{req.operation:<6} {req.filename:<20} "
              f"{req.size_kb:>5}KB  {duration:>7}ms")
        current_time += duration

    print(f"\nTotal I/O time: {current_time}ms")


# Simulate
io_requests = [
    IORequest("Chrome",   "read",  "cache/page.html",   50),
    IORequest("VS Code",  "write", "project/main.py",   12),
    IORequest("Spotify",  "read",  "music/song.mp3",   4000),
    IORequest("Terminal", "read",  "logs/system.log",    200),
    IORequest("Slack",    "write", "data/messages.db",   80),
]

print("=== Disk I/O Queue Simulation ===\n")
simulate_io_queue(io_requests)

# Expected output:
# === Disk I/O Queue Simulation ===
#
# Disk bandwidth: 10 KB/ms
#
#   Time  Process      Op     File                  Size  Duration
# -------------------------------------------------------------------
#    0ms  Chrome       read   cache/page.html        50KB       5ms
#    5ms  VS Code      write  project/main.py        12KB       1ms
#    6ms  Spotify      read   music/song.mp3       4000KB     400ms
#  406ms  Terminal     read   logs/system.log       200KB      20ms
#  426ms  Slack        write  data/messages.db       80KB       8ms
#
# Total I/O time: 434ms

Notice the convoy effect again: Spotify's large music file blocks Terminal and Slack, even though their requests are small. Real operating systems use more sophisticated algorithms (like I/O scheduling with priority levels) to mitigate this.

Multiple Queues: Priority Levels

Modern operating systems don't use a single queue. They use multiple priority queues. System-critical processes (the kernel, device drivers) get higher priority than user applications. Within each priority level, Round Robin ensures fairness.

class MultiLevelScheduler:
    """Simplified multi-level priority scheduling."""

    def __init__(self, quantum: int = 3):
        self.high_priority = Queue()     # system processes
        self.medium_priority = Queue()   # interactive apps
        self.low_priority = Queue()      # background tasks
        self.quantum = quantum

    def add_process(self, name: str, burst: int,
                    priority: str) -> None:
        process = {"name": name, "burst": burst,
                   "remaining": burst, "priority": priority}
        if priority == "high":
            self.high_priority.enqueue(process)
        elif priority == "medium":
            self.medium_priority.enqueue(process)
        else:
            self.low_priority.enqueue(process)
        print(f"  Added '{name}' ({burst}ms, {priority} priority)")

    def _get_next_queue(self) -> Queue | None:
        """Return the highest-priority non-empty queue."""
        if not self.high_priority.is_empty():
            return self.high_priority
        if not self.medium_priority.is_empty():
            return self.medium_priority
        if not self.low_priority.is_empty():
            return self.low_priority
        return None

    def run(self) -> None:
        """Execute all processes by priority."""
        current_time = 0
        print(f"\nExecution (quantum={self.quantum}ms):")

        while True:
            queue = self._get_next_queue()
            if queue is None:
                break

            process = queue.dequeue()
            run_time = min(self.quantum, process["remaining"])
            print(f"  [{current_time:>3}-{current_time + run_time:>3}] "
                  f"{process['name']:<15} "
                  f"({process['priority']})")
            current_time += run_time
            process["remaining"] -= run_time

            if process["remaining"] > 0:
                # Put it back in its priority queue
                queue.enqueue(process)

        print(f"\nAll processes complete at {current_time}ms")


# Demonstrate
print("=== Multi-Level Priority Scheduling ===\n")
scheduler = MultiLevelScheduler(quantum=2)
scheduler.add_process("Kernel Timer", 3, "high")
scheduler.add_process("USB Driver", 2, "high")
scheduler.add_process("Chrome", 6, "medium")
scheduler.add_process("VS Code", 4, "medium")
scheduler.add_process("Backup", 8, "low")
scheduler.add_process("Indexer", 5, "low")
scheduler.run()

# Expected output:
# === Multi-Level Priority Scheduling ===
#
#   Added 'Kernel Timer' (3ms, high priority)
#   Added 'USB Driver' (2ms, high priority)
#   Added 'Chrome' (6ms, medium priority)
#   Added 'VS Code' (4ms, medium priority)
#   Added 'Backup' (8ms, low priority)
#   Added 'Indexer' (5ms, low priority)
#
# Execution (quantum=2ms):
#   [  0-  2] Kernel Timer    (high)
#   [  2-  4] USB Driver      (high)
#   [  4-  5] Kernel Timer    (high)
#   [  5-  7] Chrome          (medium)
#   [  7-  9] VS Code         (medium)
#   [  9- 11] Chrome          (medium)
#   [ 11- 13] VS Code         (medium)
#   [ 13- 15] Chrome          (medium)
#   [ 15- 17] Backup          (low)
#   [ 17- 19] Indexer         (low)
#   [ 19- 21] Backup          (low)
#   [ 21- 23] Indexer         (low)
#   [ 23- 25] Backup          (low)
#   [ 25- 26] Indexer         (low)
#   [ 26- 28] Backup          (low)
#
# All processes complete at 28ms

Notice the pattern: all high-priority processes finish before any medium-priority process runs, and all medium-priority processes finish before any low-priority process runs. This is why system-critical operations (like responding to a keystroke or processing a network packet) feel instant even when your computer is heavily loaded with background tasks.

What We Learned

Queues are fundamental to operating systems. Process scheduling, I/O management, and network buffering all rely on FIFO queues.
FCFS is simple but unfair. Long processes block short ones (the convoy effect). This is acceptable for batch processing but terrible for interactive systems.
Round Robin uses a queue to achieve fairness. By cycling through processes in queue order and giving each a fixed time slice, every process gets regular CPU time.
Multiple priority queues let the OS serve critical operations first while still being fair within each priority level.
The same data structure (queue) appears at multiple levels of the same system — CPU scheduling, disk I/O, network buffers, and print spooling all use queues, sometimes with different policies layered on top.

Connections to This Course

Chapter 5 (Loops): The scheduling loop (while not queue.is_empty()) is a while loop driven by a queue's state — a pattern you first encountered in Chapter 5.
Chapter 14 (OOP): The Process and MultiLevelScheduler classes encapsulate state and behavior, just as you learned in Chapter 14.
Chapter 17 (Algorithms): The choice between FCFS and Round Robin is an algorithm design decision with measurable performance trade-offs — the same kind of thinking you applied in Chapter 17.

Try It Yourself

Modify the Round Robin scheduler to support processes arriving at different times (not all at time 0). You'll need to check arrival times before adding processes to the ready queue.
Implement Shortest Job First (SJF) scheduling: always process the job with the smallest burst time next. This minimizes average wait time but requires knowing burst times in advance. (Hint: you'll need a priority queue — sort by burst time.)
Research multilevel feedback queues — the algorithm actually used by most modern operating systems. A process that uses its entire quantum gets moved to a lower-priority queue, while a process that finishes early stays at a higher priority. This automatically rewards interactive processes.
Add "starvation detection" to the multi-level scheduler: if a low-priority process has been waiting for more than a threshold time, temporarily boost its priority.

Case Study 2: How Operating Systems Use Queues

Process Scheduling and I/O Queues

The Problem: One CPU, Many Processes

Simulating FCFS Scheduling

The Problem with FCFS

Round Robin: Fair Time Sharing

Comparing the Two Approaches

I/O Queues: The Other Kind of Waiting

Multiple Queues: Priority Levels

What We Learned

Connections to This Course

Try It Yourself