Free Space Management: Bitmaps
What You'll Learn
You'll learn how file systems use bitmaps—compact arrays of bits—to efficiently track which disk blocks are free or allocated.
The Core Idea
Imagine a parking lot with 100 spaces. Instead of writing a list of which spaces are empty, you could use a simple chart where each box is either checked (occupied) or unchecked (available). A bitmap works exactly this way for disk blocks.
In bitmap free space management, the file system maintains an array where each bit represents one disk block. If a bit is 0, that block is free; if it's 1, the block is allocated (or vice versa, depending on convention). This single structure provides a complete map of your entire disk's availability.
Why Bitmaps?
Compared to other free space tracking methods (like linked lists of free blocks), bitmaps offer several advantages:
- Compact representation: One bit per block means minimal storage overhead
- Fast contiguous allocation: You can quickly scan for consecutive
0bits to allocate adjacent blocks - Direct access: Finding the status of block n is just a matter of checking bit n
Example Structure
For a disk with 16 blocks, your bitmap might look like:
1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1
This shows blocks 1, 4, 5, 6, 10, 11, and 13 are free, while others are allocated.
Storage Overhead
If you have 1 million blocks, you need 1 million bits (about 125 KB) to track them all—a tiny fraction of your total disk space.
Key Takeaway: Bitmaps provide a space-efficient, fast method for tracking free disk blocks by using one bit per block to indicate availability, enabling quick allocation decisions and minimal storage overhead.