Virtual Memory & TLB

How virtual addresses are translated to physical frames through the page table, and how the TLB caches translations to keep it fast.

9 min read Watch it move Build it

Virtual memory lets every program act as if it owns a huge, private, contiguous block of addresses — even though physical RAM is smaller, shared, and scattered. Each program uses virtual addresses; the hardware translates every one into a physical address in real RAM before the access happens. The translation table is the page table, and the TLB is the cache that keeps that translation fast.

Pages, frames, and the split address

Memory is cut into fixed-size pages (virtual side) and equal-size frames (physical side). A virtual address splits cleanly into a page number and an offset: the high bits name the page, the low bits name the byte inside it. Translation replaces the page number with its frame number and *keeps the offset unchanged*.

4 KB pages, 32-bit virtual address:

  offset = log2(4096) = 12 bits
  VPN    = 32 - 12     = 20 bits

  | virtual page number (20) | offset (12) |
            |  page table  |
            v
  | physical frame number | offset (12) |   (same offset)

Translating an address

1Split the virtual address into VPN (virtual page number) and offset.
2Look up the VPN in the TLB — a small cache of recent VPN -> frame translations.
3TLB hit: take the frame number directly. One quick step.
4TLB miss: walk the page table in memory to find the frame, then load that entry into the TLB.
5If the page table marks the page not in RAM, a page fault traps to the OS, which fetches the page from disk into a free frame.
6Combine the frame number with the original offset to form the physical address, then do the access.

Why the TLB matters

Without a TLB, *every* memory access would need an extra memory access just to read the page table — doubling the cost. The TLB caches the handful of translations a program is actively using, so the common case skips the page table entirely. Locality applies to translations too.

Worked example — effective access time

Say a memory access takes 100 ns and the TLB hit rate is 95%. On a hit, translation is essentially free and the access costs one memory reference. On a miss (single-level page table), reading the page table adds a second reference.

EAT = hit * (1 mem) + miss * (2 mem)
    = 0.95 * 100 + 0.05 * 200
    = 95 + 10
    = 105 ns

A 95% hit rate adds only 5 ns of overhead to a 100 ns access — translation is nearly invisible.

A page fault is not a TLB miss

A TLB miss just means the translation was not cached — the page may still be in RAM, found by walking the page table (microseconds at most). A page fault means the page is not in RAM at all and must come from disk (milliseconds) — thousands of times costlier. Do not conflate them.

OperationTimeSpace

TLB hit · translation is free~1 cyclesmall cache

TLB miss (page in RAM) · walk the tableextra mem accesspage table

Page fault · OS loads the page~ms (disk)frame + disk

Check yourself

Memory access is 100 ns and the TLB hit rate is 95%; a miss needs a second access for the page table. What is the effective access time?