w_smith@wookie.DEC.COM.UUCP (03/08/87)
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_smithcoln@hpl-opus.UUCP (03/11/87)
Regarding CPM disk caching: I, too, have recently added disk caching to my BIOS code to improve effective hard disk performance, with good results. However, I cache on a disk record (128 byte) basis, reducing the granularity problem. Since the BDOS requests records in any case, this puts the cache logically between the BDOS and any blocking/deblocking/track-reading code that you might have in the physical disk driver. I have 180 kbytes of bank switched memory which is divided between the hash table (2048 words), the cached records themselves (128 bytes/record), and the table identifying the cached records (4 bytes/entry). Each cached record is identified by its drive designator, track, and sector (as seen by the BDOS). The cache is currently operating with "write through", so the disk is never out of sync. Preliminary profiling with a typical mix (for me) of editing, assembling, and file manipulation operations suggests that record writes are only 5%-10% of the total accesses. Reading a large file from the cache (assuming no cache misses but including all the operating system overhead for directory lookup) runs under 2 milliseconds per record. The hashed record lookup is crucial to achieve this speed. To reallocate cache space I use a simple "not recently used" algorithm, somewhat similar to what are called "clock" algorithms. Each record in the cache is assigned a flag bit, set whenever the record is accessed. Upon a cache miss, a reallocation pointer circulates through the cache entries, looking for an entry with the flag not set, and unsetting the flag of each entry it passes. Note that it is guaranteed to eventually find an unset flag. Records that are used often, will set their bit again, before they are dropped from the cache on the next circulation of the pointer. The code is (naturally?) written in Z-80 assembly, and is fairly clean, but has machine dependencies due to the memory bank switching. Please let me know if you desire further information, or can make suggestions. Mike Coln hplabs!coln coln@hplabs.HP.COM
barr@convex.UUCP (03/12/87)
Take a look at Maurice J. Bach's book "The Design of the UNIX Operating System." Look specifically at the section describing the chapter describing the algorithms and data structures used to implement the buffer cache. (I think it's in chapter 3.) The key idea is that the linked list structures automatically implement an LRU strategy which is a lot easier and faster than maintaining and checking reference history.