Fragmentation - Learning Module

Loading content...

0/240

External Fragmentation

The Puzzle of Scattered Free Space

Imagine a parking lot with 100 spaces. Fifty cars are parked, scattered throughout the lot, leaving 50 empty spaces. A tour bus needing 20 contiguous spaces arrives—but the 50 empty spaces are dispersed in groups of 3, 5, 7, and smaller clusters. Despite having 50% vacancy, the bus cannot park. This is external fragmentation.

In memory management, external fragmentation occurs when free memory is distributed in non-contiguous holes throughout the address space. The system may have plenty of total free memory, but no single contiguous region large enough to satisfy a request. The memory is free, it's just in the wrong places.

External fragmentation is the defining challenge of variable-partition memory allocation. Unlike internal fragmentation (waste within allocations), external fragmentation represents waste in the free pool—memory that exists but cannot be used. Understanding and managing external fragmentation is essential for any system that allocates variable-sized memory regions.

What You Will Learn

By the end of this page, you will understand external fragmentation's causes and mechanics, why it's inevitable in variable-partition systems, how to measure and quantify fragmentation severity, and strategies including compaction and allocation algorithms that combat its effects.

Defining External Fragmentation

External fragmentation occurs when the total free memory is sufficient to satisfy a memory request, but no single contiguous block is large enough. Free memory exists external to allocated regions—in the gaps between them—but is fragmented into unusable pieces.

Formal Definition:

External Fragmentation exists when: Σ(Free Blocks) ≥ Request Size but Max(Free Block Size) < Request Size

In other words:

Total free memory ≥ what's needed
But the largest available hole < what's needed

The memory request fails despite adequate total resources.

Converting Mermaid diagram...

Why 'External'?

The fragmentation is external because the wasted space lies outside of any allocation—in the free list, between allocated regions. Contrast this with internal fragmentation, where waste is inside allocations.

The Fundamental Problem:

External fragmentation is intrinsic to variable-partition allocation. When processes of different sizes arrive and depart in unpredictable order:

Each departure creates a hole of specific size
New arrivals may not exactly fill existing holes
Remaining fragments create smaller holes
Over time, memory becomes a checkerboard of small, unusable holes

Unlike internal fragmentation (bounded by partition/page size), external fragmentation can grow unboundedly. In pathological cases, a system could fail to allocate 1MB despite having 100MB free—if that 100MB is scattered across thousands of tiny holes.

The Irony of External Fragmentation

External fragmentation is a consequence of good allocation—matching process sizes exactly. Systems that avoid internal fragmentation (through exact-fit allocation) inevitably suffer external fragmentation. Systems that avoid external fragmentation (through fixed-size allocation) inevitably suffer internal fragmentation. This trade-off is fundamental.

How External Fragmentation Develops

External fragmentation accumulates through the natural lifecycle of memory allocation. Let's trace how a pristine memory space degrades into fragmented chaos:

Evolution of External Fragmentation
Step	Action	Memory State	Holes	Largest Hole
1	Initial state	100 KB free	1 hole: 100 KB	100 KB
2	Allocate P1 (30 KB)	P1(30) + 70 free	1 hole: 70 KB	70 KB
3	Allocate P2 (20 KB)	P1(30) + P2(20) + 50 free	1 hole: 50 KB	50 KB
4	Allocate P3 (25 KB)	P1 + P2 + P3(25) + 25 free	1 hole: 25 KB	25 KB
5	Free P2	P1 + [20 free] + P3 + 25 free	2 holes: 20+25 KB	25 KB
6	Allocate P4 (15 KB)	P1 + P4(15) + [5 free] + P3 + 25 free	2 holes: 5+25 KB	25 KB
7	Free P1	[30 free] + P4 + [5 free] + P3 + 25 free	3 holes: 30+5+25 KB	30 KB
8	Allocate P5 (28 KB)	P5(28) + [2 free] + P4 + [5 free] + P3 + 25 free	3 holes: 2+5+25 KB	25 KB

After step 8, we have 32 KB free total, but cannot allocate 26 KB because our largest hole is only 25 KB. This is external fragmentation in action.

Key Observations:

Hole Creation: Every process termination creates a hole equal to its size
Hole Splitting: Allocations that don't exactly fill holes create smaller leftover holes
Hole Multiplication: Over time, one large hole becomes many small holes
Hole Coalescing: Adjacent holes can merge when neighbors depart, but this requires luck

The Fragmentation Ratchet:

With typical workloads, fragmentation tends to worsen over time:

Processes arrive and depart asynchronously
Exact-fit arrivals for existing holes are rare
Holes fragment faster than they coalesce
Available memory becomes increasingly unusable

Without intervention (compaction, special allocation strategies), external fragmentation approaches a steady-state that wastes substantial memory.

The Fragmentation Death Spiral

In severe fragmentation, small allocations succeed (filling tiny holes), but large allocations fail. This biases the remaining holes toward being even smaller. The system can reach a state where significant memory is free but only tiny allocations can succeed—a self-reinforcing spiral.

Visualization and Mechanics

Understanding external fragmentation requires visualizing how memory looks after extended operation. Let's examine the structure of fragmented memory in detail.

memory_fragmentation_simulation.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
 
#define MEMORY_SIZE 1024  // 1024 units of memory
#define MAX_PROCESSES 100
 
typedef struct {
    int start;
    int size;
    bool allocated;
    int process_id;
} MemoryBlock;
 
typedef struct {
    MemoryBlock blocks[MAX_PROCESSES * 2];
    int block_count;
    int total_memory;
} MemoryManager;
 
void init_memory(MemoryManager* mm) {
    mm->block_count = 1;
    mm->total_memory = MEMORY_SIZE;
    mm->blocks[0] = (MemoryBlock){0, MEMORY_SIZE, false, -1};
}
 
