From owner-freebsd-hackers Sun Oct 27 09:46:01 1996 Return-Path: owner-hackers Received: (from root@localhost) by freefall.freebsd.org (8.7.5/8.7.3) id JAA03889 for hackers-outgoing; Sun, 27 Oct 1996 09:46:01 -0800 (PST) Received: from dyson.iquest.net ([198.70.144.127]) by freefall.freebsd.org (8.7.5/8.7.3) with ESMTP id JAA03883 for ; Sun, 27 Oct 1996 09:45:57 -0800 (PST) Received: (from root@localhost) by dyson.iquest.net (8.8.2/8.6.9) id MAA05900; Sun, 27 Oct 1996 12:45:42 -0500 (EST) From: "John S. Dyson" Message-Id: <199610271745.MAA05900@dyson.iquest.net> Subject: Re: LRU algorithms To: mark@quickweb.com (Mark Mayo) Date: Sun, 27 Oct 1996 12:45:41 -0500 (EST) Cc: hackers@FreeBSD.org In-Reply-To: from "Mark Mayo" at Oct 27, 96 11:33:40 am Reply-To: dyson@FreeBSD.org X-Mailer: ELM [version 2.4 PL24 ME8] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit 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. > 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