The GATE Grind

GATE 2025 CS (CS2) – Question 47

Operating System · Memory Management and Virtual Memory · 2 marks · Multiple select

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):

Refinitially1*2*3*4*5*416*451*3*2*
Frame 1-1111111666662
Frame 2--224444444111
Frame 3---33555555533

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

  1. Least Recently Used page replacement policy
  2. Least Frequently Used page replacement policy
  3. Most Frequently Used page replacement policy
  4. Optimal page replacement policy

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.**

More Memory Management and Virtual Memory questions

All Memory Management and Virtual Memory questions →