Operating systems

1 · What an operating system actually does

Here is a moment you've almost certainly lived. You have a browser with forty tabs open, a music player, a video call, your editor, and a build running in the terminal — all at once, on a machine with maybe eight CPU cores. That's five, ten, fifty programs all convinced they own the computer, and somehow none of them notices the others. No tab can read your bank password out of another tab; a crashing build doesn't take down your call. Someone is refereeing all of that, invisibly, thousands of times a second. That someone is the operating system, and most engineers go years without ever looking at it directly — until the day a service falls over and the only useful question is "what is the OS actually doing under here?"

The reason this deserves a chapter at the top of a systems track is simple: every architecture you designed in SD5–SD7 is a fiction the OS maintains. "My service has its own memory," "my container is isolated," "requests are handled fairly" — none of those are true at the silicon level. There is one lump of RAM, a handful of cores, and one disk, all shared. The OS spends its entire life lying convincingly to every program so that each one can pretend it's alone. Understand the mechanism behind the lie and suddenly a whole class of production mysteries — why a box thrashes under load, why a "fast" service is slow, why adding threads didn't help — stops being magic.

A useful analogy: think of the OS as the manager of a shared workshop. Many workers (programs) want the same tools (CPU, memory, disk), and left alone they'd fight, grab each other's parts, and injure each other. The manager does three things — hands out time at the workbench in turns, gives each worker a locked cupboard nobody else can open, and stands between the workers and the dangerous machinery so no one loses a finger. That's scheduling, memory isolation, and mediated I/O. The common beginner mistake is to picture the OS as "the desktop" — the windows and icons you click. That's just one more program. The real OS is the referee you never see, and the part that matters for systems work is the tiny privileged core called the kernel.

An operating system is the program that sits between your code and the hardware. Three jobs matter most: it shares the CPU among many programs (scheduling), it gives each program its own private memory (isolation, covered in SD9), and it mediates access to devices — disk, network, screen — so one buggy program cannot corrupt another or crash the machine. The OS is a resource manager and a protection boundary at the same time.

2 · Processes vs threads

This is the distinction that sits behind more confused engineering conversations than almost any other. Someone says "just add more threads and it'll go faster," someone else says "no, use separate processes," and both are half-right and half-talking-past-each-other because they never pinned down what actually differs between the two. Get this clear once and a surprising amount downstream — the Python GIL, why a worker pool is shaped the way it is, why one crash kills everything and another doesn't — falls into place.

Try this picture. A process is a house: it has its own walls, its own address, and its own furniture, and the people inside cannot wander into the neighbour's house. A thread is a person living inside one house. You can have several people (threads) in the same house, and they share everything — the same fridge, the same rooms, the same mess. Two houses (processes) share nothing unless they deliberately mail things to each other. That single image predicts every row in the table below: housemates (threads) coordinate instantly because they share the fridge, but if one leaves the stove on the whole house burns (a bad thread corrupts the whole process). Separate houses (processes) are safe from each other but slow to build and awkward to pass things between.

Why the sharing is the entire story. Threads are attractive precisely because they share memory: two threads can hand data back and forth just by writing to the same variable — no copying, no serialization, near-instant. But that same shared memory is a loaded gun. If two threads touch the same variable at the same time, you get a race condition: a bug that depends on the exact microsecond timing of the scheduler, appears once in ten thousand runs, and is nearly impossible to reproduce. That's the demon you'll spend all of SD9 learning to cage. Processes dodge it entirely — separate memory means no shared state to corrupt — but you pay for that safety with heavier creation and the need for explicit inter-process communication (pipes, sockets, shared-memory segments).

The mistake to avoid: reaching for threads "for speed" without asking what your work is actually waiting on. If your program is stuck waiting on the network or disk (I/O-bound), threads help a lot — while one waits, another runs. If it's crunching numbers with no waiting (CPU-bound), threads in a language with a global lock like Python's GIL won't speed it up at all, and you want separate processes instead. Naming what your bottleneck is comes before choosing the tool. With that framing, here is the crisp definition and a side-by-side comparison.

