Most Recently Used Policy - Belady's Anomaly

[Anirudd]

Hi Gurus,

 

 

For an algorithm to experience Belady's anomaly, a page that will be referenced in future needs to necessarily evicted.

I understand that MRU as its name stands, removes pages that are needed the most, totally opposite to the idea of locality of reference. Although there are certain instances where it does better than others ( for example in case of a loop).

 

Is it true that MRU can suffer Belady's Anomaly in any unfavorable cases?

 

I have searched for an answer to this query for a day long, but found no explicit answer to this. I believe someone from the Science Forum, can surely help me understand this.

 

Thanks,

Aniruddha

India

Edited September 9, 2012 by Anirudd

[Ben Banana]

I am not highly experienced with such algorithms, though I do have minimal experience. A few nights ago... I was working on some utility for managing buffers in a cache-like way, but I was merely winging it. In fact, I haven't even heard of these terms until today, but I did a quick search on them and soon realized what you are asking. Do you have a working MRU implementation? As far as I can speak, I recommend you do the experimental science and confirm the answer yourself. There's also the likelihood that someone who has a deeper theoretical background in cache algorithms could easily answer this question without necessarily testing it. I'm sorry I can not be of more help to you. Cheers