Home/Learn/Operating Systems/Internal vs External Fragmentation

Internal vs External Fragmentation

Beginner

Memory Management

Internal fragmentation is wasted space inside an allocated block; external fragmentation is free memory that exists but is too scattered to satisfy large allocation requests.

Overview

Fragmentation is any memory that cannot be usefully used. Internal fragmentation occurs when the allocator gives a larger block than requested — the unused portion inside the allocation is wasted. Paging inherently causes internal fragmentation: if a process needs 4097 bytes, it gets two 4 KB pages — 4095 bytes are wasted in the second page. External fragmentation occurs when many small free holes are scattered across memory with no single contiguous block large enough to satisfy a request, even though total free memory is sufficient. Segmentation suffers from external fragmentation. Solutions: compaction (move all used memory together — expensive), coalescing (merge adjacent free blocks), the buddy system (power-of-2 allocations that merge easily), and the slab allocator (Linux kernel — pre-allocates fixed-size object caches). Java GC collectors exhibit the same trade-offs: CMS (non-compacting) → external fragmentation in old gen; G1/ZGC (compacting) → avoid external fragmentation at GC cost.

Internal vs External Fragmentation Illustrated

Imagine a parking lot (RAM) where each space is 4 metres wide (page size). If a car is 3 metres wide (actual request), 1 metre is wasted per space — internal fragmentation. External fragmentation is like having 10 separate 1-metre gaps throughout the lot — a bus (large allocation) cannot fit even though 10 metres of space exist in total.

Java — internal fragmentation (paging) and external fragmentation example

// Internal fragmentation: paging rounds up to page size
int PAGE_SIZE = 4096;  // 4 KB

int actualRequest = 4097;  // bytes needed
int pagesNeeded   = (int) Math.ceil((double) actualRequest / PAGE_SIZE);  // 2 pages
int allocated     = pagesNeeded * PAGE_SIZE;     // 8192 bytes allocated
int wasted        = allocated - actualRequest;   // 4095 bytes wasted inside!

System.out.printf("Requested:  %d bytes%n", actualRequest);
System.out.printf("Allocated:  %d bytes (%d pages)%n", allocated, pagesNeeded);
System.out.printf("Internal fragmentation: %d bytes (%.1f%% waste)%n",
    wasted, 100.0 * wasted / allocated);

// External fragmentation: free memory exists but not contiguous
// Memory map (block sizes in KB): [FREE:4][USED:8][FREE:2][USED:16][FREE:6][USED:4][FREE:3]
int[] freeBlocks = {4, 2, 6, 3};  // KB
int totalFree = Arrays.stream(freeBlocks).sum();  // 15 KB total free
int needed = 8;  // 8 KB request
boolean canSatisfy = Arrays.stream(freeBlocks).anyMatch(b -> b >= needed);
System.out.printf("%nTotal free: %d KB, largest block: %d KB%n",
    totalFree, Arrays.stream(freeBlocks).max().getAsInt());
System.out.printf("Can satisfy %d KB request: %b  (external fragmentation = %b)%n",
    needed, canSatisfy, !canSatisfy);

Java GC and Fragmentation: G1GC Compaction

The Java heap exhibits both fragmentation types. Object allocation in the young generation is bump-pointer (no fragmentation). After many GC cycles, the old generation accumulates differently-sized holes (external fragmentation). CMS left old gen uncompacted, causing promotion failures. G1GC divides the heap into 1–32 MB regions and compacts during mixed GC collections, relocating live objects to pack regions. ZGC and Shenandoah compact concurrently without stop-the-world pauses.

Java — G1GC compaction after fragmentation, monitoring with MemoryMXBean

// Forcing GC and observing heap compaction effect
MemoryMXBean memBean = ManagementFactory.getMemoryMXBean();

System.out.println("=== Before GC ===");
MemoryUsage before = memBean.getHeapMemoryUsage();
System.out.printf("Heap used: %d MB / committed: %d MB%n",
    before.getUsed() / 1_048_576, before.getCommitted() / 1_048_576);

// Create many short-lived objects to fragment old gen
List<byte[]> refs = new ArrayList<>();
for (int i = 0; i < 10_000; i++) {
    refs.add(new byte[1024]);      // 1 KB objects
    if (i % 3 == 0) refs.remove(0);  // release every 3rd → leaves holes
}

System.gc();  // hint — G1GC will compact during this collection
Thread.sleep(200);

System.out.println("
=== After GC (G1 compacted) ===");
MemoryUsage after = memBean.getHeapMemoryUsage();
System.out.printf("Heap used: %d MB / committed: %d MB%n",
    after.getUsed() / 1_048_576, after.getCommitted() / 1_048_576);

// G1GC JVM flags:
// -XX:+UseG1GC -XX:G1HeapRegionSize=4m -XX:MaxGCPauseMillis=200

Key Points to Remember

1Internal fragmentation: wasted space inside an allocated block — paging causes this (page larger than request).
2External fragmentation: total free memory sufficient but no single contiguous block large enough.
3Paging eliminates external fragmentation; segmentation suffers from it.
4Compaction solves external fragmentation by relocating objects — expensive (stop-the-world or concurrent).
5G1GC and ZGC compact the Java heap to avoid promotion failures from old-gen fragmentation.
6Buddy system: power-of-2 allocations enable O(1) coalescing — used in Linux kernel page allocator.

Interview Questions

What is the difference between internal and external fragmentation?

EasyAmazon

Why does paging eliminate external fragmentation but introduce internal fragmentation?

EasyFlipkart

How does G1GC address heap fragmentation differently from CMS?

MediumNetflix

What is the buddy system and how does it reduce external fragmentation?

HardGoogle

Ask Aria about Internal vs External Fragmentation

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Thrashing

Contiguous Memory Allocation Strategies