From owner-freebsd-hackers Sun Oct 27 08:35:10 1996 Return-Path: owner-hackers Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id IAA29820 for hackers-outgoing; Sun, 27 Oct 1996 08:35:10 -0800 (PST) Received: from vinyl.quickweb.com (vinyl.sentex.ca [206.222.77.8]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id IAA29812 for ; Sun, 27 Oct 1996 08:35:06 -0800 (PST) Received: from localhost (mark@localhost) by vinyl.quickweb.com (8.7.5/8.7.3) with SMTP id LAA24245 for ; Sun, 27 Oct 1996 11:33:40 -0500 (EST) X-Authentication-Warning: vinyl.quickweb.com: mark owned process doing -bs Date: Sun, 27 Oct 1996 11:33:40 -0500 (EST) From: Mark Mayo To: hackers@freebsd.org Subject: LRU algorithms Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-hackers@freebsd.org X-Loop: FreeBSD.org Precedence: bulk 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