Consider the memory reference string given below for a memory with 3 frames…

FIFO (First-In-First-Out) page replacement keeps the resident pages in a queue ordered strictly by arrival time. Every reference to a page not currently resident is a fault; when the frames are full, that fault evicts the page that has been resident the longest, regardless of how recently it was used, and a hit never changes the queue order.

1. Reference 1: not resident, frames are not full yet -> load 1 -> queue (oldest to newest): [1] -> fault.

2. Reference 2: not resident -> load 2 -> queue: [1, 2] -> fault.

3. Reference 3: not resident -> load 3 -> queue: [1, 2, 3] -> fault.

4. Reference 4: not resident, frames full -> evict the oldest page, 1 -> queue: [2, 3, 4] -> fault.

5. Reference 1: not resident -> evict the oldest page, 2 -> queue: [3, 4, 1] -> fault.

6. Reference 2: not resident -> evict the oldest page, 3 -> queue: [4, 1, 2] -> fault.

7. Reference 5: not resident -> evict the oldest page, 4 -> queue: [1, 2, 5] -> fault.

8. Reference 1: already resident -> queue unchanged: [1, 2, 5] -> hit.

9. Reference 2: already resident -> queue unchanged: [1, 2, 5] -> hit.

10. Reference 3: not resident -> evict the oldest page, 1 -> queue: [2, 5, 3] -> fault.

11. Reference 4: not resident -> evict the oldest page, 2 -> queue: [5, 3, 4] -> fault.

12. Reference 5: already resident -> queue unchanged: [5, 3, 4] -> hit.

Cross-check by counting hits instead of faults: only three of the twelve references land on an already-resident page - the repeated references to 1 and 2 once 5 has replaced 4, and the final reference to 5 - so the remaining nine references are faults, matching the step-by-step trace above.

FIFO page replacement with 3 frames therefore produces nine page faults for this reference string.