// Visualize current memory state
void visualize_memory(MemoryManager* mm) {
    printf("
|");
    for (int i = 0; i < mm->block_count; i++) {
        char fill = mm->blocks[i].allocated ? '#' : '.';
        int display_size = mm->blocks[i].size / 16;  // Scale down
        if (display_size < 1) display_size = 1;
        for (int j = 0; j < display_size; j++) {
            printf("%c", fill);
        }
        printf("|");
    }
    printf("
");
}
 
// Calculate fragmentation statistics
void analyze_fragmentation(MemoryManager* mm) {
    int total_free = 0;
    int hole_count = 0;
    int largest_hole = 0;
    int smallest_hole = MEMORY_SIZE;
    
    for (int i = 0; i < mm->block_count; i++) {
        if (!mm->blocks[i].allocated) {
            total_free += mm->blocks[i].size;
            hole_count++;
            if (mm->blocks[i].size > largest_hole) 
                largest_hole = mm->blocks[i].size;
            if (mm->blocks[i].size < smallest_hole) 
                smallest_hole = mm->blocks[i].size;
        }
    }
    
    printf("
Fragmentation Analysis:
");
    printf("  Total Free Memory: %d units
", total_free);
    printf("  Number of Holes: %d
", hole_count);
    printf("  Largest Hole: %d units
", largest_hole);
    printf("  Smallest Hole: %d units
", 
           hole_count > 0 ? smallest_hole : 0);
    printf("  Average Hole Size: %.1f units
", 
           hole_count > 0 ? (float)total_free / hole_count : 0);
    
    // Calculate external fragmentation ratio
    if (total_free > 0) {
        float frag_ratio = 1.0 - (float)largest_hole / total_free;
        printf("  External Fragmentation Ratio: %.2f%%
", 
               frag_ratio * 100);
        printf("  (Unusable free memory due to fragmentation)
");
    }
}
 
// First-fit allocation
bool allocate_first_fit(MemoryManager* mm, int size, int pid) {
    for (int i = 0; i < mm->block_count; i++) {
        if (!mm->blocks[i].allocated && mm->blocks[i].size >= size) {
            // Split block if necessary
            if (mm->blocks[i].size > size) {
                // Shift blocks to make room for new one
                for (int j = mm->block_count; j > i + 1; j--) {
                    mm->blocks[j] = mm->blocks[j-1];
                }
                mm->block_count++;
                
                // Create new hole after allocation
                mm->blocks[i+1] = (MemoryBlock){
                    mm->blocks[i].start + size,
                    mm->blocks[i].size - size,
                    false,
                    -1
                };
                mm->blocks[i].size = size;
            }
            mm->blocks[i].allocated = true;
            mm->blocks[i].process_id = pid;
            return true;
        }
    }
    return false;  // Allocation failed
}
 
// Free memory and coalesce adjacent holes
void free_memory(MemoryManager* mm, int pid) {
    for (int i = 0; i < mm->block_count; i++) {
        if (mm->blocks[i].process_id == pid) {
            mm->blocks[i].allocated = false;
            mm->blocks[i].process_id = -1;
            
            // Coalesce with next block if also free
            if (i + 1 < mm->block_count && !mm->blocks[i+1].allocated) {
                mm->blocks[i].size += mm->blocks[i+1].size;
                // Shift blocks down
                for (int j = i + 1; j < mm->block_count - 1; j++) {
                    mm->blocks[j] = mm->blocks[j+1];
                }
                mm->block_count--;
            }
            
            // Coalesce with previous block if also free
            if (i > 0 && !mm->blocks[i-1].allocated) {
                mm->blocks[i-1].size += mm->blocks[i].size;
                // Shift blocks down
                for (int j = i; j < mm->block_count - 1; j++) {
                    mm->blocks[j] = mm->blocks[j+1];
                }
                mm->block_count--;
            }
            break;
        }
    }
}
 
int main() {
    MemoryManager mm;
    init_memory(&mm);
    
    printf("=== External Fragmentation Demonstration ===
");
    printf("Memory Size: %d units
", MEMORY_SIZE);
    printf("Legend: # = allocated, . = free
");
    
    // Simulate allocations
    printf("
Initial state:");
    visualize_memory(&mm);
    
    allocate_first_fit(&mm, 200, 1);
    allocate_first_fit(&mm, 150, 2);
    allocate_first_fit(&mm, 100, 3);
    allocate_first_fit(&mm, 180, 4);
    allocate_first_fit(&mm, 120, 5);
    printf("After allocating P1(200), P2(150), P3(100), P4(180), P5(120):");
    visualize_memory(&mm);
    
    // Deallocate some processes (creating holes)
    free_memory(&mm, 2);  // Free P2 (150 units)
    free_memory(&mm, 4);  // Free P4 (180 units)
    printf("After freeing P2 and P4:");
    visualize_memory(&mm);
    
    // Try to allocate something that doesn't fit any single hole
    bool success = allocate_first_fit(&mm, 250, 6);
    printf("Attempt to allocate P6(250): %s", 
           success ? "SUCCESS" : "FAILED");
    visualize_memory(&mm);
    
    analyze_fragmentation(&mm);
    
    // Continue fragmentation
    allocate_first_fit(&mm, 80, 7);
    allocate_first_fit(&mm, 50, 8);
    free_memory(&mm, 3);
    free_memory(&mm, 5);
    allocate_first_fit(&mm, 60, 9);
    
    printf("
After more operations:");
    visualize_memory(&mm);
    analyze_fragmentation(&mm);
    
    return 0;
}

The Checkerboard Effect:

After extended operation, memory resembles a checkerboard:

|####|..|#####|...|##|.|#######|....|###|..|#|

Each . segment is a free hole; each # segment is an allocated region. The holes are:

Scattered unpredictably
Of varying sizes
Usually smaller than what's needed
Collectively substantial but individually insufficient

Coalescing:

When adjacent allocated regions both become free, their holes merge:

Before: |###|...|###|    (two 3-unit holes)
After P2 frees: |...|...|###|  → |......|###|  (one 6-unit hole)

Automatic coalescing helps slow fragmentation but cannot eliminate it when non-adjacent regions free.

Implementation Detail: Coalescing

Proper memory allocators always coalesce adjacent free blocks during deallocation. This requires maintaining metadata (size, allocation status) for each block, typically in a header preceding the data area. Without coalescing, fragmentation accelerates dramatically.

Measuring External Fragmentation

Quantifying external fragmentation helps assess system health and make allocation policy decisions. Several metrics capture different aspects of fragmentation:

1. Basic Fragmentation Ratio:

Fragmentation Ratio = 1 - (Largest Free Block / Total Free Memory)

Ranges from 0 (no fragmentation—one contiguous hole) to approaching 1 (severe fragmentation)
A ratio of 0.5 means the largest hole contains only half the free memory
A ratio of 0.9 means 90% of free memory is scattered in smaller holes

2. Fragmentation Index (Alternative):

Fragmentation Index = 1 - (Largest Allocatable Size / Total Free Memory)

This is more practical—it measures what can actually be allocated versus total free.

3. Hole Count and Distribution:

Number of holes
Mean, median, standard deviation of hole sizes
Size distribution (histogram of hole sizes)

Fragmentation Severity Interpretation
Fragmentation Ratio	Interpretation	Likely Symptoms	Recommended Action
0.00 - 0.20	Minimal	System healthy, large allocations succeed	Normal operation
0.20 - 0.40	Low	Occasional large allocation delays	Monitor, consider preventive compaction
0.40 - 0.60	Moderate	Large allocations may fail, system slowing	Schedule compaction, review allocation patterns
0.60 - 0.80	High	Significant requests failing, memory under-utilized	Compaction needed, consider algorithm change
0.80 - 1.00	Severe	Most allocations fail despite free memory	Immediate compaction, system redesign needed

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct {
    size_t* hole_sizes;
    size_t hole_count;
    size_t total_memory;
    size_t allocated_memory;
} MemoryState;
 
typedef struct {
    double basic_ratio;
    double fragmentation_index;
    size_t largest_hole;
    size_t smallest_hole;
    double average_hole;
    double std_deviation;
    size_t hole_count;
    size_t total_free;
    double usable_percent;  // Percent of free memory actually usable
} FragmentationMetrics;
 
FragmentationMetrics analyze_fragmentation(MemoryState* state) {
    FragmentationMetrics m = {0};
    
    if (state->hole_count == 0) {
        m.fragmentation_index = 0;  // All memory allocated (or none)
        return m;
    }
    
    // Basic statistics
    m.hole_count = state->hole_count;
    m.total_free = 0;
    m.largest_hole = 0;
    m.smallest_hole = (size_t)-1;
    
    for (size_t i = 0; i < state->hole_count; i++) {
        size_t hole = state->hole_sizes[i];
        m.total_free += hole;
        if (hole > m.largest_hole) m.largest_hole = hole;
        if (hole < m.smallest_hole) m.smallest_hole = hole;
    }
    
    m.average_hole = (double)m.total_free / m.hole_count;
    
    // Standard deviation
    double variance = 0;
    for (size_t i = 0; i < state->hole_count; i++) {
        double diff = state->hole_sizes[i] - m.average_hole;
        variance += diff * diff;
    }
    m.std_deviation = sqrt(variance / m.hole_count);
    
    // Fragmentation ratios
    m.basic_ratio = 1.0 - ((double)m.largest_hole / m.total_free);
    m.fragmentation_index = m.basic_ratio;  // Same for external frag
    
    // Usable percentage (how much can we actually allocate?)
    // This depends on request distribution, but largest hole is key
    m.usable_percent = 100.0 * m.largest_hole / m.total_free;
    
    return m;
}
 
void print_metrics(FragmentationMetrics* m) {
    printf("
=== External Fragmentation Metrics ===
");
    printf("Total Free Memory: %zu bytes
", m->total_free);
    printf("Number of Holes: %zu
", m->hole_count);
    printf("Largest Hole: %zu bytes
", m->largest_hole);
    printf("Smallest Hole: %zu bytes
", m->smallest_hole);
    printf("Average Hole: %.1f bytes
", m->average_hole);
    printf("Std Deviation: %.1f bytes
", m->std_deviation);
    printf("
Fragmentation Ratio: %.2f (%.0f%%)
", 
           m->basic_ratio, m->basic_ratio * 100);
    printf("Usable Free Memory: %.1f%%
", m->usable_percent);
    printf("Wasted (Fragmented): %.1f%%
", 100 - m->usable_percent);
    
    // Severity assessment
    printf("
Severity: ");
    if (m->basic_ratio < 0.2) printf("MINIMAL - System healthy
");
    else if (m->basic_ratio < 0.4) printf("LOW - Monitor situation
");
    else if (m->basic_ratio < 0.6) printf("MODERATE - Consider compaction
");
    else if (m->basic_ratio < 0.8) printf("HIGH - Compaction recommended
");
    else printf("SEVERE - Immediate action required
");
}
 
int main() {
    // Example: A fragmented memory system
    size_t holes[] = {150, 32, 85, 12, 200, 45, 8, 18};
    size_t num_holes = sizeof(holes) / sizeof(holes[0]);
    
    MemoryState state = {
        .hole_sizes = holes,
        .hole_count = num_holes,
        .total_memory = 2048,
        .allocated_memory = 1498  // 2048 - sum(holes)
    };
    
    printf("Memory Configuration:
");
    printf("Total Memory: %zu bytes
", state.total_memory);
    printf("Allocated: %zu bytes
", state.allocated_memory);
    printf("Holes: ");
    for (size_t i = 0; i < num_holes; i++) {
        printf("%zu ", holes[i]);
    }
    printf("
");
    
    FragmentationMetrics m = analyze_fragmentation(&state);
    print_metrics(&m);
    
    // Demonstrate what allocations would succeed/fail
    printf("
=== Allocation Feasibility ===
");
    size_t test_sizes[] = {50, 100, 150, 200, 250, 300};
    for (size_t i = 0; i < sizeof(test_sizes)/sizeof(test_sizes[0]); i++) {
        printf("Request %zu bytes: %s
", test_sizes[i],
               test_sizes[i] <= m.largest_hole ? "POSSIBLE" : "BLOCKED by fragmentation");
    }
    
    return 0;
}

Real-World Monitoring

Production systems monitor fragmentation continuously. Linux exposes fragmentation info through /proc/buddyinfo and /proc/pagetypeinfo. Database systems track page fragmentation percentages. When thresholds are crossed, automated compaction or defragmentation triggers.

Causes and Contributing Factors

External fragmentation emerges from fundamental characteristics of dynamic memory allocation. Understanding the causes helps design systems that minimize fragmentation.

Root Causes of External Fragmentation

•Variable Request Sizes: When allocation requests vary in size, released memory rarely matches subsequent requests, leaving remnants.
•Non-Sequential Deallocation: Processes terminate in different orders than they started. The 'holes' created don't form contiguous regions.
•Request/Hole Size Mismatch: An allocation that's smaller than an available hole splits that hole. The remnant may be too small for practical use.
•Long-Lived Allocations: Persistent allocations 'pin' memory regions, preventing adjacent holes from coalescing across them.
•Allocation Pattern Variability: Workloads with high variance in allocation sizes fragment faster than those with consistent sizes.

Patterns That Worsen Fragmentation

•Highly variable allocation sizes
•Long-lived allocations interleaved with short-lived ones
•LIFO (stack-like) deallocation patterns
•Allocations that fragment large holes into unusable pieces
•Workloads with extreme size outliers

Patterns That Minimize Fragmentation

•Uniform allocation sizes (best case)
•FIFO deallocation (oldest freed first)
•Grouping similar-sized allocations together
•Short-lived allocations from one pool, long-lived from another
•Periodic full compaction/restart opportunities

The Entropy Analogy:

External fragmentation resembles entropy in thermodynamics:

Initial state: Low entropy (organized, contiguous memory)
Over time: Entropy increases (memory becomes disordered, fragmented)
Second law: Fragmentation naturally increases without energy input
Reducing entropy: Requires work (compaction, reorganization)

Just as heat naturally disperses and never spontaneously reconcentrates, memory holes naturally scatter and rarely spontaneously merge into large contiguous regions. Compaction is the 'work' required to fight memory entropy.

Real-World Fragmentation Rates

Studies of real workloads show that fragmentation typically stabilizes at 20-50% of free memory being unusable under steady-state conditions. Pathological workloads (e.g., many small allocations interspersed with occasional large ones) can push this above 80%.

Solutions and Mitigation Strategies

Several strategies address external fragmentation, each with distinct trade-offs:

External Fragmentation Mitigation Strategies
Strategy	Description	Pros	Cons
Compaction	Move allocations to collect free space into one contiguous hole	Eliminates fragmentation completely	Expensive (CPU, I/O), requires relocatable addresses
Paging	Divide memory into fixed-size pages; any page can satisfy any request	Eliminates external fragmentation entirely	Introduces internal fragmentation, page table overhead
Best-Fit Allocation	Choose the smallest hole that fits, minimizing leftover fragments	Reduces remnant sizes	May create many tiny unusable holes
Buddy System	Allocate in power-of-2 blocks; easy merging of adjacent buddies	Efficient coalescing, limited fragmentation	High internal fragmentation (power-of-2 rounding)
Pool Allocation	Separate pools for different size classes	Excellent for known patterns	Complex management, may waste memory if pools imbalanced
Slab Allocation	Pre-allocate object caches for common sizes	Near-zero fragmentation for cached objects	Only works for known, repeated allocations

Compaction in Detail:

Compaction physically moves allocated regions to consolidate free space. This is conceptually simple but operationally complex:

Compaction Algorithm:

Find all allocated regions
Calculate new positions (packed contiguously)
Move each region to its new position
Update all pointers/references to reflect new addresses

Requirements:

Relocatable code (position-independent)
All references must be updatable (registers, pointers)
Must pause execution during compaction (stop-the-world)
Or: use indirection (handles) allowing moves without updating user pointers

Converting Mermaid diagram...

Why Paging Solves External Fragmentation:

Paging divides both physical memory (into frames) and virtual memory (into pages) into equal-sized units. Because every frame is interchangeable:

Any free frame can satisfy any page request
No holes are 'too small'—either you have a free frame or you don't
Multiple free frames can serve one allocation (non-contiguous physical allocation)
External fragmentation becomes impossible by definition

This is why paging became the dominant memory management technique. The cost (internal fragmentation in the last page) is bounded and predictable, unlike external fragmentation which can grow arbitrarily.

Modern OS Approach

Modern operating systems use paging for process memory (avoiding external fragmentation there) but still face external fragmentation in kernel memory allocators. The Linux kernel uses the buddy system combined with slab allocators to manage this—a hybrid approach that handles both large and small allocations efficiently.

External vs. Internal Fragmentation

Understanding the relationship between external and internal fragmentation is crucial for memory system design. They represent different manifestations of allocation inefficiency and often trade off against each other.

Comparison: External vs. Internal Fragmentation
Aspect	External Fragmentation	Internal Fragmentation
Location of Waste	Between allocations (in free pool)	Within allocations (in allocated blocks)
Cause	Variable-sized allocations leave holes	Fixed-size blocks exceed actual need
Visibility	Free memory exists but unusable	Allocated memory partially unused
Measurement	1 - (largest_hole / total_free)	(allocated - used) / allocated
Boundedness	Unbounded (can approach 100%)	Bounded by allocation unit size
Recovery	Compaction or clever allocation	Cannot recover without reallocation
Allocation Scheme	Variable partitions, segments	Fixed partitions, paging
Eliminated By	Paging (fixed-size allocation)	Perfect-fit allocation

The Fundamental Trade-Off:

Variable-Size Allocation:
  ✓ Zero internal fragmentation (exact fit)
  ✗ External fragmentation accumulates
  
Fixed-Size Allocation:
  ✓ Zero external fragmentation (any slot works)
  ✗ Internal fragmentation inevitable

Why This Trade-Off Exists:

With variable-sized allocation:

Each allocation gets exactly what it needs (no internal waste)
But holes left by deallocations don't match new requests (external waste)

With fixed-sized allocation:

Every hole is the same size, so any hole fits any request (no external waste)
But most requests don't perfectly match the fixed size (internal waste)

The Paging Compromise:

Paging represents the industry's answer to this dilemma:

Accept bounded internal fragmentation (up to one page per allocation)
Completely eliminate external fragmentation
The bounded internal fragmentation is deemed acceptable given paging's other benefits (protection, virtual memory, simplicity)

You Can't Have Both

No allocation scheme eliminates both internal and external fragmentation. Attempts to minimize one typically increase the other. The art of memory management is choosing which fragmentation type is acceptable for your workload and constraints.

Summary: External Fragmentation

We've explored the mechanics, measurement, and mitigation of external fragmentation. Let's consolidate the key insights:

Key Takeaways

•Definition: External fragmentation occurs when free memory is scattered in non-contiguous holes, making large allocations impossible despite sufficient total free memory.
•Cause: Variable-sized allocations and non-sequential deallocations naturally fragment the free pool over time.
•Measurement: The fragmentation ratio (1 - largest_hole/total_free) quantifies severity; values above 0.5 indicate significant problems.
•Unbounded Growth: Unlike internal fragmentation, external fragmentation can grow arbitrarily, potentially rendering most free memory unusable.
•Solutions: Compaction (expensive), paging (eliminates), buddy system (limits), slab allocation (for fixed sizes).
•Trade-Off: External and internal fragmentation trade off—reducing one typically increases the other. Paging's fixed-size approach chooses bounded internal fragmentation over unbounded external fragmentation.

What's Next:

Having understood both internal and external fragmentation, we now examine a classic result that quantifies expected fragmentation: the 50-percent rule. This empirical observation provides insight into how much memory is wasted under typical allocation patterns and helps explain why fragmentation is an inevitable cost of dynamic memory management.

Page Complete

You now understand external fragmentation—the challenge of scattered free memory that plagues variable-partition systems. This knowledge explains why paging became dominant despite its internal fragmentation cost, and why systems needing variable-sized allocations must employ sophisticated strategies to remain usable.

External Fragmentation

The Puzzle of Scattered Free Space

What You Will Learn

Defining External Fragmentation

Formal Definition:

External Fragmentation exists when: Σ(Free Blocks) ≥ Request Size but Max(Free Block Size) < Request Size

In other words:

Total free memory ≥ what's needed
But the largest available hole < what's needed

The memory request fails despite adequate total resources.

Converting Mermaid diagram...

Why 'External'?

The Fundamental Problem:

External fragmentation is intrinsic to variable-partition allocation. When processes of different sizes arrive and depart in unpredictable order:

Each departure creates a hole of specific size
New arrivals may not exactly fill existing holes
Remaining fragments create smaller holes
Over time, memory becomes a checkerboard of small, unusable holes

The Irony of External Fragmentation

How External Fragmentation Develops

External fragmentation accumulates through the natural lifecycle of memory allocation. Let's trace how a pristine memory space degrades into fragmented chaos:

Evolution of External Fragmentation
Step	Action	Memory State	Holes	Largest Hole
1	Initial state	100 KB free	1 hole: 100 KB	100 KB
2	Allocate P1 (30 KB)	P1(30) + 70 free	1 hole: 70 KB	70 KB
3	Allocate P2 (20 KB)	P1(30) + P2(20) + 50 free	1 hole: 50 KB	50 KB
4	Allocate P3 (25 KB)	P1 + P2 + P3(25) + 25 free	1 hole: 25 KB	25 KB
5	Free P2	P1 + [20 free] + P3 + 25 free	2 holes: 20+25 KB	25 KB
6	Allocate P4 (15 KB)	P1 + P4(15) + [5 free] + P3 + 25 free	2 holes: 5+25 KB	25 KB
7	Free P1	[30 free] + P4 + [5 free] + P3 + 25 free	3 holes: 30+5+25 KB	30 KB
8	Allocate P5 (28 KB)	P5(28) + [2 free] + P4 + [5 free] + P3 + 25 free	3 holes: 2+5+25 KB	25 KB

After step 8, we have 32 KB free total, but cannot allocate 26 KB because our largest hole is only 25 KB. This is external fragmentation in action.

Key Observations:

Hole Creation: Every process termination creates a hole equal to its size
Hole Splitting: Allocations that don't exactly fill holes create smaller leftover holes
Hole Multiplication: Over time, one large hole becomes many small holes
Hole Coalescing: Adjacent holes can merge when neighbors depart, but this requires luck

The Fragmentation Ratchet:

With typical workloads, fragmentation tends to worsen over time:

Processes arrive and depart asynchronously
Exact-fit arrivals for existing holes are rare
Holes fragment faster than they coalesce
Available memory becomes increasingly unusable

Without intervention (compaction, special allocation strategies), external fragmentation approaches a steady-state that wastes substantial memory.

The Fragmentation Death Spiral

Visualization and Mechanics

Understanding external fragmentation requires visualizing how memory looks after extended operation. Let's examine the structure of fragmented memory in detail.

memory_fragmentation_simulation.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
 
#define MEMORY_SIZE 1024  // 1024 units of memory
#define MAX_PROCESSES 100
 
typedef struct {
    int start;
    int size;
    bool allocated;
    int process_id;
} MemoryBlock;
 
typedef struct {
    MemoryBlock blocks[MAX_PROCESSES * 2];
    int block_count;
    int total_memory;
} MemoryManager;
 
void init_memory(MemoryManager* mm) {
    mm->block_count = 1;
    mm->total_memory = MEMORY_SIZE;
    mm->blocks[0] = (MemoryBlock){0, MEMORY_SIZE, false, -1};
}
 
// Visualize current memory state
void visualize_memory(MemoryManager* mm) {
    printf("
|");
    for (int i = 0; i < mm->block_count; i++) {
        char fill = mm->blocks[i].allocated ? '#' : '.';
        int display_size = mm->blocks[i].size / 16;  // Scale down
        if (display_size < 1) display_size = 1;
        for (int j = 0; j < display_size; j++) {
            printf("%c", fill);
        }
        printf("|");
    }
    printf("
");
}
 
// Calculate fragmentation statistics
void analyze_fragmentation(MemoryManager* mm) {
    int total_free = 0;
    int hole_count = 0;
    int largest_hole = 0;
    int smallest_hole = MEMORY_SIZE;
    
    for (int i = 0; i < mm->block_count; i++) {
        if (!mm->blocks[i].allocated) {
            total_free += mm->blocks[i].size;
            hole_count++;
            if (mm->blocks[i].size > largest_hole) 
                largest_hole = mm->blocks[i].size;
            if (mm->blocks[i].size < smallest_hole) 
                smallest_hole = mm->blocks[i].size;
        }
    }
    
    printf("
Fragmentation Analysis:
");
    printf("  Total Free Memory: %d units
", total_free);
    printf("  Number of Holes: %d
", hole_count);
    printf("  Largest Hole: %d units
", largest_hole);
    printf("  Smallest Hole: %d units
", 
           hole_count > 0 ? smallest_hole : 0);
    printf("  Average Hole Size: %.1f units
", 
           hole_count > 0 ? (float)total_free / hole_count : 0);
    
    // Calculate external fragmentation ratio
    if (total_free > 0) {
        float frag_ratio = 1.0 - (float)largest_hole / total_free;
        printf("  External Fragmentation Ratio: %.2f%%
", 
               frag_ratio * 100);
        printf("  (Unusable free memory due to fragmentation)
");
    }
}
 
// First-fit allocation
bool allocate_first_fit(MemoryManager* mm, int size, int pid) {
    for (int i = 0; i < mm->block_count; i++) {
        if (!mm->blocks[i].allocated && mm->blocks[i].size >= size) {
            // Split block if necessary
            if (mm->blocks[i].size > size) {
                // Shift blocks to make room for new one
                for (int j = mm->block_count; j > i + 1; j--) {
                    mm->blocks[j] = mm->blocks[j-1];
                }
                mm->block_count++;
                
                // Create new hole after allocation
                mm->blocks[i+1] = (MemoryBlock){
                    mm->blocks[i].start + size,
                    mm->blocks[i].size - size,
                    false,
                    -1
                };
                mm->blocks[i].size = size;
            }
            mm->blocks[i].allocated = true;
            mm->blocks[i].process_id = pid;
            return true;
        }
    }
    return false;  // Allocation failed
}
 
// Free memory and coalesce adjacent holes
void free_memory(MemoryManager* mm, int pid) {
    for (int i = 0; i < mm->block_count; i++) {
        if (mm->blocks[i].process_id == pid) {
            mm->blocks[i].allocated = false;
            mm->blocks[i].process_id = -1;
            
            // Coalesce with next block if also free
            if (i + 1 < mm->block_count && !mm->blocks[i+1].allocated) {
                mm->blocks[i].size += mm->blocks[i+1].size;
                // Shift blocks down
                for (int j = i + 1; j < mm->block_count - 1; j++) {
                    mm->blocks[j] = mm->blocks[j+1];
                }
                mm->block_count--;
            }
            
            // Coalesce with previous block if also free
            if (i > 0 && !mm->blocks[i-1].allocated) {
                mm->blocks[i-1].size += mm->blocks[i].size;
                // Shift blocks down
                for (int j = i; j < mm->block_count - 1; j++) {
                    mm->blocks[j] = mm->blocks[j+1];
                }
                mm->block_count--;
            }
            break;
        }
    }
}
 
int main() {
    MemoryManager mm;
    init_memory(&mm);
    
    printf("=== External Fragmentation Demonstration ===
");
    printf("Memory Size: %d units
", MEMORY_SIZE);
    printf("Legend: # = allocated, . = free
");
    
    // Simulate allocations
    printf("
Initial state:");
    visualize_memory(&mm);
    
    allocate_first_fit(&mm, 200, 1);
    allocate_first_fit(&mm, 150, 2);
    allocate_first_fit(&mm, 100, 3);
    allocate_first_fit(&mm, 180, 4);
    allocate_first_fit(&mm, 120, 5);
    printf("After allocating P1(200), P2(150), P3(100), P4(180), P5(120):");
    visualize_memory(&mm);
    
    // Deallocate some processes (creating holes)
    free_memory(&mm, 2);  // Free P2 (150 units)
    free_memory(&mm, 4);  // Free P4 (180 units)
    printf("After freeing P2 and P4:");
    visualize_memory(&mm);
    
    // Try to allocate something that doesn't fit any single hole
    bool success = allocate_first_fit(&mm, 250, 6);
    printf("Attempt to allocate P6(250): %s", 
           success ? "SUCCESS" : "FAILED");
    visualize_memory(&mm);
    
    analyze_fragmentation(&mm);
    
    // Continue fragmentation
    allocate_first_fit(&mm, 80, 7);
    allocate_first_fit(&mm, 50, 8);
    free_memory(&mm, 3);
    free_memory(&mm, 5);
    allocate_first_fit(&mm, 60, 9);
    
    printf("
After more operations:");
    visualize_memory(&mm);
    analyze_fragmentation(&mm);
    
    return 0;
}

The Checkerboard Effect:

After extended operation, memory resembles a checkerboard:

|####|..|#####|...|##|.|#######|....|###|..|#|

Each . segment is a free hole; each # segment is an allocated region. The holes are:

Scattered unpredictably
Of varying sizes
Usually smaller than what's needed
Collectively substantial but individually insufficient

Coalescing:

When adjacent allocated regions both become free, their holes merge:

Before: |###|...|###|    (two 3-unit holes)
After P2 frees: |...|...|###|  → |......|###|  (one 6-unit hole)

Automatic coalescing helps slow fragmentation but cannot eliminate it when non-adjacent regions free.

Implementation Detail: Coalescing

Measuring External Fragmentation

Quantifying external fragmentation helps assess system health and make allocation policy decisions. Several metrics capture different aspects of fragmentation:

1. Basic Fragmentation Ratio:

Fragmentation Ratio = 1 - (Largest Free Block / Total Free Memory)

Ranges from 0 (no fragmentation—one contiguous hole) to approaching 1 (severe fragmentation)
A ratio of 0.5 means the largest hole contains only half the free memory
A ratio of 0.9 means 90% of free memory is scattered in smaller holes

2. Fragmentation Index (Alternative):

Fragmentation Index = 1 - (Largest Allocatable Size / Total Free Memory)

This is more practical—it measures what can actually be allocated versus total free.

3. Hole Count and Distribution:

Number of holes
Mean, median, standard deviation of hole sizes
Size distribution (histogram of hole sizes)

Fragmentation Severity Interpretation
Fragmentation Ratio	Interpretation	Likely Symptoms	Recommended Action
0.00 - 0.20	Minimal	System healthy, large allocations succeed	Normal operation
0.20 - 0.40	Low	Occasional large allocation delays	Monitor, consider preventive compaction
0.40 - 0.60	Moderate	Large allocations may fail, system slowing	Schedule compaction, review allocation patterns
0.60 - 0.80	High	Significant requests failing, memory under-utilized	Compaction needed, consider algorithm change
0.80 - 1.00	Severe	Most allocations fail despite free memory	Immediate compaction, system redesign needed

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct {
    size_t* hole_sizes;
    size_t hole_count;
    size_t total_memory;
    size_t allocated_memory;
} MemoryState;
 
typedef struct {
    double basic_ratio;
    double fragmentation_index;
    size_t largest_hole;
    size_t smallest_hole;
    double average_hole;
    double std_deviation;
    size_t hole_count;
    size_t total_free;
    double usable_percent;  // Percent of free memory actually usable
} FragmentationMetrics;
 
FragmentationMetrics analyze_fragmentation(MemoryState* state) {
    FragmentationMetrics m = {0};
    
    if (state->hole_count == 0) {
        m.fragmentation_index = 0;  // All memory allocated (or none)
        return m;
    }
    
    // Basic statistics
    m.hole_count = state->hole_count;
    m.total_free = 0;
    m.largest_hole = 0;
    m.smallest_hole = (size_t)-1;
    
    for (size_t i = 0; i < state->hole_count; i++) {
        size_t hole = state->hole_sizes[i];
        m.total_free += hole;
        if (hole > m.largest_hole) m.largest_hole = hole;
        if (hole < m.smallest_hole) m.smallest_hole = hole;
    }
    
    m.average_hole = (double)m.total_free / m.hole_count;
    
    // Standard deviation
    double variance = 0;
    for (size_t i = 0; i < state->hole_count; i++) {
        double diff = state->hole_sizes[i] - m.average_hole;
        variance += diff * diff;
    }
    m.std_deviation = sqrt(variance / m.hole_count);
    
    // Fragmentation ratios
    m.basic_ratio = 1.0 - ((double)m.largest_hole / m.total_free);
    m.fragmentation_index = m.basic_ratio;  // Same for external frag
    
    // Usable percentage (how much can we actually allocate?)
    // This depends on request distribution, but largest hole is key
    m.usable_percent = 100.0 * m.largest_hole / m.total_free;
    
    return m;
}
 
void print_metrics(FragmentationMetrics* m) {
    printf("
=== External Fragmentation Metrics ===
");
    printf("Total Free Memory: %zu bytes
", m->total_free);
    printf("Number of Holes: %zu
", m->hole_count);
    printf("Largest Hole: %zu bytes
", m->largest_hole);
    printf("Smallest Hole: %zu bytes
", m->smallest_hole);
    printf("Average Hole: %.1f bytes
", m->average_hole);
    printf("Std Deviation: %.1f bytes
", m->std_deviation);
    printf("
Fragmentation Ratio: %.2f (%.0f%%)
", 
           m->basic_ratio, m->basic_ratio * 100);
    printf("Usable Free Memory: %.1f%%
", m->usable_percent);
    printf("Wasted (Fragmented): %.1f%%
", 100 - m->usable_percent);
    
    // Severity assessment
    printf("
Severity: ");
    if (m->basic_ratio < 0.2) printf("MINIMAL - System healthy
");
    else if (m->basic_ratio < 0.4) printf("LOW - Monitor situation
");
    else if (m->basic_ratio < 0.6) printf("MODERATE - Consider compaction
");
    else if (m->basic_ratio < 0.8) printf("HIGH - Compaction recommended
");
    else printf("SEVERE - Immediate action required
");
}
 
int main() {
    // Example: A fragmented memory system
    size_t holes[] = {150, 32, 85, 12, 200, 45, 8, 18};
    size_t num_holes = sizeof(holes) / sizeof(holes[0]);
    
    MemoryState state = {
        .hole_sizes = holes,
        .hole_count = num_holes,
        .total_memory = 2048,
        .allocated_memory = 1498  // 2048 - sum(holes)
    };
    
    printf("Memory Configuration:
");
    printf("Total Memory: %zu bytes
", state.total_memory);
    printf("Allocated: %zu bytes
", state.allocated_memory);
    printf("Holes: ");
    for (size_t i = 0; i < num_holes; i++) {
        printf("%zu ", holes[i]);
    }
    printf("
");
    
    FragmentationMetrics m = analyze_fragmentation(&state);
    print_metrics(&m);
    
    // Demonstrate what allocations would succeed/fail
    printf("
=== Allocation Feasibility ===
");
    size_t test_sizes[] = {50, 100, 150, 200, 250, 300};
    for (size_t i = 0; i < sizeof(test_sizes)/sizeof(test_sizes[0]); i++) {
        printf("Request %zu bytes: %s
", test_sizes[i],
               test_sizes[i] <= m.largest_hole ? "POSSIBLE" : "BLOCKED by fragmentation");
    }
    
    return 0;
}

Real-World Monitoring

Causes and Contributing Factors

External fragmentation emerges from fundamental characteristics of dynamic memory allocation. Understanding the causes helps design systems that minimize fragmentation.

Root Causes of External Fragmentation

•Variable Request Sizes: When allocation requests vary in size, released memory rarely matches subsequent requests, leaving remnants.
•Non-Sequential Deallocation: Processes terminate in different orders than they started. The 'holes' created don't form contiguous regions.
•Request/Hole Size Mismatch: An allocation that's smaller than an available hole splits that hole. The remnant may be too small for practical use.
•Long-Lived Allocations: Persistent allocations 'pin' memory regions, preventing adjacent holes from coalescing across them.
•Allocation Pattern Variability: Workloads with high variance in allocation sizes fragment faster than those with consistent sizes.

Patterns That Worsen Fragmentation

•Highly variable allocation sizes
•Long-lived allocations interleaved with short-lived ones
•LIFO (stack-like) deallocation patterns
•Allocations that fragment large holes into unusable pieces
•Workloads with extreme size outliers

Patterns That Minimize Fragmentation

•Uniform allocation sizes (best case)
•FIFO deallocation (oldest freed first)
•Grouping similar-sized allocations together
•Short-lived allocations from one pool, long-lived from another
•Periodic full compaction/restart opportunities

The Entropy Analogy:

External fragmentation resembles entropy in thermodynamics:

Initial state: Low entropy (organized, contiguous memory)
Over time: Entropy increases (memory becomes disordered, fragmented)
Second law: Fragmentation naturally increases without energy input
Reducing entropy: Requires work (compaction, reorganization)

Real-World Fragmentation Rates

Solutions and Mitigation Strategies

Several strategies address external fragmentation, each with distinct trade-offs:

External Fragmentation Mitigation Strategies
Strategy	Description	Pros	Cons
Compaction	Move allocations to collect free space into one contiguous hole	Eliminates fragmentation completely	Expensive (CPU, I/O), requires relocatable addresses
Paging	Divide memory into fixed-size pages; any page can satisfy any request	Eliminates external fragmentation entirely	Introduces internal fragmentation, page table overhead
Best-Fit Allocation	Choose the smallest hole that fits, minimizing leftover fragments	Reduces remnant sizes	May create many tiny unusable holes
Buddy System	Allocate in power-of-2 blocks; easy merging of adjacent buddies	Efficient coalescing, limited fragmentation	High internal fragmentation (power-of-2 rounding)
Pool Allocation	Separate pools for different size classes	Excellent for known patterns	Complex management, may waste memory if pools imbalanced
Slab Allocation	Pre-allocate object caches for common sizes	Near-zero fragmentation for cached objects	Only works for known, repeated allocations

Compaction in Detail:

Compaction physically moves allocated regions to consolidate free space. This is conceptually simple but operationally complex:

Compaction Algorithm:

Find all allocated regions
Calculate new positions (packed contiguously)
Move each region to its new position
Update all pointers/references to reflect new addresses

Requirements:

Relocatable code (position-independent)
All references must be updatable (registers, pointers)
Must pause execution during compaction (stop-the-world)
Or: use indirection (handles) allowing moves without updating user pointers

Converting Mermaid diagram...

Why Paging Solves External Fragmentation:

Paging divides both physical memory (into frames) and virtual memory (into pages) into equal-sized units. Because every frame is interchangeable:

Any free frame can satisfy any page request
No holes are 'too small'—either you have a free frame or you don't
Multiple free frames can serve one allocation (non-contiguous physical allocation)
External fragmentation becomes impossible by definition

Modern OS Approach

External vs. Internal Fragmentation

Comparison: External vs. Internal Fragmentation
Aspect	External Fragmentation	Internal Fragmentation
Location of Waste	Between allocations (in free pool)	Within allocations (in allocated blocks)
Cause	Variable-sized allocations leave holes	Fixed-size blocks exceed actual need
Visibility	Free memory exists but unusable	Allocated memory partially unused
Measurement	1 - (largest_hole / total_free)	(allocated - used) / allocated
Boundedness	Unbounded (can approach 100%)	Bounded by allocation unit size
Recovery	Compaction or clever allocation	Cannot recover without reallocation
Allocation Scheme	Variable partitions, segments	Fixed partitions, paging
Eliminated By	Paging (fixed-size allocation)	Perfect-fit allocation

The Fundamental Trade-Off:

Variable-Size Allocation:
  ✓ Zero internal fragmentation (exact fit)
  ✗ External fragmentation accumulates
  
Fixed-Size Allocation:
  ✓ Zero external fragmentation (any slot works)
  ✗ Internal fragmentation inevitable

Why This Trade-Off Exists:

With variable-sized allocation:

Each allocation gets exactly what it needs (no internal waste)
But holes left by deallocations don't match new requests (external waste)

With fixed-sized allocation:

Every hole is the same size, so any hole fits any request (no external waste)
But most requests don't perfectly match the fixed size (internal waste)

The Paging Compromise:

Paging represents the industry's answer to this dilemma:

Accept bounded internal fragmentation (up to one page per allocation)
Completely eliminate external fragmentation
The bounded internal fragmentation is deemed acceptable given paging's other benefits (protection, virtual memory, simplicity)

You Can't Have Both

Summary: External Fragmentation

We've explored the mechanics, measurement, and mitigation of external fragmentation. Let's consolidate the key insights:

Key Takeaways

•Definition: External fragmentation occurs when free memory is scattered in non-contiguous holes, making large allocations impossible despite sufficient total free memory.
•Cause: Variable-sized allocations and non-sequential deallocations naturally fragment the free pool over time.
•Measurement: The fragmentation ratio (1 - largest_hole/total_free) quantifies severity; values above 0.5 indicate significant problems.
•Unbounded Growth: Unlike internal fragmentation, external fragmentation can grow arbitrarily, potentially rendering most free memory unusable.
•Solutions: Compaction (expensive), paging (eliminates), buddy system (limits), slab allocation (for fixed sizes).
•Trade-Off: External and internal fragmentation trade off—reducing one typically increases the other. Paging's fixed-size approach chooses bounded internal fragmentation over unbounded external fragmentation.

What's Next:

Page Complete