A process is a running program with its own private address space — its own view of memory. A thread is a single flow of execution inside a process; a process can have many threads that share the same memory. That sharing is the whole trade-off: threads are cheap to create and communicate through shared memory, but that shared memory is exactly what causes the race conditions you will fight in SD9.

process.py# MODEL: a process is really just a bundle of state the OS tracks in a
# "process control block" (PCB). We model that bundle as a dataclass.
from dataclasses import dataclass, field

@dataclass
class Process:
    pid: int
    arrival: int          # tick it becomes ready
    burst: int            # CPU ticks it needs
    priority: int = 0     # lower = more important (convention here)
    remaining: int = field(init=False)
    def __post_init__(self):
        self.remaining = self.burst

jobs = [Process(1, 0, 5), Process(2, 1, 3), Process(3, 2, 8)]
for j in jobs:
    print(f"pid={j.pid} arrival={j.arrival} burst={j.burst} remaining={j.remaining}")

pid=1 arrival=0 burst=5 remaining=5
pid=2 arrival=1 burst=3 remaining=3
pid=3 arrival=2 burst=8 remaining=8

3 · Context switching — the illusion of many at once

Start with the fact that should bother you. Your laptop has, say, eight cores, yet you routinely run hundreds of processes — check your activity monitor and you'll see three hundred plus. Eight cores. Three hundred programs. All apparently running "at the same time." They are not. At any given instant a core is executing exactly one thread, and the sensation of everything running at once is a magic trick performed so fast your eyes can't catch it. The trick has a name and a price, and both matter enormously the day you're trying to figure out why a busy server is spending its CPU on nothing.

The trick is like a single teacher helping thirty students, one at a time, but rotating so fast that every student feels continuously attended to. To switch from student A to student B, the teacher has to do bookkeeping: note exactly where A had got to (which page, which line), then pick up B's notes and remember where B had left off. For a CPU, "where you left off" is the contents of its registers and its program counter — the tiny scratchpad of what-am-I-doing-right-now. A context switch is the OS saving all of that for the outgoing thread and restoring it for the incoming one. It happens millions of times an hour, and each one is a few microseconds of pure overhead — work that produces no actual progress on anyone's program.

Here's the part that surprises people and where the real cost hides. The visible save-and-restore of registers is cheap. The expensive, invisible cost is the cache. A running thread warms up the CPU's fast local caches with its data; when you switch to a different thread, those caches are now full of the wrong thread's data, and the new thread limps along on cache misses until it warms the cache back up. So the true cost of a switch is not just the hand-off — it's the cold-start penalty that lingers afterward. This is why "just switch more often to feel snappier" is a trap: past a point you spend more time switching and re-warming than doing work. In extreme cases a system does almost nothing but switch — a pathology called thrashing, where CPU sits near 100% while real throughput collapses.

The common mistake is to treat context switches as free and reason only about "work to be done." Real capacity planning counts the switches too. The lab below models exactly this — total time as useful work plus a fixed cost per switch — so you can feel why a scheduler that preempts too eagerly can lose to one that lets jobs run a little longer. Keep that overhead in mind: it's the hidden tax that the round-robin quantum in the next section is really tuning.

A single CPU core runs exactly one thread at a time. The OS creates the illusion of many programs running at once by switching between them extremely fast. A context switch is that hand-off: the kernel saves the current thread's registers and program counter, then loads another thread's saved state. It is not free — the switch itself burns CPU cycles and cold caches, so a scheduler that switches too often wastes real work.

switch_cost.py# MODEL: each context switch costs a fixed number of "overhead" ticks.
# Fewer switches -> less overhead, but (see round-robin) worse responsiveness.
def total_time(work_ticks, switches, switch_cost=1):
    return work_ticks + switches * switch_cost

print("2 switches:", total_time(100, 2))    # 102
print("50 switches:", total_time(100, 50))  # 150

2 switches: 102
50 switches: 150

4 · CPU scheduling — a runnable simulator

Think about the last time you were stuck in a supermarket queue behind someone with a full trolley while you held a single sandwich. The rage you felt — "why am I waiting ten minutes to buy one thing?" — is the exact problem a CPU scheduler exists to manage, and different checkout policies produce wildly different amounts of that rage. Express lanes, "next customer please" rotation, letting the pregnant woman go first: those are scheduling algorithms, and a supermarket that picks the wrong one has furious customers even though the total amount of scanning is identical. The CPU faces the same choice thousands of times a second, and which policy it picks decides whether your machine feels instant or sluggish under the same load.

