University of Washington

Section 9: Virtual Memory (VM)

 Overview and motivation
 Indirection
 VM as a tool for caching
 Memory management/protection and address translation
 Virtual memory example

Virtual Memory as Cache

 University of Washington

VM and the Memory Hierarchy

 Think of virtual memory as an array of N = 2n contiguous
bytes stored on a disk
 Then physical main memory (DRAM) is used as a cache for
the virtual memory array
 The cache blocks are called pages (size is P = 2p bytes)
Virtual memory Physical memory
0
VP 0 Unallocated
0
VP 1 Cached Empty PP 0
Uncached PP 1
Unallocated Empty
Cached
Uncached Empty
Cached PP 2m-p-1
M-1
VP 2n-p-1 Uncached
N-1

Virtual pages (VPs) Physical pages (PPs)

stored on disk cached in DRAM

Virtual Memory as Cache

 University of Washington

Memory Hierarchy: Core 2 Duo Not drawn to scale

L1/L2 cache: 64 B blocks

~4 MB ~4 GB ~500 GB
L1
I-cache
L2
Main
32 KB unified
cache Memory
L1
CPU Reg
D-cache

Throughput: 16 B/cycle 8 B/cycle 2 B/cycle 1 B/30 cycles

Latency: 3 cycles 14 cycles 100 cycles millions Disk
Miss penalty (latency): 33x

Miss penalty (latency): 10,000x

Virtual Memory as Cache

 University of Washington

DRAM Cache Organization

 DRAM cache organization driven by the enormous miss
penalty
 DRAM is about 10x slower than SRAM
 Disk is about 10,000x slower than DRAM
 (for first byte; faster for next byte)

 Consequences?
 Block size?
 Associativity?
 Write-through or write-back?

Virtual Memory as Cache

 University of Washington

DRAM Cache Organization

 DRAM cache organization driven by the enormous miss
penalty
 DRAM is about 10x slower than SRAM
 Disk is about 10,000x slower than DRAM
 (for first byte; faster for next byte)

 Consequences
 Large page (block) size: typically 4-8 KB, sometimes 4 MB
 Fully associative
Any VP can be placed in any PP
 Requires a “large” mapping function – different from CPU caches
 Highly sophisticated, expensive replacement algorithms
 Too complicated and open-ended to be implemented in hardware
 Write-back rather than write-through
Virtual Memory as Cache
 University of Washington

Indexing into the “DRAM Cache”

Main memory
0:
CPU Chip 1:
2:
Virtual address Physical address
(VA) (PA) 3:
CPU MMU 4:
5:
6:
7:
8:

...
M-1:

Data word

How do we perform the VA -> PA translation?

Virtual Memory as Cache

 University of Washington

Address Translation: Page Tables

 A page table (PT) is an array of page table entries (PTEs) that
maps virtual pages to physical pages.
Physical memory
Physical page (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
How many page tables are in the system? VP 6
One per process
Virtual Memory as Cache
VP 7
 University of Washington

Address Translation With a Page Table

Virtual address (VA)
Page table
base register Virtual page number (VPN) Virtual page offset (VPO)
(PTBR)

Page table address Page table

for process Valid Physical page number (PPN)

Valid bit = 0:
page not in memory
(page fault)

In most cases, the hardware

(the MMU) can perform this Physical page number (PPN) Physical page offset (PPO)
translation on its own,
without software assistance Physical address (PA)

Virtual Memory as Cache

 University of Washington

Page Hit
 Page hit: reference to VM byte that is in physical memory

Physical memory
Physical page (DRAM)
Virtual address
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Virtual Memory as Cache
 University of Washington

Page Fault
 Page fault: reference to VM byte that is NOT in physical
memory
Physical memory
Physical page (DRAM)
Virtual address
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
What happens when a page
VP 6
fault occurs?
VP 7
Virtual Memory as Cache
 University of Washington

Fault Example: Page Fault

int a[1000];
 User writes to memory location main ()
{
 That portion (page) of user’s memory a[500] = 13;
is currently on disk }

80483b7: c7 05 10 9d 04 08 0d movl $0xd,0x8049d10

User Process OS

exception: page fault

movl
Create page and
returns load into memory

 Page handler must load page into physical memory

 Returns to faulting instruction: mov is executed again!
 Successful on second try
Virtual Memory as Cache
 University of Washington

Handling Page Fault

 Page miss causes page fault (an exception)

Physical memory
Physical page (DRAM)
Virtual address number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Virtual Memory as Cache
 University of Washington

Handling Page Fault

 Page miss causes page fault (an exception)
 Page fault handler selects a victim to be evicted (here VP 4)

Physical memory
Physical page (DRAM)
Virtual address number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Virtual Memory as Cache
 University of Washington

Handling Page Fault

 Page miss causes page fault (an exception)
 Page fault handler selects a victim to be evicted (here VP 4)

Physical memory
Physical page (DRAM)
Virtual address number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 3 PP 3
1
1
0
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Virtual Memory as Cache
 University of Washington

Handling Page Fault

 Page miss causes page fault (an exception)
 Page fault handler selects a victim to be evicted (here VP 4)
 Offending instruction is restarted: page hit!
Physical memory
Physical page (DRAM)
Virtual address number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 3 PP 3
1
1
0
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Virtual Memory as Cache
 University of Washington

Why does it work? Locality

 Virtual memory works well because of locality
 Same reason that L1 / L2 / L3 caches work

 The set of virtual pages that a program is “actively” accessing

at any point in time is called its working set
 Programs with better temporal locality will have smaller working sets

 If (working set size < main memory size):

 Good performance for one process after compulsory misses

 If (SUM(working set sizes) > main memory size):

 Thrashing: Performance meltdown where pages are swapped (copied)
in and out continuously

Virtual Memory as Cache