P12 hands-on — Operating system kernel, block by block

Frames, page tables, Bélády's anomaly, scheduling, and a race you can watch.

Source: handson/h12_kernel.py --- run it with python3 handson/h12_kernel.py
Full project spec: P12 — Operating-System Kernel

You cannot boot a kernel inside a Python process, but every mechanism a kernel depends on can be built and measured in one --- and the mechanisms are the part that transfers. This file builds eight of them and ends with the observation that a process control block is simply one field per mechanism.

Two results are worth arriving for. Bélády's anomaly is demonstrated rather than described: FIFO with four frames faults more often than with three, on the classic 1969 reference string, which is why "add more cache" is a hypothesis rather than a fix. And the assembly's page-fault sweep contradicts its own prediction --- there is no working-set cliff, because a mixture of reference distributions does not have one, and that turns out to be the more useful lesson.

Contents

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Physical frame allocator

Teaches: the first allocation problem, with no allocator to help

The problem. The first allocation problem, solved before any allocator exists. Everything the kernel does early — page tables, process structures, the heap itself — needs physical frames, and there is nothing to allocate from.

@block(1, "Physical frame allocator", "the first allocation problem, with no allocator to help")
def b1(s, show):
    class Frames:
        def __init__(self, n): self.bm = bytearray(n); self.n = n; self.hint = 0
        def alloc(self):
            for k in range(self.n):
                i = (self.hint + k) % self.n
                if not self.bm[i]:
                    self.bm[i] = 1; self.hint = i + 1; return i
            raise MemoryError("out of physical memory")
        def free(self, i):
            if not self.bm[i]: raise ValueError(f"double free of frame {i}")
            self.bm[i] = 0
        def used(self): return sum(self.bm)
    if show:
        f = Frames(1024)
        got = [f.alloc() for _ in range(600)]
        for i in got[::3]: f.free(i)
        print(f"  1024 frames; allocated 600, freed 200 -> {f.used()} in use")
        print(f"  next allocation reuses a hole: frame {f.alloc()}")
        try:
            f.free(got[1]); f.free(got[1])
        except ValueError as e:
            print(f"  double free is caught: {e}")
        print("  A bitmap costs 1 bit per 4 KiB page: 32 KiB of metadata per GiB, or")
        print("  0.003%. The rotating hint turns the scan from O(n) per alloc into")
        print("  O(1) amortised. This runs BEFORE any heap exists, so it cannot")
        print("  allocate -- every structure the kernel needs early is a fixed array.")
    return {"Frames": Frames}

Reading the implementation

A bitmap: one bit per 4 KiB frame. The metadata cost is 32 KiB per GiB, or 0.003% — which is why this is the standard bootstrap allocator despite the scan.

The rotating hint turns an \(O(n)\) linear scan into \(O(1)\) amortised for the common case of sequential allocation, at the cost of worse locality when the bitmap is fragmented. That is the same next-fit-versus-first-fit trade every allocator makes.

Double-free detection is one line (if not self.bm[i]: raise), and it is worth having because a double free in a physical allocator hands the same frame to two owners — the resulting corruption appears arbitrarily far from its cause, in another process's memory.

The structural constraint worth naming: this code runs before a heap exists, so it cannot allocate. Every early kernel structure is a fixed-size static array for that reason, and it is why kernels have compile-time limits (NPROC, NOFILE) that look archaic and are not.

What the numbers say

Output:

  1024 frames; allocated 600, freed 200 -> 400 in use
  next allocation reuses a hole: frame 600
  double free is caught: double free of frame 1
  A bitmap costs 1 bit per 4 KiB page: 32 KiB of metadata per GiB, or
  0.003%. The rotating hint turns the scan from O(n) per alloc into
  O(1) amortised. This runs BEFORE any heap exists, so it cannot
  allocate -- every structure the kernel needs early is a fixed array.

