Anonymous user menu

A computer has twenty physical page frames : GATE 2014 - Paper 2

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 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

Answer

Page reference string for the program will be:
1, 2, 3, 4, ..., 100, 1, 2, 3, 4, ..., 100, 1, 2, 3, 4, ..., 100.
The current status of 20 frames shows page numbers from 101 to 120. Implementation of optimal page replacement policy for above given page reference string would be as follows:

So, there would be 300 page faults in total (each access 100 page faults). Also it is visible that every time a replacement is done for the page which is most recently referred as it will be least recently referred in future. So, for the given page reference string
optimal page replacement policy is working same as most recently used policy and thus number of page faults will be same in both of them.

So, the correct answer is option (D).

1Comment
Sourav Pal @sp995
23 Sep 2017 11:35 am

i think solution is wrong