Paging eliminates external fragmentation completely. But there's a tradeoff: it introduces internal fragmentation—wasted space within allocated pages. This is the cost of using fixed-size allocation units.

Imagine shipping goods in standard-size containers. If your shipment partially fills the last container, that unused space travels with your goods—you've paid for capacity you're not using. This is internal fragmentation in paging: memory allocated but not utilized within each process's last page.

The good news? Internal fragmentation in paging is predictable, bounded, and typically far less wasteful than the external fragmentation it replaces.

Internal Fragmentation Defined:

Internal fragmentation is the wasted space within an allocated memory unit due to the unit being larger than the memory actually needed.

Key Distinction from External Fragmentation:

External Fragmentation: Unusable space BETWEEN allocated blocks
                        (free memory in holes too small to use)

Internal Fragmentation: Unusable space INSIDE allocated blocks
                        (allocated but unused portion of a page)

┌──────────────────────────────────────────────────────────┐
│External fragmentation: holes between allocations          │
│                                                           │
│    [Block A]    [hole]    [Block B]    [hole]   [Block C] │
│                   ↑          ↑           ↑                │
│               wasted     wasted      wasted               │
└──────────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────────┐
│Internal fragmentation: unused space within allocations    │
│                                                           │
│    [Used│░░│]    [Used│░│]    [Used│░░░░░│]               │
│         ↑             ↑              ↑                   │
│       wasted       wasted         wasted                 │
│      (in page)   (in page)      (in page)                │
└──────────────────────────────────────────────────────────┘

Why Internal Fragmentation Occurs in Paging:

In paging, memory is allocated in whole pages. Processes rarely need exact multiples of the page size. Therefore:

1. Process needs N bytes
2. System allocates ⌈N / PageSize⌉ pages (ceiling—round up)
3. Wasted = (pages allocated × page size) - N

Example:

Process needs 10,300 bytes with 4KB (4096 byte) pages:

• Pages needed = ⌈10,300 / 4,096⌉ = ⌈2.51⌉ = 3 pages
• Bytes allocated = 3 × 4,096 = 12,288 bytes
• Bytes wasted = 12,288 - 10,300 = 1,988 bytes (internal fragmentation)

This wasted space is in the last (partially filled) page.

Let's rigorously analyze internal fragmentation in paging systems.

Statistical Model:

Assume allocation sizes are uniformly distributed (any byte count equally likely). For a page size of S bytes:

• Waste per allocation ranges from 0 bytes (exact fit) to S-1 bytes (off by 1)
• Expected waste per allocation = (S-1) / 2 ≈ S/2 (average of 0 and S-1)

For a process with M independent memory regions:

Total expected waste = M × (S/2)

Where:
- M is the number of memory regions (code, data, heap, stack segments)
- S is the page size in bytes

Example:

Typical process with 4 memory regions, 4KB pages:

• Expected waste = 4 × 2KB = 8KB per process

With 2MB huge pages:

• Expected waste = 4 × 1MB = 4MB per process

Waste as Percentage of Process Memory:

For a process with total allocation A and M regions:

Waste = M × (S/2)
Waste % = (M × S/2) / A × 100%
        = M × S / (2A) × 100%

For small processes, this percentage can be significant:

• Process using 16KB with 4KB pages: Waste = 8KB = 50% overhead
• Process using 1MB with 4KB pages: Waste = 8KB = 0.8% overhead
• Process using 4GB with 4KB pages: Waste = 8KB = 0.0002% overhead

Key Insight: Internal fragmentation is a fixed overhead per region, not proportional to process size. This means:

• Large processes barely notice it
• Small processes feel it most
• The aggregate depends on process count, not total memory

Let's examine internal fragmentation in realistic scenarios.

Scenario 1: Desktop Workstation

System: 32 GB RAM, 4 KB pages, running ~200 processes

Typical process:
- Code segment: 1-50 MB (variable)
- Data segment: 100 KB - 2 GB (highly variable)
- Stack: 8-16 MB per thread
- Heap: 1 MB - 8 GB per process

Estimate with 4 regions per process:
- Internal fragmentation: 200 × 4 × 2 KB = 1,600 KB = 1.6 MB
- Percentage of 32 GB: 0.005%

Verdict: Negligible

Scenario 2: Enterprise Server

System: 512 GB RAM, 4 KB pages, 2,000 processes (containers)

Internal fragmentation: 2,000 × 4 × 2 KB = 16 MB
Percentage of 512 GB: 0.003%

Verdict: Negligible

Scenario 3: Server with Huge Pages

System: 256 GB RAM, 2 MB pages for database, 100 small processes using 4 KB pages

Database (4 GB allocation with 2 MB pages):
- Waste: ~1 MB (half of last huge page)

Small processes (100 × 10 MB each):
- If forced to use 2 MB pages: 100 × 4 × 1 MB = 400 MB waste (1.5% of RAM)
- With 4 KB pages: 100 × 4 × 2 KB = 800 KB waste (negligible)

