Lesson 8: Virtual Memory & the TLB

Opening: every process lives inside its own illusion

Lesson 7 sped up access to PHYSICAL memory using caches. But the address a program SEES (a pointer in C, a variable inside a JS engine) is rarely the real PHYSICAL address on the RAM stick — the operating system inserts a layer of indirection: each process gets its own VIRTUAL address space, fully isolated from every other process, translated into a real PHYSICAL address on every single access. What that indirection costs — and how the hardware hides it — is this lesson's subject.

1. Virtual memory & paging

Virtual memory allows: (1) running a program LARGER THAN physical RAM (the unused parts live on disk and are loaded into RAM on demand), and (2) safe ISOLATION — process A cannot accidentally (or deliberately) read or write process B's memory, because A's and B's virtual addresses translate into entirely different physical REGIONS. Memory is divided into fixed-size pages — typically 4KB by default — and a Page Table records which PHYSICAL page (a page frame) each VIRTUAL page currently points at.

A virtual address (32-bit example):
+----------------------------+---------------+
|  VPN (Virtual Page Number) |   Offset      |
|          20 bits           |    12 bits    |
+----------------------------+---------------+
   looks up the Page Table     byte WITHIN the page (unchanged by translation)

# The VPN indexes the Page Table -> PFN (Physical Frame Number)
# Physical address = (PFN << 12) | Offset
#   the offset is carried over UNCHANGED; only the VPN is translated

2. The MMU, and what a page table entry really contains

Section 1 said the Page Table "records which physical page each virtual page points at", but it did not say WHO does the looking up, nor what an entry in that table actually holds. Those two questions decide the rest of the lesson.

The one doing the lookup is the MMU (Memory Management Unit): a piece of hardware inside the CPU, not a part of the operating system. Every time a program reads or writes an address, the MMU intercepts that virtual address, consults the page table, and only then releases the corresponding physical address. The operating system merely builds the page table; the MMU is what enforces it on every access, so a program has no way to route around it.

And a page table entry — a PTE (Page Table Entry) — is not just a PFN. That is why Section 3 is about to compute "4 bytes per entry" rather than the 20 bits a PFN alone would need. Alongside the PFN, a PTE carries several flag bits that the MMU reads on EVERY access:

One Page Table Entry (PTE), simplified:
+--------------------------+-----+-----+-----+-----+
|  PFN (physical frame)    |  NX | R/W |  D  |  P  |
+--------------------------+-----+-----+-----+-----+
                              |     |     |     |
   no-execute -----------------+    |     |     |
   writable? (0 = read-only) -------+     |     |
   dirty: page was written to ------------+     |
   present: mapping is valid at all ------------+

# The MMU reads these flags on EVERY access, in hardware.
# P = 0  -> the mapping does not exist -> raise a page fault
# R/W= 0 -> a write to this page raises a fault (read-only page)
# NX = 1 -> executing code from this page raises a fault
# D  = 1 -> the page differs from its copy on disk (see Lesson 7: write-back)

With those four bits, three things Section 1 only asserted now have a concrete mechanism:

• How a page fault is DETECTED. Not by "failing to find" anything — but by the P (present) bit. The MMU reads the PTE, sees $P=0$, and immediately raises an exception for the operating system to handle (load the page from disk into RAM, update the PTE, then re-run the faulting instruction). The program never learns this happened — it only sees one of its instructions take a few million cycles longer than usual.
• How isolation is ENFORCED. Section 1 said virtual memory provides "safe isolation", but a private page table is only half of it: it stops process A from reaching process B's memory. The other half is the R/W and NX bits, which stop a process from harming ITSELF — writing into a read-only region, or executing data as though it were code. This is exactly the mechanism Lesson 2 promised when it said the operating system marks code regions "read-only and non-writable (the NX/XD bit) right down at the MMU hardware level" — this NX bit in the PTE is precisely what makes Lesson 2's self-modifying code impossible on a modern system.
• Why swapping a page out is sometimes FREE. The D (dirty) bit records whether the page has been WRITTEN since it was loaded — the same meaning as the cache dirty bit in Lesson 7, just at page granularity instead of cache-line granularity. If $D=0$, the copy on disk is still identical, so the operating system can simply DROP the page from RAM and write nothing at all. If $D=1$, it must write the page out to disk first — thousands of times slower. The same operation, "free up one page", costs wildly differently depending on exactly one bit.

3. Computing page table structure & size

For an $A$-bit virtual address with an $O$-bit page offset ($2^O$ bytes per page), the MAXIMUM possible number of virtual pages is $2^{A-O}$. The most naive SINGLE-LEVEL page table allocates room for EVERY possible virtual page — including the ones the program will NEVER touch:

$$\text{Single-level Page Table Size} = 2^{A-O} \times \text{Entry Size}$$

Verified for real: with a 32-bit virtual address, 4KB pages ($O=12$) and a 4-byte entry (PTE), a single-level page table costs exactly 4,194,304 bytes = 4MB per process. That sounds tolerable — but for a 64-bit address (real modern CPUs use 48 usable bits), the SAME formula yields 256GB — utterly impossible for a data structure that must exist SEPARATELY for EVERY running process.

function pageTableEntryCount(addressBits, pageOffsetBits) {
  return Math.pow(2, addressBits - pageOffsetBits);
}
function singleLevelPageTableSizeBytes(addressBits, pageOffsetBits, entryBytes) {
  return pageTableEntryCount(addressBits, pageOffsetBits) * entryBytes;
}
// Verified: singleLevelPageTableSizeBytes(32, 12, 4) = 4.194.304 byte (4MB)
// Verified: singleLevelPageTableSizeBytes(48, 12, 4) / 1024^3 = 256 (GB - impossible!)

