// the one-minute version
Under the tidy tree of Chapter 13, the OS must map each file onto raw disk blocks. The big decision is the allocation method: contiguous (fast but fragments), linked/FAT (no external fragmentation but slow random access), or indexed (an index block lists a file's blocks — the modern winner). The OS also tracks which blocks are free and must recover cleanly after a crash.
A file looks like one smooth stream of bytes. On disk it's often scattered across blocks all over. The implementation job: remember which blocks belong to which file, find free ones to grow into, and not lose your data when the power dies mid-write.
01 On-disk structures
A file system keeps bookkeeping on the disk itself: a boot block (startup code), a superblock/volume control block (total blocks, free count, sizes), a directory structure (names → file records), and a per-file record — UNIX calls it an inode — holding the file's attributes and pointers to its data blocks. Crucially, the inode does not hold the file's name (the directory does), which is what makes hard links work.
02 Allocation methods
The central design choice — how to assign disk blocks to a file:
Contiguous
Store a file in consecutive blocks. Fast for sequential and direct access (just offset from the start). But it suffers external fragmentation and a file can't easily grow past its neighbor.
Linked
Each block holds a pointer to the next, like a chain. No external fragmentation, files grow freely — but direct access is slow (follow the chain), and one broken pointer loses the rest of the file.
FAT
A variant of linked, where all the "next" pointers live in a File Allocation Table at the start of the volume. Faster random access than scattered links; the basis of MS-DOS and USB-stick file systems.
Indexed
Give each file an index block listing all its data-block addresses. Fast direct access (look up the block) and no external fragmentation. The standard modern approach.
Fig 1 — Indexed allocation. One index block holds the addresses of all the file's data blocks, scattered anywhere — fast random access, no external fragmentation.
03 Free-space management
The OS must know which blocks are available. Two common methods: a bit map (one bit per block, 1 = free) that's compact and makes finding contiguous free runs easy; or a linked free list chaining free blocks together. Allocating flips bits / pops the list; deleting returns blocks to free. Bit maps are favored when you want contiguous allocation; they're small enough to cache in RAM.
04 Directory implementation
A directory is itself a file whose contents map names to file records. A simple linear list of entries is easy but slow to search in a big directory (linear scan per lookup); a hash table or B-tree makes name lookup fast. This is why looking up a file in a directory with a million entries can be slow or fast depending on the design — and why some file systems index directories.
05 Crash recovery
Writing a file touches several structures — the data block, the free map, the directory, the inode. If the power dies between those writes, the file system is left inconsistent (a block marked used but in no file, or vice versa; a directory entry pointing at a half-written inode).
fsck — scan the entire disk on boot to find and repair inconsistencies, which can take many minutes on a large volume. The modern fix is journaling (Chapter 15).common catches & gotchas
- Inode holds no name — The name is in the directory; the inode holds attributes and block pointers. This separation enables hard links and trips up beginners.
- Linked allocation kills random access — To read block 500 you must follow 499 pointers. Great for sequential, terrible for direct access — the opposite of contiguous.
- Multi-level indexing favors small files — Direct pointers make small files cheap; indirect blocks only kick in for large files. The design is deliberately asymmetric.
- Directory lookup can be O(n) — A linear-list directory scans every entry per lookup. Huge directories are slow unless hashed/indexed.
- A crash mid-write corrupts structures — Multi-step updates aren't atomic on plain file systems. Without journaling you risk inconsistency and a slow fsck.
06 Questions students actually ask
Why is indexed allocation usually preferred?
It gives fast direct access (look up any block in the index) and avoids external fragmentation, while letting files grow. Contiguous is fast but fragments and can't grow easily; linked grows freely but is slow for random access.
What does the inode store?
A file's attributes (owner, size, permissions, timestamps) and pointers to its data blocks — including multi-level index pointers for large files. It does not store the file's name; that's in the directory.
Bit map vs free list for free space?
A bit map uses one bit per block — compact and good at finding contiguous runs. A linked free list chains free blocks — simple but harder to find contiguous space. Both track what's available to allocate.
What is multi-level indexing?
The inode holds a few direct block pointers plus single-, double-, and triple-indirect pointers to index blocks. Small files use only direct pointers (fast); huge files reach more blocks through the indirect levels.
What makes a file system inconsistent?
A crash partway through a multi-step update — e.g., a block allocated in the free map but not yet linked into a file. The structures contradict each other, which recovery (fsck or journaling) must fix.
07 Key takeaways
- On-disk structures: boot block, superblock, directories, and per-file inodes (which hold no name).
- Allocation: contiguous (fast, fragments), linked/FAT (flexible, slow random), indexed (the modern choice).
- Large files use multi-level indexes (direct + indirect pointers).
- Free space is tracked by bit map or linked list.
- Directories are linear lists, hash tables, or B-trees — lookup speed depends on the choice.
- A crash mid-update causes inconsistency; recovery (fsck, or journaling) repairs it.
08 Wrapping up
You've seen how one file system lays itself out on disk. But a real OS runs many file systems at once and must survive crashes gracefully — the internal machinery that makes that work is next. Next up: File-System Internals.