OS Galvin - Doubt

Question

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$))

???

Comments

this doesn't hold true because LRU and Optimal may give different page fault.

yes but Optimal will give same for S and S^r same, LRU will give same for S and S^r

it doesn't mean both Algorithm will give same page fault. both are stack based algorithm i think.

while Optimal look forward, LRU look backward.

---

Is these lines from galvin?

What is page number?

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 .

Is it true always? where u got these lines?

---

@srestha yep! it's given in Galvin and i have seen few such examples also.

---

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

Page fault of S = Page fault of S^R

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

---

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

page 376 in 8th edition

page 416 in 9th edition

---

yes got it :)