Operating systems: processes, virtual memory, file systems, and the kernel boundary

Why this subject matters now

The operating system used to be the thing under the application, a layer whose details only kernel developers needed. Three shifts changed that. The first is that the machine stopped getting faster per core around 2005, so a modern server is fifty or a hundred hardware threads with a deep and non-uniform memory hierarchy, and the kernel is what decides which of those threads runs what, where its memory lives, and how much cache it destroys for its neighbors. The second is that devices got fast. A single NVMe drive answers a 4 KiB read in tens of microseconds and sustains a million operations per second, which is the same order as the cost of the software path that used to be invisible next to a 10 ms seek. That inversion is the reason the block layer was rewritten around multiple queues and the reason io_uring exists. A 100 Gb/s network interface delivers a small packet every few hundred nanoseconds, fewer cycles than a system call took a decade ago. The third is that deployment moved into containers and virtual machines, so every practitioner now debugs across a boundary that is either a namespace (a restricted view of one kernel) or a hypervisor (a second level of address translation), and confusing the two produces both security mistakes and performance mysteries.

The measured consequences are concrete. On the machine used throughout this page, an ordinary function call costs 1.39 ns and the cheapest possible system call costs 133.8 ns, a factor of 96. Spectre and Meltdown mitigations pushed that ratio up across the industry after 2018 and are the direct cause of the batching designs that followed. A context switch between two processes on the same core costs about 1.9 microseconds of round-trip latency here, but the interesting part is what it does to the caches. With a 64 MiB working set per peer, the same ping-pong costs 11.3 microseconds more per turn than running alone, six times the direct switch cost. A minor page fault costs about 1.5 microseconds, so touching a fresh 512 MiB anonymous mapping one page at a time costs nearly 200 ms of pure fault handling, which is why huge pages and MAP_POPULATE are not micro-optimizations for large models. Reading a file whose pages are already in the page cache runs at 9.0 GB/s here, while reading the same file after eviction runs at 2.3 GB/s. Nothing in that list is exotic, and all of it decides whether a training job is compute-bound or waiting.

Several things a practitioner is expected to know today were optional five years ago. Linux replaced the completely fair scheduler with EEVDF in 6.6, and "eligible" and "lag" now carry precise meanings in that model. eBPF turned the kernel into a programmable, verified extension surface and is now the standard way to answer a production performance question. io_uring made asynchronous storage and network I/O a shared-ring problem rather than a syscall problem. cgroup v2 is what actually enforces a memory or CPU limit in a training cluster, and what happens at the limit matters. And fsync semantics, not the file system's marketing, decide whether data survives a power cut.

Core theory

What an operating system is for

Three jobs explain almost every design decision in a kernel. Multiplexing reconciles one CPU, one memory, and one disk with many programs, so the OS time-shares the processor, space-shares the memory, and multiplexes the device queues. Isolation means a buggy or hostile program must not be able to read another's memory, corrupt its files, or hold the processor forever, so the OS uses hardware it alone controls (privilege levels, the MMU, the timer interrupt) to make those things impossible rather than merely discouraged. Abstraction exists because raw hardware is hostile to program against, so the OS exports a small number of virtual objects, and the good ones are those that can be implemented efficiently over many different hardware realizations. A file is a nameable, growable, byte-addressable sequence, and the same abstraction works over a spinning disk, an SSD, a network server, and a memory-backed filesystem. A process is a virtualized CPU plus a virtualized memory. A socket is a virtualized wire.

