GATE - 2014 | OS | A computer has twenty physical page frames which contain pages

GATE - 2014 [Operating System]

Question:

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

Solution:

Option (D) is Correct.

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 the future.

So, for the given page reference string optimal page replacement policy is working the same as the most recently used policy and thus the number of page faults will be the same in both of them.

Thank You