CS 208 s20 — Virtual Memory: Optimization

1 Video

Here is a video lecture for the material outlined below. It covers CSPP section 9.6 (p. 813–824). It contains sections on

introduction (0:03)
page hit/miss review (0:58)
permissions (9:30)
TLBs (18:12)
bringing it all together (25:15)
multi-level page tables (35:34)
virtual memory worksheet overview (45:40)
conclusion (49:46)

Using this diagram, fill in the steps for a page hit¹:

and a page fault²:

want to enforce things like read-only code and kernel-only memory
page table permission bits natural way to do this
- extend page table to include read/write/execute bits
- MMU checks them on every memory access
- if violated, raises exception and kernel sends SIGSEGV (segmentation fault) signal to process

Section	Read	Write	Execute
Stack	1	1	0
Heap	1	1	0
Static Data	1	1	0
Literals	1	0	0
Instructions	1	0	1

MMU has to access memory twice: once to get the PTE, and again for the actual memory request
- we can speed up address translation via a small cache of page table entries (called a translation lookaside buffer (TLB)
  - VPN split into tag and index for this cache
  - modern Intel processors have 128 or 256 entries in TLB

Basic Parameters
- \(N=2^n\) — Number of addresses in virtual address space
- \(M=2^m\) — Number of addresses in physical address space
- \(P=2^p\) — Page size (bytes)
Components of the virtual address (VA)
- VPO — Virtual page offset
- VPN — Virtual page number
- TLBI — TLB index
- TLBT — TLB tag
Components of the physical address (PA)
- PPO — Physical page offset (same as VPO)
- PPN — Physical page number

suppose 64-bit virtual addresses (\(n=64\)), 8 KB pages (\(p=13\)), 8 GB physical memory (\(m=33\))
- how many page table entries? 2^n-p = 2⁵¹
- how many bits per PTE? PPN width + management bits = \(m - p + 5\) (valid, dirty, read, write, execute) = 25 bits or about 3 bytes
- we can't actually have 4 million GB worth of page table entries for each process
we can use multi-level page tables to reduce memory overhead
- VPN split into \(k\) segments, one for each level of page table
- instead of a million page table entries in memory, most unused, we have have a level 1 table with 1000 entries, and then only have a second level of 1000 for allocated level 1 entries

Below is background for the virtual memory worksheet assigned as this topic's homework.

addressing:
- 14-bit virtual addresses
- 12-bit physical addresses
- 64-byte pages

page table
- only showing first 16 entries (out of how many? one for every virtual page = \(2^{n-p} = 2^8 = 256\))
- using 2 hex digits for PPN even though it's only 6 bits
- other management bits not shown

translation lookaside buffer
- 16 entries
- 4-way associative
- VPN split into TLB tag (TLBT) and TLB index (TLBI)

processor sends virtual address to MMU
MMU requests page table entry (PTE) from page table in cache/memory
- using page table base register (PTBR) to find beginning of page table for current process
PTE sent to MMU
MMU send physical address to cache/memory requesting data
cache/memory sends data to processor

processor sends virtual address to MMU
MMU requests page table entry (PTE) from page table in cache/memory
PTE sent to MMU
valid bit is zero, MMU triggers page fault exception
page fault handler (an operating system function) identifies page to evict
- if modified (dirty) write out (page out) to disk
handler loads (pages in) new page, updates PTE in memory
handler returns to original process, restarting faulting instruction