Understanding File Allocation Schemes and Fragmentation

File allocation schemes determine how files are stored on disk. Different schemes have different advantages and disadvantages, particularly concerning how efficiently they use storage space and whether they lead to fragmentation.

Fragmentation is a phenomenon where storage space becomes unusable because it is divided into many small, disconnected blocks. There are two main types: internal fragmentation and external fragmentation.

Let's focus on external fragmentation as asked in the question. External fragmentation occurs when there is enough total free space on the disk to satisfy a request, but this free space is scattered in small, non-contiguous blocks, so it cannot be used to allocate a file that requires a single large contiguous block.

Analysis of File Allocation Schemes and External Fragmentation

A. Contiguous Allocation

In contiguous allocation, each file occupies a single, contiguous block of storage space on the disk. For example, if a file needs 10 blocks, it will be allocated blocks 50 through 59 contiguously.

• How it works: A file is stored as one continuous chunk of blocks. The directory entry for the file stores the starting block address and the length of the file.
• Fragmentation: Contiguous allocation suffers from external fragmentation. As files are created and deleted, holes of free space appear between allocated files. These holes might be too small to accommodate new files, even if the total free space is sufficient.

B. Indexed Allocation

In indexed allocation, each file has a dedicated index block. This index block contains pointers to all the disk blocks occupied by the file. The blocks pointed to by the index block do not need to be contiguous.

• How it works: A file's directory entry points to an index block. The index block contains addresses of the actual data blocks, which can be scattered anywhere on the disk.
• Fragmentation: Indexed allocation does not suffer from external fragmentation in the same way contiguous allocation does. While individual blocks might be small, the system can allocate any free block to a file as needed, as long as there are enough free blocks available. There is no requirement for the entire file to be in one contiguous space.

C. Linked Allocation

In linked allocation, each file is a linked list of disk blocks. Each block contains a pointer to the next block in the file. The blocks can be scattered anywhere on the disk.

• How it works: A file's directory entry stores the address of the first block. Each block of the file contains data and a pointer to the next block.
• Fragmentation: Linked allocation also does not suffer from external fragmentation. Like indexed allocation, it can use any free block available on the disk. Files are formed by linking arbitrary blocks, eliminating the need for contiguous space for the entire file.

Summary Table

Revision Table: Key Differences

Additional Information on File Allocation

While Indexed and Linked allocation avoid external fragmentation, they might introduce other issues. Linked allocation makes direct access (random access) to data blocks slow because you might have to traverse the links from the start of the file. Indexed allocation improves direct access by using the index block but introduces overhead for the index blocks themselves and potential limits on file size based on index block size. Contiguous allocation provides excellent read performance and direct access but is rigid and suffers from external fragmentation and difficulty with file growth.

Real-world file systems often use variations or combinations of these basic schemes to balance performance, flexibility, and space utilization.