The Gateway to Computer Science Excellence
+44 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 (105k points)
edited by | 8.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. 

9 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 (621 points)

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
50,648 questions
56,429 answers
99,921 users