Virtual Memory

Virtual memory gives each process the illusion of a large, contiguous, private address space — much bigger than physical RAM. The CPU works with virtual addresses; the Memory Management Unit (MMU) translates them on the fly to physical addresses in RAM. This buys three things at once:

• Isolation — process A’s virtual address 0x1000 maps to a different physical location than process B’s, so processes cannot stomp on each other.
• Transparency — each process can assume it has the whole machine to itself.
• Efficiency — only actively used pages need to be resident; the rest can live on disk and be swapped in on demand.

Physical vs Virtual Addressing

A physical address names a real byte in RAM (e.g. 0x004F2A). A virtual address is what the program’s instructions actually use; it is only meaningful once the MMU maps it.

The mapping is not one-to-one. Two virtual addresses can point at the same physical frame (shared libraries), and a virtual address can map to nothing resident (a page fault → the OS fetches it from disk). Without an MMU, every address would be physical — one process could read another’s memory or corrupt the kernel.

Paging & Page Frames

Physical memory is sliced into equal-sized chunks called page frames (typically 4 KiB). Virtual memory is sliced into equally sized pages. The mapping “which page lives in which frame” is stored in a page table, one per process.

Because both are fixed size, paging eliminates external fragmentation (the scattered holes that plague variable-size allocation). Its cost is internal fragmentation — the last page of a program rarely fills completely, wasting on average half a page per mapping.

A page table entry typically stores the frame number plus flags: present/resident bit, dirty bit, reference bit, and protection bits. The present bit is the linchpin: if it’s 0, the page is on disk, not RAM, and touching it triggers a page fault.

Segmentation: Variable-Sized Logical Units

Paging treats memory as flat, fixed-size chunks. Segmentation instead mirrors the program’s logical structure — code, data, heap, stack each live in a segment of the size the program actually needs. A virtual address is a pair: (segment number, offset). A segment table (one per process) maps each segment number to a base (its start address) and a limit (its length).

Because segment sizes vary, the allocation problem is real: when a segment grows or a new one is created, the OS must find a contiguous region of the right size — and after a while memory becomes littered with unusably small gaps. That is external fragmentation (holes between segments), the exact problem fixed-size paging was designed to eliminate.

• Paging → fixed-size pages, no external fragmentation, but up to a page of internal fragmentation per mapping.
• Segmentation → intuitive (each segment matches a program component, protection can be per-segment), but externally fragmented and slow to allocate.

Real systems don’t choose one. Classic designs (x86) supported segmented paging: segments give logical structure and per-segment permissions, while inside each segment the address space is paged so frames stay fixed-size. Modern 64-bit OSes effectively run flat paging (one flat address space, no segment semantics) because a flat space plus page permissions is simpler — the segment’s benefits survive in page-table protection bits instead.

Page Table Structures: the Multi-Level Page Table

A flat page table maps every possible page number to an entry. On 64-bit systems that table is absurdly large: with 4 KiB pages and a 48-bit address space there are 2³⁶ ≈ 69 billion entries — a multi-hundred-gigabyte table per process if allocated flat. The fix is a multi-level (hierarchical) page table — a tree of page tables where only the levels actually used are materialized:

• Level 0 (root) — a single small table indexing the top bits of the virtual address.
• Level 1…N — each entry in the level above points to the next level’s table; a null entry means that entire subtree is unmapped and no table is allocated for it.

A 4-level scheme (PML4 → PDPT → PD → PT, as in x86-64) uses 9 address bits per level + 12 offset bits. Translation becomes a 4-step walk: index into the root → follow pointer → index again → follow → … → find the frame → add the offset. Each level is one page (4 KiB), so a walk touches only 4 pages — the TLB absorbs almost all of them in practice.

The win: a tiny process whose address space uses a fraction of the 2⁴⁸ range allocates only the small subset of tables it touches, instead of a multi-GB flat array. The cost: a TLB miss is now a multi-level walk rather than one array lookup — which is exactly why the TLB matters so much and why modern CPUs cache page-walk results in a dedicated page-walk cache.

Address Translation & the TLB

To translate a virtual address the MMU:

1. Splits the address into a page number (high bits) and an offset (low bits).
2. Looks up the frame for that page number in the page table.
3. Composes the physical address: physical = frame × pageSize + offset (equivalently frame << offsetBits | offset).

A raw page-table lookup on every access would double the cost of every memory access — so the MMU keeps a Translation Lookaside Buffer (TLB), a tiny, fast cache of recent page→frame mappings.

• TLB hit — translation done in one step, no memory access for the page table.
• TLB miss — the MMU walks the page table (slow), and the entry is cached in the TLB for next time.
• Page fault — the page isn’t resident at all; the OS performs a disk I/O to swap it in, then retries the instruction. Page faults are normal (cold-start and swapping), but a pathological rate of them is called thrashing.

The interactive translator above walks exactly these steps, showing the TLB lookup, the page-table entry, and the composed physical address (or the fault) for each example address.

Swapping

When the sum of resident pages exceeds physical memory, the OS must evict pages to a swap device. The question “which page do I throw out?” is the page replacement problem, and it is the last piece of the memory puzzle the interactive simulator demonstrates.

Page Replacement Policies

FIFO — First-In, First-Out

Evict the page that has been resident the longest, using a simple queue. Cheap and obvious — but it ignores usage, so a frequently used page can be thrown out right before it’s needed. Worse, FIFO exhibits Belady’s anomaly: adding frames can increase the number of faults.

LRU — Least Recently Used

Evict the page unused for the longest time. LRU approximates the optimal policy well because the recent past predicts the near future. Its weakness is cost: hardware support or timestamp bookkeeping is needed for every access, and scanning for the oldest entry is expensive.

Clock (Second Chance)

An efficient approximation of LRU. Each frame has a reference bit, set to 1 whenever its page is accessed. A hand sweeps the frames in a circle:

• bit is 1 → the page got a second chance: clear the bit, advance.
• bit is 0 → evict this page.

A single reference bit is hardware-cheap (one bit per frame) yet captures recency well — the practical workhorse of real OSes.

Optimal (Belady’s MIN)

Evict the page whose next use is farthest in the future (or never). Provably the minimum possible number of faults — but it requires knowing the future, so it is not implementable. It exists as the benchmark: every real policy is judged by how close it gets.

Worked Example

Consider the classic reference string (20 accesses) with 3 frames:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Run each policy in the visualizer and compare the fault counts:

Notice the ordering: FIFO ≥ Clock ≥ LRU ≥ Optimal — never a surprise, since each policy is a refinement of the last. Then bump the frame count from 3 to 4 and rerun FIFO on the short string 1 2 3 4 1 2 5 1 2 3 4 5: faults go from 9 to 10 — Belady’s anomaly, live.

When Each Policy Is the Right Tool

Practice Trajectory

1. Hand-trace FIFO and LRU on the worked example; confirm the fault counts above.
2. Explain why FIFO’s queue ignores usage and how Belady’s anomaly is even possible.
3. Trace the Clock hand for the worked example and identify where second-chance frames are rescued.
4. Argue why LRU can never beat Optimal but FIFO can be beaten by LRU.
5. Walk a virtual address through TLB → page table → physical address (or fault) by hand.
6. Explain why a flat page table is infeasible on 64-bit and sketch how a 4-level table allocates only the used subtrees.

When It’s the Right Tool