The scheduler is where operating systems stop being descriptive and become genuinely interesting, because there is no single right answer — only trade-offs you choose deliberately. Serve strictly in arrival order and it's dead fair but one big job stalls everyone behind it (the supermarket's full-trolley problem, called the convoy effect). Always serve the shortest job and average waiting drops to its mathematical minimum — but a long job might never get served if short ones keep arriving (starvation). Rotate everyone through small time slices and it feels responsive — but you pay the context-switch tax from the last section on every rotation. Each policy optimizes a different thing and quietly sacrifices another; the engineer's job is to know which sacrifice their workload can afford.

What makes this section special is that you don't have to take any of that on faith. You will simulate all four policies in plain Python and read the numbers off yourself. The two numbers that matter are waiting time (how long a job sat ready but ignored — this is the customer's felt rage) and turnaround time (arrival to finish — the total trip). A batch system that runs overnight cares about turnaround; an interactive system where a human is drumming their fingers cares about waiting time and responsiveness. Same workload, different metric, different "best" policy — which is why the labs below make you measure rather than memorize.

The mistake to sidestep: believing there's a universally optimal scheduler you can just look up. There isn't, and interviewers love to catch people asserting one. SJF being "provably optimal for average wait" is true and also nearly useless in practice, because it assumes you know each job's length in advance — you almost never do. The real lesson isn't the four algorithms; it's the habit of naming what you're optimizing for, then choosing the policy that buys it at an acceptable cost. With that mindset, here are the four classics and the metrics we'll hold them to.

The scheduler decides which ready thread runs next. Four classic policies: FCFS (first-come-first-served — a plain queue), SJF (shortest-job-first — run the smallest burst next), round-robin (each job gets a fixed time slice, then goes to the back of the queue), and priority (run the most important first). We measure each with two numbers: waiting time (ticks spent ready but not running) and turnaround time (finish − arrival).

scheduler_nonpre.py# MODEL of two non-preemptive schedulers. Each returns per-job (wait, turnaround).
# Non-preemptive = once a job starts it runs to completion.
from dataclasses import dataclass

@dataclass
class Job:
    pid: int; arrival: int; burst: int

def run_nonpreemptive(jobs, pick_next):
    """pick_next(ready, now) -> the Job to run next."""
    jobs = sorted(jobs, key=lambda j: j.arrival)
    now, done, metrics = 0, [], {}
    pending = list(jobs)
    while pending:
        ready = [j for j in pending if j.arrival <= now]
        if not ready:                      # CPU idle until next arrival
            now = min(j.arrival for j in pending); continue
        j = pick_next(ready, now)
        start = now
        now += j.burst                     # runs to completion
        turnaround = now - j.arrival
        wait = start - j.arrival
        metrics[j.pid] = (wait, turnaround)
        pending.remove(j)
    return metrics

def report(name, m):
    avg_w = sum(w for w, _ in m.values()) / len(m)
    avg_t = sum(t for _, t in m.values()) / len(m)
    print(f"{name:5s} avg_wait={avg_w:.2f} avg_turnaround={avg_t:.2f}")

jobs = [Job(1, 0, 7), Job(2, 2, 4), Job(3, 4, 1), Job(4, 5, 4)]
fcfs = run_nonpreemptive(jobs, lambda ready, now: min(ready, key=lambda j: j.arrival))
sjf  = run_nonpreemptive(jobs, lambda ready, now: min(ready, key=lambda j: j.burst))
report("FCFS", fcfs)
report("SJF", sjf)

FCFS  avg_wait=4.75 avg_turnaround=8.75
SJF   avg_wait=4.00 avg_turnaround=8.00

round_robin.py# MODEL: round-robin gives each job a fixed time "quantum", then rotates.
# Preemptive = a running job can be interrupted before it finishes.
from collections import deque
from dataclasses import dataclass

@dataclass
class Job:
    pid: int; arrival: int; burst: int

