GATE Overflow Test Series | Operating Systems | Test 2 | Question: 27

Question

A computer has twenty physical page frames which contain pages numbered $1001$ through $1020$ entered in order. Now a program accesses the pages numbered $1001, 1002, \dots, 1100$ in that order, and repeats the access sequence once in the reverse order. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program? (Mark all the appropriate choices)

• A. Least-recently-used
• B. First-in-first-out
• C. Most-recently-used
• D. Last-in-first-out

Answer 1

Consider FIFO: First $20$ accesses will be page hits. Then the page frame $1001$ will be replaced by frame $1021, 1002$ will be replaced by frame $1022$ and so on, all further accesses will be page faults until $1100$ is accessed. Then, we'll have $20$ more page hits in the reverse direction for page frames $1100-1081.$ So, for $200$ page frame accesses we'll have $200-40=160$ page faults. This is indeed same as optimal replacement strategy because we are replacing the page frame which is going to be accessed furthest in future.

LRU is same as FIFO for the given access sequence.

For MRU, first $20$ accesses will be page hits. Then, page frame $1021$ replace $1020, 1022$ will replace $1021$ and so on until $1100$ will replace $1099.$ In the reverse direction, $1100$ will be a page hit. Then, $1099$ will replace $1100, 1098$ will replace $1099$ and so on until $1020$ replacing $1021.$ Then $1019-1001$ will be hits. So, total page faults $ = 200 - 20 - 1 -19 = 160.$

LIFO will also follow the MRU sequence.

So, the correct answer is $A;B;C;D.$