The three goals conflict, and most of the interesting engineering is in the conflict. Isolation wants every crossing checked, while multiplexing wants crossings to be cheap. Abstraction wants a uniform interface, but performance wants the application to see what the device actually is (which is why O_DIRECT, madvise, posix_fadvise, and io_uring's registered buffers all exist as escape hatches). Lampson's 1983 collection of design hints is the compact statement of the tradeoffs, and it is worth reading for the vocabulary alone. Do one thing well, keep the common path fast, use hints, handle normal and worst case separately, and reason end to end about where a check belongs.

The mechanism/policy split runs through the whole subject. The mechanism for time-sharing is the timer interrupt plus the context switch. The policy is the scheduler, and it changes every few years. The mechanism for memory protection is the page table, and the policy is replacement and placement. Ritchie and Thompson's 1974 description of UNIX is the classic demonstration of how far a small set of orthogonal mechanisms (the file descriptor, the process, the shell as an ordinary program) can be pushed, and nearly every system in use today inherits its shape.

The kernel boundary, from privilege and traps to the system call path

Isolation rests on a hardware distinction between at least two modes of execution. On x86-64 these are rings, and in practice only two are used, ring 3 for user code and ring 0 for the kernel. The distinction is not a software convention. In ring 3 the processor refuses to execute instructions that would let a program escape, such as loading CR3 (the page-table root), disabling interrupts, writing most model-specific registers, executing I/O port instructions when the permission bitmap forbids them. A page table entry carries a user/supervisor bit, so kernel memory is not addressable from ring 3 even though it lives in the same address space. On ARM the same idea appears as exception levels EL0 and EL1, with EL2 for a hypervisor, and on RISC-V as U, S and M modes.

A user program therefore cannot call the kernel. It can only cause a trap, a synchronous, hardware-defined transfer that changes privilege and jumps to an address the kernel chose in advance. There are three sources of entry, and keeping them straight matters for debugging. A system call is a deliberate trap (syscall on x86-64, svc on ARM). An exception is an involuntary trap caused by the current instruction (page fault, divide by zero, invalid opcode). An interrupt is asynchronous and unrelated to the running instruction (timer, device completion, inter-processor interrupt).

Here is the x86-64 system call path end to end, which is worth memorizing because so much else hangs on it.

  user space                                 kernel space
  ----------                                 ------------
  1. arguments into registers
     rax = syscall number, rdi rsi rdx r10 r8 r9 = args
  2. SYSCALL instruction
       - hardware saves RIP -> rcx, RFLAGS -> r11
       - loads RIP from MSR_LSTAR, CS/SS from MSR_STAR
       - masks flags per MSR_SYSCALL_MASK (clears IF: interrupts off)
       - raises CPL to 0.  NOTE: it does NOT switch the stack.
                                    ---------------------------------->
                                    3. entry_SYSCALL_64:
                                       swapgs (GS now points at per-CPU area)
                                       stash user rsp in per-CPU scratch
                                       load kernel rsp from cpu_current_top_of_stack
                                       build struct pt_regs on the kernel stack
                                    4. with KPTI: switch CR3 to the kernel page
                                       table (user table lacks kernel mappings)
                                    5. bounds-check rax against sys_call_table,
                                       run seccomp filters and audit hooks
                                    6. call sys_xxx(regs) ... the actual work
                                    7. syscall_exit_to_user_mode:
                                       check TIF_ flags: signals, need_resched,
                                       so a syscall return is a scheduling point
                                    8. restore CR3 (user), swapgs back,
                                       SYSRET: RIP <- rcx, RFLAGS <- r11, CPL 3
  9. result in rax (negative errno on failure)
                                    <----------------------------------

Two details in that sequence explain most of the cost. SYSCALL is fast precisely because it does very little. It does not switch stacks, does not save general-purpose registers, and does not consult a descriptor table. Everything else is software the kernel writes, and each mitigation added since 2018 lands there. Kernel page-table isolation, the fix for Meltdown, adds a CR3 write on entry and another on exit. Without process context identifiers each of those would flush the entire TLB, which is why PCID support went from a curiosity to a requirement. Spectre variant 2 mitigations add indirect-branch barriers or retpolines on the same path. The measured cost of the cheapest syscall on the machine below is 133.8 ns, roughly 270 cycles at its nominal 2.0 GHz, against 1.39 ns for a plain function call.

The second detail is that a system call return is a scheduling point. Step 7 checks whether a signal is pending and whether need_resched is set, so a program that syscalls frequently gets preempted at convenient boundaries, and a program in a tight compute loop is preempted only by the timer interrupt (or not at all, on a nohz_full isolated core).

Because the boundary is expensive, the kernel offers ways to avoid it. The vDSO is a small shared object the kernel maps into every process containing real code, not stubs, for calls that only need to read kernel-maintained data. On this machine clock_gettime costs 32.2 ns through the vDSO and 188.6 ns when forced through the kernel with syscall(SYS_clock_gettime, ...), a 5.9× difference for the identical result. Batching interfaces (readv, sendmmsg, io_uring) amortize one crossing over many operations. Shared memory removes the crossing entirely for data, leaving it only for synchronization, which is exactly the futex design discussed later.

Processes, address spaces, and threads

A process is the OS's answer to "what does it mean to run a program", namely a virtualized CPU (its own register state, its own illusion of continuous execution) plus a virtualized memory (its own address space) plus the ambient rights and resources that go with it. The kernel's record of all this is the process control block, called struct task_struct in Linux, and it is instructive to enumerate what it must hold, because every field corresponds to something that has to be saved, restored, or checked.

The address space is the other half. A 64-bit Linux process on x86-64 with four-level paging has a 48-bit canonical address space split in half, user addresses from 0 to 0x00007fffffffffff (128 TiB) and kernel addresses from 0xffff800000000000 upward, with the sign-extension rule making everything between those two ranges non-canonical and faulting. The layout inside the user half is a policy choice, and the modern one is deliberately randomized.

  0x0000_0000_0000_0000  +---------------------------+
                         |  (unmapped, so *NULL      |
                         |   faults instead of       |   mmap_min_addr
                         |   silently reading)       |
                         +---------------------------+
              ~0x5555...  |  text (r-x)               |  ELF, PIE base randomized
                         |  rodata (r--)             |
                         |  data + bss (rw-)         |
                         +---------------------------+
                         |  heap  -> grows up        |  brk / sbrk, then mmap
                         |                           |  for large allocations
                         +---------------------------+
                         |                           |
              ~0x7f00...  |  mmap region:             |  shared libraries,
                         |  anonymous + file maps    |  malloc arenas, thread
                         |  <- grows down            |  stacks, the vDSO
                         +---------------------------+
                         |  main stack <- grows down |  RLIMIT_STACK, guard gap
  0x0000_7fff_ffff_ffff  +---------------------------+
       non-canonical hole (any access faults)
  0xffff_8000_0000_0000  +---------------------------+
                         |  direct map of all RAM    |  page_offset_base
                         |  vmalloc, vmemmap, kernel |  (also randomized)
                         |  text and modules         |
  0xffff_ffff_ffff_ffff  +---------------------------+

The kernel half is mapped into every process, protected by the user/supervisor bit, which is what makes a system call cheap, since the kernel does not have to change address spaces to run. Meltdown broke that arrangement by letting speculative execution leak the contents of supervisor pages, and the fix (kernel page-table isolation) gives each process a second, nearly empty page table for user mode, which is why step 4 of the syscall path above exists.

A thread is the same structure with the memory half shared. Linux does not have two mechanisms. clone takes flags saying which parts of the parent to share, and fork and pthread_create are two points in that space. CLONE_VM shares the mm_struct, CLONE_FILES the descriptor table, CLONE_FS the root and working directory, CLONE_SIGHAND the handler table, and CLONE_THREAD puts the new task in the same thread group so it shares a pid as seen by getpid. A container runtime uses the same call with CLONE_NEWNS, CLONE_NEWPID and friends, which is the first hint that containers are not a separate mechanism.

User-level threads (green threads, fibers, goroutines, async tasks) multiplex many logical threads onto few kernel threads. They win on switch cost, because a switch is a function call that saves a few registers and swaps stacks, with no ring transition, so hundreds of nanoseconds becomes tens. They lose on blocking, because a blocking system call blocks the kernel thread and therefore every user thread on it, and on parallelism, because the kernel schedules only what it can see. Every practical runtime therefore uses an M:N arrangement with non-blocking I/O underneath, which is exactly why io_uring and epoll matter to language runtimes.

fork, exec, wait, and why copy-on-write is the right answer

UNIX separates process creation from program loading. fork makes a duplicate of the caller, returning 0 in the child and the child's pid in the parent. execve replaces the current address space with a new program, and wait reaps the child and collects its exit status. The separation looks wasteful and is in fact the source of the shell's power. Between the fork and the exec the child is an ordinary program that can rearrange its own descriptors, which is how redirection (dup2 onto fd 1), pipelines (pipe then two dup2s), and privilege dropping (setuid before exec) are implemented without any of them being special cases in the kernel.

The obvious implementation of fork copies the entire address space, which is absurd when the common sequence is fork immediately followed by exec, discarding the copy. Copy-on-write is the fix and it is worth deriving rather than asserting. Let the parent have \( n \) resident pages. At fork time, instead of copying page contents, the kernel copies the page tables and marks every writable private page read-only in both parent and child, bumping each physical page's reference count. Reads then proceed at full speed in both processes. A write traps as a protection fault. The fault handler sees the VMA is writable but the PTE is not and the page is shared, allocates a new frame, copies 4 KiB, points the faulting process's PTE at the copy with write permission, and drops the old page's count. When the count falls to one, the last owner's PTE can simply be made writable again with no copy at all.

The cost model follows directly. Let \( c_{pt} \) be the per-page cost of duplicating page-table entries, \( c_{f} \) the cost of one copy-on-write fault including the 4 KiB copy, and \( w \) the number of pages the child actually writes before exec or exit. Eager copying costs \( n\,c_{copy} \). Copy-on-write costs

The measured values on this machine are \( c_{pt} \approx 25 \) ns per 4 KiB page (from the fork sweep below, where 524288 pages cost 14.27 ms) and \( c_{f} \approx 2.0 \) µs. Copying a page outright at the machine's memory bandwidth is roughly 4096 B / 10 GB/s ≈ 0.4 µs, so \( c_f \) is dominated by the trap and the page allocation rather than by the copying. Copy-on-write wins whenever \( n c_{pt} + w c_f < n c_{copy} \), that is when \( w/n < (c_{copy} - c_{pt})/c_f \approx (400 - 25)/2000 = 0.19 \). A child that writes fewer than about a fifth of its inherited pages comes out ahead, and a child that calls exec writes essentially none.

Three things to read from that table. The per-page cost is flat at roughly 25 ns once the fixed cost of creating a task (about 33 µs, visible as the 153 ns/page at 1 MiB) is amortized, confirming that fork is linear in pages, not bytes, because the kernel walks the page tables. Copying 2 GiB of data outright would take roughly 200 ms at 10 GB/s, and the measured fork takes 14.3 ms, so copy-on-write buys about 14× even before considering that the child usually touches almost none of it. And the copy-on-write fault is 2.0 µs, some 80× the marginal page-table cost, which is why a fork-heavy workload with a large writable heap (a garbage-collected runtime, or a Python process whose reference counts touch every object header) sees the cost reappear later as fault storms rather than at the fork itself.

That last point has a famous consequence for data loaders. A Python process that forks worker processes shares its objects copy-on-write, but CPython writes a reference count into the object header on every access, so merely iterating a shared list dirties one page per object touched and the memory is copied anyway. Storing the dataset as a NumPy array or a memory-mapped file avoids this, because the payload bytes are not object headers.

execve is the other half. It builds a fresh mm_struct, maps the ELF segments as private file-backed mappings (so the text is shared with every other instance of the program and demand-paged from the page cache), sets up the stack with argv, envp and the auxiliary vector, maps the vDSO, and transfers control to the dynamic loader, which then maps the shared libraries. It is worth appreciating how much of a process start is file mapping. strace -c /bin/true on this machine counts 109 system calls, of which 77 fail, almost all of them the loader probing candidate paths for shared objects.

wait exists because the exit status has to live somewhere until someone asks. A process that has exited but not been reaped is a zombie. Nearly all its resources are gone, but the task_struct remains so the parent can read the status. If the parent exits first, the child is reparented (to init, or to the nearest ancestor marked as a subreaper) and reaped there. This is also why a container's PID 1 matters. In a pid namespace, PID 1 inherits orphans, and if it does not reap them the namespace fills with zombies.

Context switch mechanics, and why processes cost more than threads

A context switch is the sequence that stops one task and starts another on the same CPU. In Linux the core of it is __schedule calling context_switch, which does three things. It switches the memory context if the incoming task has a different mm (write CR3, possibly with a PCID), switches the kernel stack and the callee-saved registers (switch_to, a short piece of assembly), and hands off the floating-point and vector state lazily. The register save is genuinely small. The caller-saved registers are already on the kernel stack from the trap that got us here, so switch_to saves a handful of registers and swaps the stack pointer.

Measuring it requires care, because the natural experiment (send a message and wait for a reply) also measures the pipe. The standard trick is a ping-pong between two peers pinned to the same logical CPU. Neither can proceed without the other being scheduled, so one round trip contains exactly two context switches, and the same experiment run between two threads of one process isolates the address-space change.

The process case is 7.8% more expensive than the thread case, about 136 ns per switch. That is the direct cost of changing address spaces, and it is small for a specific reason. x86-64 process context identifiers let the CPU tag TLB entries with an address space, so writing CR3 no longer flushes the TLB. On hardware or configurations without PCID the same experiment shows a much larger gap, because every switch would throw away every translation. The cross-core rows are included to make a different point. When the peers are on different cores nothing is being switched at all, and the 16 µs is the cost of an inter-processor interrupt, a wakeup, and the cache line of the pipe buffer bouncing between cores. It is slower than the switch, which is the opposite of most people's intuition and the reason sched_yield-based spin loops behave so strangely.

The direct cost is not the real cost. A context switch also destroys cache and TLB state, and the victim pays for it afterward as misses. The experiment below adds a working set. Each peer touches 512 random 64-byte lines in its own buffer per turn, and the same work is timed with no peer at all as a baseline.

Overhead grows from 5.05 µs to 11.30 µs as the working set grows from 32 KiB to 64 MiB, while the direct switch cost is unchanged at about 1.9 µs per switch. In other words, at a large working set roughly 6 µs per turn is cache and TLB rebuilding, three times the mechanical cost of the switch itself. This is the quantitative version of "context switches are expensive", and it explains cache affinity in schedulers, the value of pinning latency-sensitive threads, and why a machine running twice as many runnable threads as cores can lose far more than the switch count suggests.

Scheduling, where the metrics conflict before any policy is chosen

Scheduling looks like an optimization problem until the objective is written down, at which point it becomes several incompatible optimization problems. Let job \( i \) arrive at \( a_i \), require \( C_i \) of service, first run at \( s_i \), and complete at \( f_i \). The standard quantities are turnaround \( T_i = f_i - a_i \), response \( R_i = s_i - a_i \), and waiting \( W_i = T_i - C_i \). A scheduler can minimize average turnaround, or minimize average or worst-case response, or maximize throughput, or divide the processor in fixed proportions, or guarantee that every periodic task meets a deadline. These pull in different directions. Minimizing average turnaround means running short jobs first, which starves long ones. Minimizing response means switching constantly, which wastes the processor on switches and cache misses. Proportional fairness means deliberately not running the job that would finish soonest.

FIFO (first come, first served) is the baseline, with no preemption and jobs run to completion in arrival order. It has zero overhead and terrible average turnaround whenever a long job arrives first, the convoy effect. With four jobs of length 10, 4, 2 and 8 arriving together in that order, completion times are 10, 14, 16 and 24, so average turnaround is (10+14+16+24)/4 = 16.0.

Shortest job first runs the same jobs in the order 2, 4, 8, 10, giving completions 2, 6, 14, 24 and average turnaround (2+6+14+24)/4 = 11.5, an improvement of 28% for free. That it is optimal is worth proving, because the proof is short and the technique (exchange argument) recurs everywhere.

Claim. For \( n \) jobs all available at time 0 on one processor with no preemption, ordering by non-decreasing service time minimizes average turnaround.

Proof. Under a non-preemptive order \( \pi(1), \dots, \pi(n) \), the completion time of the \( k \)-th job is the sum of the first \( k \) service times, so

The total is a weighted sum in which the weights \( n, n-1, \dots, 1 \) are fixed and decreasing in position. By the rearrangement inequality, such a sum is minimized when the largest weight multiplies the smallest \( C \), which is exactly non-decreasing order of \( C \). Concretely, suppose two adjacent jobs in positions \( k, k+1 \) have \( C_{\pi(k)} > C_{\pi(k+1)} \). Swapping them leaves every other job's completion time unchanged (the pair occupies the same total interval) and changes the pair's sum of completion times from \( (P + C_{\pi(k)}) + (P + C_{\pi(k)} + C_{\pi(k+1)}) \) to \( (P + C_{\pi(k+1)}) + (P + C_{\pi(k+1)} + C_{\pi(k)}) \), where \( P \) is the work before the pair. The difference is \( C_{\pi(k)} - C_{\pi(k+1)} > 0 \), so the swap strictly improves the objective. Repeating eliminates every inversion and terminates at sorted order. \( \blacksquare \)

With arrivals over time the preemptive version, shortest remaining time first, is optimal for average turnaround by the same argument applied at each arrival. Neither is implementable, since both require knowing \( C_i \) in advance, and neither bounds starvation. Every real scheduler is therefore an attempt to approximate "short jobs first" from observed behavior while bounding the harm to long jobs.

Round robin and the quantum tradeoff, computed

Round robin preempts at a fixed quantum \( q \) and cycles. Response time becomes bounded. With \( n \) runnable tasks and switch cost \( c \), the worst-case wait before a task first runs is \( (n-1)(q + c) \). The processor overhead fraction is \( c/(q+c) \). Both formulas point in opposite directions, which is the entire design tension.

Take three jobs of 10 ms each arriving together and a switch cost of 0.05 ms, and compute exactly.

Round robin is the worst policy for average turnaround on equal-length jobs, because it finishes all of them at nearly the same late time instead of finishing some early. With a 1 ms quantum the three jobs complete at roughly 28, 29 and 30 ms, against 10, 20 and 30 ms under FIFO. It is chosen anyway, because interactive response is what users perceive. With ten runnable tasks and a 0.005 ms switch, a 1 ms quantum gives a 9.05 ms worst-case wait at 0.50% overhead, and a 10 ms quantum gives a 90.05 ms wait at 0.05% overhead. Human perception puts the knee around 10 ms of jitter, which is why time-sharing quanta have sat in the single-digit millisecond range since the 1970s, and why Linux's EEVDF base slice is on the order of a millisecond rather than a microsecond. The floor is set by the measured 1.9 µs switch cost plus several microseconds of cache rebuilding.

Priorities, starvation, and multi-level feedback queues

Static priorities solve responsiveness and create starvation. A steady supply of high-priority work means low-priority work never runs. Priority inversion is the sharper failure, where a high-priority task waits on a lock held by a low-priority task that cannot get the processor because a medium-priority task is running. The fix is priority inheritance (the holder temporarily runs at the waiter's priority), which Linux implements for PTHREAD_PRIO_INHERIT mutexes and for PI-futexes. The Mars Pathfinder resets in 1997 are the standard cautionary example of what happens without it.

A multi-level feedback queue approximates shortest-job-first without an oracle by using observed behavior as a proxy. The rules are usually stated as follows. A job at higher priority runs first. Jobs at the same priority round robin. A new job enters at the top. A job that uses its entire allotment at a level moves down a level, and a job that yields before its allotment expires stays. The last rule alone is gameable (a program that sleeps for a microsecond just before its quantum expires keeps top priority forever), so the allotment must be measured as cumulative CPU time at a level rather than per-quantum, and periodic priority boosting of everything prevents starvation and adapts when a batch job turns interactive. The design is the practical answer to "prefer short and interactive jobs while bounding harm to long ones", and it is the ancestor of the interactivity heuristics in every desktop scheduler through the 2000s.

Proportional share with lottery and stride

A different objective is to guarantee each task a specified share of the processor rather than a priority ordering. Lottery scheduling (Waldspurger and Weihl, 1994) gives each task tickets and draws a random winner each quantum, so expected share is \( t_i / \sum_j t_j \) and no starvation is possible as long as a task holds a ticket. Randomness gives correct behavior in expectation with no state, and it composes, since currencies let a group subdivide its allocation locally.

The variance is the problem. Over \( N \) quanta, the number of wins for a task with probability \( p \) has standard deviation \( \sqrt{N p (1-p)} \), so relative error decays only as \( 1/\sqrt{N} \). Stride scheduling replaces the dice with exact arithmetic. Give each task a stride inversely proportional to its tickets, keep a pass value, and always run the task with the lowest pass, then advance its pass by its stride. The result is deterministic proportional allocation with error bounded by one quantum. With tickets 100, 50 and 250 and a numerator of 10,000, the strides are 100, 200 and 40. Running the algorithm for 80 quanta gives exactly 20, 10 and 50 allocations, matching the ideal shares of 25%, 12.5% and 62.5% with no error at all. Stride's pass value is the direct ancestor of the virtual runtime in the completely fair scheduler.

Linux specifically, from O(1) to CFS to EEVDF

Before 2.6 the Linux scheduler scanned every runnable task on every decision, which was fine at ten tasks and quadratic pain at thousands. The O(1) scheduler (2003) replaced the scan with 140 priority levels, two arrays (active and expired) per CPU, and a bitmap so that "find the highest non-empty priority" is a single find-first-set instruction. Constant-time decisions came at the cost of an elaborate interactivity heuristic that estimated sleep time to decide priority bonuses, and it was tuned, retuned and still produced audible desktop stalls.

CFS (2.6.23, 2007) threw the heuristic away and modelled an ideal machine that runs every runnable task simultaneously at a fraction of speed proportional to its weight. Each task carries a virtual runtime that advances at a rate inversely proportional to its weight,

The scheduler always runs the task with the smallest virtual runtime, kept in a red-black tree keyed by it, so the decision is \( O(\log n) \) and equality of virtual runtimes is exactly equality of weighted service. The nice level maps to weight through a table in which each step multiplies by about 1.25, so that one nice level changes relative share by roughly 10% in a two-task system. The table values are 1024, 820, 655, 526, 423, 335, ..., 15 for nice 0 through 19, and indeed \( 1024/1.25^5 = 335.5 \) against the table's 335 for nice 5.

The slice length comes from a target latency. With total weight \( W = \sum_j w_j \), task \( i \) receives \( \text{slice}_i = L \cdot w_i / W \) within each latency period \( L \), floored by a minimum granularity so that a hundred runnable tasks do not produce hundred-microsecond slices. Two tasks at nice 0 and nice 5 with \( L = 24 \) ms get \( 24 \times 1024/1359 = 18.08 \) ms and \( 24 \times 335/1359 = 5.92 \) ms. Both advance virtual runtime by the same amount over their own slices, \( 18.08 \times 1024/1024 = 18.08 \) and \( 5.92 \times 1024/335 = 18.08 \), which is the invariant that makes the tree ordering meaningful.

That arithmetic is directly testable. Two spinning processes pinned to one logical CPU for four seconds, with the second reniced, give the following on this machine.

The agreement is within a tenth of a percent at every level, which is a stronger statement than it looks. It says the weight table is not a hint or a bias, it is an exact proportional-share contract that the scheduler honors over multi-second horizons. This is also what cgroup cpu.weight controls, one level up the hierarchy.

EEVDF (earliest eligible virtual deadline first) replaced CFS as the default in Linux 6.6, implementing an algorithm published by Stoica and Abdel-Wahab in 1995. The motivation is that CFS has no principled notion of latency. A task that wants a short slice for responsiveness and a task that wants a long slice for throughput are treated identically, and the various latency hacks bolted onto CFS over the years (wakeup preemption granularity, GENTLE_FAIR_SLEEPERS) were unprincipled patches. EEVDF adds two concepts.

Lag is the difference between the service a task should have received and what it did receive. With virtual time \( V(t) \) advancing at \( 1/W \) per unit of service and \( S_i(t) \) the actual service,

and the lags always sum to zero because total ideal service equals total actual service. A task is eligible when its lag is non-negative, that is when it has received no more than its share so far. Among eligible tasks, EEVDF runs the one with the earliest virtual deadline, defined from the task's requested slice \( r_i \) as

A task asking for a short slice gets a near deadline and therefore runs sooner, at the price of running for less time, and a task asking for a long slice waits longer but runs uninterrupted. Latency and throughput become a per-task request rather than a global tunable, which is what sched_setattr's sched_runtime hint expresses. Fairness is preserved because eligibility gates everything. A task that has run ahead of its share is not eligible at all until virtual time catches up.

A concrete step. Three tasks with weights 1024, 1024 and 512 have \( W = 2560 \). After 30 ms of total service, ideal shares are \( 30 \times 1024/2560 = 12 \) ms, 12 ms and 6 ms. Suppose actual service is 12, 10 and 8 ms. Then lags are 0, +2 and −2 ms. Normalized virtual runtimes \( S_i w_0 / w_i \) are 12, 10 and 16, and virtual time is \( 30 \times 1024/2560 = 12 \). Tasks 1 and 2 are eligible (12 ≤ 12 and 10 ≤ 12), task 3 is not (16 > 12). With a 3 ms requested slice the deadlines are \( 12 + 3 = 15 \), \( 10 + 3 = 13 \) and \( 16 + 3 \times 1024/512 = 22 \), so task 2 runs next, the task that is furthest behind, with the tie broken by deadline rather than by raw virtual runtime.

Real-time scheduling with rate monotonic and EDF

Time-sharing asks for good average behavior, while real-time asks for a guarantee. The standard model (Liu and Layland, 1973) is \( n \) independent periodic tasks, task \( i \) with period \( T_i \), worst-case execution time \( C_i \), deadline equal to its period, preemptible at zero cost. Utilization is \( U = \sum_i C_i / T_i \).

Rate monotonic assigns static priorities by rate, with shorter periods getting higher priority. It is optimal among static-priority policies, and it is schedulable if \( U \le n(2^{1/n} - 1) \), which decreases from 1.000 at \( n = 1 \) to 0.828, 0.780, 0.757, 0.743 at \( n = 2,3,4,5 \) and tends to \( \ln 2 \approx 0.693 \).

The bound is worth deriving for two tasks, where the whole structure is visible. Assume \( T_1 < T_2 < 2T_1 \) so \( F = \lfloor T_2/T_1 \rfloor = 1 \), and consider the critical instant when both are released together, which is the worst case because it maximizes interference. Let \( G = T_2/T_1 - F \). Fix \( C_1 \) and ask for the largest \( C_2 \) that still meets its deadline. If \( C_1 \le T_2 - F T_1 \), the second task's period contains \( F + 1 \) full executions of task 1, so \( C_2^{\max} = T_2 - (F+1)C_1 \) and \( U = C_1/T_1 + 1 - (F+1)C_1/T_2 \), which is decreasing in \( C_1 \). If instead \( C_1 \ge T_2 - F T_1 \), then \( C_2^{\max} = F(T_1 - C_1) \) and \( U = C_1(1/T_1 - F/T_2) + F T_1/T_2 \), which is increasing in \( C_1 \). The minimum of the maximum utilization therefore sits at the boundary \( C_1 = T_2 - F T_1 = G T_1 \), where

Differentiating, \( U'(G) = 1 - F(F+1)/(F+G)^2 \), which vanishes at \( G = \sqrt{F(F+1)} - F \). For \( F = 1 \) this is \( \sqrt{2} - 1 = 0.4142 \), and substituting back gives \( U = 0.4142 + 0.5858/1.4142 = 0.8284 = 2(2^{1/2} - 1) \), the claimed bound. The general \( n \) case is the same argument with \( n \) tasks and a longer optimization. Liu and Layland's paper carries it out, and the result is not reproduced here.

The bound is sufficient, not necessary. Response-time analysis is exact. The response of task \( i \) is the fixed point of

iterated from \( R_i^{(0)} = C_i \) until it stops changing, and the task set is schedulable if every \( R_i \le T_i \). For \( (C,T) = (1,4), (2,6), (3,12) \) the utilization is \( 1/4 + 1/3 + 1/4 = 5/6 = 0.833 \), above the three-task bound of 0.780, so the simple test says nothing. Iterating gives \( R_1 = 1 \le 4 \), then \( R_2 = 2 + \lceil 2/4 \rceil \cdot 1 = 3 \), stable, \( 3 \le 6 \). For task 3, \( R_3 = 3 \to 3 + \lceil 3/4 \rceil 1 + \lceil 3/6 \rceil 2 = 6 \to 3 + \lceil 6/4 \rceil 1 + \lceil 6/6 \rceil 2 = 3+2+2 = 7 \to 3 + \lceil 7/4 \rceil 1 + \lceil 7/6 \rceil 2 = 3+2+4 = 9 \to 3 + \lceil 9/4 \rceil 1 + \lceil 9/6 \rceil 2 = 3+3+4 = 10 \), then stable at 10, and \( 10 \le 12 \). The set is schedulable despite failing the utilization test.

EDF assigns priorities dynamically by absolute deadline and is optimal in a stronger sense. If any schedule meets all deadlines, EDF does, and for this task model EDF is schedulable exactly when \( U \le 1 \). The optimality proof is an exchange argument. Take any feasible schedule and let \( t \) be the earliest instant at which it runs a job whose deadline is later than that of some other job available at \( t \). Swap the two jobs' allocations at \( t \) and at the later time when the earlier-deadline job would have run. The earlier-deadline job now finishes no later than before, and the later-deadline job finishes no later than the earlier one's original completion, which was itself no later than the swapped job's deadline, so no deadline that was met becomes missed. Each swap moves the schedule strictly closer to EDF order in a finite-length schedule, so after finitely many swaps the schedule is EDF and still feasible. \( \blacksquare \)

EDF's weakness is overload. At \( U > 1 \) it degrades chaotically, missing deadlines across the whole task set rather than sacrificing the least important ones, whereas rate monotonic degrades predictably from the bottom priority up. Linux implements both worlds. SCHED_FIFO and SCHED_RR are static-priority classes above the fair class, and SCHED_DEADLINE is a constant-bandwidth-server EDF implementation that admits a task only if the new utilization stays below the limit, which is admission control turning EDF's overload failure into a rejected request.

Multicore scheduling with per-CPU runqueues, balancing, and affinity

A single global runqueue is correct and does not scale. Every scheduling decision on every core takes the same lock, and the runqueue's cache lines bounce. Linux therefore keeps a runqueue per CPU, and the fairness argument becomes a balancing argument across queues. The balancer is driven by scheduling domains, a hierarchy reflecting the machine. SMT siblings share a core, cores share an L3, and sockets share a NUMA node. Balancing happens more aggressively and more often at the cheap levels of the hierarchy and rarely at the expensive ones, because migrating a task between SMT siblings costs nothing while migrating it across sockets throws away its cache and, worse, leaves its memory on the wrong node.

The measurements above quantify why affinity is not superstition. A task with a 64 MiB working set that loses its caches pays about 11.3 µs per resumption on this machine. If it runs for 100 µs between switches, that is an 11% tax. Migration across a NUMA boundary is worse, because the tax is permanent, since every subsequent memory access crosses the interconnect until the pages are migrated. Linux's automatic NUMA balancing addresses this by periodically unmapping a sample of a task's pages so the next access faults, recording which node faulted, and migrating either the pages to the task or the task to the pages. That mechanism, deliberately causing faults to collect information, is a good example of the kernel using a cheap hint rather than exact accounting.

Two failure modes are worth naming. Work conservation can fail. cgroup bandwidth control (cpu.max) makes a task unrunnable when its quota is exhausted, so cores idle while work waits, and in a training cluster this shows up as throughput collapse when the quota is set slightly below what the job needs. And thundering herds appear on wakeup, when many tasks waiting on one event are all made runnable at once and all migrated at once. Both are policy problems that no amount of scheduler-internal cleverness fixes. They are fixed by setting limits correctly and by waking one waiter (FUTEX_WAKE with a count of one, EPOLLEXCLUSIVE) rather than all.

Synchronization inside the kernel

Kernel synchronization differs from application synchronization in one decisive way. Some of the code cannot sleep. An interrupt handler has no process context to block, so it cannot take a mutex, cannot wait for memory reclaim, and must allocate with GFP_ATOMIC or not at all. That single constraint explains why the kernel has half a dozen locking primitives where a user program has one.

The foundation is the atomic read-modify-write. On x86 a lock-prefixed instruction (lock cmpxchg, lock xadd) makes the operation indivisible with respect to other cores by holding the cache line in the exclusive state for the duration. On ARM and RISC-V the same effect comes from a load-linked / store-conditional pair retried in a loop. Everything else is built from these. The memory-ordering rules that go with them, and the acquire/release vocabulary, are developed in concurrent systems programming. The kernel spells them smp_load_acquire, smp_store_release and smp_mb.

Spinlocks versus sleeping locks is a cost comparison, not a taste. A waiter that spins burns \( t_{\text{hold}} \) of processor time, while a waiter that sleeps burns roughly two context switches, measured at 3.8 µs round trip on this machine. Spinning is right when the critical section is much shorter than that and when the holder is guaranteed to be running on another core (which is why spinning is wrong on a uniprocessor and wrong when the holder can be preempted). Hence the rules. Kernel spinlocks disable preemption while held, and any lock also taken by an interrupt handler must be taken with interrupts disabled on the local CPU (spin_lock_irqsave), or the handler can deadlock against the code it interrupted. Sleeping locks (struct mutex, semaphores, rw_semaphore) are right for long or blocking critical sections, and Linux's mutex is itself adaptive. It spins while it observes that the owner is still running, and sleeps once the owner is descheduled.

Naive test-and-set spinlocks fail at scale because every waiter keeps writing the same cache line, so the line ping-pongs and the winner is arbitrary. Queued locks fix both. MCS locks give each waiter its own cache line to spin on and hand the lock along the queue in FIFO order, and Linux's qspinlock packs an MCS queue into a four-byte word so that the uncontended fast path is a single compare-and-swap while contention degrades into a queue rather than a stampede.

Futexes are the user-space half of the same design, and the split is the point. The lock word lives in ordinary shared memory, so an uncontended acquire and release are a compare-and-swap and a store with no kernel involvement at all, and the kernel is called only to sleep and to wake. FUTEX_WAIT takes an address and an expected value and atomically checks and sleeps, which closes the race where a waiter decides to sleep just as the holder releases. The measured behavior of the three-state futex mutex implemented below bears this out. With one thread and 200,000 lock/unlock pairs, zero futex system calls are issued. With eight threads contending, 284,471 calls are issued over 1.6 M acquisitions, or 0.18 per acquisition. The fast path really is free, and the slow path is entered only when there is something to wait for.

RCU (read-copy-update) is the kernel's answer to read-mostly data, and it is worth understanding because nothing in user space looks like it. Readers execute rcu_read_lock, dereference a pointer, and execute rcu_read_unlock. In the common non-preemptible build those first and last operations compile to nothing at all, so a reader costs exactly one dependent load. Writers do not modify in place. They copy the object, modify the copy, publish it with a release store to the pointer, and then wait for a grace period, a period after which every CPU has passed through a quiescent state (a context switch, a return to user mode, or an idle period), which proves that no reader can still hold the old pointer, because a reader is not allowed to sleep or be preempted inside a read-side critical section. Only then is the old copy freed, either by blocking in synchronize_rcu or asynchronously via call_rcu.

The asymmetry is the design. Readers pay nothing and never block writers, while writers pay a latency measured in milliseconds and the memory cost of keeping two versions alive. That trade is correct exactly when reads vastly outnumber writes and stale-but-consistent reads are acceptable, which describes routing tables, the dentry cache, module lists, and namespace lookups. It is wrong when writes are frequent (the grace-period cost dominates) or when a reader must see the very latest value (RCU gives no such guarantee, since a reader may observe the old version for the duration of its critical section). Seqlocks occupy a neighboring point, where readers retry if a writer intervened, which is cheap for small, frequently-updated values such as the timekeeping structures the vDSO reads.

Memory, from segmentation to multi-level page tables

Virtual memory solves four problems at once, and it is useful to keep them separate because different mechanisms would solve each alone. Relocation means a program can be compiled for one address range and run anywhere. Protection means a process cannot name another's memory, so isolation is enforced by the addressing hardware rather than by checks in software. Sharing means the same physical page can appear in several address spaces, which is how shared libraries, shared memory, and copy-on-write all work. Overcommit and demand paging mean the sum of virtual sizes can exceed physical memory because a mapping need not have a frame behind it until it is touched.

The earliest schemes were base-and-bound (one register pair per process, giving relocation and protection but no sharing and no sparseness) and segmentation (a small number of base/bound pairs for code, data and stack, which allows sharing at segment granularity and sparse address spaces, but suffers external fragmentation because segments have arbitrary sizes). Paging removes external fragmentation by making every allocation unit the same size, at the cost of internal fragmentation of at most one page per region and, critically, at the cost of a much larger translation table.

The table size is the problem that shapes everything else. A flat page table for a 48-bit address space with 4 KiB pages needs \( 2^{48}/2^{12} = 2^{36} \) entries, and at 8 bytes each that is 512 GiB of table per process. The fix is to exploit sparseness with a radix tree. Split the virtual page number into fields, one per level, and allocate a table only where something is mapped. x86-64 uses four levels of 512 entries each (\( 512 = 4096/8 \), so each table is exactly one page), consuming \( 4 \times 9 = 36 \) bits plus a 12-bit offset for 48 bits total. The remaining 16 bits must be a sign extension of bit 47, which is what makes non-canonical addresses fault. Five-level paging (LA57) adds a fifth 9-bit field for a 57-bit space, and this machine's CPU reports the la57 flag.

Decompose a real address. Take 0x00007F9C2B4D51A8, a typical stack or mmap address.

  0x0000_7F9C_2B4D_51A8
   = 0000000000000000 011111111 001110000 101011010 011010101 000110101000
     |--- sign 16 ---||--PML4--||--PDPT--||---PD---||---PT---||-- offset --|
                          255       112       346       213        0x1a8

  walk (each step is a physical memory read of 8 bytes):
    CR3 -----------------> PML4 table, entry 255  -> PDPT frame
    PDPT table, entry 112 ------------------------> PD   frame
    PD   table, entry 346 ------------------------> PT   frame
    PT   table, entry 213 ------------------------> data frame
    physical address = (data frame << 12) | 0x1a8

Four memory references for one translation, and each of them can itself miss in the cache. That is the cost the TLB exists to eliminate. If the PD entry had its page-size bit set, the walk would stop one level early and the entry would map a 2 MiB page with a 21-bit offset (\( \texttt{0x000D51A8} \) here). A PDPT entry with that bit set maps a 1 GiB page.

Page-table memory is now proportional to what is actually mapped. One gibibyte of contiguous 4 KiB mappings needs \( 2^{30}/2^{21} = 512 \) page tables plus one each of PD, PDPT and PML4, so \( 515 \times 4096 = 2.11 \) MiB, about 0.2% of the mapped size. With 2 MiB pages the 512 leaf tables disappear and the cost falls to three pages, 12 KiB. This 0.2% is also the per-process cost of a large shared mapping. A hundred processes each mapping the same 100 GiB dataset pay 200 MiB of page tables each unless the mapping is shared at the table level, which is exactly what hugetlbfs page table sharing and, more recently, mshare proposals address.

TLBs, huge pages, and the cost of a walk

The translation lookaside buffer caches recent translations. A typical modern x86 core has a small first-level data TLB of a few dozen entries and a second-level TLB of order two thousand entries. With 4 KiB pages, two thousand entries cover \( 2048 \times 4\,\text{KiB} = 8 \) MiB of address space. With 2 MiB pages the same entries cover 4 GiB. That ratio is the entire argument for huge pages, and it is measurable.

The measurement below is a dependent pointer chase, one 8-byte slot per page, arranged as a random cycle over 131,072 pages of a 512 MiB region, so every load depends on the previous one and nothing can be overlapped or prefetched. The data working set is identical in both runs, and only the page size differs.

Read the last row carefully, because it is the one people get wrong. Huge pages did not make memory faster. They removed 19.8 ns of page-walk latency from a 136 ns access, about 15%. The gain is bounded by how much of the access time was translation, and it appears only when the working set is large enough to miss the TLB but the data misses anyway. Huge pages also have real costs. The allocator must find physically contiguous, aligned 2 MiB blocks, so under fragmentation either the allocation stalls in compaction or silently falls back. Internal fragmentation wastes up to 2 MiB per sparse region, and a copy-on-write fault on a huge page copies 2 MiB instead of 4 KiB. The 554 ns per 4 KiB of first touch in the table is exactly that cost showing up. The fault count fell by 512× but each fault now zeroes 2 MiB, and zeroing is bandwidth-bound.

Two further mechanisms matter in practice. Address space identifiers (ASIDs on ARM, PCIDs on x86) tag TLB entries with the address space they belong to, so a context switch need not flush the TLB, which is why the measured process-versus-thread switch gap above is only 136 ns. And TLB shootdown exists because the TLB is per-core and the page tables are shared. A process that unmaps or changes protection on a page must invalidate the entry on every core that might have cached it, which Linux does by sending inter-processor interrupts and waiting. On a 52-thread machine a single munmap of a widely-shared mapping can therefore cost tens of microseconds and disturb every core, which is why high-performance allocators recycle memory rather than returning it, and why MADV_FREE (mark pages reclaimable without unmapping) exists.

Page faults, demand paging, and what each kind costs

A page fault is an exception raised by the MMU when a translation fails, and the interesting fact is that most faults are not errors. The handler receives the faulting address (in CR2 on x86) and an error code saying whether the access was a read or a write, whether it came from user or supervisor mode, and whether the entry was absent or present-but-forbidden. It then looks the address up in the process's tree of virtual memory areas and decides which of several very different situations it is in.

The order-of-magnitude gap between a minor fault (1.5 µs) and a major fault (tens of µs) is the reason the page cache, the readahead machinery and the working-set logic exist, and the gap between a minor fault and an ordinary store (21.5 ns) is the reason pre-faulting matters. One useful optimization is visible in the measurements. Mapping a warm 2 GiB file and reading every byte took only 32,768 minor faults, not 524,288, because Linux's fault-around installs a batch of surrounding PTEs on each fault. Dividing gives 64 KiB per fault, precisely the default fault_around_bytes of 65536, so each fault maps 16 pages.

Replacement policies, and Belady's anomaly demonstrated

When memory is full, some page must be evicted. The policies are best compared on a fixed reference string, which is what the simulator below does. The canonical string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

The bolded entries are Belady's anomaly. FIFO takes more faults with four frames than with three, 10 against 9. More memory made things worse. The mechanism is easy to see by hand. With three frames, after 1 2 3 the reference to 4 evicts 1, to 5 evicts 2, and so on. With four frames the eviction order is different in a way that happens to discard exactly the pages about to be used. This is not a curiosity about one string. Running FIFO over the same string repeated three times and sweeping the frame count finds the anomaly again at four frames, 30 faults against 27 at three frames.

LRU and OPT cannot exhibit this, and the reason is a structural property worth knowing by name. A policy is a stack algorithm if for every reference string and every \( m \), the set of pages resident with \( m \) frames is a subset of the set resident with \( m+1 \) frames. If that inclusion holds, then any reference that hits with \( m \) frames also hits with \( m+1 \), so the fault count is non-increasing in memory size and no anomaly is possible. LRU satisfies it because its resident set is exactly the \( m \) most recently used distinct pages, and the \( m \) most recent are always a subset of the \( m+1 \) most recent. OPT satisfies it by a similar argument on future distances. FIFO does not, because its resident set depends on insertion order rather than on a nested ranking of the pages, so the two configurations can disagree about which page to hold.

OPT (Belady's MIN, 1966) evicts the page whose next use is farthest in the future. It is unimplementable and it is the yardstick. On the trace below it takes roughly half the faults of LRU, which is the honest measure of how much a real policy leaves on the table. LRU is the practical target, and exact LRU is too expensive to implement (it would require updating a timestamp or a list on every memory access, in hardware). CLOCK is the standard approximation. Keep the frames in a circle with one reference bit each, set by the hardware on access. On a miss, advance the hand, clearing set bits (giving those pages a second chance) until a clear bit is found, and evict there. It costs one bit per frame and one amortized scan step per miss.

Two conclusions from that table. CLOCK tracks LRU closely (within 10% at every size, and better than LRU at 48 frames) while costing a single bit per frame, which is why every real system uses a CLOCK variant rather than true LRU. And on a purely random trace over the same 64 pages, FIFO, LRU and CLOCK are indistinguishable (17,541, 17,547 and 17,551 faults at 8 frames), because with no locality there is no information in the past to exploit. Only OPT, which cheats by seeing the future, does better at 12,394. Replacement policy matters exactly to the extent that the workload has locality, which is the practical lesson for anyone tuning a cache.

Working sets, thrashing, and what the kernel actually does

Denning's working set (1968) makes locality quantitative. The working set \( W(t, \tau) \) is the set of distinct pages referenced in the window \( (t - \tau, t] \), and its size is the memory the process needs to run without excessive faulting. On the trace above, the average working-set size grows from 6.72 pages at \( \tau = 10 \) to 14.04 at \( \tau = 50 \), 19.45 at \( \tau = 100 \), 44.59 at \( \tau = 500 \) and 54.54 at \( \tau = 1000 \). The shape of that curve is the point. It rises steeply and then flattens near the size of the hot set, and the knee is where a memory allocation stops buying fault reductions.

Thrashing is what happens when the sum of the working sets exceeds physical memory. Each process faults, blocks on I/O, and while it waits the others evict its pages, so the system spends all its time paging and almost none computing. Utilization collapses non-linearly, and the classic mistake is to respond by admitting more work, which makes it worse. The principled response is admission control. Keep the sum of working sets below memory and suspend whole processes rather than starving all of them, which is the reasoning behind Denning's working-set policy and behind the modern practice of setting per-container memory limits so that one job's growth cannot evict another's.

Linux does not implement any of the textbook policies literally. It keeps two lists, active and inactive, and approximates LRU with a second-chance promotion between them. A page enters the inactive list and is promoted to active only on a second reference, which protects the working set from a single large streaming scan. It records refault distances so that a page evicted and quickly re-read can be recognized as having been evicted too eagerly. Since 6.1 it also ships multi-generational LRU, which replaces the two lists with a small number of generations aged by a scanning algorithm and has measurably lower CPU cost and better hit rates under memory pressure. Anonymous pages need swap to be evictable at all. On a machine with no swap configured, as here, the only reclaimable memory is clean file-backed pages, which is why a memory-hungry job on a swapless container hits the OOM killer rather than degrading gracefully.

Overcommit is the policy that lets the sum of mappings exceed memory plus swap. Linux's default heuristic mode (vm.overcommit_memory = 0, which is what this machine reports) accepts allocations that look reasonable and refuses wild ones, while strict mode (2) refuses anything beyond a configured ratio, at the cost of breaking programs that map far more than they touch. The case for overcommit is precisely copy-on-write and sparse mappings. A process that forks with a 100 GiB heap needs no new memory until it writes. The case against is that failure moves from a malloc that returns NULL to an OOM killer that picks a victim later, from a context that has no idea what the memory was for. The kernel's score is roughly the fraction of memory the process uses, adjusted by oom_score_adj, and the practical consequences are familiar to anyone who has run training jobs. The largest process (usually the one doing the real work) is the most likely victim, and the fix is per-cgroup limits so the kill happens inside the offending container.

Kernel allocators, buddy and slab

The kernel allocates memory at two granularities and uses a different algorithm for each. The buddy allocator hands out physically contiguous runs of pages in power-of-two orders (order 0 = 4 KiB up to order 10 = 4 MiB on x86-64). A request for order \( k \) takes a free block of order \( k \). If none exists it splits a block of order \( k+1 \) into two buddies, recursively. On free, a block is coalesced with its buddy if the buddy is also free, and the buddy's address is computable by flipping one bit (\( \text{buddy} = \text{addr} \oplus (2^k \times 4096) \)), which makes coalescing \( O(1) \) rather than a search. The cost is internal fragmentation up to a factor of two, and the benefit is that contiguity is maintained without a compaction pass.

Most kernel objects are far smaller than a page and are allocated and freed constantly, such as task_struct, inodes, dentries, and network buffers. Bonwick's slab allocator (1994) caches objects of one type in slabs carved from pages, keeps them initialized (so a freed object can be handed out again without re-running its constructor), and colors slabs by offsetting their start so that objects of the same type in different slabs do not all map to the same cache set. Linux's current implementation, SLUB, keeps a per-CPU active slab so the fast path is a pointer bump with no lock, falls back to per-node partial lists, and returns empty slabs to the buddy allocator. The SLAB implementation was removed in 6.8, leaving SLUB as the only choice.

The reason to know this as an application developer is diagnostic. slabtop and /proc/slabinfo attribute kernel memory to object types, so "the machine is out of memory but no process is large" usually resolves to dentry or inode caches grown by a workload that touched millions of files, which is a common shape for a data-loading pipeline over a directory of small files.

File systems, from inodes and directories to allocation

A file system turns a flat array of fixed-size blocks into named, growable byte sequences with metadata and (sometimes) durability guarantees. The classic UNIX decomposition separates three things that are often confused. An inode is the file, a fixed-size record holding type, permissions, owner, timestamps, link count, size, and the map from file offsets to disk blocks. A directory is an ordinary file whose contents are name-to-inode-number pairs. A name is therefore not a property of a file at all, which explains a set of behaviors that otherwise look arbitrary. A file can have several names (hard links, with the link count in the inode), renaming within a file system moves no data, and deleting a file that a process still has open removes the name but not the inode, so the space is reclaimed only when the last link and the last open descriptor are gone.

The block map is where the design choices are. Contiguous allocation gives perfect sequential performance and cannot grow files. Linked allocation grows freely and destroys random access. Keeping the links in a separate table is the FAT design, which needs the whole table in memory to be fast. The UNIX answer is a multi-level index inside the inode, some direct block pointers, then a single indirect block (a block full of pointers), a double indirect, and a triple indirect. Small files, which are the overwhelming majority, are reachable with no indirection at all, while large files remain possible.

The arithmetic is worth doing once. With 4 KiB blocks and 4-byte block numbers, one indirect block holds \( 4096/4 = 1024 \) pointers. With 12 direct pointers the reachable file size is

The cost is that reading one byte at the end of a 3 TiB file requires three metadata reads before the data read, though in practice those indirect blocks are cached. The deeper problem is that describing a contiguous 1 GiB region takes 262,144 individual block pointers, which is why modern file systems use extents, a triple (file offset, block offset, length) describing a whole run. One extent replaces those quarter of a million pointers, shrinking metadata by orders of magnitude and making sequential I/O expressible in one request. ext4 and XFS are both extent-based, and XFS has been extent-based and B+tree-indexed since the early 1990s.

FFS (McKusick and colleagues, 1984) is the design that made the layout itself the performance story. The original UNIX file system scattered inodes at one end of the disk and data wherever it fit, so a simple read walked the arm back and forth and achieved a few percent of the drive's bandwidth. FFS divided the disk into cylinder groups, each with its own inode table, data blocks and free bitmaps, and applied locality heuristics. Put a file's inode in the same group as its directory, put its data blocks in the same group as its inode, and spread directories across groups so that groups do not fill unevenly. It added fragments so that a large block size did not waste half the disk on small files, and it reserved a fraction of space (the well-known 10%) because allocation quality collapses when a file system is nearly full and the allocator can no longer find nearby free blocks. The reported improvement was an order of magnitude in delivered bandwidth. Every one of those ideas survives. The free-space reserve and the locality heuristics are still in ext4, and the "keep related things close" principle simply changed units when the media stopped having an arm.

Crash consistency through journaling, and what each mode guarantees

A single logical operation touches several blocks. Appending to a file updates the free bitmap, the inode (size, block pointer, timestamp) and the data block. A crash between those writes leaves the file system inconsistent in ways that range from harmless (lost space, where the bitmap says allocated but nothing points to it) to catastrophic (a block claimed by two files, or an inode pointing at a block containing another user's old data). The disk offers atomicity only for a single sector, so consistency has to be constructed.

The pre-journal answer was to write in a careful order and repair after a crash with fsck, which scans the entire file system. That is correct and takes time proportional to the file system size, which stopped being acceptable when file systems reached terabytes. Journaling replaces the scan with write-ahead logging. Describe the update in a log, wait for the log to be durable, then apply the update in place. After a crash, replay the log from its last checkpoint, which takes time proportional to the log, not the disk.

  Journaled transaction, ext3/ext4 with JBD2:

    1. TxB (transaction begin, id)      -.
    2. journal blocks: metadata (and     |  written to the log area,
       data too, in data=journal mode)   |  order within the group free
                                        -'
    3. barrier / FUA: the log contents must be durable
    4. TxE (commit block, with checksum)    <- the atomic switch
    5. barrier
    6. checkpoint: write the same blocks to their real locations
    7. free the log space

  Recovery: replay every transaction whose TxE is present and whose
  checksum matches; discard any partial tail.

The commit block is what makes the transaction atomic. It is one sector, so it either exists or does not. The checksum in it lets ext4 detect a torn transaction whose contents were reordered by the device, which in turn allows dropping one of the two barriers, a real performance win. The three data modes then differ in what, besides metadata, they order.

Notice what none of the modes promise, namely that a write which the application performed is present at all. Journaling protects the file system's own invariants. It says nothing about application durability. That is fsync's job, and the gap between those two ideas is the single most common source of data-loss bugs.

The alternatives are worth knowing. Soft updates (Ganger and McKusick) track dependencies between in-memory blocks and order the writes so the on-disk state is always recoverable without a log, at the price of considerable complexity and a background fsck for leaked space. Copy-on-write file systems (ZFS, btrfs) never overwrite live data. An update writes new blocks, then new versions of the metadata pointing at them, up to a root block that is switched atomically. Consistency is then structural rather than logged, snapshots are nearly free (keep the old root and its reachable blocks), and end-to-end checksums stored in the parent pointer detect silent corruption that a journal cannot. The costs are fragmentation over time and read-modify-write amplification for small random updates inside large blocks, plus the awkward interaction between copy-on-write and workloads that overwrite in place (databases, virtual machine images), which is why those are usually given a no-copy-on-write attribute.

Log-structured file systems (Rosenblum and Ousterhout, 1991) take the idea to its conclusion. Treat the whole device as an append-only log, buffer writes in memory and flush them as large segments, and keep an inode map, itself logged, to find the current location of each inode. Writes become purely sequential, which was the right bet when disks' sequential bandwidth was improving much faster than their seek time. The cost is cleaning. Segments accumulate dead blocks and must be compacted, and the cleaner competes with the workload exactly when the file system is busy and full. A well-known critique from a competing group showed that on transaction-processing workloads the cleaning cost could erase the benefit, and the debate over which policy wins under which workload has never fully closed.

That design did not lose. It moved. An SSD's flash translation layer is a log-structured file system. Pages cannot be overwritten, so writes go to a fresh page, a mapping table is updated, and a garbage collector reclaims erase blocks by copying out the still-valid pages. So is an LSM tree, the structure under RocksDB, LevelDB, Cassandra and the storage engines of most modern key-value systems. Buffer in memory, flush sorted runs, compact in the background. The same three-part vocabulary (sequential writes, an indirection map, background cleaning with a write-amplification cost) describes all three, and the same tuning question appears in each, how much space to leave free so the cleaner has room to work.

The page cache, writeback, and fsync

Every read and write through the normal path goes through the page cache, which is unified with the virtual memory system. A page of a file is the same object whether it was mapped with mmap or read with read. Reads are served from it and trigger readahead when a sequential pattern is detected. Writes mark pages dirty and return immediately. Writeback happens later, driven by per-device flusher threads, when dirty memory exceeds vm.dirty_background_ratio, when a page's age exceeds vm.dirty_expire_centisecs (30 s by default), or synchronously when dirty memory exceeds vm.dirty_ratio and the writer is throttled.

The measurements make the layering visible. On this machine, writing 2 GiB into the page cache runs at 2.71 GB/s and returns before anything reaches the device. The subsequent fsync of that dirty data takes 606 ms, which implies about 3.5 GB/s of actual device throughput. Reading the same file cold gives 2.28 GB/s and warm gives 9.02 GB/s, so the cache is worth 4.0× on sequential reads. For random 4 KiB reads the gap is far larger, 47.0 µs cold against 1.00 µs warm, a factor of 47. And the durability cost is stark. Appending 4 KiB and returning takes 1.15 µs, while appending 4 KiB and calling fsync takes 608.7 µs, a factor of 529.

fsync(fd) means make this file's data and the metadata needed to find it durable. It does not mean the directory entry is durable, so the standard safe-write recipe is write to a temporary file, fsync the temporary, rename over the target, then fsync the containing directory. fdatasync skips metadata that does not affect retrieval (such as the modification time) and is measurably cheaper for append-heavy workloads. Neither says anything about ordering between different files, and neither is transitive.

Applications get this wrong constantly, and the failures were catalogued systematically. A 2014 study from a group at Wisconsin built a tool that explores the crash states reachable from a recorded I/O trace and found protocol violations in widely used software, including databases and version control systems, that assumed atomic renames, ordered writes across files, or that a single write smaller than a block is atomic. Two rules fall out. First, assume nothing is ordered unless an fsync separates it. Second, check the return value. Before Linux 4.13, an I/O error during writeback could be reported to whichever descriptor happened to call fsync first and then cleared, so a second fsync would return success on data that was never written. That behavior caused a well-publicized round of fixes in database engines in 2018 and led to the current error-sequence mechanism, which reports the error to every descriptor open at the time of the failure. A failed fsync is not retryable in general. The dirty pages have been dropped or marked clean, and the correct response is to treat the process's view of the file as invalid.

Storage and I/O through the block layer, devices, and queues

Below the file system sits the block layer, whose unit is the bio, a description of a transfer as a list of memory segments plus a device offset. Bios are merged (adjacent requests combined), sorted, and dispatched to a driver. The original design had one request queue per device with one lock, which was correct when the device could do 200 operations per second and absurd when it could do a million. The queue lock became the bottleneck before the device did. The multi-queue rewrite splits this into per-CPU software staging queues and a set of hardware dispatch queues matching the device's own queue pairs, so that in the common case no two cores touch the same lock or the same cache line on the I/O path.

I/O schedulers live between the two. On a rotating disk the scheduler's job was seek reduction, and elevator algorithms (SCAN, C-SCAN, and Linux's deadline variants) were worth large factors. On flash they mostly are not, which is why none is the default for NVMe and why this machine reports [none] mq-deadline for its virtual disks. mq-deadline remains useful for guaranteeing that reads are not starved by a flood of writes. BFQ provides proportional fairness between processes and costs enough CPU to matter at high IOPS, and Kyber targets tail latency by throttling depth. The general rule is that scheduling helps when the device is slower than the software and hurts when it is faster.

The hardware difference is worth quantifying because it drives every layout decision above it. Take a 7,200 rpm disk with a 4.2 ms average seek and 200 MB/s of media transfer rate. Average rotational latency is half a revolution, \( 60{,}000/7200/2 = 4.17 \) ms. A random 4 KiB read costs \( 4.2 + 4.17 + 0.02 = 8.39 \) ms, an effective rate of 0.49 MB/s, roughly 0.25% of the drive's streaming bandwidth. A random 1 MiB read costs \( 4.2 + 4.17 + 5.24 = 13.6 \) ms, an effective 77 MB/s. Positioning dominates until the transfer is megabytes, which is the entire justification for cylinder groups, for large blocks, for readahead, and for log-structured designs.

An SSD has no arm and a different pathology. Flash is read and written in pages (4 to 16 KiB) but erased only in blocks of hundreds of pages, and a page cannot be rewritten without erasing its block. The flash translation layer therefore writes updates to fresh pages and keeps a mapping table, and a garbage collector must eventually reclaim blocks by copying out the pages that are still valid. If a candidate block of 1024 pages holds \( v \) valid pages, reclaiming it costs \( v \) page writes and yields \( 1024 - v \) free pages, so the write amplification is

At \( v = 512 \) that is 2.0, at \( v = 900 \) it is 8.26, and at \( v = 1000 \) it is 42.7. Amplification explodes as the drive fills, which is why drives overprovision (a "512 GB" drive containing 512 GiB of flash keeps about 7% hidden) and why enterprise drives reserve far more. It is also why TRIM matters. Without it the drive believes deleted data is still valid and copies it forever. The application-level consequence is direct. Small random overwrites are the workload that destroys both endurance and throughput, and the fix is the same one file systems adopted, namely batch writes into large sequential units.

NVMe is the interface built for that device. Instead of one command queue behind a host bus adapter, it exposes up to 64K submission/completion queue pairs of up to 64K entries, so each core can own a queue pair with no shared lock, and interrupts are steered per queue with MSI-X. The protocol has a handful of mandatory commands and no translation to a decades-old bus protocol. Combined with the multi-queue block layer, the path from a thread to the device can be lock-free end to end.

Data movement itself is done by DMA. The driver hands the device a physical address (or an IOMMU-translated one) and the device reads or writes memory directly, raising an interrupt on completion. Two details bite in practice. The buffer must be physically contiguous or described by a scatter-gather list, which is why the kernel has a DMA mapping API and why user pages must be pinned before a device can touch them, since a page being written by a device cannot be swapped, migrated, or made copy-on-write. And an IOMMU sits between the device and memory, translating and restricting device addresses, which is what makes it safe to hand a device to a virtual machine or a user-space driver.

Interrupts versus polling is the same tradeoff as spinning versus sleeping, one level down. An interrupt is efficient when events are rare and wasteful when they are frequent, because each one costs an entry, a handler, and a return, and at high rates a machine can enter receive livelock where it spends all its time in interrupt handlers and never runs the code that would drain the queues. NAPI is the canonical fix. On the first packet interrupt the driver disables further interrupts for that queue and schedules a poll, the poll drains up to a budget of packets in one pass, and interrupts are re-enabled only when the queue is found empty. The system therefore behaves like an interrupt-driven system at low load (good latency, no wasted cycles) and a polling system at high load (good throughput, bounded overhead), with no tuning knob deciding which. Storage has the same idea in io_poll, where a thread submitting to a very fast device spins on the completion queue rather than paying for an interrupt and a wakeup.

io_uring, moving the interface out of the syscall

io_uring attacks the crossing cost directly by putting the interface in memory shared between the application and the kernel. Two ring buffers are mapped, a submission queue of descriptors and a completion queue of results, each with a head and tail index that the two sides update with release stores and acquire loads. Submitting an operation means writing a submission entry and advancing the tail. One io_uring_enter can then submit an arbitrary number of them and optionally wait for completions, so the number of ring transitions is decoupled from the number of operations. With IORING_SETUP_SQPOLL a kernel thread polls the submission queue and the count drops to zero in steady state.

   application                shared memory                kernel
   -----------                -------------                ------
   fill SQE[i]  ------------>  [ SQE array ]
   sq_tail++    ------------>  [ SQ ring: head, tail ]  --> io_uring_enter
                                                            (or SQPOLL thread
                                                             notices the tail)
                                                        submits to the block
                                                        or network stack
                               [ CQ ring: head, tail ]  <-- completion posted
   read CQE, cq_head++  <-----  [ CQE array ]

   N operations, 1 (or 0) ring transitions instead of N.

The measured effect separates two things that are often conflated. On warm random 4 KiB reads served entirely from the page cache, a pread loop takes 851 ns per read and io_uring at queue depth 64 takes 790 ns, a gain of only 8%. When the operation is cheap and synchronous, batching saves the syscall but the work still happens inline and serially. On cold reads that reach the device, the same comparison is 26.7 µs against 6.60 µs, a factor of 4.0, or 37.4 against 151.4 thousand operations per second. The gain there is not syscall amortization at all. It is queue depth. A blocking pread has one request outstanding, so throughput is one over the latency, while the ring keeps 64 in flight and the device pipelines them. That distinction is the single most useful thing to know about asynchronous I/O interfaces. They buy concurrency first and syscall amortization second.

Virtualization by trap-and-emulate, and why x86 needed help

A hypervisor multiplexes the machine among operating systems, which is the same problem one level down and with a harder constraint, since the guest kernel expects to execute privileged instructions. Popek and Goldberg's 1974 criterion states the requirement precisely. An architecture is classically virtualizable if every sensitive instruction (one whose behavior depends on, or changes, the privilege or resource configuration) is privileged (traps when executed outside supervisor mode). Then the hypervisor can run the guest directly at low privilege and emulate each trap. That is trap-and-emulate, with native speed for ordinary instructions.

x86 famously failed this test. Roughly a dozen and a half instructions were sensitive but not privileged. The standard example is POPF, which silently ignores the attempt to change the interrupt flag in user mode instead of trapping, so a guest kernel disabling interrupts would simply have no effect and no way to notice. The two answers were binary translation (scan the guest's kernel code, rewrite the problematic instructions into calls into the hypervisor, cache the translations) and paravirtualization (modify the guest to call the hypervisor deliberately through a hypercall interface), the approach Xen took in 2003 with very low overhead at the cost of requiring a ported guest. Hardware support arrived as VT-x and AMD-V, adding a root mode for the hypervisor and a non-root mode for the guest, with a control structure describing which events exit to the hypervisor. A 2006 comparison from the VMware group made an unpopular point that turned out to be important. First-generation hardware virtualization was often slower than a good binary translator, because a VM exit cost thousands of cycles and the hardware path took an exit where the translator had inlined the fast case. The lesson generalizes to any hardware/software offload argument.

Memory is the harder half. The guest maintains its own page tables mapping guest-virtual to guest-physical addresses, and the hypervisor must map guest-physical to host-physical. Shadow page tables did this in software. The hypervisor built a combined table and write-protected the guest's tables so it could intercept updates, which was correct and expensive. Nested paging (EPT on Intel, NPT on AMD) puts the second translation in hardware, and the cost moves to the page walk. A guest walk of a four-level table requires the hardware to translate each of the four guest-physical table addresses through the four-level nested table, plus the final address, so the worst case is

instead of four. This is the two-dimensional page walk. The mitigations are exactly the ones a bare-metal system uses, more urgently, huge pages in both dimensions (which cut the walk depth on both axes), and larger page-walk caches. It is also why a memory-intensive workload in a virtual machine can show a translation overhead that no profiler attributes to any instruction.

Hypervisors come in two shapes. Type 1 runs on the bare metal (Xen, ESXi, Hyper-V's root design), while type 2 runs inside a host operating system (VirtualBox, and arguably KVM, which turns Linux itself into the hypervisor by adding a mode to it). The modern trend is toward minimal device models. Rather than emulating a full PC, expose virtio queues (shared-memory rings, the same idea as io_uring) and keep the device model tiny to shrink the attack surface. Firecracker is the extreme point, a virtual machine monitor of a few tens of thousands of lines of Rust supporting a handful of virtio devices, booting in tens of milliseconds, built for running untrusted functions at high density.

Containers, one kernel with restricted views

A container is not a lightweight virtual machine. It is a set of ordinary processes on the host kernel, with three separate mechanisms applied.

Namespaces restrict what a process can see. Each namespace type virtualizes one global resource, mount (the file system tree), pid (process numbers), net (interfaces, ports, routing tables), uts (hostname), ipc (System V and POSIX IPC), user (uid and gid mappings, including the ability to be root inside without being root outside), cgroup (the visible cgroup root), and time (boot and monotonic offsets). They are created by clone or unshare flags and joined with setns. The effect is directly demonstrable. Running unshare -Ur --pid --fork --mount-proc ps -e on this machine prints exactly one process, PID 1, which is ps itself. Nothing was virtualized. The same kernel is simply refusing to show the rest.

cgroups restrict what a process can consume. The v2 unified hierarchy places every process in exactly one cgroup and attaches controllers to it, cpu.weight (the same weight arithmetic as the scheduler, one level up), cpu.max as a quota and period pair (so 200000 100000 means two CPUs' worth of runtime per 100 ms period), memory.max as a hard limit that triggers reclaim and then the OOM killer inside the cgroup, memory.high as a throttling threshold that slows the offender rather than killing it, io.max for device bandwidth and IOPS, plus pids.max. The v2 accounting model fixed the main v1 problem, which was that memory and I/O were in separate hierarchies and therefore could not be attributed to the same entity. Writeback I/O caused by a cgroup's dirty pages happens long after the write, in a kernel thread, and only a unified hierarchy can charge it correctly. Pressure stall information (/sys/fs/cgroup/.../cpu.pressure and friends) reports the fraction of time tasks were stalled on each resource, which is a far better signal for autoscaling than utilization.

A layered file system supplies the image. OverlayFS composes read-only lower layers with a writable upper layer. A read finds the topmost version of a file, and a write copies the file up into the writable layer first. That is copy-on-write at file granularity, with the consequence that modifying one byte of a 10 GiB file inside a container copies 10 GiB.

The security consequence of "one kernel" is the whole story. Every container on a host shares one kernel, so the attack surface is the entire system-call interface, roughly 350 calls plus ioctls, and a single kernel vulnerability is a container escape. A virtual machine has a much narrower interface (the virtual hardware plus the hypercall surface), which is why multi-tenant platforms either run a VM per tenant or interpose something. gVisor takes the second route, implementing a substantial portion of the Linux system call interface in a user-space kernel written in Go, so the host kernel sees only a small, tightly filtered set of calls from the sandbox. Kata Containers takes the first, running each pod in a lightweight virtual machine while preserving the container interface. Both are responses to the same observation, that namespaces were designed for isolation between cooperating workloads, not against hostile ones.

Kernel structure, from monolithic and micro to modules and eBPF

A monolithic kernel runs all its services (file systems, drivers, network stack) in one address space at supervisor privilege, so a call between subsystems is a function call. A microkernel keeps only address spaces, threads and IPC in the kernel and moves the rest into user-space servers, so a file operation becomes a message to a file server. The microkernel argument is fault isolation and evolvability. A driver bug crashes a server rather than the machine, and services can be replaced or restarted independently. The monolithic argument was performance, and in the Mach era the numbers supported it, since a message round trip cost far more than a function call.

The interesting historical wrinkle is that the performance argument was substantially demolished and the outcome did not change. Liedtke's L4 work in the mid-1990s showed that IPC costs were an artifact of implementation rather than of the architecture, cutting round-trip costs by more than an order of magnitude relative to Mach through careful design (registers instead of memory for small messages, avoiding cache and TLB pollution, making the fast path a few hundred instructions). Microkernels then went on to succeed comprehensively in the places where the isolation argument is decisive, such as seL4, with a machine-checked proof of functional correctness from a group in Australia, and QNX and its relatives in safety-critical embedded systems. General-purpose desktops and servers stayed monolithic, mostly for reasons of momentum, driver ecosystems, and the fact that a monolithic kernel with loadable modules recovers much of the practical modularity without paying for address-space crossings.

Loadable modules are the compromise, code compiled against the kernel's internal interfaces and loaded at runtime into the kernel address space. They give configurability and independent distribution, and they give nothing at all in the way of isolation, since a module is kernel code with kernel privileges.

eBPF is the modern answer to the question modules answer badly, how to extend the kernel safely. A program is written in a restricted C dialect, compiled to a small RISC-like bytecode, and loaded through a verifier before being attached to a hook (a tracepoint, a kprobe, a network path, a cgroup operation, a scheduler hook). The verifier is the interesting part. It performs symbolic execution over all paths of the program's control-flow graph, tracking for every register an abstract value (a type, a known constant, a range) so that it can prove memory safety statically. Every pointer dereference is within the bounds of a known object, every map access is checked, every helper call has arguments of the right types. It requires the program to terminate, originally by rejecting all loops and since 5.3 by requiring bounded loops it can prove terminating. It caps complexity, currently at one million verified instructions. Programs that pass are JIT-compiled to native code and run in kernel context at kernel speed.

The result is a genuinely new capability, production-safe, programmable observability and policy inside the kernel, without a module, without a reboot, and without the ability to crash the machine. It is now the substrate for tracing (the bcc and bpftrace tool collections), for high-performance networking (XDP handles packets before the stack, Cilium implements service routing and policy this way), for security policy (LSM hooks in BPF), and, since 6.12, for pluggable scheduling policies through sched_ext, which lets a scheduler be written and loaded as a BPF program. That last one closes a long loop. The scheduling policy debate that produced O(1), CFS and EEVDF can now be settled empirically per workload rather than globally per kernel version.

Unikernels sit at the other extreme. Link the application with just the library operating system functions it uses, producing a single-address-space image that boots on a hypervisor in milliseconds. MirageOS, from a group at Cambridge, demonstrated the idea in OCaml with images measured in megabytes. The security argument is a tiny attack surface and no shell to exploit, while the practical objection is debuggability and the loss of every operational tool that assumes a UNIX. The ideas that survived are visible in Firecracker-style minimal guests and in library operating systems used for specific services rather than as a general model.

Security, from privilege separation and capabilities to the attack surface

The classical UNIX model is coarse. Root can do everything, and everyone else is checked against file permissions. Two refinements matter. Privilege separation splits a program into a small privileged part and a large unprivileged one that does the parsing and talking to the network, communicating over a pipe, so that a bug in the large part yields nothing. OpenSSH's design is the standard reference implementation of the pattern. Capabilities in the POSIX sense split root into about forty independently grantable powers (CAP_NET_BIND_SERVICE, CAP_SYS_ADMIN, CAP_DAC_OVERRIDE, ...), so a web server can bind port 80 without being able to load a kernel module. The idea is older and deeper than the POSIX version, going back to capability systems where a capability is an unforgeable reference that both names an object and conveys the right to use it. That lineage runs from the 1970s research systems through seL4 and, in hardware, through the CHERI work at Cambridge, which puts capabilities in the pointer representation itself.

seccomp restricts which system calls a process may make at all, using a classic-BPF filter over the call number and argument registers, with the filter installed irrevocably and inherited across fork and exec. It is what container runtimes use to shrink the shared-kernel attack surface from 350-odd calls to a few dozen. Its cost is small and measurable. On this machine, adding one filter raises the cost of a raw getpid from 133.5 ns to 144.5 ns, about 11 ns or 8%, and stacking a second filter of 130 instructions on top adds essentially nothing more (144.0 ns), because filters are JIT compiled and the added comparisons are perfectly predicted. Paying 8% on the syscall path to remove most of the kernel's attack surface is one of the better trades available.

ASLR randomizes the base addresses of the stack, the heap, the mmap region and, for position-independent executables, the program itself, so that an attacker who can corrupt memory cannot predict where to jump. Its strength is the number of random bits, which on 64-bit systems is large enough to matter but is undermined by any information leak, and it composes with non-executable stacks, stack canaries and control-flow integrity rather than replacing them. The kernel randomizes its own layout too (KASLR), which is exactly what the speculative-execution attacks of 2018 broke, since Meltdown allowed reading kernel memory from user space and thereby derandomized everything. Kernel page-table isolation, the fix, is the reason the syscall costs measured on this page are what they are. It is a permanent tax paid on every crossing to compensate for a hardware flaw.

The strategic point is that the kernel's attack surface is enormous and shared. Every system call, every ioctl, every parsing path for a file system or network protocol is reachable from unprivileged code, and the historical rate of exploitable bugs is not zero. That is why the defenses stack. Reduce what is reachable (seccomp, namespaces), reduce what a compromise grants (capabilities, user namespaces, privilege separation), make exploitation harder (ASLR, CFI, hardened allocators), and, when the tenant is genuinely hostile, put a different boundary around it (a virtual machine, or a user-space kernel).

Worked problems

Implementation

Everything below was compiled and run on the machine described in the measurement table. C is the natural language here because the subject is the interface between a program and a kernel written in C. Rust appears where it illuminates a structure (the fast-path and slow-path split of a lock, the shape of a replacement policy) and Python where the job is measurement or simulation rather than system programming. The numbers quoted in the theory sections come from exactly these programs, and the excerpts below are taken verbatim from files that were compiled and run.

What a kernel crossing costs

The first program compares a non-inlined function call against the cheapest real system call. Three details make the difference between a measurement and a number. The call goes through a volatile function pointer so the compiler cannot inline or hoist it, the process is pinned so migration does not add noise, and syscall(SYS_getpid) is used rather than getpid() so that no library caching can intervene. The Python version measures the same thing through ctypes and is instructive for a different reason. It shows the interpreter overhead sitting on top of the syscall.

// What a ring transition costs, measured against a plain call.
// gcc -O2 -o snip_syscall snip_syscall.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <unistd.h>
#include <sched.h>
#include <sys/syscall.h>

static inline uint64_t now_ns(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);          // served by the vDSO
    return (uint64_t)ts.tv_sec * 1000000000ull + ts.tv_nsec;
}

// A volatile function pointer defeats inlining, so this is a real call/ret.
long __attribute__((noinline)) plain_call(long x) { return x + 1; }
static long (*volatile call_ptr)(long) = plain_call;

int main(void) {
    cpu_set_t set;                                 // pin: migration adds noise
    CPU_ZERO(&set); CPU_SET(3, &set);
    sched_setaffinity(0, sizeof set, &set);

    const long N = 3000000;
    long sink = 0;

    for (long i = 0; i < N / 10; i++) sink += call_ptr(i);       // warm i-cache
    uint64_t t0 = now_ns();
    for (long i = 0; i < N; i++) sink += call_ptr(i);
    uint64_t t1 = now_ns();
    double call_ns = (double)(t1 - t0) / N;

    // syscall(SYS_getpid) is the cheapest real trap available: the kernel does
    // essentially nothing, so this measures entry plus exit, not kernel work.
    for (long i = 0; i < N / 100; i++) sink += syscall(SYS_getpid);
    t0 = now_ns();
    for (long i = 0; i < N; i++) sink += syscall(SYS_getpid);
    t1 = now_ns();
    double sys_ns = (double)(t1 - t0) / N;

    printf("call %.2f ns, syscall %.2f ns, ratio %.0fx (sink=%ld)\n",
           call_ns, sys_ns, sys_ns / call_ns, sink);
    return 0;
}

"""Python measurement harness for the same question.

ctypes.CDLL(None).syscall lets a raw syscall be issued with no libc caching in
the way, so the number is comparable to the C loop.
"""
import ctypes
import statistics
import time

libc = ctypes.CDLL(None, use_errno=True)
libc.syscall.restype = ctypes.c_long
SYS_getpid = 39                       # x86-64; see asm/unistd_64.h


def timed(fn, n):
    """Median ns/op over 7 trials, so a stray preemption cannot dominate."""
    trials = []
    for _ in range(7):
        t0 = time.perf_counter_ns()
        fn(n)
        t1 = time.perf_counter_ns()
        trials.append((t1 - t0) / n)
    return statistics.median(trials)


def py_call(n, _f=lambda x: x + 1):
    s = 0
    for i in range(n):
        s += _f(i)
    return s


def raw_syscall(n, _s=libc.syscall, _nr=SYS_getpid):
    s = 0
    for _ in range(n):
        s += _s(_nr)
    return s
# ...
if __name__ == "__main__":
    n = 200000
    print(f"python function call : {timed(py_call, n):8.1f} ns")
    print(f"raw getpid syscall   : {timed(raw_syscall, n):8.1f} ns")
    print(f"ctypes time(NULL)    : {timed(ctypes_overhead, n):8.1f} ns")

Output on this machine is call 1.35 ns, syscall 137.05 ns, ratio 102x from the C version, and from the Python version a 73.8 ns interpreted function call, 339.5 ns for the raw syscall through ctypes, and 180.9 ns for a ctypes call to time(NULL). The last two together say that roughly 180 ns of the 339 ns is the foreign function interface rather than the kernel, which is the sort of thing a measurement harness has to isolate before its numbers mean anything.

Context switches, by making them unavoidable

The ping-pong below pins both peers to one logical CPU, so each round trip forces two switches, and runs the identical experiment between two processes and between two threads of one process. The difference between those two numbers is the cost of changing address spaces, everything else being equal.

// Context-switch cost by pipe ping-pong, processes versus threads.
// Both peers are pinned to the SAME logical CPU, so a message cannot be
// delivered without descheduling the sender and scheduling the receiver:
// one round trip is exactly two context switches.
// gcc -O2 -pthread -o snip_pingpong snip_pingpong.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
/* ... */
static int a2b[2], b2a[2];

static void echo_loop(int cpu) {
    pin(cpu);
    char c;
    for (int i = 0; i < ROUNDS; i++) {
        if (read(a2b[0], &c, 1) != 1) return;
        if (write(b2a[1], &c, 1) != 1) return;
    }
}
static void *thread_side(void *arg) { echo_loop(*(int *)arg); return NULL; }

static double drive(int cpu) {
    pin(cpu);
    char c = 'x';
    for (int i = 0; i < WARM; i++) {
        if (write(a2b[1], &c, 1) != 1 || read(b2a[0], &c, 1) != 1) return -1;
    }
    uint64_t t0 = now_ns();
    for (int i = WARM; i < ROUNDS; i++) {
        if (write(a2b[1], &c, 1) != 1 || read(b2a[0], &c, 1) != 1) return -1;
    }
    return (double)(now_ns() - t0) / (ROUNDS - WARM);
}

int main(void) {
    int cpu = 3;
    if (pipe(a2b) || pipe(b2a)) return 1;
    pid_t pid = fork();
    if (pid == 0) { echo_loop(cpu); _exit(0); }
    double proc_rt = drive(cpu);
    waitpid(pid, NULL, 0);
    close(a2b[0]); close(a2b[1]); close(b2a[0]); close(b2a[1]);

    if (pipe(a2b) || pipe(b2a)) return 1;
    pthread_t th;
    pthread_create(&th, NULL, thread_side, &cpu);
    double thr_rt = drive(cpu);
    pthread_join(th, NULL);
    close(a2b[0]); close(a2b[1]); close(b2a[0]); close(b2a[1]);

    printf("process round trip %.0f ns -> %.0f ns per switch\n", proc_rt, proc_rt / 2);
    printf("thread  round trip %.0f ns -> %.0f ns per switch\n", thr_rt, thr_rt / 2);
    printf("address-space change costs %.0f ns of that, %.1f%%\n",
           (proc_rt - thr_rt) / 2, 100.0 * (proc_rt - thr_rt) / thr_rt);
    return 0;
}

The output is process round trip 3719 ns -> 1860 ns per switch; thread round trip 3491 ns -> 1746 ns per switch; address-space change costs 114 ns of that, 6.5%. Running the same binary with the two peers on different cores gives roughly 16 µs per round trip, which measures inter-processor wakeup and cache-line transfer rather than switching, and is a good reminder to check what an experiment is actually exercising.

fork, copy-on-write, and demand paging

The next program sweeps resident set size and separates two costs that are usually conflated, the page-table duplication paid at fork and the per-page copy paid later, on the first write. Transparent huge pages are disabled for the region so the page-table work is visible rather than divided by 512.

// fork() cost against resident size, and the price of the COW faults after it.
// gcc -O2 -o snip_fork snip_fork.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
/* ... */
int main(void) {
    size_t sizes[] = { 1ul<<20, 16ul<<20, 128ul<<20, 512ul<<20 };
    for (int s = 0; s < 4; s++) {
        size_t bytes = sizes[s], pages = bytes / PAGE;
        char *m = mmap(NULL, bytes, PROT_READ|PROT_WRITE,
                       MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
        madvise(m, bytes, MADV_NOHUGEPAGE);        // force 4 KiB PTEs
        for (size_t i = 0; i < pages; i++) m[i * PAGE] = 1;   // make resident

        // (a) fork alone. The child exits at once, so the only work is building
        //     the child's page tables and marking both sides read-only.
        int reps = 20;
        uint64_t acc = 0;
        for (int r = 0; r < reps; r++) {
            uint64_t t0 = now_ns();
            pid_t pid = fork();
            if (pid == 0) _exit(0);
            acc += now_ns() - t0;                  // time the parent's return
            waitpid(pid, NULL, 0);
        }
        double fork_us = (double)acc / reps / 1000.0;

        // (b) the child writes one byte per inherited page: one write-protection
        //     fault, one page allocation and one 4 KiB copy each.
        int fds[2];
        if (pipe(fds)) return 1;
        pid_t pid = fork();
        if (pid == 0) {
            uint64_t t0 = now_ns();
            for (size_t i = 0; i < pages; i++) m[i * PAGE] ^= 1;
            double per = (double)(now_ns() - t0) / pages;
            ssize_t w = write(fds[1], &per, sizeof per); (void)w;
            _exit(0);
        }
        double cow = 0;
        ssize_t r = read(fds[0], &cow, sizeof cow); (void)r;
        waitpid(pid, NULL, 0);
        close(fds[0]); close(fds[1]);

        printf("%6zu MiB (%7zu pages): fork %8.1f us (%5.1f ns/page), "
               "COW fault %.0f ns\n",
               bytes >> 20, pages, fork_us, fork_us * 1000.0 / pages, cow);
        munmap(m, bytes);
    }
    return 0;
}

The companion program measures demand paging directly, covering the first touch of every page in a fresh anonymous mapping, the same stores once the mappings exist, MAP_POPULATE, transparent huge pages, and a dependent pointer chase that isolates translation cost from data cost.

// Demand paging costs: minor faults, MAP_POPULATE, huge pages, and the TLB.
// gcc -O2 -o snip_faults snip_faults.c
#define _GNU_SOURCE
#include <stdio.h>
/* ... */
int main(void) {
    cpu_set_t s; CPU_ZERO(&s); CPU_SET(3, &s); sched_setaffinity(0, sizeof s, &s);
    prctl(PR_SET_THP_DISABLE, 0, 0, 0, 0);      // clear an inherited disable bit
    size_t pages = SIZE / PAGE;

    // 1. demand-zero anonymous memory: one minor fault per 4 KiB page
    char *m = mmap(NULL, SIZE, PROT_READ|PROT_WRITE,
                   MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    madvise(m, SIZE, MADV_NOHUGEPAGE);
    long f0 = minflt(); uint64_t t0 = now_ns();
    for (size_t i = 0; i < pages; i++) m[i * PAGE] = 1;
    uint64_t t1 = now_ns(); long f1 = minflt();
    printf("4 KiB first touch : %6.0f ns/page over %ld faults\n",
           (double)(t1 - t0) / pages, f1 - f0);

    // 2. the same stores once the PTEs exist: no fault, just a store
    t0 = now_ns();
    for (size_t i = 0; i < pages; i++) m[i * PAGE] = 2;
    t1 = now_ns();
    printf("already mapped    : %6.1f ns/page\n", (double)(t1 - t0) / pages);
    double base_chase = chase(m, pages);
    munmap(m, SIZE);

    // 3. MAP_POPULATE builds every PTE inside one syscall
    t0 = now_ns();
    m = mmap(NULL, SIZE, PROT_READ|PROT_WRITE,
             MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0);
    t1 = now_ns();
    printf("MAP_POPULATE      : %6.0f ns/page (one syscall, no user trap/page)\n",
           (double)(t1 - t0) / pages);
    munmap(m, SIZE);

    // 4. transparent huge pages: 512x fewer faults, but each zeroes 2 MiB
    char *raw = mmap(NULL, SIZE + (2ul<<20), PROT_READ|PROT_WRITE,
                     MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    m = (char *)(((uintptr_t)raw + (2ul<<20) - 1) & ~((uintptr_t)(2ul<<20) - 1));
    madvise(m, SIZE, MADV_HUGEPAGE);            // 2 MiB alignment is required
    f0 = minflt(); t0 = now_ns();
    for (size_t i = 0; i < pages; i++) m[i * PAGE] = 1;
    t1 = now_ns(); f1 = minflt();
    printf("2 MiB first touch : %6.1f ms total over %ld faults\n",
           (double)(t1 - t0) / 1e6, f1 - f0);
    double thp_chase = chase(m, pages);
    munmap(raw, SIZE + (2ul<<20));

    printf("random chase      : %.1f ns with 4 KiB pages, %.1f ns with 2 MiB "
           "pages (%.1f ns of page-walk saved)\n",
           base_chase, thp_chase, base_chase - thp_chase);
    return 0;
}

The output is 4 KiB first touch 1571 ns/page over 131075 faults; already mapped 22.5 ns/page; MAP_POPULATE 960 ns/page; 2 MiB first touch 74.1 ms total over 256 faults; random chase 129.9 ns with 4 KiB pages, 113.9 ns with 2 MiB pages. The fault count is read from getrusage rather than assumed, which is what makes the huge-page row trustworthy. 256 faults for 512 MiB is exactly one per 2 MiB, so the kernel really did use huge pages.

Page replacement and Belady's anomaly

FIFO, LRU, CLOCK and OPT on the same reference strings, with fault counts. The Python version additionally sweeps a trace with locality, a purely random trace, working-set sizes, and a scan over frame counts that finds every FIFO anomaly on a repeated string. The Rust version is the same four policies, and the two agree exactly on the canonical string.

"""Page replacement algorithms on real reference strings.

Implements FIFO, LRU, CLOCK (second chance), and OPT (Belady's optimal
lookahead policy), counts faults, and demonstrates Belady's anomaly.
Run: python3 pagerepl.py
"""
import json
import random
from collections import OrderedDict, deque
# ...
def fifo(refs, frames):
    resident, q, faults = set(), deque(), 0
    for p in refs:
        if p in resident:
            continue
        faults += 1
        if len(resident) == frames:
            victim = q.popleft()
            resident.discard(victim)
        resident.add(p)
        q.append(p)
    return faults


def lru(refs, frames):
    cache, faults = OrderedDict(), 0
    for p in refs:
        if p in cache:
            cache.move_to_end(p)          # most recently used at the tail
            continue
        faults += 1
        if len(cache) == frames:
            cache.popitem(last=False)     # evict the least recently used
        cache[p] = True
    return faults


def clock(refs, frames):
    """Second-chance: a circular scan over frames with one reference bit each.

    A hit sets the reference bit. A miss advances the hand, clearing set bits
    (giving those pages a second chance) until it finds a frame whose bit is
    already clear, and evicts that one.
    """
    slots = [None] * frames
    ref = [0] * frames
    where = {}
    hand, faults = 0, 0
    for p in refs:
        if p in where:
            ref[where[p]] = 1
            continue
        faults += 1
        while True:
            if slots[hand] is None:
                break
            if ref[hand] == 0:
                del where[slots[hand]]
                break
            ref[hand] = 0                 # second chance, keep scanning
            hand = (hand + 1) % frames
        slots[hand] = p
        ref[hand] = 1
        where[p] = hand
        hand = (hand + 1) % frames
    return faults


def opt(refs, frames):
    """Belady's MIN: evict the page whose next use is farthest in the future."""
    nxt = {}
    future = [None] * len(refs)
    for i in range(len(refs) - 1, -1, -1):
        future[i] = nxt.get(refs[i], float("inf"))
        nxt[refs[i]] = i
    resident, faults = set(), 0
    for i, p in enumerate(refs):
        if p in resident:
            continue
        faults += 1
        if len(resident) == frames:
            # recompute the next use of every resident page from position i
            def next_use(q):
                for j in range(i + 1, len(refs)):
                    if refs[j] == q:
                        return j
                return float("inf")
            victim = max(resident, key=next_use)
            resident.discard(victim)
        resident.add(p)
    return faults
# ...
if __name__ == "__main__":
    out = {}

    # 1. Belady's anomaly on the canonical string
    belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
    out["belady_string"] = belady
    out["belady_anomaly"] = {
        str(f): {"fifo": fifo(belady, f), "lru": lru(belady, f),
                 "clock": clock(belady, f), "opt": opt(belady, f)}
        for f in (3, 4, 5)
    }

    # 2. a longer trace with locality, swept over frame counts
    trace = locality_trace()
    out["locality_trace"] = {
        "length": len(trace), "distinct_pages": len(set(trace)),

// Page replacement policies and Belady's anomaly, standard library only.
// rustc -O snip_pagerepl.rs -o snip_pagerepl
use std::collections::{HashMap, VecDeque};

fn fifo(refs: &[u32], frames: usize) -> usize {
    let mut resident: Vec<u32> = Vec::new();
    let mut queue: VecDeque<u32> = VecDeque::new();
    let mut faults = 0;
    for &p in refs {
        if resident.contains(&p) {
            continue;
        }
        faults += 1;
        if resident.len() == frames {
            let victim = queue.pop_front().unwrap();
            resident.retain(|&x| x != victim);
        }
        resident.push(p);
        queue.push_back(p);
    }
    faults
}

fn lru(refs: &[u32], frames: usize) -> usize {
    let mut order: Vec<u32> = Vec::new(); // front = least recently used
    let mut faults = 0;
    for &p in refs {
        if let Some(i) = order.iter().position(|&x| x == p) {
            let v = order.remove(i);
            order.push(v);
            continue;
        }
        faults += 1;
        if order.len() == frames {
            order.remove(0);
        }
        order.push(p);
    }
    faults
}

// Second chance: a circular hand over the frames, one reference bit each.
// ...
fn opt(refs: &[u32], frames: usize) -> usize {
    let mut resident: Vec<u32> = Vec::new();
    let mut faults = 0;
    for i in 0..refs.len() {
        let p = refs[i];
        if resident.contains(&p) {
            continue;
        }
        faults += 1;
        if resident.len() == frames {
            let next_use = |q: u32| -> usize {
                refs[i + 1..].iter().position(|&x| x == q).map_or(usize::MAX, |k| k)
            };
            let victim = *resident.iter().max_by_key(|&&q| next_use(q)).unwrap();
            resident.retain(|&x| x != victim);
        }
        resident.push(p);
    }
    faults
}

fn main() {
    let s: Vec<u32> = vec![1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];
    println!("frames  fifo  lru  clock  opt");
    for f in 3..=5 {
        println!("{:>6}  {:>4}  {:>3}  {:>5}  {:>3}",
                 f, fifo(&s, f), lru(&s, f), clock(&s, f), opt(&s, f));
    }
    let a3 = fifo(&s, 3);
    let a4 = fifo(&s, 4);
    println!("Belady's anomaly: FIFO takes {} faults with 3 frames and {} with 4",
             a3, a4);
    assert!(a4 > a3);
}

Weighted fair scheduling, CFS and EEVDF side by side

The simulator implements both policies over the same task set using the kernel's actual weight table, so the difference between "always run the minimum virtual runtime" and "among eligible tasks run the earliest virtual deadline" is visible rather than described. It also computes lag, which is the quantity EEVDF bounds and CFS does not.

"""Weighted fair scheduling: CFS virtual runtime and EEVDF lag/deadline.

Both policies are simulated on the same task set so the difference in what they
optimise is visible: CFS always runs the minimum-vruntime task, EEVDF runs the
eligible task with the earliest virtual deadline.
"""
from dataclasses import dataclass, field

# kernel/sched/core.c, sched_prio_to_weight[]: nice 0..19 (nice -20 is 88761)
NICE_TO_WEIGHT = [1024, 820, 655, 526, 423, 335, 272, 215, 172, 137,
                  110, 87, 70, 56, 45, 36, 29, 23, 18, 15]
NICE_0_LOAD = 1024


@dataclass
class Task:
    name: str
    nice: int = 0
    vruntime: float = 0.0        # service received, scaled to nice-0 units
    service: float = 0.0         # real CPU time received, ms
    slice_ms: float = 3.0        # request size (EEVDF); base slice in CFS
    deadline: float = 0.0
    history: list = field(default_factory=list)

    @property
    def weight(self):
        return NICE_TO_WEIGHT[self.nice]


def cfs(tasks, total_ms, sched_latency=24.0, tick=1.0):
    """Run min-vruntime for `total_ms`. A task's slice is latency*w/W and its
    vruntime advances by delta*1024/w, so equal vruntime means weighted-equal
    service."""
    t = 0.0
    while t < total_ms:
        W = sum(x.weight for x in tasks)
        cur = min(tasks, key=lambda x: (x.vruntime, x.name))
        slice_ms = sched_latency * cur.weight / W
        run = min(slice_ms, total_ms - t)
        cur.service += run
        cur.vruntime += run * NICE_0_LOAD / cur.weight
        cur.history.append((round(t, 3), cur.name, round(run, 3)))
        t += run
    return tasks


def eevdf(tasks, total_ms):
    """Virtual time V advances at 1/W per unit of real service. A task is
    eligible when its vruntime is at most V (equivalently, lag >= 0); among the
    eligible it runs the earliest virtual deadline, ve + slice*1024/w."""
    t, V = 0.0, 0.0
    trace = []
    while t < total_ms:
        W = sum(x.weight for x in tasks)
        for x in tasks:
            x.deadline = x.vruntime + x.slice_ms * NICE_0_LOAD / x.weight
        eligible = [x for x in tasks if x.vruntime <= V + 1e-9]
        if not eligible:                       # V has not caught up yet
            eligible = tasks
        cur = min(eligible, key=lambda x: (x.deadline, x.name))
        run = min(cur.slice_ms, total_ms - t)
        cur.service += run
        cur.vruntime += run * NICE_0_LOAD / cur.weight
        V += run * NICE_0_LOAD / W             # same units as vruntime
        t += run
        trace.append((round(t, 2), cur.name, round(V, 3)))
    return tasks, trace


def lag(tasks, total_ms):
    W = sum(x.weight for x in tasks)
    return {x.name: round(total_ms * x.weight / W - x.service, 3) for x in tasks}

Over 120 ms with two nice-0 tasks and one nice-5 task, CFS delivers shares 0.4297 / 0.4297 / 0.1406, exactly the weight ratios, and EEVDF delivers 0.4250 / 0.4250 / 0.1500 with lags of +0.565, +0.565 and −1.131 ms summing to zero, the same fairness, with the instantaneous error explicitly bounded and reported. The third experiment gives one task a 1 ms request and another a 12 ms request. Both still receive half the processor, but the short-slice task runs far more often, which is the property CFS could not express.

A futex mutex whose fast path never enters the kernel

The three-state futex mutex is the canonical demonstration that synchronization does not have to be a system call. The C version counts its own futex calls, and the Rust version builds the same fast-path/slow-path split with only the standard library, using park and unpark in place of the futex syscall, and counts how often the fast path failed.

// A futex mutex: uncontended lock and unlock never enter the kernel.
// States: 0 = free, 1 = held with no waiters, 2 = held and someone is waiting.
// gcc -O2 -pthread -o snip_futex snip_futex.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
#include <stdatomic.h>
#include <pthread.h>
#include <unistd.h>
#include <linux/futex.h>
#include <sys/syscall.h>

static atomic_int futex_calls = 0;

static int futex(_Atomic int *addr, int op, int val) {
    atomic_fetch_add_explicit(&futex_calls, 1, memory_order_relaxed);
    return (int)syscall(SYS_futex, (int *)addr, op | FUTEX_PRIVATE_FLAG,
                        val, NULL, NULL, 0);
}

typedef struct { _Atomic int state; } fmutex;

static void flock_(fmutex *m) {
    int c = 0;
    // Fast path: one uncontended compare-exchange, zero syscalls.
    if (atomic_compare_exchange_strong(&m->state, &c, 1)) return;
    // Slow path: announce that a waiter exists, then sleep on the word.
    if (c != 2) c = atomic_exchange(&m->state, 2);
    while (c != 0) {
        futex(&m->state, FUTEX_WAIT, 2);   // sleeps only if state is still 2
        c = atomic_exchange(&m->state, 2);
    }
}

static void funlock_(fmutex *m) {
    // If nobody ever registered as a waiter, the store alone finishes the job.
    if (atomic_fetch_sub(&m->state, 1) != 1) {
        atomic_store(&m->state, 0);
        futex(&m->state, FUTEX_WAKE, 1);
    }
}

static fmutex mu = { 0 };
static long counter = 0;
#define ITERS 200000

static void *worker(void *arg) {
    (void)arg;
    for (int i = 0; i < ITERS; i++) { flock_(&mu); counter++; funlock_(&mu); }
    return NULL;
}

// The same fast-path/slow-path split with only the standard library. Rust's
// std::sync::Mutex is a futex mutex on Linux; this spells the structure out
// using park/unpark as the sleeping mechanism instead of the futex syscall.
// rustc -O snip_futex.rs -o snip_futex
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use std::thread;

struct SpinPark {
    locked: AtomicBool,
    parked: Mutex<Vec<thread::Thread>>, // the wait queue the kernel would own
    slow: AtomicUsize,                  // how often the fast path failed
}

impl SpinPark {
    fn new() -> Self {
        SpinPark { locked: AtomicBool::new(false), parked: Mutex::new(Vec::new()),
                   slow: AtomicUsize::new(0) }
    }

    fn lock(&self) {
        // Fast path: one atomic swap, no kernel involvement at all.
        if self.locked.swap(true, Ordering::Acquire) == false {
            return;
        }
        self.slow.fetch_add(1, Ordering::Relaxed);
        // Slow path: spin briefly, because most holds are shorter than the cost
        // of sleeping and waking, then register and block.
        for _ in 0..64 {
            if self.locked.swap(true, Ordering::Acquire) == false {
                return;
            }
            std::hint::spin_loop();
        }
        loop {
            self.parked.lock().unwrap().push(thread::current());
            if self.locked.swap(true, Ordering::Acquire) == false {
                return;
            }
            thread::park();
        }
    }

    fn unlock(&self) {
        self.locked.store(false, Ordering::Release);
        if let Some(t) = self.parked.lock().unwrap().pop() {
            t.unpark();
        }
    }
}

The output from the C version is 1 thread: counter=200000 futex syscalls=0 and 8 threads: counter=1600000 futex syscalls=284471 (0.18 per acquisition). The Rust version reports 113,368 slow-path entries out of 400,000 acquisitions under the same eight-way contention. Both numbers say the same thing. An uncontended lock costs one atomic operation, and contention is what costs a crossing.

The page cache, cold and warm

Measuring a cold read without root is a matter of evicting only the file under test. posix_fadvise(POSIX_FADV_DONTNEED) drops this file's clean pages and leaves everyone else's alone, which /proc/sys/vm/drop_caches does not. Python exposes the call directly, so the whole harness is twenty lines.

"""Cold versus warm reads of the same file, without root.

posix_fadvise(POSIX_FADV_DONTNEED) drops just this file's clean pages from the
page cache, which is the honest way to measure a cold read on a shared machine:
/proc/sys/vm/drop_caches would evict everyone else's data too.
"""
import os
import time

PATH = "/tmp/pagecache_demo.bin"
SIZE = 512 << 20            # 512 MiB
CHUNK = 1 << 20


def make_file():
    buf = b"\xa5" * CHUNK
    with open(PATH, "wb") as f:
        for _ in range(SIZE // CHUNK):
            f.write(buf)
        f.flush()
        os.fsync(f.fileno())


def read_all(fd):
    os.lseek(fd, 0, os.SEEK_SET)
    n = 0
    t0 = time.perf_counter()
    while True:
        b = os.read(fd, CHUNK)
        if not b:
            break
        n += len(b)
    return n / (time.perf_counter() - t0) / 1e9      # GB/s


if __name__ == "__main__":
    make_file()
    fd = os.open(PATH, os.O_RDONLY)
    os.posix_fadvise(fd, 0, 0, os.POSIX_FADV_DONTNEED)
    cold = read_all(fd)                               # pages must come from disk
    warm = read_all(fd)                               # now every page is cached
    warm2 = read_all(fd)
    os.posix_fadvise(fd, 0, 0, os.POSIX_FADV_DONTNEED)
    cold2 = read_all(fd)
    os.close(fd)
    os.unlink(PATH)
    print(f"cold  {cold:6.2f} GB/s")
    print(f"warm  {warm:6.2f} GB/s   (again {warm2:6.2f} GB/s)")
    print(f"cold again after eviction {cold2:6.2f} GB/s")
    print(f"page cache is worth {warm / cold:.1f}x on this file")

Output on a 512 MiB file is 2.14 GB/s cold, 7.29 and 7.33 GB/s warm, 2.17 GB/s cold again after eviction. The C measurement over 2 GiB in the table below gives 2.28 and 9.02 GB/s. The gap between 7.3 and 9.0 is the interpreter allocating a fresh bytes object per read, which is exactly the kind of overhead a data loader pays and rarely accounts for.

io_uring against a synchronous loop

Written against the raw io_uring_setup and io_uring_enter system calls rather than liburing, so that the three mapped regions and the head/tail protocol are visible. The release store to the submission tail and the acquire load of the completion tail are the entire synchronization contract with the kernel.

// io_uring against the raw syscall interface, so every ring field is visible.
// The design point: submissions and completions live in memory shared with the
// kernel, so N operations cost one io_uring_enter, not N syscalls.
// gcc -O2 -o snip_uring snip_uring.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <time.h>
#include <sys/mman.h>
#include <sys/syscall.h>
#include <linux/io_uring.h>

#define QD  64                       // ring entries submitted per batch
#define BLK 4096                     // read size
#define FILESZ (512ull << 20)
/* ... */
static double uring_loop(struct ring *r, int fd, char *dst, int nops) {
    seed();
    uint64_t t0 = now_ns();
    int done = 0;
    while (done < nops) {
        unsigned tail = *r->sq_tail;
        for (int i = 0; i < QD; i++) {
            unsigned idx = tail & *r->sq_mask;
            struct io_uring_sqe *sqe = &r->sqes[idx];
            memset(sqe, 0, sizeof *sqe);
            sqe->opcode = IORING_OP_READ;
            sqe->fd     = fd;
            sqe->off    = next_off();
            sqe->addr   = (unsigned long long)(dst + (size_t)i * BLK);
            sqe->len    = BLK;
            sqe->user_data = i;
            r->sq_array[idx] = idx;
            tail++;
        }
        __atomic_store_n(r->sq_tail, tail, __ATOMIC_RELEASE);
        if (io_uring_enter_(r->fd, QD, QD, IORING_ENTER_GETEVENTS) < 0) {
            perror("io_uring_enter"); exit(1);
        }
        unsigned head = *r->cq_head;
        unsigned ctail = __atomic_load_n(r->cq_tail, __ATOMIC_ACQUIRE);
        while (head != ctail) {
            struct io_uring_cqe *cqe = &r->cqes[head & *r->cq_mask];
            if (cqe->res != BLK) { fprintf(stderr, "res=%d\n", cqe->res); exit(1); }
            head++; done++;
        }
        __atomic_store_n(r->cq_head, head, __ATOMIC_RELEASE);
    }
    return (double)(now_ns() - t0) / done;
}

The output is cold random 4 KiB reads at queue depth 64: 6.46 us each, 154.7 kIOPS, against 26.7 µs and 37.4 kIOPS for the equivalent pread loop at queue depth one.

Asking the running system

Finally, the commands that answer these questions in production without writing a program. Everything here reads /proc, /sys or a tracing interface. The perf lines are included for completeness and are refused on this machine, which sets perf_event_paranoid to 4.

# Counting what a program asks the kernel for. /bin/true makes 109 calls on
# this machine, 77 of which fail: the dynamic loader probing library paths.
strace -c -f /bin/true

# Which calls, in order, with timings. -T adds the time spent inside each.
strace -T -e trace=openat,mmap,read /bin/true

# Faults, switches and migrations for one command, when perf is permitted
# (this machine reports perf_event_paranoid=4, so these are refused here).
perf stat -e page-faults,minor-faults,major-faults,context-switches,cpu-migrations ./a.out
perf record -g ./a.out && perf report --stdio

# Per-process fault and I/O accounting without perf: /proc is always readable.
grep -E 'minflt|majflt' /proc/self/stat >/dev/null   # fields 10-13 of stat
cat /proc/self/status | grep -E 'VmRSS|VmSwap|Threads'
cat /proc/self/smaps_rollup | grep -E 'Rss|Pss|AnonHugePages'

# Which of a file's pages are actually in the page cache, and evicting them
# without root (POSIX_FADV_DONTNEED affects only this file).
python3 -c "import os,sys; fd=os.open(sys.argv[1],os.O_RDONLY); \
os.posix_fadvise(fd,0,0,os.POSIX_FADV_DONTNEED)" ./dataset.bin

# Scheduler and affinity: what the kernel thinks this task is allowed to use.
taskset -pc $$                      # current affinity mask
chrt -p $$                          # policy and priority
cat /proc/sys/kernel/sched_rt_runtime_us

# cgroup v2: where a process is accounted and what its limits are.
cat /proc/self/cgroup
cat /sys/fs/cgroup/cpu.max /sys/fs/cgroup/memory.max 2>/dev/null
cat /sys/fs/cgroup/cpu.pressure /sys/fs/cgroup/io.pressure 2>/dev/null

# Namespaces: a container is a view, not a machine. This prints one process.
unshare -Ur --pid --fork --mount-proc ps -e

# Block layer: queue depth, scheduler, and rotational flag as the kernel sees it.
cat /sys/block/vda/queue/scheduler /sys/block/vda/queue/nr_requests \
    /sys/block/vda/queue/rotational

# eBPF, when the tools are installed: syscall latency histograms, page faults
# by process, and block I/O latency, all without stopping the workload.
#   bpftrace -e 'tracepoint:raw_syscalls:sys_enter { @[comm] = count(); }'
#   bpftrace -e 'software:page-faults:1 { @[comm] = count(); }'
#   biolatency-bpfcc 1 10

How it is done in practice

The measurements, and the machine they came from

All numbers on this page were produced by the programs above on one machine, an Intel Xeon Platinum 8480+ (Sapphire Rapids), 26 cores and 52 logical CPUs on a single socket, 442 GiB of RAM, L1d 32 KiB and L2 4 MiB per core with 16 MiB of L3 visible, running Linux 6.8.0-1046-nvidia on Ubuntu 22.04 as a KVM guest, with gcc 11.4.0 at -O2, Python 3.10.12, ext4 on a virtio-blk device, one NUMA node visible, no swap configured, transparent huge pages set to madvise, and the EEVDF scheduler under a cgroup v2 unified hierarchy. It is a shared, multi-tenant virtual machine, so these are engineering numbers, not microarchitectural truth, medians of repeated runs, good to perhaps ten percent, and systematically pessimistic relative to bare metal wherever a VM exit is involved. The raw output is in classes/data/os.json.

Two things are deliberately absent. Hardware performance counters (perf stat) are unavailable on this machine, which sets perf_event_paranoid to 4, so no cycle-level attribution is reported. And NUMA effects could not be measured, since the guest sees a single NUMA node, so cross-node latency and bandwidth on this machine are unavailable rather than estimated.

What matters for machine-learning systems

The page cache decides whether a data loader is fast. The measurements above give the whole picture. A dataset that fits in cache is read at 9.0 GB/s with 1.0 µs random access, and one that does not is read at 2.3 GB/s with 47 µs random access, a 47× difference on the access pattern that matters for shuffled training. The practical rules follow directly. Check residency rather than guessing, since free -g and /proc/meminfo's Cached line say how much of the dataset is actually in memory. Prefer few large shards to many small files, because 16,000 images per second through a file-per-sample layout is 48,000 system calls per second before any data moves. Give the kernel the truth with posix_fadvise, where SEQUENTIAL doubles the readahead window, and DONTNEED behind a one-pass scan keeps it from evicting data that will be reused. And do not assume O_DIRECT is faster. It measured 2.11 GB/s here against 2.28 GB/s buffered on a cold read, because it gives up readahead and gains only the copy.

Pinned memory is a DMA requirement, not a tuning option. A GPU's DMA engine reads host memory by physical address, so a page it is copying cannot be swapped, migrated or made copy-on-write. Ordinary pageable memory therefore cannot be the source of an asynchronous transfer at all. The driver stages it through an internal pinned bounce buffer, one chunk at a time, serializing the copy. Measured here, that is 21.0 GB/s from pageable memory against 54.8 GB/s from pinned memory for a 256 MiB transfer, a factor of 2.6, and only the pinned path can overlap with compute because only it can be issued asynchronously. The catch is the other measured number. Pinning 256 MiB took 95.7 ms, roughly 2.7 GB/s of page-locking work, because the kernel must fault in and pin every page and update accounting. Pinning per batch would cost more than it saves. The correct pattern, which is what a well-configured PyTorch DataLoader with pin_memory=True does, is to allocate a small pool of pinned staging buffers once and recycle them.

NUMA placement follows the same logic one level up. Memory is allocated on the node of the CPU that first touches it, not the one that allocated the address range, so a common failure is a single-threaded initialization pass that places the entire arena on one node, after which every worker on other nodes pays remote latency and interconnect bandwidth forever. The fixes are to first-touch in parallel with the same thread-to-data mapping the computation will use, to bind explicitly (numactl --cpunodebind --membind, or mbind), and for GPU work to place host buffers on the node with the PCIe affinity of the target device, which nvidia-smi topo -m reports. This machine exposes a single NUMA node, so the effect could not be measured here.

Huge pages for large models. A 70-billion-parameter model in bf16 is 140 GB of resident memory. With 4 KiB pages that is 34.2 million page-table entries and, at the measured 1,509 ns per minor fault, about 52 seconds of pure fault handling to touch it all once. With 2 MiB pages it is 66,800 faults and the measured first-touch cost falls by 2.7× overall. The steady-state gain is the translation coverage, since a second-level TLB of a couple of thousand entries covers 8 MiB with 4 KiB pages and 4 GiB with 2 MiB pages. Use madvise(MADV_HUGEPAGE) on the specific large, dense, long-lived regions rather than setting the system-wide policy to always, which is the configuration that produces latency spikes from compaction stalls. On this machine the policy is already madvise, which is the sensible default.

cgroup limits in training clusters. Every containerized job runs under memory.max and cpu.max, and both fail in characteristic ways. Exceeding memory.max with no swap, which is the normal configuration, means reclaim of clean file pages first (so the job's page cache evaporates and its data loading slows down before anything is killed) and then an OOM kill inside the cgroup. Setting memory.high below memory.max converts the cliff into a throttle and buys time to notice. cpu.max enforces a quota per period, so a job that briefly needs more than its quota is stalled to the end of the period. With the default 100 ms period this produces exactly the pattern of periodic 50 ms stalls that gets misdiagnosed as a network problem. Pressure stall information is the honest signal. cpu.pressure, memory.pressure and io.pressure report the fraction of time tasks were stalled waiting for each resource, which is what an autoscaler should react to rather than utilization.

Why data loaders are usually OS-bound. Add up what one training step asks of the kernel. There are file opens and reads (system calls and possibly major faults), decode (user CPU), collation into pinned buffers (a copy plus, if done wrong, page pinning), a host-to-device transfer (DMA), and inter-process communication between loader workers and the trainer (pipes or shared memory, with context switches at every handoff). The GPU is idle for all of it unless it overlaps. The measurements say where the time goes, 96 µs per cold 110 KiB file read, 1.9 µs per context switch, 3.8 µs per sleep-and-wake round trip between a worker and the trainer, 1.5 µs per minor fault on a freshly allocated buffer, and, at the worst, 47 µs per uncached random read. A loader that does a few dozen of those per sample and produces samples at 16,000 per second is spending the equivalent of many cores in the kernel. This is why the standard remedies are all operating-system remedies, multiple worker processes so that blocking overlaps, persistent workers so the pool is not rebuilt each epoch, pinned buffer pools, prefetch depth greater than one so the queue never empties, large sequential shards instead of small files, and, increasingly, moving decode to the GPU so the CPU only moves bytes. Measuring which of these is binding takes two numbers, GPU utilization during a step and the loader's queue depth. If the queue is empty and utilization is low, the problem is upstream in the kernel, not in the model.

The current research frontier

Pluggable scheduling. The largest recent change to the kernel's oldest policy debate is sched_ext, merged in 6.12, which lets a scheduling policy be written as a set of BPF callbacks and loaded at runtime, with a watchdog that falls back to the built-in scheduler if the custom one misbehaves. It arrived from engineers at Meta and Google after years of resistance, and it changes the character of the argument. Instead of one policy per kernel release, workload-specific schedulers can be tried in production, and the scx collection now includes policies tuned for gaming latency, for virtualized workloads, and for cache-topology-aware placement. EEVDF itself, merged in 6.6 and based on the 1995 algorithm, continues to be refined around slice requests and latency nice.

Memory management under new hardware. Multi-generational LRU, developed at Google and merged in 6.1, replaced the two-list reclaim heuristic with generation-based aging and measurably improves both hit rate and reclaim CPU cost. CXL attaches memory over a serial link at latencies between DRAM and storage, which turns the machine into an explicitly tiered memory system and revives page-placement research that had been dormant since NUMA balancing. DAMON, contributed from industry, samples access patterns cheaply enough to drive promotion and demotion policies, and the kernel now has tiering machinery that treats CXL memory as a slow NUMA node. Whether the right interface is transparent tiering or explicit application control is genuinely open.

Kernel-bypass and its retreat. The line of work that began with exokernels at MIT and continued through Arrakis (Washington and ETH Zurich) and Demikernel argues that the kernel should be a control plane while data plane operations go straight from application to device. SPDK and DPDK are the production forms. The counter-argument has strengthened. io_uring recovered most of the syscall-amortization benefit while keeping the kernel's protection and sharing, and the microsecond-scale scheduling work from MIT (Shenango, Caladan) showed that a kernel-adjacent scheduler can reallocate cores at microsecond granularity, which pure bypass cannot do because it dedicates cores statically. The current synthesis is that bypass wins for single-tenant appliances and loses for shared infrastructure.

Programmable kernels and their limits. eBPF keeps expanding. BPF programs now implement schedulers, LSM security policies, congestion control, and storage functions, and work from a group at Columbia showed that resubmitting dependent storage requests from inside the kernel's completion path can cut the latency of index lookups substantially. The tension is verification. Every extension of what programs may do makes the verifier's job harder, and verifier bugs are kernel vulnerabilities. That is one of two reasons several cloud providers disable unprivileged io_uring and restrict BPF. The other is that both enlarged the attack surface faster than it could be audited.

Confidential computing inverts the trust relationship the whole subject assumes. AMD SEV-SNP, Intel TDX and ARM CCA encrypt and integrity-protect guest memory so that the hypervisor, and therefore the cloud operator, cannot read it. The operating-system consequences are subtle. The guest can no longer trust the hypervisor's answers about time, topology or device behavior, so interfaces that were merely performance-sensitive become security-sensitive, and paravirtualized devices need explicitly shared bounce buffers. Related work on the untrusted-host model informs sandboxing designs like gVisor and the microVM approach of Firecracker.

Rust in and around kernels. Rust support landed in Linux 6.1 and the first substantial drivers followed. The argument is that roughly two thirds of serious kernel vulnerabilities are memory-safety bugs that a checked language rules out by construction. Research kernels written entirely in Rust are further along. rCore, from a group at Tsinghua, is a RISC-V kernel used to study whether ownership discipline can express kernel-internal sharing, and Asterinas explores a framekernel structure where an unsafe core is small and auditable. Whether the ergonomics of expressing kernel lifetime rules in Rust are worth the friction is still being settled in public.

Storage interfaces that expose the truth. Zoned namespaces and flexible data placement let the host, rather than the drive's firmware, decide where data lands, eliminating the double garbage collection that happens when a log-structured application runs on a log-structured drive. That is the exokernel argument applied to flash. Stop emulating a block device and expose what the hardware is. On the GPU side, direct paths from storage to device memory (GPUDirect Storage, and research on letting GPU threads issue storage requests) attack exactly the loader bottleneck described above by removing the host bounce entirely.

Open source to read

Reading kernels is the fastest way to convert this material from vocabulary into understanding. The list below is ordered from smallest to largest commitment, with the file to open first.

• mit-pdos/xv6-riscv — a complete UNIX-like kernel in about nine thousand lines of C, readable in a weekend, with real processes, page tables, a journaled file system and a shell. Open kernel/proc.c for fork, exit, wait and scheduler in one file, then kernel/vm.c for a three-level RISC-V page walker that is fifty lines long. Nothing else on this list gives the same ratio of understanding to effort.
• torvalds/linux — the production system every measurement here came from. Open kernel/sched/fair.c for EEVDF: the weight table and update_curr make the virtual-runtime arithmetic concrete, and pick_eevdf implements the eligibility and deadline rule described above. Then mm/memory.c (handle_mm_fault and do_wp_page, which is copy-on-write in the flesh), mm/page_alloc.c for the buddy allocator, and fs/jbd2/commit.c for the journal commit sequence.
• axboe/liburing — the user-space library for io_uring, and the readable specification of the ring protocol. Open src/queue.c to see how submission and completion are actually synchronized with the kernel, then the examples/ directory, which contains complete programs worth more than any tutorial.
• libbpf/libbpf — the canonical way to load and attach BPF programs, and the home of compile-once-run-everywhere relocations. Open src/libbpf.c and follow bpf_object__load to see what the kernel is actually asked to verify.
• iovisor/bcc — a large collection of production BPF tools, and the fastest way to learn what is observable. Open tools/biolatency.py: it is a complete block-I/O latency histogram in under a hundred lines, and reading it teaches both the tracing interface and where the block layer's boundaries are.
• opencontainers/runc — the reference container runtime, and the shortest path to seeing that a container is namespaces plus cgroups plus a mount. Open libcontainer/nsenter/nsexec.c, the small C program that does the clone and setns dance before Go's runtime starts, then the cgroup manager code for how limits are written.
• google/gvisor — a user-space kernel implementing much of the Linux system call interface, which makes the interface's size visible in a way nothing else does. Open runsc/main.go for the entry point, then browse pkg/sentry/, where the syscall implementations live.
• firecracker-microvm/firecracker — a minimal virtual machine monitor in Rust, built for density and fast boot. Start in src/vmm/, the VMM crate, and read the device model: it is short precisely because the design refuses to emulate a whole PC.
• openzfs/zfs — the reference implementation of a copy-on-write, checksummed, pooled file system. Open module/zfs/arc.c, the adaptive replacement cache, which is the best-documented real-world answer to the replacement question this page poses with FIFO, LRU and CLOCK.

Common misconceptions

"A container is a lightweight virtual machine." It is not a virtual machine at all. The processes in a container run on the host kernel and make ordinary system calls to it; what differs is that namespaces restrict what they can see and cgroups restrict what they can consume. The consequence is not academic: the tenant's attack surface is the whole system-call interface rather than a small hardware model, a kernel privilege-escalation bug is a container escape, and uname inside the container reports the host's kernel version because it is the host's kernel.

"fork copies the parent's memory." It copies page tables, not pages, and marks everything read-only so that the copy happens lazily and only for pages that are written. The measured cost is about 25 ns per resident page, so a 2 GiB process forks in 14 ms rather than the roughly 200 ms a real copy would take. The corollary that matters more: fork is still linear in the number of pages, so a large process forks slowly even though no data moves, and the deferred cost reappears later as 2 µs copy-on-write faults, which is why a Python worker that merely touches inherited objects ends up copying them anyway.

"More memory can only reduce page faults." False for FIFO and for CLOCK, as demonstrated above: on the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO takes 9 faults with three frames and 10 with four. Belady's anomaly is impossible only for stack algorithms, whose resident sets are nested as memory grows; LRU and OPT qualify and FIFO does not. The practical version of this mistake is assuming that any cache gets monotonically better with size, which is false for any eviction policy that is not stack-based.

"Threads are much cheaper to switch than processes." Measured here, a thread switch is 1,749 ns and a process switch 1,885 ns, a difference of 7.8%. Tagged TLB entries (PCID) made the address-space change cheap. What actually dominates is the cache and TLB state destroyed by whatever runs next, which is identical for threads and processes: with a 64 MiB working set the indirect cost is 11.3 µs per turn, six times the direct cost. Optimize for fewer switches and better locality, not for threads over processes.

"If fsync returned success, the data is safe." Only this file's data, and only if the file's name is already durable: creating a file and calling fsync on it does not make the directory entry durable, so after a crash the data can exist with no name. Ordering between separate files is not guaranteed by anything except an intervening fsync. And before Linux 4.13, a writeback error could be reported once and then cleared, so a retried fsync could return success on data that was never written; the modern behavior reports the error to every descriptor that was open at the time, and a failed fsync should be treated as data loss, not as a retryable condition.

"System calls are slow because switching to kernel mode is expensive." The mode switch itself is a few dozen cycles. The 133.8 ns measured here is mostly software: stack and register setup, the page-table switch that kernel page-table isolation added to mitigate Meltdown, seccomp filter evaluation, audit hooks, and the return path's signal and reschedule checks. The proof is the vDSO, which runs the same clock_gettime logic without a trap in 32.2 ns against 188.6 ns for the trapping version, and the seccomp measurement, where adding a filter costs a measurable 11 ns of that total.

"io_uring is fast because it avoids system calls." That is the smaller effect. On warm reads served from the page cache, where there is no I/O to overlap, io_uring at queue depth 64 beat a pread loop by only 8%. On cold reads that reach the device, it won by 4.0×, because 64 requests were in flight instead of one. Asynchronous interfaces buy concurrency first and syscall amortization second, and a design that batches submissions without increasing queue depth captures almost none of the benefit.

"Huge pages make memory access faster." They remove page-walk time, nothing else. Measured on a random dependent chase over 512 MiB, the access cost fell from 136.1 ns to 116.3 ns: the 19.8 ns of walk disappeared and the remaining 116 ns of cache and DRAM latency did not move. They also cost something: allocation needs contiguous aligned blocks, so under fragmentation the allocator stalls in compaction, and a copy-on-write fault on a huge page copies 2 MiB. Enable them for large, dense, long-lived regions with madvise rather than system-wide.

Self-check

References

1. Arpaci-Dusseau, R. and Arpaci-Dusseau, A. (2018). Operating Systems: Three Easy Pieces, version 1.00. University of Wisconsin. Full text. The clearest derivation-first treatment of virtualization, concurrency and persistence; the source of the "three easy pieces" framing used throughout this page.
2. Silberschatz, A., Galvin, P. and Gagne, G. (2018). Operating System Concepts, 10th edition. Wiley. The standard comprehensive reference; strongest on scheduling and deadlock formalism.
3. Tanenbaum, A. and Bos, H. (2014). Modern Operating Systems, 4th edition. Pearson. Broadest coverage of alternative designs, including the microkernel case argued by one of its principals.
4. Kerrisk, M. (2010). The Linux Programming Interface. No Starch Press. The definitive description of what each system call actually promises; the reference used for the fork, exec, mmap and fsync semantics here.
5. Bovet, D. and Cesati, M. (2005). Understanding the Linux Kernel, 3rd edition. O'Reilly. Dated but still the best structural walkthrough of the memory management and I/O subsystems.
6. Love, R. (2010). Linux Kernel Development, 3rd edition. Addison-Wesley. Concise treatment of the scheduler, synchronization primitives and interrupt context constraints.
7. Gregg, B. (2020). Systems Performance: Enterprise and the Cloud, 2nd edition, and (2019) BPF Performance Tools. Addison-Wesley. The methodology and the tooling for measuring everything in this page on a running system.
8. Ritchie, D. and Thompson, K. (1974). The UNIX time-sharing system. Communications of the ACM 17(7). doi:10.1145/361011.361061. The origin of the process, file descriptor and shell design that everything here inherits.
9. Lampson, B. (1983). Hints for computer system design. SOSP. doi:10.1145/800217.806614. The design vocabulary: end-to-end, hints, fast paths, and handling the normal and worst cases separately.
10. Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5(2). Introduces the optimal policy used as the yardstick here, and the anomaly named after him.
11. Denning, P. (1968). The working set model for program behavior. Communications of the ACM 11(5). doi:10.1145/363095.363141. Locality made quantitative, and the basis of the thrashing analysis.
12. Liu, C. L. and Layland, J. (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20(1). doi:10.1145/321738.321743. Rate-monotonic optimality, the utilization bound derived above, and EDF's exactness.
13. Waldspurger, C. and Weihl, W. (1994). Lottery scheduling: flexible proportional-share resource management. OSDI, MIT. Proportional share as a first-class goal; the stride variant in the companion work is the direct ancestor of virtual runtime.
14. McKusick, M., Joy, W., Leffler, S. and Fabry, R. (1984). A fast file system for UNIX. ACM TOCS 2(3), Berkeley. doi:10.1145/989.990. Cylinder groups, fragments, and the free-space reserve.
15. Rosenblum, M. and Ousterhout, J. (1992). The design and implementation of a log-structured file system. ACM TOCS 10(1), Berkeley. doi:10.1145/146941.146943. Sequential writing and cleaning, the design that reappears in SSD firmware and LSM trees. Seltzer and colleagues later argued from measurements that cleaning costs can erase the benefit on update-heavy workloads.
16. Bonwick, J. (1994). The slab allocator: an object-caching kernel memory allocator. USENIX Summer. Object caching, constructors and slab coloring, still the shape of Linux's SLUB.
17. Ganger, G., McKusick, M., Soules, C. and Patt, Y. (2000). Soft updates: a solution to the metadata update problem in file systems. ACM TOCS 18(2), Carnegie Mellon and Berkeley. The main alternative to journaling, and a good test of whether the crash-consistency reasoning here is understood.
18. Pillai, T., Chidambaram, V., Alagappan, R., Al-Kiswany, S., Arpaci-Dusseau, A. and Arpaci-Dusseau, R. (2014). All file systems are not created equal: on the complexity of crafting crash-consistent applications. OSDI, Wisconsin. The systematic catalogue of application-level durability bugs discussed above.
19. Bjørling, M., Axboe, J., Nellans, D. and Bonnet, P. (2013). Linux block IO: introducing multi-queue SSD access on multi-core systems. SYSTOR. doi:10.1145/2485732.2485740. Why the single request queue had to go.
20. Axboe, J. (2019). Efficient IO with io_uring. Design document, and the liburing repository. The ring protocol whose measured behavior is reported above.
21. Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., Neugebauer, R., Pratt, I. and Warfield, A. (2003). Xen and the art of virtualization. SOSP, Cambridge. doi:10.1145/945445.945462. Paravirtualization, and the numbers that made virtualization credible for servers.
22. Adams, K. and Agesen, O. (2006). A comparison of software and hardware techniques for x86 virtualization. ASPLOS, VMware. doi:10.1145/1168857.1168860. The result that first-generation hardware assistance was often slower than binary translation. Popek and Goldberg's 1974 formal criteria (doi:10.1145/361011.361073) state the requirement it violates.
23. Liedtke, J. (1995). On micro-kernel construction. SOSP. doi:10.1145/224056.224075. The demolition of the microkernel performance argument; Klein and colleagues' seL4 verification (SOSP 2009) is where that line of work arrived, and Accetta and colleagues' Mach (USENIX 1986, Carnegie Mellon) is where it started.
24. Baumann, A., Barham, P., Dagand, P.-E., Harris, T., Isaacs, R., Peter, S., Roscoe, T., Schüpbach, A. and Singhania, A. (2009). The multikernel: a new OS structure for scalable multicore systems. SOSP, ETH Zurich and Microsoft Research. doi:10.1145/1629575.1629579. Treating a many-core machine as a distributed system; contrast with Boyd-Wickizer and colleagues' OSDI 2010 analysis from MIT, which argued the shared-memory kernel scales further than expected.
25. Peter, S., Li, J., Zhang, I., Ports, D., Woos, D., Krishnamurthy, A., Anderson, T. and Roscoe, T. (2014). Arrakis: the operating system is the control plane. OSDI, Washington and ETH Zurich. The kernel-bypass argument in its clearest form; Engler, Kaashoek and O'Toole's exokernel (SOSP 1995, MIT) is its ancestor, and Agache and colleagues' Firecracker (NSDI 2020) is the microVM answer to the same isolation question.
26. McKenney, P. and Slingwine, J. (1998). Read-copy update: using execution history to solve concurrency problems. PDCS. The grace-period argument behind RCU; O'Neil and colleagues' log-structured merge-tree (Acta Informatica 1996) is the storage-side relative of the same read-optimized thinking.