def round_robin(jobs, quantum):
    jobs = sorted(jobs, key=lambda j: j.arrival)
    remaining = {j.pid: j.burst for j in jobs}
    finish = {}
    now, i, q = 0, 0, deque()
    def admit(t):                    # move arrivals up to time t into the queue
        nonlocal i
        while i < len(jobs) and jobs[i].arrival <= t:
            q.append(jobs[i].pid); i += 1
    admit(now)
    while q:
        pid = q.popleft()
        slice_ = min(quantum, remaining[pid])
        now += slice_
        remaining[pid] -= slice_
        admit(now)                   # new arrivals queue ahead of the re-added job
        if remaining[pid] > 0:
            q.append(pid)            # not done -> back of the line
        else:
            finish[pid] = now
        if not q:                    # CPU would idle: pull in a future arrival
            admit(now)
            if not q and i < len(jobs):
                now = jobs[i].arrival; admit(now)
    by_pid = {j.pid: j for j in jobs}
    metrics = {}
    for pid, f in finish.items():
        j = by_pid[pid]
        turnaround = f - j.arrival
        metrics[pid] = (turnaround - j.burst, turnaround)  # (wait, turnaround)
    return metrics

jobs = [Job(1, 0, 7), Job(2, 2, 4), Job(3, 4, 1), Job(4, 5, 4)]
for qn in (2, 4):
    m = round_robin(jobs, qn)
    avg_w = sum(w for w, _ in m.values()) / len(m)
    print(f"RR q={qn} avg_wait={avg_w:.2f}")

RR q=2 avg_wait=5.00
RR q=4 avg_wait=4.50

5 · System calls & the user/kernel boundary

Here's a question that stumps people who have written code for years: when your Python program runs open("data.txt"), what actually opens the file? Not your program. Your program is not allowed to touch the disk — it has no idea where the disk even is, and it would be a catastrophe if it did. Instead it politely asks the kernel to do it. That asking has a mechanism, a cost, and a hardware-enforced wall behind it, and the day you profile a slow service and discover it's spending 80% of its time crossing that wall, you'll be glad you know it's there.

The analogy that makes it click: think of the kernel as a bank teller behind bulletproof glass. You (user code) cannot walk into the vault and grab cash — obviously. You slide a request through a slot ("withdraw $50"), the teller checks you're allowed, does the privileged thing in the secure area, and slides the result back. A system call is that slot. Your program fills out a request, the CPU flips from user mode (restricted — can't touch hardware) into kernel mode (full privilege), the kernel validates and performs the operation, then flips you back to user mode with the answer. Every file read, every network packet, every new process you spawn goes through that slot. There is no other way in.

Why build a wall at all, instead of just letting programs do what they want? Because "trust every program with the hardware" is how you get a single buggy app that overwrites another app's memory, corrupts the disk, or wedges the whole machine. The user/kernel boundary is the hardware saying "prove you're allowed before I let you near the dangerous parts." It's the same isolation instinct as the process boundaries from section 2, but enforced one level deeper — in the CPU itself, which literally refuses to execute privileged instructions while in user mode. That refusal is what keeps one crashing tab from taking down your entire laptop.

Now the practical payoff, because this is where the boundary bites in real systems. Crossing it is not free — every system call pays for the mode switch and the associated overhead, on the order of a microsecond or more. That sounds tiny until you do it a million times. The classic beginner mistake is writing a loop that does one tiny write per record: a hundred thousand records become a hundred thousand boundary crossings, and the crossings, not the actual writing, dominate your runtime. The fix — batching, one big write instead of many small ones — is why buffered writers, bulk database inserts, and vectorized APIs exist everywhere in production code. The model below makes this concrete, and it's the intuition behind Exercise 6. Here is the precise definition and the trap that trips into the kernel.

Your program cannot touch the disk or network directly — it would be a security and stability disaster. Instead it makes a system call: a controlled request that traps into the kernel, switches the CPU from user mode (restricted) to kernel mode (full privilege), runs the privileged operation, and returns. open, read, write, fork and socket are all system calls. The mode switch is the hardware-enforced line between "your code" and "trusted code".

