CS61C: Great Ideas in Computer Architecture (aka Machine Structures)

Lecture 24: Virtual Memory

Instructor: Justin Yokota�Slide Credit: Lisa Yan

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

2

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

3

CS 61C

Summer 2026

How much memory is my computer using?

• My computer reports that I'm using 13.8 GB of Random Access Memory (out of 15.7 GB total)
• Let's verify this by calculating from some other data.
• Might be a bit off because of some factor we don't know yet, but it shouldn't be too far off…
• Currently my computer is using 422 processes, each of which needs an address space
• My computer is a 64-bit computer, so memory addresses are 48 bits long
• Total = 422 * 2⁴⁸ bytes = 100 petabytes (about 8 million times off)
• Wait…

CS 61C

Summer 2026

Virtual Memory

• If we gave each process a full 2⁴⁸ bytes of RAM, we won't be able to fit any processes in our RAM.
• Can we do better?
• Most processes don't use all their address space.
• They mostly use one block of memory in the code segment, another block in the stack, and maybe a few blocks in the heap/data segments.
• Solution: Chop up main memory into "pages" of a few KiB each. Only store pages that a program actually tries to access.
• Ex. A program may be using 1 page for its code, 1 page for its stack, 4 pages for its heap, etc.
• When we run a program, it needs to believe that it has access to its full 2³² bit address space (on a 32-bit machine). This memory doesn't actually exist; it's "virtual" memory.
• When a program actually needs a page of memory, we'll allocate a page of physical memory.

CS 61C

Summer 2026

Virtual Memory

• Virtual memory is the next level in the memory hierarchy:
• Give each process the illusion of a full memory address space that it has completely for itself.
• Under the hood: working set of pages reside in main memory;�other pages are on disk.
• Benefits:
• Demand paging provides the ability to run programs larger than the primary memory (DRAM).
• OS can share memory and protect programs from each other.
• Hides differences between machine configurations.
• (Historically, virtual memory predates caches.)
• Logic here wants more flexibility than hardware can permit. So we'll incorporate it in the OS.

CS 61C

Summer 2026

Virtual Memory Saves Unused Pages

CS 61C

Summer 2026

Virtual Memory Protects Programs from Each Other

CS 61C

Summer 2026

The Illusion of Virtual Address Space

Processes use virtual addresses.�Many processes, all using same (conflicting) addresses

Different processes run simultaneously

0xF…F

0x0…0

0xF…F

0x0…0

0xF…F

0x0…0

CS 61C

Summer 2026

The Translation to Virtual Address Space

Different processes run simultaneously

0x07FF FFFF

0x0000 0000

Translator/Memory Manager

Memory uses physical addresses.

CS 61C

Summer 2026

Address Sizes: The Hive Machines

CS 61C

Summer 2026

Virtual Addresses vs. Physical Addresses

• Address Space: set of addresses for all available memory locations.
• Now, two kinds of memory addresses!
• Virtual Address Space
• Set of addresses that the user program knows about
• Physical Address Space
• Set of addresses that map to actual physical locations in memory
• Hidden from user applications
• For each process, the memory manager maps (translates) between these two address spaces.

CS 61C

Summer 2026

How is the Memory Hierarchy Managed?

• registers ↔ memory
• By compiler (or assembly level programmer)
• cache ↔ main memory
• By the cache controller hardware
• main memory ↔ disks (secondary storage)
• By the operating system (virtual memory)
• Virtual to physical address mapping assisted by the hardware (‘translation lookaside buffer’ or TLB)
• By the programmer (files)

CS 61C

Summer 2026

For Today: Assume Caches Don't Exist

• Virtual Memory is much easier to understand if we assume no caches.
• We’ll reintroduce caches along with Translation Lookaside Buffers (TLBs) later.

Processor chip

DRAM chip –e.g. �DDR3/4/5�HBM/HBM2/3

SSD, HDD�Drives

(assume this doesn’t exist)

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

15

CS 61C

Summer 2026

Paged Memory

• Physical memory (DRAM) is broken into pages.
• A disk access loads an entire page into memory.
• Should be large enough to amortize high access time.
• Typical page size: 4 KiB+ (on modern OSes)
• Need 12 bits of page offset to address all 4 KiB bytes.

0xF…F

0x0…0

text

stack

heap

data

Page Number 0

Page Number 1

(paged) virtual address space

CS 61C

Summer 2026

Paged Memory

