Free Space Management: Linked List
What You'll Learn
You'll learn how file systems can track free disk blocks by linking them together in a chain, and understand the storage trade-offs this approach involves.
The Core Idea
Instead of using a bitmap to track free space (where each bit represents whether a block is free or allocated), a file system can maintain a linked free list. In this approach, each free block stores a pointer to the next free block, forming a chain. The file system keeps a pointer to the head of this list—the first free block.
When you need to allocate a block, you simply grab the head of the list and update the head pointer to the next block in the chain. When you free a block, you add it to the front of the list (or anywhere in the chain).
How It Works
Think of it like a scavenger hunt where each clue (free block) tells you where the next clue is hidden. The file system's superblock says "start at block 47," and block 47 contains data saying "the next free block is 103," and so on.
Storage Overhead
Here's the interesting trade-off: each free block must dedicate some space to store the pointer to the next free block. If blocks are 4KB but pointers are only 4 bytes, this overhead is negligible. However, you cannot use a free block's full capacity until you allocate it and remove it from the list.
The overhead is proportional to the number of free blocks, unlike bitmaps where overhead is proportional to total blocks. When the disk is nearly full (few free blocks), the linked list is very compact. When mostly empty, it's larger but still distributed across the free blocks themselves.
Key Takeaway: Linked free lists chain available blocks together using pointers stored in each free block, offering low overhead when disk space is scarce but requiring traversal to find free blocks and sacrificing pointer space in each free block.