GATE 2025 CS2 Q.47: solution and answer

Official answer: DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Number the references by position: $$\begin{array}{cccccccccccccc}\text{Position}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13\\ \text{Reference}& 1& 2& 3& 4& 5& 4& 1& 6& 4& 5& 1& 3& 2\end{array}$$ From the table, the evictions are: position 4 (page 4) evicts 2, position 5 (page 5) evicts 3, position 8 (page 6) evicts 1, position 11 (page 1) evicts 4, position 12 (page 3) evicts 5, and position 13 (page 2) evicts 6. Positions 6, 7, 9 and 10 are hits.

2. LRU (A). At position 4 the frames hold 1, 2 and 3, last used at positions 1, 2 and 3. The least recently used page is 1, so LRU evicts 1. The table evicts 2, so the policy is not LRU.

3. Frequency counts. For LFU and MFU, a page's frequency is the number of times it has been referenced in the string so far. Before position 8 the counts are $1:2$ (positions 1 and 7), $4:2$ (positions 4 and 6) and $5:1$ (position 5). Before position 12 the pages in frames have counts $6:1$ (position 8), $1:3$ (positions 1, 7 and 11) and $5:2$ (positions 5 and 10).

4. LFU (B). At position 8 the frames hold 1, 4 and 5 with counts 2, 2 and 1. LFU must evict 5, the least frequently used page. The table evicts 1, so the policy is not LFU. All three pages entered memory once and were never evicted before this point, so the counts are the same whether or not a count is reset on eviction. LFU fails either way.

5. MFU (C). At position 12 the frames hold 6, 1 and 5 with counts 1, 3 and 2. MFU must evict page 1, the most frequently used page. The table evicts 5, so the policy is not MFU. There is a second, separate failure at position 4. The three pages in frames each have count 1, so MFU has a tie, and both usual tie-breaks pick page 1: oldest-loaded first (FIFO) and least recently used. The table evicts 2.

6. Optimal (D). At each replacement, evict the page whose next use is farthest away, or a page that is never used again. Position 4: frames 1, 2, 3, next used at 7, 13 and 12, so evict 2. Matches. Position 5: frames 1, 4, 3, next used at 7, 6 and 12, so evict 3. Matches. Position 8: frames 1, 4, 5, next used at 11, 9 and 10, so evict 1. Matches.

7. Optimal, continued. At position 11 the frames hold 6, 4 and 5, and the rest of the string is 3, 2. None of the three pages is used again, so evicting any of them is optimal, including the table's choice of 4. At position 12 the frames hold 6, 1 and 5, and only 2 follows, so evicting 5 is optimal. At position 13 nothing follows, so evicting 6 is optimal. Every replacement in the table is one that Optimal can make.

8. Only the Optimal policy fits every replacement in the table. The answer is (D).