Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

The LFU algorithm: Can someone please explain this?

The LFU algorithm: Can someone please explain this?

The LFU algorithm: Can someone please explain this?

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,

RE: The LFU algorithm: Can someone please explain this?

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?


As always, I hope that helped!

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

RE: The LFU algorithm: Can someone please explain this?

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

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!!

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close