476 views

2 Answers

Best answer
2 votes
2 votes
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$
selected by
2 votes
2 votes

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

Related questions

1 votes
1 votes
1 answer
1
Xylene asked Aug 11, 2017
1,012 views
Consider page references, 1,2,3,5,2,3,4 and number of frames = 3.In the end will the frame contain 4,2,3 or 5,4,3 ?
1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
4
Jyoti Kumari97 asked Jan 15, 2019
510 views
Assume there are 5 frames and consider the following reference string find the number of page faults using NRU page replacement algorithm.3,2,3, 0,8,4,2,5,0,9,8,3,2