Date   : Wed, 11 Mar 1987 02:43:48 GMT
From   : hpcea!hpspdla!hpl-opus!coln@hplabs.hp.com (Mike Coln)
Subject: Re: Help on caching algorythm?

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