How Does Virtual Memory Work? A Deep Dive into Paging and Multi‑Level Page Tables

Memory is the computer's main storage, allocating address space for each process to hold data.

Memory

Simply put, memory is a data shelf where the smallest addressable unit is typically one byte. Each byte is numbered by a memory address, starting from 0 and increasing linearly, called a linear address. Hexadecimal notation (e.g., 0x00000003, 0x1A010CB0) is used to represent these addresses.

The address space size is limited by the width of the address bus. For example, Intel's 32‑bit 80386 CPU has a 32‑bit address bus, allowing addresses from 0x00000000 to 0xFFFFFFFF.

Memory uses Random Access Memory (RAM), meaning access time is independent of the data's location, unlike sequential media such as tape.

While memory can hold both kernel and user‑process data, it is volatile; power loss erases its contents, so persistent storage (e.g., disks) is still required.

Virtual Memory

Processes cannot directly access physical memory addresses; they operate on virtual memory addresses. The operating system translates these virtual addresses to real physical addresses, a mechanism called virtual memory.

Each process has its own set of virtual addresses, which are independent of other processes. Virtual and physical addresses correspond as shown in the diagram.

Applications see only virtual addresses. In C, the address of a variable can be printed as follows:

int v = 0;
printf("%p", (void *)&v);

Because the OS controls the translation, programs are unaware of the underlying physical locations, enhancing isolation and security. Virtual memory also enables memory sharing without copying, allowing multiple processes to map the same physical region (e.g., shared libraries, kernel data).

Memory Paging

To avoid storing a mapping for every byte, Linux uses paging. Memory is divided into pages (typically 4 KB). The page size can be queried with:

$ getconf PAGE_SIZE
4096

Paging reduces the number of entries dramatically: each page represents 4096 bytes, so the total number of page entries is about one‑fourth of a thousandth of the total byte count.

Within a page, addresses are contiguous; the lower 12 bits of an address serve as the offset within the page, while the higher bits identify the page number.

Multi‑Level Page Tables

Linux stores the virtual‑to‑physical mapping in page tables. A single linear page table would waste space because many entries are unused. Instead, Linux employs multi‑level page tables, where the virtual page number is split into several parts. The first level indexes a set of second‑level tables, each covering a subset of the address space. Only the needed second‑level tables are allocated, saving memory.

The process is analogous to a telephone directory: a top‑level book maps area codes to local books, and each local book contains the actual numbers. Unused area codes are left empty, avoiding unnecessary storage.

Multi‑level tables also allow the second‑level tables to reside in non‑contiguous memory, making efficient use of fragmented space.

In summary, Linux manages memory by dividing it into pages, using virtual memory to separate process address spaces, and employing multi‑level page tables to keep the mapping data compact and fast.