syscall_gate.py# MODEL: a syscall is a guarded entry point. In user mode you may NOT run a
# privileged op directly; you must request it and let the "kernel" validate + run it.
class Kernel:
    def __init__(self):
        self.mode = "user"
        self._files = {}
    def syscall(self, name, *args):
        self.mode = "kernel"            # trap: switch to kernel mode
        try:
            handler = getattr(self, f"_sys_{name}", None)
            if handler is None:
                return (-1, "ENOSYS")   # no such system call
            return handler(*args)
        finally:
            self.mode = "user"          # return: back to user mode
    def _sys_write(self, path, data):
        self._files.setdefault(path, "")
        self._files[path] += data
        return (0, len(data))
    def _sys_read(self, path):
        return (0, self._files.get(path, ""))

k = Kernel()
print(k.syscall("write", "/tmp/log", "hello"))   # (0, 5)
print(k.syscall("read", "/tmp/log"))             # (0, "hello")
print(k.syscall("launch_missiles"))              # (-1, "ENOSYS")
print("mode after return:", k.mode)              # back in user mode

(0, 5)
(0, 'hello')
(-1, 'ENOSYS')
mode after return: user

Knowledge check

def fcfs(jobs):  # jobs: list of (pid, arrival, burst)
    jobs = sorted(jobs, key=lambda j: j[1])
    now, metrics = 0, {}
    for pid, arrival, burst in jobs:
        start = max(now, arrival)      # idle-jump if CPU is waiting
        completion = start + burst
        turnaround = completion - arrival
        wait = turnaround - burst
        metrics[pid] = (wait, turnaround)
        now = completion
    return metrics

m = fcfs([(1, 0, 7), (2, 2, 4), (3, 4, 1), (4, 5, 4)])
for pid, (w, t) in m.items():
    print(f"pid={pid} wait={w} turnaround={t}")
print("avg wait:", sum(w for w, _ in m.values()) / len(m))

def run(jobs, pick_next):
    pending = sorted(jobs, key=lambda j: j[1])  # (pid, arrival, burst)
    now, metrics = 0, {}
    pending = list(pending)
    while pending:
        ready = [j for j in pending if j[1] <= now]
        if not ready:
            now = min(j[1] for j in pending); continue
        pid, arrival, burst = pick_next(ready, now)
        wait = now - arrival
        now += burst
        metrics[pid] = (wait, now - arrival)
        pending.remove((pid, arrival, burst))
    return metrics

def avg_wait(m): return sum(w for w, _ in m.values()) / len(m)

jobs = [(1, 0, 7), (2, 2, 4), (3, 4, 1), (4, 5, 4)]
fcfs = run(jobs, lambda r, now: min(r, key=lambda j: j[1]))
sjf  = run(jobs, lambda r, now: min(r, key=lambda j: j[2]))
print(f"FCFS avg wait {avg_wait(fcfs):.2f}")
print(f"SJF  avg wait {avg_wait(sjf):.2f}")

from collections import deque

def round_robin(jobs, quantum):        # (pid, arrival, burst)
    jobs = sorted(jobs, key=lambda j: j[1])
    remaining = {p: b for p, a, b in jobs}
    arrival = {p: a for p, a, b in jobs}
    burst = {p: b for p, a, b in jobs}
    now, i, q, finish = 0, 0, deque(), {}
    def admit(t):
        nonlocal i
        while i < len(jobs) and jobs[i][1] <= t:
            q.append(jobs[i][0]); i += 1
    admit(now)
    while q:
        pid = q.popleft()
        s = min(quantum, remaining[pid]); now += s; remaining[pid] -= s
        admit(now)
        if remaining[pid] > 0: q.append(pid)
        else: finish[pid] = now
        if not q and i < len(jobs):
            now = jobs[i][1]; admit(now)
    return {p: ((finish[p] - arrival[p]) - burst[p], finish[p] - arrival[p]) for p in finish}

jobs = [(1, 0, 7), (2, 2, 4), (3, 4, 1), (4, 5, 4)]
for q in (1, 2, 4, 8):
    m = round_robin(jobs, q)
    print(f"q={q}: avg wait {sum(w for w,_ in m.values())/len(m):.2f}")

