7.2 Internal vs External Fragmentation

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.2⏱️16 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Memory Allocators

💡 Core Intuition

🍳 The Everyday Analogy: The Moving Boxes Dilemma

Imagine packing personal belongings into moving boxes for a cross-country relocation:

Architecture Flow

The Moving Boxes Storage Pipeline

Contrasting trapped box volume with uncombinable room floor space

💡 Hover or click any card for deep-dive operational details

📦Pre-Sized Crates

Standardized 10-Gallon Crates

Fixed Allocation Partition

You pack a small desk lamp (3 gallons) into a mandatory 10-gallon crate.

→

Contrast With Floor Gaps

🚚Floor Gaps

Truck Cargo Floor Gaps

Scattered External Holes

Boxes of arbitrary shapes are stacked in the moving truck.

→

Resolve The Bottleneck

🔄Reorganization

Consolidation & Re-Packing

Compaction / Paging

Unload and slide all boxes forward to unify floor space, or disassemble items into standardized blocks.

• Internal Fragmentation: Wasted space trapped inside an allocated container because the container was larger than the object.
• External Fragmentation: Free space scattered outside containers across memory in disconnected pockets, rendering it impossible to fulfill a large contiguous request.

---

💻 Bridging to Computer Science

Memory fragmentation represents one of the most critical inefficiencies in system architecture. Every byte of RAM lost to fragmentation is a byte unavailable for active compute workloads, disk caches, or process thread stacks.

---

📚 Core Deep-Dive & Concepts

1. Internal Fragmentation: Definition & Mechanics

Internal Fragmentation occurs when memory is allocated in fixed-size blocks or partitions, and a process requests an amount of storage smaller than the allocated block.

Mathematical Formulation

For a set of $n$ active partitions $\{P_1, P_2, \dots, P_n\}$ where partition $P_i$ has physical capacity $S(P_i)$, and the hosted process requests memory $R(P_i) \le S(P_i)$:

$\text{Internal Fragmentation in Partition } i = S(P_i) - R(P_i)$

$\text{Total Internal Fragmentation } = \sum_{i=1}^{n} \Big( S(P_i) - R(P_i) \Big)$

Key Characteristics

1. Occurs Exclusively in Fixed-Size Allocations: Occurs in fixed-size memory partitioning, paging systems (on the terminal page of a process), and power-of-two slab allocators.
2. Zero Internal Fragmentation in Pure Dynamic Partitioning: Because dynamic partitioning carves out exactly $R(P_i)$ bytes from unallocated RAM, $S(P_i) - R(P_i) = 0$.
3. Internal Waste is Non-Reclaimable: The unused space is legally owned by the occupying process. The operating system cannot assign that remaining sliver to another process without violating memory isolation.

---

2. External Fragmentation: Definition & Mechanics

External Fragmentation occurs in contiguous memory allocation schemes when dynamic process arrivals and departures leave physical memory broken into scattered, non-contiguous free holes.

Formal Definition

A memory state exhibits external fragmentation if:

$\sum_{j=1}^{m} \text{Size}(\text{FreeHole}_j) \ge \text{Process Request } R_{\text{new}}$

$\text{Yet for all } j \in \{1, 2, \dots, m\}: \quad \text{Size}(\text{FreeHole}_j) < R_{\text{new}}$

The total aggregate free memory across physical RAM is strictly greater than or equal to the requested memory, but because contiguous allocation mandates a single unbroken address range, the operating system cannot fulfill the allocation.

