Memory Fragmentation: Internal vs. External Fragmentation

In modern Memory Management, the efficiency of physical memory (RAM) utilization is a primary performance bottleneck. As the operating system (OS) dynamically loads and terminates processes, physical memory is continuously allocated and deallocated. Over time, this dynamic allocation cycle leads to a phenomenon known as Fragmentation. []

Fragmentation refers to the condition where physical memory becomes broken into small, non-contiguous pieces, rendering a portion of the system's memory capacity unusable. Even if the total amount of free memory is mathematically sufficient to run a process, the system may fail to allocate memory because the free space is not contiguous or is trapped within already allocated blocks. []

Memory allocation strategies generally fall into two categories: Fixed Partitioning (where memory is split into static, predetermined blocks) and Dynamic Partitioning (where memory is allocated on-demand based on process size). These two paradigms suffer from different types of fragmentation:

1. Internal Fragmentation: Occurs when memory is allocated in fixed-size blocks. If a process requires less memory than the block size, the remaining space within that block is wasted and cannot be used by other processes. []
2. External Fragmentation: Occurs when memory is allocated dynamically. As processes finish and leave, they create "holes" of free memory. Although the aggregate free space across all holes may be large, it is scattered in non-contiguous chunks, making it impossible to satisfy a single large memory request. []

The diagram below illustrates how both forms of fragmentation manifest in physical memory:

Mathematical Formulations of Fragmentation

To analyze fragmentation quantitatively, we can define formal mathematical models for both types of memory waste.

1. Internal Fragmentation

Let $S_{partition}$ represent the fixed size of an allocated memory block or partition, and let $S_{process}$ represent the actual memory requested by a process. If the partition is assigned to this process, then:

$S_{partition} \ge S_{process}$

The resulting internal fragmentation $F_{internal}$ within that partition is defined as:

$F_{internal} = S_{partition} - S_{process}$

If a system contains $M$ active partitions, each holding a process of size $S_{process, i}$ within a partition of size $S_{partition, i}$, the total internal fragmentation $F_{total\_internal}$ is the sum of the individual wastes: []

$F_{total\_internal} = \sum_{i=1}^{M} (S_{partition, i} - S_{process, i})$

2. External Fragmentation

Let physical memory contain $n$ scattered, non-contiguous free blocks (holes), where the size of the $i$-th free block is $s_i$. The total available free memory $S_{free}$ is: []

$S_{free} = \sum_{i=1}^{n} s_i$

If a new process requests a contiguous chunk of memory of size $S_{req}$, external fragmentation occurs when:

$S_{free} \ge S_{req} \quad \text{and} \quad s_i < S_{req} \quad \forall \ i \in \{1, 2, \dots, n\}$

In this scenario, the system has enough total free memory to satisfy the request, but because no individual free block $s_i$ is large enough, the process cannot be loaded. []