Page Replacement optimal verses MRU

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

=============================================================

First of all how many Page Faults are there in optimal PRA?

I'm getting as following -

100 PF in 1st access of 100 pages.

80 PF in 2nd access of 100 pages.

80 PF in 3rd access of 100 pages.

Totally = 100+80+80 = 260 PF are there out of total 300 references of 100 pages.

Is that correct? whereas some people are having like -

100+(100-19)+(100-19) PF and some are going for 4th round. why the need to go to 4th access of 100 pages?

Answer 1

As far as number of sequences are concerned, it depends on how you read the problem statement.

Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE.

From this line, I perceive that program has accessed this sequence once and again repeats this sequence thrice. So, total four times.

But, I think here number of sequence is not that important. We just need to find page replacement pattern of the given policies in the options, which is similar to Optimal Page Replacement policy.

For the above sequence, which is

1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100

Both First-In-First-Out and Least-Recently-Used policies perform the same way and give same number of page faults. (Not always, but for this sequence)

For both of these policies, the number of page faults are 400. A program will make a replacement for every new page. For the first 20 pages from sequence, program replace the older pages 101 to 120. Then for every new page, a replacement is made in similar fashion.

21st page in place of 1st page

22nd page in place of 2nd page and so on.

After every 20 iteration, a frame will contain entire new set of pages.

Similarly, Last-In-First-Out performs the same way as Most-Recently-Used for this sequence and gives same number of page faults as Most-Recently-Used policy.

Here every time the last page is replaced by the new one.

So, 120th page is replaced by 1st page

1st page is replaced by 2 and so on.

So, here also 400 page faults occurs.

But, I don't think any of the given policy performs the same way as Optimal PR.

In Optimal PR, we'll have 100 + (100-19) + (100-19) + (100-20) = 342 page faults.