Memory Fragmentation: Internal and External
Internal Fragmentation
Read aloud is unavailable in this browser.
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.
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 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.
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:
- •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.
| 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.
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
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
#include <stdio.h>#include <stdint.h> // Calculate internal fragmentation for an allocation schemetypedef 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 partitionssize_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 pagessize_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
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)
| 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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
#include <stdio.h>#include <stdlib.h> // Analyze internal fragmentation for various page sizesvoid 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_sizevoid 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 (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.
- •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.
| 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.
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:
- •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.
- •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).
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
#include <stdio.h>#include <stdint.h> // BAD: Natural declaration order causes paddingstruct 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;}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.
| 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.
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.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.