Virtual memory

Vocabulary

English	Meaning
virtual address	An address in a process's virtual address space, translated or checked by memory-management hardware.
page table/peɪdʒ ˈteɪbl/	A structure recording virtual-page mappings and access information.
physical frame	A fixed-size block of physical memory that can hold a page.
TLB	Translation lookaside buffer: a cache of recent virtual-to-physical address translations.
page fault/peɪdʒ fɒlt/	An exception raised when a memory access cannot be completed using the current page mapping, for example because the required page is not in physical memory.

The grandest illusion

The virtual address splits into page number and offset; the page table maps virtual pages to physical frames, one entry per page; the TLB caches translations.
Course machine: 16-bit virtual, 256-byte pages $\Rightarrow$ 256 virtual pages; 12-bit physical $\Rightarrow$ 16 frames — each process may address 64 KiB while only 4 KiB exists.

{exercise:uni-cs0704-mapping}

Practice

16-bit virtual addresses with 256-byte pages give — virtual pages

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Address $0x0204$: offset $0x04$, VPN $0x02$. First access: TLB miss, table walk — VPN 2 to frame 5, physical $5 \times 256 + 4 = 0x0504$; the TLB caches VPN 2.
Address $0x0210$: same VPN — TLB hit, physical $0x0510$, no walk. An 8-page loop of 8000 accesses with a 10-entry LRU TLB misses 8 times (compulsory): a $99.9\%$ hit rate.

{exercise:uni-cs0704-walk}

Practice

With VPN 2 mapped to frame 5, address 0x0204 translates to —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Address $0x0400$: VPN 4, entry invalid $\to$ page fault. The process blocks; the OS picks a victim (LRU, dirty — write it back), reads the page in, updates table and TLB, restarts the instruction.
Cost model: TLB hit 1 ns, walk 10 ns, fault 5 ms — one fault per million accesses still costs 5 ns per access on average: the hierarchy tolerates rarity, not frequency.

Example

An invalid access is an error; a fault is just a fetch. The valid bit tells them apart.

{exercise:uni-cs0704-fault}

Practice

A page fault differs from an invalid access because the fault —

Difficulty 1/5 · 100 coins + a small bonus on first completion today