Free-Space Management
Free-Space Table
File storage organizes occupied data blocks, but where should a new block be saved? Scanning all disk blocks to find free space is inefficient, so free space also needs a management mechanism.
A free-space table records each free region's first block and number of blocks. This method supports contiguous allocation.
| Entry | First free block | Free block count |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 8 | 3 |
| 3 | 13 | 2 |
| 4 | … | … |
When space is requested, the system scans the table until a suitable free region is found. Removing a file reclaims its space: the table is scanned to find an entry for the released region's first physical block and block count.
This method works well when there are few free regions. Many small regions make the table large and slow to search. This allocation technique is suited to contiguous files.
Free-Block List
Free space can also be managed by a linked list, with each free block pointing to the next. Creating a file removes one or more blocks from the head; reclaiming space inserts the released blocks at the head.
Only a pointer to the first free block needs to remain in main memory. The method is simple but does not support random access. Searching or moving blocks along the list can require several I/O operations, while pointers consume storage space.
In large file systems with many free regions or blocks, free-space tables and lists can become large and inefficient.
Bitmap (Bit Table)
A bitmap uses one binary bit for each disk block. Here, 0 means free and 1 means allocated. Many Linux file systems manage free space with bitmaps.
One disk, three maps of its free blocks
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Allocate and return bitmap blocks
Here 0 means free and 1 means allocated. Allocate four blocks by scanning from the lowest block number, then release them. State the selected blocks, bitmap after allocation and remaining free count.
Implement allocate(bitmap, count) in Python. It may use scattered blocks; if space is insufficient return None without changing any bit. Assume valid 0/1 bits and a positive integer count. Also calculate bitmap storage for a 1 GiB disk with 4 KiB blocks (GiB = 2³⁰ bytes, KiB = 2¹⁰ bytes).