What are File Allocation Methods in an OS?
Contiguous, linked, and indexed file allocation compared — trade-offs, fragmentation, and extents — with OS interview questions answered.
Expected Interview Answer
File allocation methods are the strategies a file system uses to map a file’s logical blocks onto physical disk blocks, and the three classic approaches are contiguous, linked, and indexed allocation, each trading off seek performance, fragmentation, and ease of growth differently.
Contiguous allocation stores a file as one unbroken run of disk blocks, which gives excellent sequential and random-access speed since only a start block and length are needed, but it suffers from external fragmentation and makes files hard to grow in place. Linked allocation stores each block with a pointer to the next block, so a file can grow one block at a time anywhere on disk with no external fragmentation, but random access is slow because the OS must walk the chain from the start, and a corrupted pointer can lose the rest of the file. Indexed allocation gives each file an index block holding pointers to all of its data blocks, which supports fast random access without contiguous placement, at the cost of the extra index block overhead and the need for multi-level or linked index blocks once a file grows very large. Real file systems like ext4 use extent-based indexed allocation, a hybrid that groups contiguous runs into indexed extents to get most of the speed of contiguous allocation with the flexibility of indexing.
- Explains the space vs speed trade-off behind real file systems
- Clarifies why random access differs so much between methods
- Connects fragmentation behavior to allocation strategy choice
- Foundation for understanding extent-based modern file systems
AI Mentor Explanation
Contiguous allocation is like reserving one unbroken block of seats for a whole travelling supporters group, fast to find and walk to but impossible to expand once neighboring seats are sold. Linked allocation is like each supporter holding a ticket that names the seat of the next supporter in their group, so the group can scatter anywhere in the stadium and grow freely, but finding the tenth supporter means walking the whole chain from the first. Indexed allocation is like the group captain holding a single card listing every seat number in the group directly, letting anyone be found instantly without walking a chain.
Step-by-Step Explanation
Step 1
Contiguous allocation
File occupies one unbroken run of blocks; only a start block and length are stored, giving fast sequential and random access.
Step 2
Linked allocation
Each block stores a pointer to the next block, allowing scattered growth but requiring a full chain walk for random access.
Step 3
Indexed allocation
A dedicated index block stores pointers to every data block, enabling direct random access without contiguity.
Step 4
Hybrid extents
Modern file systems like ext4 index contiguous extents rather than individual blocks, balancing speed and flexibility.
What Interviewer Expects
- Correct description of contiguous, linked, and indexed allocation
- A concrete trade-off between each method (fragmentation vs random access)
- Awareness that random access is the weak point of linked allocation
- Knowledge that modern file systems use extent-based hybrids
Common Mistakes
- Saying linked allocation supports fast random access
- Forgetting that contiguous allocation suffers external fragmentation
- Not mentioning the index block overhead of indexed allocation
- Confusing file allocation methods with free-space management (bitmaps, free lists)
Best Answer (HR Friendly)
“File allocation methods are how a file system decides where to physically store the pieces of a file on disk. Contiguous allocation packs a file into one solid block for speed but makes it hard to grow; linked allocation scatters pieces with pointers between them so it grows easily but is slow to jump around in; and indexed allocation keeps a separate map of every piece so you get fast random access without needing everything to be next to each other.”
Code Example
#define MAX_BLOCKS 128
struct inode {
int size_bytes;
int index_block; /* block holding the pointer array */
};
int get_block_address(struct inode *file, int logical_block,
int *index_table) {
/* index_table was read from disk at file->index_block */
if (logical_block >= MAX_BLOCKS) {
return -1; /* out of range for single-level index */
}
return index_table[logical_block]; /* direct lookup, no chain walk */
}Follow-up Questions
- How does multi-level indexing handle very large files?
- Why does linked allocation eliminate external fragmentation?
- How do modern file systems like ext4 use extents instead of per-block pointers?
- What happens to a linked-allocation file if one pointer becomes corrupted?
MCQ Practice
1. Which file allocation method suffers most when doing random access?
Linked allocation requires walking the pointer chain from the start of the file, making random access slow.
2. What is the main downside of contiguous allocation?
Because a file must occupy one unbroken run, free space becomes fragmented and growing a file often requires relocation.
3. What does indexed allocation add compared to linked allocation?
Indexed allocation stores all block pointers in one index block, so any block can be located directly instead of via a chain.
Flash Cards
Name the three classic file allocation methods. — Contiguous, linked, and indexed allocation.
Which method is fastest for random access? — Contiguous or indexed allocation — both allow direct block lookup.
Which method has no external fragmentation? — Linked allocation, since blocks can be scattered anywhere.
What do modern file systems use instead of per-block indexing? — Extent-based indexing, which indexes contiguous runs of blocks.