Operating SystemsFile System Implementation

Contiguous Allocation

LevelIntermediate

Duration75 mins

TopicFile System Implementation

3 / 5

External Fragmentation

The Fragmentation Problem

Imagine a parking lot where cars must park in consecutive spaces. As cars come and go, gaps appear between parked vehicles. Eventually, you might have 10 empty spaces scattered across the lot, but no consecutive sequence of 5 spaces for a new truck. This is external fragmentation—free space exists but isn't contiguous, making it unusable for large allocations.

External fragmentation is the Achilles' heel of contiguous allocation. It's why this elegantly simple approach isn't used for general-purpose file systems despite its performance advantages.

What You Will Learn

By the end of this page, you'll understand how external fragmentation develops, its mathematical properties, how to measure fragmentation, and why it fundamentally limits contiguous allocation's applicability.

How Fragmentation Develops

External fragmentation emerges naturally from the create-delete cycle of file operations. Let's trace through a sequence that demonstrates the problem:

Initial State: Empty disk with 100 contiguous free blocks

Step 1: Create files A (10 blocks), B (20 blocks), C (15 blocks), D (25 blocks)

Used: 70 blocks | Free: 30 contiguous blocks

Step 2: Delete files B and D

Used: 25 blocks | Free: 75 blocks (but fragmented!)

Result: 75 blocks free, but largest contiguous region is only 30 blocks. A 50-block file cannot be created despite having 75 blocks free.

Converting Mermaid diagram...

Fragmentation Analysis
Metric	Value	Implication
Total Free Blocks	75	Appears to have plenty of space
Number of Free Regions	3	Space is scattered
Largest Contiguous Region	30	Maximum allocatable file size
Fragmentation Ratio	60%	1 - (30/75) = 0.60

Mathematical Analysis of Fragmentation

The 50% Rule (empirically observed by Knuth) states that for systems using contiguous allocation with First Fit:

After reaching steady state, approximately 1/3 of memory holes are lost to fragmentation. If there are n allocated segments, there will be approximately n/2 holes.

This means external fragmentation is inherent to contiguous allocation—it's not a bug but a mathematical consequence of the allocation pattern.

Fragmentation Metrics:

fragmentation_metrics.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
51
52
53
54
55
56
57
/*
 * Fragmentation Measurement and Analysis
 */
 
typedef struct {
    uint64_t total_free_blocks;      /* Sum of all free regions */
    uint64_t largest_free_extent;    /* Biggest contiguous region */
    uint32_t free_extent_count;      /* Number of free regions */
    double external_fragmentation;   /* Primary metric */
    double average_hole_size;        /* Avg size of free regions */
} fragmentation_metrics_t;
 
void calculate_metrics(disk_t *disk, fragmentation_metrics_t *m) {
    /* Scan disk to find all free extents */
    m->total_free_blocks = 0;
    m->largest_free_extent = 0;
    m->free_extent_count = 0;
    
    uint64_t current_extent = 0;
    for (uint64_t i = 0; i < disk->total_blocks; i++) {
        if (is_free(disk, i)) {
            current_extent++;
            m->total_free_blocks++;
        } else {
            if (current_extent > 0) {
                m->free_extent_count++;
                if (current_extent > m->largest_free_extent)
                    m->largest_free_extent = current_extent;
                current_extent = 0;
            }
        }
    }
    
    /* Handle trailing extent */
    if (current_extent > 0) {
        m->free_extent_count++;
        if (current_extent > m->largest_free_extent)
            m->largest_free_extent = current_extent;
    }
    
    /* Calculate metrics */
    if (m->total_free_blocks > 0) {
        /* External fragmentation: how much free space is unusable */
        m->external_fragmentation = 1.0 - 
            ((double)m->largest_free_extent / m->total_free_blocks);
        
        m->average_hole_size = 
            (double)m->total_free_blocks / m->free_extent_count;
    }
}
 
/*
 * Interpretation:
 * - external_fragmentation = 0.0: All free space is contiguous (optimal)
 * - external_fragmentation = 0.5: Half of free space is "trapped"
 * - external_fragmentation = 0.9: 90% of free space unusable for large files
 */

Factors Affecting Fragmentation Severity

Several factors influence how quickly and severely fragmentation develops:

Fragmentation Accelerators

•High file turnover — Frequent create/delete cycles fragment space faster than stable workloads.
•Variable file sizes — Mix of small and large files creates irregular hole patterns.
•Nearly full disk — Less room for reallocation, forcing tight packing that fragments quickly.
•Random deletion pattern — Deleting files from various locations scatters holes.
•Long-lived small files — Pin large regions, preventing consolidation.

Fragmentation Reducers

•Sequential deletion — Deleting files in creation order consolidates holes.
•Uniform file sizes — Similar-sized files create uniform holes that fit future allocations.
•Low disk utilization — More free space means more room for contiguous allocation.
•Write-once workloads — No deletions means no fragmentation growth.

