Memory Management & Virtual Memory

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.

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.

When It’s the Right Tool