A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 20 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program? A. Last-in-first-out B. First-in-first-out C. Least-recently-used D. Most-recently-used

GATE 2014 · Operating System · Page Replacement · medium

Answer: LRU gives 20 faults (same as OPT = 20). Answer: C. Least-recently-used

  1. Trace pass 1 for OPT and LRU: Pass 1 access: 1, 2, 3, ..., 20. Page 1 accessed: not in {101..120}: FAULT. OPT evicts some page from {101..120} (all have next_use=infinity since program never uses them). LRU similarly: pages 101..120 have never been accessed by the program, so all are LRU candidates. Both evict one of {101..120} and load page 1. Similarly for pages 2 through 20: each faults; each policy evicts from the shrinking set {101..120}. After page 20 is loaded: all of {101..120} have been evicted, frames = {1..20}. Pass 1 faults = 20 for both OPT and LRU.
  2. Trace passes 2 and 3: After pass 1: frames = {1, 2, ..., 20}. Pass 2 access: 1, 2, ..., 20 — every page already in frames: 0 faults. Pass 3 access: 1, 2, ..., 20 — every page already in frames: 0 faults. OPT total = 20, LRU total = 20.
  3. Check MRU behavior: During pass 1, when page 20 faults (after accessing 1,2,...,19): MRU would evict the most recently accessed page = page 19 (just accessed). This loads page 20 but evicts page 19 from frames. In pass 2: page 1 hits, ..., page 19 faults (evicted by MRU!), MRU now evicts page 20 (most recent). This creates thrashing — MRU causes many more than 20 total faults. MRU does NOT match OPT.
  4. Check FIFO behavior: During pass 1: the initial pages 101..120 are the oldest (loaded before program started). FIFO evicts them in order 101, 102, ..., 120 as program pages 1..20 are loaded. After pass 1: frames = {1..20}. Passes 2 and 3: all hits. FIFO total = 20. FIFO also matches OPT! However, the key subtlety: FIFO evicts based on LOAD ORDER, which requires knowledge of when 101..120 were loaded. If they were loaded at the same 'time' (initial state), FIFO may be ambiguous. LRU is unambiguous — it always evicts 101..120 since they have never been accessed DURING the program's run.