Page Replacement Algorithms
When physical memory fills up and a new page needs to come in, something already sitting in RAM has to leave. But which one?
That decision belongs to the page replacement algorithm. Pick the wrong page to evict and you will be fetching it back from disk almost immediately. Pick well and page faults stay low. Four main algorithms tackle this problem, each with a different strategy.
1. FIFO (First In First Out)
The simplest possible approach. Whatever page arrived in memory first is the first one to go when space is needed. The OS maintains a queue of loaded pages. New pages join the back of the queue. When eviction is needed, the page sitting at the front gets kicked out.
No usage tracking is needed. No timestamps. Just the order of arrival.
Example Parameters:
Page reference string: 3, 4, 2, 6, 4, 3, 4, 7, 3, 6
Number of frames: 3| Step | Reference | Frames | Page Fault | Evicted |
|---|---|---|---|---|
| 1 | 3 | 3 | Yes (1) | - |
| 2 | 4 | 3, 4 | Yes (2) | - |
| 3 | 2 | 3, 4, 2 | Yes (3) | - |
| 4 | 6 | 4, 2, 6 | Yes (4) | 3 (oldest) |
| 5 | 4 | 4, 2, 6 | No | - |
| 6 | 3 | 2, 6, 3 | Yes (5) | 4 (oldest) |
| 7 | 4 | 6, 3, 4 | Yes (6) | 2 (oldest) |
| 8 | 7 | 3, 4, 7 | Yes (7) | 6 (oldest) |
| 9 | 3 | 3, 4, 7 | No | - |
| 10 | 6 | 4, 7, 6 | Yes (8) | 3 (oldest) |
Total Page Faults = 8 Page Fault Rate = 8/10 = 80% Pages Evicted = 3, 4, 2, 6, 3
2. LRU (Least Recently Used)
LRU takes a more informed approach. Rather than evicting the oldest arrival, it evicts the page that has gone the longest without being touched. The reasoning is that pages used recently are likely to be needed again soon, so they should stay. Pages that nobody has asked for in a while are the safer bet for removal.
Each page access updates that page's usage timestamp. When eviction time comes, the page with the stalest timestamp loses its frame.
Example Parameters:
Page reference string: 2, 5, 4, 2, 7, 5, 3, 5, 7, 4
Number of frames: 3| Step | Reference | Frames | Page Fault | Evicted |
|---|---|---|---|---|
| 1 | 2 | 2 | Yes (1) | - |
| 2 | 5 | 2, 5 | Yes (2) | - |
| 3 | 4 | 2, 5, 4 | Yes (3) | - |
| 4 | 2 | 2, 5, 4 | No | - |
| 5 | 7 | 5, 4, 7 | Yes (4) | 2 (LRU) |
| 6 | 5 | 4, 7, 5 | No | - |
| 7 | 3 | 7, 5, 3 | Yes (5) | 4 (LRU) |
| 8 | 5 | 7, 3, 5 | No | - |
| 9 | 7 | 3, 5, 7 | No | - |
| 10 | 4 | 5, 7, 4 | Yes (6) | 3 (LRU) |
Total Page Faults = 6 Page Fault Rate = 6/10 = 60% Pages Evicted = 2, 4, 3
Notice step 4: page 2 is referenced again, updating its recency. When eviction is needed at step 5, page 2 escapes because it was just used. Page 5 in step 6 similarly survives because it was recently accessed.
3. LFU (Least Frequently Used)
LRU cares about when a page was last used. LFU cares about how often a page has been used overall. Every page carries a counter that increments each time it is accessed.
When a frame must be freed, the page with the lowest access count gets evicted. On a tie, FIFO or LRU ordering breaks the deadlock depending on the implementation.
Example Parameters:
Page reference string: 4, 3, 1, 4, 3, 4, 6, 3, 4, 2
Number of frames: 3| Step | Ref | Frequency Table | Frames | Fault |
|---|---|---|---|---|
| 1 | 4 | 4:1 | 4 | Yes (1) |
| 2 | 3 | 4:1, 3:1 | 4, 3 | Yes (2) |
| 3 | 1 | 4:1, 3:1, 1:1 | 4, 3, 1 | Yes (3) |
| 4 | 4 | 4:2, 3:1, 1:1 | 4, 3, 1 | No |
| 5 | 3 | 4:2, 3:2, 1:1 | 4, 3, 1 | No |
| 6 | 4 | 4:3, 3:2, 1:1 | 4, 3, 1 | No |
| 7 | 6 | 4:3, 3:2, 1:1 → evict 1 (freq=1) | 4, 3, 6 | Yes (4) |
| 8 | 3 | 4:3, 3:3, 6:1 | 4, 3, 6 | No |
| 9 | 4 | 4:4, 3:3, 6:1 | 4, 3, 6 | No |
| 10 | 2 | 4:4, 3:3, 6:1 → evict 6 (freq=1) | 4, 3, 2 | Yes (5) |
Total Page Faults = 5 Page Fault Rate = 5/10 = 50% Pages Evicted = 1, 6
Pages 4 and 3 accumulate high counts early and hold their frames throughout. Pages that show up infrequently get pushed out when space is needed.
4. Optimal Page Replacement
The optimal algorithm is the theoretical gold standard. When a page must be evicted, it looks ahead at the entire future sequence of page references and removes whichever page will not be needed for the longest stretch of time going forward.
By definition no other algorithm can do better on the same reference string with the same number of frames. It produces the absolute minimum number of page faults possible.
Example Parameters:
Page reference string: 2, 3, 4, 2, 5, 3, 6, 5, 4, 3, 2, 6
Number of frames: 3| Step | Ref | Frames | Fault | Evicted | Reason |
|---|---|---|---|---|---|
| 1 | 2 | 2 | Yes (1) | - | - |
| 2 | 3 | 2, 3 | Yes (2) | - | - |
| 3 | 4 | 2, 3, 4 | Yes (3) | - | - |
| 4 | 2 | 2, 3, 4 | No | - | - |
| 5 | 5 | 2, 3, 5 | Yes (4) | 4 | 4 next appears at step 9, latest of the three |
| 6 | 3 | 2, 3, 5 | No | - | - |
| 7 | 6 | 2, 3, 6 | Yes (5) | 5 | 5 appears at step 8 but won't appear after; 6 needed now |
| 8 | 5 | 2, 3, 5 | Yes (6) | 6 | 6 next appears at step 12, latest |
| 9 | 4 | 2, 4, 5 | Yes (7) | 3 | 3 next at step 10 but not again; 4 comes sooner |
| 10 | 3 | 3, 4, 5 | Yes (8) | 2 | 2 next at step 11 but 5 appears later; evict 2 |
| 11 | 2 | 2, 3, 4 | Yes (9) | 5 | 5 not in future reference |
| 12 | 6 | 2, 3, 6 | Yes (10) | 4 | 4 not in future reference |
Total Page Faults = 10 Page Fault Rate = 10/12 = 83%
Even the optimal algorithm cannot avoid cold-start faults when frames are empty. Its advantage over other algorithms grows most visible on longer reference strings with more reuse patterns.
Comparing All Four Algorithms
Using the same reference string (2, 5, 4, 2, 7, 5, 3, 5, 7, 4) with 3 frames as a baseline:
| Algorithm | Total Page Faults | Page Fault Rate | Practical? |
|---|---|---|---|
| FIFO | 8 | 80% | Yes, very simple |
| LRU | 6 | 60% | Yes, moderately complex |
| LFU | 5 | 50% | Yes, but aging issues |
| Optimal | Lowest possible | Best case | No, future unknown |
When to Use Which
- FIFO works when simplicity is the priority and memory access patterns are unpredictable. Its queue structure is trivial to implement and maintain.
- LRU is the go-to choice for most general purpose operating systems. It strikes a reasonable balance between performance and implementation effort, and it closely approximates optimal behavior on many real workloads.
- LFU shines in environments where certain pages are accessed heavily and repeatedly over long periods, like database buffer caches where popular tables stay hot. It struggles with workloads that shift access patterns over time.
- Optimal serves as a measuring stick. When evaluating a new algorithm or tuning an existing one, comparing its fault rate against optimal on the same reference string tells you exactly how much room for improvement remains.
Summary
Page replacement is one of those decisions that happens thousands of times per second on a busy system, yet most of the time goes completely unnoticed. The goal is always the same: keep the pages most likely to be needed next in the limited frames available, and push out the ones least likely to be touched again soon.
FIFO does this crudely, LRU does it well, LFU does it differently, and Optimal does it perfectly but only in theory.