The 50-Percent Rule (Knuth's Derivation)

In dynamic storage allocation systems utilizing first-fit or best-fit policies, statistical equilibrium leads to a fundamental relationship discovered by Donald Knuth:

$\text{Number of Free Holes } \approx \frac{1}{2} N$

Where $N$ represents the number of allocated process blocks in steady state.

• Consequence: Roughly one-third of all memory can be lost to external fragmentation ($1$ hole for every $2$ allocated blocks). If an OS maintains $N$ active processes, approximately $0.5 N$ non-contiguous holes litter the address space.

---

3. Comprehensive Comparison Matrix

---

4. Overcoming External Fragmentation: Compaction

The primary method to resolve external fragmentation within a contiguous allocation architecture is Compaction (also called memory defragmentation or garbage collection):

Memory Compaction & Relocation Phases

Consolidating scattered free holes into a single contiguous pool via dynamic relocation

1

Fragmented Initial State

Scattered Holes

Total free memory equals 200 MB (Hole 1 = 80 MB, Hole 2 = 120 MB). Process P4 requests 180 MB contiguous space and stalls due to external fragmentation.

2

Pipeline Freeze & Base Relocation

Execution Halted

Kernel freezes CPU scheduling. Relocates Process P2 downward by 80 MB and Process P3 downward by 200 MB across the memory bus.

3

PCB Hardware Register Updates

MMU Reconfiguration

Operating system updates the hardware Base / Relocation registers inside the Process Control Blocks (PCBs) for P2 and P3.

4

Unified Contiguous Free Pool

Unblocked Allocation

All active processes packed tightly against low memory; unified 200 MB contiguous hole created. Process P4 (180 MB) allocated seamlessly.

Prerequisites & Massive Overhead of Compaction

1. Dynamic Execution-Time Relocation Required: Compaction is impossible if address binding occurs at compile time or load time (static binding). It is strictly feasible only if the architecture supports dynamic hardware relocation where the MMU computes $\text{Physical Address} = \text{Base Register} + \text{Logical Address}$.
2. CPU Bus Overhead: Compaction requires reading every single byte of an active process from DRAM and writing it to new physical DRAM locations across the system memory bus.
   • For a system moving $16\text{ GB}$ of RAM over a memory bus running at $25.6\text{ GB/s}$, memory compaction introduces hundreds of milliseconds of complete CPU pipeline freeze.
   • For interactive and real-time systems, this latency spike is intolerable.
3. The Architectural Alternative: Eliminate contiguous allocation entirely! By introducing Paging, the operating system permits a process to reside in non-contiguous physical frames, permanently destroying external fragmentation without moving a single byte of memory.

---

🏭 In The Real World: Production Case Study

Linux Kernel SLAB / SLUB Allocator & High-Speed Caches

The Linux kernel faces intense fragmentation pressures when allocating internal structures (such as task_struct, mm_struct, and file descriptors):

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Consider a dynamic memory partitioning system where memory holes are currently available in the following order: $100\text{ KB}$, $500\text{ KB}$, $200\text{ KB}$, $300\text{ KB}$, and $600\text{ KB}$. A new process requests $210\text{ KB}$.

1. Can the request be satisfied by a single hole?
2. If instead of single holes, the system had three processes requesting $250\text{ KB}$, $350\text{ KB}$, and $450\text{ KB}$ simultaneously, and total free space is $1700\text{ KB}$, describe the condition under which external fragmentation prevents allocation.

Answer:

1. Yes. The hole of $500\text{ KB}$ or $300\text{ KB}$ or $600\text{ KB}$ can easily satisfy the $210\text{ KB}$ request.
2. The total free memory is $100 + 500 + 200 + 300 + 600 = 1700\text{ KB}$.
   • The total memory demanded by the three processes is $250 + 350 + 450 = 1050\text{ KB}$.
   • Even though $1700\text{ KB} > 1050\text{ KB}$ (an excess of $650\text{ KB}$ free RAM), if available individual holes cannot contiguously accommodate each process due to order of allocation, one or more processes will be starved. This failure to allocate despite ample total free memory is external fragmentation.

---

Question 2: True or False: Paging completely eliminates all forms of fragmentation. Justify your answer. Answer: False. While paging completely eliminates external fragmentation (because any logical page can be placed into any available physical frame, regardless of contiguity), paging still suffers from internal fragmentation.

• Specifically, the final page of a process rarely requires an exact multiple of the page size.
• If a process requires $8193$ bytes and the page size is $4096$ bytes ($4\text{ KB}$), the process is allocated $\lceil 8193 / 4096 \rceil = 3$ pages ($12288$ bytes).
• The third page uses only $1$ byte, leaving $4095$ bytes idle inside that frame as internal fragmentation. On average, internal fragmentation in paging is $\frac{1}{2} \times \text{Page Size}$ per process.

Common Interview Traps

• The Dynamic Partitioning Myth: Never claim that dynamic partitioning suffers from internal fragmentation. Because partitions are custom carved to the process's requested byte boundary, internal fragmentation is identically zero.
• The Static Relocation Trap: Compaction is strictly prohibited in systems using compile-time or load-time address binding. Why? Because instructions in machine code hold hardcoded absolute physical addresses; shifting a process's bytes to another physical memory range will corrupt every pointer, jump instruction, and function call! Only systems with dynamic runtime hardware relocation (MMU base register) can perform compaction.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.1 Contiguous Memory AllocationNext Topic →7.3 Dynamic Storage Allocation Algorithms