Virtual Memory & Page Tables

in reviewThis lesson is complete and being validated before release - details may still change.

Virtual memory

Loading interactive demo…

The left grid is the virtual address space, 16 pages of 4 words, each cell a page showing the frame that holds it. The right grid is the physical memory, one cell per frame showing the page inside it. The strip between them is the translation buffer, the pairs it remembers; the strip beneath is the access stream, each address marked as it resolves. Tap a virtual word to ask where it really is.Take the tour, or press and explore. Legend:

The panel beside the stage is the real VirtualMemory class from the published library executing in your browser, with the current line highlighted.

The page being translated and the frame it resolves to.
A page that is in memory, and a table walk in the stream.
A buffer hit in the stream, and a buffer entry just used.
A page fault in the stream, and a frame about to be emptied.
A page on disk, a free frame, and accesses still to come.

accesses counts the stream so far; buffer hits, walks, and faults split it by what the translation cost; evictions counts the faults that threw a page out rather than filling a free frame.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The lie. The stack and heap lesson drew a program's memory as 32 words from 0 to 31. No program has ever had that. The addresses a program uses are virtual: a numbering that belongs to the program alone, that starts at zero for every process, and that the hardware translates on every single access into a physical address in the memory that actually exists. The translation is what lets two programs both use address 100, lets a program use more memory than the machine has, and keeps one process out of another's data.

Pages and frames. Translating every word would need a table as large as memory, so addresses are translated in pages. With $P$ words per page, virtual address $a$ is word $a \bmod P$ of page $\lfloor a / P \rfloor$ ; on this stage $P = 4$ , so the two low bits are the offset and the rest the page number. Physical memory is cut into frames of the same size, and the page table has one entry per virtual page saying which frame holds it, or that none does. The physical address is $f \cdot P + (a \bmod P)$ for frame $f$ . Only the page number changes; the offset passes straight through.

Three costs. A translation can be answered three ways, and the whole design is about how often each happens. The translation lookaside buffer, a cache of the last few page-to-frame pairs, answers in a cycle: a hit. A miss walks the page table in memory, an access or several: a walk. An entry with no frame is a page fault: the operating system takes over, finds a frame, reads the page from disk in milliseconds, fills the entry, and restarts the instruction, which never knows it was interrupted. The ratios are roughly one, a hundred, and a million, so the stage's fault count is the number that matters.

Replacement. When every frame is full, a fault must evict a page. First in, first out evicts the page loaded earliest, which is cheap to track and ignores use. Least recently used evicts the page untouched longest, which is what the cache lesson's lines do and what real systems approximate with a referenced bit per page, since exact timestamps cost too much. Neither is optimal: Belady showed the best policy evicts the page needed furthest in the future, which nothing can know.

The working set and thrashing. A program touches a few pages heavily at a time, its working set. With at least that many frames it faults once per page and then hits; with one fewer it can fault on every access, because the page it wants next is always the one it just gave up. The big loop pattern cycles through five pages on four frames: fifteen faults in fifteen accesses under either policy, and zero after the first five with a fifth frame. A machine in that state is thrashing, and the cure is memory or fewer programs, not a cleverer policy.

The buffer. The TLB is the cache lesson again, one level up: a few entries, a tag that is the page number, replacement of the entry used longest ago. A working set that fits the frames but not the buffer walks the table on every return, which costs cycles but not milliseconds. Real buffers hold dozens to thousands of entries, and larger pages make each entry cover more memory, which is why databases ask for huge pages.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

