CS 208 s20 — Virtual Memory: Addressing

1 Video

Here is a video lecture for the material outlined below. It covers CSPP sections 9.1 through 9.4 (p. 802–812). It contains sections on

FDR (0:03)
introduction (1:29)
physical addressing (8:59)
virtual addressing (10:06)
main memory as a cache for disk (12:26)
address translation (20:12)
spreadsheet: page hit (26:52)
spreadsheet: page fault (30:05)
VM: memory management (37:52)
conclusion (44:20)

enables system to use memory efficiently by treating it as a cache for a private address space stored on disk
simplifies memory management via uniform address space for each process
protects the private address space of each process

physical addressing: CPU sends exact physical byte address to memory
- used by early systems, modern microcontrollers, and Cray supercomputers

virtual addressing: use memory management unit (MMU) chip to translate virtual addresses to physical byte addresses using lookup table (page table) stored in memory and managed by operating system

both virtual and physical memory partitioned into blocks (similar to hardware caches) called pages
- memory can be viewed as a cache for pages stored on disk
- virtual pages can be unallocated, cached (resident in memory), or uncached (only on disk)
- a "cache miss" is called a page fault
in this context, cache misses are extremely expensive given the relative speed of memory and disk access (100,000x slower)
- this disparity dominates how memory is organized
- memory as a "cache of pages" will act as a fully associative cache (single set, pages can go anywhere)
- memory will have write-back behavior when it comes to propagating changes to disk (delay and batch writes to disk)
- large page size (4KB to 2MB)
- sophisticated replacement algorithms (beyond the scope of this course)
page table keeps track of mapping virtual pages to physical pages
temporal locaity again important for performance
- when the working set is larger than physical memory, system can grind to a crawl due to continuous swapping of pages (thrashing)

a special register called the page table base register (PTBR) points to the page table
similar to how memory addresses split up into different segments for caching, \(n\)-bit virtual addresses split into a \(p\)-bit virtual page offset (VPO) and an (\(n-p\))-bit virtual page number (VPN)
- VPN selects page table entry (used as an offset from the beginning of the table)
- physical page address generated by concatenating physical page number (PPN) stored in the page table with the VPO
  - virtual and physical pages are the same size, so the VPO is also a valid offset into the physical page
in a page fault (valid bit is zero), MMU triggers an exception and control is transferred to a page fault handler in the operating system
- page identified for eviction, written to disk (paged out) if it has been modified (if it's only been read, handler can just overwrite it)
- new page swapped in, page table updated
- restart interrupted instruction

multiple virtual pages from different processes can be mapped to the same physical page
virtual memory helps memory management by:
- simplifying linking by allowing the same format regardless of actual physical address (e.g., code segment always starts at virtual address 0x400000)
- simplyfying loading—loader allocated virtual pages for code and static data/literals and points page table entry at the relevant sections of the object file
  - data gets paged in as needed
- simplifying sharing—instead of separate copies of printf in each process, distinct virtual pages all map to the same physical page
- simplifying allocation—arrangement of physical pages is invisible to the program, and the operating system can store them anywhere within memory