GATE CSE 2025 | Set 2 | Question: 37

Question

​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):
$$  \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?

• A. Least Recently Used page replacement policy
• B. Least Frequently Used page replacement policy
• C. Most Frequently Used page replacement policy
• D. Optimal page replacement policy

Comments

option A) LRU - at Reference 4, LRU would replace Page 1 (oldest), but the given data replaces Page 2. so not LRU.

option B) LFU - at Reference 4 , when all the inserted pages have Frequency=1, so here we use FIFO, so 1 should replace instead of 2.

 option C) MFU - same here also at Reference 4 , when all the inserted pages have Frequency=1, so here we use FIFO, so 1 should replace instead of 2.
So ans is D.

Answer 1

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

1) Here LRU fails because 1 is least recently used not 2.
2) Here LFU fails because least used until that point is 5 not 1.
3) Here MFU fails because most used until that point is 1 not 5.
Only Optimal Page Replacement algorithm is correct.

Comments

Tie break for MFU is always FIFO?

---

@Aditya_Anil yes even for LFU ...u can see my answer below i have mentioned it there the tie breaker

---

wrong answer,
tier breaker of LFU and MFU is fifo, so on accessing 4, 1 will get replaced.
In LRU also on accessing 4, 1 will get replace as it is the oldest one.
 

Answer 2

Here request refers to the requested page from the reference string Frame0,Frame1,Frame2 are the contents of 3 frames and * denotes the page fault in :

You can clearly see that none of the LRU,MRU,LFU matches the above contents of the frames and Optimal page replacement alogorithm can only obtain the above result

So,Option D is correct answer

Comments

No @Venkatasai it is NOT TRUE and there is no BY DEFAULT here.

what we have to follow when there is a tie break will be given in the question.

---

@Ekalavyaa yes if given in question, then we have to follow that but here nothing is given as such in the question hence by default it uses FIFO policy only.

---

I think @Ekalavyaa is right . They have given the Complete Page table, which means we should check which replacement policies are consistent with the replacements shown.

For example, at the first replacement, the frames contain 1, 2, and 3, and 2 is replaced. We shouldn't simply assume FIFO as the default tie-breaker. RAND (Random page replacement Policy) used as tie breaker can choose 2, since it randomly selects a page/frame for replacement.

Similarly, for policies like LFU/MFU, ties may require a tie-breaking rule. FIFO can be used as a tie-breaker if the question specifies or permits it, but we shouldn't automatically introduce FIFO just because there is a tie.

The important thing is that the given table is the evidence: check every replacement against each option and eliminate policies that fundamentally cannot produce the shown sequence. If a policy can produce the sequence, including through a legitimate tie-break or random choice, it cannot be ruled out merely because it didn't follow FIFO.

Also this was a MSQ of 2 marks, so maybe they want us to do all this.

Answer 3

option A) LRU - at Reference 4, LRU would replace Page 1 (oldest), but the given data replaces Page 2. so not LRU.

option B) LFU -  LFU is one such page replacement policy in which the least frequently used pages are replaced. If the frequency of pages is the same, then the page that has arrived first is replaced first. Now at reference 4 ie when 4 comes  1 2 3 all of them has a frequency of 1 but as 1 has arrived 1st it should get replaced but instead 2 gets replaced .hence it is not LFU

option c) MFU - MFU Algorithm is a Page Replacement Algorithm in the Operating System that replaces the page accessed a maximum number of times in the past. If more than one page is accessed the same number of times, then the page which occupied the frame first will be replaced ie that arrived 1st should get replaced. Again at reference 4 ie when 4 comes ...1 2 3 all has the same frequency (1 for all) but as 1 arrived 1st it should get replaced but instead 2 got replaced hence it is not MFU

option D) optimal - at reference 4 when 4 comes it sees that out of 1 2 and 3 .. 2 will be used last therefore it replaces with 2 ..at reference 5 ie when 5 comes it sees that out of 1 4 3 .3 will be used last so 3 got replaced and so on ..u can verify it follows optimal page replacement algo

Therefore answer is option D) Optimal page replacement policy

 

Answer 4

At Reference 4, LRU would replace Page 1 (oldest), but the given data replaces Page 2. so not LRU.

At Reference 11(page 1),page frequencies are 1:2 ,2:1 ,3:1 ,4:3 ,5:2. and 1 is replacing 4 which is most frequently used, hence its not LFU.

At Reference 8(page 6),page frequencies are 1:2 ,2:1 ,3:1 ,4:2 ,5:1. but 6 replacing 1 which is MFU , it should have replaced 2 or 3, so not MFU.

It is Optimal page replacement policy because when it is replacing 4 at page reference 4, it is seeing in future that 2 is used at last.

Then again when it is replacing 3 with 5 at page reference 5, it is seeing that 3 is needed after 1. and so on you can keep verifying.

so answer to this MSQ was only D.