Date: Sun, 27 Oct 1996 11:33:40 -0500 (EST) From: Mark Mayo <mark@quickweb.com> To: hackers@freebsd.org Subject: LRU algorithms Message-ID: <Pine.BSF.3.94.961027112509.24196A-100000@vinyl.quickweb.com>
next 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. TIA, Mark ------------------------------------------- | Mark Mayo mark@quickweb.com | | C-Soft www.quickweb.com | ------------------------------------------- "To iterate is human, to recurse divine." - L. Peter Deutsch
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.3.94.961027112509.24196A-100000>