FIFO Page Replacement
What you'll learn: How the simplest page replacement algorithm works by evicting the page that has been in memory the longest.
When physical memory is full and a page fault occurs, the operating system must choose which page to evict to make room. The First-In-First-Out (FIFO) algorithm solves this by maintaining a queue of pages in the order they were loaded into memory, and always replacing the oldest one.
How FIFO Works
Think of FIFO like a line at a coffee shop with limited seating. When all seats are taken and a new customer arrives, the person who has been sitting the longest must leave—regardless of whether they're about to finish their work or just started. FIFO operates the same way: it tracks which page arrived first and evicts it when space is needed, without considering how frequently or recently that page was used.
The algorithm maintains pages in a queue structure:
- When a new page is loaded, it's added to the back of the queue
- When a page must be evicted, remove the page at the front of the queue
- The new page takes its place at the back
The FIFO Anomaly
Surprisingly, FIFO can exhibit Belady's Anomaly—adding more page frames can sometimes increase page faults rather than decrease them. This counterintuitive behavior happens because FIFO ignores usage patterns entirely.
Advantages and Drawbacks
Advantages: Extremely simple to implement and understand; fair in a temporal sense.
Drawbacks: Ignores page usage frequency and recency; may evict frequently-used pages; suffers from Belady's Anomaly.
Key Takeaway: FIFO page replacement is the simplest algorithm that evicts the oldest page in memory, but its complete disregard for actual page usage patterns makes it inefficient for most real-world workloads.