How Virtual Memory Powers Modern Operating Systems: A Deep Dive

Overview

Processes share CPU and memory resources, so operating systems need robust memory‑management mechanisms to prevent leaks. Modern OSes introduce virtual memory, an abstraction that gives each process a consistent, private address space, creating the illusion of exclusive main‑memory ownership.

Virtual memory is not merely "using disk space to extend RAM"; its key benefit is defining a continuous virtual address space, simplifying programming. Extending memory onto disk is a natural consequence: the virtual space may reside on disk and be cached in RAM on demand, and some OSes may swap an entire process’s memory to disk when RAM is scarce.

Virtual memory provides three essential capabilities:

It treats main memory as a high‑speed cache for a virtual address space stored on disk, caching only active regions.

It offers each process a consistent address space, reducing programmer‑level memory‑management complexity.

It protects each process’s address space from interference by others.

The following sections explain how virtual memory works in hardware and how Linux implements it.

CPU Addressing

Memory is organized as an array of M consecutive byte‑sized units, each with a unique physical address (PA). The simplest access method is physical addressing, using PA directly.

Modern processors use virtual addressing: the CPU must translate a virtual address to a physical address before accessing real memory.

Virtual addressing requires cooperation between hardware and the OS. The CPU contains a Memory Management Unit (MMU) that translates virtual addresses to physical addresses using page tables managed by the OS.

Page Tables

Virtual memory is divided into fixed‑size virtual pages (VP) of size P=2^p bytes; physical memory is divided into physical pages (PP) of the same size P.

The OS maintains a page‑table data structure in RAM that records the mapping between virtual pages and physical pages. Each entry (Page Table Entry, PTE) contains a valid bit indicating whether the virtual page is cached in RAM.

Examples of PTE states:

VP 0, VP 4, VP 6, VP 7 are cached in physical memory.

VP 2 and VP 5 are present in the page table but not cached.

VP 1 and VP 3 have not been allocated.

When a process calls malloc() or uses the new keyword, the OS creates or reserves a virtual page on disk and updates the page table with a new PTE pointing to that page.

Additional permission bits in PTEs (e.g., read/write, kernel mode) allow the CPU to raise protection faults (segmentation faults) when violated.

Page Hit

If the MMU finds a PTE with a valid bit of 1 (e.g., PTE 4), the corresponding physical page (PP 1) is used, completing the translation.

Page Fault

If the MMU finds a PTE with a valid bit of 0 (e.g., PTE 2), a page‑fault occurs. The OS’s page‑fault handler selects a victim page, writes it back to disk if dirty, loads the needed virtual page into memory, updates the PTE, and resumes the faulting instruction, which then translates successfully.

This on‑demand paging strategy minimizes unnecessary disk I/O.

Multi‑Level Page Tables

For large address spaces (e.g., 2 32 = 4 GB on a 32‑bit system), a single page table is inefficient. Hierarchical page tables split the virtual address into multiple VPN components, each indexing a level of the table. A two‑level example maps a 4 GB space with 1024 first‑level entries (each covering 4 MB) and 1024 second‑level entries (each covering 4 KB).

This structure resembles a B‑Tree, allowing unused upper‑level entries to be omitted, saving memory.

Address Translation Process

Address translation maps an N‑element virtual address space to an M‑element physical address space. The MMU uses the Page Table Base Register (PTBR) to locate the current page table. A virtual address consists of a virtual page number (VPN) and a page‑offset (VPO). The MMU uses the VPN to select the appropriate PTE, extracts the physical page number (PPN), and concatenates it with the VPO to form the physical address.

With a k‑level page table, the virtual address is split into k VPN fields and one VPO; the MMU must walk k PTEs to obtain the final PPN.

TLB

To avoid frequent memory accesses for PTEs, CPUs cache recent PTEs in a Translation Lookaside Buffer (TLB). A TLB entry stores a single PTE; the index and tag are derived from the VPN.

TLB hit flow:

CPU submits a virtual address to the MMU.

MMU retrieves the PTE from the TLB.

MMU translates the PTE to a physical address and sends it to cache/memory.

Cache returns the data to the CPU (or accesses memory if needed).

If the TLB misses, the MMU fetches the PTE from memory, updates the TLB (evicting if full), and proceeds.

Virtual Memory in Linux

Linux gives each process its own virtual address space, divided into kernel and user regions. User space includes code, data, heap, shared libraries, and stack; kernel space contains kernel code and data structures, some of which are shared across processes.

Linux organizes virtual memory into areas (segments) such as code, data, heap, shared libraries, and stack. Each area is described by a vm_area_struct linked from the process’s mm_struct. The mm_struct also holds a pointer to the top‑level page table (pgd).

mm_struct : overall state of virtual memory.

vm_start / vm_end : start and end addresses of an area.

vm_prot : protection bits for pages in the area.

vm_flags : flags indicating sharing, private status, etc.

Memory Mapping

Linux can map a virtual memory region to a file on disk (file‑backed mapping) or to an anonymous zero‑filled region. The mapping is lazy: pages are not loaded into RAM until the CPU accesses them. When a page is first accessed, the kernel allocates a physical page, possibly writes back a modified page, and updates the page table.

File‑backed mappings allow user‑space I/O to bypass the kernel, while anonymous mappings are used for dynamic allocation (e.g., malloc()).

Dynamic Memory Allocation

The heap is a contiguous virtual region managed by a dynamic allocator. The allocator tracks allocated and free blocks, often using free‑list structures (implicit or explicit) and strategies such as first‑fit, next‑fit, or best‑fit. Segregated storage maintains multiple free‑lists for different size classes to improve allocation speed.

Garbage Collection

Languages with automatic memory management use garbage collectors to reclaim unreachable heap objects. Common techniques include reference counting and reachability analysis, with algorithms such as mark‑sweep, mark‑compact, copying, and generational collection.

Summary

Virtual memory abstracts physical memory, giving each process a private address space. The CPU, MMU, page tables, TLB, and paging mechanisms cooperate to translate addresses, handle page faults, and maintain locality through working sets. Linux implements these concepts via hierarchical page tables, TLB caching, memory‑mapped files, and dynamic allocators, simplifying linking, loading, sharing, and protection.

References

CS:APP3e, Bryant and O'Hallaron

Virtual memory – Wikipedia

Garbage collection (computer science) – Wikipedia