GATE CS 2025 Set 2 Q.47: Memory Management and Virtual Memory

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

initially                 after
    -     1* 2* 3* 4* 5* 4 1 6*  4  5 1* 3* 2*
    -      1  1  1  1  1 1 1  6  6  6  6  6  2
    -      -  2  2  4  4 4 4  4  4  4  1  1  1
    -      -  -  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?

Least Recently Used page replacement policy

Least Frequently Used page replacement policy

Most Frequently Used page replacement policy

Optimal page replacement policy

Official answer and solution

Official answer: D
From: Official GATE 2025 answer key

Solution

Check each page replacement against future page references (Optimal) and past usage history (LRU, LFU, MFU).

Let us check the replacements after the first three cold misses (1*, 2*, 3*), when the frames hold {1, 2, 3}:

At 4*: Page 2 is replaced, leaving {1, 4, 3}.
- Under LRU, 1 is the least recently used page, so LRU would evict 1 (eliminating A).
- Under Optimal, future references are 5 4 1 6 4 5 1 3 2: 1 is used at index 7, 3 at index 12, and 2 at index 13 (farthest in the future). Thus Optimal evicts 2.
At 5*: Frames hold {1, 4, 3}; page 3 is evicted, leaving {1, 4, 5}.
- Under MFU and LFU, all three pages {1, 4, 3} have frequency $1$ ; with FIFO tie-breaking, LFU would evict 1, and MFU at later steps (6* when 4 and 5 have frequency $2$ while 1 is evicted with frequency $2$ ) also fails.
- Under Optimal, future references are 4 1 6 4 5 1 3 2: 4 is used next, then 1, and 3 is used farthest in the future, so Optimal evicts 3.
At 6*: Frames hold {1, 4, 5}; future references are 4 5 1 3 2. Since 1 is referenced farthest in the future (after 4 and 5), Optimal evicts 1.
At 1*, 3*, 2*: At 1* (frames {6, 4, 5}, future 3 2), none of {6, 4, 5} is used again, so Optimal can evict 4; similarly at 3* it evicts 5, and at 2* it evicts 6.

Thus Optimal page replacement policy (D) is the only matching policy.

Final answer

Option (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 47 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source