P12 — Operating-System Kernel or Kernel Subsystems

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P12 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Large · 121 hours · Weeks 100–110 · Stage 5 · Rust (or C)

Second-highest overrun risk in the journey. A hard decision point is scheduled at week 3: if the bootable path has cost you more than 15 hours in toolchain problems that teach nothing, switch to the user-space option and keep every learning objective.

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Choosing Your Target
• Central Technical Questions
• The Numbers You Are Going To Measure
• Showcase — Predict the Context Switch Before Measuring It
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

Eleven projects have treated some numbers as free: a system call, a page fault, a context switch, a lock acquisition. This project puts prices on all of them, measured on your own hardware.

That matters concretely and immediately. The cost of a syscall determines whether io_uring is worth it. The cost of a context switch determines the right thread-pool size, and why goroutines beat threads. The cost of a page fault explains why P03's mmap experiment behaved as it did. Every performance intuition you have used since Stage 1 has been resting on numbers you had never measured.

The second reason is isolation. You will implement the user/kernel boundary and then try to violate it from user space. Watching your own protection work — and finding the case where it does not — is the only way to develop real intuition about the difference between a security boundary and a convention.

Completeness is explicitly not the goal. The kernel will not run a shell. It will not have a network stack. It will schedule a handful of processes, fault pages in and out, service a few syscalls, and be measured to death. That is the project.

Prerequisites

• P11-II helpful: dispatch loops, stack frames, and root-set traversal all reappear
• Rust or C; comfort with pointers, alignment, and volatile access
• Willingness to debug with no debugger for a while (though QEMU + GDB is available and you should set it up in milestone 1)

Duration and Size

Large, 121 hours, 11 weeks.

Choosing Your Target

Decide in week 1, and re-decide at week 3.

Recommendation: B, with C as the declared fallback. RISC-V on QEMU with riscv64-unknown-elf gets you booting in a day rather than a week, and the privileged spec is a readable ~100 pages instead of Intel's several thousand.

The week-3 decision rule: if you have spent more than 15 hours on toolchain, linker scripts, or bootloader issues without having taken a timer interrupt, switch to C. You lose the MMU and the privilege boundary; you keep scheduling, paging simulation, syscall-boundary measurement, context switching, and filesystems — which is most of the learning and all of the measurement.

Central Technical Questions

1. What does a context switch actually cost, and what is it made of? Register save is nanoseconds; the real cost is elsewhere.
2. What is a page fault, and what is the cost of the resulting work?
3. What does the user/kernel boundary buy, and what does crossing it cost?
4. How does a scheduler decide? And what does each policy optimise at the expense of what?
5. Why is virtual memory worth its complexity? Give three reasons, only one of which is "more memory than you have".
6. What is the actual mechanism of isolation? Not "the OS prevents it" — which hardware feature, checked when?

The Numbers You Are Going To Measure

Predict each before you measure. Reference measurements taken on the machine used to build this track (12-core arm64 macOS laptop, clang -O2, C):

Three lessons are already visible before you write a line of kernel code:

1. getpid() at 1.23 ns is the classic bad syscall benchmark. It is four times the cost of an empty loop iteration, which is impossible for a mode switch. libc caches the value. Every "syscalls cost 1 ns" claim traces to this. Use a syscall that must trap — close(-1) fails in the kernel and returns immediately, which is close to a pure boundary-crossing measurement.
2. A real syscall is ~128 ns, ~410× an empty loop iteration. That number is why batching interfaces exist — io_uring, sendmmsg, vectored I/O — and why a per-request gettimeofday in a hot loop is a real cost.
3. A context switch is ~1,676 ns, ~13× a syscall. And this is the cheap case: same machine, tiny working set, warm caches. The dominant real cost is the cache and TLB pollution the new process causes, which does not appear in a ping-pong microbenchmark at all. Measuring a switch between two processes with 1 MB working sets — E4 — will produce a much larger number, and understanding why is the point.

Reproduce all of these on your machine in milestone 1, before writing any kernel code, so you have a host baseline to compare your own kernel against.

Showcase — Predict the Context Switch Before Measuring It

Twenty minutes with a calculator, before any kernel code. The ping-pong number in the table above is the best case; this is what it omits.

# P12 -- predict the context-switch cost before you measure it.
L1, DRAM = 0.91, 121.10     # ns, measured
SWITCH   = 1530.0           # ns, ping-pong best case
print(f"{'working set':>12}{'lines':>9}{'refill cost':>14}{'total':>12}{'vs best case':>14}")
for kb in (4, 64, 256, 1024, 4096):
    lines = kb*1024/64
    refill = lines*DRAM
    tot = SWITCH + refill
    print(f"{kb:>9} KB{lines:>9.0f}{refill/1000:>12.1f} us{tot/1000:>10.1f} us{tot/SWITCH:>12.0f}x")
