The Gateway to Computer Science Excellence
+52 votes

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?

  1. Least-recently-used
  2. First-in-first-out
  3. Last-in-first-out
  4. Most-recently-used
in Operating System by Veteran
edited by | 10.2k views
Why we can't consider Last In First Out ?

Each time it will replace the most recent frame only like MRU, so how option D is more appropriate than option C ?

For other readers please read @Shreya Roy's comment for getting difference between LIFO and MRU.

How  many Page fault will occur?

I think there would be

Optimal: 260-page fault

MRU: 260-page fault

LIFO: 262-page fault

NOTE (if reference string has 300-page request i.e 1 2 .... 100 1 2 .... 100 1 2 .... 100 and demand paging is used)

I think in MRU  when 1st page is arrived then it  replace  101 or any of 101 .....120 .Then when the 2nd page comes then it will replace 1St page ,,isnt as it is used most recent.Then how optimal page replacement algorithm is same as MRU . I think no option is correct.correct me if i am wrong.
what if in in the second round access is reverse means 100 to 1

then the answer for the same question would  be FIFO or not ?

please confirm.
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. 


10 Answers

0 votes

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







by Junior
0 votes

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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
118,145 users