CS 208 s20 — 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. introduction (0:03)
  2. page hit/miss review (0:58)
  3. permissions (9:30)
  4. TLBs (18:12)
  5. bringing it all together (25:15)
  6. multi-level page tables (35:34)
  7. virtual memory worksheet overview (45:40)
  8. conclusion (49:46)

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=9f4528f8-dbbd-4145-8954-abcf01089a4b

2 Review

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


and a page fault2:


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


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



4.2 Bringing It All Together



  • 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


5 Extended Example

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)


  • cache
    • direct-mapped with 4-byte blocks
    • total capacity of 64 bytes (16 blocks)
    • physically addressed
    • physical address split into cache tag (CT), cache index (CI) and cache offset (CO)
    • just a coincidence that PPN is the same width as the cache tag


6 Homework

  1. Virtual memory worksheet (solutions below3)
  2. The week 8 quiz is due 9pm tonight, June 3 (it's very short!)
  3. Make a lab 5 check-in forum post by 9pm tonight, June 3




  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


  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
Request VPN TLBT TLBI TLB hit? page fault? PPN CT CI CO cache hit? data (byte)
0x03d4 0x0f 0x03 3 yes no 0x0d 0x0d 5 0 yes 0x36
0x038f 0x0e 0x03 2 no yes - - - - - -
0x0020 0x00 0x00 0 no no 0x28 0x28 8 0 no -
0x036b 0x0d 0x03 1 yes no 0x2d 0x2d a 3 yes 0x3b