GATE CS 2014 Set 2 — Question 43

The resident pages 101 to 120 are never referenced by the program, so the first 20 references (pages 1 to 20) fault and simply take over those 20 frames under every policy. After that the frames hold pages $1, \dots, 20$ and the reference string is the cycle $1, 2, \dots, 100$ repeated, which is the worst case for recency-based eviction.Optimal (OPT). On each fault OPT evicts the page whose next use is farthest in the future. With a cyclic string that is always the page just used, i.e. the most recently used page. Counting faults gives $100$ in the first pass and $80$ in each of the next two passes: 260 faults.MRU. MRU evicts the most recently used page, which in this cyclic string is exactly OPT's victim at every fault, so MRU makes the same choices and also incurs 260 faults.LRU and FIFO (A, B). Both evict the page that is needed again soonest (the oldest one), so every one of the $300$ references faults: 300 faults.LIFO (C). LIFO evicts the page loaded last. It keeps pages $1, \dots, 19$ fixed and cycles all other pages through one frame, so only 19 pages hit per pass: $100 + 81 + 81 = 262$ faults, two more than OPT.Only MRU matches the optimal policy.Answer: (D) Most-recently-used