Consider the reference string 0 1 2 3 0 1 4 0 1 2 3 4 If FIFO page replacement…

Key insight: Simulate the FIFO replacement exactly, track the frame contents and evictions. On a hit do nothing; on a miss evict the oldest-inserted page.

Three page frames (capacity = 3):

• Reference 0 -> frames = [0, -, -] — page fault (1)

• Reference 1 -> frames = [0, 1, -] — page fault (2)

• Reference 2 -> frames = [0, 1, 2] — page fault (3)

• Reference 3 -> evict 0 -> frames = [3, 1, 2] — page fault (4)

• Reference 0 -> evict 1 -> frames = [3, 0, 2] — page fault (5)

• Reference 1 -> evict 2 -> frames = [3, 0, 1] — page fault (6)

• Reference 4 -> evict 3 -> frames = [4, 0, 1] — page fault (7)

• Reference 0 -> hit -> frames = [4, 0, 1] — no fault (7)

• Reference 1 -> hit -> frames = [4, 0, 1] — no fault (7)

• Reference 2 -> evict 4 -> frames = [1, 4 replaced by 2 results in ordering; effective frames = [1,4,2] ] — page fault (8)

• Reference 3 -> evict 1 -> frames = [4, 2, 3] — page fault (9)

• Reference 4 -> hit -> frames = [4, 2, 3] — no fault (9)

Four page frames (capacity = 4):

• Reference 0 -> frames = [0, -, -, -] — page fault (1)

• Reference 1 -> frames = [0, 1, -, -] — page fault (2)

• Reference 2 -> frames = [0, 1, 2, -] — page fault (3)

• Reference 3 -> frames = [0, 1, 2, 3] — page fault (4)

• Reference 0 -> hit — no fault (4)

• Reference 1 -> hit — no fault (4)

• Reference 4 -> evict 0 -> frames = [1, 2, 3, 4] — page fault (5)

• Reference 0 -> evict 1 -> frames = [2, 3, 4, 0] — page fault (6)

• Reference 1 -> evict 2 -> frames = [3, 4, 0, 1] — page fault (7)

• Reference 2 -> evict 3 -> frames = [4, 0, 1, 2] — page fault (8)

• Reference 3 -> evict 4 -> frames = [0, 1, 2, 3] — page fault (9)

• Reference 4 -> evict 0 -> frames = [1, 2, 3, 4] — page fault (10)

Result: Three frames => 9 page faults; Four frames => 10 page faults. This example also demonstrates Belady's anomaly, where increasing the number of frames increases the number of faults.