Virtual memory is a memory management technique in which every program sees its own private, contiguous address space, while the operating system and the processor's memory management unit (MMU) map those virtual addresses onto physical RAM in fixed-size blocks called pages. It lets many programs run at once without overwriting each other, lets a program use more memory than is physically free by keeping some pages on disk, and avoids the fragmentation that comes from placing whole programs in physical memory. It sits right at the boundary between hardware and software.
Introduction to Virtual Memory. Great video from Tech with Nikola on YouTube. Virtual memory is a common memory management technique in a computer's operating system, and a big part of why you can play a video game such as Diablo 4 while a music app like Spotify runs alongside it, without one crashing the other. The video explains the problems virtual memory solves, the core principles behind it, how it is implemented, and the optimisation techniques that make it fast. A chapter list is at the end of this post, and the explanation below follows the same order so you can read and watch side by side.
Key takeaways
- Programs use virtual addresses. The MMU translates each one to a physical address using page tables set up by the operating system.
- Memory is split into pages (4 KiB is the common base size on x86 and Arm, with larger pages also supported). A virtual address is a page number plus an offset within the page.
- Virtual memory solves three problems: not enough memory, memory fragmentation, and security (isolation between programs).
- A page fault occurs when a page is not mapped in RAM; the operating system loads it, or stops the program if the access is illegal.
- The translation lookaside buffer (TLB) caches recent translations, and multi-level page tables keep the tables themselves small.
The problems virtual memory solves
Not enough memory
Without virtual memory, every running program must fit in physical RAM at the same time. With it, only the pages a program is actively using need to be in RAM. The rest can stay on disk (in a swap file or page file) and be brought in on demand. Programs can therefore be written as if memory were larger than what is physically installed, at the cost of slow disk accesses if the working set does not fit.
Memory fragmentation
If each program needs one contiguous block of physical memory, free space becomes scattered into holes too small to use as programs start and stop. Paging removes this problem: a program's virtual space looks contiguous, but its pages can sit in any free physical frames, anywhere in RAM.
Security and isolation
If programs share one physical address space, a bug or a malicious program can read or overwrite another program's data, or the operating system itself. With virtual memory, each process has its own page table. A process simply has no mapping for another process's memory, and each page carries permission bits (read, write, execute, user or kernel only) that the hardware checks on every access.
The key idea behind all three solutions is the same: add a level of indirection between the address a program uses and the address the memory sees.
How virtual memory is implemented
The virtual address space and physical memory are both divided into equal-size blocks. Virtual blocks are pages; physical blocks are frames. A virtual address is split into two fields: the virtual page number (VPN) and the page offset. The offset passes through unchanged. The VPN is looked up in the page table to find the physical frame number (PFN), and the physical address is PFN followed by the offset.
The page table
The page table is a data structure in memory, one per process, that maps each VPN to a page table entry (PTE). A PTE typically holds the frame number, a valid (present) bit, permission bits, and accessed and dirty bits that the operating system uses to decide which pages to evict. The processor holds a pointer to the current table in a register (CR3 on x86, SATP on RISC-V, TTBR on Arm) and the operating system changes it on every context switch.
Worked example: address translation
Assume a 32-bit virtual address and 4 KiB pages. A 4 KiB page needs 12 bits of offset (212 = 4,096), leaving 20 bits for the VPN.
| Step | Value |
|---|---|
| Virtual address | 0x00403ABC |
| VPN (upper 20 bits) | 0x00403 |
| Offset (lower 12 bits) | 0xABC |
| Page table entry for VPN 0x00403 (illustrative) | valid, PFN 0x001F2 |
| Physical address (PFN, offset) | 0x001F2ABC |
The table values are illustrative. Note the cost of a flat table at this size: 220 entries of 4 bytes is 4 MiB per process, even if the program uses only a few pages. That is the reason multi-level tables exist.
Page faults
If the PTE's valid bit is clear, the MMU raises a page fault, an exception handled by the operating system. If the address is legal but the page is on disk (or has never been touched), the OS finds a free frame, evicting another page if needed, loads the data, updates the PTE and restarts the instruction. If the address is illegal or the access breaks the permission bits, the OS stops the program, which is the familiar segmentation fault or access violation. Servicing a fault from disk takes millions of processor cycles, so a system that faults constantly (thrashing) becomes very slow.
Making it fast
Translation lookaside buffer (TLB)
Every load, store and instruction fetch needs a translation. If each one required a page table read from memory, every memory access would cost at least two. The TLB is a small, fast cache inside the processor that holds recent VPN to PFN translations. On a TLB hit, translation completes in about a cycle, often in parallel with the cache lookup. On a miss, a hardware page table walker (on x86, Arm and most RISC-V designs) or a software handler fetches the PTE and fills the TLB. Because programs show locality, TLB hit rates are usually very high. TLBs are typically split into levels, with a few dozen entries in the first level and hundreds to a few thousand in the second; exact sizes vary by processor.
In the worked example above, once VPN 0x00403 is in the TLB, any further access within that 4 KiB page, such as 0x00403000 to 0x00403FFF, translates without touching the page table.
Multi-level page tables
A multi-level table splits the VPN into several fields, each indexing one level of a tree. Only the parts of the tree that cover used memory are allocated. On x86-64 with 4-level paging, a 48-bit virtual address is split into four 9-bit indexes plus a 12-bit offset; each table has 512 entries of 8 bytes, exactly one 4 KiB page. Newer x86 processors support 5-level paging with 57-bit addresses, and RISC-V defines Sv39, Sv48 and Sv57 schemes on the same pattern.
The trade-off is the walk length: a TLB miss with 4-level tables can need four memory reads before the data access. Processors reduce this with caches for the upper levels of the walk, and operating systems use huge pages (2 MiB or 1 GiB on x86-64) so one TLB entry covers far more memory.
Why hardware designers care
For chip designers, virtual memory is not only an OS topic. The MMU, TLBs and page table walker are significant blocks in any application processor, and their sizes directly affect performance on large workloads. Caches have to deal with virtual or physical indexing and tagging. Devices that access memory directly need an IOMMU (the Arm SMMU, Intel VT-d, or the RISC-V IOMMU) so they can share virtual address spaces safely. Changing a mapping on a multi-core chip requires TLB shootdowns across cores, which is a common performance and verification corner. Small microcontrollers often skip full virtual memory and use a simpler memory protection unit (MPU) instead.
Common mistakes and misconceptions
- Virtual memory is not the same as swap. Swap is one use of virtual memory. A system with no swap file still uses virtual addresses and page tables for isolation.
- The offset is never translated. Only the page number changes; the low bits pass through, which is why page sizes are powers of two.
- A page fault is not always an error. Most page faults are normal events, such as the first touch of newly allocated memory.
- Bigger pages are not free. Huge pages cut TLB misses but waste memory when only part of a page is used.
FAQ
What does the MMU do?
It translates virtual addresses to physical addresses on every access, checks permission bits, and raises a page fault when a mapping is missing or an access is not allowed.
How big is a page?
The common base size is 4 KiB on x86 and Arm, with larger page sizes also available. Some Arm systems use 16 KiB or 64 KiB base pages.
What happens on a TLB miss?
The page table walker reads the page table entries from memory (often hitting in the data caches), installs the translation in the TLB and retries the access. If the walk finds an invalid entry, it becomes a page fault.
Why does each process have its own page table?
So that the same virtual address in two processes can map to different physical memory. That gives isolation, and it lets every program be linked as if it owned the whole address space.
Video chapters
- 00:00 Intro
- 00:19 Problem: Not Enough Memory
- 01:17 Problem: Memory Fragmentation
- 02:20 Problem: Security
- 03:10 Key Problem
- 04:42 Solution: Not Enough Memory
- 05:58 Solution: Memory Fragmentation
- 06:32 Solution: Security
- 07:30 Virtual Memory Implementation
- 09:49 Page Table
- 10:40 Example: Address Translation
- 11:54 Page Faults
- 13:28 Recap
- 14:18 Translation Lookaside Buffer (TLB)
- 15:46 Example: Address Translation with TLB
- 16:57 Multi-Level Page Tables
- 18:48 Example: Address Translation with Multi-Level Page Tables
- 19:58 Outro
nice blog
ReplyDelete