The LFU algorithm: Can someone please explain this? 1

[Cake]

Hello everyone,
I'm not sure exactly where to post a question like this,
but beings most OSs are written in C and most algorithms are
platform independent, I figured this is the best place to
post unless someone knows of another forum here at Tek-Tips.

I want to find out more about LFU than it just stands
for Least Frequently Used. It is a page replacement
algorithm and that's about all I can find about it. I can
find several things on OPT, LRU, and FIFO, however it does
not help much.

So here's my question: How can I find out and prove that
this certain algorithm (LFU) is or isn't a stack algorithm.

Much thanks,
Cake.

 

[mbaranski]

LFU is the following:

You have a list of memory page references and integers, basically this keeps track of which pages are in memory. Think of it as a data structure containig a memory reference and a counter.

Each time you access a page, up the counter.

When you have to replace the page, select the one with the lowest counter. I don't know if after that you'd zero all the counters and start over (that is a lot of overhead) or not.

This should be enough info to prove whether it's a stack algo. or not, what do you think?

MWB. As always, I hope that helped!

Disclaimer:
Beware: Studies have shown that research causes cancer in lab rats.

 

[Cake]

Thanks, that makes more sense when it is explained in
simpler terms. I used Belady's Anomaly and the inclusion
property to prove that it was a stack algorithm. It really
sort of sounds like it's pretty much on a similar track as
LRU.

I don't think you'd zero every counter, I've heard something
about this algorithm with heavily accessed pages sticking
in memory and never being released after they are not used
anymore - exactly for that reason. Anyway, who knows.

Thank you so much for your help!!
Cake.