Page Replacement Algorithms
A page replacement algorithm decides which page to evict from physical memory when a page fault occurs and no free frame is available. Common choices are FIFO (evict the oldest-loaded page), LRU (evict the least recently used page) and Optimal (evict the page not needed for the longest time), which is only a theoretical benchmark.
When a page fault occurs and there's no free physical frame available, the OS has to choose an existing page to evict to make room for the new one. Which page gets picked matters a lot for performance, evicting a page that's about to be needed again immediately just causes another fault right away, while evicting a page that won't be needed for a long time avoids that cost.
FIFO (First-In, First-Out)
Evict whichever page has been in memory the longest, regardless of how recently or often it's actually been used. It's simple to implement (just track load order in a queue) but can behave poorly: a page loaded a long time ago but still being actively used gets evicted just because of its age, causing an avoidable fault right after.
LRU (Least Recently Used)
Evict whichever page hasn't been accessed for the longest time. This tracks actual usage rather than just load time, and performs much better in practice, since a page that hasn't been touched in a while is genuinely a good guess for "won't be needed again soon."
Optimal (theoretical benchmark)
Evict whichever page won't be used again for the longest time in the future. This requires knowing the future reference sequence in advance, which is impossible in a real running system, but it's used as the theoretical best-case benchmark to measure how close a real algorithm (like LRU) comes to ideal behavior.
A worked example comparing FIFO and LRU
Reference string (the sequence of pages accessed, in order): 1, 2, 3, 1, 4, with only 3 physical frames available.
FIFO:
- Access 1: fault, load 1. Frames: [1]
- Access 2: fault, load 2. Frames: [1, 2]
- Access 3: fault, load 3. Frames: [1, 2, 3]
- Access 1: already in frames, no fault. Frames: [1, 2, 3]
- Access 4: fault, frames full, evict oldest-loaded (1, loaded first). Frames: [2, 3, 4]
Total faults: 4.
LRU:
- Access 1: fault, load 1. Frames: [1]
- Access 2: fault, load 2. Frames: [1, 2]
- Access 3: fault, load 3. Frames: [1, 2, 3]
- Access 1: already in frames, no fault, but 1 is now the most recently used. Frames: [1, 2, 3] (recency order: 2, 3, 1)
- Access 4: fault, frames full, evict least recently used (2, since 3 and 1 were both touched more recently). Frames: [3, 1, 4]
Total faults: 4 in this particular short example, but LRU's advantage shows up over longer, more realistic reference strings where recently-touched pages really are more likely to be touched again soon, exactly the locality-of-reference pattern real programs exhibit.
Where this matters in real systems
Real operating systems don't implement textbook-perfect LRU exactly, tracking the precise recency of every single page access would itself be too expensive. Linux instead uses an approximation (a "clock" or second-chance algorithm, which cycles through pages checking a reference bit that hardware sets on access, giving a page a "second chance" if that bit is set rather than evicting it immediately) that captures most of LRU's real-world benefit at a fraction of the bookkeeping cost.
What interviewers actually ask about page replacement algorithms
- "Compare FIFO and LRU." FIFO evicts based purely on load order, ignoring actual usage; LRU evicts based on how recently a page was actually accessed, which usually performs better because of locality of reference.
- "What is the Optimal algorithm, and why can't it actually be implemented?" It evicts the page that won't be used again for the longest future time, which requires knowing the future access pattern in advance, impossible to know in a real running system; it's used only as a theoretical benchmark.
- "Why doesn't Linux implement exact LRU?" Because tracking the precise access recency of every page is itself too expensive; Linux uses a cheaper approximation (a clock/second-chance algorithm) instead.
- "What is Belady's Anomaly?" A counterintuitive real phenomenon where, for FIFO specifically, increasing the number of available physical frames can sometimes increase the total number of page faults rather than decrease it, one of the reasons FIFO is considered a weaker algorithm than LRU in practice.
Key takeaways
- Page replacement algorithms decide which page to evict when memory is full and a new page needs loading.
- FIFO evicts by load order; LRU evicts by actual recency of use and generally performs better.
- Optimal is a theoretical benchmark requiring future knowledge, impossible to implement for real.
- Real systems like Linux use cheaper LRU approximations (clock/second-chance) rather than exact LRU tracking.
More in Memory Management
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
Compare FIFO and LRU.
FIFO evicts based purely on load order, ignoring actual usage; LRU evicts based on how recently a page was actually accessed, which usually performs better because of locality of reference.
What is the Optimal algorithm, and why can't it actually be implemented?
It evicts the page that won't be used again for the longest future time, which requires knowing the future access pattern in advance, impossible to know in a real running system; it's used only as a theoretical benchmark.
Why doesn't Linux implement exact LRU?
Because tracking the precise access recency of every page is itself too expensive; Linux uses a cheaper approximation (a clock/second-chance algorithm) instead.
What is Belady's Anomaly?
A counterintuitive real phenomenon where, for FIFO specifically, increasing the number of available physical frames can sometimes increase the total number of page faults rather than decrease it, one of the reasons FIFO is considered a weaker algorithm than LRU in practice.