CS 208 s21 — Virtual Memory: Addressing

Table of Contents

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

  1. FDR (0:00)
  2. introduction (1:26)
  3. physical addressing (8:19)
  4. virtual addressing (9:26)
  5. main memory as a cache for disk (11:05)
  6. address translation (17:59)
  7. spreadsheet: page hit (24:40)
  8. spreadsheet: page fault (27:53)
  9. VM: memory management (35:14)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=32e7bf0d-5278-4dd0-a68a-ac59010e1d56

2 Virtual Memory Provides Important Capabilities

  • 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

3 Why Study Virtual Memory?

  • central to the design of many system components across many levels
  • provides the programmer with powerful tools (e.g., memory mapping)
  • misuse of memory can cause strange and insidious bugs

4 Memory Addressing

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

addressing-physical.png

  • 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

addressing-virtual.png

5 Main Memory as a Cache

  • 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)

6 Address Translation

addrtrans.png

  • 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

6.1 Spreadsheet Diagram

  • link
  • page hit: virtual memory reference is in physical memory
  • page miss: virtual memory reference is NOT in physical memory
    • transfer control to page fault handler (exception)
    • handler selects page to be evicted
      • when do we need to write contents back to disk?
    • write new page to physical memory
    • update page table (validate new page, invalidate evicted page)
    • handler restarts faulting instruction

7 Management

  • 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