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.
Round Robin: Fair Time Sharing
The classic fix is Round Robin (RR) scheduling, and the schedulers in interactive operating systems are built on its core idea: take turns. Each process gets a fixed slice of CPU time (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")
# Fresh processes, all arriving at time 0
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- 21] Chrome ###
# [ 21- 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
Careful: the FCFS run above used staggered arrival times (0, 1, 2, 3, 4), while the Round Robin run had everyone arrive at time 0. A fair comparison needs the same workload, so run fcfs_schedule on a fresh copy of the all-at-time-0 list. You get an average wait of 11.4ms and an average turnaround of 15.8ms.
Let's add one more metric, response time: how long a process waits before it gets the CPU for the first time (start_time - arrival_time). That's the delay you feel as a user, the gap between clicking and the app reacting.
| Metric (all 5 processes arrive at 0ms) | FCFS | Round Robin (q=3) |
|---|---|---|
| Avg wait time | 11.4ms | 10.2ms |
| Avg turnaround time | 15.8ms | 14.6ms |
| Avg response time | 11.4ms | 5.2ms |
| Fairness | Low — long jobs block short ones | High — everyone gets regular turns |
Round Robin wins every row here, but don't read too much into the first two. It looks good on averages partly because the longest job, Chrome, happened to be first in line. Put the shortest jobs first (Terminal, Spotify, VS Code, Slack, Chrome) and FCFS's average turnaround drops to 9.0ms, beating Round Robin's 10.8ms on that ordering. Round Robin's dependable win is response time: no process waits for everything ahead of it to finish, only for each of them to take one turn. In an interactive system (like your desktop), that 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 starts dropping packets. Overflowing queues like this are one of the telltale symptoms of 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':>7} {'Duration':>9}")
print("-" * 66)
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:>4}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 awhileloop driven by a queue's state — a pattern you first encountered in Chapter 5. - Chapter 14 (OOP): The
ProcessandMultiLevelSchedulerclasses 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 (MLFQ), which many real operating systems, including BSD Unix derivatives, Solaris, and Windows, have used in some form as their base scheduler. A process that keeps using up its time slices drifts down to lower-priority queues, while one that gives up the CPU early (say, to wait for a keystroke) stays near the top. This automatically rewards interactive processes. Chapter 8 of Operating Systems: Three Easy Pieces (see Further Reading) is a great place to start.
-
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.