Course contentsShow
← Computer Science
Lesson 1403 of 2,87232. File SystemsFree lesson

Free Space Management: Bitmaps

Understand bitmap representation of free blocks where each bit indicates block availability.

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 0 bits 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.