Project ForgeConsider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 on a demand paged virtual memory system with main memory size of 3 page frames, which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then
- AOPTIMAL < LRU < FIFO
- OPTIMAL < FIFO < LRU
- COPTIMAL = LRU
- DOPTIMAL = FIFO
Explanation
FIFO: faults on 1,2,3,4,1,2 (evicting oldest each time) = 6 faults. LRU: faults on every reference except the repeat of 2 at position 4 (tracing the recency stack shows each subsequent reference is a miss because the working set keeps cycling through more distinct pages than fit in 3 frames) = 9 faults. OPTIMAL (Belady's, evicting the page used furthest in the future): faults on 1,2,3,4,1(hit),3(hit),2,4(hit),1(hit) = 5 faults. So OPTIMAL(5) < FIFO(6) < LRU(9).
Source: GATE CS 2012 (2012)
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.