The real solution: a MULTI-LEVEL page table (x86 32-bit splits it 10-10-12 bits) — the level-1 table is ALWAYS allocated (small, fixed size), but a level-2 table is allocated ONLY for regions that genuinely have pages in use. Verified for real: with 512 pages in use (2MB of address space actually touched, out of the 4GB available in a 32-bit space) — a 2-level page table costs just 8,192 bytes (8KB), exactly 512 times cheaper than single-level (4MB).

function twoLevelPageTableSizeBytes(numUsedPages, entriesPerTable, entryBytes) {
  const firstLevelBytes = entriesPerTable * entryBytes;              // ALWAYS allocated
  // only the regions actually in use
  const numSecondLevelTables = Math.ceil(numUsedPages / entriesPerTable);
  const tableBytes = entriesPerTable * entryBytes;
  return firstLevelBytes + numSecondLevelTables * tableBytes;
}
// Verified: twoLevelPageTableSizeBytes(512, 1024, 4) = 8192 bytes (8KB)
// Against 4MB single-level for the SAME 32-bit space -> 512x cheaper

4. The TLB: the address-translation accelerator

The problem: the Page Table ITSELF lives in RAM — meaning that EVERY time the CPU needs to translate a virtual address into a physical one, it must spend an EXTRA RAM access reading the page table, BEFORE the SECOND RAM access that fetches the data it actually wanted. The TLB (Translation Lookaside Buffer) solves this by acting as a cache FOR the page table: it stores recently translated (VPN → PFN) pairs, using exactly the Set-Associative + LRU structure of Lesson 7.

It is worth pausing on precisely what a TLB miss costs, because that is the entire reason the TLB exists. When the TLB has no translation, the MMU has to go and consult the page table in RAM itself — an operation with its own name: a page table walk. And the number of RAM trips equals the NUMBER OF LEVELS in the table, because each level lives somewhere different:

TLB HIT  -> 1 RAM access total:
             (translation comes from the TLB, on-chip)
             [1] read the data itself

TLB MISS -> 3 RAM accesses total, with the 2-level table of Section 3:
             [1] read the level-1 table   -> address of the level-2 table
             [2] read the level-2 table   -> the PFN
             [3] read the data itself

# So a TLB miss costs 3x the memory traffic of a hit, not 2x - the walk is
# EXTRA work on top of the access you actually wanted.
# On x86-64 the page table has FOUR levels, so a miss there costs 5 accesses.

That is this section's number to remember: with the 2-level table, a failed translation costs 3 RAM trips instead of 1, and the real 4-level table of x86-64 costs 5. Section 3 showed that a multi-level structure is the ONLY thing that makes a page table fit in RAM at all — but its price is that each lookup grows longer with each level. The TLB is what buys that price back: as long as the translation is still in the TLB, the whole walk is skipped entirely.

function translateAddress(virtualAddress, pageOffsetBits, tlb, pageTable) {
  const { vpn, offset } = splitVirtualAddress(virtualAddress, pageOffsetBits);
  let pfn = tlb.lookup(vpn);
  if (pfn !== null) {
    const physicalAddress = (pfn << pageOffsetBits) | offset;
    return { physicalAddress, tlbHit: true, pageFault: false };
  }
  if (pageTable.has(vpn)) {
    pfn = pageTable.get(vpn);
    tlb.insert(vpn, pfn); // remember it for next time
    const physicalAddress = (pfn << pageOffsetBits) | offset;
    return { physicalAddress, tlbHit: false, pageFault: false };
  }
  return { physicalAddress: null, tlbHit: false, pageFault: true }; // VPN is not mapped
}
// Verified: first access to a VPN  -> tlbHit=false (the Page Table is consulted)
// Verified: SECOND access, same VPN -> tlbHit=true  (now cached in the TLB)
// Verified: access to an unmapped VPN -> pageFault=true

5. Hands-on: translating virtual addresses live & simulating the TLB

Enter a virtual address (in hex) to translate it through a REAL TLB + Page Table (3 pages are pre-mapped: VPN 5, 6 and 9) — try the SAME address twice to watch the TLB go from MISS to HIT, or try another VPN to see a page fault. The calculator below compares single-level against two-level page table size directly:

Summary

• ✅ Virtual memory lets a program exceed physical RAM and isolates processes safely, through a Page Table translating VPN → PFN.
• ✅ The MMU is the HARDWARE block inside the CPU that enforces the page table on every access; a PTE holds not just the PFN but P/R-W/NX/D bits — P is how a page fault gets detected, R/W and NX are how isolation gets enforced, and D decides whether swapping a page out requires a write at all.
• ✅ A TLB miss forces the MMU to walk the page table itself: a 2-level table costs 3 RAM trips instead of 1, and x86-64's 4-level table costs 5 — which is the entire reason the TLB exists.
• ✅ Verified: a 32-bit single-level page table costs 4MB; a 48-bit space (real 64-bit) would need 256GB — impossible, forcing a multi-level structure.
• ✅ Verified: a 2-level page table costs only 8KB when 2MB of address space is actually used — 512 times cheaper than single-level, because level-2 tables are allocated only for regions genuinely in use.
• ✅ The TLB is a cache FOR the page table — verified: the first access to a page is a TLB miss, the next access to the SAME page is a TLB hit, and accessing an unmapped page raises a page fault.
• ✅ Pitfall: the TLB must be flushed on every context switch — the hidden cost of changing process.

Review quiz