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

It will be (D) i.e Most-recently-used.

To be clear "repeats the access sequence THRICE" means totally the sequence of page numbers are accessed $4$ times though this is not important for the answer here. 

If we go optimal page replacement algorithm it replaces the page which will be least used in near future.  

Now we have frame size $20$ and reference string is

$$1, 2, \dots, 100,1, 2, \dots, 100,1, 2, \dots, 100, 1, 2, \dots, 100$$

First $20$ accesses will cause page faults - the initial pages are no longer used and hence optimal page replacement replaces them first. Now, for page $21$, according  to reference string page 1 will be used again after $100$ and similarly $2$ will be used after $1$ so, on and so the least likely to be used page in future is page $20$. So, for $21^{\text{st}}$ reference page $20$ will be replaced and then for $22^{\text{nd}}$ page reference, page $21$ will be replaced and so on which is MOST RECENTLY USED page replacement policy.  

PS: Even for Most Recently Used page replacement at first all empty (invalid) pages frames are replaced and then only most recently used ones are replaced.

Comments

how are we talking about more than 300 misses when there are only 300 references?

---

because there are total 400 references in reference string read carefully u will get it.

---

@Arjun when the MRU algorithm is executing 
101 will be replaced by 1.

and now 1 is most recently used hence 1 should be replaced by 2.
and so on 
is this correct 

Answer 2

The optimal page replacement algorithm swaps out the page whose next use will occur farthest in the future. In the given question, the computer has 20 page frames and initially page frames are filled with pages numbered from 101 to 120. Then program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. The first 20 accesses to pages from 1 to 20 would definitely cause page fault. When 21st is accessed, there is another page fault. The page swapped out would be 20 because 20 is going to be accessed farthest in future. When 22nd is accessed, 21st is going to go out as it is going to be the farthest in future. The above optimal page replacement algorithm actually works as most recently used in this case. As a side note, the first 100 would cause 100 page faults, next 100 would cause 81 page faults (1 to 19 would never be removed), the last 100 would also cause 81 page faults.

Comments

How do we get 20 hits? we get 19 hits in the second round(from 1-19), then 20 will replace 100, 21 will replace 20 and so on again till 100. How is 100 considered a hit in this sequence. I can't figure this out. Please explain

---

@Rishav_Bhatt replying too late .... But i think you had also considered "repeat the access sequence thrice" means sequence of page numbers are accessed 4 times.

---

Aware1111 After the first round the sequence we will be having is 1,2,3,4.............19,100. 100 will be placed in the last frame as 20 will be replaced by 21, then 21 with 22 and so on till 100. Now when the second sequence starts till 1-19 there will be a hit now 20 will now be replaced with 19 as 19 is the will be not used for the longest time, similarly 20 by 21 till 99. Now when in the second sequence we come across 100 it will be a hit. Hence in the second sequence, we get 20 hits

Answer 3

The optimal algorithm gives 340 page faults(assuming 3 sequences from 1-100): 

We have 20 frames containing 20 pages:  101, 102, 103, 104.....120. Since these pages are never referred again in future, we will replace them all. So, we now have 1, 2, 3, .... 17, 18, 19, 20 in the frames. 20 would not be used for the longest duration, so we remove 20 and load 21. Repeating this till we reach 100.

Now, we have 1, 2, 3,... 17, 18 , 19, 100. In second repetition we get 19 hits (for 1-19). Now 100 is needed in this repetition but 19 in next.

 (1, 2, 3, 4, .... 19, 20,.... 99, 100  | 1, 2, 3,... 19, 20, 100)

So removing 19 and loading 20^th page. At this instance main memory has

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

20 is the best candidate to remove because it'd be needed later than the rest (like 1 , 2, 3...) in next iteration. So removing 20 and loading 21. Again to accommodate 22, 21 is best candidate to be removed. Repeating this process, we reach 100, which is already present in memory. So total hits become 20. Before the next repetition, main memory has

1, 2, 3, ...18, 99, 100

At the beginning, there would be total 18 hits. Since we need 99 and 100 in this iteration, 18 shall be removed, followed by 19, 20.... till 98. So at the end, again we have 20 hits. In the third iteration too, 17 shall be replaced, 98, 99, 100 already found in main memory, summing up the total hits to 20. So total page faults with optimal algorithm are 100+(100-20)+(100-20)+(100-20)=340

---

This clearly is MRU or most recently used where the latest referred page gets removed. For eg, in first iteration, since 19 was referred last, we removed it. But the frames were not empty at the beginning. Only optimal algorithm looks at the future demands and decides the best course, all the other algorithms make decisions based on previous entries. Hence neither MRU nor LIFO would eliminate all the 20 entries 101, 102, .... 120.

In fact MRU and LIFO in such circumstances would yield same results because they would keep replacing the last entry and perform worst. Thus to answer, we must assume the frames as empty, in which case MRU would better LIFO (because LIFO would remove the last entered page such as 100, thus reducing hits by 1.)

Comments

great answer.

FIFO=LRU=400 page faults

MRU=optimal=340 pf

LIFO=343 pf

---

If there are 300 pages given(1 to 100, 1 to 100, 1 to 100)..then how page faults occur more than 340 ?

---

There are 3 ADDITIONAL repetitions, therefore in total there will 400 pages in the sequence

Answer 4

Correct Answer is MRU. Let's see how

we can convert this problem to 3 pages and 5 page accesses which is accessed 3 times (you can access any no. of times above 2 it does not matter) because ratio of page fault will be same.

Note- Whenever there is repeated sequence like 12345 12345 then optimal convert itself into MRU & whenever there is reverse sequence like12345 54321 then optimal convert itself into LRU.

Comments

@Nitesh Singh 2 Yes bro if we get this idea that "fault rate ratio will be similar",we can save lot of time in exam.But here given like initally 101 to 120 numbered pages are there,so doubt is which one to consider MRU page among them?If we consider like last page 120,then all the faults will occur at 120 for every page since we are not using any other page as per MRU.Then it boiled down to page replacement with no of frames=1.So it should have 300 faults right? Then how  will it be equal with optimal?