Skip to content
GATETECH
Official PYQ · 2025Set 2 · Q37Memory Management and Virtual MemoryMCQ2 marks

GATE CS 2025 Set 2 Q37 — Memory Management and Virtual Memory

Explain with AI

​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):
initiallyafter−1∗2∗3∗4∗5∗416∗451∗3∗2∗−1111111666662−−224444444111−−−33555555533\begin{array}{|c|lllllllllllll|} \hline \text{initially} & \text{after} \\ \hline -&1^* &2^* & 3^* & 4^* & 5^* & 4 & 1 & 6^* & 4 & 5 & 1^* & 3^* & 2^* \\ \hline -&1 & 1 & 1 & 1 & 1 & 1 & 1 & 6 & 6 & 6 & 6 & 6 & 2 \\ \hline -&- & 2 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 1 & 1 & 1 \\ \hline -&- & - & 3 & 3 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 3 & 3 \\ \hline \end{array}
The *-marked references cause page replacements.

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

Choose one option
View worked solution

Answer: D

To determine which page replacement policy is used, we analyze the page replacement decisions at key steps:

  1. Least Recently Used (LRU): At step 4 (reference to page 4), the frames contain [1, 2, 3]. The least recently used page is 1. However, page 2 is replaced instead. Thus, LRU is not used.
  2. Least Frequently Used (LFU): At step 8 (reference to page 6), the frames contain [1, 4, 5]. The frequencies of the pages in memory are:
    • Page 1: 2 times (at steps 1 and 7)
    • Page 4: 2 times (at steps 4 and 6)
    • Page 5: 1 time (at step 5)
    LFU should replace page 5 (lowest frequency), but page 1 is replaced instead. Thus, LFU is not used.
  3. Most Frequently Used (MFU): At step 12 (reference to page 3), the frames contain [6, 1, 5]. The frequencies of the pages in memory are:
    • Page 6: 1 time (at step 8)
    • Page 1: 3 times (at steps 1, 7, and 11)
    • Page 5: 2 times (at steps 5 and 10)
    MFU should replace page 1 (highest frequency), but page 5 is replaced instead. Thus, MFU is not used.
  4. Optimal Page Replacement: Let's check the decisions under Optimal policy:
    • At step 4 (reference to 4): Frames are [1, 2, 3]. Future references are 1 (step 7), 3 (step 12), and 2 (step 13). Page 2 is referenced furthest in the future, so it is replaced. (Matches trace)
    • At step 5 (reference to 5): Frames are [1, 4, 3]. Future references are 4 (step 6), 1 (step 7), and 3 (step 12). Page 3 is referenced furthest in the future, so it is replaced. (Matches trace)
    • At step 8 (reference to 6): Frames are [1, 4, 5]. Future references are 4 (step 9), 5 (step 10), and 1 (step 11). Page 1 is referenced furthest, so it is replaced. (Matches trace)
    All subsequent decisions are also consistent with the Optimal policy (where pages with no future references are replaced). Thus, Optimal is the policy in use.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Management and Virtual Memory questions