Page-Replacement: Worked Examples
Worked example 1: OPT on 1 2 3 2 4 3 5 1 3 2 3 4 (2024 Q4)
Three frames. OPT replacement: evict the page whose next use is farthest in the future.
| Step | Ref | Frames after | Fault? | Evicted? | Reason |
|---|---|---|---|---|---|
| 1 | 1 | [1] | Yes | — | First load |
| 2 | 2 | [1, 2] | Yes | — | First load |
| 3 | 3 | [1, 2, 3] | Yes | — | First load |
| 4 | 2 | [1, 2, 3] | No | — | 2 present |
| 5 | 4 | [1, 4, 3] | Yes | 2 | 2 next at pos 10, 1 at pos 8, 3 at pos 6. 2’s next is farthest → evict 2 |
| 6 | 3 | [1, 4, 3] | No | — | 3 present |
| 7 | 5 | [1, 5, 3] | Yes | 4 | 4 never used again, 1 next at pos 8, 3 at pos 9 |
| 8 | 1 | [1, 5, 3] | No | — | 1 present |
| 9 | 3 | [1, 5, 3] | No | — | 3 present |
| 10 | 2 | [2, 5, 3] | Yes | 1 | 1 never used again; 5 and 3 also no future. Any → evict 1 |
| 11 | 3 | [2, 5, 3] | No | — | 3 present |
| 12 | 4 | [2, 4, 3] | Yes | 5 | No future for any. Evict 5 |
OPT faults: 8 (1, 2, 3, 4, 5, 2, 4)
Worked example 2: LRU on the same string
LRU: evict the page whose last use is farthest in the past.
| Step | Ref | Frames after (LRU order) | Fault? | Evicted? |
|---|---|---|---|---|
| 1 | 1 | [1] | Yes | — |
| 2 | 2 | [1, 2] | Yes | — |
| 3 | 3 | [1, 2, 3] | Yes | — |
| 4 | 2 | [1, 3, 2] | No | — |
| 5 | 4 | [3, 2, 4] | Yes | 1 (LRU) |
| 6 | 3 | [2, 4, 3] | No | — |
| 7 | 5 | [4, 3, 5] | Yes | 2 (LRU) |
| 8 | 1 | [3, 5, 1] | Yes | 4 (LRU) |
| 9 | 3 | [5, 1, 3] | No | — |
| 10 | 2 | [1, 3, 2] | Yes | 5 (LRU) |
| 11 | 3 | [1, 2, 3] | No | — |
| 12 | 4 | [2, 3, 4] | Yes | 1 (LRU) |
LRU faults: 8 (1, 2, 3, 4, 5, 1, 2, 4). Same as OPT.
Worked example 3: FIFO on the same string
| Step | Ref | Frames after (FIFO order) | Fault? | Evicted? |
|---|---|---|---|---|
| 1 | 1 | [1] | Yes | — |
| 2 | 2 | [1, 2] | Yes | — |
| 3 | 3 | [1, 2, 3] | Yes | — |
| 4 | 2 | [1, 2, 3] | No | — |
| 5 | 4 | [2, 3, 4] | Yes | 1 (oldest) |
| 6 | 3 | [2, 3, 4] | No | — |
| 7 | 5 | [3, 4, 5] | Yes | 2 (oldest) |
| 8 | 1 | [4, 5, 1] | Yes | 3 (oldest) |
| 9 | 3 | [5, 1, 3] | Yes | 4 (oldest) |
| 10 | 2 | [1, 3, 2] | Yes | 5 (oldest) |
| 11 | 3 | [1, 3, 2] | No | — |
| 12 | 4 | [3, 2, 4] | Yes | 1 (oldest) |
FIFO faults: 9. Worse than OPT/LRU by 1 fault.
Worked example 4: Belady’s anomaly with FIFO
Reference: 1 2 3 4 1 2 5 1 2 3 4 5
3 frames (FIFO): faults at 1,2,3,4,1,2,5,3,4 = 9 faults. 4 frames (FIFO): faults at 1,2,3,4,1,2,5,1,2,3,4,5 = 10 faults.
More frames → more faults. This is Belady’s anomaly. The extra frame changed the load order so that a useful page (1 or 2) was evicted at a critical moment, causing an extra fault later.
Tripos technique
When answering page-replacement questions:
- Draw a table with columns for Step, Reference, Frames (after replacement), Fault? (Yes/No), and optionally Evicted.
- Show the frame contents after each reference, not before.
- For OPT, compute the “next-use distance” for each resident page after each reference.
- For LRU, keep the stack ordered most-to-least recent; the victim is always the last element.
- For FIFO, a simple queue suffices — push new pages, pop the oldest.
Past Paper Questions
2024 Paper 2 Question 4(b–c): Compute page-replacement sequences for OPT, LRU, FIFO on 1 2 3 2 4 3 5 1 3 2 3 4 with 3 frames. State and explain Belady’s anomaly. [13 marks]