440 views
Which of the page replacement algorithm has the property that if we traverse the reference string from start to end or from end to start,the number of page faults will be same?
asked | 440 views
0
LRU AND OPTIMAL

LRU-a page that is not going to be used longest time in past.

OPTIMAL--a page that is not going to be used longest time in future.

+3

Thank you .I have read from galvin.It is clearly mentioned there that in case of lru and optimal the number of page fautls and string and its reverse will be same.

It also mentions about Optimal in forward traverse and lru in reverse traverse.Will we also have same page faults in this case?

Form galvin(LRU)

We can think of this strategy as the optimal page-replacement algorithm looking backward in time, rather than forward.

So if I have string S and Sr as reverse string then can i conclude the following?

1. LRU,Pagefault(S)=Pagefault(Sr)

2.Optimal,Pagefault(S)=Pagefault(Sr)

3.PageFault_IN_LRU(S)=PageFault_IN_Optimal(Sr)

I hope question is clear.

+1
page fault in LRU(s)!=OPTIMAL(Sr)            #page frames=3

consider this string 1,2,3,1,2,3,4,1,2,3,1,2,3,4 #of faluts in LRU=8

reverse=4,3,2,1,3,2,1,4,3,2,1,3,2,1 #of faults in OPTIMAL=6
+1
Thank you for explanation.Got the point