Made easy workbook

Question

The number of page faults with a given string "S " using LRU algorithm is "N" and considering the reverse of string S^R the number of page faults will be

A)N.                    B)N/2

C)2N.                  D)3.75N

Comments

A. It will remain same as LRU is stack based Algorithm.

---

Please sir explain it.

---

It is Given in the Galvin. I haven't yet been able to find its formal proof and neither couldn't prove it yet myself. As soon as I find a proof or prove it myself formally, I will post it here. Or someone else might prove it.

But I am pretty sure that this Phenomenon must be True because of Stack Algorithm property that LRU and Optimal possess. 

 

---

Brother, even though in case of optimal algorithm it provides same no.of faults, but those are not same

i mean on string s, a is hit, on reverse of a string may be b is hit--- but finally no.of hits are equal.

 

But incase of LRU, those elements also same, i mean on string s, a is hit, on reverse of a string also a is hit

Answer 1

Option A is right, yes it will be same.

by checking examples you can get this...

but we should have to understand why this is so?

 

if the string is  __ __ __ __ Y __ __ Y __ __ 

for the first time Y will be Page Fault, but  assume Y is hit. ( due to come within the range of no.of frames. )

 

Reverse of String is  __ __ Y __ __ Y __ __ __ __

for the first time Y will be Page Fault, but Y should be hit ( due to distance between them is not changed. )

 

Therefore hit's are preserved ===> No.of Faults Same

 

Comments

Your logic will make it True for ALL the Page Replacement algorithms that are there. Because It does not say anything about LRU or Stack etc.

---

How it will be true for FIFO?

Reverse of String is  __ __ Y __ __ Y __ __ __ __

let Y is bought at very first,  after Y it has a new symbol X, but think that all frames allocated to that process are full, then X should replace Y, due to this reason it is not true.

---

Why this is working for LRU? 

because in LRU, by getting a page at time t, it should be present in memory upto t+(n-1) time,

if hit in String s ===> same page referred btw t+1 to (t+(n-1))+1

String S^R  ===> the distance between those two pages ( for considering hit) does not changed, therefore hit will be preserved.