The LFU algorithm: Can someone please explain this?
The LFU algorithm: Can someone please explain this?
(OP)
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.
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.
Talk To Other Members
RE: The LFU algorithm: Can someone please explain this?
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.
RE: The LFU algorithm: Can someone please explain this?
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.