Virtual Memory
20 min
Virtual memory lets programs use more memory than physically exists by keeping only the actively-needed pages in RAM, swapping the rest to disk. When a program accesses a page that's NOT currently in memory — a page fault — the OS must load it, and if memory is already full, evict something else to make room. WHICH page gets evicted is exactly the same kind of tradeoff as the Complexity Analysis course's cache tradeoffs, applied to memory management.
FIFO (First-In-First-Out) evicts whichever page has been in memory the LONGEST, regardless of how recently it was actually used:
def fifo_page_faults(pages, capacity):
frame = []
faults = 0
for p in pages:
if p not in frame:
faults += 1
if len(frame) >= capacity:
frame.pop(0) # evict the oldest-loaded page
frame.append(p)
return faults
More memory (higher capacity) generally means fewer faults -- but FIFO has a genuine quirk called Belady's Anomaly, where adding MORE frames can occasionally cause MORE faults on some access patterns. LRU never has that problem.
LRU (Least Recently Used) evicts based on ACTUAL usage recency, not just load order — a page that's still being accessed regularly survives, even if it was loaded a long time ago:
def lru_page_faults(pages, capacity):
frame = []
faults = 0
for p in pages:
if p in frame:
frame.remove(p)
frame.append(p) # mark as most-recently-used
else:
faults += 1
if len(frame) >= capacity:
frame.pop(0) # evict the least-recently-used page
frame.append(p)
return faults
LRU generally performs better than FIFO in practice (it more closely tracks which pages are actually "hot"), but it's more expensive to implement precisely — this is exactly the same LRU idea you'll reuse in the Redis course's caching module, since caches and virtual memory are solving the structurally identical problem.
Write `fifo_page_faults(pages, capacity)`: simulate FIFO page replacement over the sequence `pages` with `capacity` frames, returning the total number of page faults.
Write `lru_page_faults(pages, capacity)`: same simulation, but evict the Least-Recently-Used page instead of the oldest-loaded one.
What does LRU (Least Recently Used) page replacement evict when memory is full and a new page needs to be loaded?
You can simulate FIFO and LRU page replacement and count page faults, and understand why LRU generally outperforms FIFO by tracking actual usage recency.