CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 3 of 7 · 2 min read

Contiguous and linked

Think of seating a family at a restaurant. Contiguous allocation asks for one long table, which is quick to serve and hard to find when the restaurant is busy. Linked allocation gives each person any free seat and a note that says where the next one sits, which is easy to arrange and slow to follow. The analogy stops in one place: a waiter walks quickly between seats, while following a link on disk costs a read.

In plain words: In contiguous allocation a file occupies consecutive blocks. The directory needs only the first block and the length. Reading in order is as fast as the disk can go, and a byte at any offset is found by arithmetic. The problem is external fragmentation: after many creations and deletions, the free space is split into small gaps, and a new file cannot find a long enough run although the total free space is large. A file also cannot grow if the next block is in use. In linked allocation each block holds the number of the next block. Any free block can be used, so there is no external fragmentation, but a byte in the middle needs a walk along the chain, and one lost pointer loses the rest of the file.

A worked example (made up to show the idea). To reach block 1,000 of a linked file, the system reads 1,000 blocks in turn to follow the chain, which at 13.2 ms each is 13.2 s. A file allocation table (FAT) fixes this by moving all the next-block numbers out of the data blocks and into one table at the start of the disk. The table is kept in memory, so the walk to block 1,000 is 1,000 memory lookups, followed by one disk read. The cost of the FAT is its size. For a 1 TiB disk with 4 KiB clusters and 4-byte entries, the table has 2^40 / 2^12 = 268,435,456 entries, which is 1 GiB of memory.

The key lines. FAT is simple and is still used on small devices and memory cards for that reason. Contiguous allocation lives on in optical discs and in the extents of page 4. Linked allocation, in its pure form, is rare.

External fragmentation

External fragmentation is the state in which the free space of a storage area is split into many small pieces, so that a request for a large contiguous piece fails although the total free space would be enough. It is the cost of contiguous allocation.

Example: a disk with 100 free blocks in 50 separate gaps of 2 cannot hold a contiguous file of 10 blocks.

Check yourself: 1. Why is reading a contiguous file in order fast? 2. How does a FAT make the walk to block 1,000 cheaper? 3. How big is a FAT for 2^28 clusters with 4-byte entries?