Virtual Memory

Some slides based on those provided by the authors of the text

Topics
• Motivations for VM
• Address translation
• Accelerating translation with TLBs
 Motivations for Virtual Memory
• Use Physical DRAM as a Cache for the Disk
• Address space of a process can exceed physical memory size
• Sum of address spaces of multiple processes can exceed physical
memory
• Simplify Memory Management
• Multiple processes resident in main memory.
– Each process with its own address space
• Only “active” code and data is actually in memory
– Allocate more memory to process as needed.
Provide Protection
• One process can’t interfere with another.
– because they operate in different address spaces.
• User process cannot access privileged information
– different sections of address spaces have different permissions.

CompOrg Fall - Virtual Memory 2

 Motivation #1: DRAM a “Cache” for
Disk
Full address space is quite large:
• 32-bit addresses: ~4,000,000,000 (4 billion) bytes
• 64-bit addresses: ~16,000,000,000,000,000,000 (16 quintillion) bytes
Disk storage is ~156X cheaper than DRAM storage
• 8 GB of DRAM: ~ $10,000
• 8 GB of disk: ~ $64
To access large amounts of data in a cost-effective
manner, the bulk of the data must be stored on disk
8 GB: ~$64
256 MB: ~$320
4 MB: ~$400

SRAM DRAM Disk

CompOrg Fall - Virtual Memory 3

 Levels in Memory
Hierarchy
cache virtual memory

C
CPU 8B a 32 B 4 KB
CPU Memory
Memory disk
disk
c
regs
regs h
e

Register Cache Memory Disk Memory

size: 32 B 32 KB-4MB 128 MB 30 GB
speed: 3 ns 6 ns 60 ns 8 ms
$/Mbyte: $100/MB $1.25/MB $0.008/MB
line size: 8B 32 B 4 KB

larger, slower, cheaper

CompOrg Fall - Virtual Memory 4

 DRAM vs. SRAM as a
DRAM vs. disk is more“Cache”
extreme than SRAM vs. DRAM
• Access latencies:
– DRAM ~10X slower than SRAM
– Disk ~100,000X slower than DRAM
• Importance of exploiting spatial locality:
– First byte is ~100,000X slower than successive bytes on disk
» vs. ~4X improvement for page-mode vs. regular accesses to DRAM
• Bottom line:
– Design decisions made for DRAM caches driven by enormous cost of
misses

SRAM DRAM Disk

CompOrg Fall - Virtual Memory 5

Impact of These Properties on Design
If DRAM was to be organized similar to an SRAM cache, how
would we set the following design parameters?
• Line size?
– Large, since disk better at transferring large blocks
• Associativity?
– High, to minimize miss rate
• Write through or write back?
– Write back, since can’t afford to perform small writes to disk
What would the impact of these choices be on:
• miss rate
– Extremely low. << 1%
• hit time
– Must match cache/DRAM performance
• miss latency (penalty)
– Very high. ~20ms
• tag storage overhead
– Low, relative to block size

CompOrg Fall - Virtual Memory 6

 Locating an Object in a “Cache”
SRAM Cache
• Tag stored with cache line
• Maps from cache block to memory blocks
– From cached to uncached form
• No tag for block not in cache
• Hardware retrieves information
– can quickly match against multiple tags “Cache”
Tag Data

Object Name 0: D 243

X = X? 1: X 17
• •
• •
• •
N-1: J 105

CompOrg Fall - Virtual Memory 7

Locating an Object in a “Cache” (cont.)
DRAM Cache
• Each allocated page of virtual memory has entry in page table
• Mapping from virtual pages to physical pages
– From uncached form to cached form
• Page table entry even if page not in memory
– Specifies disk address
• OS retrieves information

Page Table “Cache”

Location Data
Object Name D: 0 0: 243
X J: On Disk 1: 17
• •
• •
• •
X: 1 N-1: 105
CompOrg Fall - Virtual Memory 8
 A System with Physical Memory Only