Consequences of Fragmentation

External fragmentation creates serious operational problems:

Fragmentation Consequences
Problem	Description	Severity
Allocation Failure	Cannot create files despite free space	Critical
Space Waste	Free blocks trapped in unusable fragments	High
Allocation Time	Longer searches for suitable holes	Medium
User Confusion	"Disk full" with visible free space	High
System Instability	Critical operations may fail unexpectedly	Critical

The Usability Gap

Consider a disk with 50% free space but severe fragmentation. A user sees "50 GB free" but cannot create a 1 GB file. From the user's perspective, the system is broken. This UX disaster is why general-purpose file systems abandoned pure contiguous allocation.

Detection and Monitoring

Systems using contiguous allocation need fragmentation monitoring to trigger preventive action before allocation failures occur:

Key Metrics to Monitor:

Fragmentation Index: 1 - (largest_hole / total_free)
Hole Count Ratio: number_of_holes / number_of_files
Allocation Success Rate: successful_allocations / attempted_allocations
Average Search Length: blocks_scanned_per_allocation

fragmentation_monitor.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
/*
 * Fragmentation Monitoring Thresholds
 */
 
typedef enum {
    FRAG_HEALTHY,      /* < 20% fragmentation */
    FRAG_WARNING,      /* 20-50% fragmentation */
    FRAG_CRITICAL,     /* 50-80% fragmentation */
    FRAG_EMERGENCY     /* > 80% fragmentation */
} fragmentation_level_t;
 
fragmentation_level_t assess_fragmentation(double frag_ratio) {
    if (frag_ratio < 0.20) return FRAG_HEALTHY;
    if (frag_ratio < 0.50) return FRAG_WARNING;
    if (frag_ratio < 0.80) return FRAG_CRITICAL;
    return FRAG_EMERGENCY;
}
 
const char* recommended_action(fragmentation_level_t level) {
    switch (level) {
        case FRAG_HEALTHY:  return "No action needed";
        case FRAG_WARNING:  return "Schedule compaction";
        case FRAG_CRITICAL: return "Compact soon";
        case FRAG_EMERGENCY: return "Immediate compaction";
    }
}

Summary: External Fragmentation

Key Takeaways

•External fragmentation occurs when free space is scattered into non-contiguous regions.
•It's a mathematical inevitability with contiguous allocation under normal create/delete workloads.
•The 50% rule predicts significant fragmentation overhead at steady state.
•Fragmentation causes allocation failures even when total free space is sufficient.
•Monitoring is essential to detect fragmentation before it causes operational problems.

Page Complete

You now understand external fragmentation—its causes, measurement, and consequences. Next, we'll explore the solution: compaction, and why it's both necessary and expensive.

3 / 5

Loading learning content...

Operating SystemsFile System Implementation

Contiguous Allocation

LevelIntermediate

Duration75 mins

TopicFile System Implementation

3 / 5

External Fragmentation

The Fragmentation Problem

External fragmentation is the Achilles' heel of contiguous allocation. It's why this elegantly simple approach isn't used for general-purpose file systems despite its performance advantages.

What You Will Learn

How Fragmentation Develops

External fragmentation emerges naturally from the create-delete cycle of file operations. Let's trace through a sequence that demonstrates the problem:

Initial State: Empty disk with 100 contiguous free blocks

Step 1: Create files A (10 blocks), B (20 blocks), C (15 blocks), D (25 blocks)

Used: 70 blocks | Free: 30 contiguous blocks

Step 2: Delete files B and D

Used: 25 blocks | Free: 75 blocks (but fragmented!)

Result: 75 blocks free, but largest contiguous region is only 30 blocks. A 50-block file cannot be created despite having 75 blocks free.

Converting Mermaid diagram...

Fragmentation Analysis
Metric	Value	Implication
Total Free Blocks	75	Appears to have plenty of space
Number of Free Regions	3	Space is scattered
Largest Contiguous Region	30	Maximum allocatable file size
Fragmentation Ratio	60%	1 - (30/75) = 0.60

Mathematical Analysis of Fragmentation

The 50% Rule (empirically observed by Knuth) states that for systems using contiguous allocation with First Fit:

After reaching steady state, approximately 1/3 of memory holes are lost to fragmentation. If there are n allocated segments, there will be approximately n/2 holes.

This means external fragmentation is inherent to contiguous allocation—it's not a bug but a mathematical consequence of the allocation pattern.

Fragmentation Metrics:

fragmentation_metrics.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
51
52
53
54
55
56
57
/*
 * Fragmentation Measurement and Analysis
 */
 
typedef struct {
    uint64_t total_free_blocks;      /* Sum of all free regions */
    uint64_t largest_free_extent;    /* Biggest contiguous region */
    uint32_t free_extent_count;      /* Number of free regions */
    double external_fragmentation;   /* Primary metric */
    double average_hole_size;        /* Avg size of free regions */
} fragmentation_metrics_t;
 