• Physical memory (DRAM) is broken into pages.
• A disk access loads an entire page into memory.
• Should be large enough to amortize high access time.
• Typical page size: 4 KiB+ (on modern OSes)
• Need 12 bits of page offset to address all 4 KiB bytes.

• Memory translation maps a Virtual Page Number (VPN) to a Physical Page Number (PPN).

Virtual and physical pages are the same size. Same # bits to address offset within a page!

CS 61C

Summer 2026

Address Translation

​

• A page table translates virtual addresses to physical addresses for a given process. Each entry in the table:
• Corresponds to a virtual page number.
• If page is in memory, entry has corresponding physical page number.
• Else, entry should tell OS to trigger page fault to load page from disk.

CS 61C

Summer 2026

Analogy: Return of the Librarian

• Earlier, we imagined that memory was a library. For a program to access a memory address:
• Call the librarian for the data
• The librarian goes to that data location and responds with the data there.
• With virtual memory:
• The librarian doesn't actually have enough books to store everyone's data.
• So when you first start using some chunk of memory, the librarian takes a spare book and assigns it to you.
• The librarian is responsible for translating from your memory address to the right book
• To keep track of this, the librarian reserves one of the books for themselves and writes down each book that's being used, and who it belongs to.

CS 61C

Summer 2026

Address Translation Example 1

​

Assume each page is 4 KiB and we have 4 physical pages

Step 1: Program tries load data at 0xFFFF F004.

CS 61C

Summer 2026

Address Translation Example 1

​

Step 2: OS translates VA to the physical address (PA) in memory.

• Split Virtual Address into virtual page number and offset (0xFFFFF 004)
• Extract virtual page number (VPN) from VA (0xFFFFF)
• Look up VPN in page table

CS 61C

Summer 2026

Address Translation Example 1

​

Step 3: Page table lists VPN as corresponding to a physical page. Page hit.

• Construct PA: physical page number + offset (from virtual address): 0x1004

CS 61C

Summer 2026

Address Translation Example 1

​

Step 4: Read data at the corresponding memory location, and return it to the program

• Read data at 0x1004 in physical memory
• Send that data back to the program

0x43

CS 61C

Summer 2026

Address Translation Example 2

​

Assume each page is 4 KiB and we have 4 physical pages

Step 1: Program tries to malloc new location. C library translates this to an sbrk, which requests an extra page of memory from the OS

CS 61C

Summer 2026

Address Translation Example 2

​

Step 2: OS finds empty physical page

• If no page is available, copy (evict) a page to disk and reuse that page
• OS can choose to decline the new memory allocation, in which case malloc returns NULL

CS 61C

Summer 2026

Address Translation Example 2

​

Step 3: OS updates Page Table, and returns the new location

CS 61C

Summer 2026

Address Translation Example 3

​

Let's try accessing the address that was just sent to disk

Step 1: Program tries load data at 0xFFFF F004.

CS 61C

Summer 2026

Address Translation Example 3

​

Step 2: OS translates VA to the physical address (PA) in memory.

• Split Virtual Address into virtual page number and offset (0xFFFFF 004)
• Extract virtual page number (VPN) from VA (0xFFFFF)
• Look up VPN in page table

CS 61C

Summer 2026

Address Translation Example 3

​

Step 3: Page table doesn't have the PPN listed. Page Fault

• Another part of the OS takes over here to decide if the data is on disk, or if the access is illegal
• In this case, the data is on disk, so the OS loads the data from disk back to a physical page

CS 61C

Summer 2026

Address Translation Example 3

​

Step 4: Read data at the corresponding memory location, and return it to the program

• Read data at 0x2004 in physical memory
• Send that data back to the program

0x43

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

31

CS 61C

Summer 2026

Translation Example

What Physical Address does this Virtual Address translate to?

0x00003450

A. 0x00003450

B. 0x0000250

C. 0x00503450

D. 0x0F543450

E. 0x0F54450

F. Disk/Other

CS 61C

Summer 2026

Translation Example: Solution

What Physical Address does this Virtual Address translate to?

0x00003450

A. 0x00003450

B. 0x0000250

C. 0x00503450

D. 0x0F543450

E. 0x0F54450

F. Disk/Other

CS 61C

Summer 2026

Translation Example: Solution

What Physical Address does this Virtual Address translate to?

0x00003450

A. 0x00003450

B. 0x0000250

C. 0x00503450

D. 0x0F543450

E. 0x0F54450

