Memory Management in Operating Systems Explained

Memory management is arguably the operating system’s most performance-critical function. It must allocate limited physical memory among competing processes, enforce isolation (preventing one process from reading another’s data), and provide the abstraction of virtual memory — giving every process the illusion of a large, private, contiguous address space. The quality of memory management directly determines system throughput, responsiveness, and the number of concurrent processes that can run without thrashing.

The Physical Memory Abstraction Problem

Without an abstraction layer, programs would need to coordinate physical memory usage explicitly. Early batch systems loaded one program at a time into physical memory starting at address 0. This was simple but made multiprogramming impossible — two programs could not reside in memory simultaneously because their address spaces would overlap.

The solution evolved in stages. Base and limit registers (IBM System/360, 1964) allowed two processes to coexist: each process was loaded into a contiguous physical region, and the CPU translated every memory access by adding the process’s base register and checking against the limit register. Swapping moved entire processes between memory and disk to increase multiprogramming. The fundamental limitation was that each process still required a contiguous physical allocation, leading to fragmentation.

Virtual Memory and the MMU

Virtual memory decouples the addresses a program sees (virtual addresses) from the addresses the hardware uses (physical addresses). Each process has its own complete virtual address space — 48 bits (256 TB) on x86-64, or 57 bits (128 PB) with 5-level paging on recent CPUs. The Memory Management Unit (MMU), a hardware component integrated into the CPU, translates every virtual address to its corresponding physical address on each memory access.

The translation is invisible to the running program. The program uses addresses from 0 to its maximum virtual address; the MMU and the OS conspire to map those addresses to physical frames. This provides:

• Isolation: Process A’s virtual address X maps to physical frame Y; Process B’s virtual address X maps to physical frame Z. Neither process can access the other’s physical memory.
• Simplified linking: All programs can assume they start at address 0 or a standard base address, regardless of where they are actually loaded in physical memory.
• Efficient memory use: Only the currently needed portions of a process’s address space need to occupy physical RAM. The rest can reside on disk.

Paging

Paging divides virtual memory into fixed-size pages (typically 4 KB on x86-64) and physical memory into frames of the same size. A page table maps each virtual page to a physical frame. When a process accesses a virtual address, the MMU splits it into a virtual page number (VPN) and an offset. The page table is consulted to find the corresponding physical frame number (PFN), and the physical address is constructed as (PFN × page_size + offset).

Multi-Level Page Tables

A flat page table for a 48-bit virtual address space with 4 KB pages would require 2^36 entries per process — 512 GB of page table memory per process with 8-byte entries. This is obviously impractical. Multi-level page tables solve the problem by making page table structure sparse: only the levels that cover allocated virtual memory regions are stored.

The x86-64 architecture uses 4-level paging (PML4, PDPT, PD, PT) with 4 KB pages:

• Level 4 (PML4): 512 entries, each covering 512 GB
• Level 3 (PDPT): 512 entries, each covering 1 GB
• Level 2 (PD): 512 entries, each covering 2 MB
• Level 1 (PT): 512 entries, each covering 4 KB

Only allocated entries at each level consume memory. A process using 8 MB of memory requires a PML4 entry (one 4 KB page), two PDPT entries (one 4 KB page with two valid entries), 4 PD entries (one 4 KB page), and 1024 PT entries (16 4 KB pages) — approximately 19 pages (76 KB) for page tables, rather than 512 GB.

On CPUs with 5-level paging (Intel Ice Lake and later, supporting 57-bit virtual addresses), a fifth table level covers 256 PB of address space.

Translation Lookaside Buffer (TLB)

Even with multi-level tables, each page table walk requires 4–5 sequential memory accesses. If every instruction fetch and data access required a page table walk, virtual memory would be catastrophically slow. The TLB is a hardware cache that stores recently used virtual-to-physical translations. Each TLB entry maps a virtual page number to a physical frame number, with protection bits and access statistics.

A TLB hit delivers the translation in one CPU cycle. A TLB miss triggers a hardware page walk (typically 4–5 memory accesses, 10–50 cycles) that refills the TLB. TLB misses on the instruction path or on hot data paths are a primary source of performance degradation.

TLB reach is the total amount of memory accessible without TLB misses: TLB entries × page size. With 64 TLB entries and 4 KB pages, reach is 256 KB. Modern workloads routinely exceed this, which is why larger page sizes are critical.

Page Replacement Algorithms

When physical memory is overcommitted — processes collectively demand more pages than available frames — the OS must evict some pages to make room for new ones. The choice of eviction victim substantially affects performance.

FIFO (First-In, First-Out)

FIFO evicts the page that has been in memory the longest. It is simple to implement (a circular queue) but performs poorly because frequently used pages can be evicted, causing immediate page faults. Belady’s Anomaly (1969) showed that increasing the number of page frames can increase the page fault rate under FIFO — a counterintuitive result that disqualified FIFO for serious use.

