7.2Allocation: contiguous, linked, FAT and indexed
The idea
Allocation methods decide how a file's blocks are placed on disk: contiguous, linked, FAT or indexed.
Think of it like this: Contiguous: a book on one shelf. Linked: pages scattered, each saying where the next is. Indexed: a contents page listing where every page is.
Why it exists
Each method trades fragmentation, speed of random access and robustness.
How it works
- Contiguous: start and length; fast but external fragmentation.
- Linked: each block points to the next; slow random access.
- FAT: all the next-pointers kept in one table in memory.
- Indexed: an index block lists all data blocks; supports direct access.
Worked example: 64 GB disk, 4 KB blocks, 4-byte FAT entries
16 777 216 blocks (2²⁴), so the FAT is 2²⁴ × 4 B = 64 MB. Each entry needs at least 24 bits.
Now play with it
- →Use the FAT calculator for your own disk.
- →Read which method supports fast direct access.
| Method | Sequential | Direct access | External fragmentation | Weak point |
|---|---|---|---|---|
| Contiguous | fast | fast | yes | growing a file, compaction |
| Linked | fine | slow (follow the chain) | no | one lost pointer loses the rest; pointer space |
| FAT (linked table) | fine | good (table in memory) | no | table must fit in memory |
| Indexed | fine | fast | no | index block overhead for tiny files |
The entry must be wide enough to name any block: ⌈log₂ (blocks)⌉ bits, usually rounded up to whole bytes.
Check yourself
Which method has no external fragmentation and poor direct access?
Exam notes (the dense version)
Contiguous: a start block and a length; fast sequential and direct access, but external fragmentation and growth is hard. Linked: each block holds a pointer to the next; no fragmentation but direct access means following the chain, and a pointer lost means the rest lost. FAT: the pointers are kept in a table in memory (one entry per block), which makes random access fast. Indexed: an index block lists the file's blocks; supports direct access; large files need multi-level indexes. FAT size = number of blocks × entry size.
Previous year questions: File Systems (5)
PYQs are grouped by topic, so this is the full set for File Systems; try the ones that match this subtopic. Open all 5 on the topic page.