The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
404 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 in Operating System by Boss (27.1k points) | 404 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.

#more info read OS BY GALVIN
+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

Please log in or register to answer this question.

Related questions

+1 vote
1 answer
6
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,049 questions
53,194 answers
184,527 comments
70,400 users