7.1 Contiguous Memory Allocation: Fixed vs Dynamic Partitioning

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.1⏱️18 min read

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

💡 Core Intuition

🍳 The Everyday Analogy: The City Parking Lot

Imagine a municipal parking authority designing a parking facility for diverse vehicles (motorcycles, compact cars, delivery vans, and semi-trucks):

Architecture Flow

The Parking Allocation Strategy Pipeline

Contrasting fixed slot allocation with dynamic flexible boundaries

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

🅿️Approach A

Fixed-Size Marked Bays

Fixed Partitioning

Concrete barriers paint every parking bay into equal 20-foot spaces.

→

Alternative Policy

🚗Approach B

Open Unmarked Strip

Dynamic Partitioning

An open paved lot where attendants park each vehicle bumper-to-bumper.

→

Enforce Hardware Boundary

🚧Guard Rails

Attendant Guard Rails

Base & Limit Registers

A checkpoint barrier ensures drivers stay strictly within their allotted zones.

• Fixed Partitioning: Simple to administer, but large partitions allocated to tiny tasks squander space inside each slot.
• Dynamic Partitioning: Maximizes density on entry, but creates fragmented unallocated gaps between processes over time.
• The Operating System's Core Mandate: Provide processes with execution space while guaranteeing strict isolation through hardware-assisted memory translation.

---

💻 Bridging to Computer Science

In modern computing, execution requires loading program code and runtime data from secondary storage into Main Memory (RAM). The operating system must balance three competing physical constraints:

1. Large Capacity: Satisfying memory hungry user applications.
2. Minimal Unit Cost: Balancing economic viability per gigabyte.
3. Low Access Latency: Minimizing CPU stall cycles while fetching instructions.

Because no single physical technology simultaneously offers picosecond speeds, terabyte capacity, and minimal cost, computer architects construct a Memory Hierarchy.

The Universal Computer Memory Hierarchy

Balancing access latency, storage density, and silicon economics across computing tiers

Tier 1: < 1 ns

CPU Registers

⚡

Direct hardware execution registers located inside the CPU core. Zero bus latency.

Program CounterStack PointerGeneral Purpose Registers

↓Register-to-L1 Cache Bus

Tier 2: 1 – 10 ns

CPU SRAM Caches (L1 / L2 / L3)

🚀

On-chip SRAM arrays buffering hot instructions and working data sets.

Split L1 iCache/dCacheUnified L2 CacheShared L3 LLC

↓Integrated Memory Controller (IMC) Bus

Tier 3: 50 – 100 ns

Main Memory (Physical DRAM)

🧠

Volatile primary storage holding active process address spaces and kernel structures.

DDR4 / DDR5 DRAMKernel VFS Page CacheProcess RSS

↓PCIe / SATA Storage Controller Bus

Tier 4: 10 µs – 10 ms

Secondary Storage (NVMe / SSD / HDD)

💽

Non-volatile persistent storage housing backing filesystem binaries and swap space.

NVMe PCIe Gen 4/5NAND Flash CellsMagnetic Disk Platters

Within this hierarchy, the operating system manages Main Memory as the staging ground for CPU execution. Two fundamental disciplines govern how processes are placed in physical RAM:

• Contiguous Allocation: The process must occupy a single, continuous, uninterrupted block of physical memory addresses.
• Non-Contiguous Allocation: The process's address space can be split across scattered physical frames (Paging and Segmentation).

---

📚 Core Deep-Dive & Concepts

1. The Fundamental Principle: Locality of Reference

Program execution does not access memory uniformly or randomly. Instead, memory access patterns exhibit intense spatial and temporal concentration known as Locality of Reference:

---

2. Operating System Responsibilities in Memory Management

The operating system kernel executes three primary mandates regarding memory subsystems:

1. Address Translation & Relocation: Translating compiler-generated Logical Addresses into hardware-routable Physical Addresses dynamically at runtime.
2. Allocation & Deallocation: Deciding which processes enter RAM, determining their physical boundaries, and returning freed blocks to available pools when processes terminate.
3. Protection & Isolation: Preventing errant or malicious processes from reading or overwriting the memory of neighboring processes or kernel structures.

---

