Allocation Methods

The direct access nature of disks allows us to store many files on the same disk. The main problem now is to allocate space to these files so that disk space is effectively utilized, and files can be quickly accessed. 

Contiguous Allocation 

The contiguous allocation method requires each file to occupy a set of contiguous (adjoining) addresses on the disk. The contiguous allocation of a file is defined by the disk address of the first block and its length. 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 file .   

 Dynamic Storage Allocation 

Note: Disk space is thus a collection of free and used segments. Each segment is a contiguous set of disk blocks. An unallocated segment is called a hole. Disk space consists of allocated blocks and free holes. First-fit, best-fit and worst-fit are most common strategies to select a free hole from the set of available holes: 

1. First-fit: Allocates the first sufficiently large hole, starting from the beginning or the previous search endpoint.
2. Best-fit: Allocates the smallest sufficient hole, requiring a full list search unless sorted by size.
3. Worst-fit: Allocates the largest hole, also needing a full list search unless sorted by size.

First-fit and best-fit are more efficient than worst-fit but can cause external fragmentation as files are allocated and deleted. 

Compaction 

Note: To prevent disk space loss from external fragmentation, users run a repacking routine, copying and reallocating files to create one contiguous free space. A challenge with contiguous allocation is accurately estimating and allocating the required space for new files. 

Linked Allocation 

In linked allocation, each file is a linked list of disk blocks; the disk blocks may be scattered anywhere on the disc. The directory contains a pointer to the first and last block of the file. Linked allocation is shown in figure  

Indexed Allocation 

In indexed allocation, all pointers are stored in an index block, with each file having its own index block containing disk block addresses. This method supports access without external fragmentation. Systems may combine contiguous allocation for small files and indexed allocation for larger files, though indexed allocation is more complex.