Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 23, Arpaci-Dusseau & Arpaci-Dusseau

Complete Virtual Memory Systems

Page tables, TLBs, and replacement policies are the core. A complete VM system also needs performance tricks, real address-space layout, and security.

Crux: what else is needed? How do features improve performance, functionality, or security?

We look at two designs: VAX/VMS [LL82] (many ideas still live on) and Linux (phones to datacenters — the curse of generality).

VAX/VMS

DEC VAX-11: 32-bit VA, 512-byte pages (23-bit VPN + 9-bit offset). Top VPN bits select segments — a paging + segmentation hybrid.

Region	Role
P0	User code + heap (grows down)
P1	User stack (grows up)
S	System / kernel (shared across processes)

Tiny pages → huge linear tables. Mitigations:

Separate PTs for P0 and P1 — no table for the unused middle
User page tables in kernel virtual memory (S) — can be swapped under pressure

Translation may consult the system page table before the user PTE; the hardware TLB usually hides that cost.

Real address space

Page 0 invalid — null-pointer dereference → invalid PTE → trap (segfault if unhandled)
Kernel mapped into every process — switch P0/P1 only; S stays. Easy copy_from_user, swap of page-table pages, kernel as a “protected library”
Privilege in PTE protection bits — user mode cannot touch kernel pages

Page replacement without a reference bit

VAX PTE: valid, protect, modify, OS-reserved, PFN — no use bit.

Segmented FIFO [RL81]: each process has an RSS cap; pages on a per-process FIFO. On overflow, first-in leaves the process and goes to a global clean or dirty second-chance list. Another process may take from the clean list; if the owner faults first, salvage without disk I/O. Larger second-chance lists ≈ closer to LRU.

Quiz

Rank the sequence

1 / 1

Order the life of a page under VAX segmented FIFO replacement, from being resident to possibly being reused without disk I/O.

OrderDrag the handle to rearrange — top should be first.

1The owning process re-faults on the page before it is reclaimed, so it is salvaged with no disk I/O
2The page is resident and counted against its process's RSS
3The page sits on a global clean or dirty second-chance list
4The page is first-in on its process's per-process FIFO and the process hits its RSS cap, so the page is evicted from the process

Drag items into the correct order (or use ↑↓), then check.

Emulating reference bits [BJ81]: mark pages inaccessible; first access traps → restore real protect; untouched pages look “cold.”

Clustering: batch dirty pages to swap for large disk transfers (still standard).

Lazy tricks

Be lazy

Defer work to cut latency — and sometimes avoid it entirely.

Demand zeroing: grow heap with invalid “demand-zero” PTEs; zero + map only on first fault
Copy-on-write (COW) [BB+72]: share R/O; copy only on write. Critical for fork() then exec() (most pages never need a real copy). Shared libraries too

Quiz

Rank the sequence

1 / 1

Order what happens to a page under copy-on-write across fork() then exec().

OrderDrag the handle to rearrange — top should be first.

1If the process instead calls exec() before writing, the original shared page is simply dropped — no copy was ever needed
2fork() marks the page read-only and shared between parent and child (refcount 2)
3If the child writes to the page, a fault triggers a real copy so each process gets its own page

Drag items into the correct order (or use ↑↓), then check.

Linux (x86 focus)

Same big idea: user VA + kernel VA; context switch changes user mappings only; user mode cannot touch kernel pages.

Classic 32-bit split at 0xC0000000. Two kernel flavors:

Type	Allocator	Property
Kernel logical	`kmalloc`	Direct map to low physical; contiguous phys → good for DMA; not swapped
Kernel virtual	`vmalloc`	Virtually contiguous only; easier large allocs; historically helped address > ~1 GB RAM

Page tables and huge pages

x86: hardware-managed multi-level PTs. 64-bit uses ~48 bits of VA today → 4-level walk (more levels as more bits light up).

Huge pages (2 MB / 1 GB): main win is TLB coverage for big-memory apps (TLB misses can burn ~10% cycles [B+13]). Linux: first explicit huge pages (mmap/shmget), then transparent huge pages. Costs: internal fragmentation, awkward swap, alloc overhead.

Consider incrementalism

Ship specialized support, learn, then generalize — Linux huge pages did this.

Page cache and 2Q

Unified page cache: mmap’d files, file read/write data, and anonymous (heap/stack) pages. Dirty pages flushed by pdflush-style threads.

Replacement: modified 2Q [JS94] — first touch → inactive; re-reference → active; reclaim from inactive. Resists “scan a huge file once” thrashing the whole cache. Lists approximated (Clock-like), not perfect LRU.

mmap is everywhere: executables and shared libs are mapped even if main never calls mmap (pmap shows [anon], stack, .so mappings).

Security

Modern difference vs VMS: networked attackers.

Buffer overflows → inject / overwrite; may escalate privilege
NX / XD — mark pages non-executable (e.g. stack)
ROP / return-to-libc — chain existing gadgets; NX alone insufficient
ASLR / KASLR — randomize layout so gadget addresses are hard to predict
Meltdown / Spectre — speculation leaves microarchitectural traces; KPTI isolates most kernel PTEs (security vs page-table switch cost)

Interactive

Try: VAX address space · segmented FIFO · demand-zero/COW · Linux 2Q / security.

Check your understanding

Quiz