A page replacement algorithm is used by an operating system's virtual memory manager to decide which memory page to evict when a new page needs to be loaded and all frames are full. The goal is to minimize page faults — situations where the requested page is not in memory and must be fetched from disk, which is significantly slower.

FIFO replaces the page that has been in memory the longest. It maintains a queue of loaded pages. When a page fault occurs and all frames are full, the page at the front of the queue is evicted. While simple to implement, FIFO suffers from Belady's Anomaly — increasing the number of frames can sometimes increase the number of page faults.

LRU replaces the page that hasn't been accessed for the longest time. It's based on the principle of temporal locality — recently used pages are likely to be used again soon. LRU generally performs better than FIFO but requires tracking access timestamps, making it more complex to implement in hardware. LRU does not suffer from Belady's Anomaly.

The Optimal (OPT or MIN) algorithm replaces the page that will not be used for the longest time in the future. It guarantees the minimum possible number of page faults for a given reference string and frame count. However, it requires future knowledge of the reference string, making it impossible to implement in practice. It serves as a theoretical benchmark to evaluate other algorithms.

Belady's Anomaly is a counterintuitive phenomenon where increasing the number of available frames actually increases the number of page faults for the FIFO algorithm with certain reference strings. This anomaly does not occur with stack-based algorithms like LRU and Optimal. The classic example reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 vs 4 frames demonstrates this effect.

Efficient page replacement is critical for system performance because page faults incur significant latency (accessing disk is ~100,000× slower than RAM). Modern operating systems use approximations of LRU (like the Clock algorithm) that balance performance with implementation complexity. Understanding these algorithms is fundamental to OS design, database buffer management, and cache systems.

The table shows the state of memory frames after each page reference. The top row shows the reference string with color coding (red = page fault, green = hit). Each subsequent row represents a frame, showing which page it holds at each step. Cells with orange background indicate a page just loaded due to a page fault. Green cells indicate a hit. The bottom indicator row shows PF for page faults and ✓ for hits.