File Allocation Methods

Introduction

When you save a file to disk, the file system must decide WHERE on the physical disk to place the file's data blocks. This decision — file allocation — significantly impacts performance (how fast files are read/written), space utilization (how much disk space is wasted), and flexibility (how easily files can grow or shrink).

Three major allocation methods exist, each with distinct tradeoffs. Modern file systems often combine ideas from multiple methods for optimal performance.

Method 1: Contiguous Allocation

Each file occupies a set of contiguous (adjacent) blocks on disk. The directory entry stores the starting block and the file length.

Advantages:

• Excellent sequential AND random access performance (read ahead, calculate any block position instantly)
• Simple directory entry (just start + length)
• Minimal seek time (blocks are adjacent)

Disadvantages:

• External fragmentation (free space becomes scattered holes)
• File size must be known at creation time (cannot easily grow)
• Compaction needed periodically (expensive)

Used in: CD-ROMs/DVDs (write-once media), some embedded systems

Method 2: Linked Allocation

Each file is a linked list of disk blocks. Each block contains data AND a pointer to the next block. Blocks can be scattered anywhere on disk.

Advantages:

• No external fragmentation (any free block works)
• Files can grow easily (just link a new block)
• No need to know file size in advance

Disadvantages:

• Poor random access (must follow links from beginning to find block N)
• Space overhead (each block uses some bytes for the pointer)
• Reliability issue: if one pointer is corrupted, rest of file is lost

FAT (File Allocation Table)

A major improvement on linked allocation. Instead of storing pointers in each data block, ALL pointers are collected into a separate table in a fixed location on disk.

The FAT is cached in memory, making random access possible without reading individual blocks. FAT12, FAT16, and FAT32 use this approach.

Method 3: Indexed Allocation

Each file has an index block (like a table of contents) that contains pointers to ALL of the file's data blocks. Random access is fast — look up block N directly in the index.

Advantages:

• Direct random access (index gives location of any block)
• No external fragmentation
• Files grow easily (add entry to index)

Disadvantages:

• Index block overhead (wastes space for small files)
• Index block size limits file size (what if file needs more entries than one block holds?)

Multi-Level Index (Unix inode)

Unix/Linux uses a hybrid multi-level index scheme to handle files of any size efficiently:

Small files (< 48KB with 4KB blocks) use only direct pointers — no overhead. Large files use indirect pointers as needed.

Comparison

Real-World Analogy

Contiguous allocation is like reserving consecutive seats at a concert — great if you know your group size in advance, problematic if it changes. Linked allocation is like a treasure hunt — each clue leads to the next location. Indexed allocation is like a restaurant seating chart — the host has a map showing where every table (block) is, so anyone can be found immediately.

Key Takeaways

• Contiguous: best performance but suffers from external fragmentation and inflexibility
• Linked: eliminates fragmentation but has poor random access; FAT improves this
• Indexed: good random access with manageable overhead; inode multi-level indexing handles all file sizes
• Modern file systems (ext4, NTFS) use extent-based approaches (hybrid of contiguous + indexed)
• The choice impacts read/write performance, space efficiency, and reliability