Examples:
• most Cray machines, early PCs, nearly all embedded systems, etc.

Memory

0:
Physical 1:
Addresses

CPU

N-1:

Addresses generated by the CPU point directly to bytes in physical

memory CompOrg Fall - Virtual Memory 9
 A System with Virtual Memory
Examples:
• workstations, servers, modern PCs, etc. Memory

0:
Page Table 1:
Virtual Physical
Addresses 0: Addresses
1:

CPU

P-1:
N-1:

Disk

Address Translation: Hardware converts virtual addresses to

physical addresses via an OS-managed lookup table (page table)10
CompOrg Fall - Virtual Memory
Page Faults (Similar to “Cache Misses”)
What if an object is on disk rather than in memory?
• Page table entry indicates virtual address not in memory
• OS exception handler invoked to move data from disk into memory
– current process suspends, others can resume
– OS has full control over placement, etc.

Before fault After fault

Memory
Memory
Page Table
Virtual Page Table
Physical
Addresses Addresses Virtual Physical
Addresses Addresses
CPU
CPU

Disk
Disk
CompOrg Fall - Virtual Memory 11
 Servicing a Page Fault
Processor Signals (1) Initiate Block Read
Controller Processor
Processor
• Read block of length P Reg
(3) Read
starting at disk address Done
X and store starting at
memory address Y Cache
Cache
Read Occurs
• Direct Memory Access
Memory-I/O
Memory-I/Obus
bus
(DMA)
• Under control of I/O (2) DMA Transfer
controller I/O
I/O
Memory controller
controller
I / O Controller Memory
Signals Completion
• Interrupt the processor disk
Disk disk
Disk
• OS resumes suspended
process
CompOrg Fall - Virtual Memory 12
 Motivation #2: Memory
Multiple processesManagement
can reside in physical memory.
How do we resolve address conflicts?
• what if two processes access something at the same address?

memory invisible to
kernel virtual memory user code
%esp stack

Memory mapped region

Linux/x86 forshared libraries

process
the “brk” ptr
memory runtime heap (via malloc)

image uninitialized data (.bss)

initialized data (.data)
program text (.text)
forbidden
0
CompOrg Fall - Virtual Memory 13
Solution: Separate Virtual Addr. Spaces
• Virtual and physical address spaces divided into equal-sized blocks
– blocks are called “pages” (both virtual and physical)
• Each process has its own virtual address space
– operating system controls how virtual pages as assigned to physical
memory
– every program can start at the same address (virtual address)!

0
Virtual 0 Address Translation Physical
Address VP 1 PP 2 Address
VP 2 Space
Space for ... (DRAM)
Process 1:
N-1
(e.g., read/only
PP 7
library code)
Virtual 0
VP 1
Address PP 10
VP 2
Space for ...
Process 2: M-1
N-1 14
CompOrg Fall - Virtual Memory
 Contrast: Macintosh Memory Model
MAC OS 1–9
• Does not use traditional virtual memory
Shared Address Space
P1 Pointer Table

Process P1 A

B
“Handles” P2 Pointer Table
C
Process P2
D

All program objects accessed through “handles”

• Indirect reference through pointer table
• Objects stored in shared global address space
CompOrg Fall - Virtual Memory 15
 Macintosh Memory
Allocation / Deallocation Management
• Similar to free-list management of malloc/free
Compaction
• Can move any object and just update the (unique) pointer in pointer table

Shared Address Space

P1 Pointer Table
B
Process P1

“Handles” P2 Pointer Table

C
Process P2
D

E
CompOrg Fall - Virtual Memory 16
 Mac vs. VM-Based Memory
Allocating, deallocating,Mgmt
and moving memory:
• can be accomplished by both techniques
Block sizes:
• Mac: variable-sized
– may be very small or very large
• VM: fixed-size
– size is equal to one page (4KB on x86 Linux systems)
Allocating contiguous chunks of memory:
• Mac: contiguous allocation is required
• VM: can map contiguous range of virtual addresses to disjoint
ranges of physical addresses
Protection
• Mac: “wild write” by one process can corrupt another’s data

