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

Answer: (D)

Explanation: 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.

 

Iteration 1: (1-100) Not present – all replaced 1-20 in 20 frames, 21-100 in 20th frame. hence, page faults = 100

Iteration 2: (1-19) present | (20-99) NOT present | (100) present – the replacements are done at the 19th frame hence, page faults = 100 – 19 – 1 = 80

Iteration 3: (1-18) present | (19-98) NOT present | (99-100) present – the replacements are done at the 18th frame hence page faults = 100 – 18 – 2 = 80

Iteration 4: (1-17) present | (17-97) NOT present | (98-100) present – the replacements are done at the 17th frame hence page faults = 100 – 17 – 3 = 80

 

Total page faults = 100 + 80 + 80 +80 = 340

 

Along with generating same number of page faults M.R.U also generates replacements at the same positions as in the Optimal algorithm.(Assuming the given 101-120 pages are INVALID (not belonging to the same process) or Empty).

While the LIFO replacement does not behave like Optimal replacement algorithm as it generates 343 page faults. Because from 21st page all pages are placed in 20th frame, therefore hits per iteration reduces down to 19 from the 2nd iteration of pages. Whereby

Total Page faults = 100 + 81 + 81 + 81 = 343

Answer 2

101….120 are already loaded in 1…..20...by MRU we would end up replacing 20^th frame(120) as this is most recently used..I dont think it will match Optimal Algo..

Answer 3

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

INIT

{101,102,103....120}

 

OPTIMAL:

Round 1:

{1,2,3....100} == 100

Round 2:

{1,2,3....18,99,100} == 80  HIT {1-19,100}

Round 3:

{1,2,3....18,99,100} == 80  HIT {1-18,99,100}

Round 4:

{1,2,3....17,98,99,100} == 80  HIT {1-17,98,99,100}

Total = 340