CS 208 s21 — Virtual Memory: Optimization

Table of Contents

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

  1. page hit/miss review (0:34)
  2. permissions (8:57)
  3. TLBs (17:32)
  4. bringing it all together (24:19)
  5. multi-level page tables (34:30)

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=66278060-b89a-4c3c-ae93-ac59010e34a2

2 Review

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

page-hit.png

and a page fault2:

page-fault.png

3 Protection

  • 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

page-table-permissions.png

3.1 Permissions Review

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

4 Improving Performance

4.1 Translation Lookaside Buffer (TLB)

  • 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

tlb-hit.png

tlb-miss.png

4.2 Bringing It All Together

address-translation.png

address-manipulation.png

  • 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

4.3 Multi-Level Page Tables

  • suppose 64-bit virtual addresses (\(n=64\)), 8 KB pages (\(p=13\)), 8 GB physical memory (\(m=33\))
    • how many page table entries? 2n-p = 251
    • 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

multilevel.png

Footnotes:

1

page-hit.png

  1. processor sends virtual address to MMU
  2. 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
  3. PTE sent to MMU
  4. MMU send physical address to cache/memory requesting data
  5. cache/memory sends data to processor
2

page-fault.png

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