Fast Seek Technique
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Chen, FP: AUTHOR [+3]
This article describes a technique for use in a computer system which locates file cluster information using a file extent map that is dynamically created in main memory from cluster chains on disk, thereby reducing the number of disk seeks and access to the disk space map.
Fast Seek Technique
describes a technique for use in a computer
system which locates file cluster information using a file extent map
that is dynamically created in main memory from cluster chains on
disk, thereby reducing the number of disk seeks and access to the
disk space map.
The fast seek
technique disclosed herein creates an extent map
in the main memory by recording disk space information of the file
extents. An extent is a block of contiguous disk clusters of a file.
A cluster is a basic disk allocation unit and a file can be
comprised of one or more extents. The file extent information is not
pre-recorded in the extent map. Instead the extents are discovered
in "real time" and recorded in the extent map. Extents in the extent
map can grow dynamically as new portions of them are discovered or
added through file expansion.
disk space information of a file is not cached in
the file extent map. On the disk space information of the file that
has been accessed by the application is mapped. The access to the
extent information in the extent map does not have to return the
exact information of the extent. It can return the closest
information so far recorded in the extent map if complete information
is not available.
map allows a denser recording of the disk space map
than keeping the entire disk space map. It keeps only the disk space
information of extents accessed by the application. Also, the disk
space information of multiple clusters in a single extent is recorded
in the same extent entry. Extent maps of closed files are not
discarded. Instead, they are preserved in a separate list for later
use if the files are reopened. Extent caching does not stop if the
main memory cache buffer is full. Instead, the buffer is recycled by
discarding the least recently used extents of the least recently
Fig. 1 shows
the structure of the extent map. Cluster
information of recently opened files in extent maps is stored in a
main memory cache. This cache is managed based on least recently
used (LRU) and most recently used (MRU) extent maps with the MRU
extent map at the top of queue for rapid access. If the cache buffer
is full, the LRU extent from the LRU file extent map will be released
to make space for new extents.
map of each file may not contain the complete disk
space information of the file. The map contains only the disk space
information of the file extent accessed by the application. The
extent map will grow as more and more extents are found during file
access by the application.
The user can
also specify the size of the cache buffer used by
the extent maps. Once it is installed, disk operating system (DOS)
kernel can call fast seek functions. When an application accesses a
file, DOS kernel passes the file cluster information on the disk to