Internal Fragmentation - Memory Fragmentation: Internal and External | OneNoughtOne

0/236

Operating SystemsFragmentation

Memory Fragmentation: Internal and External

LevelIntermediate

Duration90 mins

TopicFragmentation

1 / 5

Internal Fragmentation

The Hidden Cost of Allocating Memory

Imagine renting a storage unit for your belongings. You need 70 cubic feet of space, but the smallest available unit is 100 cubic feet. You pay for 100 cubic feet, but 30 cubic feet sits permanently empty—wasted yet unusable for anyone else. This is the essence of internal fragmentation in memory management.

In operating systems, when a process requests memory, the system often allocates more than requested. The difference between what's allocated and what's actually used represents internal fragmentation—memory that belongs to a process but serves no computational purpose. It's allocated, so no other process can use it. It's unused, so it contributes nothing to the owning process.

Understanding internal fragmentation is critical because it's an unavoidable consequence of many memory allocation schemes, particularly those using fixed-size partitions or alignment constraints. The art lies in minimizing this waste while maintaining efficient allocation and access patterns.

What You Will Learn

By the end of this page, you will understand what internal fragmentation is, why it occurs, how to calculate and measure it, where it manifests in real systems (from memory allocators to file systems), and strategies to minimize its impact while balancing other system constraints.

Defining Internal Fragmentation

Internal fragmentation occurs when the memory allocated to a process or data structure exceeds the memory actually required by that process or data structure. The excess memory is trapped within the allocation—internal to it—and cannot be used for any other purpose.

Formal Definition:

Internal Fragmentation = Allocated Memory - Requested Memory

Where:

Allocated Memory is the actual amount of memory reserved for the request
Requested Memory is the amount the process actually needs

This phenomenon is inherent to allocation schemes where:

Memory is divided into fixed-size blocks or partitions
Allocations must be aligned to specific boundaries
Minimum allocation granularities exist
Overhead structures consume space within allocations

The 'Internal' in Internal Fragmentation

The fragmentation is called 'internal' because the wasted space exists inside the allocated region. The process owns this memory; it's just not using all of it. Contrast this with external fragmentation, where wasted space exists between allocations—in the free pools.

Converting Mermaid diagram...

Why Does Internal Fragmentation Occur?

Several fundamental reasons drive internal fragmentation:

Fixed Partition Sizes: When memory is divided into predetermined partition sizes (e.g., 1KB, 4KB, 16KB), a request for 750 bytes must receive a 1KB partition, wasting 274 bytes.
Alignment Requirements: Many hardware architectures require data to be aligned at specific boundaries (e.g., 4-byte, 8-byte, or page boundaries). A 13-byte request might be padded to 16 bytes for alignment.
Allocation Overhead: Memory allocators often store metadata (size, flags, pointers) within the allocated block. A 100-byte request might consume 116 bytes (16 bytes of metadata + 100 bytes of data).
Power-of-Two Sizing: Many allocators round up to the next power of two for efficiency. A request for 260 bytes becomes a 512-byte allocation, wasting 252 bytes (48.8%).

Sources and Causes of Internal Fragmentation

Internal fragmentation doesn't arise from poor implementation—it's often an intentional trade-off for performance, simplicity, or hardware compatibility. Let's examine the primary sources in depth:

Primary Sources of Internal Fragmentation

•Fixed-Size Partitioning: The operating system divides memory into partitions of predetermined sizes. Regardless of actual need, a process receives an entire partition. If partitions are 64KB and a process needs 40KB, 24KB (37.5%) is wasted internally.
•Page/Frame Sizing: In paging systems, memory is allocated in fixed-size pages (commonly 4KB). The last page of any allocation is almost always partially filled. A process using 10,000 bytes requires 3 pages (12,288 bytes), wasting 2,288 bytes (18.6%).
•Block-Based Allocators: Memory allocators often organize free memory into size classes (e.g., 8, 16, 32, 64, 128 bytes). A 17-byte request is satisfied from the 32-byte class, wasting 15 bytes (46.9%).
•Hardware Alignment Constraints: CPUs often access memory more efficiently when data is aligned to natural boundaries. Compilers and allocators pad structures and allocations to meet these requirements.
•Allocator Metadata: Every allocation typically carries overhead for bookkeeping—block size, allocation flags, free list pointers. This metadata is part of the allocated block but not usable by the application.

