Virtual Memory & Page Replacement

Virtual Memory — "Pretend You Have More RAM"

Analogy: Your laptop has 8GB RAM but you open 30GB worth of apps. Virtual memory lets this work by keeping only the NEEDED parts in RAM, and swapping the rest to disk when needed.

Valid bit in page table entry:
  1 = page is in RAM (fast access)
  0 = page is on disk → PAGE FAULT

When page fault happens:
  1. OS traps (hardware interrupt)
  2. Find a free frame (or EVICT a page from RAM)
  3. Load needed page from disk into frame
  4. Update page table (valid bit = 1)
  5. Restart the faulting instruction

Cost of a page fault:

Memory access:  ~200ns
Disk access:    ~8,000,000ns  (40,000× slower!)

EAT = (1-p) × mem_access + p × fault_service_time

For EAT to be < 2× mem_access:
p < 1 / 40,000 = 0.0025%  (less than 1 fault per 40,000 accesses)

---

Page Replacement — Who Gets Evicted?

When RAM is full and a new page must be loaded, which page do we throw out?

OPT — The Perfect (But Impossible) Algorithm

Replace the page that will NOT be used for the LONGEST time in the future.

Why impossible: requires knowing the future!
Why useful: gives MINIMUM possible page faults — used as benchmark

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
With 3 frames, OPT gives fewer faults than any other algorithm.

FIFO — First In, First Out

Replace the oldest page (the one that entered RAM first).

Analogy: Replace the oldest item on the shelf, regardless of how often you use it. Might evict a heavily-used page!

Implementation: queue of pages (front = oldest)

WARNING — Belady's Anomaly:
More frames can sometimes give MORE page faults with FIFO!

FIFO Example:

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frames:

Step:  1  2  3  4  1  2  5  1  2  3  4  5
F[0]:  1  1  1  4  4  4  5  5  5  5  4  4
F[1]:     2  2  2  1  1  1  1  1  3  3  3
F[2]:        3  3  3  2  2  2  2  2  2  5
Fault: F  F  F  F  F  F  F  -  -  F  F  F  = 9 faults

4 frames → 10 faults! (Belady's anomaly)

LRU — Least Recently Used

Replace the page that was last used LONGEST AGO.

Analogy: Replace the book you haven't opened in the longest time.

Has the STACK PROPERTY: more frames → never more faults
No Belady's anomaly!

Problem: expensive to implement exactly
  Option 1: timestamp every memory access (hardware overhead)
  Option 2: doubly-linked list + hash map (O(1) but complex)
  Option 3: Clock algorithm (practical approximation)

LRU Example:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4
3 frames:

t=1: 7 → [7] fault
t=2: 0 → [7,0] fault
t=3: 1 → [7,0,1] fault
t=4: 2 → evict LRU=7 → [0,1,2] fault
t=5: 0 → 0 already in frames! HIT
t=6: 3 → evict LRU=1 → [0,2,3] fault
t=7: 0 → HIT
t=8: 4 → evict LRU=2 → [0,3,4] fault
Total: 6 faults

Clock Algorithm — Practical LRU Approximation

Each page frame has a REFERENCE BIT (set to 1 when page accessed).
Circular list of frames with a "clock hand."

On page fault:
  While frame at hand has ref_bit = 1:
    Set ref_bit = 0 (give a second chance)
    Advance hand
  Replace frame at hand (ref_bit = 0)

"Second chance" algorithm — page gets one more chance if recently used.

---

Thrashing — When Paging Kills Performance

Analogy: You have 10 books you need but only desk space for 3. You constantly pick up a book, put one back, pick another... more time moving books than actually reading!

THRASHING: CPU utilisation drops because processes spend more time
           waiting for page faults than executing code.

Cause:   Too many processes competing for too few frames
         Each process gets fewer frames than its working set needs

Signs:   High page fault rate, low CPU utilisation, disk constantly busy

Fix:
  1. Reduce degree of multiprogramming (suspend some processes)
  2. Use Working Set model (allocate enough frames for each process)
  3. Page Fault Frequency algorithm (monitor and adjust dynamically)

---

Working Set Model

Working set W(t, Δ) = set of pages referenced in the last Δ accesses

Δ = working set window size (parameter to tune)

If total working set sizes > total frames → thrashing likely
If total working set sizes ≤ total frames → safe to run all processes

Allocate to each process: ≥ |W(t, Δ)| frames

---

Quick Check

Q1. Reference string: 1,2,3,1,4,3,5,3. 3 frames, LRU. How many page faults?

t=1: 1 → [1] fault
t=2: 2 → [1,2] fault
t=3: 3 → [1,2,3] fault
t=4: 1 → hit [1 most recent, 2,3]
t=5: 4 → evict LRU=2 → [1,3,4] fault
t=6: 3 → hit [1,4,3]
t=7: 5 → evict LRU=1 → [4,3,5] fault
t=8: 3 → hit
Total: 5 faults

Q2. Does LRU suffer from Belady's anomaly? Answer: No. LRU has the stack property — the set of pages in memory with n frames is always a subset of the set with n+1 frames. More frames = never more faults.

Q3. Why is OPT never used in real systems? Answer: It requires knowing which pages will be accessed in the future, which is impossible at runtime. It is used only as a theoretical benchmark.