Date: Sun, 27 Oct 1996 12:45:41 -0500 (EST) From: "John S. Dyson" <toor@dyson.iquest.net> To: mark@quickweb.com (Mark Mayo) Cc: hackers@FreeBSD.org Subject: Re: LRU algorithms Message-ID: <199610271745.MAA05900@dyson.iquest.net> In-Reply-To: <Pine.BSF.3.94.961027112509.24196A-100000@vinyl.quickweb.com> from "Mark Mayo" at Oct 27, 96 11:33:40 am
next in thread | previous in thread | raw e-mail | index | archive | help
>
> Hi there.. I've been trying to look at more and more of the kernel as my
> knowledge of operating systems increases (you never know, some day I might
> actually be able to contribute something!! :-)) , and I see the LRU (Least
> Recently Used) algorithm used all over the place. I'm familiar with the
> concepts, mostly for page replacement stuff, but I'm a little curious
> about implementation.
>
> Of course, whenver I see LRU mentioned in the source tree, it's tied into
> some enormous purpose, and it's hard for me to see the thing at work :-(
> Basically, I'd like to get familiar with LRU so I can understand it's use
> in the various page, vm, mpool, etc.. spots in the OS (seems to be an
> important bit of conceptual knowledge). But, I can't find a simple
> implementation of LRU anywhere (I search altavista, excite, etc..) -- I'd
> like to figure out some data structures to use with it. I've seen the
> phrases "LRU chain" and "LRU list" used quite often..
>
> I'm assuming it just a doubly linked-list with some extra bits in the
> struct for the modified, present/absent, restricted, etc.. Correct?
>
> Any pointers would be helpful, in a book, or preferably available on the
> net.
>
Conceptually LRU looks like this most of the time in the kernel... First
off, TAILQ and LRU are pretty much compatible. TAILQ allows insertion
onto the end of a list easily.
First define a tailq:
TAILQ_HEAD(,vmpage) pagequeue;
Create an item that has an entry for the list in it.
struct vmpage {
TAILQ_ENTRY(vmpage) queueentry;
} *m;
Then insert the item onto the list at the end:
TAILQ_INSERT_TAIL(&pagequeue, m, queueentry);
Every time you sense the use of the page you will want to:
TAILQ_REMOVE(&pagequeue, m, queueentry);
TAILQ_INSERT_TAIL(&pagequeue, m, queueentry);
This will put the page back onto the end of the queue and
will have the effect of pushing recently used pages onto
the end of the queue. The pages at the beginning of the
queue would be the most likely candidate for removal...
Get the first candidate for removal:
old_m = TAILQ_FIRST(&pagequeue);
Note that this algorithm is only a close approx for LRU
in the case where you sense recent use. It is exactly
LRU if you perform the REMOVE/INSERT operation every
time an access occurs.
There might be some errors in the above, but this gives
an approximation of how to implement LRU with the
queue macros... (And that is the vast majority of our
management of lists nowadays.)
John
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199610271745.MAA05900>