File Allocation Methods

A hard disk is viewed by the operating system as a massive, 1-dimensional array of fixed-size disk blocks (usually 512 bytes or 4KB each). When you save a 20MB video file, the OS must find 5,000 free blocks on the disk to store it.

The main problem is how to allocate these blocks to files so that disk space is utilized effectively and files can be accessed quickly. There are three major methods of allocating disk space.

1. Contiguous Allocation

Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk.

• How it works: The directory entry for the file indicates the address of the starting block and the length of the area allocated for this file. If a file is 3 blocks long and starts at block 14, it occupies blocks 14, 15, and 16.
• Pros:
  • Blazing fast access. Because the blocks are physically next to each other on the spinning disk platter, the disk head only needs to move once.
  • Supports both sequential and direct (random) access efficiently.
• Cons:
  • External Fragmentation: Over time, as files are created and deleted, the disk becomes dotted with free holes of various sizes.
  • File Growth: If a file needs to grow (e.g., a log file), there might not be any free blocks immediately following it. The OS must copy the entire file to a new, larger hole.

2. Linked Allocation

Linked allocation solves all problems of contiguous allocation. With linked allocation, each file is a linked list of disk blocks; the disk blocks may be scattered anywhere on the disk.

• How it works: The directory contains a pointer to the first and last blocks of the file. Each block contains a pointer to the next block.
  • If a block is 512 bytes, a pointer might take up 4 bytes, leaving 508 bytes for data.
• Pros:
  • Zero external fragmentation. Any free block anywhere on the disk can be used.
  • Files can grow indefinitely.
• Cons:
  • No Direct Access: To read the 500th block of a file, the OS must start at the 1st block and traverse 499 pointers across the disk. This is incredibly slow.
  • Reliability: If a single pointer is corrupted by a bad sector, the entire remainder of the file is permanently lost.

FAT (File Allocation Table)

An important variation of linked allocation is the FAT file system (used by MS-DOS and older USB thumb drives). Instead of storing the pointers inside the data blocks, a massive table (the FAT) is stored at the beginning of the volume. The table contains one entry for each disk block, and functions identically to a linked list, but allows faster traversal because the table is cached in RAM.

3. Indexed Allocation

Indexed allocation solves the direct-access problem of linked allocation by bringing all the pointers together into one location: the Index Block.

• How it works: Each file has its own index block, which is an array of disk-block addresses. The $i$-th entry in the index block points to the $i$-th data block of the file.
• Pros:
  • Supports direct access. To read the 500th block, simply look up the 500th entry in the index block.
  • No external fragmentation.
• Cons:
  • Pointer Overhead: An entire index block must be allocated even for a tiny file that only needs 1 or 2 data blocks, wasting space.
  • Large Files: If a file is so massive that its array of pointers cannot fit inside a single Index Block, the OS must use advanced techniques like Multilevel Indexes (an index block that points to other index blocks). This is exactly how the ext4 file system in Linux is structured using inodes.