CHAPTER 4

(continued):
VIRTUAL MEMORY
 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.
 Virtual memory is stored in a hard disk image. The physical
memory holds a small number of virtual pages in physical
page frames.
A mapping between a virtual and a physical memory:
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 ~300X cheaper than DRAM storage

• To access large amounts of data in a cost-effective
manner, the bulk of the data must be stored on dis
80 GB: ~$110
1GB: ~$200
4 MB: ~$500

SRAM DRAM Disk

 Levels in Memory
Hierarchy
cache virtual memory

C
CPU a Memory
CPU c Memory disk
disk
regs
regs h
e

Register Cache Memory Disk Memory

size: 32 B 32 KB-4MB 1024 MB 100 GB
speed: 1 ns 2 ns 30 ns 8 ms
$/Mbyte: $125/MB $0.20/MB $0.001/MB

larger, slower, cheaper

 DRAM vs. SRAM as a “Cache”

• DRAM vs. disk is more 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

SRAM DRAM Disk

 A System with Virtual Memory
• Examples:
Memory
• workstations, servers, modern PCs, etc.
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 OS-managed lookup table (page table)
 Page Faults (like “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
 Solution: Separate Virt. 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
0
Virtual 0 Address Translation Physical
Address VP 1 PP 2 Address
Space for VP 2 Space
... (DRAM)
Process 1:
N-1

PP 7
Virtual 0
VP 1
Address PP 10
VP 2
Space for ...
Process 2: M-1
N-1
 Motivation #3: Protection
• Page table entry contains access rights
information
• hardware enforces this protection (trap into OS if
Page Tables
violation occurs) 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
• • •
• • •
• • •
 VM Address Translation
• Virtual Address Space
• V = {0, 1, …, N–1}
• Physical Address Space
• P = {0, 1, …, M–1}
• M<N
 VM Address Translation
• Parameters
• P = 2 = page size (bytes).
p

• N = 2 = Virtual address limit

n

n–1
• M = 2 = Physical address limit
m
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

Page offset bits don’t change as a result of translation

 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)
 Address Translation via Page
Table
page table base register virtual address
n–1 p p–1 0
VPN acts virtual page number (VPN) page offset
as
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
 Page Table Operation

• 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
• 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
 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
 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
 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

 Multi-Level Page Tables
Level 2
Tables
• Given:
• 4KB (212) page size
• 32-bit address space
• 4-byte PTE Level 1
Table
• Problem:
• Would need a 4 MB page table!
• 220 *4 bytes

• 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
 Simple Memory System Example
• Addressing
• 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)
Simple Memory System Page Table

• Only show first 16 entries

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
 Simple Memory System TLB

• TLB
• 16 entries

12•
TLBT associative
4-way TLBI
13 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
 Simple Memory System Cache
• Cache CT CI CO
• 16 lines
11 10 9 8 7 6 5 4 3 2 1 0
• 4-byte line size
• Direct mapped 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 – – – –
 Address Translation Example #1
• Virtual Address 03D4
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

Offset ___ CI___ PPN

CT ____ Hit? __ Byte: ____ PPO
 Address Translation Example #2
• Virtual Address 0B8F
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

Offset ___ CI___ CT ____ Hit? PPN

__ Byte: ____ PPO
 Address Translation Example #3
• Virtual Address 0040
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0

VPN ___ TLBI ___TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____
VPN VPO
• Physical Address

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

Offset ___ CI___

PPN
CT ____ Hit? __ Byte: ____
PPO
 Exercise
Consider a virtual memory system with the following
properties:
• 40-bit virtual address
• 16-Kbyte pages
• 36-bit physical byte address
- What is the total size of the page table, assuming that
the valid, protection, dirty and use bits take a total of
4 bits and that all the virtual pages are in use.
- Assume that the virtual memory system is
implemented with a 2-way set-associative TLB with a
total of 256 TLB entries. Describe the virtual-to-
physical mapping, specifying the width of all fields in
mapping process.