CompOrg Fall - Virtual Memory 17

 MAC OS X
“Modern” Operating System
• Virtual memory with protection
• Preemptive multitasking
– Other versions of MAC OS require processes to voluntarily relinquish
control
Based on MACH OS
• Developed at CMU in late 1980’s

CompOrg Fall - Virtual Memory 18

 Motivation #3: Protection
Page table entry contains access rights information
• hardware enforces this protection (trap into OS if violation occurs)
Page Tables Memory
Read? Write? Physical Addr 0:
VP 0: Yes No PP 9 1:
Process i: VP 1: Yes Yes PP 4
VP 2: No No XXXXXXX
• • •
• • •
• • •

Read? Write? Physical Addr

VP 0: Yes Yes PP 6
Process j: VP 1: Yes No PP 9 N-1:
VP 2: No No XXXXXXX
• • •
• • •
• • •
CompOrg Fall - Virtual Memory 19
 Address Translation

Address translation must be fast (it happens on

every memory access).

We need a fully associative placement policy.

• miss penalty is huge!

We can’t afford to go looking at every virtual page

to find the right one
• we don’t use the tag bits approach

CompOrg Fall - Virtual Memory 20

 VM Address Translation
V = {0, 1, . . . , N–1} virtual address space N>M
P = {0, 1, . . . , M–1} physical address space

MAP: V  P U {} address mapping function

MAP(a) = a' if data at virtual address a is present at physical
address a' in P
=  if data at virtual address a is not present in P

page fault
fault
Processor handler

Hardware 
Addr Trans Main Secondary
a Mechanism Memory memory
a'
OS performs
virtual address part of the physical address this transfer
on-chip (only if miss)
memory mgmt unit (MMU) 21
CompOrg Fall - Virtual Memory
 VM Address Translation
Parameters
• P = 2p = page size (bytes).
• N = 2n = Virtual address limit
• M = 2m = Physical address limit

n–1 p p–1 0
virtual page number page offset virtual address

address translation

m–1 p p–1 0
physical page number page offset physical address

Notice that the page offset bits don't change as a result of translation
CompOrg Fall - Virtual Memory 22
 Page Tables
Virtual Page Memory resident
Number page table
(physical page
Valid or disk address)
Physical Memory
1
1
0
1
1
1
0
1
0 Disk Storage
1 (swap file or
regular file system file)

CompOrg Fall - Virtual Memory 23

 Address Translation via Page Table
page table base register virtual address
n–1 p p–1 0
VPN acts as virtual page number (VPN) page offset
table index
valid access physical page number (PPN)

if valid=0
then page
not in memory m–1 p p–1 0
physical page number (PPN) page offset

physical address
CompOrg Fall - Virtual Memory 24
 Page Table Operation
Translation
• Separate (set of) page table(s) per process
• VPN forms index into page table (points to a page table entry)
Computing Physical Address
• Page Table Entry (PTE) provides information about page
– if (valid bit = 1) then the page is in memory.
» Use physical page number (PPN) to construct address
– if (valid bit = 0) then the page is on disk
» Page fault
» Must load page from disk into main memory before continuing
Checking Protection
• Access rights field indicate allowable access
– e.g., read-only, read-write, execute-only
– typically support multiple protection modes (e.g., kernel vs. user)
• Protection violation fault if user doesn’t have necessary permission
CompOrg Fall - Virtual Memory 25
 Integrating VM and Cache
VA PA miss
Trans- Main
CPU Cache
lation Memory
hit
data

Most Caches “Physically Addressed”

• Accessed by physical addresses
• Allows multiple processes to have blocks in cache at same time
• Allows multiple processes to share pages
• Cache doesn’t need to be concerned with protection issues
– Access rights checked as part of address translation
Perform Address Translation Before Cache Lookup
• But this could involve a memory access itself (of the PTE)
• Of course, page table entries can also become cached

