GATE CSE 2014 Set 2 | Question: 33

Question

A computer has twenty physical page frames which contain pages numbered $101$ through $120$. Now a program accesses the pages numbered $\text{1, 2, ..., 100}$ in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

• A. Least-recently-used
• B. First-in-first-out
• C. Last-in-first-out
• D. Most-recently-used

Comments

I have the same doubt!

---

@Arjun sir, here all the answers have made the assumption that for MRU the pages 101 to 120 will be swaped out. Can we make assumptions like this in exam? Because in this case Optimal will not behave exactly like MRU, and the reason is the twenty pages that were already loaded. Please note here I have taken the sequence as 1,2,3,.....99,100,1,2,3......99,100,1,2,3.....99,100.
  
Please correct me if I am wrong, according to my calculations, in Optimal we will get 40/300 page hit rate, and in MRU we will get 0/300 Page Hit Rate. 
I know MRU and Optimal work exactly same when the sequence is in a loop but in this question, the twenty frames are already loaded and that is what is making the difference. 

---

Refer this comment https://gateoverflow.in/1992/gate2014-2-33?show=116681#c116681

Answer 1

The page frame access sequence is

1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,

Using OPTIMAL replacement method from first 1....100 , first 20 page fault will take place as there are no common pages ,,from 21 to 100 again page fault will take place (these page fault will be equivalent to using MRU replacement method ). after these replacement the page frames will contain [1.....19,100] no pages .Considering the next sequence,no page fault from 1 to 19 and at the 20 page no ,19 will get replaced from the page frame and in the further sequence till 99 there will be page fault(these will be equivalent to using MRU ) and the resulting pages in frames will be 1...18 ,99,100 . going through the further sequence we will get the total page fault as 260 ......... replacing the pages using optimal method is equivalent to MRU replacement method thus answer (D)

Comments

which contain pages numbered 101 through 120

Now for page access 1, one of the frame gets replaced and the most recently used frame becomes 1. So, during the next access to page numbered 2, shouldn't page 1 be replaced as per MRU policy? 

---

hm yes sir ,i didnt consider that :(

---

Actually yo are correct. Pages 101-120 are not referenced by the current process. So, they are replaced first even with MRU policy.

---

arjun sir i am getting the same no of page faults for LIFO also. LIFO will also behave as MRU after the frames 1-20 are present in the frames. please clear this huge doubt.

And as you are saying- " Pages 101-120 are not referenced by the current process. So, they are replaced first even with MRU policy." Isnt it the case for LIFO too????

---

problem with LIFO is :

initially we had 101 ,102,....120 when we load frame no1 then last in was 120 and 1 replaced in 120 ,then when frame 2 come last used was frame 1 again frame 1 replaced, subsequently in the same page frame(i.e 10th frame) we have to replace all the 300 next pages. so number of miss will be 300. but in optimal we have 260 missed. as explained above by arjun sir.

---

Sir, how can MRU policy replace the pages that aren't in it's sequence? MRU derives which pages to remove only from it's own sequence.

Answer 2

Optimal PRA(Page Replacement Algorithm) behaves like MRU PRA  when the sequence is repeated only in case, where the frames are empty.

Here, the frames are already initialized with 101 to 120. So, none of the given options are correct.

 

Answer 3

OPTIMAL will take 340 ( 100 +80+80+80 ) page faults.

FIFO will take 400( 100 +100+100+100 ) page faults.

LRU will take 400( 100 +100+100+100 ) page faults.

MRU will take 340( 100 +80+80+80 ) page faults.

LIFO will take 343 ( 100+81*3 ) page faults

The answer is (D)

Answer 4

I don't Know how are they getting 300+ page fault even there are only 300 numbers  lets say if every page number gets one page fault then max would be 300...My answer is

Caption

OPTIMAL=260

LRU=FIFO=300

LIFO=262

MRU=260

 

Comments

its done once then repeated thrice, still MRU is the correct option