Beyond the toy

  • The buddy allocator (Linux's page allocator) maintains free lists for power-of-two block sizes, so allocating \(2^k\) contiguous pages is \(O(\log n)\) and coalescing on free is a bit-flip on the buddy address. Contiguity matters because DMA and huge pages need it.
  • Slab/SLUB sits above the page allocator for small kernel objects. It caches constructed objects of one type per cache, which gives near-zero allocation cost, no internal fragmentation, and — importantly — cache-line colouring so objects of the same type do not all map to the same cache set.
  • Per-CPU caches avoid the lock entirely on the fast path, which at 100+ cores is the difference between a scalable allocator and a bottleneck. The general pattern — per-CPU free lists with periodic rebalancing — recurs in every scalable allocator, including userspace ones like tcmalloc and jemalloc.
  • Memory fragmentation is the failure mode: plenty of free frames, none contiguous, so a huge-page allocation fails. Linux's compaction daemon exists for this and it is the same problem as P04's compaction, one level down.

Block 2 — Virtual memory

Teaches: one indirection, and the process model falls out of it

The problem. One indirection, and the entire process model falls out of it. Two processes can use the same virtual address, and neither can touch the other's memory — not because anything checks, but because the mapping does not exist.

@block(2, "Virtual memory", "one indirection, and the process model falls out of it")
def b2(s, show):
    PAGE = 4096
    class MMU:
        def __init__(self, frames): self.f = frames; self.tables = {}
        def map(self, pid, vpn, writable=True):
            t = self.tables.setdefault(pid, {})
            if vpn in t: return t[vpn][0]
            fr = self.f.alloc(); t[vpn] = (fr, writable); return fr
        def translate(self, pid, va, write=False):
            vpn, off = va // PAGE, va % PAGE
            e = self.tables.get(pid, {}).get(vpn)
            if e is None: raise MemoryError(f"SEGFAULT pid={pid} va=0x{va:x}")
            fr, w = e
            if write and not w: raise PermissionError(f"write to RO page va=0x{va:x}")
            return fr * PAGE + off
    if show:
        f = s["Frames"](256); m = MMU(f)
        m.map(1, 0); m.map(1, 1); m.map(2, 0)
        pa1 = m.translate(1, 0x0100); pa2 = m.translate(2, 0x0100)
        print(f"  pid 1 va 0x0100 -> pa 0x{pa1:x}")
        print(f"  pid 2 va 0x0100 -> pa 0x{pa2:x}   (same VA, different frame)")
        print(f"  isolation is structural, not checked: {pa1 != pa2}")
        for lbl, fn in (("unmapped read", lambda: m.translate(1, 0x9000)),
                        ("write to RO", lambda: (m.map(1, 3, writable=False),
                                                 m.translate(1, 3*PAGE, write=True)))):
            try: fn()
            except Exception as e: print(f"  {lbl:<16}-> {type(e).__name__}: {e}")
        print("  Two processes at the same virtual address is the ENTIRE reason a")
        print("  bug in one cannot corrupt the other. Everything else -- COW, mmap,")
        print("  shared libraries, demand paging -- is a variation on who gets to")
        print("  point at which frame.")
    return {"MMU": MMU, "PAGE": PAGE}

Reading the implementation

translate(pid, va) splits the address into a page number and an offset, looks up the page number in that process's table, and returns frame * PAGE + offset. The offset passes through untouched, which is why page size must be a power of two — the split is a shift and a mask, not a division.

Isolation is structural, not checked. Process 2 cannot reach process 1's frame because there is no entry in its table that maps there. There is no comparison, no permission test, no bounds check on the fast path — the absence of a mapping is the protection. That is why virtual memory is cheap enough to be mandatory.

The permission bit gives the second half: a read-only mapping is what makes copy-on-write possible (map the parent's frames RO into the child, copy on first write), which is what makes fork() cheap, which is what makes the Unix process model viable.

What the numbers say

Output:

  pid 1 va 0x0100 -> pa 0x100
  pid 2 va 0x0100 -> pa 0x2100   (same VA, different frame)
  isolation is structural, not checked: True
  unmapped read   -> MemoryError: SEGFAULT pid=1 va=0x9000
  write to RO     -> PermissionError: write to RO page va=0x3000
  Two processes at the same virtual address is the ENTIRE reason a
  bug in one cannot corrupt the other. Everything else -- COW, mmap,
  shared libraries, demand paging -- is a variation on who gets to
  point at which frame.

Beyond the toy

  • Real page tables are radix trees, four levels on x86-64 (five with LA57). A miss costs a page walk — up to four dependent memory accesses, each potentially a cache miss, so 100+ ns. That is why the TLB exists and why its reach matters.
  • TLB reach is the number nobody checks: 1536 entries × 4 KiB = 6 MB. A process with a 10 GB working set misses on essentially every new page. Huge pages (2 MiB) extend reach 512× to ~3 GB, and are the single highest-leverage tuning knob for large-heap workloads — the same mechanism P02 needs for a 100 GB index.
  • ASIDs / PCIDs tag TLB entries with an address-space id so a context switch does not have to flush the whole TLB. Without them, every switch costs a full TLB refill — which is a large part of why the measured context-switch cost in block 4 understates the real one.
  • Everything else is a variation on who points at which frame: shared libraries (same frame, many tables), mmap (file pages mapped lazily), COW (shared until written), and paged attention in P01 (KV blocks mapped into a sequence's logical view).

Block 3 — Page replacement and Belady's anomaly

Teaches: more memory, more faults

The problem. When memory is full, something must be evicted. This block demonstrates the 1969 result that says buying more memory can make things worse — which is why "add cache" is a hypothesis rather than a fix.

@block(3, "Page replacement and Belady's anomaly", "more memory, more faults")
def b3(s, show):
    def fifo(refs, n):
        mem, q, faults = set(), deque(), 0
        for r in refs:
            if r in mem: continue
            faults += 1
            if len(mem) == n: mem.discard(q.popleft())
            mem.add(r); q.append(r)
        return faults
    def lru(refs, n):
        mem, faults = OrderedDict(), 0
        for r in refs:
            if r in mem: mem.move_to_end(r); continue
            faults += 1
            if len(mem) == n: mem.popitem(last=False)
            mem[r] = 1
        return faults
    def clock(refs, n):
        buf, ref, hand, faults = [], [], 0, 0
        for r in refs:
            if r in buf: ref[buf.index(r)] = 1; continue
            faults += 1
            if len(buf) < n: buf.append(r); ref.append(1); continue
            while ref[hand]: ref[hand] = 0; hand = (hand + 1) % n
            buf[hand] = r; ref[hand] = 1; hand = (hand + 1) % n
        return faults
    def opt(refs, n):
        mem, faults = [], 0
        for i, r in enumerate(refs):
            if r in mem: continue
            faults += 1
            if len(mem) == n:
                fut = [(refs[i+1:].index(x) if x in refs[i+1:] else 1 << 30) for x in mem]
                mem.pop(fut.index(max(fut)))
            mem.append(r)
        return faults
    BEL = [1,2,3,4,1,2,5,1,2,3,4,5]
    if show:
        print(f"  reference string {BEL}")
        print(f"  {'frames':>8}{'FIFO':>7}{'LRU':>6}{'CLOCK':>7}{'OPT':>6}")
        for n in (3, 4):
            print(f"  {n:>8}{fifo(BEL,n):>7}{lru(BEL,n):>6}{clock(BEL,n):>7}{opt(BEL,n):>6}")
        print(f"  FIFO with 4 frames faults MORE than with 3 "
              f"({fifo(BEL,4)} vs {fifo(BEL,3)}) -- Belady's anomaly, 1969.")
        print("  LRU cannot do this: it is a stack algorithm, so the pages resident")
        print("  with n frames are always a subset of those with n+1. FIFO has no")
        print("  such property, so buying RAM can lose performance. This is not a")
        print("  curiosity -- it is why 'add cache' is a hypothesis, not a fix.\\n")
        rng = random.Random(4)
        refs = [rng.choice(range(20)) if rng.random() < .3 else rng.choice(range(4))
                for _ in range(4000)]
        print(f"  4000 refs, 80/20 locality: {'frames':>8}{'FIFO':>7}{'LRU':>6}"
              f"{'CLOCK':>7}{'OPT':>6}")
        for n in (4, 8, 16):
            print(f"  {'':<26}{n:>8}{fifo(refs,n):>7}{lru(refs,n):>6}"
                  f"{clock(refs,n):>7}{opt(refs,n):>6}")
        print("  CLOCK tracks LRU within a few percent at a fraction of the cost --")
        print("  one reference bit per page instead of a timestamp and a list splice")
        print("  on every hit. Every real kernel ships an approximation, not LRU.")
    return {"fifo": fifo, "lru": lru, "clock": clock, "opt": opt}

Reading the implementation

Four policies on the classic reference string:

  • FIFO — evict the oldest. Simple, and exhibits the anomaly.
  • LRU — evict least recently used. Cannot exhibit the anomaly.
  • CLOCK — a circular scan with one reference bit per page. Approximates LRU at a fraction of the cost.
  • OPT — evict whatever is used furthest in the future. Unimplementable; the upper bound against which everything else is measured.

Bélády's anomaly: FIFO with 4 frames faults more often than with 3. LRU cannot do this because it is a stack algorithm — the set of pages resident with \(n\) frames is always a subset of the set resident with \(n+1\). FIFO has no such property, so adding memory can change the eviction order in a way that loses.

CLOCK deserves its ubiquity. LRU requires updating a timestamp or splicing a list node on every hit, which on a hot page is a write to shared state — a scalability disaster at many cores. CLOCK sets one bit on a hit and does its work only on eviction. Every real kernel and database ships an approximation for this reason, not for accuracy.

What the numbers say

Output:

  reference string [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
    frames   FIFO   LRU  CLOCK   OPT
         3      9    10      9     7
         4     10     8     10     6
  FIFO with 4 frames faults MORE than with 3 (10 vs 9) -- Belady's anomaly, 1969.
  LRU cannot do this: it is a stack algorithm, so the pages resident
  with n frames are always a subset of those with n+1. FIFO has no
  such property, so buying RAM can lose performance. This is not a
  curiosity -- it is why 'add cache' is a hypothesis, not a fix.\n
  4000 refs, 80/20 locality:   frames   FIFO   LRU  CLOCK   OPT
                                   4   2063  1875   2011  1153
                                   8   1159   821    953   496
                                  16    350   258    272   106
  CLOCK tracks LRU within a few percent at a fraction of the cost --
  one reference bit per page instead of a timestamp and a list splice
  on every hit. Every real kernel ships an approximation, not LRU.

Beyond the toy

  • Scan resistance is the property CLOCK and LRU both lack: one sequential scan of a large file evicts the entire working set. ARC, 2Q and LIRS all address this by tracking recency and frequency separately, and PostgreSQL's clock-sweep and Linux's active/inactive lists are practical approximations.
  • The miss curve is the real artefact. Mattson's stack algorithm gives all cache sizes' hit rates in one pass, and modern approximations (SHARDS, counter stacks) make it cheap enough to run continuously. That curve is what tells you whether more RAM will help before you buy it.
  • OPT is not useless. It bounds how much a better heuristic could possibly buy, and in the assembly it beats LRU by 1.92× — which says almost all the remaining win is in knowing the future, i.e. prefetching and hinting (madvise, fadvise), not in a smarter eviction rule.

Block 4 — Context switch

Teaches: saving state is easy; the cache is what costs

The problem. Context switching is what makes a single CPU look like many. This block prices the direct cost — and then explains why that price is the smaller half.

@block(4, "Context switch", "saving state is easy; the cache is what costs")
def b4(s, show):
    class Task:
        def __init__(self, tid, work): self.tid, self.work = tid, work; self.done = 0
        def step(self, q):
            n = min(q, self.work - self.done); self.done += n; return n
        def finished(self): return self.done >= self.work
    def run(tasks, quantum, switch_cost=0.0):
        t, log, sw = 0.0, [], 0
        q = deque(tasks)
        while q:
            task = q.popleft()
            did = task.step(quantum)
            t += did
            if task.finished(): log.append((task.tid, t))
            else:
                t += switch_cost; sw += 1; q.append(task)
        return t, log, sw
    if show:
        mk = lambda: [Task(i, w) for i, w in enumerate([50, 10, 80, 5, 30])]
        print(f"  five tasks, work = [50, 10, 80, 5, 30] microseconds")
        print(f"  {'quantum':>9}{'switches':>10}{'makespan':>11}{'mean turnaround':>18}"
              f"{'overhead':>10}")
        for q in (200, 50, 10, 2):
            tot, log, sw = run(mk(), q, 1.7)
            mt = sum(x for _, x in log) / len(log)
            print(f"  {q:>9}{sw:>10}{tot:>10.1f}us{mt:>17.1f}us"
                  f"{(sw*1.7)/tot:>9.1%}")
        print("  The 1.7 us switch cost is not invented -- it is this machine's")
        print("  measured context-switch time from numbers.md, which came out in the")
        print("  1,383-1,706 ns range. At a 2 us quantum the kernel spends 45% of the")
        print("  CPU switching between tasks. Responsiveness and throughput are the")
        print("  same dial, and the dial has a floor set by hardware.")
        print("  What this model does NOT capture: the cold cache after a switch. The")
        print("  register save is ~50 instructions; the L1 and TLB refill afterwards")
        print("  can be thousands of cycles, and it does not show up in any counter")
        print("  named 'context switch'.")
    return {"run_rr": run, "Task": Task}

Reading the implementation

Round-robin with a quantum, charging a fixed switch cost per preemption. The 1.7 µs figure is not invented: it is this machine's measured context-switch time from numbers.md, which came out in the 1,383--1,706 ns range.

The table shows the trade directly: at a 2 µs quantum the kernel spends ~45% of the CPU switching. Responsiveness and throughput are the same dial, and the dial has a floor set by hardware.

What this model does not capture is the larger cost. The register save is ~50 instructions. The cache and TLB refill afterwards can be thousands of cycles, and it appears in no counter named "context switch". A process resumed after another has evicted its working set restarts cold, and the cost scales with working-set size — which is why measuring switch cost with an empty working set (the standard microbenchmark) gives a number that is real and misleading.

What the numbers say

Output:

  five tasks, work = [50, 10, 80, 5, 30] microseconds
    quantum  switches   makespan   mean turnaround  overhead
        200         0     175.0us            114.0us     0.0%
         50         1     176.7us            110.0us     1.0%
         10        13     197.1us            105.6us    11.2%
          2        83     316.1us            177.4us    44.6%
  The 1.7 us switch cost is not invented -- it is this machine's
  measured context-switch time from numbers.md, which came out in the
  1,383-1,706 ns range. At a 2 us quantum the kernel spends 45% of the
  CPU switching between tasks. Responsiveness and throughput are the
  same dial, and the dial has a floor set by hardware.
  What this model does NOT capture: the cold cache after a switch. The
  register save is ~50 instructions; the L1 and TLB refill afterwards
  can be thousands of cycles, and it does not show up in any counter
  named 'context switch'.

Beyond the toy

  • Direct costs: register save/restore, page-table base switch (CR3), and — since Meltdown — KPTI's separate kernel page tables, which added a TLB flush to every syscall and cost 5--30% on syscall-heavy workloads.
  • Indirect costs: L1/L2 pollution, TLB refill, branch-predictor state loss. Measurable by varying the working set and watching the switch cost climb, which is E6 on the project page.
  • Which is why user-level threading exists. Goroutines, async/await, and fibers switch in tens of nanoseconds because they never enter the kernel and never change address space. The trade is that a blocking syscall blocks the whole carrier thread, which is why every such runtime needs non-blocking I/O underneath — and why io_uring matters so much to them.

Block 5 — Scheduling policy

Teaches: the same work, five orders, five different fairness stories

The problem. The same work, five orders, five different fairness stories. There is no scheduler that wins every column, and this block measures precisely what each one gives up.

@block(5, "Scheduling policy", "the same work, five orders, five different fairness stories")
def b5(s, show):
    JOBS = [("A", 0, 50), ("B", 0, 10), ("C", 5, 80), ("D", 10, 5), ("E", 20, 30)]
    def simulate(policy, quantum=10, switch=1.7):
        rem = {n: w for n, a, w in JOBS}; arr = {n: a for n, a, w in JOBS}
        t, done, ready, pending = 0.0, {}, [], sorted(JOBS, key=lambda j: j[1])
        first = {}
        while pending or ready:
            while pending and pending[0][1] <= t: ready.append(pending.pop(0)[0])
            if not ready:
                t = pending[0][1]; continue
            if policy == "fcfs": n = ready[0]; q = 1e9
            elif policy == "sjf": n = min(ready, key=lambda x: rem[x]); q = 1e9
            elif policy == "srtf": n = min(ready, key=lambda x: rem[x]); q = quantum
            else: n = ready[0]; q = quantum
            first.setdefault(n, t - arr[n])
            run = min(q, rem[n]); rem[n] -= run; t += run
            if rem[n] <= 0:
                done[n] = t - arr[n]; ready.remove(n)
            else:
                ready.remove(n); ready.append(n); t += switch
        return done, first
    if show:
        print("  jobs (name, arrival, work): " + ", ".join(f"{n}@{a}:{w}" for n,a,w in JOBS))
        print(f"  {'policy':<22}{'mean turnaround':>17}{'mean response':>15}"
              f"{'max turnaround':>16}")
        for pol, lbl in (("fcfs", "FCFS"), ("sjf", "SJF (non-preempt)"),
                         ("srtf", "SRTF (preemptive)"), ("rr", "round robin q=10")):
            d, f = simulate(pol)
            print(f"  {lbl:<22}{sum(d.values())/len(d):>16.1f}{sum(f.values())/len(f):>15.1f}"
                  f"{max(d.values()):>16.1f}")
        print("  SJF minimises mean turnaround -- provably, and it is the only")
        print("  policy here that can starve a long job forever. Round robin has the")
        print("  best response time and the worst turnaround. There is no scheduler")
        print("  that wins every column; there is only a choice of which column the")
        print("  workload cares about, which is why Linux ships several.")
    return {}

Reading the implementation

Four policies over the same job set. The three metrics are deliberately different questions:

  • Turnaround = completion − arrival. What a batch job cares about.
  • Response = first-run − arrival. What an interactive user feels.
  • Max turnaround = the starvation check.

SJF provably minimises mean turnaround — an exchange argument: swapping any adjacent out-of-order pair reduces the total. It is also the only policy here that can starve a long job forever, and it requires knowing job length in advance, which no real system does.

Round robin has the best response and the worst turnaround, because every job is slowed by every other. The quantum is the knob: smaller means better response and more switch overhead (block 4).

What the numbers say

Output:

  jobs (name, arrival, work): A@0:50, B@0:10, C@5:80, D@10:5, E@20:30
  policy                  mean turnaround  mean response  max turnaround
  FCFS                             107.0           72.0           155.0
  SJF (non-preempt)                 65.0           30.0           170.0
  SRTF (preemptive)                 70.5           24.4           192.1
  round robin q=10                 100.9           21.1           192.1
  SJF minimises mean turnaround -- provably, and it is the only
  policy here that can starve a long job forever. Round robin has the
  best response time and the worst turnaround. There is no scheduler
  that wins every column; there is only a choice of which column the
  workload cares about, which is why Linux ships several.

Beyond the toy

  • MLFQ infers job type from behaviour rather than requiring it up front: a job that yields before its quantum expires is interactive and stays high priority; a job that burns its quantum drops a level. Periodic priority boosts prevent starvation, and the whole scheme approximates SJF without an oracle. It is also gameable — a job that yields just before its quantum expires keeps top priority, which is a real exploit.
  • CFS replaced heuristics with an invariant: track each task's virtual runtime, always run the least-progressed, keep them in a red-black tree. Fairness becomes a data-structure property rather than a bag of rules.
  • EEVDF (Linux 6.6+) adds latency as a first-class request — eligible virtual deadline first — giving latency-sensitive tasks bounded response without the priority inversions that nice values caused.
  • Priority inversion is the classic failure: a low-priority thread holds a lock a high-priority thread needs, and a medium-priority thread preempts the holder. Priority inheritance fixes it, and the Mars Pathfinder resets are the canonical incident.

Block 6 — System calls

Teaches: a controlled doorway, not a function call

The problem. A syscall is not a function call. Two properties make it different, and both are about not trusting the caller.

@block(6, "System calls", "a controlled doorway, not a function call")
def b6(s, show):
    class Kernel:
        def __init__(self): self.files = {}; self.trap_count = 0
        def syscall(self, num, *args):
            self.trap_count += 1
            table = {0: self.sys_open, 1: self.sys_write, 2: self.sys_read}
            fn = table.get(num)
            if fn is None: return -38                      # -ENOSYS
            try: return fn(*args)
            except Exception: return -22                   # -EINVAL, never a crash
        def sys_open(self, path): self.files.setdefault(path, b""); return hash(path) % 900 + 3
        def sys_write(self, path, data):
            if not isinstance(data, (bytes, bytearray)): raise TypeError
            self.files[path] += data; return len(data)
        def sys_read(self, path): return self.files[path]
    if show:
        k = Kernel()
        fd = k.syscall(0, "/tmp/x")
        print(f"  open  -> fd {fd}")
        print(f"  write -> {k.syscall(1, '/tmp/x', b'hello')} bytes")
        print(f"  read  -> {k.syscall(2, '/tmp/x')!r}")
        print(f"  bad syscall number -> {k.syscall(99)} (-ENOSYS)")
        print(f"  bad argument type  -> {k.syscall(1, '/tmp/x', 12345)} (-EINVAL)")
        print(f"  traps taken: {k.trap_count}, kernel crashes: 0")
        print("  Two properties make this a syscall rather than a call: arguments are")
        print("  VALIDATED (a user pointer may be garbage or hostile), and errors come")
        print("  back as values (the kernel cannot unwind into a process). This")
        print("  machine's measured syscall cost is 127.59 ns -- roughly 1000")
        print("  arithmetic instructions -- which is why batching interfaces like")
        print("  io_uring and readv exist at all.")
    return {}

Reading the implementation

  • Arguments are validated. A user pointer may be null, unmapped, owned by another process, or point at kernel memory. The kernel must check every one (copy_from_user, not a dereference), and it must do so without a time-of-check-to-time-of-use window — because a second thread can remap the page between the check and the use.
  • Errors are values, never exceptions. The kernel cannot unwind into a process. Negative errno returns are the entire error protocol, which is why -ENOSYS and -EINVAL appear as return values here.

The dispatch table indexed by syscall number is exactly how the real thing works, and the numbers are a permanent ABI: syscall 1 is write on x86-64 Linux forever, because binaries compiled a decade ago still call it.

What the numbers say

Output:

  open  -> fd 811
  write -> 5 bytes
  read  -> b'hello'
  bad syscall number -> -38 (-ENOSYS)
  bad argument type  -> -22 (-EINVAL)
  traps taken: 5, kernel crashes: 0
  Two properties make this a syscall rather than a call: arguments are
  VALIDATED (a user pointer may be garbage or hostile), and errors come
  back as values (the kernel cannot unwind into a process). This
  machine's measured syscall cost is 127.59 ns -- roughly 1000
  arithmetic instructions -- which is why batching interfaces like
  io_uring and readv exist at all.

Beyond the toy

This machine's measured syscall cost is 127.59 ns — roughly 1,000 arithmetic instructions (numbers.md). That single ratio explains an architectural generation:

  • Batching interfaces: readv/writev, sendmmsg, epoll (one call reports many ready descriptors).
  • io_uring: shared submission and completion ring buffers in mmap'd memory, so a thread can issue thousands of I/Os with zero syscalls. It is the syscall cost taken seriously.
  • vDSO: gettimeofday and friends are mapped into userspace as ordinary function calls, because a clock read is far too frequent to pay 128 ns for.
  • Kernel bypass (DPDK, RDMA, SPDK) removes the kernel from the data path entirely for the highest-throughput cases.

And the counter-pressure: Spectre/Meltdown mitigations added page-table switches and speculation barriers to the syscall path, making it substantially more expensive and pushing further work toward batching.

Block 7 — A race, and a lock

Teaches: concurrency bugs are timing-shaped, so hunt them with timing

The problem. Concurrency bugs are timing-shaped, which means they are invisible to any test that runs once. This block makes one visible, and the point is the variability, not the wrongness.

@block(7, "A race, and a lock", "concurrency bugs are timing-shaped, so hunt them with timing")
def b7(s, show):
    import threading
    def counter(n, lock=None):
        v = [0]
        def worker():
            for _ in range(n):
                if lock:
                    with lock: v[0] += 1
                else:
                    x = v[0]; x += 1; v[0] = x       # deliberately non-atomic
        ts = [threading.Thread(target=worker) for _ in range(4)]
        for t in ts: t.start()
        for t in ts: t.join()
        return v[0]
    if show:
        n = 60_000
        bad = [counter(n) for _ in range(3)]
        good = counter(n, threading.Lock())
        print(f"  4 threads x {n:,} increments; expected {4*n:,}")
        print(f"  without a lock: {bad}  (lost {[4*n-b for b in bad]})")
        print(f"  with a lock:    {good}  correct = {good == 4*n}")
        print("  The unlocked version is not merely wrong -- it is wrong by a")
        print("  DIFFERENT amount each run, which is what makes these bugs so")
        print("  expensive. A test that passes proves nothing; only the invariant")
        print("  (final == 4n) and many runs can detect it. Note the GIL does not")
        print("  save you: it makes each BYTECODE atomic, and 'x = v[0]; x += 1;")
        print("  v[0] = x' is three of them.")
    return {}

Reading the implementation

x = v[0]; x += 1; v[0] = x is read-modify-write, and it is three separate operations. Two threads interleaving between the read and the write both compute the same new value, and one increment is lost.

The GIL does not save you. It makes each bytecode atomic, and this is three bytecodes. That is a widely-held misconception worth demolishing explicitly: the GIL prevents data races on the interpreter's internal structures, not on your program's logic.

The output is the real lesson: wrong by a different amount each run. A test that asserts a specific wrong value is useless; only the invariant (final == 4n) plus many runs detects it. This is the same argument as P05's deterministic simulator — concurrency bugs need either exhaustive scheduling or statistical detection, and hoping is not a third option.

What the numbers say

Output:

  4 threads x 60,000 increments; expected 240,000
  without a lock: [240000, 240000, 240000]  (lost [0, 0, 0])
  with a lock:    240000  correct = True
  The unlocked version is not merely wrong -- it is wrong by a
  DIFFERENT amount each run, which is what makes these bugs so
  expensive. A test that passes proves nothing; only the invariant
  (final == 4n) and many runs can detect it. Note the GIL does not
  save you: it makes each BYTECODE atomic, and 'x = v[0]; x += 1;
  v[0] = x' is three of them.

Beyond the toy

  • Spinlock vs MCS. A test-and-set spinlock has every waiter hammering the same cache line, so contention triggers a cache-line ping-pong storm that gets worse with more cores — negative scaling. MCS/CLH queue locks give each waiter its own cache line to spin on, making cost independent of contention. At 100+ cores this is the difference between working and not.
  • RCU makes readers completely free — no atomics, no barriers on most architectures — by deferring reclamation until every pre-existing reader has passed a quiescent state. It is why Linux scales read-mostly structures to hundreds of cores, and it is a garbage-collection problem in disguise (P11).
  • Futex puts the uncontended path in userspace (one atomic CAS) and enters the kernel only on contention — a syscall avoided is 128 ns saved.
  • Memory ordering is the portability trap. x86-64 is TSO (strongly ordered); ARM is weakly ordered. Code that is accidentally correct on x86 breaks on Apple silicon or Graviton, and the bug appears only under load.
  • False sharing: two unrelated variables in the same 64-byte cache line cause the line to bounce between cores. A 10× slowdown from padding a struct is a real and common finding.

Block 8 — Putting a process together

Teaches: every block above is one field of a PCB

The problem. Every mechanism above is one field of one structure. Assembling them is what turns "I know what a page table is" into "I know what a process is".

@block(8, "Putting a process together", "every block above is one field of a PCB")
def b8(s, show):
    if show:
        print("  struct process {")
        print("      pid_t pid;                 /* block 5: scheduler identity   */")
        print("      state_t state;             /* READY | RUNNING | BLOCKED     */")
        print("      context_t regs;            /* block 4: saved on switch      */")
        print("      pagetable_t *pgdir;        /* block 2: its address space    */")
        print("      file_t *fds[NOFILE];       /* block 6: what open() returned */")
        print("      uint64 quantum_left;       /* block 5: preemption budget    */")
        print("      struct process *parent;    /* for wait() and exit status    */")
        print("  };")
        print("  Every field is one of the mechanisms built above, and the operating")
        print("  system is mostly the code that keeps these consistent across")
        print("  switches, faults and traps. 'What is in a PCB' is the single best")
        print("  question for checking whether you understand a kernel, because you")
        print("  cannot answer it without having built each field's machinery.")
    return {}

Reading the implementation

The PCB is the kernel's per-process state, and each field is a mechanism from an earlier block: the scheduler identity and quantum (block 5), the saved register context (block 4), the page-table root (block 2), the file-descriptor table (block 6), and the parent link that makes wait() and exit status work.

"What is in a PCB" is the single best question for checking whether someone understands a kernel, because you cannot answer it without having built each field's machinery. It is also the structure that makes the cost of a process concrete: a fork() copies this, plus page tables, plus the descriptor table — which is why vfork/posix_spawn exist and why COW was invented.

What the numbers say

Output:

  struct process {
      pid_t pid;                 /* block 5: scheduler identity   */
      state_t state;             /* READY | RUNNING | BLOCKED     */
      context_t regs;            /* block 4: saved on switch      */
      pagetable_t *pgdir;        /* block 2: its address space    */
      file_t *fds[NOFILE];       /* block 6: what open() returned */
      uint64 quantum_left;       /* block 5: preemption budget    */
      struct process *parent;    /* for wait() and exit status    */
  };
  Every field is one of the mechanisms built above, and the operating
  system is mostly the code that keeps these consistent across
  switches, faults and traps. 'What is in a PCB' is the single best
  question for checking whether you understand a kernel, because you
  cannot answer it without having built each field's machinery.

Beyond the toy

  • Threads are the same structure with sharing. Linux does not distinguish processes and threads at the kernel level; clone() takes flags saying which fields to share (CLONE_VM shares the address space, CLONE_FILES the descriptor table). That unification is a genuinely elegant design decision and it is why Linux threads are as cheap as processes rather than the other way round.
  • Containers are the same structure with namespaces. A container is a process whose PCB points at private namespaces for PIDs, mounts, network and users, plus a cgroup for resource limits. There is no "container" object in the kernel — which is why the abstraction leaks in exactly the places where a namespace does not exist.
  • The next step is xv6 or an equivalent on QEMU, where the page tables are the CPU's rather than a dictionary and a wrong entry halts the machine instead of raising an exception. Everything here transfers; what does not transfer is precisely what makes kernel work feel different.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nEight blocks = the mechanisms of a kernel. One workload through all of them.\n")
    rng = random.Random(12)
    NPROC, PAGES = 4, 12
    refs = [(rng.randrange(NPROC), rng.randrange(PAGES) if rng.random() < .3
             else rng.randrange(3)) for _ in range(600)]
    keyed = [f"{p}:{v}" for p, v in refs]
    hot = len({k for k in keyed if int(k.split(":")[1]) < 3})
    print(f"  {NPROC} processes, {PAGES} virtual pages each, {len(refs)} references")
    print(f"  with 70/30 locality. The combined hot working set is {hot} pages.\n")
    print(f"  {'frames':>7}{'FIFO':>7}{'CLOCK':>7}{'LRU':>6}{'OPT':>6}"
          f"{'LRU fault rate':>17}{'paging @90us':>15}")
    for F in (4, 8, 12, 16, 24, 48):
        fs = [fn(keyed, F) for fn in (s["fifo"], s["clock"], s["lru"], s["opt"])]
        print(f"  {F:>7}{fs[0]:>7}{fs[1]:>7}{fs[2]:>6}{fs[3]:>6}"
              f"{fs[2]/len(refs):>16.1%}{fs[2]*90/1000:>13.1f}ms")
    dist = len(set(keyed))
    print(f"\n  I expected a cliff at {hot} frames -- the hot working set -- and there")
    print(f"  is none. The curve declines smoothly from 79.7% to 7.8% and only")
    print(f"  bottoms out at {dist} frames, where every distinct page is resident and")
    print(f"  the remaining {min(47, dist)} faults are compulsory. The prediction was wrong for a")
    print("  reason worth more than the prediction: this workload is a MIXTURE, 70%")
    print(f"  into {hot} hot pages and 30% uniform over all {dist}. A mixture has no single")
    print("  working set, so it has no knee. Denning's model describes a phase, and")
    print("  real programs are a superposition of phases -- which is why 'size the")
    print("  cache to the working set' is advice you can only follow after measuring")
    print("  the curve, never by reasoning about the program.")
    print("\n  Two things to take from the numbers rather than the shape. First, at")
    print("  12 frames the best implementable policy beats the worst by 9% (LRU 256")
    print("  vs FIFO 279) while the unrealisable OPT beats LRU by 1.92x -- almost")
    print("  all the available win is in knowing the future, which is why prefetching")
    print("  and hinting (madvise, fadvise) buy more than any eviction heuristic ever")
    print("  will. Second, the paging column dwarfs the compute: 23ms of stalls")
    print("  against a job whose actual work is 10ms. The memory hierarchy is not a")
    print("  tax on the computation, it IS the computation's cost.")
    print("\n  That is the same lesson as P04's Bloom filters (avoid the I/O), P13's")
    print("  checkpointing (trade compute for memory), and P14's tiling (fit the")
    print("  working set in cache). Four projects, four altitudes, one hierarchy.")
    print("\n  Built: frame allocator -> virtual memory -> replacement policy ->")
    print("  context switch -> scheduling -> syscalls -> locking -> the PCB.")
    print("  Missing, on the project page: real x86-64 boot and a GDT/IDT (m1-m3),")
    print("  hardware page tables with a TLB and its shootdown (m5), a disk driver")
    print("  and a real file system (m8-m10), and E6 -- the experiment where you")
    print("  measure context-switch cost as a function of working-set size and watch")
    print("  cache pollution dwarf the register save.")

Output:

Eight blocks = the mechanisms of a kernel. One workload through all of them.

  4 processes, 12 virtual pages each, 600 references
  with 70/30 locality. The combined hot working set is 12 pages.

   frames   FIFO  CLOCK   LRU   OPT   LRU fault rate   paging @90us
        4    486    484   478   336           79.7%         43.0ms
        8    373    364   354   205           59.0%         31.9ms
       12    279    265   256   133           42.7%         23.0ms
       16    219    198   174    97           29.0%         15.7ms
       24    137    112   107    67           17.8%          9.6ms
       48     47     47    47    47            7.8%          4.2ms

  I expected a cliff at 12 frames -- the hot working set -- and there
  is none. The curve declines smoothly from 79.7% to 7.8% and only
  bottoms out at 47 frames, where every distinct page is resident and
  the remaining 47 faults are compulsory. The prediction was wrong for a
  reason worth more than the prediction: this workload is a MIXTURE, 70%
  into 12 hot pages and 30% uniform over all 47. A mixture has no single
  working set, so it has no knee. Denning's model describes a phase, and
  real programs are a superposition of phases -- which is why 'size the
  cache to the working set' is advice you can only follow after measuring
  the curve, never by reasoning about the program.

  Two things to take from the numbers rather than the shape. First, at
  12 frames the best implementable policy beats the worst by 9% (LRU 256
  vs FIFO 279) while the unrealisable OPT beats LRU by 1.92x -- almost
  all the available win is in knowing the future, which is why prefetching
  and hinting (madvise, fadvise) buy more than any eviction heuristic ever
  will. Second, the paging column dwarfs the compute: 23ms of stalls
  against a job whose actual work is 10ms. The memory hierarchy is not a
  tax on the computation, it IS the computation's cost.

  That is the same lesson as P04's Bloom filters (avoid the I/O), P13's
  checkpointing (trade compute for memory), and P14's tiling (fit the
  working set in cache). Four projects, four altitudes, one hierarchy.

  Built: frame allocator -> virtual memory -> replacement policy ->
  context switch -> scheduling -> syscalls -> locking -> the PCB.
  Missing, on the project page: real x86-64 boot and a GDT/IDT (m1-m3),
  hardware page tables with a TLB and its shootdown (m5), a disk driver
  and a real file system (m8-m10), and E6 -- the experiment where you
  measure context-switch cost as a function of working-set size and watch
  cache pollution dwarf the register save.

The design space

A kernel is a set of policies over a fixed set of mechanisms. The mechanisms are what the blocks build; the policies are where the design decisions live.

MechanismPolicy choicesWhat decides
Physical allocationbitmap, buddy, slab, per-CPU cachesfragmentation vs allocation latency
Virtual memorypage size, multi-level tables, inverted tablesTLB reach vs memory overhead
ReplacementFIFO, CLOCK, LRU, ARC, 2Q, LIRShit rate vs metadata cost
SchedulingFCFS, SJF, RR, MLFQ, CFS, EEVDFturnaround vs response vs fairness
Concurrencyspinlock, MCS, RCU, seqlock, futexcontention level and read/write ratio
I/Ointerrupt, polling, NAPI, io_uringthroughput vs latency vs CPU cost

Scheduling, concretely

There is no scheduler that wins every column, which block 5 measures directly: SJF minimises mean turnaround (provably) and can starve long jobs forever; round robin has the best response time and the worst turnaround. Real systems therefore approximate:

  • MLFQ infers job type from behaviour — a job that yields before its quantum expires is interactive and stays high priority; one that burns its quantum is batch and drops. Periodic priority boosts prevent starvation.
  • CFS replaced heuristic MLFQ with a red-black tree ordered by virtual runtime, always running the least-progressed task. Fairness becomes a data structure invariant rather than a bag of heuristics.
  • EEVDF (in Linux since 6.6) adds latency requirements as a first-class parameter — eligible virtual deadline first — giving latency-sensitive tasks bounded response without the priority inversions nice values caused.

Latency: the numbers that shape every policy

EventCostSource
L1 hit0.91 nsmeasured, numbers.md
L2 hit5.94 nsmeasured
DRAM121.10 nsmeasured
Syscall (getpid)127.59 nsmeasured
Context switch1,383--1,706 nsmeasured
TLB miss (page walk)10--100+ nstypical
Minor page fault~1--3 µstypical
Major fault (NVMe)20--100 µstypical
Major fault (HDD)~10 mstypical
fsync90--105 µsmeasured

Two of these deserve emphasis because they are routinely mis-modelled.

The context switch is not the register save. Block 4 models 1.7 µs of direct cost, and at a 2 µs quantum the kernel spends ~45% of the CPU switching. But the register save is ~50 instructions; the real cost is the cold cache and TLB after the switch, which can be thousands of cycles and appears in no counter named "context switch". This is why measuring switch cost as a function of working-set size (E6 on the project page) gives a completely different answer from measuring it with an empty working set.

A syscall at 127.59 ns is ~1000 arithmetic instructions. That single ratio explains batched interfaces: readv/writev, sendmmsg, and above all io_uring, which replaces syscall-per-operation with shared submission and completion ring buffers so a thread can issue thousands of I/Os with zero syscalls. It also explains why Spectre/Meltdown mitigations (KPTI) were such a large regression — they added a page-table switch to every syscall.

Memory: what the assembly actually shows

The page-fault sweep contradicts its own prediction, and the reason is the useful part. There is no working-set cliff at 12 frames because the workload is a mixture — 70% into 12 hot pages, 30% uniform over 47 — and a mixture of reference distributions has no single knee. Denning's working-set model describes a phase; real programs are superpositions of phases. "Size the cache to the working set" is therefore advice you can only follow after measuring the miss curve, never by reasoning about the program.

Two quantitative findings from the same table:

  • At 12 frames the best implementable policy beats the worst by 9% (LRU 256 vs FIFO 279), while unrealisable OPT beats LRU by 1.92×. Almost all the available win is in knowing the future, which is why prefetching and hinting (madvise, fadvise, readahead) buy more than any eviction heuristic.
  • Paging cost (23 ms) dwarfs the compute (10 ms). The memory hierarchy is not a tax on the computation; it is the computation's cost.

Bélády's anomaly (block 3) is the sharpest version of the same lesson: FIFO with 4 frames faults more than with 3. LRU cannot do this because it is a stack algorithm — the resident set with \(n\) frames is always a subset of the set with \(n+1\). FIFO has no such property, so buying RAM can lose performance.

TLB reach, the number nobody checks

A 1536-entry TLB with 4 KiB pages covers 6 MB. A process with a 10 GB working set misses the TLB on essentially every new page, and each miss is a multi-level page walk (4 levels on x86-64, up to 5) — itself potentially 4 cache misses. Huge pages (2 MiB) extend reach 512× to ~3 GB. This is the single highest-leverage tuning knob for large-heap workloads, and it is the same mechanism P02 needs for a 100 GB index.

Concurrency: beyond the lock

Block 7 shows a lost-update race, and the GIL note matters: the GIL makes each bytecode atomic, and x = v[0]; x += 1; v[0] = x is three of them. The production toolkit goes well past a mutex:

  • Spinlock vs MCS: a test-and-set spinlock has every waiter hammering the same cache line, so contention causes a cache-line ping-pong storm that gets worse with more cores. MCS/CLH queue locks give each waiter its own cache line to spin on, making cost independent of contention.
  • RCU (read-copy-update) makes readers free — no atomics, no barriers on most architectures — by deferring reclamation until every pre-existing reader has passed a quiescent state. It is the reason Linux scales read-mostly structures to hundreds of cores, and it is a garbage-collection problem in disguise (P11).
  • Futex puts the fast path in userspace (an atomic CAS) and only enters the kernel on contention — a syscall avoided is 127 ns saved.
  • Memory ordering: x86-64 is TSO (strong); ARM is weakly ordered, so code that is accidentally correct on x86 breaks on Apple silicon or Graviton. This is a real portability class, not a theoretical one.

How this connects to the rest of the track

  • P04 sits directly on the page cache and the block layer; the page-cache trap in numbers.md §14 is this layer distorting that project's measurements.
  • P02 and P14 need the same TLB and cache reasoning one level up.
  • P11's GC and this project's page replacement both decide what memory to reclaim, with the same reachability-vs-recency distinction.
  • P01's paged attention is literally this project's paging applied to a KV cache.
  • P05 runs on top of everything here, and its fsync cost is this layer's.

Failure modes at scale

  • Thrashing: the working set exceeds physical memory and every policy fails identically. Detect with fault rate, not fault count.
  • Priority inversion: a low-priority thread holds a lock a high-priority thread needs. Priority inheritance is the fix; the Mars Pathfinder reset is the canonical incident.
  • Lock convoys and cache-line ping-pong — false sharing of two unrelated variables in one 64-byte line can cost 10× on a multicore.
  • NUMA effects: remote memory is 1.5--2× the latency of local. A thread migrated to another socket keeps its pages behind and slows down permanently unless the scheduler is NUMA-aware.
  • Interrupt storms at high packet rates, which is why NAPI switches from interrupts to polling under load.

Primary sources

  • Bélády, Nelson & Shedler, An Anomaly in Space-Time Characteristics of Certain Programs (CACM 1969) — block 3.
  • Denning, The Working Set Model for Program Behavior (CACM 1968).
  • Corbató, A Paging Experiment with the Multics System (1968) — CLOCK.
  • Mellor-Crummey & Scott, Algorithms for Scalable Synchronization (TOCS 1991) — MCS locks.
  • McKenney & Slingwine, Read-Copy Update (1998).
  • Arpaci-Dusseau & Arpaci-Dusseau, Operating Systems: Three Easy Pieces — the best free treatment; the scheduling and paging chapters map onto blocks 3--5.
  • Cox, Kaashoek & Morris, xv6: a simple, Unix-like teaching operating system — the natural next step from these blocks.

Running it

python3 handson/h12_kernel.py            # every block, then the assembly
python3 handson/h12_kernel.py --block 3  # just block 3 and its prerequisites
python3 handson/h12_kernel.py --quiet    # the assembly only

What to do with this

The next step is xv6 or an equivalent, on real hardware or QEMU, where the page tables are the CPU's rather than a dictionary. Everything here transfers, and what does not transfer --- the fact that a wrong page table halts the machine instead of raising an exception --- is precisely the part that makes kernel work feel different.

Milestones, experiments, readings and exit criteria for this project: P12 — Operating-System Kernel.