Optimal (MIN or Belady’s Algorithm)

Belady’s Optimal algorithm evicts the page that will be used farthest in the future. It provides the theoretical minimum page fault rate. It is impossible to implement because it requires knowledge of future memory accesses. It serves as a theoretical upper bound for evaluating practical algorithms.

LRU (Least Recently Used)

LRU evicts the page that has not been accessed for the longest time. It closely approximates Optimal for most workloads because programs tend to exhibit temporal locality — pages accessed recently are likely to be accessed again soon. True LRU (maintaining a fully ordered access list) is expensive: every memory access would update a linked list, and the page fault handler would scan the list.

Clock (Second Chance) Algorithm

The Clock algorithm approximates LRU efficiently. Page frames are arranged in a circular buffer. Each frame has a reference bit, set by the MMU when the page is accessed (hardware sets this bit automatically). The page replacement sweeps a clock hand: if the current frame’s reference bit is 1, clear it and advance; if 0, evict that page. Clock variants (WSClock, adding dirty-bit awareness and a working set estimator) are used in production operating systems.

Working Set Model

Peter Denning’s working set model (1968) formalized the observation that processes access memory in localized sets. A process’s working set is the set of pages it has referenced in the last Δ (working set window). If the sum of all processes’ working sets exceeds physical memory, the system thrashs — spending more time paging than executing. The OS can reduce thrashing by temporarily suspending (swapping out) some processes.

Modern Memory Management in Production OSes

Linux uses four-level (or five-level) page tables with per-process page table roots stored in mm_struct->pgd. Huge pages (2 MB and 1 GB) are available explicitly (hugetlbfs) or transparently (Transparent Huge Pages, THP). THP automatically promotes groups of 4 KB pages to 2 MB pages when contiguous physical memory is available, reducing TLB pressure. NUMA-aware allocation places memory on the local NUMA node, minimizing remote memory access latency.

Windows NT uses a similar paging architecture with the addition of memory-mapped sections (the basis of file-backed pages) and a working set manager that dynamically adjusts per-process working sets.

macOS uses the XNU kernel with compressed memory — inactive pages are compressed in memory before being paged to disk, reducing I/O. The memory pressure mechanism (signaled through dispatch_source_set_memorypressure) allows applications to respond to memory constraints proactively.

FAQ

What is the difference between paging and segmentation?

Paging divides memory into fixed-size units (pages/frames). Segmentation divides memory into variable-sized logical units (code segment, data segment, stack). Paging eliminates external fragmentation and simplifies allocation. Segmentation provides natural protection boundaries and simplifies data sharing. Most modern systems use paged segmentation or pure paging — x86-64 uses paging only; segmentation is essentially disabled in long mode.

How do huge pages improve performance?

Huge pages (2 MB or 1 GB) increase TLB reach. A single TLB entry for a 2 MB page covers 512× more memory than a 4 KB entry. Databases and virtualized workloads that reference large contiguous address ranges benefit significantly. PostgreSQL, Redis, and KVM recommend enabling huge pages.

What causes thrashing, and how can I detect it?

Thrashing occurs when the sum of active processes’ working sets exceeds physical memory. The page fault rate spikes dramatically. Symptoms in Linux: high si (swap in) and so (swap out) values in vmstat, high %iowait, and degraded responsiveness. Solutions: increase RAM, reduce the number of concurrent processes (decrease process count in configuration), or use the working set model to control multiprogramming.

How does the Linux kernel find a free page when a page fault occurs?

The page allocator (buddy allocator) manages free page frames. If a free page exists in the per-CPU free lists or partner lists, the allocator returns it immediately. If the system is under memory pressure, the direct reclaim path (shrink_page_list) scans active and inactive LRU lists, evicting clean pages and writing dirty pages back. If reclaim fails, the OOM killer selects and terminates a process.

What is NUMA, and why does it complicate memory management?

Non-Uniform Memory Access (NUMA) systems have multiple memory controllers, each local to a group of CPUs (a NUMA node). Accessing memory on a remote node adds latency (20–40% higher than local access on typical servers). The OS must allocate memory on the node where the process runs and migrate pages (via automatic NUMA balancing in Linux) when processes move between nodes.

The Virtual Memory Guide covers demand paging and page table details in depth. The Process Scheduling Guide explains how the scheduler cooperates with the memory manager. Silberschatz, Galvin, and Gagne, Operating System Concepts (10th ed.), Chapters 8–9, and Tanenbaum and Bos, Modern Operating Systems (4th ed.), Chapter 3, provide comprehensive textbook coverage. The Linux kernel source’s Documentation/admin-guide/mm/ directory describes each memory management subsystem.