29. File Allocation Methods

The OS must decide which disk blocks belong to a file and how to track them.

1. Contiguous Allocation — all blocks stored side by side; the inode just stores start + length. Fast sequential and random access, but external fragmentation and hard to grow a file. Used on CD-ROMs/DVDs.

2. Linked Allocation — each block holds data + a pointer to the next block, like a linked list. No external fragmentation, easy to grow, but sequential-only access and pointer overhead (a broken pointer loses the rest of the file). FAT improves this by moving pointers into a separate in-memory table.

3. Indexed Allocation — a dedicated index block holds all pointers to a file's data blocks. Fast random access, no external fragmentation, but wastes space on tiny files. Multi-level indexing (direct → single → double → triple indirect) is exactly what ext4 uses.

Contiguous Linked Indexed
Random access	Fast	Slow	Fast
Sequential access	Fast	OK	Fast
External fragmentation	Yes	No	No
File growth	Hard	Easy	Easy
Used in	CD-ROMs, DVDs	FAT (Windows)	ext4, UNIX

---