Verdict: Mixed page sizes essential for efficiency

Worst Case: Many Small Processes with Huge Pages:

Anti-pattern: Force 2 MB pages on shell scripts and utilities

Shell script using 500 KB:
- With 4 KB pages: 1 page waste on average = 2 KB
- With 2 MB pages: Full 2 MB allocated, 1.5 MB wasted (300% overhead!)

100 such small processes:
- 4 KB pages: 200 KB total waste
- 2 MB pages: 150 MB total waste (750× more!)

This is why modern systems use tiered page sizes:

• 4 KB for general use and small processes
• 2 MB for large datasets and applications that benefit
• 1 GB for massive in-memory databases

Is trading external fragmentation for internal fragmentation worthwhile? Let's compare directly.

Side-by-Side Comparison:

Quantitative Example: 128 GB Server

Contiguous allocation (external fragmentation):
- Expected waste: ~33% = 42 GB
- Usable memory: 86 GB
- Requires periodic compaction
- Unpredictable allocation failures

Paging with 4 KB pages (internal fragmentation):
- 1000 processes × 4 regions × 2 KB = 8 MB
- Page table overhead: ~2-4 GB (hierarchical tables, large processes)
- Total overhead: ~4 GB
- Usable memory: 124 GB
- No fragmentation-related failures ever

The Verdict:

Internal fragmentation wastes roughly 2-3% of memory (including page table overhead). External fragmentation wastes roughly 33% of memory.

Paging is approximately 10× more memory efficient than contiguous allocation.

Several factors influence the actual internal fragmentation in a system:

1. Page Size:

The most direct factor. Larger pages = more potential waste.

Table: Maximum waste per region vs. page size

Page Size    Max Waste/Region    Typical Waste/Region
512 B        511 bytes           256 bytes
4 KB         4,095 bytes         2,048 bytes
64 KB        65,535 bytes        32,768 bytes
2 MB         2,097,151 bytes     ~1 MB
1 GB         ~1 GB               ~512 MB

2. Number of Memory Regions:

Each region has its own internal fragmentation:

Simple process: 2 regions (code + data)
- Waste: ~1 page = 4 KB

Multi-threaded process: 2 + N threads (each thread needs stack)
- 10 threads: 12 regions
- Waste: ~6 pages = 24 KB

Process with many shared libraries:
- Each library: additional code + data regions
- 20 libraries × 2 regions = 40 additional regions
- Waste: ~20 pages = 80 KB

3. Alignment Requirements:

Many allocations are aligned to page boundaries for various reasons:

Memory-mapped files: Start at page boundary
- File size 100 KB → 25 pages needed, up to 4 KB waste

Stack guard pages: Full pages left unmapped
- No fragmentation (page is used for protection, not data)

Data structure alignment:
- Large arrays often page-aligned for cache/TLB efficiency
- Compiler may pad to page boundary, increasing apparent waste

4. Application Behavior:

Some applications minimize fragmentation naturally:

Well-designed allocation:
- Allocate in page-size multiples when possible
- Pool small objects together
- Reuse memory rather than reallocating

Poor allocation patterns:
- Many small, independent allocations
- Sparse virtual address space usage
- Many memory regions due to fragmented heap

While internal fragmentation is usually acceptable, situations may call for its reduction:

1. Use Appropriate Page Sizes:

2. Slab Allocation for Kernel Objects:

Problem: Kernel allocates many small objects (inodes, task structs, etc.)
Naive: One object per page → massive waste

Solution: Slab Allocator
┌────────────────────────────────────────────────────┐
│                      Page                           │
│ ┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐ │
│ │Task ││Task ││Task ││Task ││ Free││ Free││ Free│ │
│ │Struct││Struct││Struct││Struct││     ││     ││     │ │
│ └─────┘└─────┘└─────┘└─────┘└─────┘└─────┘└─────┘ │
└────────────────────────────────────────────────────┘

Multiple small objects share a page.
Waste reduced from ~4 KB per object to ~0 per object.
Only the last page in the slab has fragmentation.

3. Memory Pools:

Application-level technique:

1. Allocate large chunk (multiple pages)
2. Subdivide for small objects
3. Manage sub-allocation internally

Result: Multiple small allocations share pages.
Used by: jemalloc, tcmalloc, game engines, etc.

4. Demand Zeroing / Copy-on-Write:

These techniques don't reduce fragmentation directly but reduce its impact:

Demand Zeroing:
- Allocate pages 'virtually' without physical frames
- Only allocate frame when page is first accessed
- Unused portion of last page never physically allocated

Copy-on-Write:
- Share pages until modification
- Only the modified portions consume physical memory

5. Architecture-Level Solutions:

• Subpage Protection (rare): Some architectures allow finer-grained protection, reducing forced page alignment.
• Transparent Huge Pages (THP): Automatically upgrade/downgrade page sizes based on usage, though with challenges.
• Variable Page Sizes (ARM): Some ARM implementations support multiple configurable base page sizes.