CompOrg Fall - Virtual Memory 26

 Speeding up Translation with a TLB
“Translation Lookaside Buffer” (TLB)
• Small hardware cache in MMU
• Maps virtual page numbers to physical page numbers
• Contains complete page table entries for small number of pages

hit
VA PA miss
TLB Main
CPU Cache
Lookup Memory

miss hit

Trans-
lation
data

CompOrg Fall - Virtual Memory 27

 Address Translation with a TLB
n–1 p p–1 0
virtual page number page offset virtual address

valid tag physical page number

. TLB
. .

TLB hit
physical address

tag index byte offset

valid tag data

Cache

cache hit data

CompOrg Fall - Virtual Memory 28
 Simple Memory System
Addressing Example
• 14-bit virtual addresses
• 12-bit physical address
• Page size = 64 bytes

13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN VPO
(Virtual Page Number) (Virtual Page Offset)

11 10 9 8 7 6 5 4 3 2 1 0

PPN PPO
(Physical Page Number) (Physical Page Offset)

CompOrg Fall - Virtual Memory 29

 Simple Memory System Page
• Only show first 16 entries Table

VPN PPN Valid VPN PPN Valid

00 28 1 08 13 1
01 – 0 09 17 1
02 33 1 0A 09 1
03 02 1 0B – 0
04 – 0 0C – 0
05 16 1 0D 2D 1
06 – 0 0E 11 1
07 – 0 0F 0D 1

CompOrg Fall - Virtual Memory 30

 Simple Memory System
TLB TLB
• 16 entries
• 4-way associative

TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN VPO

Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid
0 03 – 0 09 0D 1 00 – 0 07 02 1
1 03 2D 1 02 – 0 04 – 0 0A – 0
2 02 – 0 08 – 0 06 – 0 03 – 0
3 07 – 0 03 0D 1 0A 34 1 02 – 0

CompOrg Fall - Virtual Memory 31

 Simple Memory System
Cache Cache
• 16 lines
• 4-byte line size
• Direct mapped
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0

PPN PPO
Idx Tag Valid B0 B1 B2 B3 Idx Tag Valid B0 B1 B2 B3
0 19 1 99 11 23 11 8 24 1 3A 00 51 89
1 15 0 – – – – 9 2D 0 – – – –
2 1B 1 00 02 04 08 A 2D 1 93 15 DA 3B
3 36 0 – – – – B 0B 0 – – – –
4 32 1 43 6D 8F 09 C 12 0 – – – –
5 0D 1 36 72 F0 1D D 16 1 04 96 34 15
6 31 0 – – – – E 13 1 83 77 1B D3
7 16 1 11 C2 DF 03 F 14 0 – – – –
CompOrg Fall - Virtual Memory 32
 Address Translation Example
Virtual Address 0x03D4 #1
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN VPO
VPN ___ TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____

Physical Address
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0

PPN PPO

Offset ___ CI___ CT ____ Hit? __ Byte: ____

CompOrg Fall - Virtual Memory 33
 Multi-Level Page Tables
Given:
• 4KB (212) page size Level 2
• 32-bit address space Tables
• 4-byte PTE
Problem:
• Would need a 4 MB page table! Level 1
– 220 *4 bytes Table
Common solution
• multi-level page tables
• e.g., 2-level table (P6)
– Level 1 table: 1024 entries, each of ...
which points to a Level 2 page table.
– Level 2 table: 1024 entries, each of
which points to a page

CompOrg Fall - Virtual Memory 34

 Main Themes
Programmer’s View
• Large “flat” address space
– Can allocate large blocks of contiguous addresses
• Processor “owns” machine
– Has private address space
– Unaffected by behavior of other processes
System View
• User virtual address space created by mapping to set of pages
– Need not be contiguous
– Allocated dynamically
– Enforce protection during address translation
• OS manages many processes simultaneously
– Continually switching among processes
– Especially when one must wait for resource
» E.g., disk I/O to handle page fault
CompOrg Fall - Virtual Memory 35