Page 158 - DCAP403_Operating System

Unit 8: File Management

space are contiguous, linked, and indexed. Each method has its advantages and disadvantages. Notes
Accordingly, some systems support all three (e.g. Data General’s RDOS). More commonly, a
system will use one particular method for all fi les.

8.9.1 Contiguous Allocation

The 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 fi rst sector of the next cylinder), it is only one track.
Thus, the number of disk seeks required for accessing contiguous allocated fi les 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+2, …, 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 fi le.

The 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-fi t, best-fit, and worst-fi t

strategies are the most common strategies used to select a free hole from the set of available holes.
Simulations have shown that both fi rst-fi t and best-fi t are better than worst-fi t in terms of both
time storage utilization. Neither fi rst-fit nor best-fit is clearly best in terms of storage utilization,

but fi rst-fit is generally faster.

These 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.
Another 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.

Figure 8.6: Diagram of Contiguous Allocation
directory
File A File Name Start Block Length
0 1 2 3 4 File A 2 3
File B 9 5
5 6 7 8 9 File C 18 8
File B File D 30 2
File E 26 3
10 11 12 13 14
15 16 17 18 19
15
16
17
18
19
File C
20 21 22 23 24
File E Since blocks are allocated
25 26 27 28 29 contiguously, external
fragmentation may occur.
File D Thus, compaction may be
30 31 32 33 34 needed.

LOVELY PROFESSIONAL UNIVERSITY 151