F. Disk/Other

CS 61C

Summer 2026

Translation Example: Solution

What Physical Address does this Virtual Address translate to?

0x00003450

A. 0x00003450

B. 0x0000250

C. 0x00503450

D. 0x0F543450

E. 0x0F54450

F. Disk/Other

CS 61C

Summer 2026

Determining VPN/PPN size

• Assume a 32-bit machine with 8GiB of RAM and 16KiB pages.
• How many bits would there be for each of the following?

​

CS 61C

Summer 2026

Determining VPN/PPN size

• Assume a 32-bit machine with 8GiB of RAM and 16KiB pages.
• 16 KiB = 2¹⁴ -> 14 bits offset

​

CS 61C

Summer 2026

Determining VPN/PPN size

• Assume a 32-bit machine with 8GiB of RAM and 16KiB pages.
• 32-bit machine = 32-bit virtual addresses -> 32-14 = 18 bit VPN.

​

CS 61C

Summer 2026

Determining VPN/PPN size

• Assume a 32-bit machine with 8GiB of RAM and 16KiB pages.
• 2³³ bytes of RAM = 2^33-14 pages = 2¹⁹ pages -> 19 bit PPN

​

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

40

CS 61C

Summer 2026

What does a Page Table look like?

• One page table per process.
• One entry per virtual page number.
• Entry has physical page number (if in memory) as well as status bits (more later).
• A page table is NOT a cache
• A page table is a lookup table!
• It does NOT have data.
• All VPNs have an entry in the page table.
• Index 0 -> stores which physical page corresponds to VPN 0

Page table

PPN

status bits

CS 61C

Summer 2026

What does a Page Table Entry look like?

• Each page table entry stores:
• The physical page number associated with the given VPN
• Status bits/metadata
• For this class, we'll talk about the following:
• Valid Bit
• Dirty bit
• Write protection bit

Page table

PPN

status bits

CS 61C

Summer 2026

Valid Bit

• Page table entries track a valid bit to indicate if the page is in memory (DRAM) or only on disk (similar to valid bit in a cache).
• On each memory access, first check if page table entry is “valid.”
• Valid/on → In main memory
• Read/write data as directed by process.
• Not Valid/off → On disk
• Trigger page fault exception
• OS intervenes to allocate the page into DRAM
• If out of memory, first select a page to replace in DRAM
• Store outgoing page to disk.
• Read requested page from disk into DRAM.
• Finally, read/write data as directed by process.

CS 61C

Summer 2026

Dirty Bit

• Main memory acts like a “cache” for secondary memory/disk.
• Should writes always go directly to disk (write-through), or
• Should writes only go to disk when page is evicted (write-back)?
• All virtual memory systems systems use write-back.
• Disk accesses take way too long!
• Recall that write-back policy requires a dirty bit to keep track of pages that have an unsynced write.
• When a page gets replaced:
• Dirty bit on: Write outgoing page back to disk.
• Dirty bit off: No disk write.

CS 61C

Summer 2026

Write Protection Bit

• Page table write protection bit: on = page is “protected.”
• Writing to a protected page triggers an OS exception.
• Useful for pages that should never be modified
• Ex. Program code, system data, etc.
• The OS acts to protect programs:
• Isolate memory between processes.
• Each process gets dedicated “private” memory.
• Errors in one program won’t corrupt memory of other programs.
• Prevent user programs from messing with OS’s memory.
• Allow memory sharing where safe.

CS 61C

Summer 2026

Write Protection bit use case: Safe Memory Sharing

​

• Each process gets its own page table
• Normally, different processes have different data
• What if two processes want to share the same data?
• Have their page table map two virtual pages to the same physical page!

• Common use case: two processes accessing the same dynamically-linked library (like stdlib.h)
• Don't want to let programs modify stdlib, so turn on write protection for those pages.

CS 61C

Summer 2026

How big is a page table?

We have a system with:

• 32-bit virtual addresses
• 4 KiB pages
• 32-bit page table entries

How much memory does our page table take? How many pages?

CS 61C

Summer 2026

How big is a page table?

We have a system with:

• 32-bit virtual addresses
• 4 KiB pages
• 32-bit page table entries

How much memory does our page table take?

• 2¹² bytes per page
• 32-bit virtual address -> 20 bit VPN, 12 bit page offset
• 2²⁰ PTEs = 2²² bytes = 4 MiB

How many pages?

• 4 MiB / 4 KiB = 1024 pages

