File Allocation
Methods
There are three major methods of storing files on disks: contiguous, linked,
and indexed.
1. Contiguous Allocation
Contiguous Allocation requires that all
blocks of a file be kept together contiguously. Performance is very fast,
because reading successive blocks of the same file generally requires no
movement of the disk heads, or at most one small step to the next adjacent
cylinder.
Problems can arise when files grow, or if the exact size of a file is
unknown at creation time:
o
Over-estimation of the file's
final size increases external fragmentation and wastes disk space.
o
Under-estimation may require that
a file be moved or a process aborted if the file grows beyond its originally
allocated space.
o
If a file grows slowly over a
long time period and the total final space must be allocated initially, then a
lot of space becomes unusable before the file fills the space.
A variation is to allocate file
space in large contiguous chunks, called extents. When a file
outgrows its original extent, then an additional one is allocated. ( For
example an extent may be the size of a complete track or even cylinder, aligned
on an appropriate track or cylinder boundary. ) The high-performance files
system Veritas uses extents to optimize performance.
2. Linked Allocation
·
Disk files can be stored as
linked lists, with the expense of the storage space consumed by each link. (
E.g. a block may be 508 bytes instead of 512. )
·
Linked allocation involves no
external fragmentation, does not require pre-known file sizes, and allows files
to grow dynamically at any time.
·
Unfortunately linked allocation
is only efficient for sequential access files, as random access requires
starting at the beginning of the list for each new location access.
·
Allocating clusters of
blocks reduces the space wasted by pointers, at the cost of internal
fragmentation.
·
Another big problem with linked
allocation is reliability if a pointer is lost or damaged. Doubly linked lists
provide some protection, at the cost of additional overhead and wasted space.
·
The File Allocation
Table, FAT, used by DOS is a variation of linked allocation, where all
the links are stored in a separate table at the beginning of the disk. The
benefit of this approach is that the FAT table can be cached in memory, greatly
improving random access speeds.
3. Indexed Allocation
Indexed Allocation combines all of the
indexes for accessing each file into a common block ( for that file ), as
opposed to spreading them all over the disk or storing them in a FAT table.
Some disk space is wasted ( relative to linked lists or FAT tables )
because an entire index block must be allocated for each file, regardless of
how many data blocks the file contains.
Performance
·
The optimal allocation method is
different for sequential access files than for random access files, and is also
different for small files than for large files.
·
Some systems support more than
one allocation method, which may require specifying how the file is to be used
( sequential or random access ) at the time it is allocated. Such systems
also provide conversion utilities.
·
Some systems have been known to
use contiguous access for small files, and automatically switch to an indexed
scheme when file sizes surpass a certain threshold.
·
And some systems adjust their
allocation schemes ( e.g. block sizes ) to best match the characteristics of
the hardware for optimum performance.
No comments:
Post a Comment