Loading learning content...
In the realm of memory and storage allocation, external fragmentation is one of the most insidious problems. It describes a paradox: a system can have more than enough free space in total, yet be unable to allocate even a modest request because that free space is scattered into pieces too small to use.
Contiguous allocation suffers terribly from this problem. As files are created and deleted, the disk becomes a Swiss cheese of unusable gaps. Eventually, allocating a new file requires expensive compaction—moving existing files to consolidate free space—or simply fails.
Linked allocation's most celebrated achievement is the complete elimination of external fragmentation. This page explores how and why this works, what it means for disk utilization, and what subtle inefficiencies remain despite this victory.
By the end of this page, you will fully understand why linked allocation is immune to external fragmentation, see concrete examples demonstrating this property, appreciate the 100% utilization implications for disk capacity, and recognize that while external fragmentation is eliminated, internal fragmentation remains as a separate concern.
Before appreciating linked allocation's solution, we must deeply understand the problem it solves.
Formal Definition:
External fragmentation occurs when total free space exists to satisfy an allocation request, but the free space is not contiguous—it's broken into pieces, none of which is large enough for the request.
The Contiguous Allocation Problem:
In contiguous allocation, a file must occupy consecutive disk blocks. As files are created and deleted over time:
Quantifying External Fragmentation:
External fragmentation can be measured as:
External Fragmentation = 1 - (Largest Free Hole / Total Free Space)
For the example above:
Impact of external fragmentation:
Studies of memory allocation show that, on average, external fragmentation wastes approximately 1/3 of memory under first-fit allocation. This is sometimes called the '50% rule' because it means you may need 150% of actual data size to store 100% of data.
Linked allocation's immunity to external fragmentation stems from a simple but profound change in how we think about allocation:
In linked allocation, files don't need contiguous space. ANY free block can be used for ANY file.
The Key Insight:
When files are linked lists of blocks:
Mathematical Certainty:
If at least one block is free, an allocation of one block succeeds. Since files are built one block at a time:
Allocation succeeds if: total_free_blocks >= blocks_needed
There's no requirement about WHERE those free blocks are located.
Formal Proof of Zero External Fragmentation:
Theorem: Linked allocation has zero external fragmentation.
Proof:
1. Definition: External fragmentation exists when total_free >= request
but no contiguous region >= request.
2. In linked allocation, allocation requires:
- For request of N blocks, find N free blocks (any N blocks)
- Contiguity is NOT required
3. Therefore, the condition "no contiguous region >= request" is
meaningless for linked allocation.
4. Allocation succeeds iff total_free >= N blocks needed.
5. Since the contiguity constraint is eliminated, external
fragmentation (by definition) cannot occur. ∎
This is not an approximation or 'usually true'—it's a mathematical certainty. Linked allocation CANNOT suffer external fragmentation by the very nature of how allocation works. If you have 1000 free blocks scattered across a disk, you can allocate a 1000-block file, period.
Let's walk through a scenario that would be catastrophic for contiguous allocation but perfectly normal for linked allocation.
Initial State:
A 16-block disk with scattered free blocks after various file operations:
Analysis:
| Category | Blocks | Details |
|---|---|---|
| File A (blue) | 0, 7, 13 | 3 blocks scattered |
| File B (purple) | 2, 3, 11 | 3 blocks, partially contiguous |
| File C (orange) | 5, 8, 15 | 3 blocks scattered |
| FREE (green) | 1, 4, 6, 9, 10, 12, 14 | 7 blocks total |
Contiguous Allocation View:
Largest free gap analysis:
Maximum contiguous allocation possible: 2 blocks
A request for 3+ blocks would FAIL, despite having 7 free blocks.
Linked Allocation View:
Now let's allocate a new 5-block file using linked allocation:
123456789101112131415161718192021222324252627282930
// Allocate 5 blocks for new file// Free blocks available: 1, 4, 6, 9, 10, 12, 14 (7 total)// Need 5 blocks - SUCCESS FileEntry *create_file("data.txt") { FileEntry *file = new_file_entry(); // Block 1: First block of file file->first_block = allocate_next_free(); // Returns block 1 // Allocation proceeds through free list: // Block 1 → points to Block 4 // Block 4 → points to Block 6 // Block 6 → points to Block 9 // Block 9 → points to Block 10 // Block 10 → points to EOF return file;} // Resulting file chain:// Directory: data.txt → Block 1// Block 1: data, ptr → 4// Block 4: data, ptr → 6// Block 6: data, ptr → 9// Block 9: data, ptr → 10// Block 10: data, ptr → EOF // Remaining free blocks after allocation: 12, 14 (2 blocks)// All 5 blocks successfully allocated!The disk was severely fragmented—no contiguous run longer than 2 blocks. Yet we successfully allocated a 5-block file. This is the power of eliminating the contiguity requirement.
The elimination of external fragmentation has a profound implication: every free block is always usable.
The Utilization Guarantee:
With linked allocation:
Comparison with Contiguous Allocation:
| Scenario | Total Capacity | Free Space | Contiguous Usable | Linked Usable |
|---|---|---|---|---|
| Fresh disk | 1000 blocks | 1000 blocks | 1000 blocks (100%) | 1000 blocks (100%) |
| After light use | 1000 blocks | 600 blocks | ~550 blocks (92%) | 600 blocks (100%) |
| After moderate use | 1000 blocks | 400 blocks | ~250 blocks (63%) | 400 blocks (100%) |
| After heavy use | 1000 blocks | 300 blocks | ~80 blocks (27%) | 300 blocks (100%) |
| Severely fragmented | 1000 blocks | 200 blocks | ~20 blocks (10%) | 200 blocks (100%) |
Real-World Implications:
Consider a 1TB disk with 50% free space (500GB):
| Allocation Method | Usable Free Space | Lost to Fragmentation |
|---|---|---|
| Contiguous (new disk) | ~500GB | ~0GB |
| Contiguous (1 year use) | ~300GB | ~200GB |
| Contiguous (3 years use) | ~100GB | ~400GB |
| Linked (any age) | ~500GB | ~0GB |
The difference is dramatic. Linked allocation provides predictable, stable capacity regardless of how the disk is used.
On SSDs and flash storage, the absence of external fragmentation is even more valuable. Flash devices use wear-leveling algorithms that deliberately scatter writes. Linked allocation aligns perfectly with this behavior, while contiguous allocation fights against it.
The End of Compaction:
Contiguous allocation systems require periodic compaction—moving files to consolidate free space. Compaction is:
With linked allocation, compaction is never needed. The disk can be 99% full with single-block free spaces scattered everywhere, and the next allocation still succeeds instantly.
While linked allocation eliminates external fragmentation, it does NOT eliminate internal fragmentation—a different but related problem.
Internal Fragmentation Defined:
Internal fragmentation occurs when allocated space is larger than the data stored in it, wasting space within the allocated region.
In block-based file systems, the unit of allocation is the block. If a file doesn't perfectly fill its blocks, space is wasted:
File size: 10,000 bytes
Block size: 4,096 bytes (4KB)
Data per block: 4,092 bytes (4 bytes for pointer)
Blocks needed: ceil(10,000 / 4,092) = 3 blocks
Space allocated: 3 × 4,096 = 12,288 bytes
Space used for data: 10,000 bytes
Space used for pointers: 3 × 4 = 12 bytes
Space wasted (internal frag): 12,288 - 10,000 - 12 = 2,276 bytes
Average Internal Fragmentation:
For any random file size, the last block is, on average, half full:
Average internal fragmentation = (Block Size) / 2
= 4096 / 2 = 2,048 bytes per file
For a file system with 1 million files:
The Pointer Overhead Tax:
Linked allocation has additional internal "fragmentation" from pointers:
Pointer overhead = (Pointer Size / Block Size) × 100%
= (4 / 4096) × 100% = 0.098%
For a 1TB disk:
| Scenario | Avg File Size | Files per TB | Internal Frag/File | Total Waste |
|---|---|---|---|---|
| Many small files | 4KB | 244 million | ~2KB | ~200GB (20%) |
| Medium files | 100KB | 10 million | ~2KB | ~20GB (2%) |
| Large files | 1MB | 1 million | ~2KB | ~2GB (0.2%) |
| Huge files | 1GB | 1,000 | ~2KB | ~2MB (0.0002%) |
Internal fragmentation disproportionately affects small files. A 1-byte file still requires one full block (4KB), wasting 99.98% of the space. File systems optimize for this with techniques like tail packing, inline data, or variable block sizes.
While linked allocation doesn't suffer from external fragmentation in terms of space, it introduces a different kind of fragmentation: physical fragmentation or scatter.
The Locality Problem:
When allocating blocks from a free list:
Why This Matters on HDDs:
Hard disk drives have mechanical read heads that must physically move:
Contiguous blocks: Block 100 → Block 101 → Block 102
Single track read, no seeks
Time: ~0.1ms per block
Scattered blocks: Block 100 → Block 5,432 → Block 789
Seek for each block
Time: ~5-10ms per block
100x performance difference for sequential file access!
Measuring File Scatter:
The degree of scatter can be quantified as:
Scatter Index = Number of non-consecutive block transitions / Total blocks - 1
Perfectly contiguous file: 0%
Completely scattered file: 100%
Example:
A file with blocks: 5, 6, 7, 23, 24, 50
| File Size | Scatter % | Contiguous Time | Scattered Time | Slowdown |
|---|---|---|---|---|
| 1 MB (244 blocks) | 0% | ~50ms | ~50ms | 1x |
| 1 MB (244 blocks) | 25% | ~50ms | ~350ms | 7x |
| 1 MB (244 blocks) | 50% | ~50ms | ~650ms | 13x |
| 1 MB (244 blocks) | 100% | ~50ms | ~1.2s | 24x |
| 10 MB (2,440 blocks) | 50% | ~500ms | ~6.5s | 13x |
On solid-state drives, seek time is essentially zero. Random access takes about the same time as sequential access. This eliminates the scatter penalty, making linked allocation much more practical on modern SSD-based systems.
Defragmentation vs Compaction:
Note the distinction:
Linked allocation doesn't need compaction, but files can still benefit from defragmentation for read performance. However, defragmentation doesn't affect space utilization—it's purely a performance optimization.
How the file system chooses which free block to allocate affects scatter and performance. Several strategies exist:
1. First Available (FIFO):
Allocate the first block on the free list:
2. Best Fit (Nearest):
Allocate the free block closest to the file's existing blocks:
3. Rotor/Circular:
Maintain a rotating pointer through free blocks:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
// Strategy 1: First Availableuint32_t allocate_first_available() { if (free_list_head == NULL_BLOCK) { return INVALID_BLOCK; // Disk full } uint32_t block = free_list_head; free_list_head = get_next_free(block); return block;} // Strategy 2: Nearest to Targetuint32_t allocate_nearest(uint32_t target) { uint32_t best = NULL_BLOCK; uint32_t best_distance = UINT32_MAX; for (uint32_t block = first_free; block != NULL_BLOCK; block = get_next_free(block)) { uint32_t distance = abs((int32_t)block - (int32_t)target); if (distance < best_distance) { best = block; best_distance = distance; if (distance <= 1) break; // Adjacent found, can't do better } } if (best != NULL_BLOCK) { remove_from_free_list(best); } return best;} // Strategy 3: Rotor Allocationstatic uint32_t rotor = 0; uint32_t allocate_rotor() { uint32_t start = rotor; do { if (is_block_free(rotor)) { uint32_t block = rotor; rotor = (rotor + 1) % total_blocks; mark_block_allocated(block); return block; } rotor = (rotor + 1) % total_blocks; } while (rotor != start); return INVALID_BLOCK; // Disk full}| Strategy | Time Complexity | Locality | Best For |
|---|---|---|---|
| First Available | O(1) | Poor | Fast allocation, any storage |
| Nearest to Target | O(n) or O(log n) | Excellent | HDD sequential workloads |
| Rotor | O(n) worst case | Moderate | SSD wear leveling |
| Reserved Zones | O(1) | Excellent | Known access patterns |
FAT uses a variation of 'nearest to target': when allocating, it searches forward from the last allocated block. This provides reasonable locality while maintaining simplicity. The search wraps around if the end is reached without finding a free block.
We've thoroughly explored linked allocation's greatest strength—the complete elimination of external fragmentation. Let's consolidate our understanding:
What's next:
The next page confronts linked allocation's most significant weakness: poor random access performance. We'll analyze why seeking to block N requires reading N blocks, see the mathematical proof of O(n) access complexity, and understand why this makes pure linked allocation impractical for many workloads.
You now understand why linked allocation is immune to external fragmentation and guarantees 100% space utilization. This fundamental property made linked allocation (particularly the FAT variant) successful for decades. However, this strength comes with tradeoffs we'll examine next.