CS 61C

Summer 2026

Page Tables are Stored in Memory

​

• Each page table is ~4 MiB
• Not bad compared to main memory (often on the order of GiBs), but too big for a cache.
• Can be improved with two layer page table (see skipped slides)
• Solution: store page tables in main memory.
• Caveat: Two (slow) memory accesses per lw/sw on cache miss!
• Read page table (stored in main memory) to translate to physical address
• Read physical page, also in main memory
• To minimize performance penalty:
• Transfer cache lines (not words) between DRAM and processor cache
• Use a cache for frequently used page table entries … (TLB)

CS 61C

Summer 2026

4 MiB is still kind of big

​

• Our page table is currently 4 MiB
• Not bad compared to main memory (often on the order of GiBs), but it's still big
• We use a page table because most memory in a program is empty
• Interesting note: Most VPNs in a page table are empty as well…
• Solution: Make a page table of page tables!
• Called a multi-level page table

CS 61C

Summer 2026

Multi-level page tables

​

• Our page table starts at an L1 page table
• Each entry in the L1 page table corresponds to a portion of the original (big) page table
• Corresponds to the top bits of the VPN
• If any entry in that part of the page table is valid, allocate an L2 page table, and note its location (physical page) in the L1 page table
• The L2 page table acts as a regular page table and stores PPNs of the corresponding virtual page
• Slot in L2 page table corresponds to bottom bits of the VPN
• For optimal size, VPN should be split evenly between L1 and L2 page table

CS 61C

Summer 2026

Multi-level page tables

​

L1 Page table

L2

status bits

L2 Page table

PPN

status bits

L2 Page table

PPN

status bits

L2 Page table

PPN

status bits

CS 61C

Summer 2026

How big is each L1/L2 page table?

We have a system with:

• 32-bit virtual addresses
• 4 KiB pages
• 32-bit page table entries
• VPN split in half between L1 and L2 tables

How much memory does each L1/L2 page table take? How many pages?

CS 61C

Summer 2026

How big is a page table?

We have a system with:

• 32-bit virtual addresses
• 4 KiB pages
• 32-bit page table entries
• VPN split in half between L1 and L2 tables

How much memory does our page table take?

• 2¹² bytes per page
• 32-bit virtual address -> 20 bit VPN, 12 bit page offset -> 10 VPN bits per table
• 2¹⁰ PTEs = 2¹² bytes = 4 KiB = 1 page

CS 61C

Summer 2026

The "Magic" Page Table

​

• If we use a 2-layer page table with a 10-10-12 split (L1-L2-Page offset), and PTEs are 32 bits long, then every page table takes up exactly one page of memory
• For 32-bit systems, this is really efficient
• So page sizes of 4 KiB became fairly common
• Previous semesters tended to use this particular example for multi-level page tables (which were in scope at that time)
• Currently out of scope, but interesting to know.

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

56

CS 61C

Summer 2026

Address Translation: Avoid Page Table Walks

​

• Good Virtual Memory design should be�fast (~1 clock cycle) and space efficient.
• However, every instruction/data access needs address translation.
• A page table walk is the process of accessing the page table in memory.
• If page tables are in memory, then each memory access takes several memory accesses to complete (very slow)
• Solution: Cache some address translations in the Translation Lookaside Buffer (TLB).

Physical address

Virtual address

​

possible page table walk?

address translation

CS 61C

Summer 2026

The TLB Caches Address Lookups

​

• A page table stores VPN-PPN mappings
• The translation lookaside buffer (TLB) is a cache of VPN-PPN mappings.
• The TLB is much closer to CPU and caches.
• Predates data caches (so uses an older name)
• Unlike a data cache, does NOT store the data in the page
• Just speeds up the process of looking for the PPN in the page table, still needs to access the physical page to get actual data

The TLB

Process 1�Page Table

​

CS 61C

Summer 2026

TLB Details

​

• Technical details:
• Doesn't store much data, so relatively small
• Fully associative (usually)
• Replacement policy: FIFO (stores the most recently accessed pages)
• Can be multi-level, but we'll restrict to single-level TLB for this class
• TLB is on the core, but needs care when the core switches active process
• Each process has different page table, so different VPN-PPN mapping
• Easiest: OS flushes all/part of the TLB by invalidating its entries.
• Harder: track which process corresponds to which entries

The TLB

Process 1�Page Table

​

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

60

CS 61C

Summer 2026

Address Translation Example

