CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 2 of 7 · 2 min read

The problem

Think of a parking garage where cars arrive and leave all day. The attendant must find a space for each new car, remember where each car is, and keep room for cars that stay for a long time. The analogy stops in one place: a car does not grow, while a file may grow after it is placed.

In plain words: A file system must record, for each file, which disk blocks hold its bytes and in which order. Files grow, shrink and are deleted, so the free space becomes scattered. A method is good if it reads a file in order quickly (few moves of the arm, large transfers), reaches any byte in the middle quickly, wastes little space, and lets a file grow without moving it. No method wins on all four.

A worked example (made up to show the idea). A file of 100,000 bytes needs 25 blocks of 4 KiB (24.4 rounded up). If its blocks are all next to each other, one seek and one transfer of 100 KB read it all. If they are spread over 25 places, it costs 25 seeks. At 13.2 ms per random block (Level 8, page 1) that is 25 x 13.2 = 330 ms, against about 13 ms plus 1 ms of transfer for the contiguous case. The layout of a file can matter more than its size.

The key lines. The four methods in this page are contiguous, linked (with the FAT variant), indexed and extent allocation. The first two are simple and the last two are used by Unix and Linux file systems.

Allocation method

An allocation method is the rule by which a file system chooses disk blocks for a file and records where they are. It decides how fast a file can be read in order, how fast a byte at a given offset can be found, how much space is wasted, and how easily the file can grow.

Example: contiguous allocation puts a file in consecutive blocks and records only the first block and the length.

Check yourself: 1. How many 4 KiB blocks does a file of 100,000 bytes need? 2. Name the four things that a good method balances. 3. Why can the layout of a file matter more than its size?