Vault

ECS154A-L23

3 min read

Cramming before final

Virtual-Memory

Transclude of ECS154A-L23-2025-03-19-21.27.38.excalidraw

Motivation for virtual memory:

  • Trying to solve problem of:
  • Each process assumes a complete virtual machine
  • The OS breaks physical memory into something called frames (page frames)
  • Each process will have a page table, which contains a map of virtual page number to physical frame number
  • [ Virtual Frame Number | Page Number ] => [ Physical Frame Number | Page Number ]
    • VF # will be longer than PF #
  • Inside the OS, it keeps track of which page tables and processes:
    • Page # -> Process/Owner
For Example

Transclude of ECS154A-L23-2025-03-19-21.38.10.excalidraw

13 bit VA, 1k byte mem, 64 byte pages
[ 7 bits | 6 bits]

  • 13 bit VA
    How many frames?
  • 1k / 64 = 16
    How wide is each page table entry?
  • 4
    How many entries in the page table?
  • 2
New Ex

17 bit address, 16k mem, 512 byte pages
VA: [ 8 bits | 9 bits] (out of 17 bit address)
PA: [ 5 bits | 9 bits] (out of 14 bit address (thats log2(16k) mem))

  • How many page table entries?
    • 2
  • How wide is a page table?
    • 5
  • How many frames?
    • 16k / 512 = 2^14 / 2^9 = 2^5 = 32
  • How wide?
    • 5
New Ex

19 bit VA, 32K mem, 1k page
VA: [ 9 | 10]
PA: [ 5 | 10]

MAPPING FROM VA TO PA KNUCKLEHEAD. THESE ARE EASY
Number of entries in PT?

  • 2^9
    How wide?
  • 5
    How many frames?
  • 32 (32k/1k)
    • Can use this to get how wide too, SHOULD BE log2(frames)=wide
New

32 bit VA, 1M mem, 2k byte
VA: [ 21 | 11]
PA: [ 9 | 11 ]
^ get by either doing bit assignment, or: 1M/2k = 2^20 / 2^11 = 2

Mapping from 21 bit space to 9 bit space

Number of entries:

  • 2^21
    Wide?
  • 9 bits

How big is our page table? 2^21 x 2 bytes = 2^22 bytes

  • Our total memory is 2^10, 2^22 MOGS it
    So, we need a base page table, and a secondary page table.
  • But now, we can

Page table walk

I don’t understand it, but instead of the one page table, you introduce secondary, and event tertiary page table

How to implement a cache:

A cache of recent virtual to physical translations

IBM invented this, since they didnt have caches they had lookaside buffers.
They called the translation cache, a TLB or Translation Lookaside Buffer

Two Options:

  • Send VA to cache, and on miss have TLB check the translation
    • Don’t have to go to memory
    • Problem: aliasing, each program has the same VA but not the same PA
  • Send
Physically Addressed Cache

CPU <-> TLB <-> Page Table <-> Mem

Virtually Addressed Cache

CPU <-> Page Table <-> TLB <-> Mem

Graph View

Backlinks