def priority_sched(jobs, k=None):      # (pid, arrival, burst, base_priority)
    pending = sorted(jobs, key=lambda j: j[1])
    pending = list(pending)
    now, metrics, entered = 0, {}, {}
    while pending:
        ready = [j for j in pending if j[1] <= now]
        if not ready:
            now = min(j[1] for j in pending); continue
        for j in ready: entered.setdefault(j[0], j[1])
        def eff(j):
            base = j[3]
            if k:                       # aging: waiting lowers the number
                base -= (now - entered[j[0]]) // k
            return base
        j = min(ready, key=eff)         # lowest effective priority number wins
        pid, arrival, burst, _ = j
        metrics[pid] = (now - arrival, now - arrival + burst)
        now += burst
        pending.remove(j)
    return metrics

# job 1 is low priority (base 4); a steady stream of priority-1 jobs keeps arriving,
# so without aging job 1 is bumped again and again.
jobs = [(1, 0, 2, 4), (2, 0, 2, 1), (3, 2, 2, 1),
        (4, 4, 2, 1), (5, 6, 2, 1), (6, 8, 2, 1)]
print("no aging, job 1:", priority_sched(jobs)[1])       # (wait, turnaround)
print("aging k=1, job 1:", priority_sched(jobs, k=1)[1])

import random
from collections import deque

def gen(n, seed=7):
    r = random.Random(seed)
    return [(i + 1, r.randint(0, 10), r.randint(1, 9)) for i in range(n)]

def run_np(jobs, pick):
    pend, now, m = list(sorted(jobs, key=lambda j: j[1])), 0, {}
    while pend:
        ready = [j for j in pend if j[1] <= now]
        if not ready: now = min(j[1] for j in pend); continue
        pid, a, b = pick(ready); m[pid] = (now - a, now - a + b); now += b; pend.remove((pid, a, b))
    return m

def run_rr(jobs, q):
    jobs = sorted(jobs, key=lambda j: j[1]); rem = {p: b for p, a, b in jobs}
    arr = {p: a for p, a, b in jobs}; bur = {p: b for p, a, b in jobs}
    now, i, dq, fin, sw = 0, 0, deque(), {}, 0
    def admit(t):
        nonlocal i
        while i < len(jobs) and jobs[i][1] <= t: dq.append(jobs[i][0]); i += 1
    admit(0)
    while dq:
        pid = dq.popleft(); sw += 1
        s = min(q, rem[pid]); now += s; rem[pid] -= s; admit(now)
        if rem[pid] > 0: dq.append(pid)
        else: fin[pid] = now
        if not dq and i < len(jobs): now = jobs[i][1]; admit(now)
    m = {p: ((fin[p] - arr[p]) - bur[p], fin[p] - arr[p]) for p in fin}
    return m, sw

def avg(m, idx): return sum(v[idx] for v in m.values()) / len(m)

W = gen(8)
fcfs = run_np(W, lambda r: min(r, key=lambda j: j[1]))
sjf  = run_np(W, lambda r: min(r, key=lambda j: j[2]))
rr, sw = run_rr(W, 3)
print(f"{'policy':6s}{'avg_wait':>10s}{'avg_turn':>10s}{'switches':>10s}")
print(f"{'FCFS':6s}{avg(fcfs,0):10.2f}{avg(fcfs,1):10.2f}{'-':>10s}")
print(f"{'SJF':6s}{avg(sjf,0):10.2f}{avg(sjf,1):10.2f}{'-':>10s}")
print(f"{'RR(3)':6s}{avg(rr,0):10.2f}{avg(rr,1):10.2f}{sw:10d}")

def model_time(n_records, batch, bytes_per_record=200,
               switch_cost_ns=1500, byte_cost_ns=2):
    """MODEL: total nanoseconds to write n_records, batch records per syscall."""
    import math
    syscalls = math.ceil(n_records / batch)
    total_bytes = n_records * bytes_per_record
    return syscalls * switch_cost_ns + total_bytes * byte_cost_ns

N = 100_000
for m in (1, 10, 100, 1000, 10_000):
    t = model_time(N, m)
    print(f"batch={m:>6}: modelled {t/1e6:.2f} ms")