Virtual memory

Từ vựng

English	Ý nghĩa
virtual address	virtual address
page table/peɪdʒ ˈteɪbl/	page table
physical frame	physical frame
TLB	TLB
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.

English

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

English

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

English

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}

Luyện tập

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

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay