The allocation method defines how the operating system assigns physical disk blocks to store the contents of files. This choice profoundly impacts disk space utilization, the speed of file access (sequential vs. random), and the ability of files to grow.

Contiguous Allocation

● Concept: Each file is allocated a single, unbroken (contiguous) set of disk blocks. All the blocks belonging to a file are physically adjacent on the disk.
● Metadata Tracking: The directory entry (or File Control Block) for a file using contiguous allocation stores two key pieces of information:
- Starting Block Address: The physical block number where the file begins.
- Length: The number of blocks the file occupies.

● Operations:
- Read/Write Sequential: To read a file sequentially, the system simply starts at the starting block and reads length number of blocks consecutively.
- Read/Write Random (Direct Access): To access a specific logical block i within the file, the physical block address is calculated as Starting_Block_Address + i.
- File Creation: The system must search the free space for a contiguous block of disk space that is large enough to hold the entire file.

● Advantages:
- Simplicity: The allocation scheme is conceptually very simple to implement and manage.
- Excellent Performance for Sequential Access: Because all blocks are physically adjacent, disk head seeks are minimal, leading to very high data transfer rates.
- Efficient Random Access: Direct calculation of any block's physical address allows for fast random access within the file.

● Disadvantages:
- External Fragmentation (Major Problem): As files are created and deleted, the disk may become fragmented with unusable holes of free space.
- File Size Growth Issues: If a file grows and there is no adjacent free space, the whole file may need to be copied elsewhere.
- Requires Prior Knowledge of File Size: This leads to either wasting space or the need to frequently resize files.

Linked Allocation

● Concept: Each file is represented as a linked list of disk blocks. The blocks belonging to a file can be scattered randomly anywhere on the disk. The order of blocks is maintained by pointers within the blocks themselves.
● Metadata Tracking: The directory entry (or File Control Block) for a file using linked allocation stores:
- Starting Block Address: The physical block number of the first block in the file.
- Ending Block Address: The physical block number of the last block in the file (to facilitate easy appending).

● Mechanism:
- Each data block contains a pointer (address) to the next block in the file.
- Read Sequential: To read a file, the system starts at the starting block, reads its content, then follows the pointer to the next block, and so on.
- Write (Appending): To append to a file, a new free block is allocated, its address is added to the pointer field of the current last block, and the ending block address in the directory entry is updated.

● Advantages:
- No External Fragmentation: Files can use any available block on the disk, regardless of its location.
- Easy File Growth: Files can grow dynamically by simply allocating new free blocks from anywhere on the disk.

● Disadvantages:
- Poor Performance for Random Access: To access a specific logical block i within a file, the system must traverse the linked list from the beginning.
- Significant Disk Head Movement: Since blocks are typically scattered across the disk, sequential access involves numerous disk head seeks.
- Reliability Issues: If a pointer becomes corrupted, the remainder of the file from that point becomes inaccessible.

Indexed Allocation

● Concept: All the pointers to a file's data blocks are collected together in a single, dedicated block called the index block. Each file has its own unique index block.
● Metadata Tracking: The directory entry (or File Control Block/inode) for a file using indexed allocation stores only one piece of information: the address of its index block.

● Mechanism:
- When a file is created, an empty index block is allocated and its address is stored in the directory entry.
- When data is written to a file, free data blocks are allocated, and their physical addresses are placed into entries within the file's index block.
- Read/Write Random (Direct Access): To access a specific logical block i within a file:
- The system first reads the index block from disk.
- Once the index block is in memory, it contains an array of pointers. The system retrieves the i-th pointer from this array.
- This i-th pointer gives the physical address of the desired data block, which is then accessed directly. This typically involves two disk reads (one for the index block, one for the data block).

● Advantages:
- No External Fragmentation: Like linked allocation, blocks can be scattered anywhere on the disk.
- Efficient Random Access: Reaches direct addressing of any data block by its logical block number.
- Handles File Growth: Files can grow dynamically by adding new block addresses to the index block.

● Disadvantages:
- Space Overhead for Index Blocks: Even small files require at least one full index block, leading to waste.
- Limited File Size (for single index block): Files can only be as large as the number of pointers in the index block.
- Multi-level Indexing to handle large files, which requires more reads.

● Multi-level Indexing (Hierarchical Indexing): To overcome the limitations of file size through indexed allocation, we use multi-level indexing where pointers in the index block point to other index blocks (single, double, triple).

● Combined Scheme (e.g., Unix Inodes): Many file systems employ a combined approach within their inode structure to optimize file organization, featuring direct pointers and indirect pointers to cater for various file sizes.