main problem in file management is how to allocate space for files
so that disk space is utilized effectively and files can be accessed
quickly. Three major methods of allocating disk space are contiguous,
linked, and indexed. Each method has its advantages and disadvantages.
Accordingly, some systems support all three (e.g. Data General's
RDOS). More commonly, a system will use one particular method
for all files.
contiguous allocation method requires each file to occupy a set
of contiguous address on the disk. Disk addresses define a linear
ordering on the disk. Notice that, with this ordering, accessing
block b+1 after block b normally requires no head movement. When
head movement is needed (from the last sector of one cylinder
to the first sector of the next cylinder), it is only one track.
Thus, the number of disk seeks required for accessing contiguous
allocated files in minimal, as is seek time when a seek is finally
needed. Contiguous allocation of a file is defined by the disk
address and the length of the first block. If the file is n blocks
long, and starts at location b, then it occupies blocks b, b+1,
, b+n-1. The directory entry for each file indicates
the address of the starting block and the length of the area allocated
for this file.
difficulty with contiguous allocation is finding space for a new
file. If the file to be created is n blocks long, then the OS
must search for n free contiguous blocks. First-fit, best-fit,
and worst-fit strategies (as discussed in Chapter 4 on multiple
partition allocation) are the most common strategies used to select
a free hole from the set of available holes. Simulations have
shown that both first-fit and best-fit are better than worst-fit
in terms of both time storage utilization. Neither first-fit nor
best-fit is clearly best in terms of storage utilization, but
first-fit is generally faster.
algorithms also suffer from external fragmentation. As files are
allocated and deleted, the free disk space is broken into little
pieces. External fragmentation exists when enough total disk space
exists to satisfy a request, but this space not contiguous; storage
is fragmented into a large number of small holes.
problem with contiguous allocation is determining how much disk
space is needed for a file. When the file is created, the total
amount of space it will need must be known and allocated. How
does the creator (program or person) know the size of the file
to be created. In some cases, this determination may be fairly
simple (e.g. copying an existing file), but in general the size
of an output file may be difficult to estimate.
problems in contiguous allocation can be traced directly to the
requirement that the spaces be allocated contiguously and that
the files that need these spaces are of different sizes. These
requirements can be avoided by using linked allocation.
linked allocation, each file is a linked list of disk blocks.
The directory contains a pointer to the first and (optionally
the last) block of the file. For example, a file of 5 blocks which
starts at block 4, might continue at block 7, then block 16, block
10, and finally block 27. Each block contains a pointer to the
next block and the last block contains a NIL pointer. The value
-1 may be used for NIL to differentiate it from block 0.
linked allocation, each directory entry has a pointer to the first
disk block of the file. This pointer is initialized to nil (the
end-of-list pointer value) to signify an empty file. A write to
a file removes the first free block and writes to that block.
This new block is then linked to the end of the file. To read
a file, the pointers are just followed from block to block.
is no external fragmentation with linked allocation. Any free
block can be used to satisfy a request. Notice also that there
is no need to declare the size of a file when that file is created.
A file can continue to grow as long as there are free blocks.
allocation, does have disadvantages, however. The major problem
is that it is inefficient to support direct-access; it is effective
only for sequential-access files. To find the ith block of a file,
it must start at the beginning of that file and follow the pointers
until the ith block is reached. Note that each access to a pointer
requires a disk read.
Another severe problem is reliability. A bug in OS or disk hardware
failure might result in pointers being lost and damaged. The effect
of which could be picking up a wrong pointer and linking it to
a free block or into another file.
indexed allocation method is the solution to the problem of both
contiguous and linked allocation. This is done by bringing all
the pointers together into one location called the index block.
Of course, the index block will occupy some space and thus could
be considered as an overhead of the method.
indexed allocation, each file has its own index block, which is
an array of disk sector of addresses. The ith entry in the index
block points to the ith sector of the file. The directory contains
the address of the index block of a file. To read the ith sector
of the file, the pointer in the ith index block entry is read
to find the desired sector.
allocation supports direct access, without suffering from external
fragmentation. Any free block anywhere on the disk may satisfy
a request for more space.
: Free Space Management