Operating System Memory Management: Virtual Memory and Paging

The addresses a process sees are fake, and turning those fake addresses into real memory is what memory management is about.

Backend performance problems often trace back to memory access patterns. Ask why Redis is fast, or why the OOM (out of memory) killer terminates a process, and the answer eventually lands on virtual memory and paging.

The problem virtual memory solves

Virtual memory gives every process its own virtual address space. The process sees a contiguous range of addresses starting at zero, but the physical location those addresses point to is somewhere else entirely. That indirection lets a process use a large address space regardless of how much physical memory exists.

Without it, two processes trying to write the same physical address would be hard to keep apart. Separate virtual address spaces mean one process cannot touch another process's memory directly. Isolation and protection are the first benefit of virtual memory.

What remains is translation. Who converts the virtual address a process presents into a physical address, and how, is the starting point for everything that follows.

Paging and address translation

Paging manages memory in fixed-size chunks. The virtual address space is divided into pages of a uniform size and physical memory into frames of that same size. On x86 the page size is usually 4KB.

A virtual address splits into two parts. The upper part is the page number and the lower part is the offset within the page. With a 32-bit address and 4KB pages (2 to the 12th power bytes), the offset takes 12 bits and the page number takes 20.

The hardware that performs the translation is the memory management unit (MMU). The MMU looks up the page number in the page table, replaces it with a frame number, and appends the offset unchanged to form the physical address.

Each process has its own page table. The same virtual address in a different process points to a different frame, so isolation holds naturally.

Why page tables grow too large

The page table itself consumes memory. On a 32-bit system with a 20-bit page number, the table holds 2 to the 20th power entries, roughly one million. At 4 bytes per entry, a single table requires about 4MB of contiguous memory. Allocating that in full for every process is wasteful.

The answer is the multi-level page table. The address is split into several fields and translation walks down through a table per level, creating lower-level tables only for the address ranges actually in use. Ranges that are never touched get no table at all, which saves memory.

x86-64 normally uses a four-level page table, and CPUs that support Intel 5-level paging extend it to five. That widens the virtual address to 57 bits, corresponding to roughly 128PB (petabytes), which is 2 to the 57th power (per the Intel 64 architecture). Each additional level adds another memory access per translation.

Cutting translation cost with the TLB

The multi-level structure has a cost. Because the page table lives in memory, translation alone costs as many memory accesses as there are levels. Add the actual data access on top and the number of memory references rises sharply.

The device that reduces this cost is the translation lookaside buffer (TLB). The TLB is a small, fast hardware cache holding recently completed address translations. When the same page is requested again, the frame number comes straight from the TLB without walking the page table.

The cost difference between a TLB hit and a miss is large. A hit runs at cache speed and is very fast; a miss has to read the page table from memory and is slow. Commonly cited estimates put a hit at around 1 nanosecond and a miss in the tens to roughly 100 nanoseconds.

Access patterns decide translation efficiency. Reading adjacent addresses in order stays within the same page and keeps the TLB hit rate high. Jumping randomly across a wide region drops the hit rate and degrades performance sharply.

Switching processes changes the virtual address space, which invalidates the old TLB entries. That is why a context switch carries the cost of flushing the TLB. Tagging TLB entries with an address space identifier (ASID) keeps entries separated per process instead of flushing everything.

Larger pages cover more memory with the same number of TLB entries. If 1,024 entries of 4KB pages cover about 4MB, the same number of entries covers about 2GB with 2MB huge pages. The tradeoff is that a larger page can waste more space in the final page.

Paging, segmentation, and fragmentation

Paging is not the only way to divide memory; segmentation is another. Segmentation splits memory into variable-size segments along meaningful boundaries such as code, data, and stack. The logical separation is clean, but fragmentation behaves differently than under paging.

Fragmentation is memory that cannot be used and is effectively thrown away. Under paging, when a request does not align with page boundaries, the leftover space in the last page is wasted. That is internal fragmentation. A 5KB request, for example, gets two 4KB pages and wastes 3KB.

Segmentation uses variable sizes, so free space ends up scattered. Even when the total free space is sufficient, allocation can fail because no single contiguous block is large enough. That is external fragmentation.

Fixed-size pages fit into any free frame, so external fragmentation never arises. That is why modern operating systems use paging as the primary mechanism.

Demand paging and page faults

There is no need to load every page of a process into physical memory up front. Demand paging loads a page only when it is actually used. A valid bit in the page table records whether the page is currently in memory.

Accessing a page that is not present raises a page fault. This is not an error but a signal asking the operating system to load the page. The OS steps in, fetches the page from disk, and if no free frame is available, picks a page to evict using a replacement algorithm.

Handling a page fault involves a disk access, so it is expensive. If memory access is measured in nanoseconds, disk access is thousands of times slower (estimate). Keeping fault frequency low is therefore the main performance lever.

Demand paging applies unchanged to memory-mapped files such as mmap. The file is mapped into the virtual address space, and reading a region triggers a page fault that loads only that part. In effect, a large file is handled piece by piece rather than loaded whole.

Page replacement and thrashing

When physical memory fills up, space has to be freed for a new page. Choosing which page to evict is the job of the page replacement algorithm. Better choices mean fewer faults from pages that have to be fetched again.

LRU combines a hash map with a doubly linked list to handle lookup, update, and eviction in O(1). The list maintains usage order and the hash map provides direct access by key. Redis key eviction policies rest on the same idea of discarding the least recently used keys first.

FIFO suffers Belady's anomaly, where adding frames can increase the number of faults. LRU and OPT avoid it because they are stack algorithms. Adding frames is guaranteed to leave the fault count the same or lower.

Thrashing is the state where memory is so scarce that the system does nothing but service faults. As faults rise the CPU looks idle, so the OS admits more processes, memory gets scarcer still, and faults explode. The working set model pins the actively used pages in memory, and page-fault-rate upper and lower bounds adjust the frame allocation to prevent it.

Summary

Virtual memory gives each process an independent address space, delivering isolation and a large address space at the same time. Paging and page tables are the mechanism that turns those virtual addresses into physical ones, with the MMU converting page numbers into frame numbers. The growth of page tables is handled by a multi-level structure and the translation cost by the TLB. Pages not in memory are loaded on a page fault, and when no frame is free, the replacement algorithm picks the page to evict. Once faults escape control the system thrashes, so keeping the working set resident is the last line of defense for performance.