3. Hardware Relocation & Memory Protection

Under contiguous allocation, compilers emit instructions referencing Logical Addresses (relative offsets starting from $0$). When a process is loaded into RAM at physical offset $\text{Base}$, the CPU must translate these addresses at hardware wire speed.

To prevent process corruption, the Memory Management Unit (MMU) uses two hardware registers:

• Base Register (Relocation Register): Stores the smallest physical address allocated to the process.
• Limit Register: Stores the total size (range) of the process's logical address space.

Mathematical Formulation of Translation

$\text{Valid Address Condition:} \quad 0 \le \text{Logical Address} < \text{Limit}$

$\text{Physical Address} = \text{Base (Relocation Register)} + \text{Logical Address}$

If the CPU generates an address where $\text{Logical Address} \ge \text{Limit}$, the MMU halts execution and triggers a hardware protection trap to the kernel, terminating the offending process with a SIGSEGV (Segmentation Violation).

---

4. Contiguous Allocation Strategies: Fixed vs Dynamic

Strategy A: Fixed-Size (Static) Partitioning

• Mechanism: Physical RAM is divided into fixed partitions during system initialization. These partitions can be of equal size or differing fixed sizes.
• Allocation Rule: Each partition can accommodate at most one process. When a process requests memory, the OS assigns an entire partition capable of holding it.
• Multiprogramming Bound: The Degree of Multiprogramming (DoM) is strictly bounded by the total number of physical partitions ($k$). Even if large amounts of free memory exist, no more than $k$ processes can reside in memory simultaneously.
• Process Size Ceiling: If a process exceeds the size of the largest physical partition, it cannot be loaded without complex overlays.
• Pathology: Suffers severely from Internal Fragmentation. If a $5\text{ MB}$ process occupies an $8\text{ MB}$ partition, the remaining $3\text{ MB}$ inside that partition is completely idle and cannot be allocated to another process.

Strategy B: Dynamic (Variable-Size) Partitioning

• Mechanism: Memory is not divided into fixed partitions beforehand. Initially, all user memory is treated as one large contiguous free pool (a single hole).
• Allocation Rule: When a process arrives, the OS carves out exactly the amount of memory requested by that process. When a process terminates, its memory is returned to the free pool and merged with adjacent free blocks.
• Internal Fragmentation: Completely eliminated! Because a process receives exactly its requested footprint, no space is wasted inside an allocated partition.
• Pathology: Suffers from External Fragmentation. Over time, as processes of varying sizes enter and exit, memory becomes fragmented into isolated, non-contiguous free holes. Even if total free memory is large, a new process may be rejected if no single hole is big enough.

---

5. Architectural Comparison Matrix

Architectural Metric	Fixed-Size Partitioning (Static)	Dynamic Partitioning (Variable)
Partition Boundaries	Fixed at boot / OS configuration	Carved dynamically at runtime
Degree of Multiprogramming	Strictly bounded by number of partitions	Dynamic (bounded only by total available RAM)
Process Size Constraint	Limited to size of largest partition	Limited to total available physical memory
Internal Fragmentation	High (residual space inside partition wasted)	Zero (exact process size allocated)
External Fragmentation	Absent (partitions are dedicated units)	Severe (scattered holes over runtime)
Implementation Complexity	Trivial (bitmap or partition table)	Moderate (linked list of free holes, merging logic)
Hardware Overhead	Minimal base/limit checking	Continuous base/limit updates, coalescing logic

---

🏭 In The Real World: Production Case Study

Bare-Metal Microcontrollers & Embedded RTOS (FreeRTOS)

Modern general-purpose operating systems (Linux, Windows, macOS) use hardware paging. However, resource-constrained embedded systems and real-time operating systems (RTOS) frequently use contiguous memory allocation for deterministic latency and lack of MMU hardware:

FreeRTOS Embedded Heap Allocation Schemes

Deterministic memory allocators for resource-constrained embedded microcontrollers

🔒

heap_1.c

Static Sequential

• Allocates memory sequentially from an array without ever freeing it.
• Deterministic: Completely immune to fragmentation and memory leaks in certified safety systems.

Key Abstractions / Calls

pvPortMalloc()

