Operating System - Contiguous Allocation, Linked Allocation, and Indexed Allocation.

File Allocation Methods in Operating Systems

When a file is saved to a storage device, the operating system must determine where and how to place its data blocks on the disk. Allocation methods define this strategy, impacting performance, space utilization, and access time.

 1. Contiguous Allocation

In contiguous allocation, all blocks of a file are stored together in one continuous sequence on the disk.

Characteristics:

  • Requires the starting block number and the file length.

  • Easy to implement and efficient for sequential and direct access.

 Example:

A file of 4 blocks starting at block 10 will occupy blocks 10, 11, 12, 13.

 Advantages:

  • Fast access (especially for sequential files).

  • Simple to read and write.

 Disadvantages:

  • External fragmentation: Free space may be scattered.

  • Difficult to grow: File size must be known in advance or moved to a larger block.

 2. Linked Allocation 

In linked allocation, each file block contains a pointer to the next block. Blocks can be scattered anywhere on the disk.

 Characteristics:

  • Only the starting block address is needed to begin reading.

  • Best suited for sequential access.

Example:

Block 5 → Block 12 → Block 8 → Block 20 (linked through pointers).

Advantages:

  • No external fragmentation.

  • File can easily grow in size.

 Disadvantages:

  • Slower access (especially for random access).

  • Overhead of storing pointers in each block.

  • If a pointer is lost or corrupted, the file chain breaks.

 3. Indexed Allocation

In indexed allocation, each file has an index block (like a table) containing pointers to all the blocks of the file.

Characteristics:

  • The index block keeps track of all data block addresses.

  • Supports both sequential and random access efficiently.

Example:

Index block → [Block 3, Block 7, Block 9, Block 15]

 Advantages:

  • Fast random access.

  • No external fragmentation.

  • Easy to expand files (by updating index).

Disadvantages:

  • Requires extra space for the index block.

  • May need multi-level indexing for large files (can slow access).

Each allocation method has trade-offs. Operating systems choose based on the use case:

  • Contiguous: Good for small, fixed-size files (e.g., boot files).

  • Linked: Works well for sequential access (e.g., logs).

  • Indexed: Best for general-purpose file systems with random access needs.