Directory & Free Space

A file system has two separate bookkeeping jobs that people often confuse. One is the directory: organising files for humans into nested folders with readable names. The other is free-space management: the machine's own ledger of which disk blocks are currently in use and which are available to hand out. They sound related, but they answer completely different questions — *where is my file?* versus *where is there room?*

Directory structures

1. 1Single-level — one flat list of all files. Simple, but every name on the whole disk must be unique, which collapses the moment two users both want notes.txt.
2. 2Two-level — one directory *per user*, so names only need to be unique within a user. Fixes collisions but allows no further grouping.
3. 3Tree-structured — folders nested inside folders down to files at the tips, named by a path like /home/user/docs/report.txt. This is the familiar layout almost every modern OS uses.
4. 4Acyclic-graph — allow the same file to appear in two folders at once (hard links), so it can be shared without copying. Powerful, but deletion must track how many names point at the data.

Free-space management

The most common scheme is a bit vector (bitmap): one bit per disk block. In this visualizer the convention is 1 = used, 0 = free. Creating a file flips some 0s to 1s; deleting one flips them back. To place a new file, the file system scans the bitmap for a run of 0s.

block:  0  1  2  3  4  5  6  7  8  9
bit:    1  1  0  0  1  0  0  0  1  1      (1 = used, 0 = free)

Reading off the 0s, the free blocks are 2, 3, 5, 6, 7. A request for a 3-block contiguous file can't use the gap at 2-3 (only two blocks), so the scan continues and places it at the first long-enough run: 5, 6, 7. Those three bits then flip to 1.