Introduction
Once a file system decides to store a file, it must choose how to allocate disk blocks to hold that file's data. The allocation method determines how efficiently the disk is used, how fast files can be read sequentially or randomly, and how easily a file can grow. The three classic allocation strategies are contiguous allocation, linked allocation, and indexed allocation, each with distinct trade-offs.
Cricket analogy: How a groundstaff stores match footage -- as one continuous unbroken reel, as scattered clips linked by handwritten notes, or as an indexed catalog pointing to each over -- determines how fast a commentator can jump to any specific over later.
Explanation
Contiguous allocation stores each file as a single run of consecutive disk blocks. The directory entry only needs to record the starting block and length. This gives excellent sequential and random-access performance because block N of the file is simply (start + N). Its major weakness is external fragmentation: as files are created and deleted, free space becomes broken into scattered small holes, and a large file may fail to find one big enough contiguous run even though total free space is sufficient; periodic compaction is needed. Linked allocation stores each file as a linked list of disk blocks scattered anywhere on disk; each block holds a pointer to the next block, and the directory entry stores the first (and sometimes last) block. This eliminates external fragmentation and allows files to grow easily, but it has no efficient random access -- to reach block N you must traverse N pointers from the start, and reliability suffers because a single corrupted pointer breaks the chain (FAT file systems solve this by keeping the pointer chain in a separate File Allocation Table rather than embedded in each block). Indexed allocation gives every file an index block containing pointers to all of that file's data blocks. This supports direct/random access (look up entry N in the index block) without external fragmentation, but it introduces overhead: the index block itself consumes space, and for very large files a single index block may not hold enough pointers, requiring multi-level or linked index blocks, adding an extra layer of indirection.
Cricket analogy: Booking one continuous block of stadium seats (contiguous) is easy to find but fails when only scattered single seats remain after other bookings (external fragmentation); a scattered group linked by "next seat is with usher X" (linked) has no such problem but finding seat 50 means asking 50 ushers in sequence; a seating chart with a master index listing every seat's location directly (indexed) gives instant lookup at the cost of maintaining that chart.
Example
/* Conceptual model of indexed allocation: an index block
holding pointers to a file's data blocks (like a simplified
Unix inode with direct block pointers). */
#define NUM_DIRECT_BLOCKS 12
#define BLOCK_SIZE_BYTES 4096
typedef struct {
int size_bytes;
int direct_blocks[NUM_DIRECT_BLOCKS]; /* physical block numbers */
int single_indirect_block; /* pointer to a block of pointers */
} inode_t;
/* Translate a logical byte offset within the file to the
physical block number, mimicking what the OS does when a
read() call needs to fetch data at a given offset. */
int logical_to_physical_block(inode_t *node, int byte_offset) {
int logical_block = byte_offset / BLOCK_SIZE_BYTES;
if (logical_block < NUM_DIRECT_BLOCKS) {
return node->direct_blocks[logical_block];
}
/* Beyond direct blocks: would follow single_indirect_block
to a table of further pointers -- one extra disk read. */
return -1; /* simplified: indicates "look in indirect block" */
}Analysis
The example shows indexed allocation's core idea: the inode stores direct pointers for the first 12 blocks, giving O(1) random access for small files. For offsets beyond the direct blocks, the OS must first read the single_indirect_block to obtain further pointers -- an extra disk I/O compared to contiguous allocation's simple arithmetic, but still far better than linked allocation's O(N) pointer chasing. This is exactly the tradeoff table to remember: contiguous is fastest but suffers external fragmentation; linked has no external fragmentation but no efficient random access; indexed supports random access and avoids external fragmentation at the cost of extra indirection and index-block space overhead.
Cricket analogy: A scorer's quick-reference card lists the first 12 overs' outcomes directly for instant recall; for overs beyond 12, they must first flip to a supplementary log sheet to find the reference, an extra lookup step -- slower than instant recall but still far faster than reading the entire ball-by-ball commentary from over 1.
Key Takeaways
- Contiguous allocation: fast sequential/random access via start+offset, but suffers external fragmentation and requires compaction.
- Linked allocation: no external fragmentation, easy growth, but no random access (must traverse pointers) and is vulnerable to broken links.
- FAT-style allocation moves the linked-list pointers into a separate table, improving reliability over embedding pointers in data blocks.
- Indexed allocation: supports random access via an index block, avoids external fragmentation, but adds indirection overhead and needs multi-level indexes for large files.
- Choice of allocation method is a core tradeoff between access speed, space efficiency, and file growth flexibility.
Practice what you learned
1. Which allocation method is most susceptible to external fragmentation?
2. What is the main drawback of linked allocation compared to indexed allocation?
3. In indexed allocation, what is the purpose of a single indirect block?
4. How does the FAT file system improve on the reliability weakness of basic linked allocation?
Was this page helpful?
You May Also Like
File System Basics
How an operating system organizes, names, and provides access to persistent data on secondary storage.
Directory Structures
How file systems organize files into single-level, two-level, tree, and acyclic-graph directory hierarchies.
Contiguous Memory Allocation
Allocating each process a single unbroken block of physical memory, and the fragmentation problems that follow.