Contiguous Allocation - Learning Module

Loading content...

0/227

Compaction Needed

Defragmenting the Disk

When external fragmentation renders contiguous allocation unusable, compaction (also called defragmentation) is the remedy. Compaction consolidates free space by relocating files to eliminate gaps, creating larger contiguous regions.

However, compaction is expensive—both in time and I/O resources. Understanding when and how to compact is essential for systems that rely on contiguous allocation.

What You Will Learn

By the end of this page, you'll understand the compaction process, various compaction algorithms, the substantial costs involved, and strategies for minimizing compaction overhead.

The Compaction Process

Compaction works by moving files to consolidate free space. The basic algorithm:

Identify holes — Locate all free regions on the disk
Select files to move — Choose files adjacent to holes
Relocate files — Read file data, write to new location
Update metadata — Modify directory entries with new locations
Mark old space free — Add vacated blocks to free list
Repeat — Continue until free space is consolidated

Converting Mermaid diagram...

Compaction Algorithms

Different compaction strategies trade off simplicity, speed, and effectiveness:

Compaction Strategies

•Simple Compaction: Move all files to one end of the disk. Maximum consolidation but most data movement.
•Partial Compaction: Merge only adjacent holes by moving the smallest neighboring file. Less I/O but incomplete consolidation.
•Selective Compaction: Move only files that create the biggest consolidated regions. Optimizes benefit per I/O cost.
•Background Compaction: Compact gradually during idle time. Minimizes user-visible impact.

compaction.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * Simple Compaction Algorithm
 * 
 * Moves all files toward block 0, leaving all
 * free space at the end of the disk.
 */
 
typedef struct {
    char name[256];
    uint64_t start_block;
    uint32_t block_count;
} file_entry_t;
 
void compact_disk(disk_t *disk, file_entry_t *files, int count) {
    uint64_t next_free = 0;  /* Next available position */
    
    /* Sort files by current start position */
    sort_by_start_position(files, count);
    
    for (int i = 0; i < count; i++) {
        file_entry_t *f = &files[i];
        
        if (f->start_block > next_free) {
            /* Need to move this file */
            printf("Moving %s: block %lu -> %lu\n",
                   f->name, f->start_block, next_free);
            
            /* Read from old location */
            void *buffer = malloc(f->block_count * BLOCK_SIZE);
            read_blocks(disk, f->start_block, 
                       f->block_count, buffer);
            
            /* Write to new location */
            write_blocks(disk, next_free, 
                        f->block_count, buffer);
            
            /* Update directory entry */
            f->start_block = next_free;
            update_directory(f);
            
            free(buffer);
        }
        
        next_free = f->start_block + f->block_count;
    }
    
    /* All space from next_free onward is now free */
    mark_range_free(disk, next_free, 
                   disk->total_blocks - next_free);
}

The Costs of Compaction

Compaction is expensive. Let's quantify the costs:

Compaction Cost Analysis (1 TB Disk, 50% Used)
Cost Type	Measurement	Impact
Data Movement	~500 GB read + 500 GB write	Hours of I/O
Time (HDD)	~6-8 hours at 100 MB/s	Long outage
Time (SSD)	~30-60 minutes at 500 MB/s	Significant delay
Disk Wear (SSD)	500 GB of writes	Reduced lifespan
Availability	System unusable or degraded	User impact
Power Consumption	Sustained high I/O	Resource cost

The Compaction Trade-off

Compaction can take longer than the time saved by faster sequential access. For frequently modified file systems, the cost of repeated compaction outweighs the benefits of contiguous allocation entirely.

Online vs Offline Compaction

Offline Compaction:

System is unavailable during compaction
Simpler implementation (no concurrency concerns)
Faster completion (no interruptions)
Used in early systems and maintenance windows

Online Compaction:

System remains available during compaction
Must handle concurrent file operations
Complex locking and consistency requirements
May take longer but preserves availability

Challenges of Online Compaction:

•Atomicity: File moves must be atomic—partial moves corrupt data
•Locking: Files being moved must be locked against modification
•Directory Updates: Must be synchronized with file relocation
•Open Files: Cannot move files with active file handles (easily)
•Crash Recovery: Must handle failures mid-compaction

Strategies to Minimize Compaction

Given compaction's costs, systems try to minimize its necessity:

Compaction Reduction Strategies

•Over-allocation: Allocate extra space for files that may grow, reducing future fragmentation.
•Delayed Allocation: Don't allocate until data is actually written, allowing better placement decisions.
•Best-Fit Allocation: Minimize wasted space per allocation, though creates tiny fragments.
•Preventive Moves: Relocate small files during idle time before fragmentation becomes severe.
•Hybrid Allocation: Use contiguous for read-heavy files, linked/indexed for others.

The Modern Solution

Modern file systems largely avoid the compaction problem by using extent-based allocation—files get contiguous extents when possible, but can span multiple non-contiguous extents when needed. This provides most of the sequential access benefits without the fragmentation crisis.

Summary: Compaction

Key Takeaways

•Compaction consolidates free space by relocating files to eliminate fragmentation gaps.
•Costs are substantial — hours of I/O, system unavailability, SSD wear.
•Online compaction preserves availability but adds complexity.
•Prevention strategies can reduce but not eliminate fragmentation.
•Modern systems use hybrid approaches to avoid pure contiguous allocation's limitations.

Page Complete

You now understand compaction—the necessary but expensive remedy for external fragmentation. Next, we'll examine the scenarios where contiguous allocation remains the best choice despite these challenges.