The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
427 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.2k points) | 427 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
49,411 questions
53,594 answers
185,830 comments
70,878 users