Every program you run believes it owns a huge, private, contiguous memory that starts at address 0. In reality, many programs share a limited amount of RAM, their pieces are scattered across physical memory, and some pieces are not in RAM at all but on disk. The illusion that makes this work is called virtual memory.
The Operating Systems tutorial explains virtual memory from the OS side: demand paging, page-replacement algorithms, thrashing. In this chapter we look at it as computer architects: what hardware sits between the CPU and memory, how a virtual address is turned into a physical address on every single load and store, how the TLB makes this fast, what happens in hardware on a page fault, and how translation interacts with the caches from Cache Mapping Techniques.
Why Hardware Support Is Needed
Virtual memory solves three problems at once:
Capacity: a program can be larger than physical memory; only the parts in use need to be in RAM.
Relocation: each program is compiled as if it starts at address 0; it can be loaded anywhere in physical memory.
Protection: one program cannot read or write another program's memory, or the kernel's.
All three need a translation on every memory access, including every instruction fetch. Software is far too slow for that, so the translation is done by a hardware unit inside the processor, the Memory Management Unit (MMU).
Virtual (logical) address: the address generated by the program running on the CPU.
Physical address: the address actually sent to the memory system.
MMU: the hardware that translates virtual addresses to physical addresses and checks access permissions.
Paging: The Hardware Mechanism
Virtual memory is divided into fixed-size pages, and physical memory into frames (page frames) of the same size, typically 4 KB. A virtual address is split into two fields:
virtual address (n bits)
+-------------------------------+-----------------+
| Virtual Page Number (VPN) | page offset |
+-------------------------------+-----------------+
n - p bits p bits (page size = 2^p bytes)
│ translate (page table / TLB) │ copied unchanged
▼ ▼
+-------------------------------+-----------------+
| Physical Frame Number (PFN) | page offset |
+-------------------------------+-----------------+
physical address (m bits)Only the page number is translated; the offset passes straight through. The mapping from VPN to PFN is stored in the page table, which lives in main memory. A processor register, the page-table base register (CR3 on x86, satp on RISC-V, TTBR0/TTBR1 on ARM), points to the page table of the currently running process.
What a Page-Table Entry Holds
| Field | Used by hardware for |
|---|---|
| Valid / Present bit | If 0, translation fails and the MMU raises a page-fault exception |
| Frame number (PFN) | Forms the high part of the physical address |
| Protection bits (R/W/X, User/Supervisor) | Checked on every access; a violation raises a protection fault |
| Referenced (Accessed) bit | Set by hardware on any access; helps the OS approximate LRU |
| Dirty (Modified) bit | Set by hardware on a write; tells the OS the page must be saved before reuse |
| Cache-control bits | E.g. "uncacheable" for memory-mapped I/O registers |
Notice the similarity with a cache line: valid bit, dirty bit, and a "tag" (the mapping). Virtual memory is, in effect, main memory acting as a fully associative, write-back cache for the disk, with pages as blocks. It is write-back because writing every store to disk would be impossibly slow, and fully associative because a page fault costs millions of cycles, so it is worth placing a page in any frame to avoid one.
Worked Example 1: Translating Addresses
A machine has 16-bit virtual addresses, 15-bit physical addresses and 4 KB pages. The current page table is:
| VPN | Valid | PFN |
|---|---|---|
| 0 | 1 | 5 |
| 1 | 0 | - |
| 2 | 1 | 1 |
| 3 | 1 | 7 |
| 4 to 15 | 0 | - |
Translate the virtual addresses 0x3A7F, 0x2FFF, 0x0010 and 0x1234.
Offset bits = log2(4096) = 12 → the last 3 hex digits are the offset
VPN bits = 16 - 12 = 4 → the first hex digit is the VPN
PFN bits = 15 - 12 = 3 → 8 frames
VA 0x3A7F: VPN 3, offset 0xA7F → PFN 7 → PA = 7 × 4096 + 0xA7F = 0x7A7F
VA 0x2FFF: VPN 2, offset 0xFFF → PFN 1 → PA = 0x1FFF
VA 0x0010: VPN 0, offset 0x010 → PFN 5 → PA = 0x5010
VA 0x1234: VPN 1, valid = 0 → PAGE FAULT (exception to the OS)With a 4 KB page and hexadecimal addresses, translation is just replacing the leading hex digit(s). That works only because 12 offset bits are exactly 3 hex digits.
Worked Example 2: Page Table Size
A system has 32-bit virtual addresses, 30-bit physical addresses and 4 KB pages. Each PTE stores the frame number plus a valid bit, a dirty bit, a referenced bit and 3 protection bits. Find the page table size per process with a single-level table, if each PTE is rounded up to a whole number of bytes.
Number of pages = 2^32 / 2^12 = 2^20 = 1,048,576 entries
Number of frames = 2^30 / 2^12 = 2^18 → PFN = 18 bits
PTE bits = 18 + 1 + 1 + 1 + 3 = 24 bits = 3 bytes
Page table size = 2^20 × 3 B = 3 MB
(with the usual 4-byte PTE: 2^20 × 4 B = 4 MB)That is per process, and it must be contiguous. A 64-bit address space would need an impossibly large flat table. The hardware solution is a multi-level (hierarchical) page table, where the VPN is split into several indexes and a table at each level is only allocated if that region of the address space is used.
Multi-Level Walk: RISC-V Sv39
The RISC-V Sv39 scheme uses 39-bit virtual addresses, 4 KB pages and 8-byte PTEs. One 4 KB page of PTEs holds 4096 / 8 = 512 = 29 entries, so each level consumes 9 bits of the VPN:
Bits to translate = 39 - 12 = 27
Levels = 27 / 9 = 3
+---------+---------+---------+--------------+
| VPN[2] | VPN[1] | VPN[0] | offset |
+---------+---------+---------+--------------+
9 bits 9 bits 9 bits 12 bits
satp → level-2 table [VPN[2]] → level-1 table [VPN[1]] → level-0 table [VPN[0]] → PFNx86-64 does the same with four 9-bit levels for 48-bit addresses (and five levels for 57-bit addresses). The hardware cost is clear: without help, every memory access needs 3 or 4 extra memory accesses just to translate the address. That is what the TLB fixes. (The OS-side details of multi-level, hashed and inverted page tables are in the Operating Systems tutorial.)
The Translation Lookaside Buffer (TLB)
TLB: a small, fast cache inside the MMU that holds recently used VPN → PFN translations together with their permission and status bits.
The TLB works for the same reason caches work: locality. One entry covers a whole page (4096 bytes), so a loop walking through an array needs a new translation only once every 4 KB.
TLB Organisation
A TLB is a cache whose "address" is the VPN and whose "data" is the PFN plus bits. So everything from Cache Mapping Techniques applies:
Small first-level TLBs (tens of entries) are often fully associative or highly associative, because a TLB miss is expensive and the TLB is small enough to compare all tags in parallel.
Larger second-level TLBs (hundreds to a few thousand entries) are set associative.
Many processors have separate instruction and data TLBs, just like split L1 caches.
TLB entry
+---+------------+-----------+-------+---+---+-------------+
| V | tag (VPN) | ASID | PFN | D | R | protection |
+---+------------+-----------+-------+---+---+-------------+
ASID (address-space ID) lets entries of different processes coexist,
so the TLB need not be flushed on every context switch.Worked Example 3: TLB Address Split
32-bit virtual addresses, 30-bit physical addresses, 4 KB pages. The TLB has 64 entries and is 4-way set associative. How is the virtual address used to index the TLB, and how wide is each tag?
Page offset = 12 bits → VPN = 32 - 12 = 20 bits
TLB sets = 64 / 4 = 16 → TLB index = 4 bits (low bits of the VPN)
TLB tag = 20 - 4 = 16 bits
+------------------+--------+--------------+
| TLB tag (16) | set(4) | offset (12) |
+------------------+--------+--------------+
|<------- VPN (20) -------->|
Each entry also stores PFN = 30 - 12 = 18 bits, plus V, D, R and protection bits.
Comparators: 4 (one per way), each 16 bits wide.The pattern is the same as a cache, except that the "offset" is the page offset and it is never used to look up the TLB.
What Happens on Every Access
CPU issues virtual address
│
▼
TLB lookup (VPN)
│ │
HIT MISS
│ └──► page-table walk in memory
│ (hardware walker on x86/ARM; software handler on classic MIPS)
│ │
│ PTE valid? ── no ──► PAGE FAULT exception → OS
│ │ yes
│ load PTE into TLB, retry
▼
permission check (R/W/X, user/kernel) ── fail ──► protection fault
│ ok
▼
physical address = PFN : offset → caches → main memoryEffective Access Time with a TLB
Let t = TLB lookup time, m = memory access time, h = TLB hit ratio and k = number of page-table levels. Ignoring data caches:
EAT = h × (t + m) + (1 − h) × (t + k·m + m)
t = 2 ns, m = 100 ns, h = 0.98.
Single-level page table (k = 1):
EAT = 0.98 × 102 + 0.02 × 202 = 99.96 + 4.04 = 104 ns
Three-level page table (k = 3):
EAT = 0.98 × 102 + 0.02 × 402 = 99.96 + 8.04 = 108 ns
Without any TLB, three levels: 3 × 100 + 100 = 400 nsThe TLB turns a 4× slowdown into an 8% slowdown. This is why no paged processor is built without one.
Adding Page Faults
If a fraction p of accesses cause a page fault that takes 8 ms to service (reading the page from disk):
EAT = (1 - p) × 100 ns + p × 8,000,000 ns
p = 0.001 → EAT = 99.9 + 8000 = 8099.9 ns (about 81 times slower!)
For at most 10% slowdown (EAT ≤ 110 ns):
100 + p × (8,000,000 - 100) ≤ 110
p ≤ 10 / 7,999,900 ≈ 1.25 × 10^-6 (fewer than 1 fault per 800,000 accesses)Page faults are so expensive that the page fault rate must be tiny. That is the hardware reason behind the OS's careful page-replacement policies.
Page Faults in Hardware: Precise Exceptions
A page fault is detected in the middle of an instruction (during fetch, or during a load/store). The hardware must make sure the instruction can simply be re-executed after the OS brings the page in:
The MMU signals a page-fault exception and records the faulting virtual address (CR2 on x86,
stvalon RISC-V,FARon ARM).The processor saves the address of the faulting instruction (for example in
sepcon RISC-V) and switches to kernel mode, jumping to the OS handler.The faulting instruction and all later instructions must have had no visible effect, while all earlier instructions have completed. This is called a precise exception.
The OS loads the page (the CPU runs other processes during the disk I/O), updates the PTE, and returns. The instruction is re-executed and now succeeds.
Instructions that change state before they finish (for example, auto-increment addressing or block-move instructions that copy many bytes) make this hard. Architectures handle it by undoing the partial change, by keeping enough state in registers to resume the instruction, or by checking that all pages are present before starting. In pipelined processors, where several instructions are in flight at once, providing precise exceptions is a major design concern.
TLB and Cache Together
A cache can be indexed and tagged with either virtual or physical address bits. This decides whether translation must happen before the cache can be accessed.
| Organisation | Index from | Tag from | Pros | Cons |
|---|---|---|---|---|
| PIPT (physically indexed, physically tagged) | Physical address | Physical address | Simple, no aliasing problems | TLB lookup must finish before cache access starts (slower) |
| VIVT (virtually indexed, virtually tagged) | Virtual address | Virtual address | No translation needed on a hit | Homonyms (same VA, different processes) need flushing or ASIDs; synonyms (two VAs for one PA) can create two copies of the same data |
| VIPT (virtually indexed, physically tagged) | Virtual address (offset bits) | Physical address | TLB and cache lookups happen in parallel | Cache size per way is limited by the page size |
Why VIPT Works and Its Size Limit
The page offset is identical in the virtual and physical address. If the cache's index + block offset bits all lie inside the page offset, the cache can start reading the set using the virtual address while the TLB translates the VPN. By the time the set's tags are read, the PFN is ready for the tag comparison.
virtual address: | VPN (to TLB) | page offset (12) |
| index | block offset |
└── must fit in here ──┘
Condition: index bits + block offset bits ≤ page offset bits
⇔ cache size / associativity ≤ page sizeExample: 4 KB pages, 32 KB L1 data cache. Cache size / associativity must be at most 4 KB, so the cache must be at least 8-way set associative. Indeed, many processors with 4 KB pages use a 32 KB 8-way or 48 KB 12-way L1 data cache: 32 KB / 8 = 48 KB / 12 = 4 KB.
A 64 KB 4-way cache would need 16 KB per way, i.e. 14 index+offset bits, 2 more than the page offset. Those 2 bits come from the VPN, so the same physical block could appear in 4 different sets (an alias). Designs that do this need extra hardware or OS support (such as page colouring) to prevent duplicates.
Page Size: A Hardware Trade-off
| Larger pages (e.g. 2 MB, 1 GB) | Smaller pages (e.g. 4 KB) |
|---|---|
| Smaller page tables | Larger page tables |
| Greater TLB reach (entries × page size), fewer TLB misses | Less TLB reach |
| More internal fragmentation (half a page wasted on average at the end of a region) | Less internal fragmentation |
| Fewer, larger disk transfers per fault | Finer-grained memory use and protection |
| Allows larger VIPT caches per way | Limits VIPT cache size per way |
Modern processors support several page sizes at once (for example 4 KB, 2 MB and 1 GB on x86-64), and the OS uses big pages where they help.
Cache vs Virtual Memory
| Aspect | Cache (CPU ↔ RAM) | Virtual memory (RAM ↔ disk) |
|---|---|---|
| Unit | Block / line (e.g. 64 B) | Page (e.g. 4 KB) |
| Miss called | Cache miss | Page fault |
| Miss penalty | Tens to hundreds of cycles | Millions of cycles |
| Miss handled by | Hardware entirely | OS software (with hardware exception support) |
| Placement | Direct / set associative | Fully associative (any frame) |
| Replacement | Simple hardware (LRU, PLRU, random) | Sophisticated OS algorithms |
| Write policy | Write-through or write-back | Always write-back (dirty bit) |
Common Mistakes
Translating the offset. Only the page number is translated; the offset is copied unchanged.
Confusing the TLB with the data cache. The TLB caches translations; L1/L2/L3 cache data and instructions.
Using the physical address width to count page-table entries. The number of entries depends on the virtual address space; the PFN width depends on the physical one.
Forgetting the page-table levels on a TLB miss. A k-level walk costs k memory accesses before the data access.
Getting the VIPT condition backwards. It is cache size ÷ associativity ≤ page size, not cache size ≤ page size.
Thinking a page fault is an error. A page fault on a valid but non-resident page is normal; only an access to an unmapped or forbidden address is an error (segmentation fault).
GATE and Interview Questions
Q1. A system has 36-bit virtual addresses, 8 KB pages and 4-byte PTEs. How big is a single-level page table?
Offset = 13 bits, so VPN = 23 bits and there are 223 entries. Size = 223 × 4 B = 225 B = 32 MB.
Q2. A TLB has 128 entries and is 4-way set associative. Virtual addresses are 32 bits and pages are 4 KB. How many bits are in each TLB tag?
VPN = 32 − 12 = 20 bits. Sets = 128 / 4 = 32, so index = 5 bits. Tag = 20 − 5 = 15 bits.
Q3. TLB lookup takes 5 ns, memory access 100 ns, TLB hit ratio 90%, two-level page table. Find the effective access time.
Hit: 5 + 100 = 105 ns. Miss: 5 + 2 × 100 + 100 = 305 ns. EAT = 0.9 × 105 + 0.1 × 305 = 94.5 + 30.5 = 125 ns.
Q4. A VIPT L1 cache is 64 KB with 4 KB pages. What is the minimum associativity that avoids aliasing?
We need cache size / associativity ≤ page size, so associativity ≥ 64 KB / 4 KB = 16.
Q5. Why is virtual memory fully associative and write-back, while L1 caches are set associative and sometimes write-through?
A page fault costs millions of cycles (a disk access), so it is worth any lookup cost to minimise faults: full associativity and clever OS replacement. Writing through to disk on every store would be impossibly slow, so it must be write-back. An L1 cache must answer in a few cycles, so it uses limited associativity and simple hardware policies.
Q6. What is TLB reach? Compute it for 64 entries with 4 KB and with 2 MB pages.
TLB reach = entries × page size, the amount of memory accessible without TLB misses. 64 × 4 KB = 256 KB; 64 × 2 MB = 128 MB.
Summary
The MMU translates every virtual address to a physical address and checks permissions; the page-table base register points to the current page table.
VA = VPN | offset; PA = PFN | offset. Only the page number is translated.
A PTE holds the PFN and valid, protection, referenced and dirty bits. Single-level table size = 2VPN bits × PTE size.
Multi-level tables split the VPN into several 9-bit indexes on modern 64-bit systems (Sv39: 3 levels, x86-64: 4 or 5).
The TLB caches translations; it is organised like a cache (tag = high VPN bits, index = low VPN bits). EAT = h(t + m) + (1 − h)(t + k·m + m).
A page fault is a precise exception: the instruction is undone, the OS loads the page, and the instruction is restarted.
VIPT caches overlap TLB and cache lookup, provided cache size ÷ associativity ≤ page size.
Next, Secondary Storage: Magnetic Disks & SSDs looks at the bottom of the hierarchy, the devices that hold the pages that are not in RAM.