Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Knight, JW: AUTHOR [+2]
Disclosed is a method for extending file systems so as to support files of a type in which the system can automatically and incrementally reclaim space used by such files in a manner specified by but independent of application programs that access the files. Such files can be used by application programs to cache data, in which the data is not required for correct program execution but can improve performance when present.
a method for extending file systems so as to
support files of a type in which the system can automatically and
incrementally reclaim space used by such files in a manner specified
by but independent of application programs that access the files.
Such files can be used by application programs to cache data, in
which the data is not required for correct program execution but can
improve performance when present.
As an example
of the use of such a file type, consider a
workstation application program that makes use of data obtained from
a remote site. If communication with the remote site is slow (e.g.
current telephone lines) and/or expensive, then it is worthwhile to
cache remote data locally using a file in the local file system.
Checking whether local data is up to date with remote data can be
done quickly and cheaply using known techniques (e.g. by checking
date of last modification, version number, etc.).
examples of programs that can make use of data saved
between program invocations exist. For example, a data compression
program could save statistics or a string dictionary (depending on
the compression method) for certain types of files (e.g. programs in
a given language), and achieve much higher compression ratios,
especially for smaller files.
property of programs illustrated by the previous
examples is that it is worthwhile for performance reasons to cache
data during and between program invocation; however the program will
still operate correctly even if some or all of its cached data is
problems in designing such programs in the context of
current file systems. In general, the larger the file used for a
cache is allowed to grow, the more performance improvement will be
obtained; on the other hand if the file is too large there will not
be enough space left to run certain programs that otherwise would
have been able to run successfully. Currently these problems are
dealt with by techniques such as specifying a maximum size for such a
file, or by the user erasing such files when more space is needed and
then retrying a program that failed due to lack of file system space.
In order to
describe cache-type files, which solve these
problems, assume a "flat file" model, where a file is a linear space
of bytes, with "holes" in those spaces that have never been written.
However, for random access to files, assume that there is a
block-oriented file system interface, as follows, where FToken is a
token for a file previously opened, and BlkNum is the block number of
a block to be read or written ("*" indicates call by reference).
FWrite(FToken, BlkNum, adr, *rc): write out one block
of data starting from address adr. The result is
returned in rc which (for example) if positive is the
number of bytes written, and otherwise specifies a