A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 3, 4, 7, 4, 6, 3, 1 Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy? A. 0 B. 1 C. 2 D. 3

GATE 2007 · Operating System · Page Replacement · medium

Answer: LRU has 1 more page fault than Optimal. Answer: B. 1

1. Simulate LRU page replacement: Access 1: miss, frames=[1], recency:1, faults=1 Access 2: miss, frames=[1,2], recency:1<2, faults=2 Access 3: miss, frames=[1,2,3], recency:1<2<3, faults=3 Access 4: miss, LRU=1 (oldest). Evict 1. frames=[2,3,4], recency:2<3<4, faults=4 Access 7: miss, LRU=2. Evict 2. frames=[3,4,7], recency:3<4<7, faults=5 Access 4: hit. frames=[3,7,4], recency:3<7<4(refreshed), faults=5 Access 6: miss, LRU=3. Evict 3. frames=[7,4,6], recency:7<4<6, faults=6 Access 3: miss, LRU=7. Evict 7. frames=[4,6,3], recency:4<6<3, faults=7 Access 1: miss, LRU=4. Evict 4. frames=[6,3,1], faults=8
2. Compute the difference: LRU faults = 8 Optimal faults = 7 Extra faults = 8 - 7 = 1