print("\\nA ping-pong benchmark measures the first row and reports 1.5 us. A real")
print("switch between two 1 MB working sets costs ~2 ms of refill it never sees.")

 working set    lines   refill cost       total  vs best case
        4 KB       64         7.8 us       9.3 us           6x
       64 KB     1024       124.0 us     125.5 us          82x
      256 KB     4096       496.0 us     497.6 us         325x
     1024 KB    16384      1984.1 us    1985.6 us        1298x
     4096 KB    65536      7936.4 us    7937.9 us        5188x
\nA ping-pong benchmark measures the first row and reports 1.5 us. A real
switch between two 1 MB working sets costs ~2 ms of refill it never sees.

The refill cost exceeds the switch itself by 1,300× at a 1 MB working set, and no ping-pong benchmark can see it. This is why E4 sweeps working-set size rather than quoting a single number — and why thread-pool sizing is a real decision rather than a default.

Implementation Milestones

Concepts To Study

• Boot: firmware → bootloader → kernel; the memory map; why the linker script matters
• Privilege levels: rings on x86, machine/supervisor/user on RISC-V; what each instruction is allowed to do
• Interrupts and exceptions: vectors, trap frames, nesting, masking, the difference between an interrupt and a trap
• Physical memory management: bitmap vs buddy vs free list; external and internal fragmentation
• Virtual memory: page tables (multi-level), TLB, ASIDs, page faults, demand paging, COW
• Page replacement: FIFO, LRU, clock, second-chance; Bélády's anomaly — FIFO can get worse with more memory, which is worth demonstrating
• Processes and threads: what is shared, what is not
• Context switching: register save, page-table switch, TLB flush vs ASIDs, and the cache pollution that dominates
• Scheduling: round-robin, priority, MLFQ, CFS/weighted fair; the throughput/latency/fairness trilemma
• Synchronisation: atomics, spinlocks, futex-style blocking, priority inversion, convoying
• System calls: the trap mechanism, argument validation (the confused-deputy problem), the cost model
• Filesystems: inodes, directories, the buffer cache, write-back vs write-through
• Isolation: what hardware enforces vs what the kernel must check

Primary-Source Readings

Budget: 17 hours.

Experiments

E7 is the best single experiment here. Bélády's anomaly — a FIFO-replacement system whose fault rate increases when you give it more memory — is deeply counterintuitive and completely reproducible with a hand-constructed reference string. Producing it yourself is the clearest possible demonstration that "more resources is better" is an assumption, not a law. LRU is a stack algorithm and provably cannot exhibit it; showing both in the same harness makes the point twice.

E4 is the most practically useful. The ~1,676 ns from a ping-pong benchmark is the best case. Sweep the working-set size and watch the switch cost rise as each process evicts the other's cache lines. The curve you produce is the real reason thread-pool sizing matters.

Benchmarks and Metrics

Every timing must use a cycle counter (rdtsc / mcycle), not a wall clock. At these magnitudes, clock read overhead is a significant fraction of what you are measuring — subtract the measured overhead of the counter read itself and say that you did.

Correctness Tests

1. Isolation. A user process attempting to read kernel memory, write another process's memory, or execute a privileged instruction must fault, and the kernel must survive. Test each explicitly — this is the project's central correctness property.
2. Syscall argument validation. Pass a kernel pointer, an unmapped pointer, a pointer that spans a mapped/unmapped boundary, and a huge length. All rejected. The spanning case is the one that gets missed.
3. Context-switch fidelity. Every register, including the stack pointer and status register, restored exactly. Test with a program that fills all registers with known values.
4. Page-table correctness. Every mapping maps what it claims; permission bits are enforced for read, write, and execute independently.
5. No memory leaks across process create/destroy cycles — census the physical allocator.
6. Scheduler liveness. No task starves under any policy. Assert a maximum wait time.
7. Lock correctness. Mutual exclusion under stress; no lost wakeups.
8. Filesystem consistency after a simulated crash.
9. Nested interrupts do not corrupt trap frames.
10. Determinism where the design allows it, for reproducible experiments.

Failure Tests

Expected Difficulties

