GATE 2025 CS (CS2) – Question 47
Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):
| Ref | initially | 1* | 2* | 3* | 4* | 5* | 4 | 1 | 6* | 4 | 5 | 1* | 3* | 2* |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 1 | - | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 6 | 2 |
| Frame 2 | - | - | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 | 1 |
| Frame 3 | - | - | - | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 3 | 3 |
The *-marked references cause page replacements.
Which one or more of the following could be the page replacement policy/policies in use?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) Most Frequently Used page replacement policy; (D) Optimal page replacement policy
Explanation
**1. Rule out LRU using an early replacement.** Before reference 4, pages 1,2,3 were loaded in that order. LRU would evict page 1, but the table evicts page 2. Therefore A cannot produce the table.
**2. Rule out LFU.** Before reference 6, page 1 has been referenced twice, page 4 twice and page 5 once. LFU would evict 5, whereas the table evicts 1. Thus B fails.
**3. Check MFU with counts reset on eviction.** At replacements after the initial fills, the evicted pages are 2,3,1,4,5,6. Their counts are maximal among resident pages: first two are ties at 1, then a tie at 2, then 3,2,1. The table can therefore be produced by MFU with suitable tie choices.
**4. Check Optimal using next use.** At reference 4, resident page 2 is needed farthest in the future; at 5, page 3 is farthest. At 6, page 1 is next needed after both 4 and 5, so it is evicted. At the final three replacements the evicted pages are never needed again, so each is an optimal tie choice. **Answers: C,D.**