File Allocation Methods

Introduction

File allocation is the mechanism that connects a file’s logical view to real storage blocks on disk. A file may look like a continuous byte stream to users and applications, but storage is divided into blocks.

The file system must remember which disk blocks belong to each file. Different allocation methods solve this mapping problem in different ways.

Why File Allocation Is Needed

A file can be thought of as a sequence of logical blocks such as L0, L1, L2, L3, and so on. These logical blocks must be mapped to the actual physical blocks on the disk where the file's data is stored. File allocation determines this mapping: logical file block => actual disk block.

For example, the file system must know where L0, L1, and L2 are stored on disk. This mapping is necessary for reading, writing, growing, and managing files.

Main File Allocation Methods

The three main file allocation methods are:

Each method makes a different tradeoff between speed, flexibility, fragmentation, and metadata overhead.

Contiguous Allocation

In contiguous allocation, all blocks belonging to a file are stored in consecutive disk blocks. For example, if L0 is stored at disk block 40, the following blocks are placed immediately after it: L1 => 41, L2 => 42, and L3 => 43.

If the starting block is 40, the next logical blocks occupy the next disk blocks. This makes sequential access fast because the file blocks are physically adjacent.

Random access is also simple. If the file starts at block 40 and the OS wants logical block 3, it can calculate:

physical block = start block + logical block number = 40 + 3 = 43

The main weakness is external fragmentation. Free space may exist on disk, but not as one continuous area large enough for the file. File growth is also difficult if the blocks after the file are already occupied.

Linked Allocation

In linked allocation, the blocks of a file can be stored anywhere on the disk rather than next to each other. Each block contains a pointer to the next block in the file, forming a chain. For example: 40 => 7 => 91 => 12 => null

This means the first block is at disk block 40, the next one is at 7, then 91, then 12.

Linked allocation is flexible because the file does not need one continuous free area. A file can grow by adding another free block to the chain.

Its main weakness is random access. To reach logical block k, the OS may need to follow the chain from the beginning. There is also pointer overhead, and if a pointer is damaged, the rest of the chain can become hard to reach.

Indexed Allocation

In indexed allocation, a separate index block stores the disk addresses of all the file's data blocks. For example, if index[3] = 12, the OS can access logical block 3 by looking up index[3] and directly finding it at disk block 12. This allows direct access to any file block without following a chain of pointers.

This gives better random access than linked allocation because the OS does not need to walk through a chain. The tradeoff is metadata overhead: the index block itself takes space and must be maintained.

Indexed allocation is especially useful when direct access to different parts of a file is important.

Summary

File allocation methods map logical file blocks to actual disk blocks. This mapping lets the operating system locate file data even when the file is stored using different layouts.

Contiguous allocation stores blocks together, linked allocation connects scattered blocks through pointers, and indexed allocation stores block addresses in an index block. Each method balances access speed, file growth, fragmentation, and metadata overhead differently.