Processes lack the authority to directly control physical hardware. Memory access is strictly governed by the CPU's Mode Bit and Privilege Level.
The CPU restricts instruction execution based on current privileges. Privileged Instructions, such as those modifying memory states or controlling external devices, can only be executed in Kernel Mode. Typical processes operate in User Mode, where hardware-level instructions for direct physical memory (RAM) access are blocked.
When a process is executed, the OS creates a Virtual Memory layout. This is a contiguous, one-dimensional logical address space granted exclusively to each process. Although it provides a linear address starting from 0x00000000 regardless of physical RAM fragmentation, mapping this address 1:1 at a byte level is architecturally unfeasible due to the astronomical size of the mapping table.
To solve this, Paging is employed. Paging divides virtual memory into fixed-size blocks called Pages (typically 4KB) and physical memory into identical blocks called Frames. Mapping information between them is stored in a Page Table, a hierarchical tree data structure.
Before the OS yields CPU control to a process, the MMU (Memory Management Unit)—the hardware address translator—is configured by setting a base register (e.g., the CR3 Register) to the physical address of that process's top-level Page Table. Subsequently, all virtual addresses generated by the process are automatically translated into physical addresses at the hardware level by the MMU.
If dynamic memory allocation is required during execution, the process cannot expand the virtual heap boundary with User Mode privileges. To bypass this, a System Call is invoked.
System Calls (e.g., sbrk, mmap) trigger a software interrupt (Trap) to temporarily elevate the CPU's privilege level to Kernel Mode. The OS, acting with kernel authority, extends the process's virtual memory range in 4KB Page increments and reserves entries in the Page Table.
Crucially, the OS does not immediately allocate physical RAM upon an expansion request; it merely marks the address as valid in the Page Table. When the process later attempts to access that virtual address, the MMU detects the absence of a mapped physical frame and triggers a Page Fault.
When the exception handler is invoked, the OS finds an empty 4KB Frame, maps it in the Page Table, and restarts the interrupted instruction. This "lazy allocation" mechanism, where physical memory is linked only upon actual access, is defined as Demand Paging.
While Demand Paging reduces physical memory waste, it introduces significant runtime overhead. Invoking a System Call and handling a Page Fault for every single variable allocation is inefficient. Furthermore, the minimum granularity of memory provided by the OS is 4KB, whereas processes often require much smaller blocks (e.g., tens of bytes).
To bridge this gap and manage overhead, a User-space Allocator is introduced. An Explicit Allocator, such as C's malloc, minimizes System Call frequency. It secures a large chunk of virtual heap space (multiples of Pages) from the OS via a single sbrk call and manages this space using its own algorithms. To optimize CPU memory access, it applies Alignment rules (e.g., 8-byte or 16-byte) when splitting or merging blocks.
Inevitably, managing memory in discrete blocks leads to Fragmentation:
-
Internal Fragmentation: Wasted space within an allocated block due to alignment rules or minimum block size constraints.
-
External Fragmentation: A state where the total free heap memory is sufficient, but because it is scattered in small, non-contiguous blocks, a large allocation request cannot be satisfied.
Ultimately, the core objective of an allocator is to maximize Throughput and Memory Utilization by avoiding expensive System Calls and optimizing internal data structures (such as Free Lists) to suppress both types of fragmentation.