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.
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
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.
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:
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