Self doubt

Question

What are the reasons behind 'Belady's Anomaly' ?

I think FIFO causes belady's anomaly because it's don't replace pages mindfully , while LRU,OPTIMAL do . They replace the pages mindfully by taking care of locality.

so is Locality of reference reason behind Belady's anomaly ?

Comments

FIFO suffers from Belady's anamoly because it does not follow 'stack rule'

stack rule states that "at any instant the pages which are present with n frames should be subset of pages present with n+k frames , k>=1"

---

Hello joshi , thanks for answering.

Can you please elaborate more about stack rule ...or give me reference ,from where you studied it..

Answer 1

1) Belady's Anomaly is the phenomenon where number of page fault increase when the page frame also increases.

Generally with the increment of page frames , page fault decreases. But in FIFO sometimes this rule violates. and page fault increses when the page frame also increases.

2)LOR is separate case than belady's anomaly. Because LOR only look after if a block is in cache, will it be required near future(Temporal locality) or it's adjacent block will require near future(Spatial locality)

3) May be Optimal page replacement policy sometimes follows Temporal LOR , but we cannot guarantee it . LOR is a block transfer from main memory to cache, to check this block or it's adjacent block are required near future or not.

Comments

Hello srestha

Thanks for answering , after your and joshi's answer i explored more and knew that LOR is not related to Bleady's anomaly. But as you wrote something about page replacement algos and LOR, i am not agree with some of your arguments

1) You wrote "Because LOR only look after if a block is in cache" ..albeit i didn't properly egt what you have mean here , but as per my current knowledge LOR is only a way to know , which data should be our priority to place in cache , because cost to access data in cache is lowest. so your statement is not making any sense to me...

2)The theme behind page replacement algos is "remove the page that is least like to be reference in future"....then how can me know which page is least likely to be reference in future , we know this by LOR concept ...so as per my knowledge , LOR is theme behind the working process of page replacement algos..

FIFO :- remove page that has been in memory the longest  , as the page was in memory from long time so we hope that now we won't need it...so FIFO is not using LOR concept

Optimal :- remove the page whose next reference is longest..although it's not practical to know this but we can bit predict by LOR that these pages are the one who are least likely to be needed now....

LRU :- remove the one that has not been referenced from the longest time , by LOR that is the page that least likely to be referenced in near future....

---

In memory data is stored like block of datas, and not like a single data. So, we can say LOR works like which block of data is required in near future.

And optimal only works like LOR for some point of time.That I have wrote in ans