← 🗂️ File Systems
Subtopic 4 of 4

7.4Free-space management and file-system structure

The idea

Free-space management tracks unused blocks: bit map, linked list, grouping or counting. The file system itself is layered and may keep a journal.

Think of it like this: A parking lot attendant with a board of occupied and free bays (bit map), or a chain of notes ("next free bay is...").

Why it exists

The OS must allocate quickly and keep the record small and safe through crashes.

How it works

  1. Bit map: one bit per block; size = blocks / 8 bytes; good at finding a run.
  2. Linked list: no extra space but slow to scan.
  3. Grouping and counting reduce the number of disk reads.
  4. Journaling logs metadata changes first so recovery after a crash is quick.

Worked example: 8 GB disk with 4 KB blocks

2 097 152 blocks, so the bit map is 262 144 bytes = 256 KB, which is 64 blocks.

Now play with it

  • →Use the bit-map calculator with 1 TB and 4 KB blocks.
  • →Compare the four methods in the table.
Blocks2097152
Bit map size (1 bit per block)256 KB
Blocks needed to hold the map64

Bit map: simple and good at finding a run of free blocks, but must be kept in memory to be fast. A linked free list needs no extra space but is slow to scan.

MethodIdeaGood for
Bit mapone bit per block (1 = free)finding contiguous runs
Linked listeach free block points to the nextno extra space
Groupingfirst free block lists n free addressesquick batch allocation
Countingaddress + number of free blocks in the runruns of free space

Check yourself

A bit map for a disk of N blocks needs

Remember: Bit map = blocks / 8 bytes. Journaling protects metadata.
Exam notes (the dense version)

Free blocks can be tracked with a bit map (one bit per block; easy to find a run of blocks; size = number of blocks / 8 bytes), a linked list of free blocks, grouping (a free block stores the addresses of n others) or counting (start address plus run length). A disk is divided into partitions, mounted into the directory tree. Layered design: application → logical file system → file-organisation module → basic file system → I/O control → devices. Journaling logs metadata changes first so a crash can be repaired quickly.

Previous year questions: File Systems (5)

PYQs are grouped by topic, so this is the full set for File Systems; try the ones that match this subtopic. Open all 5 on the topic page.