📐

heap_2.c

Best-Fit Pool

• Maintains a linked list of free blocks and allocates using best-fit heuristics.
• Does not coalesce adjacent free blocks, leaving it vulnerable to external fragmentation.

Key Abstractions / Calls

vPortFree()

🔄

heap_4.c

Dynamic Coalescing

• First-fit allocator with automatic adjacent free-block coalescing.
• Industry standard for general embedded firmware with fluctuating runtime allocations.

Key Abstractions / Calls

prvInsertBlockIntoFreeList()

🌐

heap_5.c

Multi-Bank Spanning

• Extends heap_4 to span multiple disjoint physical RAM banks (e.g. internal SRAM and external SDRAM).
• Crucial for high-end microcontrollers with disparate memory buses.

Key Abstractions / Calls

vPortDefineHeapRegions()

1. Deterministic Guarantees:
   • In aerospace avionics and automotive brake controllers, page fault delays ($10\text{ ms}$) are intolerable.
   • Systems allocate contiguous physical memory blocks statically during startup, guaranteeing zero dynamic allocation failures and bounded access latency ($< 50\text{ ns}$).
2. FreeRTOS heap_4.c Dynamic Partitioning:
   • Manages an array of heap bytes as dynamic contiguous partitions.
   • When blocks are released (vPortFree), the allocator automatically coalesces adjacent free blocks into a single larger block, mitigating external fragmentation in embedded telemetry loops.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: A system uses base and limit registers for contiguous memory allocation. A process has a base register set to 300040 and a limit register set to 120900. Determine whether the following CPU-generated logical addresses are valid, and calculate their corresponding physical addresses:

1. Logical Address: 45000
2. Logical Address: 120900
3. Logical Address: 125000

Answer:

1. For Logical Address 45000:
   • Check condition: $\text{Logical Address} < \text{Limit} \implies 45000 < 120900$ (True $\implies$ Valid).
   • $\text{Physical Address} = \text{Base} + \text{Logical Address} = 300040 + 45000 = \mathbf{345040}$.
2. For Logical Address 120900:
   • Check condition: $\text{Logical Address} < \text{Limit} \implies 120900 < 120900$ (False! Valid addresses run from $0$ to $\text{Limit} - 1$).
   • Result: Invalid Address. The MMU trips a hardware trap (Memory Protection Violation / Segmentation Fault).
3. For Logical Address 125000:
   • Check condition: $125000 < 120900$ (False).
   • Result: Invalid Address (Trap triggered).

---

Question 2: Explain why dynamic partitioning suffers from external fragmentation while fixed partitioning suffers primarily from internal fragmentation. Answer:

1. Fixed Partitioning: Memory is split into pre-sized partitions before processes arrive. When a process of size $S$ is allocated to a partition of size $P$ ($P \ge S$), the unused remainder $P - S$ is locked inside that partition. No other process can utilize it, creating internal fragmentation.
2. Dynamic Partitioning: Memory is carved to the exact size requested by incoming processes ($P = S$), so internal fragmentation is zero. However, when processes terminate in arbitrary order, the freed contiguous regions leave gaps ("holes"). As new processes of different sizes take parts of these holes, tiny unallocated slivers are left behind across RAM. The aggregate free space may exceed a new process's requirement, but because the free space is not contiguous, the request fails. This is external fragmentation.

Common Interview Traps

• The Strict Inequality Trap: Remember that $\text{Logical Address} < \text{Limit Register}$ is a strict inequality. If the limit register is $1000$, valid logical addresses are $0, 1, 2, \dots, 999$. An address of $1000$ represents an off-by-one illegal reference!
• Confusing Relocation Register with Page Table: The base/relocation register adds a single linear offset to the entire contiguous address space. It does not perform chunk-by-chunk lookup or page table traversal.
• Degree of Multiprogramming Misconception: In fixed partitioning, if you have 8 partitions and 100 MB of total RAM, and only 8 processes of size 1 MB are running, you cannot load a 9th process even though 92 MB of RAM is theoretically idle. The number of partitions strictly caps the degree of multiprogramming.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic6.5 The exec() Family of System CallsNext Topic →7.2 Internal vs External Fragmentation