Internal Fragmentation in Different Allocation Schemes
Allocation Scheme	Granularity	Request Example	Allocated	Wasted	Waste %
Fixed Partition (64KB)	64KB	40KB	64KB	24KB	37.5%
Paging (4KB pages)	4KB	10KB	12KB (3 pages)	2KB	16.7%
Buddy System (power-of-2)	Powers of 2	100 bytes	128 bytes	28 bytes	21.9%
Slab Allocator (object caches)	Object size	Exact	Exact + metadata	Metadata only	~1-5%
malloc (with 8-byte alignment)	8 bytes	13 bytes	16 bytes	3 bytes	18.8%

The Alignment Tax:

Modern processors achieve optimal performance when data is aligned at specific boundaries:

32-bit integers: Should be aligned at 4-byte boundaries
64-bit integers/pointers: Should be aligned at 8-byte boundaries
SSE/AVX vectors: May require 16-byte or 32-byte alignment
Cache lines: Often 64 bytes; aligning to cache line boundaries prevents false sharing

This alignment requirement means allocators must sometimes insert padding bytes, contributing to internal fragmentation. The alternative—unaligned access—incurs performance penalties or even hardware exceptions on some architectures.

Alignment Example in C Structures

Consider struct { char a; int b; char c; }. Naively, this needs 6 bytes (1+4+1). But with 4-byte alignment for int, the compiler pads it to 12 bytes: 1 byte for a, 3 bytes padding, 4 bytes for b, 1 byte for c, 3 bytes trailing padding. Internal fragmentation: 50%.

Quantifying Internal Fragmentation

To manage internal fragmentation effectively, we must measure it precisely. Several metrics help quantify the extent and impact of internal fragmentation:

1. Absolute Internal Fragmentation:

The total bytes wasted across all allocations.

Absolute IF = Σ (Allocated[i] - Requested[i]) for all allocations i

2. Per-Allocation Fragmentation:

Waste for a single allocation.

Fragmentation[i] = Allocated[i] - Requested[i]
Fragmentation %[i] = (Allocated[i] - Requested[i]) / Allocated[i] × 100%

3. System-Wide Fragmentation Ratio:

Overall efficiency of memory utilization.

Fragmentation Ratio = (Total Allocated - Total Requested) / Total Allocated
Utilization Efficiency = Total Requested / Total Allocated = 1 - Fragmentation Ratio

internal_fragmentation_calculator.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
#include <stdio.h>
#include <stdint.h>
 
// Calculate internal fragmentation for an allocation scheme
typedef struct {
    size_t requested;      // What the application asked for
    size_t allocated;      // What was actually allocated
} Allocation;
 
typedef struct {
    size_t total_requested;
    size_t total_allocated;
    size_t total_fragmentation;
    double fragmentation_ratio;
    double utilization_efficiency;
} FragmentationStats;
 
FragmentationStats calculate_fragmentation(Allocation* allocs, size_t count) {
    FragmentationStats stats = {0};
    
    for (size_t i = 0; i < count; i++) {
        stats.total_requested += allocs[i].requested;
        stats.total_allocated += allocs[i].allocated;
        stats.total_fragmentation += 
            (allocs[i].allocated - allocs[i].requested);
    }
    
    stats.fragmentation_ratio = 
        (double)stats.total_fragmentation / stats.total_allocated;
    stats.utilization_efficiency = 
        (double)stats.total_requested / stats.total_allocated;
    
    return stats;
}
 
// Example: Fixed partition scheme with 1KB partitions
size_t allocate_fixed_partition(size_t requested, size_t partition_size) {
    // Always allocate full partition
    return partition_size;
}
 