Measuring internal fragmentation requires understanding what's actually allocated versus what's used.

Linux Memory Inspection:

# Process memory regions (from /proc/[pid]/maps)
$ cat /proc/self/maps | head -5
55d8f8a00000-55d8f8a28000 r--p 00000000 08:01 1234  /bin/cat
55d8f8a28000-55d8f8a90000 r-xp 00028000 08:01 1234  /bin/cat
55d8f8a90000-55d8f8aa8000 r--p 00090000 08:01 1234  /bin/cat
...

# Each line is a memory region
# End - Start = region size (includes internal fragmentation)

# Process resident memory
$ ps -o pid,rss,vsz -p $$
  PID   RSS    VSZ
 1234  2048  45892

# RSS = Resident Set Size (physical memory)
# VSZ = Virtual Size (address space, may include unmapped pages)

Analyzing Fragmentation:

# Count memory regions per process
$ wc -l /proc/self/maps
47 /proc/self/maps

# Estimate fragmentation
# 47 regions × 2 KB average waste = 94 KB

# System-wide process count
$ ps aux | wc -l
234

# System-wide fragmentation estimate
# 234 processes × 47 regions × 2 KB = 22 MB
# On a 32 GB system: 22 MB / 32 GB = 0.07%

Slab Allocator Statistics (Kernel):

$ cat /proc/slabinfo | head -10
# name           <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab>
kmalloc-8192        412        416      8192          4            8
kmalloc-4096       1284       1320      4096          8            8
kmalloc-2048       3456       3520      2048         16            8
task_struct        1823       1840       640         25            4
...

# objsize: size of each object
# objperslab: objects per slab (page group)
# Fragmentation = (num_objs - active_objs) × objsize

Huge Page Allocation:

$ cat /proc/meminfo | grep Huge
AnonHugePages:    512000 kB  # Transparent huge pages in use
ShmemHugePages:        0 kB
HugePages_Total:     128     # Reserved huge pages
HugePages_Free:       32     # Unused reserved pages
HugePages_Rsvd:        0
Hugepagesize:       2048 kB  # 2 MB huge pages

# Potential huge page waste:
# If partially using a 2 MB page: up to ~1 MB waste per such allocation

Internal fragmentation isn't unique to paging—it occurs whenever fixed-size allocation units are used.

1. File System Blocks:

File system with 4 KB blocks:

File size: 10,300 bytes
- Blocks needed: ⌈10,300 / 4,096⌉ = 3 blocks
- Disk space used: 12,288 bytes
- Waste: 1,988 bytes

Same math as paging! File systems have internal fragmentation too.

Many small files → significant disk waste
Few large files → negligible waste

2. Network Packets:

Minimum Ethernet frame: 64 bytes

Sending 20 bytes of data:
- Actual payload: 20 bytes
- Padding required: 26 bytes (to reach minimum)
- Headers: 18 bytes
- Wire bytes: 64 bytes
- Efficiency: 20/64 = 31%

Small packets are 'internally fragmented' on the wire.

3. Heap Allocators:

malloc with size classes:

Size classes: 8, 16, 32, 64, 128, 256, 512, 1024...

malloc(100 bytes):
- Allocated: 128 bytes (next size class up)
- Waste: 28 bytes (22% overhead)

malloc(17 bytes):
- Allocated: 32 bytes
- Waste: 15 bytes (47% overhead!)

Size-class allocators trade internal fragmentation for speed.

4. Memory Alignment:

C/C++ struct alignment:

struct Example {
    char a;      // 1 byte, then 7 bytes padding
    double b;    // 8 bytes, aligned to 8-byte boundary
    char c;      // 1 byte, then 7 bytes padding
};
// sizeof(Example) = 24 bytes, but only 10 bytes of data!
// Internal fragmentation: 14 bytes (58%)

Optimized:
struct Example {
    double b;    // 8 bytes
    char a;      // 1 byte
    char c;      // 1 byte, then 6 bytes padding
};
// sizeof(Example) = 16 bytes
// Internal fragmentation: 6 bytes (37%) — better!

Lesson: Internal fragmentation from fixed-unit allocation is a universal phenomenon in computing. The paging case is particularly important but far from unique.

Internal fragmentation is paging's minor cost for eliminating external fragmentation. Let's consolidate what we've learned:

Module Complete:

With this page, we've completed our exploration of the fundamental concepts of paging:

1. Pages and Frames: The basic building blocks
2. Page Size: Trade-offs in choosing allocation granularity
3. Non-Contiguous Allocation: Freedom from the contiguity constraint
4. No External Fragmentation: A complete solution to a major problem
5. Internal Fragmentation: The acceptable cost of paging

These concepts form the foundation for understanding page tables, address translation, TLBs, multi-level paging, and virtual memory—topics we'll explore in subsequent modules.