Contiguous Allocation

• Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk (see Fig. 11.6).

  Figure 11.6: (a) Contiguous allocation of disk space for seven files. (b) The state of the disk after files D and F have been removed.

  
• Disk addresses define a linear ordering on the disk. 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), the head need only move from one track to the next.
  • Thus, the number of disk seeks required for accessing contiguously allocated files is minimal.
• Contiguous allocation of a file is defined by the disk address and length (in block units) 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, \ldots 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 (see Fig. 11.7).

  Figure 11.7: Contiguous allocation of disk space.

  
• Contiguous allocation is widely used on CD-ROMs. Here all the file sizes are known in advance and will never change during subsequent use of the CD-ROM file system.
• Accessing a file that has been allocated contiguously is easy.
  • For sequential access, the file system remembers the disk address of the last block referenced and, when necessary, reads the next block.
  • For direct access to block $i$ of a file that starts at block $b$, we can immediately access block $b + i$.
• Thus, both sequential and direct access can be supported by contiguous allocation.
• 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.
• Compacting all free space into one contiguous space, solves the fragmentation problem.
  • The cost of this compaction is time.
  • The time cost is particularly severe for large hard disks that use contiguous allocation, where compacting all the space may take hours and may be necessary on a weekly basis.
• Another problem with contiguous allocation is determining how much space is needed for a file.
• When the file is created, the total amount of space it will need must be found 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 (copying an existing file, for example); in general, however, the size of an output file may be difficult to estimate.
• If we allocate too little space to a file, we may find that the file cannot be extended.
• 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 overestimate 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.
• Even if the total amount of space needed for a file is known in advance, preallocation may be inefficient. The file therefore has a lager amount of internal fragmentation.