Contiguous, Linked and Indexed Allocation

Introduction

File allocation methods solve one core problem: how a file’s logical blocks map to physical disk blocks. A file may be viewed as L0, L1, L2, and so on, but the disk stores data in real block numbers.

Contiguous, linked, and indexed allocation answer this mapping problem differently. Each method has its own effect on access speed, file growth, fragmentation, and storage overhead.

Core Mapping Problem

For every logical block of a file, the operating system needs to determine where that block is actually stored on the disk. For example, if the application asks for logical block L6, the file system must know where L6 is stored physically.

The file allocation method provides this mapping, connecting each logical file block to its corresponding physical disk block. The lookup rule depends on whether the file uses contiguous, linked, or indexed allocation.

Contiguous Allocation

In contiguous allocation, all blocks of a file are stored in consecutive disk blocks. For example, if the file starts at disk block 100, its logical blocks are placed sequentially: L0 => 100, L1 => 101, L2 => 102, and L3 => 103.

This makes lookup very simple. If the starting block is known, the physical block can be calculated directly using the formula: physical block = start block + logical block number

For example, if the file starts at block 100 and the required logical block is L6, then: physical block = 100 + 6 = 106

Contiguous allocation is fast for both sequential and random access. Its main weakness is that it needs a continuous free space, so it can suffer from external fragmentation and difficult file growth.

Linked Allocation

In linked allocation, file blocks can be placed anywhere on disk. Each block stores a pointer to the next block in the file. For example: 40 => 7 => 91 => 12 => null

The file does not need consecutive storage. To read it sequentially, the OS follows the pointer chain from one block to the next.

This method avoids external fragmentation because scattered free blocks can be used. It also makes file growth easier because a new block can be added anywhere and linked to the chain.

The weakness is random access. To reach logical block L6, the OS cannot directly calculate the answer; it must follow pointers from the beginning until it reaches the required block. Each block also loses some usable space because it stores a pointer.

Indexed Allocation

In indexed allocation, a separate index block stores the disk block addresses of all the file's data blocks. This index acts as a table that connects each logical file block to its corresponding physical disk block.

For example, if index[0] = 40, index[1] = 7, index[2] = 91, and index[3] = 12, then to access logical block L3, the OS looks up index[3] and directly finds it at disk block 12.

Indexed allocation supports good random access because the logical block number can be used as an index entry. It also avoids external fragmentation because file data blocks can be scattered.

Its tradeoff is metadata overhead. The index block consumes extra storage, and very large files may need larger or multi-level indexing.

Block Lookup Comparison

This is the key difference for numericals and theory. Contiguous allocation calculates, linked allocation walks a chain, and indexed allocation checks an index.

Compact Block Usage Example

Suppose:

• Block size: 1 KB = 1024 bytes

• Pointer size: 4 bytes

• File size: 10 KB = 10240 bytes

• Indexed allocation: One index block is enough

For contiguous allocation, each block stores file data only: 10240 / 1024 = 10 data blocks

For linked allocation, each block stores a 4-byte pointer, so usable data per block is: 1024 - 4 = 1020 bytes, thus the file needs: ceil(10240 / 1020) = 11 blocks

For indexed allocation, file data still needs 10 data blocks, plus 1 index block: 10 + 1 = 11 blocks

So in this example, contiguous allocation uses 10 blocks, linked allocation uses 11 blocks because of pointer space, and indexed allocation uses 11 blocks because of the index block.

Final Comparison

The best method depends on what matters more: speed, flexibility, space overhead, or file growth.

Summary

Contiguous, linked, and indexed allocation are three ways to map logical file blocks to physical disk blocks. Contiguous allocation uses direct calculation, linked allocation follows a pointer chain, and indexed allocation uses an index block.

Contiguous allocation is fast but needs continuous space. Linked allocation is flexible but weak for random access. Indexed allocation gives direct lookup with flexible placement, but it adds index-block overhead.