Fragmentation
Fragmentation refers to the inefficient use of memory that occurs when available memory is broken into small or unusable pieces. It is typically classified into two types:
Internal Fragmentation
External Fragmentation
Internal Fragmentation
Definition: Internal fragmentation occurs when a fixed-sized memory block is allocated to a process, but the process does not use all the allocated memory. The unused space inside the block is wasted and cannot be used by other processes.
Example:
A process requests 33 bytes.
The system allocates a 64-byte block (nearest power of two).
31 bytes go unused — this is internal fragmentation.
Causes:
Fixed block allocation (e.g., Buddy System, slab allocation).
Memory is allocated in larger-than-necessary chunks.
Impact:
Wasted memory within allocated regions.
May seem like enough memory is available, but it's locked within oversized allocations.
External Fragmentation
Definition: External fragmentation occurs when free memory is split into small non-contiguous blocks scattered throughout the system. Even though total free memory might be sufficient for a request, there is no single block large enough to satisfy it.
Example:
After multiple allocations and deallocations, free blocks are scattered.
A 100-byte allocation is requested, but free blocks are 40 + 30 + 30 bytes.
Despite 100 bytes being free in total, allocation fails.
Causes:
Variable-sized memory allocation.
Random order of allocation/deallocation.
Impact:
Leads to failed allocations even when sufficient total memory is technically free.
How the Buddy System Addresses Fragmentation
The Buddy System is a memory allocation technique designed to reduce external fragmentation, but it introduces some internal fragmentation as a trade-off.
How it Works:
Memory is divided into blocks of size 2^k.
When a request is made, the nearest power-of-two block is allocated.
If the block is too large, it is split recursively into halves (buddies).
When blocks are freed, buddies are merged to form larger blocks.
Fragmentation Behavior:
Reduces External Fragmentation: Merging of buddy blocks helps defragment memory efficiently.
Incur Internal Fragmentation: Because memory is always allocated in powers of two, unused space inside blocks is common.
Example:
Request for 35 bytes → 64-byte block allocated.
29 bytes go unused → internal fragmentation.
Later, if the buddy of this 64-byte block is freed, they merge into a 128-byte block → reducing external fragmentation.
Summary Table
Type of Fragmentation
Definition
Common In
Impact
Internal
Unused space within allocated memory blocks
Buddy System, slab
Wasted but reserved space
External
Unused space between free memory blocks
Variable-size allocators
Prevents large block allocation
Last updated