OS Optimal Page replacement

Question

How the value is 36? im getting 39.

 

Answer 1

In the first pass of the string, there will be $15$ page faults.

$Number\,of\,page\,faults = 15$

There are 8 page frames, using optimal the values would be : $1|2|3|4|5|6|7|15$

On the second pass of the string, there is no page fault until $7$ as $8$ comes it will replace $7$, $9$ will replace $8$, this process continues until $14$ and at $15$ there is no page fault.

$Number\,of\,page\,faults = 15 + 7$

The page frames are : $1|2|3|4|5|6|14|15$

In the third pass of the string, there is no page fault until $6$ as $7$ comes it will replace $6$ this process continues until $13$ and at $14$ and $15$ there is no page fault.

$Number\,of\,page\,faults = 15 + 7 + 7$

The page frames are : $1|2|3|4|5|13|14|15$

In the fourth pass of the string, there is no page fault until $5$ as $6$ comes it will replace $5$ this process continues until $12$ and at $13$, $14$ and $15$ there is no page fault.

$Number\,of\,page\,faults = 15 + 7 + 7 + 7 = 36$

The page frames are : $1|2|3|4|12|13|14|15$

Answer 2

We are given 8 page frames and the requests are as:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15.

Optimal Page Replacement Algo states that whenever a page has to be swapped out we swap out a page whose occurence is farthet in the memory.

So as we are given 8 page frames and the string is repeated 4 times then :

Request String becomes:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15.

1

2

3

4

5

6

7

8

As initially the page frame is empty page faults:8

Now when 9 comeas page 1 to 7 wont be flushed out only the last page will be flushed out till 15 So Page faults=8+7=15

 

1

2

3

4

5

6

7

15

 

There will be no page faults for 1 to 7. When 8 comes 7 will be flushed out(it would be referred the farthest look at the given string).

So everytime this cell will be used So now page faults are :15+7(i.e 14-8+1)=23.

1

2

3

4

5

6

14

15

 

Now no page faults for 1,2,3,4,5 and 6. When 7 comes page fault start occuring and the cell with value 6 will always be replaced. So page fault occur for 7,8,9,10,11,12,13. No of page faults=23+7=30

Now the table is:

1

2

3

4

5

13

14

15

 

Page fault occurs for: 6,7,8,9,10,11,12 i.e 6 pages Total no of page faults=30+6=36

Hence total no of page faults=36