Memory Management Techniques: Allocation, Paging, and Segmentation

Memory management encompasses the mechanisms operating systems and runtime environments use to allocate, track, reclaim, and protect physical and virtual address spaces across competing processes. The three foundational techniques — allocation strategies, paging, and segmentation — define how hardware and software cooperate to create the illusion of abundant, isolated memory even when physical resources are constrained. Failures in memory management account for a substantial share of system vulnerabilities, including buffer overflows and use-after-free exploits catalogued by MITRE's Common Weakness Enumeration (CWE) as CWE-119 and CWE-416 respectively. Understanding the structural distinctions among these techniques is essential for systems programmers, OS architects, embedded engineers, and security analysts operating across the full memory systems landscape.

• Definition and scope
• Core mechanics or structure
• Causal relationships or drivers
• Classification boundaries
• Tradeoffs and tensions
• Common misconceptions
• Checklist or steps (non-advisory)
• Reference table or matrix
• References

Definition and scope

Memory management is the OS subsystem responsible for controlling and coordinating computer memory — specifically, the assignment of blocks called regions or segments to processes upon request and their return to a free pool upon release. The scope covers both physical memory management (direct control of DRAM addresses) and virtual memory management (the abstraction layer that maps logical addresses to physical ones).

Three techniques constitute the canonical architecture of memory management as described in the NIST SP 800-82 Rev. 3, Guide to Operational Technology Security and formalized in IEEE and ISO/IEC operating systems literature:

• Allocation — partitioning available memory into blocks and assigning them to requesting processes.
• Paging — dividing both physical memory and virtual address space into fixed-size units (pages and frames) to enable non-contiguous placement.
• Segmentation — dividing programs into variable-size logical units (segments) that reflect the natural structure of the program (code, stack, heap, data).

These techniques are not mutually exclusive. Modern 64-bit operating systems — including Linux kernel versions documented by the Linux Kernel Documentation Project — typically combine paging with limited segmentation in a hybrid architecture.

Core mechanics or structure

Allocation

Memory allocation operates at two levels: physical (allocator manages real DRAM pages) and logical (allocator manages virtual address regions). The three classical physical allocation strategies are:

1. First-fit — allocates the first free block of sufficient size. Average search time is O(n/2) for n free blocks.
2. Best-fit — scans all free blocks and allocates the smallest sufficient block, minimizing waste per allocation but maximizing fragmentation accumulation over time.
3. Worst-fit — selects the largest available block, leaving the largest residual fragment, which can reduce fragmentation for variable-size requests.

Dynamic memory allocators (e.g., malloc/free in C) implement these strategies in user space. The GNU C Library (glibc) uses a variant of the ptmalloc2 allocator, which maintains per-thread arenas and employs boundary-tag coalescing to merge adjacent free blocks.

Paging

Paging eliminates the requirement that a process's memory reside contiguously in physical RAM. The virtual address space is divided into fixed-size pages; physical memory is divided into frames of identical size. On x86-64 architectures the default page size is 4 KB, though Linux supports huge pages of 2 MB and 1 GB via the HugeTLB mechanism (Linux kernel documentation, hugetlbpage.rst).

Address translation proceeds through a page table, a data structure mapping virtual page numbers (VPNs) to physical frame numbers (PFNs). On x86-64, this table is a 4-level radix tree consuming up to 512 GB of virtual address space per level, with the CR3 register pointing to the page global directory (PGD).

The Translation Lookaside Buffer (TLB) caches recent VPN→PFN translations in hardware. A TLB miss forces a page table walk, costing 10–100 CPU cycles depending on cache residency (Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A).

Segmentation

Segmentation assigns each logical region of a program — code, initialized data, BSS, heap, stack — its own descriptor containing a base address, limit, and access permissions. On x86 processors, the Global Descriptor Table (GDT) and Local Descriptor Table (LDT) store these segment descriptors; the segment registers (CS, DS, SS, ES) hold selectors indexing into these tables.

Modern 64-bit Linux and Windows largely neutralize segmentation for user-space processes by setting segment bases to 0 and limits to the full address space, effectively flattening segmentation into a pure paging model. Segmentation remains architecturally active in embedded systems and real-time operating systems (RTOS) where logical memory regions map directly to hardware-protected zones. The AUTOSAR Adaptive Platform specification mandates memory protection units (MPUs) that enforce segment-level isolation in automotive-grade systems.

Causal relationships or drivers

Four hardware and software forces drive the design choices in memory management:

1. Physical memory scarcity — when total process working sets exceed installed DRAM (e.g., 64 GB), the OS must page to secondary storage, introducing microsecond-to-millisecond latency penalties. This is a primary driver toward virtual memory systems architectures.
2. Address space isolation requirements — security mandates (e.g., NIST SP 800-53 Rev. 5, Control SC-3 on security function isolation) require each process to operate in a private virtual address space enforced at the MMU level.
3. Fragmentation accumulation — repeated allocation and deallocation produces gaps (external fragmentation with variable-size allocators, internal fragmentation with fixed-size allocators), degrading effective memory utilization over time.
4. Processor architecture constraints — the x86 segmented architecture (retained in protected mode) and ARM's MPU-only model create divergent implementation paths that OS designers must accommodate.

The relationship between memory bottlenecks and solutions is directly tied to how well these allocation and translation mechanisms are tuned to workload access patterns.

Classification boundaries

Memory management techniques are classified along three primary axes:

