Project ForgeLeast Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the reference string 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 (3 page frames, all initially empty), how many more page faults occur with LRU than with the optimal page replacement policy?
- A0
- B1
- 2
- D3
Explanation
Trace with LRU (evict least-recently-used): 1(F),2(F),1(H, MRU=1,2),3(F)→{3,1,2}, 7(F, evict LRU=2)→{7,3,1}, 4(F, evict LRU=1)→{4,7,3}, 5(F, evict LRU=3)→{5,4,7}, 6(F, evict LRU=7)→{6,5,4}, 3(F, evict LRU=4)→{3,6,5}, 1(F, evict LRU=5)→{1,3,6}. LRU faults = 9 (only the second '1' reference hits). Optimal faults = 7 (from the previous question). Difference = 9-7 = 2.
Source: GATE CS 2007 (2007)
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.