Virtual Memory & Page Replacement

Virtual memory lets processes use more memory than physically exists by keeping only needed pages in RAM (demand paging).

Cheat sheet

  • ▸Demand paging: load a page only on first access.
  • ▸FIFO: replace oldest page; suffers Belady's anomaly.
  • ▸Optimal (OPT): replace page used farthest in future — theoretical best.
  • ▸LRU: replace least recently used — good approximation of OPT, no Belady's anomaly.
  • ▸Thrashing: system spends more time paging than executing; fix with working-set model / fewer processes.
  • ▸Copy-on-write: parent and child share pages until one writes.

Page replacement

AlgorithmBelady's anomaly?Practical?
FIFOYesYes, simple
OptimalNoNo (needs future)
LRUNoYes, costly exactly
Clock / Second chancePossibleYes, LRU approx.

Visual

Ref: 7 0 1 2 0 3   frames=3 (FIFO)
7  7  7  2  2  2
   0  0  0  0  3
      1  1  1  1
F  F  F  F  -  F   → 5 faults

Top 10 campus interview questions

Quick quiz

1. Belady's anomaly occurs in:

2. Thrashing is caused by:

3. Which algorithm gives the fewest page faults?

4. The dirty bit indicates:

5. Clock algorithm approximates: