Transcript Transistors and Logic Gates

Virtual Memory
Virtual memory
Build new hardware that automatically translates each
memory reference from a virtual address (that the
programmer sees as an array of bytes) to a physical
address (that the hardware uses to either index DRAM or
identify where the storage resides on disk)
2
Basics of Virtual memory
Any time you see the word virtual in computer
science/architecture it means “using a level of indirection”
Virtual memory hardware changes the virtual address the
programmer see into the physical ones the memory chips
see.
0x800
Disk0x3C00
ID 803C4
Virtual address
Physical address
3
Another View of the Memory Hierarchy
Thus far
{
{
Next:
Virtual
Memory
Regs
Instr. Operands
Cache
Blocks
Upper Level
Faster
L2 Cache
Blocks
Memory
Pages
Disk
Files
Tape
Larger
Lower Level
4
Virtual Memory
If Principle of Locality allows caches to offer
(usually) speed of cache memory with size of DRAM
memory,
then recursively why not use at next level to give
speed of DRAM memory, size of Disk memory?
Called “Virtual Memory”
• Also allows OS to share memory, protect programs from
each other
• Today, more important for protection vs. just another level
of memory hierarchy
• Historically, it predates caches
5
Basic Issues in Virtual Memory System Design
•Size of information blocks that are transferred from
secondary to main storage (M)
•Block of information brought into M, and M is full, then
some region of M must be released to make room for the new
block replacement policy
•which region of M is to hold the new block --> placement
policy
cache
mem
disk
reg
pages
frame
Paging Organization
virtual and physical address space partitioned into blocks of equal size
page frames
pages
6
Virtual Memory View
Virtual memory lets the programmer “see” a memory array
larger than the DRAM available on a particular computer
system.
Virtual memory enables multiple programs to share the
physical memory without:
• Knowing other programs exist.
• Worrying about one program modifying the data contents of
another.
7
Managing virtual memory
Managed by hardware logic and operating system
software.
• Hardware for speed.
• Software for flexibility and because disk storage is controlled by
the operating system.
8
Virtual to Physical Address Translation
Program
operates in
its virtual
address
space
virtual
address
(inst. fetch
load, store)
HW
mapping
physical
address
(inst. fetch
load, store)
Physical
memory
(incl. caches)
Each program operates in its own virtual address space;
~only program running
Each is protected from the other
OS can decide where each goes in memory
Hardware (HW) provides virtual -> physical mapping
9
Virtual Memory
Treat main memory like a cache
• Misses go to the disk
How do we minimize disk accesses?
• Buy lots of memory.
• Exploit temporal locality
 Fully associative? Set associative? Direct mapped?
• Exploit spatial locality
 How big should a block be?
• Write-back or write-through?
10
Virtual memory terminology
Blocks are called Pages
• A virtual address consists of
A virtual page number
A page offset field (low order bits of the address)
Virtual page number
31
Page offset
11
0
Misses are call Page faults
• and they are generally handled as an exception
11
Address Translation
Physical
address
Virtual
address
0
Address
translation
0
0
Disk
addresses
12
Need a Page Table (table that tracks where all
virtual memory pages are) components
Page table register
Virtual page number
Page offset
valid Physical page number
1
Physical page number
Physical page number
Page offset
13
Page table components
Page table register
0x00004
0x0F3
valid Physical page number
1
0x020C0
0x0F3
Physical address = 0x020C00F3
0x020C0
14
Page table components
Page table register
0x00002
0x082
valid Physical page number
0
Disk address
Exception:
page fault
1.
2.
3.
4.
5.
6.
Stop this process
Pick page to replace
Write back data
Get referenced page
Update page table
Reschedule process
15
Putting it all together
Loading your program in memory
• Ask operating system to create a new process
• Construct a page table for this process
• Mark all page table entries as invalid with a pointer to the
disk image of the program
 That is, point to the executable file containing the
binary.
• Run the program and get an immediate page fault on the
first instruction.
16
Mapping Virtual Memory to Physical Memory
Virtual Memory
Divide into equal sized
chunks (about 4KB)
Any chunk of Virtual Memory assigned
to any chuck of Physical Memory
(“page”)
Page Frame (PF) holds a page in
Physical
Memory
memory
64 MB

Stack
Heap
Static
0
Code
0
17
Paging Organization (assume 1 KB pages)
Virtual
Physical Page is unit
Address
Address of mapping
page
0
0
page
0
1K
0
1024 page 1
Addr
1024 page 1 1K
...
... ...
Trans 2048 page 2
MAP
7168 page 7 1K
...
...
1K
1K
1K
...
Physical
31744 page 31 1K
Memory Page also unit of
Virtual
transfer from disk
to physical memory Memory
18
Virtual Memory Mapping Function
Cannot have simple function to predict
arbitrary mapping
Use table lookup of mappings
Page Number Offset
Use table lookup (“Page Table”) for mappings: Page
number is index
Virtual Memory Mapping Function
• Physical Offset = Virtual Offset
• Physical Page Number
= PageTable[Virtual Page Number]
(P.P.N. also called “Page Frame”)
19
Page Table
A page table is an operating system structure which
contains the mapping of virtual addresses to
physical locations
• There are several different ways, all up to the operating
system, to keep this data around
Each process running in the operating system has
its own page table
• “State” of process is PC, all registers, plus page table
• OS changes page tables by changing contents of Page
Table Base Register
20
Size of page table
How big is a page table entry?
• For MIPS the virtual address is 32 bits
 If the machine can support 1GB of physical memory
and we use 4KB pages, then the physical page
number is 30-12 or 18 bits. Plus another valid bit +
other useful stuff (read only, dirty, etc.)
 Let say about 3 bytes.
How many entries in the page table?
• MIPS virtual address is 32 bits – 12 bit page offset = 220
or ~1,000,000 entries
Total size of page table: ~ 3 megabytes
21
Address Mapping: Page Table
Virtual Address:
concatenation
page no. offset
Page Table
Base Reg
index
into
page
table
Page Table
...
V
A.R. P. P. A.
+
Val Access Physical
-id Rights Page
Address Physical
Memory
Address
.
...
Page Table located in physical memory
22
VM Address Translation
Parameters
• P = 2p = page size (bytes). Typically 1KB–16KB
• N = 2n = Virtual address limit
• M = 2m = Physical address limit
n–1
p p–1
virtual page number
0
virtual address
page offset
address translation
m–1
p p–1
physical page number
page offset
0
physical address
Notice that the page offset bits don't change as a result of translation
23
Page Tables
Virtual Page
Number
Page Table
(physical page
Valid or disk address)
1
1
0
1
1
1
0
1
0
1
Physical Memory
Disk Storage
24
A System with Physical Memory Only
Example:
• Most Cray machines, early PCs, nearly all embedded systems,
etc.
Memory
Store 0x10
0:
1:
CPU
Load 0xf0
N-1:
CPU’s load or store addresses used directly to access memory.
25
A System with Virtual Memory
Examples:
• workstations, servers, modern PCs, etc.
Virtual
Addresses
Store 0x10
Page Table
0:
1:
Memory
0:
1:
Physical
Addresses
CPU
Load 0xf0
P-1:
N-1:
Disk
Address Translation: the hardware converts virtual addresses into
physical addresses via an OS-managed lookup table (page table)
26
Page Faults (Similar to “Cache Misses”)
What if an object is on disk rather than in memory?
• Page table entry indicates that the virtual address is not in memory
• An OS trap handler is invoked, moving data from disk into memory
 current process suspends, others can resume
 OS has full control over placement, etc.
Virtual
Addresses
CPU
Page Table
0:
1:
Memory
0:
1:
Physical
Addresses
Load 0x05
Store 0xf8
P-1:
N-1:
Disk
27
Servicing a Page Fault
(1) Initiate Block Read
Processor Signals Controller
• Read block of length P
Processor
Reg
starting at disk address X
(3) Read
and store starting at memory
Done
address Y
Cache
Read Occurs
• Direct Memory Access
• Under control of I/O
Memory-I/O bus
controller
(2) DMA Transfer
I / O Controller Signals Completion
I/O
• Interrupt processor
controller
Memory
• Can resume suspended
process
disk
Disk
disk
Dis
k
28
Motivation: Memory Management for
Multiple Processes
Multiple processes can reside in physical memory.
How do we resolve address conflicts?
(Virtual) Memory Image for Alpha Process
0000 03FF 8000 0000
Reserved
Not yet allocated
Dynamic Data
$gp
0000 0001 2000 0000
$sp
Static Data
e.g., what if two different
processes access their stacks
at address 0x11fffff80 at
the same time?
Text (Code)
Stack
Not yet allocated
0000 0000 0001 0000
Reserved
29
Solution: Separate Virtual Address Spaces
• Virtual and physical address spaces divided into equal-sized blocks
 “Pages” (both virtual and physical)
• Each process has its own virtual address space
 operating system controls how virtual pages as assigned to physical
memory
Virtual Addresses
0
Process 1:
VP 1
VP 2
Address
Translation
Physical Addresses
0
PP 2
N-1
PP 7
Process 2:
0
N-1
VP 1
VP 2
(Read-only
library code)
PP 10
M-1
30
Motivation : Process 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
Process i:
VP 0:
Yes
No
PP 9
VP 1:
Yes
Yes
PP 4
VP 2:
No
No
XXXXXXX
•
•
•
•
•
•
0:
1:
•
•
•
Read? Write? Physical Addr
Process j:
VP 0:
Yes
Yes
PP 6
VP 1:
Yes
No
PP 9
VP 2:
No
No
XXXXXXX
•
•
•
•
•
•
N-1:
•
•
•
31
Virtual Memory Problem #1
Not enough physical memory!
• Only, say, 64 MB of physical memory
• N processes, each 4GB of virtual memory!
• Could have 1K virtual pages/physical page!
Spatial Locality to the rescue
• Each page is 4 KB, lots of nearby references
• No matter how big program is, at any time only accessing a few
pages
• “Working Set”: recently used pages
32
Virtual Memory Problem #2
Map every address  1 extra memory accesses for
every memory access
Observation: since locality in pages of data, must be
locality in virtual addresses of those pages
Why not use a cache of virtual to physical address
translations to make translation fast? (small is fast)
For historical reasons, cache is called a Translation
Lookaside Buffer, or TLB
33
Translation Look-Aside Buffers
•TLBs usually small, typically 128 - 256 entries
• Like any other cache, the TLB can be fully
associative, set associative, or direct mapped
VA
Processor
hit PA
TLB
Lookup
miss
Translation
miss
Cache
Main
Memory
hit
data
34
Virtual Memory Summary
Caches: Location, Organization (block size and associativity),
Replacement
Virtual memory provides
• protection, sharing, illusion of large main memory
Virtual Memory requires twice as many memory accesses, so we
cache page table entries in the TLB.
Three things can go wrong on a memory access: cache miss, TLB
miss, page fault.
35