1. Toolchain and boot can eat two weeks. Mitigation: RISC-V, and the week-3 decision rule. Set a timer, honour it.
2. Debugging without a debugger. Mitigation: QEMU + GDB in milestone 1, before any kernel logic. Serial output early and always.
3. The first page fault handler will triple-fault, and a triple fault gives you no information. Mitigation: QEMU's -d int,cpu_reset logging, and building the handler incrementally — trap, then print, then handle.
4. Cycle-accurate measurement is subtle. Serialising instructions, counter overhead, and frequency scaling all matter. Measure the measurement first.
5. Scope is unbounded here. Every subsystem invites another. The exit criteria are the scope; a network stack is not on the list.
6. The 11-week ceiling is real. At week 11, ship what passes and write the rest into the extension section.

Scope Boundaries

In scope: boot (or a user-space harness), memory management, interrupts, syscalls, processes and threads, ≥2 scheduler policies, virtual memory with ≥2 replacement policies, synchronisation, an in-memory filesystem, a block-device abstraction.

Out of scope: a network stack; USB, graphics, or any real hardware driver beyond serial and timer; SMP and multicore (single core only — SMP is a whole second project); a shell or userland utilities; POSIX compatibility; dynamic linking; security features beyond basic isolation; power management.

SMP deserves emphasis. Adding a second CPU multiplies the difficulty of every subsequent bug. Single core, explicitly stated in the report as a limitation.

Deliverables

1. kernel/ — bootable image plus a QEMU run script, one command
2. MEASUREMENTS.md — every cost, yours and the host's, with methodology. This is the artifact of lasting value: a personal reference for what things cost
3. REPORT.md centred on E4 (context switch vs working set) and E7 (Bélády)
4. Notebook entries for E4, E6, E7
5. A boot-to-first-syscall trace with timings at each stage

Exit Criteria

• Boots (or the user-space harness runs) and reaches a scheduling loop
• ≥2 processes run concurrently with enforced isolation
• All isolation tests pass: kernel memory, cross-process memory, privileged instructions
• Syscall argument validation rejects all five hostile cases including the spanning pointer
• E2/E3 complete: your syscall cost measured and decomposed, compared against the host
• E4 complete: context-switch cost vs working-set size, plotted
• E6 complete: ≥2 scheduler policies compared on throughput, p99 latency, and fairness
• E7 complete: Bélády's anomaly demonstrated with FIFO and shown absent under LRU
• MEASUREMENTS.md complete with methodology
• REPORT.md written with a falsified prediction

Extension Ideas

• Copy-on-write fork, with a measured comparison against eager copying across process sizes.
• Synchronisation shoot-out: spinlock vs ticket lock vs MCS vs blocking, under contention, with the crossover identified. Directly applicable to every concurrent system you will ever tune.
• A real driver for one QEMU device (virtio-blk) with measured throughput.
• SMP, if you have appetite. Treat it as its own project with its own budget.

Connections

Backward: P11-II — dispatch loops, stack frames, and GC root traversal all recur. P04 — the buffer cache and I/O patterns, now from the other side.

Forward:

• → P14: memory hierarchy from the bottom. Your TLB and cache measurements are the foundation of the roofline work
• → P15: the measured costs inform every latency budget in the integrated system
• → Retroactively, everything. After this project, re-read your P03 mmap result and your P05 latency decomposition. Both will read differently

References

• Arpaci-Dusseau, R. H., Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books, 2018. ostep.org — free.
• Cox, R., Kaashoek, M. F., Morris, R. xv6: a simple, Unix-like teaching operating system. MIT, RISC-V edition.
• Ritchie, D. M., Thompson, K. The UNIX Time-Sharing System. CACM 17(7), 1974.
• Lampson, B. W. Hints for Computer System Design. SOSP 1983.
• Bélády, L. A., Nelson, R. A., Shedler, G. S. An anomaly in space-time characteristics of certain programs running in a paging machine. CACM 12(6), 1969.
• Denning, P. J. The Working Set Model for Program Behavior. CACM 11(5), 1968.
• Ousterhout, J. Why Aren't Operating Systems Getting Faster As Fast as Hardware? USENIX Summer 1990.
• Anderson, T. E., Bershad, B. N., Lazowska, E. D., Levy, H. M. Scheduler Activations. SOSP 1991.
• Mellor-Crummey, J. M., Scott, M. L. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM TOCS 9(1), 1991. MCS locks.
• Bovet, D., Cesati, M. Understanding the Linux Kernel, 3rd ed. O'Reilly, 2005.
• The RISC-V Instruction Set Manual, Volume II: Privileged Architecture. RISC-V International.
• Levin, R. et al. Policy/mechanism separation in Hydra. SOSP 1975. The idea behind making your scheduler policies swappable.