Definition
Page Replacement Policy
A page replacement policy is a memory replacement policy that decides which page in RAM to replace when a new page must be loaded and no free frames are available. The goal is to minimise page faults by selecting the page least likely to be needed soon.
Scope
Local Replacement
Candidate page chosen only from frames allocated to the faulting process.
Global Replacement
Candidate page chosen from any frame in physical memory, potentially taking a frame from another process.
Algorithms
Optimal (OPT)
Replaces the page not used for the longest future period.
- Pro: Guaranteed minimum page fault rate
- Con: Impossible to implement (requires future knowledge); serves as benchmark
Least Recently Used (LRU)
Replaces the page not accessed for the longest time.
- Logic: Based on principle of locality — unused pages unlikely to be needed soon
- Overhead: High (must track access times for every page)
First-In-First-Out (FIFO)
Replaces the page in memory longest.
- Pro: Simple (queue-based)
- Con: Poor performance (may replace heavily used page loaded early)
Clock Policy
Efficient LRU approximation using a circular buffer and use bit per frame:
- Page accessed → use bit set to 1
- Pointer (“hand”) rotates through frames
- Finds bit at 1 → sets to 0, moves on
- Finds bit at 0 → replaces that page
Comparison
Performance
LRU and Clock performance is usually near-optimal. FIFO is generally avoided in high-performance systems.