​

• Different cases of address translation impact the end-to-end latency of a single memory access.
• Memory access = address translation + data access

firefox

intellij

CPU

orange

Disk

TLB

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

CS 61C

Summer 2026

[Case 1, Best] TLB Hit

Address Translation: Instant (~1 clock cycle)

lw s5 12(a2)

srli t2 t0 3

…

firefox

addi s2 x0 3

jal label

…

intellij

Disk

"I want to read 0x00004ABC."

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

TLB

CPU

CS 61C

Summer 2026

[Case 2, Worse] TLB Miss + Page Table Walk

Page table walk (~100 cycles): Go to main memory, read page table.

lw s5 12(a2)

srli t2 t0 3

…

firefox

addi s2 x0 3

jal label

…

intellij

Disk

"I want to read 0x00004ABC."

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

TLB

CPU

VPN 4 NOT in TLB.

❌

CS 61C

Summer 2026

[Case 2, Worse] TLB Miss + Page Table Walk, cont.

Page table walk (~100 cycles): Go to main memory, read page table.�Update TLB so we have this VPN/PPN mapping handy for next time.

lw s5 12(a2)

srli t2 t0 3

…

firefox

addi s2 x0 3

jal label

…

intellij

Disk

"I want to read 0x00004ABC."

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

TLB

CPU

VPN 4 NOT in TLB.

❌

Update TLB.

CS 61C

Summer 2026

[Case 3, Worst] Page Fault

Page fault. Go to disk to load page (~1000s cycles)

lw s5 12(a2)

srli t2 t0 3

…

firefox

addi s2 x0 3

jal label

…

intellij

Disk

"I want to read 0x00004ABC."

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

TLB

CPU

VPN 4 NOT in TLB.

❌

CS 61C

Summer 2026

[Case 3, Worst] Page Fault

Update page table with PPN of the newly-loaded page.

Update TLB so we have this VPN/PPN mapping handy for next time.

lw s5 12(a2)

srli t2 t0 3

…

firefox

addi s2 x0 3

jal label

…

intellij

Disk

"I want to read 0x00004ABC."

Page Tables

Each entry 4 bytes.

Main Memory

Each page 0x1000 bytes.

TLB

CPU

VPN 4 NOT in TLB.

❌

Update TLB

Update page table.

CS 61C

Summer 2026

Summary: TLB Hits, Page Table Walk, Page Fault…

• Three cases for an address translation:

CS 61C

Summer 2026

Agenda

• Virtual Memory and Virtual Addresses
• Paged Memory and Address Translations
• Practice
• Page Table Details
• Translation Lookaside Buffer (TLB)
• Address Translation: Best/Worst Case
• Caches vs Virtual Memory

68

CS 61C

Summer 2026

The Entire Modern Memory Hierarchy

Processor chip

DRAM chip –e.g. �DDR3/4/5�HBM/HBM2/3

SSD, HDD�Drives

(now assume caches exist)

CS 61C

Summer 2026

Another View of Memory Hierarchy

​

CS 61C

Summer 2026

Memory Units

​

• Lines, pages, bytes, words are all units in the memory hierarchy.
• Cache lines ~ 64 B or 128 B
• Pages: ~4 KiB

CS 61C

Summer 2026

Caches have copies of data

​

• “Cache” Paradigm: Data at each level is a quick-access copy of data at a lower level in the memory hierarchy.
• Similarly, data pages in main memory are “cached” versions of pages on disk.
• ​

🙂

🙂

🙂

🙂

CS 61C

Summer 2026

Page Tables don't copy data

​

• A Page Table translates addresses.
• Page tables facilitate demand paging.
• Page Table keeps track of page status/location only (not data).

CS 61C

Summer 2026

Caches vs. Virtual Memory

CS 61C

Summer 2026

Putting it All Together: PIPT

​

• Can a cache hold the requested data if the corresponding page is not in main memory?
• On a memory reference, what should we access first?
• When should we translate virtual addresses?

VA

data

Load byte @ 0xFFFF F004 �to register t0

​

​

​

​

CPU

CS 61C

Summer 2026

Putting it All Together: PIPT

​

• Other more complicated designs exist, but in this class we assume physically indexed, physically tagged (PIPT) caches.
• 1. First translate virtual address to physical address.
• 2. Then use the physical address to access the data cache.

Load byte @ 0xFFFF F004 �to register t0

​

​

​

​

CPU

CS 61C

Summer 2026