Hardware Reference
In-Depth Information
units 4, 52, and 19, entry 4 in the table would contain a 52, entry 52 would contain
a 19, and entry 19 would contain a special code (e.g., 0 or
1) to indicate end of
file. The file systems used by
MS-DOS
and Windows 95 and Windows 98 worked
this way. Newer versions of Windows (2000, XP, Vista, and 7) still support this
file system but also have their own native file systems that work more like
UNIX
.
Up until now we have discussed both consecutively and nonconsecutively allo-
cated files but have not specified why both kinds are used. Consecutively allocated
files have simpler block administration, but when the maximum file size is not
known in advance, it is rarely possible to use this technique. If a file is started at
sector
j
and allowed to grow into consecutive sectors, it may bump into another file
at sector
k
and have no room to expand. If the file is not allocated consecutively,
this situation presents no problem, because succeeding blocks can be put anywhere
on the disk. If a disk contains a number of growing files, none of whose final sizes
is known, storing each of them as a consecutive file will be nearly impossible.
Moving an existing file is sometimes possible but always expensive in terms of
time and system resources.
On the other hand, if the maximum size of all files is known in advance, as it is
when a CD-ROM is burned, the recording program can preallocate a run of sectors
exactly equal in length to each file. Thus if files with lengths of 1200, 700, 2000,
and 900 sectors are to be put on a CD-ROM, they can be simply begun at sectors 0,
1200, 1900, and 3900, respectively (ignoring the table of contents here). Finding
any part of any file is simple once the file's first sector is known.
In order to allocate space on the disk for a file, the operating system must keep
track of which blocks are available and which are already in use storing other files.
For a CD-ROM, the calculation is done once and for all in advance, but for a hard
disk, files come and go all the time. One method consists of maintaining a list of
all the holes, a hole being any number of contiguous allocation units. This list is
called the
free list
. Figure 6-22(a) illustrates the free list for the disk of
Fig. 6-21(b) with one sector per allocation unit.
An alternative method is to maintain a bit map, with 1 bit per allocation unit,
as shown in Fig. 6-22(b). A 1 bit indicates that the allocation unit is already occu-
pied and a 0 bit indicates that it is available.
The first method has the advantage of making it easy to find a hole of a partic-
ular length. However, it has the disadvantage of being variable sized. As files are
created and destroyed, the length of the list will fluctuate, an undesirable charac-
teristic. The bit table has the advantage of being constant in size. In addition,
changing the status of an allocation unit from available to occupied is just a matter
of changing 1 bit. However, finding a block of a given size is difficult. Both meth-
ods require that when any file on the disk is allocated or returned, the allocation list
or table be updated.
Before leaving the subject of file-system implementation, it is worth comment-
ing about the size of the allocation unit. Several factors play a key role here. First,
seek time and rotational delay dominate disk accesses. Having invested 5-10 msec
−
