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
LRU would evict page 1 (not 2) on the reference to 4, so it is ruled out. LFU would evict 5 (lowest count) on the reference to 6, not 1, so it is ruled out. Every replacement is consistent with MFU (counts reset on eviction) and with Optimal (farthest next use).