876 views
6 votes
6 votes

Strangely, if we let $S^R$ be the reverse of a reference string S, then the page-fault rate for the OPT algorithm on S is the same as the page-fault rate for the OPT algorithm on $S^R$ . Similarly, the page-fault rate for the LRU algorithm on S is the same as the page-fault rate for the LRU algorithm on $S^R$ .

Can anyone explain why is it true?? The line just before this says - "We can think of this(referring to LRU) strategy as the optimal page-replacement algorithm looking backward in time, rather than forward."

So, shouldn't it be:

page-fault-rate(OPT($S$)) = page-fault-rate(LRU($S^R$))

???

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
Purple asked Nov 29, 2016
725 views
Answer given is B, but I think it should be D. Stack will pop the least recently used page from the top. How can having most recently used page on top help in LRU impleme...
1 votes
1 votes
2 answers
2
muthu kumar asked Dec 15, 2018
475 views
How the value is 36? im getting 39.
1 votes
1 votes
1 answer
3
Xylene asked Aug 11, 2017
1,009 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 ?