Exercises — Virtual memory — concept, page table, virtual-to-physical translation

$4\text{ KiB}=2^{12}$ bytes, so offset $=12$ bits (you need 12 bits to index 4096 bytes). VPN $=32-12=$ 20 bits. ::: offset = 12 bits, VPN = 20 bits

The offset (low 12 bits). Only the VPN is translated to a PFN; the offset indexes the same position inside the equally-sized frame. ::: The offset.

S — Split. Offset = low 12 bits of 0x5A3C. In binary 0x5A3C = 0101 1010 0011 1100; the low 12 bits are 1010 0011 1100 = 0xA3C. The bits above bit 11 give VPN = 0x5. L — Lookup. $\text{PageTable}[0x5]=0x12=$ PFN. C — Concatenate. $\text{PA}=(0x12\ll 12)|0xA3C=0x12000|0xA3C=$ 0x12A3C. ::: PA = 0x12A3C

$1\text{ KiB}=2^{10}$ → offset = 10 bits. VPN $=16-10=$ 6 bits. Entries $=2^6=$ 64 (one per possible virtual page). ::: offset 10, VPN 6, entries 64

Entries $=2^{32-12}=2^{20}=1,048,576$. Size $=2^{20}\times 4\text{ B}=2^{22}\text{ B}=$ 4 MiB per process. With hundreds of processes, that's gigabytes of tables for programs that touch only a few pages — the exact motivation for Multi-level Page Tables, which allocate sub-tables only for used regions. ::: 4 MiB per process

1. MMU splits the address, looks up VPN 0x9, sees valid = 0 → raises a page fault trap.
2. OS locates the page on disk (swap), picks a free frame — or evicts one via a replacement policy — and loads the data.
3. OS writes the new PFN into PageTable[0x9] and sets valid = 1.
4. The faulting instruction restarts (it never completed its memory access), and translation now succeeds. ::: Fault → OS loads page & updates entry → instruction restarts.

(a) $4\text{ KiB}=2^{12}$ → offset = 12 bits. (b) VPN $=48-12=$ 36 bits. (c) PFN $=40-12=$ 28 bits. (d) VA is $48-40=$ 8 bits wider. The virtual space ($2^{48}$ bytes) is $2^8=256\times$ larger than physical RAM's addressable space ($2^{40}$ bytes) — that surplus is exactly the over-commitment virtual memory buys you (extra pages live on disk). ::: offset 12, VPN 36, PFN 28, VA 8 bits wider (256× virtual/physical)

Offset of 0x00401000 = low 12 bits = 0x000. VPN = 0x401.

• A: $\text{PA}=(0xABC\ll 12)|0x000=$ 0xABC000.
• B: $\text{PA}=(0x777\ll 12)|0x000=$ 0x777000. Same virtual address, different frames → isolation. Achieved by per-process page tables; a context switch reloads the page-table base register (CR3) so each process sees its own map. ::: A → 0xABC000, B → 0x777000 (per-process tables give isolation)

The page table lives in RAM, so a naïve translation needs two RAM trips: one to fetch the entry (100 ns) and one to fetch the data (100 ns) → 200 ns total, i.e. 2× slower. This is exactly why a TLB exists: it caches recent VPN→PFN mappings on-chip so most translations skip the first RAM trip. Locality (see Cache Memory and Locality) is what makes the TLB hit rate high. ::: 200 ns, 2× slowdown

$\text{EAT}=0.95(1+100)+0.05(100+100)$ $=0.95\times 101+0.05\times 200=95.95+10=105.95\mathbf{ns}.$ The TLB collapsed a 200 ns worst case down to ~106 ns — close to the ideal 100 ns — purely by caching translations for the 95% common case. ::: EAT = 105.95 ns

Binary of 0xC0402ABC: 1100 0000 0100 0000 0010 1010 1011 1100.

• Offset = low 12 bits = 1010 1011 1100 = 0xABC.
• The remaining 20 bits are 1100 0000 0100 0000 0010 (the VPN).
• Level-1 index = top 10 bits of the VPN = 11 0000 0001 = 0x301 (= 769).
• Level-2 index = next 10 bits = 00 0000 0010 = 0x002 (= 2). Check: $(769\times 2^{22})+(2\times 2^{12})+\text{0xABC}=\text{0xC0402ABC}$. The MMU indexes the level-1 table with 0x301, follows that to a level-2 table, indexes it with 0x002, and reads the PFN — see Multi-level Page Tables. ::: offset 0xABC, L1 index 0x301 (769), L2 index 0x002 (2)

• Q: 48-bit VA, 40-bit PA, 4 KiB pages — PFN bits? ::: 28.
• Q: Naïve (no TLB) access with 100 ns RAM — total? ::: 200 ns.
• Q: Same VA in two processes maps to different frames because…? ::: per-process page tables (isolation).
• Q: In a 10/10/12 two-level scheme, how wide is each level index? ::: 10 bits.
• Q: What must you peel off before splitting the VPN into level indices? ::: the offset.