access tries the buffer, then the table, then the disk, in that order, and returns from the first that answers. The three branches are the three costs, and a run's report counts each.
The page table is an array of frame numbers or null, one entry per virtual page. Real tables are trees of such arrays so that an address space of billions of pages costs memory only where it is used.
victim is one reduce with the policy choosing the key, the load time for first in first out, the last use for least recently used. The two policies differ by one line, and by a great deal in what they evict.
An eviction clears the victim's table entry and buffer entry, so that the next touch of that page is a fault and never a stale translation. Forgetting to do the second is a classic bug in real systems, which call it a TLB shootdown when many cores must forget at once.
remember fills the buffer after a walk or a fault, dropping the entry used longest ago, and reports which page it forgot so the stage can say so.
The disk is a fault counter, not a device: the class models what is in memory, not the bytes, so a page's contents never appear.

The Atlas computer built at Manchester between 1959 and 1962 had a small core memory and a large drum, and its designers wanted programs to use the drum without knowing it was there. Their one-level store split addresses into pages, kept a set of associative page address registers that were the first translation buffer, and moved pages between drum and core behind the program's back. IBM resisted the idea for a decade and then made it universal with System/370 in 1972, Peter Denning gave it its theory with the working set, and the 386 brought it to every desk in 1985.

1962Tom Kilburn and the Atlas team - Atlas runs with a one-level store: paged addresses, associative page registers answering most translations, and a supervisor moving pages between drum and core.source
1966Laszlo Belady - A study of replacement algorithms gives the optimal policy, evicting the page needed furthest in the future, as the yardstick every real policy is measured against.source
1968Peter Denning - The working set model explains thrashing: a program needs its recently used pages resident, and with fewer frames than that it does nothing but fault.source
1972IBM - System/370 gains virtual memory, after years of IBM arguing that paging was too slow for commercial machines.source
1985Intel - The 80386 adds paging to the x86 line, the hardware that let Windows NT, OS/2, and Linux give every process its own address space on a PC.source

Used today

Every process on your machine - Each gets a private address space starting at zero; the page table is what keeps one program's pointers out of another's memory.
Memory-mapped files - A file mapped into the address space is read by faulting its pages in, so a program can treat a disk file as an array.
Copy on write - Forking a process shares every page read-only and copies one only when it is written, which is how a fork is cheap.

pattern

frames4

buffer

replace

seed1

accesses: 15 of 15
buffer hits: 5
walks: 1
faults: 9 (60%)
evictions: 5

virtual-memory.ts

import type { Tracer } from "../trace";/** Words per page: an address is a page number and an offset inside it. */export const PAGE_WORDS = 4;/** Pages in the virtual address space a process sees. */export const VIRTUAL_PAGES = 16;export const VIRTUAL_WORDS = PAGE_WORDS * VIRTUAL_PAGES;export const MAX_FRAMES = 8;export const MAX_TLB_ENTRIES = 4;export const MAX_ACCESSES = 64;/** Which resident page gives up its frame on a fault with no frame free. */export const REPLACEMENT_POLICIES = ["fifo", "lru"] as const;export type ReplacementPolicy = (typeof REPLACEMENT_POLICIES)[number];export interface PagingConfig {  /** Physical frames: how many pages can be in memory at once. */  frames: number;  /** Translations the translation lookaside buffer remembers. */  tlbEntries: number;  policy: ReplacementPolicy;}export interface TlbEntry {  page: number;  frame: number;  lastUsed: number;}export interface FrameState {  /** The virtual page in this frame, or null while it is free. */  page: number | null;  loadedAt: number;  lastUsed: number;}export interface Translation {  address: number;  page: number;  offset: number;  frame: number;  physical: number;  /** Where the frame number came from: the buffer, the table, or the disk after a fault. */  source: "tlb" | "table" | "disk";  /** The page a fault threw out of memory, or null. */  evicted: number | null;}export interface PagingReport {  accesses: number;  tlbHits: number;  walks: number;  faults: number;  evictions: number;  faultRate: number;}/** * The memory a process sees is not the memory that exists. Every address * a program uses is virtual: a page number and an offset. A page table, * one entry per virtual page, says which physical frame holds the page, * if any. A translation lookaside buffer (TLB), a tiny cache of recent * translations, answers most lookups without touching the table; a * miss walks the table; and a page with no frame is a page fault, which * loads it from disk into a free frame or, with none free, into the * frame of a victim chosen by a replacement policy, first in first out * or least recently used. The program never notices any of this, * except in time: a hit is a cycle, a walk is a memory access, a fault * is a disk read. * * Time: O(tlbEntries + frames) per access. Space: O(VIRTUAL_PAGES + frames). */export class VirtualMemory {  private readonly pageTable: (number | null)[] = new Array<number | null>(VIRTUAL_PAGES).fill(null);  private readonly frames: FrameState[];  private tlb: TlbEntry[] = [];  private time = 0;  private tlbHits = 0;  private walks = 0;  private faults = 0;  private evictions = 0;  constructor(    readonly config: PagingConfig,    private readonly tracer?: Tracer,  ) {    const { frames, tlbEntries, policy } = config;    if (!Number.isInteger(frames) || frames < 1 || frames > MAX_FRAMES) throw new RangeError(`frames must be in [1, ${MAX_FRAMES}]`);    if (!Number.isInteger(tlbEntries) || tlbEntries < 1 || tlbEntries > MAX_TLB_ENTRIES) throw new RangeError(`tlbEntries must be in [1, ${MAX_TLB_ENTRIES}]`);    if (!REPLACEMENT_POLICIES.includes(policy)) throw new RangeError(`unknown policy ${String(policy)}`);    this.frames = Array.from({ length: frames }, () => ({ page: null, loadedAt: 0, lastUsed: 0 }));  }  /** The frame holding each virtual page, or null; a copy. */  table(): readonly (number | null)[] {    return [...this.pageTable];  }  /** The buffer's entries, most recently filled last; a copy. */  buffer(): readonly TlbEntry[] {    return this.tlb.map((entry) => ({ ...entry }));  }  /** The page in each frame, or null; a copy. */  residents(): readonly (number | null)[] {    return this.frames.map((frame) => frame.page);  }  /** One access by virtual address: a TLB hit, a table walk, or a page fault. */  access(address: number): Translation {    if (!Number.isInteger(address) || address < 0 || address >= VIRTUAL_WORDS) throw new RangeError(`address ${address} is outside the ${VIRTUAL_WORDS}-word space`);    this.time++;    const page = Math.floor(address / PAGE_WORDS);    const offset = address % PAGE_WORDS;    // ▸ split the virtual address: the high part names the page, the low part the word inside it    this.tracer?.emit("translate", { address, page, offset, time: this.time, cached: this.tlb.map((entry) => entry.page) });    const cached = this.tlb.find((entry) => entry.page === page);    if (cached) {      cached.lastUsed = this.time;      this.frames[cached.frame]!.lastUsed = this.time;      this.tlbHits++;      const physical = cached.frame * PAGE_WORDS + offset;      // ▸ the buffer remembers this page's frame, so the physical address is known at once      this.tracer?.emit("hit", { page, frame: cached.frame, physical, hits: this.tlbHits });      return { address, page, offset, frame: cached.frame, physical, source: "tlb", evicted: null };    }    let frame = this.pageTable[page] ?? null;    let source: Translation["source"] = "table";    let evicted: number | null = null;    if (frame !== null) {      this.walks++;      const dropped = this.remember(page, frame);      const pageForgotten = this.remember(page, frame);      // ▸ the buffer does not, but the page table has a frame for the page: read it and remember it      this.tracer?.emit("walk", { page, frame, physical: frame * PAGE_WORDS + offset, dropped, walks: this.walks });      this.tracer?.emit("walk", { page, frame, physical: frame * PAGE_WORDS + offset, pageForgotten, walks: this.walks });    } else {      // The page is on disk. Take a free frame, or make one.      frame = this.frames.findIndex((state) => state.page === null);      if (frame === -1) {        frame = this.victim();        const victim = this.frames[frame]!;        evicted = victim.page;        this.pageTable[evicted!] = null;        this.tlb = this.tlb.filter((entry) => entry.page !== evicted);        this.evictions++;        // ▸ no frame is free: the policy picks a resident page to give up its frame        this.tracer?.emit("evict", { page: evicted, frame, policy: this.config.policy, loadedAt: victim.loadedAt, lastUsed: victim.lastUsed, evictions: this.evictions });      }      this.frames[frame] = { page, loadedAt: this.time, lastUsed: this.time };      this.pageTable[page] = frame;      this.faults++;      source = "disk";      const dropped = this.remember(page, frame);      const pageForgotten = this.remember(page, frame);      // ▸ the page is not in memory: read it from disk into a frame and record the frame in the table      this.tracer?.emit("fault", { page, frame, physical: frame * PAGE_WORDS + offset, evicted, dropped, faults: this.faults, resident: this.frames.filter((state) => state.page !== null).length });      this.tracer?.emit("fault", { page, frame, physical: frame * PAGE_WORDS + offset, evicted, pageForgotten, faults: this.faults, resident: this.frames.filter((state) => state.page !== null).length });    }    this.frames[frame]!.lastUsed = this.time;    return { address, page, offset, frame, physical: frame * PAGE_WORDS + offset, source, evicted };  }  /** Every access in order. */  run(addresses: readonly number[]): PagingReport {    if (addresses.length > MAX_ACCESSES) throw new RangeError(`${addresses.length} accesses exceeds ${MAX_ACCESSES}`);    for (const address of addresses) this.access(address);    return this.report();  }  /** The frame whose page the policy gives up: loaded longest ago, or used longest ago. */  private victim(): number {    const key = (state: FrameState): number => (this.config.policy === "fifo" ? state.loadedAt : state.lastUsed);    return this.frames.reduce((oldest, state, i) => (key(state) < key(this.frames[oldest]!) ? i : oldest), 0);  }  /** Caches a translation, dropping the least recently used entry when the buffer is full; returns the page dropped, or null. */  private remember(page: number, frame: number): number | null {    let dropped: number | null = null;    let pageForgotten: number | null = null;    if (this.tlb.length === this.config.tlbEntries) {      const stale = this.tlb.reduce((oldest, entry, i) => (entry.lastUsed < this.tlb[oldest]!.lastUsed ? i : oldest), 0);      const leastRecentEntry = this.tlb.reduce((oldest, entry, i) => (entry.lastUsed < this.tlb[oldest]!.lastUsed ? i : oldest), 0);      dropped = this.tlb[stale]!.page;      pageForgotten = this.tlb[leastRecentEntry]!.page;      this.tlb.splice(stale, 1);      this.tlb.splice(leastRecentEntry, 1);    }    this.tlb.push({ page, frame, lastUsed: this.time });    return dropped;    return pageForgotten;  }  report(): PagingReport {    const accesses = this.tlbHits + this.walks + this.faults;    return { accesses, tlbHits: this.tlbHits, walks: this.walks, faults: this.faults, evictions: this.evictions, faultRate: accesses === 0 ? 0 : this.faults / accesses };  }}

faults =: 9
faultRate =: 60%

15 accesses: 5 buffer hits, 1 table walk, and 9 page faults with 5 evictions, a fault rate of 60%.

import type { Tracer } from "../trace";/** Words per page: an address is a page number and an offset inside it. */export const PAGE_WORDS = 4;/** Pages in the virtual address space a process sees. */export const VIRTUAL_PAGES = 16;export const VIRTUAL_WORDS = PAGE_WORDS * VIRTUAL_PAGES;export const MAX_FRAMES = 8;export const MAX_TLB_ENTRIES = 4;export const MAX_ACCESSES = 64;/** Which resident page gives up its frame on a fault with no frame free. */export const REPLACEMENT_POLICIES = ["fifo", "lru"] as const;export type ReplacementPolicy = (typeof REPLACEMENT_POLICIES)[number];export interface PagingConfig { /** Physical frames: how many pages can be in memory at once. */ frames: number; /** Translations the translation lookaside buffer remembers. */ tlbEntries: number; policy: ReplacementPolicy;}export interface TlbEntry { page: number; frame: number; lastUsed: number;}export interface FrameState { /** The virtual page in this frame, or null while it is free. */ page: number | null; loadedAt: number; lastUsed: number;}export interface Translation { address: number; page: number; offset: number; frame: number; physical: number; /** Where the frame number came from: the buffer, the table, or the disk after a fault. */ source: "tlb" | "table" | "disk"; /** The page a fault threw out of memory, or null. */ evicted: number | null;}export interface PagingReport { accesses: number; tlbHits: number; walks: number; faults: number; evictions: number; faultRate: number;}/** * The memory a process sees is not the memory that exists. Every address * a program uses is virtual: a page number and an offset. A page table, * one entry per virtual page, says which physical frame holds the page, * if any. A translation lookaside buffer (TLB), a tiny cache of recent * translations, answers most lookups without touching the table; a * miss walks the table; and a page with no frame is a page fault, which * loads it from disk into a free frame or, with none free, into the * frame of a victim chosen by a replacement policy, first in first out * or least recently used. The program never notices any of this, * except in time: a hit is a cycle, a walk is a memory access, a fault * is a disk read. * * Time: O(tlbEntries + frames) per access. Space: O(VIRTUAL_PAGES + frames). */export class VirtualMemory { private readonly pageTable: (number | null)[] = new Array<number | null>(VIRTUAL_PAGES).fill(null); private readonly frames: FrameState[]; private tlb: TlbEntry[] = []; private time = 0; private tlbHits = 0; private walks = 0; private faults = 0; private evictions = 0; constructor( readonly config: PagingConfig, private readonly tracer?: Tracer, ) { const { frames, tlbEntries, policy } = config; if (!Number.isInteger(frames) || frames < 1 || frames > MAX_FRAMES) throw new RangeError(`frames must be in [1, ${MAX_FRAMES}]`); if (!Number.isInteger(tlbEntries) || tlbEntries < 1 || tlbEntries > MAX_TLB_ENTRIES) throw new RangeError(`tlbEntries must be in [1, ${MAX_TLB_ENTRIES}]`); if (!REPLACEMENT_POLICIES.includes(policy)) throw new RangeError(`unknown policy ${String(policy)}`); this.frames = Array.from({ length: frames }, () => ({ page: null, loadedAt: 0, lastUsed: 0 })); } /** The frame holding each virtual page, or null; a copy. */ table(): readonly (number | null)[] { return [...this.pageTable]; } /** The buffer's entries, most recently filled last; a copy. */ buffer(): readonly TlbEntry[] { return this.tlb.map((entry) => ({ ...entry })); } /** The page in each frame, or null; a copy. */ residents(): readonly (number | null)[] { return this.frames.map((frame) => frame.page); } /** One access by virtual address: a TLB hit, a table walk, or a page fault. */ access(address: number): Translation { if (!Number.isInteger(address) || address < 0 || address >= VIRTUAL_WORDS) throw new RangeError(`address ${address} is outside the ${VIRTUAL_WORDS}-word space`); this.time++; const page = Math.floor(address / PAGE_WORDS); const offset = address % PAGE_WORDS; // ▸ split the virtual address: the high part names the page, the low part the word inside it this.tracer?.emit("translate", { address, page, offset, time: this.time, cached: this.tlb.map((entry) => entry.page) }); const cached = this.tlb.find((entry) => entry.page === page); if (cached) { cached.lastUsed = this.time; this.frames[cached.frame]!.lastUsed = this.time; this.tlbHits++; const physical = cached.frame * PAGE_WORDS + offset; // ▸ the buffer remembers this page's frame, so the physical address is known at once this.tracer?.emit("hit", { page, frame: cached.frame, physical, hits: this.tlbHits }); return { address, page, offset, frame: cached.frame, physical, source: "tlb", evicted: null }; } let frame = this.pageTable[page] ?? null; let source: Translation["source"] = "table"; let evicted: number | null = null; if (frame !== null) { this.walks++; const dropped = this.remember(page, frame); const pageForgotten = this.remember(page, frame); // ▸ the buffer does not, but the page table has a frame for the page: read it and remember it this.tracer?.emit("walk", { page, frame, physical: frame * PAGE_WORDS + offset, dropped, walks: this.walks }); this.tracer?.emit("walk", { page, frame, physical: frame * PAGE_WORDS + offset, pageForgotten, walks: this.walks }); } else { // The page is on disk. Take a free frame, or make one. frame = this.frames.findIndex((state) => state.page === null); if (frame === -1) { frame = this.victim(); const victim = this.frames[frame]!; evicted = victim.page; this.pageTable[evicted!] = null; this.tlb = this.tlb.filter((entry) => entry.page !== evicted); this.evictions++; // ▸ no frame is free: the policy picks a resident page to give up its frame this.tracer?.emit("evict", { page: evicted, frame, policy: this.config.policy, loadedAt: victim.loadedAt, lastUsed: victim.lastUsed, evictions: this.evictions }); } this.frames[frame] = { page, loadedAt: this.time, lastUsed: this.time }; this.pageTable[page] = frame; this.faults++; source = "disk"; const dropped = this.remember(page, frame); const pageForgotten = this.remember(page, frame); // ▸ the page is not in memory: read it from disk into a frame and record the frame in the table this.tracer?.emit("fault", { page, frame, physical: frame * PAGE_WORDS + offset, evicted, dropped, faults: this.faults, resident: this.frames.filter((state) => state.page !== null).length }); this.tracer?.emit("fault", { page, frame, physical: frame * PAGE_WORDS + offset, evicted, pageForgotten, faults: this.faults, resident: this.frames.filter((state) => state.page !== null).length }); } this.frames[frame]!.lastUsed = this.time; return { address, page, offset, frame, physical: frame * PAGE_WORDS + offset, source, evicted }; } /** Every access in order. */ run(addresses: readonly number[]): PagingReport { if (addresses.length > MAX_ACCESSES) throw new RangeError(`${addresses.length} accesses exceeds ${MAX_ACCESSES}`); for (const address of addresses) this.access(address); return this.report(); } /** The frame whose page the policy gives up: loaded longest ago, or used longest ago. */ private victim(): number { const key = (state: FrameState): number => (this.config.policy === "fifo" ? state.loadedAt : state.lastUsed); return this.frames.reduce((oldest, state, i) => (key(state) < key(this.frames[oldest]!) ? i : oldest), 0); } /** Caches a translation, dropping the least recently used entry when the buffer is full; returns the page dropped, or null. */ private remember(page: number, frame: number): number | null { let dropped: number | null = null; let pageForgotten: number | null = null; if (this.tlb.length === this.config.tlbEntries) { const stale = this.tlb.reduce((oldest, entry, i) => (entry.lastUsed < this.tlb[oldest]!.lastUsed ? i : oldest), 0); const leastRecentEntry = this.tlb.reduce((oldest, entry, i) => (entry.lastUsed < this.tlb[oldest]!.lastUsed ? i : oldest), 0); dropped = this.tlb[stale]!.page; pageForgotten = this.tlb[leastRecentEntry]!.page; this.tlb.splice(stale, 1); this.tlb.splice(leastRecentEntry, 1); } this.tlb.push({ page, frame, lastUsed: this.time }); return dropped; return pageForgotten; } report(): PagingReport { const accesses = this.tlbHits + this.walks + this.faults; return { accesses, tlbHits: this.tlbHits, walks: this.walks, faults: this.faults, evictions: this.evictions, faultRate: accesses === 0 ? 0 : this.faults / accesses }; }}