void calculate_metrics(disk_t *disk, fragmentation_metrics_t *m) {
    /* Scan disk to find all free extents */
    m->total_free_blocks = 0;
    m->largest_free_extent = 0;
    m->free_extent_count = 0;
    
    uint64_t current_extent = 0;
    for (uint64_t i = 0; i < disk->total_blocks; i++) {
        if (is_free(disk, i)) {
            current_extent++;
            m->total_free_blocks++;
        } else {
            if (current_extent > 0) {
                m->free_extent_count++;
                if (current_extent > m->largest_free_extent)
                    m->largest_free_extent = current_extent;
                current_extent = 0;
            }
        }
    }
    
    /* Handle trailing extent */
    if (current_extent > 0) {
        m->free_extent_count++;
        if (current_extent > m->largest_free_extent)
            m->largest_free_extent = current_extent;
    }
    
    /* Calculate metrics */
    if (m->total_free_blocks > 0) {
        /* External fragmentation: how much free space is unusable */
        m->external_fragmentation = 1.0 - 
            ((double)m->largest_free_extent / m->total_free_blocks);
        
        m->average_hole_size = 
            (double)m->total_free_blocks / m->free_extent_count;
    }
}
 
/*
 * Interpretation:
 * - external_fragmentation = 0.0: All free space is contiguous (optimal)
 * - external_fragmentation = 0.5: Half of free space is "trapped"
 * - external_fragmentation = 0.9: 90% of free space unusable for large files
 */

Factors Affecting Fragmentation Severity

Several factors influence how quickly and severely fragmentation develops:

Fragmentation Accelerators

•High file turnover — Frequent create/delete cycles fragment space faster than stable workloads.
•Variable file sizes — Mix of small and large files creates irregular hole patterns.
•Nearly full disk — Less room for reallocation, forcing tight packing that fragments quickly.
•Random deletion pattern — Deleting files from various locations scatters holes.
•Long-lived small files — Pin large regions, preventing consolidation.

Fragmentation Reducers

•Sequential deletion — Deleting files in creation order consolidates holes.
•Uniform file sizes — Similar-sized files create uniform holes that fit future allocations.
•Low disk utilization — More free space means more room for contiguous allocation.
•Write-once workloads — No deletions means no fragmentation growth.

Consequences of Fragmentation

External fragmentation creates serious operational problems:

Fragmentation Consequences
Problem	Description	Severity
Allocation Failure	Cannot create files despite free space	Critical
Space Waste	Free blocks trapped in unusable fragments	High
Allocation Time	Longer searches for suitable holes	Medium
User Confusion	"Disk full" with visible free space	High
System Instability	Critical operations may fail unexpectedly	Critical

The Usability Gap

Detection and Monitoring

Systems using contiguous allocation need fragmentation monitoring to trigger preventive action before allocation failures occur:

Key Metrics to Monitor:

Fragmentation Index: 1 - (largest_hole / total_free)
Hole Count Ratio: number_of_holes / number_of_files
Allocation Success Rate: successful_allocations / attempted_allocations
Average Search Length: blocks_scanned_per_allocation

fragmentation_monitor.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
/*
 * Fragmentation Monitoring Thresholds
 */
 
typedef enum {
    FRAG_HEALTHY,      /* < 20% fragmentation */
    FRAG_WARNING,      /* 20-50% fragmentation */
    FRAG_CRITICAL,     /* 50-80% fragmentation */
    FRAG_EMERGENCY     /* > 80% fragmentation */
} fragmentation_level_t;
 
fragmentation_level_t assess_fragmentation(double frag_ratio) {
    if (frag_ratio < 0.20) return FRAG_HEALTHY;
    if (frag_ratio < 0.50) return FRAG_WARNING;
    if (frag_ratio < 0.80) return FRAG_CRITICAL;
    return FRAG_EMERGENCY;
}
 
const char* recommended_action(fragmentation_level_t level) {
    switch (level) {
        case FRAG_HEALTHY:  return "No action needed";
        case FRAG_WARNING:  return "Schedule compaction";
        case FRAG_CRITICAL: return "Compact soon";
        case FRAG_EMERGENCY: return "Immediate compaction";
    }
}

Summary: External Fragmentation

Key Takeaways

•External fragmentation occurs when free space is scattered into non-contiguous regions.
•It's a mathematical inevitability with contiguous allocation under normal create/delete workloads.
•The 50% rule predicts significant fragmentation overhead at steady state.
•Fragmentation causes allocation failures even when total free space is sufficient.
•Monitoring is essential to detect fragmentation before it causes operational problems.

Page Complete

You now understand external fragmentation—its causes, measurement, and consequences. Next, we'll explore the solution: compaction, and why it's both necessary and expensive.

3 / 5

Contiguous Allocation - Page 3 of 5 | OneNoughtOne