Page-Replacement Algorithms: OPT, LRU, FIFO
The page-replacement problem
When a page fault occurs and the free-frame list is empty, the OS must select a victim frame to evict, writing it to disk if dirty, and reuse the frame for the faulting page. The choice of victim determines the future page-fault rate.
Optimal (OPT / Belady’s optimal algorithm)
Replace the page that will not be used for the longest time in the future.
OPT is provably optimal — no other algorithm can produce fewer page faults. It is also unimplementable because it requires knowledge of future memory references. OPT serves as a gold standard against which real algorithms are compared.
Least Recently Used (LRU)
Replace the page that has not been used for the longest time in the past. The intuition: the recent past is a good predictor of the near future (temporal locality).
LRU is provably good — it does not suffer from Belady’s anomaly (see next note). However, implementing pure LRU requires updating a timestamp or moving a stack entry on every memory access, which is prohibitively expensive in hardware (or requires extensive software instrumentation).
First-In, First-Out (FIFO)
Replace the page that has been in memory the longest (the oldest resident page). Implemented with a simple queue: pages join at the back; the victim is taken from the front.
FIFO is simple to implement but can perform pathologically — it may evict a page that is heavily used (e.g., the programme’s hot loop code) just because it was loaded first. FIFO also exhibits Belady’s anomaly: increasing the number of frames can increase the number of page faults.
Worked example: Reference string 1 2 3 2 4 3 5 1 3 2 3 4 (2024 Q4)
Three frames.
OPT
| Ref | Frames | Fault? | Victim |
|---|---|---|---|
| 1 | [1, —, —] | Yes | — |
| 2 | [1, 2, —] | Yes | — |
| 3 | [1, 2, 3] | Yes | — |
| 2 | [1, 2, 3] | No | — |
| 4 | [1, 2, 4] | Yes | 3 (used again at pos 9) |
| 3 | [1, 2, 3] | Yes | 4 (used again at pos 9? no, 4 never used again) — wait, 4 has no future reference, 1 next at pos 8, 2 next at pos 10. Evict 4 → load 3. |
| 5 | [1, 5, 3] | Yes | 2 (next use at pos 10, further than 1 at pos 8) |
| 1 | [1, 5, 3] | No | — |
| 3 | [1, 5, 3] | No | — |
| 2 | [2, 5, 3] | Yes | 1 (next use — neither 1 nor 5 has future reference? Actually 1 has none, 5 has none, 3 has none. Any will do. Evict 1.) |
| 3 | [2, 5, 3] | No | — |
| 4 | [2, 4, 3] | Yes | 5 (no future use; 2 and 3 also no future use. Any.) |
OPT faults: Count the “Yes” rows: 1,2,3,4,3,5,2,4 = 8 faults.
LRU
| Ref | Frames | Fault? |
|---|---|---|
| 1 | [1, —, —] | Yes |
| 2 | [1, 2, —] | Yes |
| 3 | [1, 2, 3] | Yes |
| 2 | [1, 3, 2] (2 moves to front) | No |
| 4 | [3, 2, 4] | Yes (evict 1, LRU is 1) |
| 3 | [2, 4, 3] (3 touched, order: 2 is now LRU, then 4, then 3) | No |
| 5 | [4, 3, 5] | Yes (evict 2, LRU) |
| 1 | [3, 5, 1] | Yes (evict 4, LRU) |
| 3 | [5, 1, 3] (3 moves up, 5 is now LRU) | No |
| 2 | [1, 3, 2] | Yes (evict 5, LRU) |
| 3 | [1, 2, 3] (3 moves up) | No |
| 4 | [2, 3, 4] | Yes (evict 1, LRU) |
LRU faults: 1,2,3,4,5,1,2,4 = 8 faults. Same as OPT in this case.
FIFO
| Ref | Frames | Fault? |
|---|---|---|
| 1 | [1] | Yes |
| 2 | [1, 2] | Yes |
| 3 | [1, 2, 3] | Yes |
| 2 | [1, 2, 3] | No |
| 4 | [2, 3, 4] | Yes (evict 1, oldest) |
| 3 | [2, 3, 4] | No |
| 5 | [3, 4, 5] | Yes (evict 2) |
| 1 | [4, 5, 1] | Yes (evict 3) |
| 3 | [5, 1, 3] | Yes (evict 4) |
| 2 | [1, 3, 2] | Yes (evict 5) |
| 3 | [1, 3, 2] | No |
| 4 | [3, 2, 4] | Yes (evict 1) |
FIFO faults: 1,2,3,4,5,1,3,2,4 = 9 faults. Worse than OPT and LRU.
Summary table
| Algorithm | Implementation cost | Belady’s anomaly? | Typical performance |
|---|---|---|---|
| OPT | Unimplementable (needs future knowledge) | No | Optimal (by definition) |
| LRU | Expensive (timestamp/stack per access) | No | Good |
| FIFO | Trivial (queue) | Yes | Poor to mediocre |