GATE CS 2017 Set 2 Q08 — File Systems

To determine which allocation schemes avoid external fragmentation, let us analyze each scheme:

1. Contiguous Allocation: In this scheme, each file occupies a contiguous set of blocks on the disk. As files are created, updated, and deleted, the free disk space gets broken into small, non-contiguous pieces. If a new file requires $N$ blocks, but no single contiguous block of size $N$ is available (even if the total free space is greater than $N$), the file cannot be allocated. This leads to external fragmentation.
2. Linked Allocation: Here, each file is a linked list of disk blocks, which can be scattered anywhere on the disk. Since any free block can be allocated to any file, there is no external fragmentation.
3. Indexed Allocation: This scheme brings all the pointers to scattered blocks together into a single location called the index block. Just like linked allocation, blocks can be distributed anywhere on the disk, meaning there is no external fragmentation.

Therefore, only Linked (2) and Indexed (3) allocation schemes can be used if no external fragmentation is allowed.