Virtual Memory and Page Replacement With easy examples.

Virtual memory is a technique that lets programs use more memory than the physical RAM installed, by keeping only the active pages in RAM and parking the rest on disk. When a program touches a page that is on disk, the hardware raises a page fault and the operating system fetches that page into RAM, possibly evicting another page to make room. The choice of which page to evict is made by a page replacement algorithm.

This matters because it lets a computer with 8 GB of RAM run programs that together need far more, and it lets programmers write code without worrying about physical memory size. Good page replacement keeps the pages a program actually needs in RAM; a bad choice causes thrashing, where the system spends all its time swapping pages instead of doing useful work.

Key Concepts

• Demand paging: pages are loaded only when first touched, not all at program start.
• Page fault: a trap raised when the accessed page is not in RAM; the OS loads it from disk.
• Locality of reference: programs tend to reuse nearby code and data, which is why keeping pages in RAM works.
• Working set: the pages a process actively uses; if it fits in RAM, faults stay rare.
• Thrashing: when processes need more frames than exist, the CPU spends most of its time handling page faults.
• FIFO: evict the page loaded longest ago. LRU: evict the least recently used. Optimal: evict the page used farthest in the future (theoretical benchmark). Clock: circular FIFO with a reference bit giving pages a second chance.
• Belady's anomaly: with FIFO, adding frames can surprisingly increase page faults.

Formulas

• Effective access time = (1 − p) × m + p × t, where p = page fault rate (0 to 1), m = memory access time, t = page fault service time.
• Example: m = 100 ns, t = 8 ms = 8,000,000 ns, p = 0.001. EAT = 0.999 × 100 + 0.001 × 8,000,000 = 99.9 + 8000 ≈ 8.1 µs. Even a 0.1% fault rate dominates access time — which is why replacement algorithms matter so much.
• Page fault rate = number of faults ÷ number of memory references.

Worked Example

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 — 3 frames, FIFO (frames shown oldest first; F = fault, H = hit):

1. 7(F) → [7]; 0(F) → [7,0]; 1(F) → [7,0,1]; 2(F) evicts 7 → [0,1,2]; 0(H).
2. 3(F) evicts 0 → [1,2,3]; 0(F) evicts 1 → [2,3,0]; 4(F) evicts 2 → [3,0,4]; 2(F) evicts 3 → [0,4,2]; 3(F) evicts 0 → [4,2,3]; 0(F) evicts 4 → [2,3,0].
3. 3(H); 2(H); 1(F) evicts 2 → [3,0,1]; 2(F) evicts 3 → [0,1,2]; 0(H); 1(H).
4. 7(F) evicts 0 → [1,2,7]; 0(F) evicts 1 → [2,7,0]; 1(F) evicts 2 → [7,0,1].

Total: 15 faults out of 20 references = a 75% fault rate. The optimal algorithm needs only 9 faults on this string — the choice of algorithm matters enormously.

Common Misconceptions

• "More frames always means fewer faults." False for FIFO — Belady's anomaly means extra frames can raise the fault count.
• "A page fault is an error that crashes the program." It is a normal, handled event; only an invalid address, like a null pointer, kills the process.
• "Virtual memory makes RAM bigger." It creates the illusion of more memory using disk, but disk is thousands of times slower — a space trick, not a speed trick.

Real-World Applications

• Every desktop and phone OS uses demand paging.
• Databases size their buffer pools using working-set ideas.
• LRU variants drive CPU caches and web caches (CDNs).
• Mobile OSes compress or swap pages to stretch limited RAM.

Virtual memory keeps active pages in RAM and the rest on disk, fetching on demand through page faults. Replacement algorithms like FIFO, LRU, and Clock decide evictions, and the math shows even tiny fault rates dominate performance. Keeping each process's working set in memory is the whole game.