// Example: Power-of-two allocation (buddy system style)
size_t allocate_power_of_two(size_t requested) {
    size_t allocated = 1;
    while (allocated < requested) {
        allocated <<= 1;  // Multiply by 2
    }
    return allocated;
}
 
// Example: Paging with 4KB pages
size_t allocate_pages(size_t requested, size_t page_size) {
    return ((requested + page_size - 1) / page_size) * page_size;
}
 
int main() {
    size_t requests[] = {100, 750, 1500, 3000, 6000, 9500};
    size_t num_requests = sizeof(requests) / sizeof(requests[0]);
    
    printf("
=== Internal Fragmentation Analysis ===
 
");
    printf("Request\tFixed(1KB)\tBuddy\t\tPaging(4KB)
");
    printf("-------\t----------\t-----\t\t----------
");
    
    for (size_t i = 0; i < num_requests; i++) {
        size_t fixed = allocate_fixed_partition(requests[i], 1024);
        size_t buddy = allocate_power_of_two(requests[i]);
        size_t paged = allocate_pages(requests[i], 4096);
        
        printf("%zu\t%zu (%+.0f%%)\t%zu (%+.0f%%)\t%zu (%+.0f%%)
",
            requests[i],
            fixed, 100.0 * (fixed - requests[i]) / fixed,
            buddy, 100.0 * (buddy - requests[i]) / buddy,
            paged, 100.0 * (paged - requests[i]) / paged);
    }
    
    return 0;
}

Expected vs. Average Fragmentation:

For many allocation schemes, we can compute expected fragmentation statistically:

Fixed Partitions (Single Size P): If requests are uniformly distributed between 0 and P:

Average fragmentation = P/2
Average utilization = 50%

Power-of-Two Buddy System: If requests are uniformly distributed:

Worst case: Just over a power of 2, wastes nearly 50%
Average fragmentation ≈ 25-33% (depends on request distribution)

Paging (Page Size = S): For a single allocation of random size:

Expected internal fragmentation in last page = S/2
For multiple pages: fragmentation as % of total decreases with allocation size
Large allocations become efficient; small allocations may waste up to (S-1) bytes

The Small Allocation Problem

Small allocations suffer disproportionately from internal fragmentation. A 100-byte request in a 4KB page system wastes 97.6% of the allocated memory. This is why systems use specialized small-object allocators (slab allocators, pool allocators) that pack small objects efficiently.

Internal Fragmentation in Paging Systems

Paging is the dominant memory management technique in modern operating systems. While paging eliminates external fragmentation (any free frame can satisfy any page request), it introduces internal fragmentation in a specific, predictable pattern.

The Last-Page Problem:

In a paging system with page size S, any process whose memory requirement M is not an exact multiple of S will waste space in its last page.

Internal Fragmentation = S - (M mod S)    when (M mod S) ≠ 0
Internal Fragmentation = 0                when (M mod S) = 0

Statistical Analysis:

Assuming process sizes are randomly distributed:

Average internal fragmentation per process = S/2
Maximum internal fragmentation per process = S - 1
Minimum internal fragmentation per process = 0 (when size is exact multiple)

Internal Fragmentation vs. Page Size (for 50KB process)
Page Size	Pages Needed	Total Allocated	Internal Fragmentation	Waste %
512 bytes	100	51,200 bytes	1,200 bytes	2.3%
1 KB	50	51,200 bytes	1,200 bytes	2.3%
4 KB	13	53,248 bytes	2,048 bytes	3.8%
8 KB	7	57,344 bytes	6,144 bytes	10.7%
16 KB	4	65,536 bytes	14,336 bytes	21.9%
64 KB	1	65,536 bytes	14,336 bytes	21.9%

The Trade-Off: Page Size Selection

Larger pages reduce certain overheads but increase internal fragmentation:

Arguments for Smaller Pages:

Less internal fragmentation (smaller last-page waste)
Finer-grained memory protection
Better memory utilization for small processes

Arguments for Larger Pages:

Smaller page tables (fewer entries)
Better TLB coverage (each TLB entry covers more memory)
Reduced page fault overhead (fewer faults for sequential access)
Better disk I/O efficiency (larger contiguous transfers)

Modern Compromise:

Most systems use 4KB pages as a default, with support for large pages (2MB or 1GB) for specific use cases. The 4KB size represents decades of empirical tuning—small enough to limit fragmentation, large enough for efficient hardware translation.

page_fragmentation_analysis.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
#include <stdio.h>
#include <stdlib.h>
 
// Analyze internal fragmentation for various page sizes
void analyze_fragmentation(size_t process_size, size_t page_size) {
    size_t pages_needed = (process_size + page_size - 1) / page_size;
    size_t total_allocated = pages_needed * page_size;
    size_t fragmentation = total_allocated - process_size;
    double waste_percent = 100.0 * fragmentation / total_allocated;
    
    printf("Page Size: %6zu | Pages: %4zu | Allocated: %8zu | "
           "Fragmentation: %6zu (%.2f%%)
",
           page_size, pages_needed, total_allocated, 
           fragmentation, waste_percent);
}
 
// Expected internal fragmentation analysis
// For uniform random process sizes from 1 to max_size
void expected_fragmentation_analysis(size_t page_size, size_t max_size) {
    double total_fragmentation = 0;
    double total_allocated = 0;
    size_t samples = 100000;
    
    for (size_t i = 0; i < samples; i++) {
        size_t process_size = 1 + (rand() % max_size);
        size_t pages = (process_size + page_size - 1) / page_size;
        size_t allocated = pages * page_size;
        total_fragmentation += (allocated - process_size);
        total_allocated += allocated;
    }
    
    printf("
Expected Fragmentation (random sizes 1-%zu):
", max_size);
    printf("Page Size %zu: Average fragmentation %.2f bytes per process
",
           page_size, total_fragmentation / samples);
    printf("Overall utilization efficiency: %.2f%%
",
           100.0 * (1 - total_fragmentation / total_allocated));
}
 
int main() {
    printf("
=== Page Size Impact on Fragmentation ===
 
");
    printf("For a 50,000 byte process:
");
    
    size_t page_sizes[] = {512, 1024, 2048, 4096, 8192, 16384, 65536};
    for (size_t i = 0; i < sizeof(page_sizes)/sizeof(page_sizes[0]); i++) {
        analyze_fragmentation(50000, page_sizes[i]);
    }
    
    expected_fragmentation_analysis(4096, 100000);
    
    return 0;
}

Huge Pages and Fragmentation

Huge pages (2MB or larger) drastically reduce TLB pressure but can waste megabytes per process. They're optimal for applications with large, stable memory footprints (databases, HPC). For general workloads with many small processes, standard 4KB pages remain more efficient.

Real-World Manifestations

Internal fragmentation appears throughout computing systems, not just in OS memory management. Understanding its manifestations helps in designing efficient systems at every level.

Internal Fragmentation Across Systems

•User-Space Memory Allocators (malloc): Standard allocators use size classes and alignment, causing 15-25% overhead on average. Specialized allocators like jemalloc and tcmalloc reduce this through thread-local caches and sophisticated size classes.
•File Systems (Disk Blocks): A 1-byte file on a 4KB block file system consumes 4KB on disk. Directories with many small files suffer severe internal fragmentation. Some file systems use tail packing or block suballocation to mitigate this.
•Network Packets: Fixed-size buffers for variable-length packets waste bandwidth and memory. A 64-byte Ethernet minimum frame carrying a 40-byte packet wastes 38% of frame capacity.
•Database Pages: Database systems use fixed-size pages (often 8KB or 16KB). Partially filled pages represent internal fragmentation, impacting storage efficiency and I/O amplification.
•GPU Memory: Graphics APIs often require power-of-two texture dimensions. A 257×257 texture may be padded to 512×512, wasting 75% of allocated memory.
•Container/VM Resource Allocation: A container allocated 512MB that only uses 300MB represents 41% internal fragmentation of memory resources.

Internal Fragmentation Impact by Domain
Domain	Allocation Unit	Typical Waste	Mitigation Strategy
OS Memory	4KB pages	~2KB avg per process	Small object allocators, huge pages for large allocs
malloc()	8-256 byte classes	15-25% overall	Size-class tuning, thread-local caches
File Systems	4KB blocks	~2KB per small file	Tail packing, inline extents, extent-based
Databases	8-16KB pages	Variable (fill factor)	Page compaction, compression, fill factor tuning
Networks	MTU (1500 bytes)	Variable	Jumbo frames, segmentation offload
GPU Textures	Power-of-2 dims	Up to 75%	Texture atlases, NPOT support in modern GPUs

Case Study: Application Memory Allocation

Consider a web server handling requests that allocate temporary buffers:

Request type A: needs 300 bytes → allocated 512 (buddy) → 41% waste
Request type B: needs 1100 bytes → allocated 2048 → 46% waste
Request type C: needs 50 bytes → allocated 64 → 22% waste

If the server handles 10,000 concurrent requests:

Type A (40%): 4000 × 212 bytes wasted = 848 KB
Type B (35%): 3500 × 948 bytes wasted = 3.2 MB
Type C (25%): 2500 × 14 bytes wasted = 35 KB

Total internal fragmentation: ~4.1 MB — potentially significant in memory-constrained environments.

This is why high-performance servers often use custom allocators with carefully tuned size classes matching their workload patterns.

The Accidental Fragmentation

Programmers often cause internal fragmentation unknowingly. Using char buffer[1024] for a string that rarely exceeds 50 characters, or std::vector::reserve(1000) when only 200 elements are ever needed—these decisions accumulate into significant memory waste at scale.

Mitigation Strategies

While internal fragmentation cannot be completely eliminated in most allocation schemes, several strategies minimize its impact:

Allocator-Level Strategies

•Size-Class Optimization: Use granular size classes matching common allocation patterns. Instead of power-of-2 only, include intermediate sizes (48, 96, 160 bytes).
•Slab Allocation: Pre-allocate caches of same-sized objects. Eliminates per-object fragmentation when object sizes are known.
•Pool Allocators: Application-specific allocators that batch allocations for objects of known sizes.
•Bitmap Allocators: For fixed-size objects, use one bit per slot—no metadata overhead within allocations.

Application-Level Strategies

•Right-Sizing Buffers: Size buffers based on actual workload analysis, not arbitrary round numbers.
•Object Pooling: Reuse objects instead of allocating and freeing repeatedly.
•Data Structure Packing: Arrange structure members to minimize padding (largest first, then descending).
•Compact Representations: Use smaller data types where possible (int16 vs int32, packed bit fields).

struct_packing_example.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
#include <stdio.h>
#include <stdint.h>
 
// BAD: Natural declaration order causes padding
struct Wasteful {
    char a;      // 1 byte + 7 padding
    double b;    // 8 bytes
    char c;      // 1 byte + 3 padding
    int d;       // 4 bytes
    char e;      // 1 byte + 7 padding
};  // Total: 32 bytes for 15 bytes of data (53% waste!)
 
// GOOD: Ordered by size (largest first)
struct Efficient {
    double b;    // 8 bytes
    int d;       // 4 bytes
    char a;      // 1 byte
    char c;      // 1 byte
    char e;      // 1 byte + 1 padding
};  // Total: 16 bytes for 15 bytes of data (6% waste)
 
// AGGRESSIVE: Packed (may hurt performance on some architectures)
#pragma pack(push, 1)
struct Packed {
    char a;      // 1 byte
    double b;    // 8 bytes
    char c;      // 1 byte
    int d;       // 4 bytes
    char e;      // 1 byte
};  // Total: 15 bytes (0% fragmentation, but unaligned access)
#pragma pack(pop)
 
int main() {
    printf("Struct sizes:
");
    printf("Wasteful: %zu bytes (%.1f%% internal fragmentation)
",
           sizeof(struct Wasteful),
           100.0 * (sizeof(struct Wasteful) - 15) / sizeof(struct Wasteful));
    printf("Efficient: %zu bytes (%.1f%% internal fragmentation)
",
           sizeof(struct Efficient),
           100.0 * (sizeof(struct Efficient) - 15) / sizeof(struct Efficient));
    printf("Packed: %zu bytes (%.1f%% internal fragmentation)
",
           sizeof(struct Packed),
           100.0 * (sizeof(struct Packed) - 15) / sizeof(struct Packed));
    return 0;
}

The Packing Trade-Off

While struct packing eliminates internal fragmentation, it can degrade performance significantly. Unaligned memory access is slower (sometimes 10x slower or causes hardware exceptions). Always profile before aggressive packing—the memory savings may not justify the performance cost.

Relationship to Other Memory Concepts

Internal fragmentation exists within a larger ecosystem of memory management concepts. Understanding these relationships clarifies when to prioritize combating internal fragmentation versus other concerns.

Internal Fragmentation vs. Other Memory Concepts
Concept	Relationship to Internal Fragmentation	Trade-Off Dynamics
External Fragmentation	Inverse relationship in fixed vs variable partition schemes	Fixed partitions: high internal, zero external; Variable: zero internal, high external
Memory Alignment	Alignment requirements cause internal fragmentation	Better alignment = more fragmentation but faster access
Page Size	Larger pages = more internal fragmentation	Balance TLB efficiency vs. memory waste
Allocator Complexity	Sophisticated allocators reduce fragmentation but add overhead	CPU cost vs. memory cost
Caching/Locality	Fragmentation spreads data, potentially hurting cache performance	Compact data = better locality = better performance

Internal vs. External Fragmentation: The Duality

Fixed-size allocation schemes create a fundamental trade-off:

Scheme	Internal Fragmentation	External Fragmentation
Fixed partitions	HIGH (average ~50%)	NONE (any partition fits)
Variable partitions	NONE (exact fit)	HIGH (holes accumulate)
Paging	MODERATE (last page)	NONE (any frame fits page)
Segmentation	NONE (exact fit)	HIGH (variable segments)

Paging represents a practical compromise: it accepts moderate internal fragmentation (bounded by one page per process) to completely eliminate the complexity of external fragmentation and the need for compaction.

Why Paging Won:

Historically, systems tried various schemes:

Fixed partitions were too inflexible and wasteful
Variable partitions required complex management and compaction
Segmentation combined the worst of both problems
Paging provided predictable, bounded fragmentation with simple management

The overhead of internal fragmentation in paging (one page per process) proved acceptable given its benefits for memory protection, virtual memory, and implementation simplicity.

Practical Wisdom

When designing allocation strategies, internal fragmentation is often the 'price of simplicity.' Systems that minimize internal fragmentation through exact-fit allocation typically incur complexity and external fragmentation costs that outweigh the savings. Accept bounded internal fragmentation in exchange for predictable, efficient allocation.

Summary: Internal Fragmentation

We've established a comprehensive understanding of internal fragmentation. Let's consolidate the key insights:

Key Takeaways

•Definition: Internal fragmentation is wasted space within allocated memory blocks—the difference between allocated and actually used memory.
•Causes: Fixed partition sizes, page sizing, power-of-two allocators, alignment requirements, and allocator metadata all contribute to internal fragmentation.
•Quantification: Can be measured absolutely (total wasted bytes), per-allocation (waste percentage), or system-wide (utilization efficiency).
•Paging Trade-Off: Paging accepts internal fragmentation (up to one page per process) to eliminate external fragmentation entirely.
•Manifestations: Appears in OS memory, malloc, file systems, databases, network packets, and container resource allocation.
•Mitigation: Size-class optimization, slab allocation, object pooling, and structure packing reduce internal fragmentation within their respective domains.

What's Next:

Having understood internal fragmentation—waste within allocations—we now turn to its counterpart: external fragmentation. External fragmentation concerns wasted space between allocations, where free memory exists but cannot satisfy requests due to its scattered distribution. This understanding completes our picture of memory waste in allocation systems.

Page Complete

You now understand internal fragmentation—its causes, measurement, real-world impact, and mitigation strategies. This knowledge is essential for evaluating allocation schemes and understanding why modern systems accept certain fragmentation trade-offs for simplicity and predictability.