Solution - Page Fault and Page Replacement Algorithms (14M)

What is a Page Fault?
In virtual memory with demand paging, pages are loaded from secondary storage (disk) to main memory only when needed. A page fault is an exception (trap) that occurs when a running process tries to access a page that is currently not present in main memory (valid bit = 0 in Page Table or TLB miss). The MMU detects this via page table entry's present/absent bit and raises interrupt #14 (x86).

What does it signify?

• Indicates miss in main memory hierarchy; required page (or segment of program/data) is still on disk (swap space).
• Triggers OS fault handler: OS must block the process, allocate a free frame, read the page from disk into frame (I/O), update page table (frame number, valid=1), and restart the faulting instruction.
• High frequency = thrashing if insufficient frames (working set > memory).
• Counted as overhead: interrupt + context switch + disk I/O (ms) >> memory access (ns).

Page fault handling steps:

1. Trap to OS, save registers.
2. Check if reference was legal (segmentation violation vs valid page on disk).
3. Find free frame (or victim via replacement algorithm if none free).
4. If victim dirty, write back to disk.
5. Read required page from disk into frame (DMA).
6. Update page table, TLB invalidated.
7. Restart process at faulting instruction.

Page Replacement Algorithms - when memory is full (no free frame), which victim page to evict:

1. FIFO (First-In First-Out):

• Replaces page that has been in memory longest (queue). Simple via FIFO queue.
• Belady's Anomaly: More frames can increase faults! Not stack algorithm.
• Example: Reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames -> 9 faults.

2. Optimal (OPT / MIN) - Theoretical:

• Replaces page that will not be used for longest period in future (furthest next use). Gives minimum faults, used as benchmark.
• Impossible to implement perfectly (requires future knowledge), but approximated.
• Example: Same string -> 7 faults (optimal).

3. LRU (Least Recently Used):

• Replaces page that has not been used for longest time in past. Exploits locality.
• Implementation: counter/timestamp or stack, or approximation via reference bits.
• Good performance, close to Optimal. Stack algorithm (more frames never hurts).
• Example: With same string -> 10 faults.

4. Approx. LRU variants:

• NRU / Clock (Second Chance): Circular queue with reference bit R. Give second chance if R=1 then clear and rotate; if R=0 replace. Efficient.
• Aging / LFU / MFU: Least Frequently Used (count accesses) / Most Frequently Used - but LFU suffers cache pollution.

5. LIFO / Random:

• LIFO replaces last loaded; Random picks random victim - simple, avoids Belady but unpredictable.

Comparison Table:

Algorithm	Needs future?	Overhead	Anomaly	Performance
FIFO	No	Low	Yes	Poor
Optimal	Yes	-	No	Best (ideal)
LRU	No	High (stack)	No	Good
Clock	No	Low	No	Good approx.
LFU	No	Medium	No	Depends

Selection criteria: Fault rate, implementation cost, hardware support (R and M bits in page table entry help Clock/LRU approximation). Modern OS uses Clock (enhanced second chance with Dirty bit) or LRU approximation with aging.

Dirty bit: If victim page modified (M=1), must write back before replacement - double I/O cost, so some algorithms prefer clean victims (NRU class 0: R=0 M=0).