Project ForgeConsider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page-replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?
- Both incur the same number of page faults
- BFIFO incurs 2 more page faults than LRU
- CLRU incurs 2 more page faults than FIFO
- DFIFO incurs 1 more page fault than LRU
Explanation
Tracing FIFO with 5 frames over 3,8,2,3,9,1,6,3,8,9,3,6,2,1,3: faults occur on 3,8,2,9,1,6,3(evicts oldest 3? — careful trace),8,2 giving 9 total faults. Tracing LRU over the same sequence with 5 frames also gives 9 total faults (both policies happen to reach steady state with identical fault counts on this particular reference string, even though their eviction choices differ along the way). Both incur the same number of page faults.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.