in Operating System
900 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$))

???

in Operating System
900 views

4 Comments

I've tried many Questions and In Optimal and LRU it always satisfies property about,

Page fault of S = Page fault of SR

But that doesn't mean Optimal and LRU are interrelated.

page-fault-rate(OPT(S)) = page-fault-rate(LRU(SR))

This line is true sometimes only. NOT ALWAYS

0
0
@srestha It's given under the Page Replacement topic under LRU page replacement.

page 376 in 8th edition

page 416 in 9th edition
1
1
yes got it :)
0
0

Please log in or register to answer this question.

Related questions