Date   : Sat, 07 Mar 1987 1800:00
From   : w_smith%wookie.DEC@decwrl.DEC.COM (Willie Smith, LTN Components Eng.)
Subject: Help on caching algorythm?

     I'm rebuilding my BIOS to (among other things) change my 
hard disk track buffers over to caching.  I've gotten almost the 
whole thing written, but I have one algorythm I need some help 
on.  I have 4 (will be 8) buffers in another bank of memory, 
which each holds an 8 K logical track.  Each access to a buffer 
increments a counter, so I know how often (since last warm boot) 
a buffer has been used.  I've done the easy part, finding a 
buffer (if I have a cache 'hit') or allocating an unused buffer, 
now I'm looking for an algorythm to deallocate a buffer when I 
don't have a 'hit' and there aren't any free.  I have a few 
ideas, but there are problems with each:
     LRU: Least Recently Used.  I think the algorythm goes 
something like "when you use a buffer, move it's number to the 
top of a block of memory, shuffle others down to make room, and 
if you need a buffer, use the one whose number is at the bottom 
of the list."  The problems are maintaining the data structure 
without reams of code, and the fact that a buffer with a high use 
count can be deallocated by merely reading 4 (8) different tracks 
before you get back to the first one.  Thus you could lose your 
directory track fairly rapidly, and I know I'm going to need that 
frequently.
     Smallest count.  Look for the buffer that got used the 
least, and use that.  Looks good as an idea, but there is a major 
coding problem.  Given a table of 4 (8) numbers, how do you find 
the smallest? [I'm coding in Z-80 assembly, so MIN(x,y,z) doesn't 
help :+)  ].  If you start scanning from the beginning, you will 
tend to deallocate number 0 more than number 3.  If you don't 
start at the beginning, the coding gets messy.  If there are 2 
numbers that are a minimum, which one do you pick?  I though of a 
way that would work, "start with one, look for it in the table, 
if not found, look for two, if not found, look for 3, etc, etc, 
etc".  I'm using byte counters, so I'd only have to go up to 255, 
but this is kind of a hack, any better ideas?
     Are there any other, more popular, more useful, simpler, or 
more elegancache algorythms that anyone knows about?
 
Willie Smith
w_smith@wookie.dec.com
w_smith%wookie.dec.com@decwrl.dec.com [decwrl.arpa?]
 
Usenet:        the_known_universe!decwrl!wookie.dec.com!w_smith
BIX:   w_smith