Page 231 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes allocation. Contiguous allocation has some problems, however. One diffculty is finding space
for a new file. Any management system can be used, but some are slower than others. First
and best fit 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 more efficient than worst fit in
terms of both time and storage utilization. Neither first fit nor best fit is clearly best in terms of
storage utilization, but first fit is generally faster. All these algorithms suffer from the problem
of external fragmentation. As files are allocated and deleted, the free disk space is broken into
little pieces. External fragmentation exists whenever free space is broken into chunks. It becomes
a problem when the largest contiguous chunk is insufficient for a request; storage is fragmented
into a number of holes, no one of which is large enough to store the data. Depending on the
total amount of disk storage and the average file size, external fragmentation may be a minor
or a major problem. Some older PC systems used contiguous allocation on floppy disks.

Two possibilities then exist. First, the user program can be terminated, with an appropriate error
message. The user must then allocate more space and run the program again. These repeated
runs may be costly. To prevent them, the user will normally over estimate the amount of space
needed, resulting in considerable wasted space. The other possibility is to find a larger hole,
copy the contents of the file to the new space, and release the previous space. This series of
actions can be repeated as long as space exists, although it can be time consuming. However, the
user need never be informed explicitly about what is happening; the system continues despite
the problem, although more and more slowly. Even if the total amount of space needed for a
file is known in advance, preallocation may be inefficient. A file that will grow slowly over a
long period (months or years) must be allocated enough space for its final size, even though
much of that space will be unused for a long time. The file therefore has a large amount of
internal fragmentation. To minimize these drawbacks, some operating systems use a modified
contiguous-allocation scheme. Here, a contiguous chunk of space is allocated initially; and
then, if that amount proves not to be large enough, another chunk of contiguous space, known
as an extent, is added. The location of a file’s blocks is then recorded as a location and a block
count, plus a link to the first block of the next extent. On some systems, the owner of the file
can set the extent size, but this setting results in efficiencies if the owner is incorrect. Internal
fragmentation can still be a problem if the extents are too large, and external fragmentation can
become a problem as extents of varying sizes are allocated and deallocated. The commercial
Veritas file system uses extents to optimize performance. It is a high-performance replacement
for the standard UNIX UFS.

Figure 6.8: Linked Allocation of Disk Space

Directory
File Start End
jeep 9 25
0 1 1 2 3
4 5 6 7
8 9 1 10 2 11
1 2 13 14 15
16 17 18 19
2 0 21 22 23
24 25 –1 26 27

2 8 29 30 31

224 LOVELY PROFESSIONAL UNIVERSITY