8. Virtual Memory
Chapter 7 built the machinery that lets a process's pages live anywhere in physical memory; this chapter removes the last assumption — that they have to be in physical memory at all. By keeping only the pages a process is actually using resident and leaving the rest on disk, the OS lets programs be larger than RAM, lets far more of them run at once, and makes process creation nearly free. The price is that some memory references now cost a disk access instead of 100 nanoseconds, so the whole chapter is really about one question: how do you decide what stays.
<a id="81-demand-paging"></a>
8.1 Demand Paging
This section introduces the central trick — bring a page in only when it is touched — and works through what the hardware and kernel must do to make an interrupted instruction resume as if nothing happened, plus the arithmetic that shows how rare faults must be.
Concept of Virtual Memory
Theory
Start with an observation about programs rather than about hardware. Almost no program uses all of its memory, and the parts it does use, it uses in bursts. Error-handling code for conditions that never occur, features the user never opens, a symbol table consulted only on a crash, an array allocated at maximum size but filled to a fraction — all of it occupies memory that could hold something else. Measurements consistently show that over any short interval, a process touches a small fraction of its address space.
Virtual memory is the technique that exploits this: the logical address space is completely separated from physical memory, so a process's address space can be larger than all of RAM, with only the actively used portion resident. The rest lives on secondary storage and is fetched when needed.
Three benefits follow, and they are worth separating because people usually only name the first:
- Programs are not limited by physical memory. A 4 GB program runs on a 1 GB machine. The programmer stops managing overlays by hand — which is what programmers genuinely had to do before 1961.
- More programs run concurrently. If each process needs only its active fraction resident, memory holds many more processes. CPU utilisation and throughput rise, because there are more runnable processes to choose from when one blocks.
- Process creation and program loading get cheaper. Nothing needs to be read from disk before a program starts running, and
forkneed not copy anything. Both are demand-driven.
The enabling property is the one Chapter 7 ended on: pages are uniform, small, and individually relocatable. The valid/invalid bit in each PTE, already present for protection, does double duty — "invalid" now means either "not part of your address space" or "part of it, but currently on disk", and the kernel distinguishes them from its own records.
The virtual address space also gets a shape. A typical layout puts code at the bottom, then data, then a heap growing upward, and a stack growing downward from the top, with an enormous unmapped gap between them. That gap costs nothing — unmapped virtual addresses consume no page tables and no frames — which is why a 64-bit process can reserve terabytes of address space and use megabytes of memory.
The analogy is a working desk with an archive room. The desk is small (RAM); the archive holds everything (disk). You fetch a folder when you need it and return one you have not touched in a while. Someone watching only your desk would conclude you were working on three folders; the project actually spans thousands.
Example
VIRTUAL ADDRESS SPACE vs WHAT IS ACTUALLY RESIDENT
Virtual (per process) Physical memory Backing store
+------------------+ high
| stack | resident ---> +-------------+
+------------------+ | stack pg |
| | +-------------+
| HUGE UNMAPPED | costs +------------+
| GAP | NOTHING | code pages |
| | | (from the |
+------------------+ +-------------+ | exe file) |
| heap | partly ----> | heap pgs | +------------+
+------------------+ +-------------+ | heap pages |
| data | resident ---> | data pg | | (swap) |
+------------------+ +-------------+ +------------+
| code | partly -----> | code pg |
+------------------+ 0 +-------------+
only the ACTIVE FRACTION is here
VIRTUAL SIZE vs RESIDENT SIZE, A REAL PROCESS
VmSize (virtual, reserved) : 1,240 MB
VmRSS (resident, in frames) : 38 MB <- 3% of the address space
THE PTE's VALID BIT DOES DOUBLE DUTY
valid=1 -> in a frame, translate normally
valid=0 -> trap. The KERNEL then decides which case it is:
(a) legal address, page on disk -> page it in, retry
(b) not in any mapped region -> SIGSEGV
# Why "larger than RAM" works: locality means the resident set can be a
# small fraction of the address space without constant faulting.
class VirtualMemory:
def __init__(self, frames):
self.frames = frames # physical capacity, in pages
self.resident = {} # page -> frame
self.faults = 0
def access(self, page):
if page in self.resident:
return # hit: hardware handles it, ~100 ns
self.faults += 1 # miss: trap to kernel, ~100 us (SSD)
if len(self.resident) >= self.frames:
victim = next(iter(self.resident)) # naive; Section 8.2 does better
del self.resident[victim]
self.resident[page] = len(self.resident)
# A 1000-page program that loops over 8 pages: address space >> working set.
vm = VirtualMemory(frames=16)
for _ in range(1000):
for page in range(8): # the loop's working set
vm.access(page)
print(vm.faults) # 8 -- eight faults total for 8000 accesses
# The other 992 pages are never touched and never loaded.
# Virtual vs resident, on any Linux process.
grep -E 'VmSize|VmRSS|VmSwap' /proc/self/status
# VmSize: 1269484 kB <- address space reserved
# VmRSS: 38912 kB <- what is actually in RAM
# VmSwap: 512 kB <- what was pushed out to disk
# Overcommit: the kernel lets processes reserve far more than exists,
# precisely because reservations are mostly never touched.
sysctl vm.overcommit_memory # 0 = heuristic (default), 2 = strict
free -h # 'available' matters more than 'free'
Key takeaways
- Virtual memory separates the logical address space from physical memory, so a process can be larger than RAM with only its active pages resident.
- It works because of locality: over short intervals a program touches a small fraction of its address space.
- Benefits are three: programs unconstrained by RAM, higher degree of multiprogramming, and cheap process creation and program start.
- The PTE's valid bit signals both "illegal address" and "on disk"; the kernel's own records tell the two apart.
- Unmapped virtual address space is free — no page tables, no frames — which is why reserving terabytes costs nothing.
🧪 Practice
- A process has a 2 GB virtual size and a 60 MB resident set on a 4 GB machine. Explain how 40 such processes can run, and what would have to be true for that to stop working.
- Run
grep -E 'VmSize|VmRSS' /proc/self/statusfor a browser or IDE process and compute the ratio. Explain what the difference is made of.- Interview-style: "Linux lets you
mallocmore memory than the machine has, and it succeeds. Where does the failure actually happen?" Hint: think about the difference between reserving an address range and touching a page in it, and what the kernel must find at the moment of the first write.
Page Faults and Handling
Theory
A page fault is a trap raised by the MMU when a translation cannot be completed. It is not an error — it is the mechanism by which demand paging works, and on a healthy system faults happen constantly.
The sequence, in order:
- The process references an address whose PTE has the valid bit clear. The MMU traps to the kernel.
- The kernel checks the faulting address against its own record of the process's mapped regions (on Linux, the VMA list). If the address is in no region, or the access violates the region's permissions, the kernel delivers
SIGSEGV. Otherwise, the fault is legitimate. - The kernel finds a free frame. If none is free, it evicts one (Section 8.2), writing it to disk first if it is dirty.
- The kernel schedules a disk read to load the page into the frame, and blocks the process. Other processes run in the meantime — this is why a page fault is a scheduling event, not just a memory event.
- On I/O completion, the interrupt handler updates the PTE: frame number set, valid bit set.
- The faulting instruction is restarted, and this time it completes normally.
Step 6 carries a subtle hardware requirement. The instruction must be restartable — it must be possible to re-execute it from the beginning with no visible difference. That is easy for a simple load, and genuinely hard for instructions that modify memory and registers before faulting. A block-move instruction whose source and destination overlap can copy half the block, fault, and then produce wrong results if restarted. Architectures solve this by pre-touching all pages before starting, or by keeping enough state to resume mid-instruction, or (on some machines) by using temporary registers that can be rolled back.
Two kinds of fault are distinguished, and the difference is roughly a factor of a thousand in cost:
- A minor fault is resolved without I/O: the page is already in memory (in the page cache, or shared with another process, or a copy-on-write copy, or a zero-fill that just needs a blank frame). Cost: a few microseconds.
- A major fault requires a disk read. Cost: tens of microseconds on NVMe, milliseconds on a hard disk.
Watching these two counters is the single most useful diagnostic in this chapter. Lots of minor faults is normal — that is a program starting up. Lots of major faults means the working set does not fit, which is the road to thrashing (Section 8.4).
Example
THE PAGE FAULT PATH
1. CPU: mov eax, [0x7f2a1000]
|
2. MMU: PTE valid bit = 0 --> TRAP
|
3. Kernel: is the address in a valid VMA with compatible permissions?
| |
| no | yes
v v
SIGSEGV 4. find a free frame
(process dies) | none free?
| -> evict a victim (8.2),
| write back if DIRTY
v
5. issue disk read, BLOCK the process
| <- scheduler runs others
v
6. I/O completes -> set frame + valid bit
v
7. RESTART the faulting instruction
COST STRUCTURE
event typical latency ratio to RAM
-------------------------- --------------- ------------
TLB hit + RAM access ~100 ns 1x
minor fault (no I/O) ~3 us 30x
major fault, NVMe SSD ~100 us 1,000x
major fault, hard disk ~8 ms 80,000x
RESTARTABILITY: THE HARD CASE
MOV.B (A1)+, (A2)+, #1024 block move, auto-incrementing
copies 600 bytes, then destination page faults
registers A1/A2 already advanced by 600
naive restart -> copies those 600 bytes TWICE -> corruption
Fixes: touch both ends first, or save/restore the modified registers.
/* The kernel's fault handler, in outline. The two branches at the top are
the entire difference between "demand paging working" and "SIGSEGV". */
void page_fault_handler(unsigned long fault_addr, unsigned long error_code) {
struct vma *v = find_vma(current->mm, fault_addr); /* which region? */
if (!v || fault_addr < v->start) {
force_sig(SIGSEGV); /* not a mapped address */
return;
}
if ((error_code & WRITE) && !(v->flags & VM_WRITE)) {
if (v->flags & VM_COW) { do_cow_fault(v, fault_addr); return; }
force_sig(SIGSEGV); /* genuine permission error */
return;
}
struct frame *f = alloc_frame();
if (!f) f = evict_victim(); /* Section 8.2 chooses it */
if (vma_is_anonymous(v) && !in_swap(v, fault_addr))
clear_frame(f); /* MINOR: zero-fill, no I/O */
else
read_page_blocking(v, fault_addr, f); /* MAJOR: disk read */
set_pte(fault_addr, f, v->flags); /* map it, set valid bit */
/* return from trap -> hardware RESTARTS the faulting instruction */
}
# Minor vs major faults for a single command.
/usr/bin/time -v ls /usr/bin >/dev/null
# Minor (reclaiming a frame) page faults: 412 <- normal startup
# Major (requiring I/O) page faults: 0 <- everything was cached
# Force major faults by dropping the cache first (needs root).
sync && echo 3 > /proc/sys/vm/drop_caches
/usr/bin/time -v ls /usr/bin >/dev/null
# Major (requiring I/O) page faults: 78 <- now it reads from disk
# System-wide fault rates, live. 'majflt/s' is the number to watch.
pidstat -r 1 5
sar -B 1 5 # pgpgin/s, pgpgout/s, fault/s, majflt/s
Key takeaways
- A page fault is a trap, not an error; the kernel decides whether it is a legitimate demand-paging event or a
SIGSEGV. - The handler locates a frame (evicting if needed), reads the page, updates the PTE, and restarts the faulting instruction.
- The faulting instruction must be restartable, which constrains CPU design for instructions that mutate state before faulting.
- Minor faults need no I/O and cost microseconds; major faults need a disk read and cost 100 to 80,000 times more.
- A faulting process blocks, so the scheduler runs someone else — page faults are scheduling events.
🧪 Practice
- Classify each as a minor fault, a major fault, or a
SIGSEGV: first touch of a freshlymalloced page; reading a file page already in the page cache; reading a page that was swapped out; dereferencing a pointer 1 GB past the heap.- Run the
/usr/bin/time -vexperiment above on a program of your choice, with and without dropping caches, and explain the change in the two counters.- Interview-style: "Why must the CPU be able to restart a faulting instruction, and which instructions make that hard?" Hint: consider an instruction that increments a register and writes memory in the same operation, and what re-executing it from the top would do a second time.
Pure Demand Paging
Theory
If pages arrive on demand, an obvious question is: what should be resident when the process starts? Pure demand paging takes the extreme position — start with nothing. No pages are loaded at all; the very first instruction fetch faults, and every page arrives only because something touched it.
The appeal is that no page is ever loaded speculatively. Nothing is wasted on code paths never taken. Program start is instantaneous in the sense that exec returns without reading a single byte of the program's text.
The problem is the start-up burst. A program that touches 200 distinct pages during initialisation takes 200 separate faults, each a synchronous disk round trip. On a hard disk at 8 ms per fault that is 1.6 seconds of nothing but faulting — and because the accesses are sequential in the file, they could have been satisfied by a handful of large sequential reads instead.
Real systems therefore do not use pure demand paging. They use prepaging: bring in pages that are likely to be needed, in batches, exploiting the fact that a large sequential read costs barely more than a small one. The mechanisms are:
- Fault-around. On a fault, map not only the needed page but a cluster of neighbours already in the page cache. Linux does this with 16 pages by default — one fault instead of sixteen, at essentially no cost since no extra I/O is needed.
- Readahead. Detect sequential access and issue reads for upcoming pages before they are requested, so the I/O overlaps with computation.
- Explicit hints.
madvise(MADV_WILLNEED)andposix_fadviselet a program tell the kernel what it is about to touch.MADV_SEQUENTIALraises readahead aggressiveness;MADV_RANDOMdisables it.
Prepaging is a bet, and the arithmetic is what determines whether it pays. If you prepage s pages and only a fraction α are actually used, you have wasted s(1-α) page-loads. It pays when α is high or when the extra pages ride along in an I/O you were doing anyway. For sequential file reads α is near 1 and prepaging is a large win; for random access it is near 0 and prepaging is pure waste — which is exactly why MADV_RANDOM exists.
Example
PURE DEMAND PAGING vs PREPAGING, PROGRAM START-UP
PURE DEMAND (200 pages needed during init, HDD at 8 ms)
fault fault fault ... 200 times
|--8ms--|--8ms--|--8ms--| ... total 1600 ms
each is a synchronous round trip; the process is blocked throughout
PREPAGING IN CLUSTERS OF 16
|----- 1 read of 64 KB -----| x 13 total ~120 ms
the disk transfers 16 pages for barely more than the cost of 1
FAULT-AROUND (Linux, pages already in the page cache)
one fault maps 16 PTEs at once -> 1 trap instead of 16, no extra I/O
WHEN PREPAGING PAYS: s pages fetched, fraction a actually used
wasted loads = s * (1 - a)
saved faults = s * a - 1
a = 0.95, s = 16 -> wasted 0.8, saved 14.2 strongly positive
a = 0.20, s = 16 -> wasted 12.8, saved 2.2 strongly negative
(random access: prepaging burns I/O bandwidth)
# Modelling the prepaging bet: is a cluster fetch worth it?
def cost_ms(pages_needed, cluster, alpha, fault_ms=8.0, per_extra_page_ms=0.05):
"""fault_ms: cost of a disk round trip. per_extra_page_ms: marginal cost
of transferring one more page in the SAME I/O (much cheaper)."""
useful_per_fetch = max(cluster * alpha, 1)
fetches = pages_needed / useful_per_fetch
return fetches * (fault_ms + (cluster - 1) * per_extra_page_ms)
for cluster in (1, 4, 16, 64):
seq = cost_ms(200, cluster, alpha=0.95)
rnd = cost_ms(200, cluster, alpha=0.10)
print(f"cluster {cluster:3}: sequential {seq:7.1f} ms | random {rnd:7.1f} ms")
# cluster 1: sequential 1600.0 ms | random 1600.0 ms
# cluster 4: sequential 425.4 ms | random 1624.0 ms
# cluster 16: sequential 115.0 ms | random 1720.0 ms
# cluster 64: sequential 36.3 ms | random 2104.0 ms
# Large clusters are transformative for sequential access and actively
# harmful for random access -- hence madvise().
/* Telling the kernel what you are about to do. The hints are advisory,
but they change readahead policy immediately. */
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
void scan_whole_file(int fd, size_t len) {
void *p = mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
madvise(p, len, MADV_SEQUENTIAL); /* raise readahead: I go front to back */
madvise(p, len, MADV_WILLNEED); /* start loading NOW, asynchronously */
/* ... walk the mapping; most touches now hit already-resident pages ... */
madvise(p, len, MADV_DONTNEED); /* done: drop the pages, free frames */
munmap(p, len);
}
void random_lookups(int fd, size_t len) {
void *p = mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
madvise(p, len, MADV_RANDOM); /* DISABLE readahead: neighbours are
useless and would waste bandwidth */
/* ... scattered accesses ... */
munmap(p, len);
}
# Linux's fault-around window, in pages (default 16 -> 64 KB).
cat /sys/kernel/debug/fault_around_bytes # 65536
# Readahead size for a block device, in 512-byte sectors.
blockdev --getra /dev/nvme0n1 # 256 -> 128 KB
# Watch prepaging work: pgpgin (KB read) far exceeds majflt (faults taken).
sar -B 1 3
Key takeaways
- Pure demand paging loads nothing at start; every page arrives via a fault, so nothing unused is ever read.
- Its weakness is the start-up burst: hundreds of synchronous round trips where a few sequential reads would do.
- Real systems prepage: fault-around maps neighbouring cached pages, readahead anticipates sequential access,
madvisetakes explicit hints. - Prepaging is a bet on the fraction of prefetched pages actually used; it wins big for sequential access and loses for random access.
- Extra pages fetched inside an I/O you were already performing are nearly free — that is why cluster size matters more than fault count.
🧪 Practice
- A program touches 500 pages during start-up on a device with 100 us access latency. Compute total start-up fault time under pure demand paging, and under prepaging with clusters of 32 at 95% usefulness.
- Write the
madvisecalls you would use for (a) a database doing random index lookups on a memory-mapped file, (b) a log processor scanning a file front to back, and justify each.- Interview-style: "Prepaging can make a program slower. How?" Hint: think about what the extra pages displace when memory is already full, and what happens to the I/O bandwidth another process needed.
Effective Access Time
Theory
Demand paging replaces a fixed memory latency with a probability distribution: most accesses are fast, a few are catastrophically slow. Effective access time (EAT) is the weighted average, and computing it is the fastest way to develop the correct intuition about how rare faults must be.
Let p be the page-fault rate (probability that a given memory reference faults), ma the memory access time, and pft the page-fault service time:
EAT = (1 - p) × ma + p × pft
The whole lesson is in the magnitudes. With ma = 100 ns and pft = 8 ms (a hard disk), the fault is 80,000 times more expensive than a hit. That ratio means the fault term dominates unless p is extraordinarily small:
p = 0.001(one fault per 1000 accesses): EAT = 8.1 us — the machine runs 81 times slower.p = 0.0000001: EAT = 100.8 ns — a 0.8% slowdown.
To keep degradation under 10% with an 8 ms service time you need roughly one fault per 400,000 accesses. This is the key result of the section: demand paging is only viable because locality makes fault rates that low, not because faults are cheap.
The page-fault service time itself is a sum, and knowing its parts tells you what to optimise:
- Trap to the kernel, save state, verify the address (~1-2 us).
- Find a free frame, possibly evicting a victim. If the victim is dirty it must be written out first, doubling the I/O. This is why the dirty bit matters so much and why kernels write back proactively.
- The disk read itself — the dominant term.
- Interrupt, update PTE, restore state, reschedule (~1-2 us).
Two practical consequences. First, keeping clean pages available (page buffering, Section 8.2) roughly halves the worst-case service time, because eviction no longer waits for a write. Second, the hardware trend matters enormously: moving from a hard disk (8 ms) to NVMe (~100 us) lowers the fault penalty by 80x, which is why systems today tolerate fault rates that would have been ruinous in 1995. The arithmetic is unchanged; only the constant moved.
Example
EAT = (1-p) * ma + p * pft ma = 100 ns
HARD DISK, pft = 8 ms NVMe SSD, pft = 100 us
p EAT slowdown p EAT slowdown
-------- ---------- --------- -------- -------- ---------
1e-3 8.1 us 81x 1e-3 200.0 ns 2.0x
1e-4 900.0 ns 9x 1e-4 110.0 ns 1.1x
1e-5 180.0 ns 1.8x 1e-5 101.0 ns 1.01x
1e-6 108.0 ns 1.08x 1e-6 100.1 ns 1.001x
FOR <10% DEGRADATION:
hard disk : p < 1 / 400,000 references
NVMe : p < 1 / 5,000 references <- 80x more forgiving
WHERE THE SERVICE TIME GOES (major fault, SSD)
trap + verify ~2 us |##
evict CLEAN victim ~1 us |#
evict DIRTY victim ~90 us |################################# <- avoid!
disk read ~90 us |#################################
PTE update + return ~2 us |##
Keeping a pool of clean, free frames removes the middle bar entirely.
# EAT, and the fault rate a target slowdown allows.
def eat_ns(p, ma_ns=100, pft_ns=8_000_000):
return (1 - p) * ma_ns + p * pft_ns
def max_fault_rate(target_slowdown, ma_ns=100, pft_ns=8_000_000):
"""Largest p keeping EAT <= target_slowdown * ma."""
return (target_slowdown - 1) * ma_ns / (pft_ns - ma_ns)
for device, pft in [("HDD ", 8_000_000), ("SATA ", 500_000), ("NVMe ", 100_000)]:
p10 = max_fault_rate(1.10, pft_ns=pft)
print(f"{device} pft={pft/1000:8.0f} us | p for +10%: {p10:.2e} "
f"(1 fault per {1/p10:,.0f} accesses)")
# HDD pft= 8000 us | p for +10%: 1.25e-06 (1 fault per 800,000 accesses)
# SATA pft= 500 us | p for +10%: 2.00e-05 (1 fault per 50,000 accesses)
# NVMe pft= 100 us | p for +10%: 1.00e-04 (1 fault per 9,999 accesses)
# The cost of evicting a DIRTY page: two I/Os instead of one.
clean = eat_ns(1e-4, pft_ns=100_000)
dirty = eat_ns(1e-4, pft_ns=200_000) # write-back + read
print(f"clean victim {clean:.1f} ns vs dirty victim {dirty:.1f} ns")
# clean victim 110.0 ns vs dirty victim 120.0 ns -> ~2x the fault overhead
Key takeaways
EAT = (1 - p) × ma + p × pft; becausepft/mais 1,000 to 80,000, the fault term dominates at almost any non-trivialp.- Keeping degradation under 10% needs roughly one fault per 400,000 references on a hard disk, one per 10,000 on NVMe.
- Demand paging works because locality drives
pto those levels — not because individual faults are cheap. - A dirty victim doubles the I/O in the service path, so kernels keep pools of clean, pre-written frames.
- Faster storage does not change the formula, only the constant — but an 80x smaller constant changes what workloads are viable.
🧪 Practice
- With
ma = 80 nsandpft = 3 ms, compute EAT forp = 10^-3,10^-5, and10^-7, and give the slowdown factor for each.- A system must stay within 20% of raw memory speed on a device with a 250 us fault service time. Compute the maximum acceptable fault rate, expressed as one fault per N references.
- Interview-style: "Your service's p99 latency has spikes but average CPU is low.
sar -Bshows majflt/s in the thousands. Explain the mechanism connecting these observations." Hint: work out what a single major fault does to one request's latency, and what a blocked process does to CPU utilisation figures.
Copy-on-Write
Theory
Chapter 7 introduced copy-on-write as a way to share frames. Here it matters as the technique that makes process creation a demand-paged operation, and it is worth seeing the fault path in full.
The problem: fork() is defined to give the child a complete, private copy of the parent's address space. Implemented literally, forking a process with a 2 GB heap means copying 2 GB. And in the overwhelmingly common case — fork immediately followed by exec — every one of those copied bytes is discarded microseconds later.
Copy-on-write eliminates the copy without changing the semantics:
- On
fork, the child's page table is built pointing at the parent's existing frames. Nothing is copied. - Every writable page is marked read-only in both page tables, and flagged as COW in the kernel's records.
- Reads by either process proceed at full hardware speed, sharing frames.
- A write by either process triggers a protection fault. The kernel sees the COW flag, allocates a new frame, copies that one page, marks it writable in the writer's page table, and restarts the instruction. The other process keeps the original.
- When only one process still maps a COW page, the kernel can simply mark it writable again — no copy needed.
The result is that copying is proportional to the pages actually modified, not to the address space size. A fork+exec copies essentially nothing. A long-lived forked child that writes half its heap copies half its heap — but incrementally, spread over time, only for pages it really uses.
Two related mechanisms complete the picture:
- Zero-fill-on-demand. New anonymous pages (fresh
malloc,.bss, stack growth) must read as zero. Rather than allocating and clearing a frame at allocation time, the kernel maps a shared, read-only zero page into every such address, marked COW. Reads of untouched memory cost nothing and consume no frames; the first write allocates and clears a real frame. This is why a hugecallocreturns instantly and why RSS grows only as you touch the buffer. vfork. An older optimisation that suspends the parent and shares its address space outright, avoiding even the page-table copy. It is dangerous (the child must not return or modify anything) and is largely obsolete now that COW made plainforkcheap;posix_spawnis the modern answer.
One consequence to internalise for production systems: with COW plus overcommit, a forked child can fail later, when a write finds no free frame — long after the call that "succeeded". This is the mechanism behind the classic "Redis forked for a snapshot and the OOM killer fired" incident.
Example
fork() WITH COPY-ON-WRITE
step 1: fork -- page tables built, ZERO bytes copied
parent frames child
p0 -> f7 (RO) -> [ f7 ] <- p0 -> f7 (RO)
p1 -> f8 (RO) -> [ f8 ] <- p1 -> f8 (RO)
p2 -> f9 (RO) -> [ f9 ] <- p2 -> f9 (RO)
both marked READ-ONLY though both are logically writable
step 2: child writes to p1 -> PROTECTION FAULT
kernel: COW flag set -> allocate f12, copy f8 -> f12
parent frames child
p0 -> f7 (RO) -> [ f7 ] <- p0 -> f7 (RO)
p1 -> f8 (RW) [ f8 ] p1 -> f12 (RW) <- private copy
p2 -> f9 (RO) -> [ f9 ] <- p2 -> f9 (RO)
ONE page copied. Parent's p1 becomes RW again: it is now the sole user.
ZERO-FILL-ON-DEMAND: calloc(1 GB) COSTS NOTHING UNTIL TOUCHED
all 262,144 pages -> the SAME shared zero frame, read-only
read anywhere -> returns 0, no frame allocated, no fault cost
write page k -> fault, allocate a frame, clear it, map RW
RSS after calloc(1 GB) : ~0
RSS after touching 10 MB of it : ~10 MB
COST COMPARISON: fork a process with a 2 GB heap
eager copy : 2 GB memcpy ~200 ms and 2 GB extra RAM
COW + exec : page tables only ~1 ms and ~0 extra RAM
/* COW made visible: the child's memory grows one page at a time,
and the parent is untouched. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
static long rss_kb(void) { /* read our own resident size */
long kb = 0; char buf[128]; FILE *f = fopen("/proc/self/status", "r");
while (fgets(buf, sizeof buf, f))
if (sscanf(buf, "VmRSS: %ld kB", &kb) == 1) break;
fclose(f); return kb;
}
int main(void) {
size_t n = 256 * 1024 * 1024; /* 256 MB */
char *buf = malloc(n);
memset(buf, 'A', n); /* make it genuinely resident */
printf("parent before fork: %ld kB\n", rss_kb());
if (fork() == 0) {
printf("child at start : %ld kB (shares the parent's frames)\n", rss_kb());
for (size_t i = 0; i < n; i += 4096 * 1024) /* touch 1 page per 4 MB */
buf[i] = 'B'; /* each write = one COW fault+copy */
printf("child after writes: %ld kB (only touched pages copied)\n", rss_kb());
_exit(0);
}
wait(NULL);
printf("parent after : %c (unchanged)\n", buf[0]); /* 'A' */
return 0;
}
# Zero-fill-on-demand: reserving is free, touching is what costs.
import os, mmap
def rss_mb():
with open("/proc/self/statm") as f:
return int(f.read().split()[1]) * os.sysconf("SC_PAGE_SIZE") / 2**20
print(f"start: {rss_mb():7.1f} MB")
m = mmap.mmap(-1, 1024 * 1024 * 1024) # reserve 1 GB, anonymous
print(f"after 1 GB mmap: {rss_mb():7.1f} MB") # essentially unchanged
step = mmap.PAGESIZE
for off in range(0, 100 * 1024 * 1024, step):
m[off] = 1 # each first write: one fault + frame
print(f"after touching 100 MB: {rss_mb():7.1f} MB")
# start: 12.3 MB
# after 1 GB mmap: 12.3 MB <- reservation is free
# after touching 100 MB: 112.4 MB <- frames appear only on first write
m.close()
Key takeaways
- COW lets
forkshare the parent's frames read-only, copying a page only when one side writes it. - Copying becomes proportional to pages modified, not to address-space size, making
fork+execnearly free. - The trigger is a protection fault; the kernel distinguishes a COW fault from a real permission error using its own flags.
- Zero-fill-on-demand maps a shared zero page for new anonymous memory, so allocation costs nothing until first write.
- With overcommit, a COW write can fail long after
forkreturned — the classic cause of surprise OOM kills in fork-heavy services.
🧪 Practice
- A process with 1 GB resident forks; the child writes 40 MB before exiting. Compute the physical memory copied under COW versus an eager copy, and state how many COW faults occurred with 4 KB pages.
- Run the C program above and explain the child's RSS at each print. Then predict what changes if the child writes every page instead of one per 4 MB.
- Interview-style: "A database forks a child to write a snapshot. Memory usage spikes and the OOM killer fires, even though the child only reads. What happened?" Hint: the child reads, but consider what the still-running parent is doing to those shared pages during the snapshot.
<a id="82-page-replacement"></a>
8.2 Page Replacement
When a fault arrives and no frame is free, something resident must go. This section works through the algorithms for choosing the victim, from the naive to the unattainable ideal, and shows why the one everybody actually ships is a compromise.
FIFO Replacement
Theory
The simplest possible policy: evict the page that has been in memory longest. Keep a queue of resident pages in arrival order; on a fault, remove from the head and add the newcomer at the tail.
The appeal is that it costs almost nothing. No per-access bookkeeping, no hardware support, one pointer to maintain. That is genuinely valuable — a replacement algorithm runs in the fault path, and an expensive one taxes the very situation it is trying to relieve.
The flaw is that arrival time has nothing to do with future use. A page loaded at start-up and referenced on every single iteration of the main loop is, by FIFO's reckoning, the best candidate for eviction, because it has been there longest. FIFO systematically evicts exactly the pages that have proven most useful, then faults them straight back in.
FIFO also exhibits Belady's anomaly: adding frames can increase the number of faults, which violates every intuition about caches and is covered as its own topic below.
FIFO is still worth knowing for three reasons. It is the baseline every other algorithm is measured against; it is the basis of the second-chance algorithm (FIFO plus a reference bit), which is used in practice; and its failure mode teaches the central lesson of the section — that a good replacement policy must approximate future use, and the only evidence about the future available at run time is recent past use.
Example
FIFO WITH 3 FRAMES
reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2
ref 7 0 1 2 0 3 0 4 2 3 0 3 2
--------------------------------------
f0 7 7 7 2 2 2 2 4 4 4 0 0 0
f1 . 0 0 0 0 3 3 3 2 2 2 2 2
f2 . . 1 1 1 1 0 0 0 3 3 3 3
--------------------------------------
flt F F F F . F F F F F F . . 9 faults
THE CHARACTERISTIC FAILURE
ref 0 saved at t=0, used at every step
|
v
after enough other pages arrive, page 0 reaches the queue head
and is evicted -- despite being the single most-used page.
The next reference faults it back in. FIFO has no way to know.
QUEUE STATE (head is the next victim)
[ oldest | ... | newest ]
^ evicted next, regardless of how hot it is
# FIFO replacement, and a demonstration of its blind spot.
from collections import deque
def fifo(refs, frames):
resident, order, faults = set(), deque(), 0
for page in refs:
if page in resident:
continue # hit: nothing changes, not even order
faults += 1
if len(resident) == frames:
victim = order.popleft() # oldest ARRIVAL, not oldest USE
resident.remove(victim)
resident.add(page)
order.append(page)
return faults
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(fifo(refs, 3)) # 9
# The blind spot: page 0 is referenced constantly, yet keeps being evicted.
hot_loop = [0] + [i for _ in range(5) for i in (1, 2, 3, 0)]
print("FIFO :", fifo(hot_loop, 3))
# FIFO evicts page 0 whenever it ages to the queue head, no matter how
# frequently it has been used since arriving.
Key takeaways
- FIFO evicts the longest-resident page; the implementation is a single queue with no per-access work.
- Arrival time is uncorrelated with future use, so FIFO evicts hot pages that happen to be old.
- FIFO suffers Belady's anomaly: more frames can mean more faults.
- Its value is as a baseline and as the skeleton for second-chance/clock, which fix it by adding a reference bit.
🧪 Practice
- Trace FIFO with 4 frames on the reference string
1 2 3 4 1 2 5 1 2 3 4 5and count the faults. Compare with 3 frames.- Construct a reference string of at least 10 references where FIFO performs at least twice as badly as an LRU policy, and explain the structure that causes it.
- Interview-style: "FIFO needs no hardware support at all. Why is that not enough to make it a good choice?" Hint: consider what runs in the page-fault path versus what runs on every memory reference, and where the real cost of a bad eviction shows up.
Optimal Replacement
Theory
The optimal algorithm (OPT, or MIN, or Belady's algorithm) evicts the page that will not be used for the longest time in the future. It provably produces the minimum possible number of faults for a given reference string and frame count.
It is also unimplementable, because it requires knowing the future. So why study it?
Because it is the yardstick. Without OPT you can tell that algorithm A beats algorithm B, but you cannot tell whether A is close to the best achievable or leaving half the performance on the table. If LRU gives 12 faults and OPT gives 9, LRU is doing well and further tuning has little room. If OPT gives 3, the policy is the problem and it is worth fixing.
OPT is computable offline — record a real reference string, then run OPT over it — which is exactly how replacement algorithms are evaluated in research and in kernel development.
The reasoning behind OPT also justifies every practical algorithm. Since the future is unavailable, algorithms substitute a prediction of it, and essentially all of them predict from recency (recently used implies soon-to-be-used) or frequency (often used implies soon-to-be-used). Both are bets on locality. LRU is the recency bet; LFU is the frequency bet; clock is a cheap approximation of the recency bet. Every one of them is trying to guess the ordering OPT would have known.
One genuinely useful special case: when a program's access pattern is known in advance — a sequential scan of a file, a matrix traversal with a fixed stride, a compiler pass over a syntax tree — the program can tell the kernel via madvise, and the resulting behaviour approaches OPT for that region. Optimal replacement is unattainable in general and quite attainable when the programmer supplies the future.
Example
OPT WITH 3 FRAMES
reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2
At each fault, look FORWARD and evict the page used farthest away
(or never used again).
ref 7 0 1 2 0 3 0 4 2 3 0 3 2
--------------------------------------
f0 7 7 7 2 2 2 2 2 2 2 2 2 2
f1 . 0 0 0 0 0 0 4 4 4 0 0 0
f2 . . 1 1 1 3 3 3 3 3 3 3 3
--------------------------------------
flt F F F F . F . F . . F . . 6 faults
WHY 7 GOES FIRST at t=3: next use of 7 = never
next use of 0 = t=4
next use of 1 = never
-> evict 7 or 1; both never used again
COMPARISON ON THE SAME STRING, 3 FRAMES
OPT 6 faults <- the floor. Nothing can do better.
LRU 9 faults <- 50% above the floor
FIFO 9 faults
USING OPT AS A YARDSTICK
if LRU/OPT ~ 1.1 -> policy is fine, look elsewhere for wins
if LRU/OPT ~ 3.0 -> the policy is genuinely mismatched to this workload
# OPT: computable offline, and the benchmark every real algorithm is
# measured against.
def opt(refs, frames):
resident, faults = [], 0
for i, page in enumerate(refs):
if page in resident:
continue
faults += 1
if len(resident) < frames:
resident.append(page)
continue
# Evict the resident page whose NEXT use is farthest in the future.
def next_use(p):
try:
return refs.index(p, i + 1) # position of the next reference
except ValueError:
return float("inf") # never used again: ideal victim
victim = max(resident, key=next_use)
resident[resident.index(victim)] = page
return faults
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print("OPT :", opt(refs, 3)) # 6 <- the floor for this string
# Use it to judge another policy rather than guessing.
def lru(refs, frames):
resident, faults = [], 0
for page in refs:
if page in resident:
resident.remove(page); resident.append(page) # refresh recency
continue
faults += 1
if len(resident) == frames:
resident.pop(0) # least recent
resident.append(page)
return faults
o, l = opt(refs, 3), lru(refs, 3)
print(f"LRU {l}, OPT {o}, ratio {l/o:.2f}") # LRU 9, OPT 6, ratio 1.50
Key takeaways
- OPT evicts the page whose next use is farthest away and is provably fault-minimal.
- It cannot be implemented online because it requires the future; it is computed offline over a recorded reference string.
- Its role is as a yardstick — the ratio of a real policy to OPT tells you whether tuning the policy is worth the effort.
- Every practical algorithm substitutes a prediction of the future: recency (LRU, clock) or frequency (LFU).
- When the program genuinely knows its access pattern,
madvisehints let real behaviour approach OPT for that region.
🧪 Practice
- Trace OPT with 4 frames on
1 2 3 4 1 2 5 1 2 3 4 5and count faults. Compare against your FIFO answer from the previous topic.- Modify the
optfunction to also return which page it evicted at each fault, then explain in words the rule it applied at the third eviction.- Interview-style: "If OPT is unimplementable, what is it for?" Hint: think about how you would decide whether to spend a month improving a cache policy, and what number would tell you the ceiling.
LRU and Approximations
Theory
If the future is unavailable, use the recent past as a proxy for it. LRU evicts the page that has not been used for the longest time, betting that a page untouched for a while will stay untouched, and a page touched recently will be touched again. That bet is precisely the principle of temporal locality, which is why LRU performs close to OPT on real workloads.
LRU has an elegant theoretical property: it is a stack algorithm. The set of pages resident with n frames is always a subset of the set resident with n+1 frames. That guarantees LRU never suffers Belady's anomaly — more frames can only help.
The problem is implementation cost. LRU must order pages by time of last use, which means doing work on every memory reference, not just on faults. Two textbook implementations:
- Counters. Each PTE holds a timestamp, written by hardware on every access; eviction scans all entries for the minimum. Requires a hardware clock write per reference plus a linear search per fault.
- Stack. A doubly-linked list of page numbers; each reference moves its page to the top. No search on eviction (the victim is the bottom), but six pointer updates per memory reference.
Neither is remotely acceptable in hardware. A pointer update per memory access would dominate the cost of the access itself. No general-purpose CPU implements true LRU for page replacement.
So real systems approximate it, using the one piece of hardware support that is cheap: a reference bit in each PTE, set by the MMU on any access and cleared by the OS. It answers "used since I last asked?" — one bit of recency instead of a full ordering.
From that single bit, three approximations follow:
- Additional-reference-bits. Keep an 8-bit shift register per page; periodically shift the reference bit in from the left and clear it. The byte becomes a coarse history:
11000100was used recently and often,00000001was used once, long ago. Compare bytes as unsigned integers and evict the smallest. This gives roughly 8 levels of recency for one timer interrupt's worth of work. - Second chance. FIFO, but before evicting, check the reference bit: if set, clear it and give the page another pass rather than evicting it. Recently used pages survive; untouched pages are evicted in arrival order.
- Clock. Second chance implemented as a circular buffer, which is the version everyone ships — its own topic next.
Note that LRU has known pathologies of its own. A sequential scan larger than memory evicts everything useful and yields zero hits — the reason real kernels split their lists into active and inactive halves (Linux) or use scan-resistant policies like ARC and CLOCK-Pro.
Example
LRU WITH 3 FRAMES
reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2
ref 7 0 1 2 0 3 0 4 2 3 0 3 2
--------------------------------------
f0 7 7 7 2 2 2 2 4 4 4 0 0 0
f1 . 0 0 0 0 0 0 0 0 3 3 3 3
f2 . . 1 1 1 3 3 3 2 2 2 2 2
--------------------------------------
flt F F F F . F . F F F F . . 9 faults
(OPT: 6, FIFO: 9)
TRUE LRU: WHAT IT COSTS PER MEMORY REFERENCE
counters : write a timestamp into the PTE <- on EVERY access
scan every PTE to find the minimum <- on every fault
stack : unlink + relink a node (6 pointers) <- on EVERY access
verdict : unimplementable in hardware at speed
REFERENCE BIT: ONE BIT, SET BY HARDWARE, FREE
MMU on access: PTE.referenced = 1
OS periodically: read it, then clear it
-> "used since I last looked?" instead of a full ordering
ADDITIONAL REFERENCE BITS (8-bit history, shifted on each timer tick)
page history reading
---- -------- -------------------------------------
A 11000100 used in the last 2 intervals, often -> keep
B 01110111 used heavily but not most recently -> keep
C 00000001 used once, 8 intervals ago -> evict
D 00000000 not used in the last 8 intervals -> evict FIRST
compare as unsigned bytes: smallest value is the victim
# True LRU vs an 8-bit approximation: near-identical results, wildly
# different implementation cost.
def lru_exact(refs, frames):
resident, faults = [], 0 # ordered: [least ... most] recent
for page in refs:
if page in resident:
resident.remove(page) # O(n) here, 6 pointer writes in C
resident.append(page) # ...but on EVERY reference
continue
faults += 1
if len(resident) == frames:
resident.pop(0)
resident.append(page)
return faults
def lru_approx(refs, frames, tick=4):
"""Additional-reference-bits: hardware sets one bit, OS shifts on a timer."""
resident, hist, ref, faults = [], {}, {}, 0
for i, page in enumerate(refs):
if i % tick == 0: # timer interrupt: shift and clear
for p in resident:
hist[p] = (hist[p] >> 1) | (ref[p] << 7) # newest bit on the left
ref[p] = 0 # clear for next interval
if page in resident:
ref[page] = 1 # the ONLY per-access work: one bit
continue
faults += 1
if len(resident) == frames:
victim = min(resident, key=lambda p: (hist[p], p)) # smallest history
resident.remove(victim); hist.pop(victim); ref.pop(victim)
resident.append(page); hist[page] = 0; ref[page] = 1
return faults
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print("exact LRU :", lru_exact(refs, 3)) # 9
print("approx LRU:", lru_approx(refs, 3)) # 9 -- same result, 1 bit of hardware
# Linux does not implement LRU literally: it keeps two lists and promotes
# pages between them, which is scan-resistant in a way strict LRU is not.
grep -E 'Active|Inactive' /proc/meminfo
# Active(anon): 2104332 kB <- recently used anonymous pages
# Inactive(anon): 518220 kB <- candidates for eviction
# Active(file): 1204884 kB
# Inactive(file): 892112 kB <- a big sequential scan lands HERE and is
# reclaimed without evicting the active set
Key takeaways
- LRU predicts the future from recency and performs close to OPT on workloads with temporal locality.
- LRU is a stack algorithm, so it never suffers Belady's anomaly — adding frames can only reduce faults.
- Exact LRU requires work on every memory reference (timestamp or list move), so no CPU implements it.
- Real systems use the hardware reference bit: additional-reference-bit histories, second chance, or clock.
- Strict LRU is vulnerable to sequential scans; Linux's active/inactive lists exist to make eviction scan-resistant.
🧪 Practice
- Trace LRU with 4 frames on
1 2 3 4 1 2 5 1 2 3 4 5and count faults. Compare with FIFO and OPT on the same string.- Given 8-bit histories
10110000,01110000,00001111, and11000000, rank the pages from best victim to worst and justify the ordering.- Interview-style: "Why does no CPU implement true LRU, when caches implement LRU-ish policies all the time?" Hint: compare the number of entries being ordered in an 8-way cache set against the number of resident pages in a 16 GB machine.
Clock Algorithm
Theory
Clock (also called second-chance) is where theory meets shipping code. It is the algorithm that essentially every real operating system uses in some form, because it approximates LRU well while costing almost nothing.
Arrange all resident frames in a circular list, with a single pointer — the "clock hand" — into it. Each frame has a reference bit that the MMU sets on any access. To find a victim:
- Look at the frame under the hand.
- If its reference bit is 0, it has not been touched since the hand last passed. Evict it, put the new page here, set its reference bit, and advance.
- If its reference bit is 1, the page was used recently. Clear the bit and advance the hand, without evicting. The page has been given a second chance.
- Repeat.
The elegance is that clearing the bit sets a deadline: the page survives only if it is touched again before the hand comes around. Frequently used pages keep resetting their bit and are never evicted; a page touched once and abandoned loses its bit on the first pass and is evicted on the second. The hand's rotation period is an implicit recency window that adapts automatically to memory pressure — under heavy pressure the hand sweeps fast and the window shrinks.
The worst case is a full rotation, when every bit is set; but that sweep clears every bit, guaranteeing the next pass finds a victim immediately. So the amortised cost is small.
The standard refinement is the enhanced second-chance algorithm, which considers the reference bit and the dirty bit together, giving four classes:
| (ref, dirty) | Meaning | Priority |
|---|---|---|
| (0, 0) | Not used, not modified | Best victim — evict immediately, no I/O |
| (0, 1) | Not used, but modified | Must be written out first |
| (1, 0) | Recently used, clean | Probably will be used again |
| (1, 1) | Recently used and modified | Worst victim — costs I/O and is hot |
Preferring class (0,0) means most evictions are free — the frame is simply reused with no write-back. This is a large practical win, and it is why kernels also run background write-back to convert (0,1) pages into (0,0) pages before they are ever needed.
Linux's actual reclaim is a descendant of this: two LRU lists (active and inactive) per zone, with pages demoted from active to inactive and reclaimed from the inactive tail, plus reference-bit checks on the way. The structure differs; the principle — cheap approximate recency driven by a hardware bit — is identical.
Example
CLOCK: THE HAND SWEEPS, CLEARING BITS AS IT GOES
Need a victim. Hand starts at frame 0.
[f0 ref=1] -> used recently: CLEAR bit, advance (second chance)
|
[f1 ref=1] -> used recently: CLEAR bit, advance
|
[f2 ref=0] -> NOT used since the hand last passed: EVICT HERE
| new page installed, ref=1, hand advances to f3
[f3 ref=0]
|
[f4 ref=1]
\____________ back to f0 (circular)
STATE BEFORE AND AFTER
before: f0=1 f1=1 f2=0 f3=0 f4=1 hand -> f0
after : f0=0 f1=0 f2=NEW(1) f3=0 f4=1 hand -> f3
^^^^^^^^^^ these must be re-touched before the hand
returns, or they are evicted next time
ENHANCED SECOND CHANCE: FOUR CLASSES, IN VICTIM ORDER
class (0,0) not used, clean -> evict now, ZERO I/O BEST
class (0,1) not used, dirty -> write back, then evict
class (1,0) used, clean -> give a second chance
class (1,1) used, dirty -> leave alone WORST
The hand may take up to TWO passes: first pass clears reference bits,
second pass finds a (0,0) or (0,1) page guaranteed.
# Clock, with the enhanced (reference, dirty) variant.
class Clock:
def __init__(self, frames):
self.frames = [None] * frames # page number in each frame
self.ref = [0] * frames
self.dirty = [0] * frames
self.hand = 0
self.faults = 0
self.writebacks = 0
def access(self, page, writing=False):
if page in self.frames: # HIT: hardware sets the bit
i = self.frames.index(page)
self.ref[i] = 1
if writing:
self.dirty[i] = 1
return
self.faults += 1
i = self._find_victim()
if self.dirty[i]:
self.writebacks += 1 # dirty victim = extra disk I/O
self.frames[i] = page
self.ref[i], self.dirty[i] = 1, 1 if writing else 0
def _find_victim(self):
while True:
if self.frames[self.hand] is None: # free frame available
i = self.hand
self.hand = (self.hand + 1) % len(self.frames)
return i
if self.ref[self.hand] == 0: # not used since last pass
i = self.hand
self.hand = (self.hand + 1) % len(self.frames)
return i
self.ref[self.hand] = 0 # SECOND CHANCE: clear
self.hand = (self.hand + 1) % len(self.frames)
c = Clock(frames=3)
for page in [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]:
c.access(page)
print(c.faults) # 10 -- close to LRU's 9, at a fraction of the cost
# Why the hot page survives: it re-sets its bit before the hand returns.
c2 = Clock(frames=3)
for page in [0] + [p for _ in range(5) for p in (1, 2, 3, 0)]:
c2.access(page)
print(c2.faults)
# Linux's clock-descendant reclaim, observable.
grep -E 'Active|Inactive|Dirty|Writeback' /proc/meminfo
# Dirty: 12844 kB <- class (x,1): needs write-back before eviction
# Writeback: 0 kB <- currently being written
# Background write-back converts dirty pages into cheap (0,0) victims.
sysctl vm.dirty_background_ratio # start writing back at this % of memory
sysctl vm.dirty_ratio # block writers at this % (hard limit)
# Reclaim activity, per second.
sar -B 1 3 # pgscank/s (kswapd scans), pgsteal/s (pages reclaimed)
Key takeaways
- Clock is FIFO around a circular list, with the reference bit granting a second chance to recently used pages.
- Clearing the bit sets a deadline: a page survives only if touched again before the hand returns.
- Worst case is one full sweep, which clears every bit and guarantees the next pass succeeds.
- Enhanced second chance ranks victims by (reference, dirty), preferring clean unused pages so eviction needs no I/O.
- Real kernels ship descendants of clock (Linux's active/inactive lists), never true LRU.
🧪 Practice
- With 4 frames holding pages
A(ref=1) B(ref=0) C(ref=1) D(ref=1)and the hand at A, trace which page is evicted and give the final reference bits.- Extend the
Clockclass to implement the full four-class enhanced algorithm (prefer(0,0), then(0,1)), and compare write-back counts against the simple version on a write-heavy reference string.- Interview-style: "Why does the kernel bother writing dirty pages back in the background when it could just write them at eviction time?" Hint: think about which of the four classes a dirty page belongs to, and what the fault-service path costs when the only available victim needs a write first.
Counting-Based Algorithms
Theory
Recency is one proxy for future use; frequency is the other. Counting algorithms keep a reference counter per page and decide from it.
LFU (least frequently used) evicts the page with the smallest reference count, reasoning that a heavily used page is important. It works well for stable, skewed workloads — a few pages carrying most of the traffic, like a database's hot index blocks.
It has a serious defect: counts remember too much. A page referenced 5,000 times during start-up and never again keeps a count of 5,000 forever, making it effectively immortal while genuinely useful new pages with counts of 3 are evicted around it. This is called cache pollution or count staleness, and the standard fix is ageing: periodically shift all counts right by one, so old references decay exponentially and recent ones dominate.
MFU (most frequently used) evicts the page with the largest count. The argument is that a page with a small count was probably just brought in and has yet to be used, whereas a high-count page has had its turn. It performs poorly in general and is mostly of academic interest — its value is in showing that the obvious inversion of a heuristic is not automatically wrong, just usually.
Neither is common in OS page replacement, for two reasons. Maintaining a counter per page means incrementing on every reference — the same hardware objection that rules out true LRU. And empirically, on the workloads OSes actually see, they do not beat clock by enough to justify the cost.
Frequency does return, though, in hybrid policies where the reference stream is cheaper to observe. ARC (adaptive replacement cache) keeps two lists — pages seen once (recency) and pages seen more than once (frequency) — and adaptively rebalances the space between them based on which is producing hits. LIRS and CLOCK-Pro use reuse distance similarly. These are used where the layer above the OS controls its own cache: database buffer pools, ZFS's ARC, memcached-style caches. The lesson is that recency and frequency are complementary, and the systems that can afford the bookkeeping combine them.
Example
LFU vs LRU ON THE SAME STRING
references: A A A A B C D B C D B C D ... (A hot at first, then never)
LFU: count(A)=4 forever -> A is never evicted, though it is dead
B, C, D fight over the remaining frames and thrash
LRU: A ages out quickly -> B, C, D settle in
LRU wins here because it FORGETS
THE FIX: AGEING (shift counts right on a timer)
tick 0 A=32 B=3 C=4 A dominates
tick 1 A=16 B=5 C=6 A decaying, B/C growing
tick 2 A= 8 B=6 C=7
tick 3 A= 4 B=7 C=8 B and C now outrank the stale A
-> exponential decay makes recent references worth more than old ones
WHEN FREQUENCY BEATS RECENCY
workload: 10,000 pages, 90% of accesses hit the same 100 pages,
interleaved with a long sequential scan of the rest
LRU : the scan evicts the hot 100 (they are 'least recent' between hits)
LFU : the hot 100 have huge counts, the scan pages have count 1 -> survive
ARC : keeps both lists and adapts -> handles both patterns
WHERE EACH IS ACTUALLY USED
OS page replacement : clock (recency, approximate)
database buffer pools : LRU-K, ARC, CLOCK-Pro (recency + frequency)
CDN / object caches : LFU with ageing, TinyLFU
# LFU, its staleness problem, and the ageing fix -- side by side.
def lfu(refs, frames, age_every=None):
resident, count, faults, t = {}, {}, 0, 0
for page in refs:
t += 1
if age_every and t % age_every == 0:
for p in count:
count[p] >>= 1 # AGEING: exponential decay
if page in resident:
count[page] += 1 # per-reference work: the objection
continue
faults += 1
if len(resident) == frames:
# Smallest count wins; ties broken by insertion order.
victim = min(resident, key=lambda p: (count[p], resident[p]))
del resident[victim], count[victim]
resident[page] = t
count[page] = 1
return faults
# A hot start-up page that then goes cold -- LFU's classic failure.
refs = [1] * 20 + [2, 3, 4] * 15
print("LFU no ageing :", lfu(refs, 3)) # page 1 never leaves
print("LFU with ageing:", lfu(refs, 3, age_every=10)) # page 1 decays away
def lru(refs, frames):
resident, faults = [], 0
for page in refs:
if page in resident:
resident.remove(page); resident.append(page); continue
faults += 1
if len(resident) == frames:
resident.pop(0)
resident.append(page)
return faults
print("LRU :", lru(refs, 3))
Key takeaways
- LFU evicts the least-referenced page, betting on frequency rather than recency; MFU inverts it and is mostly academic.
- LFU's flaw is memory of the distant past: a once-hot page stays immortal, polluting the cache.
- Ageing — periodically halving all counts — makes recent references dominate and fixes most of the problem.
- Counting requires per-reference bookkeeping, which is why OS page replacement does not use it.
- Frequency returns in hybrids (ARC, LIRS, CLOCK-Pro, TinyLFU) used by database buffer pools and object caches, where recency and frequency are combined.
🧪 Practice
- Pages have counts A=10, B=2, C=7, D=2 (B arrived before D). Give LFU's victim and MFU's victim, and state which choice you would defend for a database index cache.
- Run the
lfufunction above with and without ageing on a reference string of your own where one page is hot early and dead later; explain the difference in faults.- Interview-style: "Your cache's hit rate collapses every night at 2 a.m. when a batch job scans the whole dataset. Which replacement policy family fixes this, and why?" Hint: the scan touches each page exactly once — ask which signal, recency or frequency, distinguishes those pages from your genuinely hot ones.
Belady's Anomaly
Theory
Every intuition about caching says that more memory cannot hurt. In 1969 Lászlo Bélády showed that for FIFO replacement this is false: there exist reference strings where increasing the number of frames increases the number of page faults.
The canonical example is the string 1 2 3 4 1 2 5 1 2 3 4 5 under FIFO. With three frames it produces 9 faults; with four frames it produces 10.
The reason is that FIFO's eviction order depends on arrival order, and adding a frame changes which pages are resident at each step, in ways that need not be a superset of the smaller configuration. With three frames, a page might be evicted early and re-loaded, which coincidentally puts the queue in a state that serves the next references well. With four frames, a different page survives, the queue is ordered differently, and the algorithm makes worse choices later.
The precise condition is captured by stack algorithms. An algorithm is a stack algorithm if, for every reference string and every n, the set of pages resident with n frames is always a subset of the set resident with n+1 frames. This inclusion property makes anomaly impossible: any page that would have been a hit with n frames is still resident with n+1.
- LRU is a stack algorithm. Its resident set is always the
nmost recently used pages, and thenmost recent are trivially a subset of then+1most recent. - OPT is a stack algorithm, by a similar argument on future distance.
- FIFO is not. Arrival order is not nested in this way.
- Clock is not, strictly, since it inherits FIFO's structure — though anomalies are rare in practice.
Why this matters beyond trivia: it is a warning that "add more resources" is not universally safe reasoning in systems, and it gives you a concrete criterion to check. If a capacity increase makes a cache perform worse, the replacement policy is not a stack algorithm and the anomaly is a real candidate explanation rather than a measurement error.
Example
BELADY'S ANOMALY: 1 2 3 4 1 2 5 1 2 3 4 5 UNDER FIFO
THREE FRAMES FOUR FRAMES
ref 1 2 3 4 1 2 5 1 2 3 4 5 ref 1 2 3 4 1 2 5 1 2 3 4 5
---------------------- ----------------------
f0 1 1 1 4 4 4 5 5 5 5 5 5 f0 1 1 1 1 1 1 5 5 5 5 4 4
f1 . 2 2 2 1 1 1 1 1 3 3 3 f1 . 2 2 2 2 2 2 1 1 1 1 5
f2 . . 3 3 3 2 2 2 2 2 4 4 f2 . . 3 3 3 3 3 3 2 2 2 2
f3 . . . 4 4 4 4 4 4 3 3 3
---------------------- ----------------------
flt F F F F F F F . . F F . flt F F F F . . F F F F F F
9 FAULTS 10 FAULTS <- MORE frames,
MORE faults
THE INCLUSION PROPERTY (why LRU is immune)
LRU with 3 frames: resident = the 3 most recently used
LRU with 4 frames: resident = the 4 most recently used
{3 most recent} is ALWAYS a subset of {4 most recent}
-> every hit at 3 frames is still a hit at 4 frames
FIFO with 3 frames: resident = the 3 most recently ARRIVED
FIFO with 4 frames: resident = the 4 most recently arrived
...but arrivals DIFFER between the two runs, because eviction
history differs -> no nesting -> anomaly possible
ALGORITHM CLASSIFICATION
stack algorithm? anomaly possible?
LRU yes no
OPT yes no
LFU yes no
FIFO NO YES
clock NO yes (rare in practice)
# Reproduce the anomaly, then show LRU is immune to it.
from collections import deque
def fifo(refs, frames):
resident, order, faults = set(), deque(), 0
for page in refs:
if page in resident:
continue
faults += 1
if len(resident) == frames:
resident.remove(order.popleft())
resident.add(page); order.append(page)
return faults
def lru(refs, frames):
resident, faults = [], 0
for page in refs:
if page in resident:
resident.remove(page); resident.append(page); continue
faults += 1
if len(resident) == frames:
resident.pop(0)
resident.append(page)
return faults
refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("frames FIFO LRU")
for f in range(1, 8):
print(f"{f:^6} {fifo(refs, f):^4} {lru(refs, f):^3}")
# frames FIFO LRU
# 1 12 12
# 2 12 12
# 3 9 10
# 4 10 8 <- FIFO: 9 -> 10 going from 3 to 4 frames. ANOMALY.
# 5 5 5 LRU is monotone non-increasing throughout.
# 6 5 5
# Search for anomalies automatically, to see how common they are.
import random
found = 0
for _ in range(2000):
s = [random.randint(1, 6) for _ in range(20)]
if any(fifo(s, n) < fifo(s, n + 1) for n in range(1, 6)):
found += 1
print(f"{found}/2000 random strings show a FIFO anomaly")
Key takeaways
- Belady's anomaly: with FIFO, adding frames can increase faults; the canonical string is
1 2 3 4 1 2 5 1 2 3 4 5. - The cause is that FIFO's resident set with
n+1frames need not contain the resident set withnframes. - Stack algorithms satisfy that inclusion property and are provably anomaly-free.
- LRU, OPT, and LFU are stack algorithms; FIFO and (strictly) clock are not.
- The practical lesson: "more memory always helps" is an assumption to check, not a law.
🧪 Practice
- Verify by hand that
1 2 3 4 1 2 5 1 2 3 4 5gives 9 FIFO faults with 3 frames and 10 with 4, drawing both frame tables.- Run the random search in the code above with different string lengths and alphabet sizes, and report how the anomaly frequency changes.
- Interview-style: "Prove informally that LRU cannot exhibit Belady's anomaly." Hint: characterise exactly which pages LRU holds with n frames at any instant, and ask whether that set is contained in the corresponding set for n+1.
Page Buffering
Theory
Every algorithm so far assumes that when a fault arrives, the kernel picks a victim and, if it is dirty, waits for a disk write before the read can proceed. That serialisation puts two I/O operations on the critical path of a single fault. Page buffering is the set of techniques that get them off it.
A free-frame pool. The kernel maintains a reserve of free frames at all times, refilled in the background by a reclaim daemon (kswapd on Linux, the page daemon on BSD) whenever free memory drops below a low-water mark. When a fault arrives, a frame is available immediately — the read starts at once, and the victim's write-back happens later, off the critical path. This roughly halves worst-case fault latency.
Proactive write-back. A separate mechanism writes dirty pages to disk while the system is idle or lightly loaded, converting (ref=0, dirty=1) pages into (0,0) pages. Cheap victims are then always available. On Linux this is governed by vm.dirty_background_ratio (start writing back) and vm.dirty_ratio (block writers — the hard limit).
Remember the victim's identity. When a page is evicted, keep the frame in the free list but record which page it held and do not clear its contents. If that page is referenced again before the frame is reused, the kernel simply revalidates the mapping — a fault with no I/O at all. This turns some major faults into minor ones, and it rescues genuinely bad eviction decisions cheaply. VAX/VMS used this to compensate for a deliberately simple FIFO policy, which is a nice illustration: a mediocre replacement algorithm plus a good buffering scheme can beat a sophisticated algorithm with none.
Modified-page list. Collect dirty victims into a list, then write them out in batches, sorted for device efficiency. One large sequential write beats many small scattered ones, particularly on rotating media, and it lets the device coalesce and schedule.
The unifying idea: replacement policy decides which page to evict, buffering decides when the associated I/O happens. Separating those two questions is what keeps I/O off the fault path — and it is why the practical difference between clock and LRU matters far less than whether the system has a healthy free-frame pool.
Example
WITHOUT BUFFERING: TWO I/Os SERIALISED ON THE FAULT PATH
fault -> pick victim -> victim dirty? -> WRITE (90 us) -> READ (90 us) -> resume
|------------------------ 180+ us blocked -----------------------|
WITH BUFFERING: THE WRITE LEAVES THE CRITICAL PATH
fault -> take a frame from the free pool -> READ (90 us) -> resume
|------------------ 90 us blocked --------------|
meanwhile, in the background:
kswapd : scan, evict, refill the free pool (asynchronous)
flusher : write dirty pages out (asynchronous)
THE WATER MARKS THAT DRIVE IT
free memory
high |---------------------- kswapd sleeps
|
low |---------------------- kswapd WAKES, reclaims until high
|
min |---------------------- direct reclaim: allocating processes
| must reclaim themselves. THIS is what
v a latency spike looks like.
REMEMBERING THE VICTIM: A MAJOR FAULT BECOMES FREE
evict page P from frame f -> f joins the free list, CONTENTS INTACT,
tagged "was P"
P referenced again before f is reused
-> no I/O at all: just re-point the PTE at f and mark it valid
-> a bad eviction decision costs microseconds, not milliseconds
# Free-frame pool plus victim-remembering: turning major faults into minor ones.
class BufferedPager:
def __init__(self, frames, pool_target=2):
self.resident = {} # page -> frame
self.free = [f"f{i}" for i in range(frames)]
self.ghost = {} # frame -> page it USED to hold
self.pool_target = pool_target
self.major = self.minor = 0
def access(self, page):
if page in self.resident:
return # hit
# Was this page's old frame recycled yet? If not, no I/O needed.
for frame, old in list(self.ghost.items()):
if old == page and frame in self.free:
self.free.remove(frame)
self.resident[page] = frame
del self.ghost[frame]
self.minor += 1 # MINOR fault: contents still there
return
if not self.free:
self._reclaim(1) # synchronous: this is the bad case
frame = self.free.pop(0)
self.ghost.pop(frame, None) # contents now genuinely discarded
self.resident[page] = frame
self.major += 1 # MAJOR fault: real disk read
self._background_reclaim() # keep the pool topped up
def _reclaim(self, n):
for _ in range(n):
if not self.resident:
return
victim = next(iter(self.resident))
frame = self.resident.pop(victim)
self.ghost[frame] = victim # REMEMBER what was here
self.free.append(frame)
def _background_reclaim(self):
if len(self.free) < self.pool_target: # low-water mark reached
self._reclaim(self.pool_target - len(self.free))
p = BufferedPager(frames=4)
for page in [1, 2, 3, 4, 5, 1, 2, 6, 1, 2]:
p.access(page)
print(f"major (disk I/O): {p.major}, minor (free): {p.minor}")
# Pages re-referenced shortly after eviction cost nothing.
# The free-frame pool and its water marks.
cat /proc/zoneinfo | grep -E 'zone |min |low |high |free '
# Node 0, zone Normal
# pages free 412883
# min 11264 <- below this: direct reclaim (latency spikes)
# low 16891 <- below this: kswapd wakes
# high 22518 <- reclaim until here, then sleep
# Reclaim work: pgscank/s is kswapd (background, good),
# pgscand/s is direct reclaim in an allocating process (bad).
sar -B 1 5
# Make the background flusher more aggressive so dirty pages are cheap victims.
sysctl vm.dirty_background_ratio=5
sysctl vm.dirty_expire_centisecs=1500
Key takeaways
- Page buffering separates "which page to evict" from "when the I/O happens", keeping disk writes off the fault path.
- A background-refilled free-frame pool means a fault always finds a frame immediately, roughly halving worst-case latency.
- Proactive write-back converts dirty pages into clean, zero-cost victims before they are needed.
- Remembering a victim's identity lets a re-referenced page be reclaimed with no I/O, turning major faults into minor ones.
- Good buffering can compensate for a mediocre replacement policy — VAX/VMS paired FIFO with exactly these techniques.
🧪 Practice
- A fault takes 90 us to read and 90 us to write back a dirty victim. Compute average fault latency when 40% of victims are dirty, with and without a free-frame pool.
- Inspect
/proc/zoneinfoon your machine, note the min/low/high watermarks, and explain what user-visible symptom appears when free memory crosses each one.- Interview-style: "VAX/VMS used a simple FIFO policy and still performed well. How?" Hint: think about what happens to a wrongly evicted page in the seconds before its frame is actually reassigned to something else.
<a id="83-frame-management"></a>
8.3 Frame Management
Replacement decides which page leaves; allocation decides how many frames each process gets in the first place. This section covers the floor imposed by hardware, the two philosophies for dividing frames among processes, and what changes when memory itself has a topology.
Minimum Number of Frames
Theory
A process cannot be given arbitrarily few frames. There is a hard floor, and it is set by the instruction set, not by policy.
The reason is instruction restart. When an instruction faults, it is re-executed from the beginning. If executing that instruction requires touching more distinct pages than the process owns frames, then satisfying the last reference necessarily evicts a page needed by an earlier one — and the instruction faults forever. The process makes no progress at all. So:
The minimum number of frames per process is the maximum number of distinct pages a single instruction can reference.
Counting that maximum means counting worst cases in the ISA:
- The instruction itself may straddle a page boundary: 2 pages.
- Each memory operand may straddle a boundary: 2 pages each.
- Indirect addressing multiplies this. A single-level indirect load touches the instruction, the pointer, and the target — and each may straddle: 6 pages. Some architectures allowed multi-level indirection, which is unbounded in principle, so they capped the chain depth precisely to keep the minimum finite.
The classic worst case is the IBM 370's MVC (move characters), which copies up to 256 bytes memory-to-memory: instruction (2) + source (2) + destination (2) = 6 frames minimum. On x86-64, a rep movsb or an instruction with a complex addressing mode gives a similar small number; practical minimums are around 8 to 16 frames.
The maximum is simply the number of frames installed. Between the floor and the ceiling sits allocation policy, and it is worth being clear that the floor is about correctness (progress is impossible below it) while everything above is about performance (too few frames means thrashing, Section 8.4). Operating systems enforce the floor absolutely and treat everything above as tunable.
Example
WHY THE FLOOR EXISTS: AN INSTRUCTION THAT CANNOT COMPLETE
Instruction: MVC dest, src (copy 256 bytes, memory to memory)
Process has 3 frames.
pages this ONE instruction touches:
instruction, bytes 0..3 page A ]
instruction, bytes 4..5 page B ] straddles a boundary
source start page C
source end page D ] straddles
dest start page E
dest end page F ] straddles
-> 6 distinct pages
With 3 frames:
fault on A -> load A (evicts something)
fault on C -> load C (evicts A!)
fault on A -> load A (evicts C!)
... forever. The instruction NEVER completes. No progress, no error.
COUNTING THE WORST CASE
component pages note
---------------------------- ----- ---------------------------
instruction 2 may straddle a page boundary
operand 1 (direct) 2 may straddle
operand 2 (direct) 2 may straddle
+ one level of indirection +2 the pointer itself
---------------------------- -----
IBM 370 MVC worst case 6
with indirect addressing 8+ (why ISAs cap indirection depth)
THE RANGE
minimum (ISA-defined) ---- policy decides here ---- maximum (installed)
~6-16 frames all of memory
below this: NO PROGRESS above: performance tuning only
# Compute the ISA-imposed floor from the instruction format.
def minimum_frames(instr_bytes, operands, indirection_levels=0,
page_size=4096, max_operand_bytes=256):
"""Worst case: everything straddles a page boundary."""
pages = 2 if instr_bytes > 1 else 1 # the instruction itself
for _ in range(operands):
pages += 2 # each operand may straddle
pages += 2 * indirection_levels # each pointer may straddle
return pages
print(minimum_frames(6, operands=2)) # 6 IBM 370 MVC
print(minimum_frames(6, operands=2, indirection_levels=1)) # 10 with indirection
print(minimum_frames(15, operands=2)) # 6 x86-64 worst case
def can_make_progress(frames, need):
return frames >= need
for f in (3, 6, 8):
print(f"{f} frames: progress on MVC? {can_make_progress(f, 6)}")
# 3 frames: progress on MVC? False <- infinite fault loop
# 6 frames: progress on MVC? True
# 8 frames: progress on MVC? True
Key takeaways
- The minimum frames per process equals the maximum number of distinct pages one instruction can reference; below it, the instruction faults forever.
- The count comes from the instruction straddling a page, each operand straddling, and each level of indirection adding more.
- IBM 370's
MVCgives the classic answer of 6; practical modern minimums are roughly 8 to 16. - Architectures cap indirection depth specifically to keep this minimum finite.
- The floor is a correctness requirement; everything above it is a performance decision.
🧪 Practice
- An architecture has 4-byte instructions, two memory operands, and supports two levels of indirection. Compute the minimum frames, showing each contribution.
- Explain what a process with fewer than the minimum frames looks like from outside: CPU usage, fault counters, and progress. Why is it not reported as an error?
- Interview-style: "Why does the instruction set determine a memory-management parameter?" Hint: start from what the CPU must do after a page fault, and ask what that requires of every page the instruction touches.
Global vs Local Allocation
Theory
When a process faults and needs a frame, whose frame may it take? Two answers, with quite different system-level behaviour.
Local replacement. A process may only evict its own pages. Its frame count is fixed by whatever allocation it was given. Consequences: a process's performance depends only on its own behaviour and is therefore reproducible — the same program with the same input faults the same number of times regardless of what else is running. But a process cannot exploit idle memory: if it is thrashing at 50 frames while 2,000 frames sit unused in an idle process, it stays at 50.
Global replacement. A faulting process may take a frame from any process. Consequences: memory flows to whoever needs it, so utilisation and total throughput are usually higher. But a process's fault behaviour now depends on everyone else's. The same program can run in 2 seconds or 40 depending on its neighbours, which makes performance unpredictable and debugging maddening. Worse, global replacement enables a cascade: one memory-hungry process steals frames from others, pushing them into faulting, so they steal frames in turn — the mechanism by which a single process drags an entire system into thrashing.
| Local | Global | |
|---|---|---|
| Victim pool | Only the faulting process's pages | Any process's pages |
| Frame count per process | Fixed | Varies dynamically |
| Performance predictability | High — depends only on itself | Low — depends on neighbours |
| Memory utilisation | Poor: idle frames stay idle | High: frames flow to demand |
| Overall throughput | Usually lower | Usually higher |
| Thrashing containment | Contained to the offender | Spreads system-wide |
| Typical use | Real-time, containers, VMs, per-cgroup limits | General-purpose default |
In practice, systems use global replacement with guard rails, which is the most useful thing to take away. Linux reclaims globally but adds: per-cgroup memory limits (memory.max) that make reclaim local to a container, mlock to pin pages that must never be evicted, OOM-killer scoring to terminate the worst offender rather than let everything degrade, and vm.swappiness to bias between evicting file pages and anonymous pages.
That combination is the modern answer: global by default for utilisation, with local boundaries drawn where isolation matters — exactly the boundary a container or a latency-sensitive service needs.
Example
THE SAME FAULT, TWO POLICIES
Before: P1 has 20 frames (thrashing), P2 has 200 (idle, mostly untouched)
LOCAL GLOBAL
P1 faults -> must evict one of P1 faults -> may take a frame from
its OWN 20 pages P2's idle 200
P1 stays at 20 frames P1 grows: 20 -> 21 -> ... -> 60
P1 keeps thrashing P1 stops thrashing
P2 keeps 200 idle frames P2 shrinks to what it actually uses
-> memory WASTED -> memory USED
...but the global downside:
P3 (a batch job) starts scanning a 50 GB file
global : P3 steals frames from the latency-sensitive P1 and P2,
which then fault, and steal in turn -> SYSTEM-WIDE THRASHING
local : P3 thrashes alone inside its own allocation, everyone else
is unaffected -> the damage is CONTAINED
THE MODERN COMPROMISE: GLOBAL INSIDE, LOCAL AT THE BOUNDARY
+-- cgroup: web (memory.max = 4 GB) --+ +-- cgroup: batch (max = 2 GB) --+
| global reclaim among its processes | | global reclaim among its own |
| P1 P2 P3 | | P9 |
+-------------------------------------+ +--------------------------------+
reclaim NEVER crosses this boundary: batch cannot steal from web
# Global vs local, on the same workload, showing both effects.
class Allocator:
def __init__(self, total_frames, policy="global"):
self.total = total_frames
self.policy = policy
self.frames = {} # pid -> frames held
self.faults = {}
def add(self, pid, initial):
self.frames[pid] = initial
self.faults[pid] = 0
def fault(self, pid, needed):
"""A process wants more frames than it holds."""
self.faults[pid] += 1
if self.frames[pid] >= needed:
return
if self.policy == "local":
return # cannot grow: keeps faulting
# Global: take from whoever has the most (crudely: the biggest holder)
donor = max((p for p in self.frames if p != pid),
key=lambda p: self.frames[p], default=None)
if donor and self.frames[donor] > 1:
self.frames[donor] -= 1
self.frames[pid] += 1 # frames flow toward demand
for policy in ("local", "global"):
a = Allocator(220, policy)
a.add("P1_needs_60", 20)
a.add("P2_idle", 200)
for _ in range(100):
a.fault("P1_needs_60", needed=60)
print(f"{policy:7}: P1={a.frames['P1_needs_60']:3} frames, "
f"P2={a.frames['P2_idle']:3}, P1 faults={a.faults['P1_needs_60']}")
# local : P1= 20 frames, P2=200, P1 faults=100 <- starved beside idle memory
# global : P1= 60 frames, P2=160, P1 faults=100 <- but it reached its target
# Draw a local boundary around a workload with cgroups v2.
mkdir -p /sys/fs/cgroup/batch
echo 2G > /sys/fs/cgroup/batch/memory.max # hard limit: reclaim stays inside
echo 1G > /sys/fs/cgroup/batch/memory.high # throttle before the hard limit
echo $$ > /sys/fs/cgroup/batch/cgroup.procs
# Per-cgroup reclaim pressure -- who is actually under memory stress.
cat /sys/fs/cgroup/batch/memory.pressure
# some avg10=12.44 avg60=8.91 avg300=3.02 total=...
# 'some' rising = tasks are stalling on memory. This is the early warning.
# Pin pages that must never be evicted (needs privileges / RLIMIT_MEMLOCK).
# In code: mlock(addr, len) or mlockall(MCL_CURRENT | MCL_FUTURE)
Key takeaways
- Local replacement confines a process to its own frames: predictable performance, but idle memory stays idle.
- Global replacement lets frames flow to demand: better utilisation and throughput, at the cost of predictability.
- Under global replacement one greedy process can drag the whole system into thrashing; local replacement contains the damage.
- Real systems are global by default with local boundaries where isolation matters — cgroup limits,
mlock, OOM scoring. - Choose local when reproducibility or isolation is the requirement (real-time, containers, multi-tenant), global otherwise.
🧪 Practice
- Two processes need 100 frames each; 150 are available. Describe the outcome under local allocation (75 each) and under global, and state which produces better total throughput and why.
- Set a
memory.maxon a cgroup, run a memory-hungry process inside it, and observememory.pressureand the process's fault counters. Explain what changes compared to running it unconfined.- Interview-style: "A batch job runs and your latency-sensitive service's p99 triples, though CPU is fine. What is the mechanism and what would you configure?" Hint: identify which resource the batch job is taking that does not show up in CPU metrics, and what boundary would stop it crossing.
Proportional Allocation
Theory
Under local replacement — or under global replacement with per-group limits — the OS must decide how many frames each process gets. There are three approaches, in increasing sophistication.
Equal allocation. Divide m available frames among n processes: m/n each. Simple and obviously fair by one definition, and obviously wrong by another: a 10 KB utility and a 2 GB database get identical allocations. The small process wastes most of what it receives; the large one thrashes.
Proportional allocation. Give each process a share proportional to its size:
a_i = (s_i / S) × m where s_i = size of process i, S = sum of all s_i
A process with 10 times the address space gets 10 times the frames. Every allocation is clamped to at least the ISA minimum from the previous topic, and the total is capped at m.
Proportional allocation is better, but it uses the wrong variable. Size is a static property; what determines fault behaviour is the working set — how many pages a process is actively touching right now. A 2 GB process looping over a 4 MB array needs 4 MB of frames, not a proportional share of memory. And a process's needs change over its lifetime: start-up, steady state, and shutdown have different demands.
Priority-weighted and dynamic allocation. Weight the share by priority as well as size (a high-priority process gets more frames, so it faults less and finishes sooner), and recompute periodically as sizes and priorities change. Under global replacement, a high-priority process can also be permitted to take frames from lower-priority ones — the frame-allocation analogue of CPU priority.
The honest summary: static allocation formulas are a starting point, and the feedback-driven schemes in Section 8.4 — working-set tracking and page-fault-frequency control — are what actually work, because they measure demand rather than estimating it from size.
Example
62 FRAMES, TWO PROCESSES: s1 = 10 pages, s2 = 127 pages
EQUAL : 31 and 31
P1 wastes 21 frames (it only has 10 pages!)
P2 gets 31 of the 127 it might want -> thrashes
PROPORTIONAL : a1 = (10/137) x 62 = 4 -> raised to the ISA minimum
a2 = (127/137) x 62 = 57
much better fit to actual size
PRIORITY-WEIGHTED (P1 is high priority, weight 3; P2 weight 1)
w1 = 3 x 10 = 30, w2 = 1 x 127 = 127
a1 = (30/157) x 62 = 11
a2 = (127/157) x 62 = 50
WHY SIZE IS THE WRONG VARIABLE
process virtual size ACTUAL working set proportional gives
------------ ------------ ------------------ ------------------
JVM service 2 GB 180 MB way too much
scan utility 12 MB 12 MB about right
sparse matrix 8 GB 40 MB absurdly too much
-> allocate on MEASURED demand (working set, Section 8.4),
not on declared size
# The three allocation formulas, side by side, with the ISA floor enforced.
def equal(sizes, frames, minimum=6):
n = len(sizes)
return {p: max(frames // n, minimum) for p in sizes}
def proportional(sizes, frames, minimum=6):
total = sum(sizes.values())
alloc = {p: max(int(s / total * frames), minimum) for p, s in sizes.items()}
# Enforcing the minimum can overshoot; trim from the largest holders.
while sum(alloc.values()) > frames:
biggest = max(alloc, key=lambda p: alloc[p])
if alloc[biggest] <= minimum:
break
alloc[biggest] -= 1
return alloc
def priority_weighted(sizes, priorities, frames, minimum=6):
weights = {p: sizes[p] * priorities[p] for p in sizes}
total = sum(weights.values())
return {p: max(int(w / total * frames), minimum) for p, w in weights.items()}
sizes = {"P1": 10, "P2": 127}
priorities = {"P1": 3, "P2": 1}
print("equal :", equal(sizes, 62))
print("proportional:", proportional(sizes, 62))
print("priority :", priority_weighted(sizes, priorities, 62))
# equal : {'P1': 31, 'P2': 31}
# proportional: {'P1': 6, 'P2': 55}
# priority : {'P1': 11, 'P2': 50}
# The flaw, made explicit: allocation by size vs allocation by demand.
virtual = {"jvm": 2048, "scanner": 12, "sparse": 8192}
working_set = {"jvm": 180, "scanner": 12, "sparse": 40}
prop = proportional(virtual, 1000)
for p in virtual:
print(f"{p:8} size {virtual[p]:5} MB, needs {working_set[p]:4} MB, "
f"proportional gives {prop[p]:4}")
# sparse gets ~790 frames for a 40 MB working set: 95% of it wasted.
Key takeaways
- Equal allocation ignores size and simultaneously starves large processes and wastes frames on small ones.
- Proportional allocation scales the share by process size, clamped below by the ISA minimum.
- Size is a static proxy for the real quantity: the working set, which is dynamic and often far smaller.
- Priority weighting lets important processes fault less; under global replacement they can also take frames from lower-priority processes.
- Feedback-driven schemes (working set, page-fault frequency) beat all static formulas because they measure demand.
🧪 Practice
- Allocate 100 frames among processes of 20, 50, and 130 pages using equal and proportional allocation, with a minimum of 8 frames. Show the arithmetic.
- Extend
priority_weightedso a process never receives more frames than its size, and explain why that clamp is needed.- Interview-style: "Why do modern kernels not use proportional allocation by process size?" Hint: consider a process that maps a 100 GB file but reads 1 MB of it, and ask what its size tells you about its frame needs.
NUMA-Aware Allocation
Theory
Everything so far has treated physical memory as uniform: any frame is as good as any other. On multi-socket servers and modern many-core chips this is false, and the difference is large enough to matter more than most replacement-policy tuning.
In a NUMA (non-uniform memory access) system, memory is physically attached to specific CPU sockets. A core can access all memory, but memory attached to its own socket (local) is reached directly, while memory attached to another socket (remote) must cross an interconnect — UPI on Intel, Infinity Fabric on AMD. Remote access typically costs 1.5x to 2.5x the latency of local access, and remote bandwidth is limited by the interconnect rather than by the memory controllers.
So which frame you allocate now determines how fast every subsequent access to it will be, for as long as that page lives. Frame allocation becomes a placement decision, not just a bookkeeping one.
The standard policies:
- First-touch (the default on Linux). A page is allocated on the node of the CPU that first writes to it — not the one that called
malloc. This is usually right, because the thread that initialises data is usually the one that uses it. It also produces a classic bug: a program that allocates and initialises a large array in a single-threaded start-up phase puts the whole array on one node, and then all worker threads on every node access it remotely. The fix is to parallelise initialisation with the same thread/data mapping used later. - Interleave. Spread pages round-robin across nodes. This gives up locality in exchange for using every memory controller's bandwidth. It is right for large shared structures accessed by all threads, where nothing would be local anyway.
- Bind / preferred. Force allocations to specific nodes. Used for pinned, latency-critical workloads such as databases and virtual machines, usually alongside CPU pinning.
There is also a replacement dimension: when memory pressure arrives, should the kernel reclaim locally (evict a local page, keep the allocation local) or allocate remotely (keep the page, accept slower access)? vm.zone_reclaim_mode controls this, and the right answer depends on whether the workload is latency-bound or capacity-bound. Linux also does automatic NUMA balancing, periodically unmapping pages to sample which node is touching them and migrating pages toward their users.
The general lesson: on a NUMA machine, where a frame is can matter as much as whether you have one. Chapter 4's scheduling discussion of NUMA and this one are the same problem seen from two sides — the scheduler places threads near their memory, and the allocator places memory near its threads.
Example
TWO-SOCKET NUMA MACHINE
+---------- Node 0 ----------+ +---------- Node 1 ----------+
| cores 0-15 | UPI | cores 16-31 |
| +----------------------+ |<====== | +----------------------+ |
| | local RAM (128 GB) | |======> | | local RAM (128 GB) | |
| +----------------------+ | | +----------------------+ |
+----------------------------+ +----------------------------+
core 0 -> node 0 memory : ~80 ns (local)
core 0 -> node 1 memory : ~140 ns (remote, ~1.75x)
THE FIRST-TOUCH BUG
BAD GOOD
main thread: each worker thread:
buf = malloc(64 GB) buf = malloc(64 GB)
for i in all: buf[i] = 0 parallel for MY range: buf[i] = 0
-> ALL pages land on node 0 -> each range lands on the node
spawn workers on both nodes of the thread that will use it
-> node 1 workers: 100% REMOTE -> ~100% LOCAL access
POLICY SELECTION
policy places pages right for
----------- --------------------- --------------------------------
first-touch node of first writer thread-private data (the default)
interleave round-robin all nodes big shared structures, bandwidth-bound
bind named nodes only pinned DBs, VMs, real-time
preferred named node, may spill soft affinity
/* First-touch done right: initialise data from the thread that will use it.
Compile: gcc -fopenmp numa.c */
#include <omp.h>
#include <stdlib.h>
#define N (1L << 30)
int main(void) {
double *a = malloc(N * sizeof(double)); /* reserves; touches nothing */
/* WRONG: single-threaded init puts every page on ONE node.
for (long i = 0; i < N; i++) a[i] = 0.0; */
/* RIGHT: the SAME schedule used by the compute loop, so each thread
first-touches exactly the pages it will later read and write. */
#pragma omp parallel for schedule(static)
for (long i = 0; i < N; i++)
a[i] = 0.0; /* page lands on THIS thread's node */
#pragma omp parallel for schedule(static) /* identical schedule = local access */
for (long i = 0; i < N; i++)
a[i] = a[i] * 2.0 + 1.0;
free(a);
return 0;
}
# The machine's topology and per-node distances.
numactl --hardware
# node 0 cpus: 0-15 node 0 size: 128000 MB
# node 1 cpus: 16-31 node 1 size: 128000 MB
# node distances: 0: 10 21 1: 21 10 <- 2.1x cost for remote
# Run pinned to one node, memory included (best latency).
numactl --cpunodebind=0 --membind=0 ./latency_sensitive_app
# Spread pages across nodes for bandwidth-bound work.
numactl --interleave=all ./bandwidth_bound_app
# Diagnose: hits are local, misses are remote.
numastat -p $(pgrep -f myapp)
# Node 0 Node 1
# Private 8204.11 102.33 <- heavily skewed = a first-touch bug
perf stat -e node-loads,node-load-misses ./app
# Let the kernel migrate pages toward the threads using them.
sysctl kernel.numa_balancing=1
Key takeaways
- On NUMA systems memory is attached to sockets; remote access costs roughly 1.5x to 2.5x local, so frame placement determines lasting performance.
- First-touch (the Linux default) allocates on the node of the CPU that first writes the page.
- The classic bug is single-threaded initialisation of a large array, which strands all pages on one node.
- Interleaving trades locality for aggregate bandwidth and suits large shared structures; binding suits pinned latency-critical workloads.
- Reclaim policy interacts with placement (
zone_reclaim_mode), and automatic NUMA balancing migrates pages toward their users.
🧪 Practice
- Local access is 80 ns and remote is 140 ns. Compute average access time when 30% of accesses are remote, and the speedup from making them all local.
- Run
numactl --hardwareandnumastatfor a running process on any multi-socket machine (or read the files under/sys/devices/system/node/). Interpret the per-node distribution.- Interview-style: "A parallel program scales well to 16 threads and then gets slower at 32 on a two-socket box. Name a memory-placement cause." Hint: at 32 threads the second socket comes into play — ask where the data was allocated and by which thread.
<a id="84-performance-concerns"></a>
8.4 Performance Concerns
Demand paging fails in one characteristic way, and this section covers the failure, the theory that explains it, the two control schemes that prevent it, and the two places the kernel's own memory needs break the paging model entirely.
Thrashing
Theory
Thrashing is the pathology of virtual memory: a system spending more time servicing page faults than executing instructions. It is worth studying carefully because its symptoms invert normal intuition — CPU utilisation falls while the disk saturates, and the system's own corrective reflex makes it worse.
The mechanism, step by step:
- A process has too few frames for its working set, so it faults frequently.
- Each fault blocks it on I/O, so it is not runnable.
- Many processes in this state means few runnable processes, so CPU utilisation drops.
- The OS observes idle CPU and concludes it can run more work, so it increases the degree of multiprogramming by admitting another process.
- The new process needs frames, which it takes (under global replacement) from processes already short of them.
- Fault rates rise further. Go to step 2.
That positive feedback loop is what makes thrashing collapse rather than degrade. Throughput does not decline gently as load rises; it climbs to a peak and then falls off a cliff, because the system's response to the early symptoms is exactly the wrong one.
From the outside it looks like: near-zero CPU utilisation, 100% disk utilisation, a fault rate in the thousands per second, load average climbing, and a machine that will not even respond to a keystroke. A crucial diagnostic point is that the system is not idle and not deadlocked — it is fully occupied doing work that produces nothing.
The cures follow from the mechanism:
- Reduce the degree of multiprogramming. Suspend or terminate processes so the rest have working-set-sized allocations. This is what an OOM killer does, bluntly.
- Use local replacement or per-cgroup limits. Confine the damage so one process cannot pull others in.
- Give the processes enough frames. Working-set tracking and page-fault-frequency control (the next two topics) do this automatically.
- Add memory, if the aggregate working set genuinely exceeds RAM. No policy can fix a workload that does not fit.
The modern form is a container hitting its memory limit: the same feedback, bounded by the cgroup, ending with the OOM killer inside that cgroup instead of a system-wide collapse.
Example
THE THRASHING CLIFF
CPU
util
100% | ___
| ___/ \
| __/ \
75% | _/ \
| _/ \
50% | _/ \
| / \
25% | / \____
| / \_______________
0% +----------------------------------------------> degree of
low optimal THRASHING multiprogramming
BEGINS
Past the peak, adding a process REDUCES throughput. The OS's usual
reflex -- "CPU is idle, admit more work" -- drives it further right.
THE FEEDBACK LOOP
too few frames --> high fault rate --> processes blocked on I/O
^ |
| v
frames taken from others <-- admit more <-- CPU looks IDLE
\______________________________________/
SYMPTOM TABLE: DISTINGUISHING THRASHING FROM OTHER STALLS
symptom thrashing CPU-bound I/O-bound (normal) deadlock
---------------- ---------- ---------- ------------------ --------
CPU utilisation very LOW ~100% low-moderate ~0%
disk utilisation ~100% low high ~0%
major faults/sec thousands ~0 low 0
swap in AND out both high ~0 ~0 0
load average climbing ~= cores moderate flat
progress none yes yes none
# The feedback loop, simulated: throughput peaks and then collapses.
def simulate(processes, total_frames=1000, working_set=120):
"""CPU utilisation and throughput as the multiprogramming level rises."""
frames_each = total_frames / processes
# Fault rate explodes once a process holds fewer frames than its working set.
if frames_each >= working_set:
fault_rate = 1e-6 # negligible: fits comfortably
else:
shortfall = (working_set - frames_each) / working_set
fault_rate = 1e-6 * (1 + 5000 * shortfall ** 3) # superlinear blow-up
fault_service_us = 100 # NVMe
# Fraction of time each process spends blocked on faults.
blocked = min(fault_rate * fault_service_us * 1000, 0.999)
runnable = processes * (1 - blocked)
cpu_util = min(runnable, 1.0)
throughput = cpu_util / max(1, processes) * processes
return cpu_util, throughput, fault_rate
print(" procs frames CPU util fault rate")
for n in (2, 4, 8, 9, 10, 12, 16, 24):
util, tput, fr = simulate(n)
bar = "#" * int(util * 40)
print(f" {n:3} {1000//n:5} {util:6.1%} {fr:9.2e} {bar}")
# procs frames CPU util fault rate
# 2 500 100.0% 1.00e-06 ########################################
# 8 125 100.0% 1.00e-06 ########################################
# 10 100 100.0% 1.05e-05 ########################################
# 12 83 73.4% 1.65e-04 #############################
# 16 62 18.9% 9.32e-04 #######
# 24 41 6.2% 3.31e-03 ## <- collapsed
# Diagnosing thrashing: the signature is si+so both high with CPU idle.
vmstat 1
# procs -----------memory---------- ---swap-- -----io---- --system-- ------cpu-----
# r b swpd free buff cache si so bi bo in cs us sy id wa st
# 0 14 892144 20112 1024 40128 4820 5104 21044 20880 8912 15k 2 6 4 88 0
# ^^^^^^ swap used ^^^^^^^^^^ paging BOTH ways ^^^^^^^^ id low, wa HIGH
# Pressure stall information: the cleanest early-warning signal.
cat /proc/pressure/memory
# some avg10=64.21 avg60=48.03 avg300=22.17 <- tasks stalling on memory
# full avg10=41.88 ... <- EVERYTHING stalled
# Contain it before it spreads.
systemd-run --scope -p MemoryMax=2G ./memory_hungry_job
Key takeaways
- Thrashing is a system spending more time paging than computing; it is driven by a positive feedback loop, not by gradual degradation.
- The signature is low CPU utilisation with saturated disk and high fault rates — the opposite of what "busy" normally looks like.
- The loop is closed by the OS's own reflex: idle CPU leads it to admit more processes, which worsens the shortage.
- Cures: reduce multiprogramming, confine with local allocation or cgroup limits, size frames by working set, or add memory.
vmstat's si/so columns and/proc/pressure/memoryare the practical diagnostics.
🧪 Practice
- Given
vmstatoutput showingsi=3200 so=3500 id=3 wa=91, diagnose the state and name three actions in priority order.- Explain precisely why increasing the degree of multiprogramming when CPU utilisation is low is correct for I/O-bound workloads and catastrophic during thrashing.
- Interview-style: "How would you distinguish a thrashing system from one that is merely I/O-bound?" Hint: both show high disk utilisation and low CPU — look for the counter that only appears when memory is the constraint, and check whether pages are moving in both directions.
Working Set Model
Theory
Thrashing happens when a process holds fewer frames than it actively needs. To prevent it, you need to quantify "actively needs" — and that is what Peter Denning's working set model, from 1968, provides.
Define a parameter Δ, the working-set window, measured in memory references. The working set of a process at time t is:
WS(t) = the set of distinct pages referenced in the interval (t - Δ, t]
Its size, WSS, is the number of frames the process needs right now to avoid faulting. The core insight is that this set is observable: it is a measurement of recent behaviour, not an estimate from process size.
The model's prescription follows immediately. Let D = Σ WSS_i be the total demand across all processes. Then:
- If
D <= m(available frames), everyone's working set fits and the system is healthy. - If
D > m, thrashing is guaranteed — the demand cannot be met by any policy.
So the OS monitors each process's WSS, sums them, and if the total exceeds memory, suspends a process and reclaims its frames for the rest. That is the thrashing cure applied preventively, driven by measurement.
Choosing Δ is the model's one tuning decision, and it matters:
- Too small: the window misses pages that are part of the current locality, WSS is underestimated, and the process is under-allocated and faults.
- Too large: the window includes pages from a previous locality, WSS is overestimated, and frames are wasted.
- About right: Δ spans one locality — typically 10,000 to a few hundred thousand references.
The underlying phenomenon is that programs move through localities: a phase where they touch one clustered set of pages (a function and its data, a loop over an array), then transition to another. Working set size is stable within a locality and jumps at transitions. Faults cluster at those transitions and are unavoidable there — the goal is to avoid faults within a phase.
Exact tracking is too expensive (it needs the reference string), so implementations approximate with a timer and reference bits: every 5,000 references, shift each page's reference bit into a small history and treat any page with a bit set in the last few intervals as in the working set. Same idea as the additional-reference-bits approximation of LRU, applied to sizing rather than eviction.
Example
WORKING SET WITH DELTA = 10 REFERENCES
reference string:
...2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 4 4 1 3 2 3 4 4 4 3 4 4 4...
|------------ t1 ------------|
|------------ t2 ------|
WS(t1) = {1, 2, 5, 6, 7} WSS = 5
WS(t2) = {3, 4} WSS = 2 <- a locality transition happened
LOCALITY PHASES OVER A PROGRAM'S LIFETIME
WSS
| ____ _______
| ____/ \______ / \___
| / \____ _____/ \___
| / V \
+--------------------------------------------------> time
startup parse compute write out exit
^ ^ ^ ^
locality transitions: faults CLUSTER here and are unavoidable
THE ADMISSION RULE
D = sum of all WSS_i m = available frames
D <= m -> healthy: everyone's active pages fit
D > m -> THRASHING IS CERTAIN: suspend a process, reclaim its frames
CHOOSING DELTA
delta too small WS misses part of the locality -> under-allocated, faults
delta correct WS = exactly the current locality
delta too large WS includes the PREVIOUS locality -> frames wasted
# Working set: measure it, sum it, and apply the admission rule.
def working_set(refs, t, delta):
"""Distinct pages referenced in the window (t-delta, t]."""
return set(refs[max(0, t - delta):t])
refs = [2,6,1,5,7,7,7,7,5,1,6,2,3,4,1,2,3,4,4,4,3,4,4,4,1,3,2,3,4,4,4,3,4,4,4]
for t in (10, 20, 30, 35):
ws = working_set(refs, t, delta=10)
print(f"t={t:2} WS={sorted(ws)} WSS={len(ws)}")
# t=10 WS=[1, 2, 5, 6, 7] WSS=5
# t=20 WS=[1, 2, 3, 4, 6] WSS=5 <- mid-transition
# t=30 WS=[1, 2, 3, 4] WSS=4
# t=35 WS=[3, 4] WSS=2 <- settled into the new locality
# The admission decision, which is the model's actual purpose.
def admission_check(working_set_sizes, available_frames):
D = sum(working_set_sizes.values())
if D <= available_frames:
return f"OK: demand {D} <= {available_frames} frames"
# Suspend the largest consumer until demand fits.
order = sorted(working_set_sizes, key=lambda p: -working_set_sizes[p])
suspended, remaining = [], D
for p in order:
if remaining <= available_frames:
break
suspended.append(p)
remaining -= working_set_sizes[p]
return f"THRASHING: demand {D} > {available_frames}. Suspend {suspended}"
print(admission_check({"P1": 40, "P2": 35, "P3": 30}, 120))
print(admission_check({"P1": 40, "P2": 90, "P3": 30}, 120))
# OK: demand 105 <= 120 frames
# THRASHING: demand 160 > 120 frames. Suspend ['P2']
# Approximating WSS cheaply with reference bits on a timer.
def wss_approx(refs, delta=10, interval=5, history_bits=2):
"""A page is 'in the working set' if referenced in the last few intervals."""
hist, ws_over_time = {}, []
for t, page in enumerate(refs):
hist.setdefault(page, 0)
hist[page] |= 1 # reference bit set
if t % interval == 0 and t:
for p in hist:
hist[p] = (hist[p] << 1) & ((1 << history_bits) - 1) # shift+clear
ws_over_time.append(sum(1 for p in hist if hist[p]))
return ws_over_time
print(wss_approx(refs)) # WSS estimate per interval, using 2 bits per page
# Approximate a process's working set by watching its resident set settle.
pidstat -r -p $(pgrep -f myapp) 1 10 # RSS over time; plateaus = localities
# Idle page tracking gives a genuine working-set measurement on Linux.
# (Set the idle bitmap, wait, then read which pages were touched.)
ls /sys/kernel/mm/page_idle/bitmap
# Per-cgroup working-set pressure, without instrumenting the program.
cat /sys/fs/cgroup/myapp/memory.stat | grep -E 'workingset|pgmajfault'
Key takeaways
- The working set is the set of distinct pages referenced in the last Δ references; its size WSS is the frames the process needs now.
- The admission rule: if the summed demand
Dexceeds available framesm, thrashing is certain — suspend a process. - Δ must span one locality: too small under-allocates, too large wastes frames.
- Programs move through localities; WSS is stable within a phase and jumps at transitions, where faults unavoidably cluster.
- Exact tracking is impractical, so implementations approximate with timer interrupts and reference-bit histories.
🧪 Practice
- For the string
1 2 3 4 1 2 5 1 2 3 4 5with Δ = 5, compute the working set and WSS at t = 5, t = 8, and t = 12.- Three processes have WSS 25, 40, and 30 with 80 frames available. Apply the admission rule and state exactly which action the OS should take.
- Interview-style: "How would you size a container's memory limit for a service you did not write?" Hint: think about what to measure over a full workload cycle, why a single peak reading is misleading, and what headroom the page cache needs.
Page-Fault Frequency Control
Theory
The working set model is theoretically clean but awkward to implement: it requires tracking a moving window of references for every process. Page-fault frequency (PFF) control reaches the same goal by a more direct route — it skips the model and measures the symptom.
The reasoning is simple. Thrashing is a high fault rate. Rather than computing working sets to predict faults, measure the fault rate and adjust frames until it lands in an acceptable range:
- Set an upper threshold and a lower threshold on faults per second.
- If a process's fault rate exceeds the upper threshold, it has too few frames. Give it more.
- If it falls below the lower threshold, it has more frames than it needs. Take some away and give them to a process that needs them.
- If no free frames exist when a process needs more, suspend a process and redistribute its frames.
This is a classic feedback controller, and it has the practical virtues of one: it needs only a per-process fault counter (which the kernel keeps anyway), it adapts automatically to phase changes, and it requires no model of the program's behaviour.
The design points are the ones any control loop has. The gap between thresholds must be wide enough to prevent oscillation — frames added and removed repeatedly around a single set point. The measurement interval must be long enough to be statistically meaningful and short enough to react before a fault storm builds. And adjustments should be gradual, since a process that just changed locality will show a transient spike that resolves itself.
Comparing the two schemes:
| Working set | Page-fault frequency | |
|---|---|---|
| Measures | Distinct pages referenced in Δ | Faults per unit time |
| Requires | Reference tracking per page | A fault counter per process |
| Acts | Preventively (before faults) | Reactively (after faults) |
| Handles locality shifts | Predicts the new WSS | Sees the fault spike, then adapts |
| Implementation cost | Higher | Low |
| Used in practice | Approximations only | Widely, in this shape |
Real kernels use PFF-shaped feedback rather than either textbook scheme literally. Linux's reclaim adjusts scanning pressure based on observed reclaim efficiency, cgroup v2's memory.high throttles a group whose reclaim rate is too high, and PSI (pressure stall information) exposes stall time directly — the modern signal, since it measures the thing that actually harms users.
Example
PFF AS A FEEDBACK LOOP
fault
rate
| upper threshold
| ....*.................................................. TAKE ACTION:
| . * ADD FRAMES
| . *
| . ** acceptable band
| . ****
| ..............*****.................................... lower threshold
| **** REMOVE FRAMES
+------------------------------------------------------> time
^ locality change ^ frames added, rate falls back into band
THE CONTROL RULES
rate > upper -> allocate more frames to this process
rate < lower -> reclaim frames from it, give them to someone needier
in band -> do nothing
need frames but none free -> SUSPEND a process, redistribute
HYSTERESIS: WHY TWO THRESHOLDS, NOT ONE
single threshold at 100 f/s:
99 -> take a frame -> 105 -> give it back -> 99 -> ... OSCILLATION
band of 50..150:
drifts inside the band without action; adjustments are rare and damped
# A PFF controller, including the hysteresis band and the suspend path.
class PFFController:
def __init__(self, total_frames, upper=150, lower=50, step=8):
self.free = total_frames
self.frames = {}
self.upper, self.lower, self.step = upper, lower, step
self.suspended = []
def add_process(self, pid, initial=16):
self.frames[pid] = initial
self.free -= initial
def adjust(self, pid, fault_rate):
if fault_rate > self.upper: # starving: needs frames
if self.free >= self.step:
self.frames[pid] += self.step
self.free -= self.step
return f"{pid}: +{self.step} frames (rate {fault_rate})"
donor = self._find_donor(pid)
if donor:
self.frames[donor] -= self.step
self.frames[pid] += self.step
return f"{pid}: +{self.step} taken from {donor}"
victim = self._suspend() # nothing left to take
return f"{pid}: no frames available -> SUSPENDED {victim}"
if fault_rate < self.lower and self.frames[pid] > 16:
self.frames[pid] -= self.step # over-provisioned
self.free += self.step
return f"{pid}: -{self.step} frames (rate {fault_rate})"
return f"{pid}: in band, no action" # hysteresis: do nothing
def _find_donor(self, exclude):
candidates = [p for p in self.frames if p != exclude and self.frames[p] > 24]
return max(candidates, key=lambda p: self.frames[p], default=None)
def _suspend(self):
victim = max(self.frames, key=lambda p: self.frames[p])
self.free += self.frames.pop(victim) # its frames go to the pool
self.suspended.append(victim)
return victim
c = PFFController(total_frames=200)
for pid in ("P1", "P2", "P3"):
c.add_process(pid, initial=40)
print(c.adjust("P1", fault_rate=400)) # P1: +8 frames (rate 400)
print(c.adjust("P2", fault_rate=10)) # P2: -8 frames (rate 10)
print(c.adjust("P3", fault_rate=100)) # P3: in band, no action
print(c.adjust("P1", fault_rate=900)) # P1: +8 taken from P2/P3, or a suspend
# The modern signal: stall time, not fault counts.
cat /proc/pressure/memory
# some avg10=0.00 avg60=0.12 avg300=0.31 <- some tasks stalled on memory
# full avg10=0.00 ... <- ALL tasks stalled
# cgroup v2 implements exactly this feedback: throttle above memory.high,
# so a group is slowed rather than allowed to thrash the machine.
echo 3G > /sys/fs/cgroup/myapp/memory.high # soft: reclaim + throttle
echo 4G > /sys/fs/cgroup/myapp/memory.max # hard: OOM kill
# Per-process fault rate: the raw input to any such controller.
pidstat -r -p $(pgrep -f myapp) 1
# UID PID minflt/s majflt/s VSZ RSS %MEM Command
# 1000 4412 1204.0 88.3 2.1G 980M 6.1 myapp
# ^^^^ sustained majflt/s is the number that matters
Key takeaways
- PFF control measures the symptom (fault rate) rather than modelling the cause (working set), and adjusts frames accordingly.
- Above the upper threshold, give a process more frames; below the lower one, take some away; if none are free, suspend a process.
- Two thresholds provide hysteresis, preventing oscillation around a single set point.
- It needs only a fault counter per process, which is why real systems use this shape rather than literal working-set tracking.
- Modern equivalents are cgroup
memory.highthrottling and PSI, which measure stall time — closer to what users actually experience.
🧪 Practice
- Thresholds are upper = 100 and lower = 30 faults/sec. Give the controller's action for processes reporting 250, 60, and 12 faults/sec.
- Explain what happens with a single threshold instead of a band, and construct a fault-rate sequence that oscillates.
- Interview-style: "Would you alert on page-fault rate or on PSI memory pressure for a production service?" Hint: consider which one changes meaning when you swap a hard disk for NVMe, and which one is measured in units of harm to the user.
Memory-Mapped Files
Theory
Virtual memory's machinery — demand paging, page replacement, dirty tracking — is not only useful for anonymous memory. Applied to files, it produces an entirely different I/O interface.
Memory mapping associates a region of a process's virtual address space with a file. After mmap, the file's contents are the memory: reading a byte at the mapped address reads that byte of the file, and writing to it modifies the file. No read, no write, no explicit buffer.
The mechanism is exactly demand paging with the file as backing store. The mapping starts with no pages resident. The first access to any page faults; the kernel reads that page of the file into a frame and maps it. Subsequent accesses are plain memory accesses at hardware speed. Dirty pages are written back to the file by the same flusher that handles anonymous pages.
The advantages over read/write:
- No copying.
read()copies from the kernel's page cache into your buffer.mmapmaps the page-cache frame straight into your address space — the data exists once. - No system calls in the steady state. After the mapping is established, access is ordinary loads and stores. A tight loop over a mapped file makes no syscalls at all.
- Sharing is automatic. Two processes mapping the same file
MAP_SHAREDmap the same frames — the fastest IPC available (Chapter 2's shared memory, backed by a file). - Lazy and partial. Mapping a 100 GB file costs nothing; only the pages touched are read.
- Natural random access. No
lseek, just pointer arithmetic.
The costs and hazards are real and worth stating:
- I/O errors become signals. A
read()returns-1witherrno. A bad page in a mapping raisesSIGBUS, which most programs do not handle. - Faults are invisible. A pointer dereference that costs 8 ms does not look like I/O in the code, which makes latency profiling harder.
- Truncation is dangerous. If another process truncates the file, touching the mapped region beyond the new end raises
SIGBUS. - Not always faster. For a single sequential pass,
read()with a large buffer can beatmmap, because it avoids per-page faults and TLB pressure.mmapwins for random access, repeated access, and sharing.
The flag that changes everything is MAP_SHARED versus MAP_PRIVATE: shared mappings write through to the file and are visible to others; private mappings are copy-on-write, so writes create private copies and never touch the file. That is how executables are mapped — text shared read-only, data private COW.
Example
read/write vs mmap
READ MMAP
+-------------+ +-------------+
| user buffer | <-- COPY --+ | user vaddr |--+
+-------------+ | +-------------+ |
| | mapped directly
+-------------------------------+ +-------------------------------+
| page cache (kernel) | | page cache (kernel) |
+-------------------------------+ +-------------------------------+
^ ^
| disk read | demand-paged
+---------+ +---------+
| file | | file |
+---------+ +---------+
two copies, one syscall per call one copy, ZERO syscalls after setup
MAP_SHARED vs MAP_PRIVATE
MAP_SHARED : writes go to the FILE and are visible to other mappers
-> IPC, databases, writing through a mapping
MAP_PRIVATE : writes trigger COW, creating a private copy
-> executable .data segments, read-mostly configuration
HOW A PROGRAM IS LOADED -- IT IS ALL MMAP
text -> mmap(file, PROT_READ|PROT_EXEC, MAP_PRIVATE) shared frames
data -> mmap(file, PROT_READ|PROT_WRITE, MAP_PRIVATE) COW
bss -> mmap(anonymous, zero-fill-on-demand)
heap -> mmap(anonymous) / brk
-> exec() reads NO program bytes: every page arrives by demand fault
WHEN TO USE WHICH
access pattern better choice why
----------------------- ------------- ---------------------------
one sequential pass read() no fault-per-page overhead
random access mmap no lseek, only touched pages
repeated access mmap page cache serves it directly
shared between processes mmap same frames, zero copies
very large file, sparse mmap lazily paged
needs errno-style errors read() mmap gives you SIGBUS
/* Memory-mapped file I/O: after mmap, file access is pointer arithmetic. */
#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
int main(void) {
int fd = open("data.bin", O_RDWR);
struct stat st;
fstat(fd, &st);
/* MAP_SHARED: writes go through to the file and to other mappers. */
char *map = mmap(NULL, st.st_size, PROT_READ | PROT_WRITE,
MAP_SHARED, fd, 0);
if (map == MAP_FAILED) { perror("mmap"); return 1; }
close(fd); /* the mapping keeps its own reference */
printf("%c\n", map[0]); /* first touch -> PAGE FAULT -> disk read */
printf("%c\n", map[1]); /* same page -> no fault, ~1 ns */
map[4096] = 'X'; /* second page -> fault, then marked DIRTY */
msync(map, st.st_size, MS_SYNC); /* force write-back NOW (durability) */
munmap(map, st.st_size); /* unmap; dirty pages flushed later */
return 0;
}
# mmap in Python: the same mechanism, and a demonstration that only
# touched pages become resident.
import mmap, os
with open("large.bin", "wb") as f: # create a 256 MB file
f.truncate(256 * 1024 * 1024)
def rss_mb():
with open("/proc/self/statm") as f:
return int(f.read().split()[1]) * os.sysconf("SC_PAGE_SIZE") / 2**20
with open("large.bin", "r+b") as f:
mm = mmap.mmap(f.fileno(), 0) # map the whole file
print(f"after mmap 256 MB : {rss_mb():6.1f} MB") # unchanged: lazy
total = 0
for off in range(0, len(mm), 4096 * 256): # touch 1 page per MB
total += mm[off] # each first touch = one fault
print(f"after sparse touch: {rss_mb():6.1f} MB") # only touched pages
mm[0:5] = b"HELLO" # write through to the file
mm.flush() # msync
mm.close()
with open("large.bin", "rb") as f:
print(f.read(5)) # b'HELLO' -- the file changed
os.remove("large.bin")
Key takeaways
mmapmaps a file into the address space so file access becomes ordinary memory access, demand-paged by the same machinery.- It avoids the copy that
read/writeperforms and eliminates system calls in the steady state. MAP_SHAREDwrites through to the file and shares frames between processes;MAP_PRIVATEis copy-on-write.- Program loading is entirely
mmap:execreads no bytes, and text pages are shared across all processes running the binary. - Trade-offs: I/O errors arrive as
SIGBUS, latency hides inside pointer dereferences, and a single sequential pass may be faster withread.
🧪 Practice
- Explain what happens, page by page, when a process maps a 10 GB file and reads bytes at offsets 0, 100, and 5,000,000,000. How many faults and how much resident memory?
- Write the
mmapflags for: a read-only configuration file, a shared counter between two processes, and a private scratch buffer. Justify each.- Interview-style: "When is
read()the better choice overmmap?" Hint: think about a single front-to-back pass over a huge file, and count the per-page costsmmapincurs that a large buffered read does not.
Kernel Memory Allocation
Theory
Everything so far has described how the kernel manages user memory. The kernel's own allocations follow different rules, and understanding why explains the two specialised allocators in the next topic.
Four constraints separate kernel memory from user memory:
1. Much of it must be physically contiguous. A device performing DMA writes to physical addresses; it does not go through the MMU (or, with an IOMMU, goes through a different one). A driver's DMA buffer must therefore occupy consecutive physical frames. Page tables cannot paper over this, so external fragmentation of physical memory is a real problem for the kernel in a way it is not for user processes.
2. Most of it cannot be paged out. Kernel data structures are used in contexts where a page fault would be fatal — inside interrupt handlers, while holding a spinlock, in the page-fault path itself. A fault there could deadlock the system. So kernel memory is generally pinned, meaning it is a hard commitment against physical RAM.
3. The allocations are small and repetitive. The kernel constantly allocates and frees small, fixed-size objects: task_struct (a few KB), inode, dentry, socket buffers, file descriptors. Millions per second on a busy server. Rounding each to a page would waste enormously; a general-purpose allocator's per-allocation overhead would dominate.
4. Failure is not an option in the same way. A user allocation failure returns NULL and the program copes. A kernel allocation failure in a critical path may mean a panic, so the kernel keeps reserves and has emergency pools.
Linux exposes this in its API, and reading it tells you which constraint applies:
| Function | Contiguity | Use |
|---|---|---|
kmalloc(size, flags) | Physically contiguous | Small allocations, DMA-capable |
vmalloc(size) | Virtually contiguous only | Large buffers where physical contiguity is unnecessary |
alloc_pages(order) | Whole physical pages, contiguous | Page-granular allocations |
kmem_cache_alloc(cache) | From a slab of same-sized objects | Frequent fixed-size objects |
The flags argument carries the context: GFP_KERNEL may sleep (so it can reclaim), GFP_ATOMIC must not sleep (interrupt context — it dips into emergency reserves and fails fast), GFP_DMA restricts to memory a device can reach.
These constraints — physical contiguity, no paging, small repetitive objects — are precisely what the buddy system and slab allocator were designed for.
Example
WHY THE KERNEL IS DIFFERENT
constraint user memory kernel memory
---------------------- -------------------- --------------------------
physical contiguity never needed (MMU) REQUIRED for DMA
pageable yes mostly NO (fault = deadlock)
allocation sizes KB to GB tens of BYTES, millions/sec
allocation failure returns NULL may PANIC
fragmentation matters external: solved external: REAL PROBLEM again
kmalloc vs vmalloc
kmalloc(8192) vmalloc(8192)
virtual : [ page A ][ page B ] virtual : [ page A ][ page B ]
physical: [ f100 ][ f101 ] physical: [ f512 ][ f7 ]
^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^
CONTIGUOUS -> DMA-safe scattered -> NOT DMA-safe
limited by fragmentation always succeeds if frames
exist anywhere
ALLOCATION CONTEXT DECIDES THE FLAG
process context, may block -> GFP_KERNEL (can reclaim, can sleep)
interrupt handler -> GFP_ATOMIC (must not sleep; uses reserves)
device-reachable memory -> GFP_DMA (address-range restricted)
Using GFP_KERNEL in an interrupt handler is a classic kernel bug:
it may sleep, and sleeping in interrupt context deadlocks the CPU.
/* Kernel allocation, and what each choice commits you to.
(Kernel-module code -- shown for the API, not to be compiled in user space.) */
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/gfp.h>
struct my_dev {
dma_addr_t dma_handle;
void *dma_buf;
char *big_scratch;
};
int setup(struct my_dev *d, struct device *dev) {
/* DMA buffer: MUST be physically contiguous and device-reachable. */
d->dma_buf = dma_alloc_coherent(dev, 64 * 1024, &d->dma_handle, GFP_KERNEL);
if (!d->dma_buf)
return -ENOMEM;
/* A big scratch buffer no device will touch: physical contiguity is
unnecessary, so vmalloc avoids stressing the buddy allocator. */
d->big_scratch = vmalloc(4 * 1024 * 1024);
if (!d->big_scratch) {
dma_free_coherent(dev, 64 * 1024, d->dma_buf, d->dma_handle);
return -ENOMEM;
}
return 0;
}
void interrupt_path(void) {
/* In interrupt context: GFP_ATOMIC. It will NOT sleep, may use emergency
reserves, and is more likely to fail -- so the caller must handle NULL. */
char *buf = kmalloc(128, GFP_ATOMIC);
if (!buf)
return; /* fail fast; never block here */
kfree(buf);
}
# What the kernel is actually holding.
grep -E 'Slab|SReclaimable|SUnreclaim|KernelStack|PageTables|VmallocUsed' /proc/meminfo
# Slab: 412880 kB <- small object caches
# SReclaimable: 301224 kB <- dentry/inode caches, reclaimable under pressure
# SUnreclaim: 111656 kB <- genuinely pinned kernel data
# KernelStack: 18432 kB <- one stack per thread, never paged
# PageTables: 88320 kB <- the tables themselves cost memory
# Physical contiguity availability -- kmalloc of large sizes depends on this.
cat /proc/buddyinfo
# trailing zeros at high orders = large contiguous allocations will FAIL
# Which kernel object types dominate.
sudo slabtop -o | head -12
Key takeaways
- Kernel memory often must be physically contiguous (DMA) and mostly cannot be paged out (faults in critical sections would deadlock).
- Kernel allocations are dominated by small, fixed-size, extremely frequent objects —
task_struct,inode,dentry, socket buffers. kmallocgives physical contiguity for DMA;vmallocgives only virtual contiguity but tolerates fragmentation.- Allocation flags encode context:
GFP_KERNELmay sleep,GFP_ATOMICmust not,GFP_DMArestricts the address range. - These constraints motivate the buddy system (contiguous physical blocks) and the slab allocator (fast fixed-size objects).
🧪 Practice
- For each, choose
kmalloc,vmalloc, or a slab cache and justify: a 32-byte network header, a 4 MB decompression buffer, a DMA ring for a NIC, a per-processtask_struct.- Read
/proc/meminfoon your machine and compute what fraction of RAM the kernel holds in Slab, KernelStack, and PageTables combined.- Interview-style: "Why can't the kernel simply page out its own data structures like it does user memory?" Hint: imagine the page-fault handler itself faulting, or a fault occurring while a spinlock is held with interrupts disabled.
Buddy System and Slab Allocation
Theory
Two allocators, layered, solve the two kernel problems from the previous topic. The buddy system manages physically contiguous page blocks; the slab allocator sits on top and manages small objects.
The buddy system allocates in blocks of 2^k pages ("order k"). To satisfy a request, it finds the smallest free block that fits; if that block is larger than needed, it splits it in half repeatedly until the right size is reached. The two halves of a split are called buddies. On free, if a block's buddy is also free, they merge back into a block of the next order, and the merge cascades upward.
The trick that makes it fast is address arithmetic. Two buddies differ in exactly one bit of their address — the one corresponding to their size — so finding a block's buddy is a single XOR:
buddy_address = block_address XOR block_size
Coalescing is therefore O(1) per level, with no searching. That is why the buddy system is the kernel's answer to physical external fragmentation.
Its cost is internal fragmentation: rounding to a power of two wastes up to 50% in the worst case. A 33 KB request consumes a 64 KB block (order 4 at 4 KB pages). Acceptable for page-level allocations, ruinous for a 32-byte object — which is why a second layer exists.
The slab allocator solves the small-object problem. For each frequently used object type, it keeps a cache: pre-allocated slabs (contiguous page runs from the buddy allocator) divided into slots of exactly that object's size, with a free list threaded through them. Allocation pops a slot; free pushes it back. Both are O(1) with no splitting, no searching, and no rounding to powers of two.
Three further wins:
- No internal fragmentation — the slot is exactly the object size, so
inodeobjects pack perfectly into their slabs. - Constructor reuse. Freed objects retain their initialised state, so re-allocating one skips the constructor. Linux exploits this for lock and list-head initialisation.
- Cache locality. Objects of the same type sit adjacent in memory, so traversing them is cache-friendly, and per-CPU free lists remove lock contention on the fast path.
Slabs live in three states — full, partial, empty — and allocation prefers partial slabs to keep memory dense. Empty slabs are returned to the buddy allocator under memory pressure, which is why SReclaimable in /proc/meminfo counts as available memory.
Linux has had three implementations: SLAB (the original, with elaborate per-CPU queues), SLUB (the current default — simpler, less metadata, better on many-core machines), and SLOB (minimal, for tiny embedded systems). The idea is Jeff Bonwick's, from Solaris in 1994, and it is now near-universal — user-space allocators like tcmalloc and jemalloc use the same size-class-plus-free-list structure.
Example
BUDDY SYSTEM: SPLIT DOWN, MERGE UP
Start: one free 1024 KB block. Request 100 KB -> rounds up to 128 KB.
1024 [------------ 1024 free ------------]
split [---- 512 ----][---- 512 free ----]
split [-256-][-256 -][---- 512 free ----]
split [128][128][-256][---- 512 free ----]
allocate [USE][128][-256][---- 512 free ----]
^^^ 128 KB block for a 100 KB request
(28 KB internal fragmentation)
FREEING, WITH XOR COALESCING
free the 128 KB block at address A
buddy = A XOR 128K <- one XOR, no search
buddy free? -> merge into a 256 KB block
its buddy free? -> merge into 512 KB
its buddy free? -> merge into 1024 KB
Cascading merge, O(1) per level.
WORST-CASE INTERNAL FRAGMENTATION
request 65 KB -> 128 KB block -> 49% wasted
-> fine for pages, hopeless for a 32-byte inode. Hence slabs.
SLAB ALLOCATOR: ONE CACHE PER OBJECT TYPE
kmem_cache "inode_cache" (object size 576 B, slab = 4 pages = 16 KB)
FULL slabs [XXXXXXXXXXXXXXXXXXXXXXXXXXXX] all 28 slots in use
PARTIAL slabs [XXXXXXXXXX....XXXX..........] <- allocate from HERE
EMPTY slabs [............................] <- return to buddy
under pressure
alloc: pop the free list of a partial slab O(1), no rounding
free : push it back, keeping the constructed state
THE TWO LAYERS TOGETHER
kmem_cache_alloc(inode_cache) <- 576 B, exact, O(1)
| needs a new slab?
v
alloc_pages(order=2) <- 4 contiguous pages from the buddy system
|
v
physical frames
# Buddy system: splitting, and coalescing via XOR.
class BuddyAllocator:
def __init__(self, total_pages):
self.max_order = total_pages.bit_length() - 1
# free_lists[k] holds addresses of free blocks of 2^k pages.
self.free_lists = {k: set() for k in range(self.max_order + 1)}
self.free_lists[self.max_order].add(0)
self.allocated = {}
def allocate(self, pages):
order = max(0, (pages - 1).bit_length()) # round UP to 2^k
for k in range(order, self.max_order + 1):
if not self.free_lists[k]:
continue
addr = self.free_lists[k].pop()
while k > order: # split down to size
k -= 1
buddy = addr + (1 << k) # the upper half
self.free_lists[k].add(buddy)
self.allocated[addr] = order
waste = (1 << order) - pages
return addr, order, waste
return None, None, None
def free(self, addr):
order = self.allocated.pop(addr)
while order < self.max_order:
buddy = addr ^ (1 << order) # THE XOR TRICK
if buddy not in self.free_lists[order]:
break # buddy busy: stop merging
self.free_lists[order].remove(buddy)
addr = min(addr, buddy) # merged block's address
order += 1 # cascade upward
self.free_lists[order].add(addr)
b = BuddyAllocator(1024)
a1, o1, w1 = b.allocate(100) # 100 pages -> order 7 (128 pages)
a2, o2, w2 = b.allocate(30) # 30 pages -> order 5 (32 pages)
print(f"alloc 100 -> order {o1}, wasted {w1} pages") # order 7, wasted 28
print(f"alloc 30 -> order {o2}, wasted {w2} pages") # order 5, wasted 2
b.free(a1); b.free(a2)
print("largest free block after coalescing:",
max(k for k, s in b.free_lists.items() if s)) # 10 -> fully merged
# Slab allocator: exact-size slots, O(1) alloc/free, state preserved.
class SlabCache:
def __init__(self, name, obj_size, slab_pages=4, page_size=4096):
self.name, self.obj_size = name, obj_size
self.per_slab = (slab_pages * page_size) // obj_size # exact packing
self.slabs = [] # each: list of free slot indices
self.stats = {"allocs": 0, "slabs_created": 0}
def alloc(self):
for slab in self.slabs: # prefer a PARTIAL slab
if slab["free"]:
self.stats["allocs"] += 1
return slab["free"].pop()
slab = {"free": list(range(self.per_slab))} # none partial: new slab
self.slabs.append(slab) # from the buddy allocator
self.stats["slabs_created"] += 1
self.stats["allocs"] += 1
return slab["free"].pop()
def free(self, slot):
# Object keeps its constructed state; re-allocation skips the constructor.
self.slabs[0]["free"].append(slot)
inode_cache = SlabCache("inode_cache", obj_size=576)
print(f"objects per slab: {inode_cache.per_slab}") # 28
for _ in range(100):
inode_cache.alloc()
print(inode_cache.stats) # {'allocs': 100, 'slabs_created': 4}
# 100 objects x 576 B = 57,600 B in 4 slabs of 16 KB = 65,536 B
# Internal fragmentation: only the slab tail, not per object.
# The buddy allocator's free lists, per order (order n = 2^n pages).
cat /proc/buddyinfo
# Node 0, zone Normal 4812 2201 980 310 88 12 3 0 0 0 0
# ^order 0 (4 KB) ^order 10 (4 MB)
# Zeros at high orders: large contiguous kmalloc will fail.
# The slab caches, by memory used.
sudo slabtop -o | head -8
# OBJS ACTIVE USE OBJ SIZE SLABS CACHE SIZE NAME
# 412k 398k 96% 0.19K 9821 78M dentry
# 188k 181k 96% 0.57K 6714 107M inode_cache
# 24k 23k 95% 7.06K 6021 172M task_struct
cat /proc/slabinfo | head -5 # the raw per-cache statistics
Key takeaways
- The buddy system allocates power-of-two page blocks, splitting on demand and merging free buddies on release.
- Buddy addresses differ in one bit, so coalescing is a single XOR — O(1), no searching.
- Its cost is internal fragmentation of up to 50%, acceptable for pages and unacceptable for small objects.
- The slab allocator layers on top: per-type caches of exact-size slots with free lists, giving O(1) allocation, no rounding, and preserved constructor state.
- Slabs are full, partial, or empty; empty slabs return to the buddy allocator, which is why reclaimable slab counts as available memory.
- Linux ships SLUB by default; the same size-class design appears in
tcmallocandjemallocin user space.
🧪 Practice
- A buddy allocator starts with 1 MB. Trace requests of 70 KB, 35 KB, and 80 KB: give the block size allocated, the internal fragmentation, and the free-list state after each.
- Two 128 KB buddies sit at addresses
0x40000and0x60000. Verify with the XOR rule whether they are buddies, and give the merged block's address and size.- Interview-style: "Why does the kernel need both a buddy allocator and a slab allocator?" Hint: compute what a 192-byte
dentrywould cost if allocated directly from a power-of-two page allocator, then multiply by the hundreds of thousands live on a busy system.
<a id="9-storage-systems"></a>