By granularity: Fixed-size (paging) vs. variable-size (segmentation, explicit allocation). Fixed granularity simplifies bookkeeping but introduces internal fragmentation; variable granularity matches program structure but produces external fragmentation.

By address space type: Physical address management (allocators, buddy systems) vs. virtual address management (paging, segmentation).

By initiating agent: Hardware-driven (MMU enforces page and segment boundaries automatically) vs. software-driven (explicit malloc/free or arena-based allocators controlled by the runtime).

By scope within the memory hierarchy: Page management operates across DRAM and swap storage; cache management (a distinct layer) operates between L1/L2/L3 SRAM caches and DRAM and is governed by hardware replacement policies rather than OS allocation logic.

Tradeoffs and tensions

Paging vs. segmentation: Paging simplifies physical allocation and eliminates external fragmentation but destroys the logical structure of programs, complicating debugging and access-control granularity. Segmentation preserves logical structure and enables per-region permissions but reintroduces external fragmentation.

Page size selection: Larger pages (2 MB huge pages) reduce TLB pressure and improve TLB hit rate for large working sets but increase internal fragmentation and worsen memory over-commitment for small allocations. Linux performance measurements cited by the Linux Kernel Mailing List (LKML) archives show throughput gains of 5–15% for database workloads when huge pages replace 4 KB pages, while memory-constrained environments may regress by a similar margin.

Eager vs. lazy allocation: Linux employs overcommit by default — the kernel grants virtual memory pages without backing them with physical frames until first access (demand paging). This reduces resident set sizes but introduces OOM (Out of Memory) killer events when physical pressure peaks, terminating processes without application-level warning.

Compaction overhead: Copying garbage collectors (used in JVM and .NET CLR) compact heap allocations to eliminate fragmentation but require stop-the-world pauses measured in milliseconds for heaps above 10 GB — a direct operational tension in latency-sensitive systems.

Security represents a separate tension axis: ASLR (Address Space Layout Randomization), required by NIST SP 800-53 Rev. 5, Control SI-16, randomizes segment and page base addresses to defeat return-oriented programming (ROP) attacks, but it reduces TLB locality, measurably increasing translation overhead on high-throughput workloads.

Common misconceptions

Misconception 1: Virtual memory equals disk swapping.
Virtual memory is the abstraction of a unified address space independent of physical storage medium. Swapping (paging to disk) is one mechanism the OS may use to back virtual pages when DRAM is exhausted. Systems with sufficient DRAM may use virtual memory without any swap activity.

Misconception 2: Paging eliminates fragmentation.
Paging eliminates external fragmentation at the page level but introduces internal fragmentation within pages. A process allocating 4,097 bytes with a 4 KB page size consumes 2 full pages, wasting 4,095 bytes.

Misconception 3: Segmentation is obsolete.
While flat memory models dominate on x86-64 Linux, segmentation remains the primary isolation primitive on ARM Cortex-M processors using MPUs, on AUTOSAR RTOS environments, and in WebAssembly's linear memory model, which enforces a single-segment boundary per module instance.

Misconception 4: malloc returns physical memory.
malloc returns a virtual address. Physical backing is deferred until the page is first written (demand paging). A 1 GB malloc succeeding does not mean 1 GB of DRAM has been reserved; it means 1 GB of virtual address space has been mapped.

Checklist or steps (non-advisory)

The following sequence describes the operational phases a process and OS kernel traverse during memory allocation under a paged virtual memory system:

1. Process issues allocation request — via malloc, mmap, or equivalent syscall.
2. Kernel checks virtual address space — identifies a free VMA (Virtual Memory Area) in the process's address map via vm_area_struct (Linux) or equivalent.
3. Kernel creates or extends VMA — marks the range as allocated with appropriate permissions (read/write/execute flags per segment type).
4. Physical frame assignment deferred — page table entries marked not-present; physical frames are not assigned at this stage (demand paging).
5. Process accesses allocated address — CPU generates a page fault (interrupt vector 14 on x86).
6. Page fault handler invoked — kernel identifies the faulting VPN, allocates a physical frame from the free list, and zeroes it (security requirement per NIST SP 800-53, Control SC-4).
7. Page table entry updated — VPN mapped to assigned PFN; present bit set; access bits initialized.
8. TLB loaded — hardware or software TLB reload makes the mapping active.
9. Faulting instruction restarted — process resumes transparently.
10. Deallocation — free or munmap marks VMA as released; physical frames returned to free list; TLB entries invalidated via TLB shootdown IPI on multi-core systems.

Reference table or matrix

The memory isolation techniques applied at the OS level build directly on the boundaries established by these allocation and translation mechanisms. For performance implications specific to cache interactions, the treatment at cache memory systems addresses how page size and allocation locality affect L1/L2 hit rates. Memory optimization strategies covers workload-specific tuning decisions derived from these structural foundations.

References

• NIST SP 800-53 Rev. 5 — Security and Privacy Controls for Information Systems and Organizations
• NIST SP 800-82 Rev. 3 — Guide to Operational Technology (OT) Security
• Linux Kernel Documentation — Memory Management
• Linux Kernel Documentation — HugeTLB Pages
• GNU C Library Manual — Memory Allocation
• MITRE CWE — CWE-119: Improper Restriction of Operations within the Bounds of a Memory Buffer
• MITRE CWE — CWE-416: Use After Free
• Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A
• AUTOSAR Adaptive Platform Specification