Some VM Complications
• Extra memory accesses
– One for translation
– One for access
• Page tables are huge
– 220 ~= 1 million entries
• Page thrashing
– Poor data usage patterns can destroy performance
• Issues with caching
– Do caches use virtual or physical addresses?
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
Translation Lookaside Buffer
• We fix the performance problem by avoiding the memory access in the
translation from virtual to physical pages.
• We buffer the common translations in a Translation lookaside buffer (TLB)
• Basically, a specialized cache of the page table
– Hit in the TLB – can skip the access to the page table
– Miss in the TLB – have to do both accesses
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
TLB – a Cache for VM
Virtual page Pg offset
v
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
tag
Physical page
Dan Ernst
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
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
How can you organize the page table?
1.
2.
Continuous 3MB region of physical memory
Bounded size continuous region of physical mem
•
3.
You will actually need 2 non-contiguous regions
Use a hash function instead of an array (“inverted page table”)
•
4.
Slower, but less memory
Build a hierarchical page table
•
•
Super page table in physical memory
Second (and maybe third) level page tables in virtual address space
•
This allows you to page the page table
Virtual Superpage
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Virtual page
Page offset
Dan Ernst
Hierarchical Page Table – Possible Structure
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
VM + Caching
• Access cache with virtual address?
– fast, but every time we switch processes, we have to completely wipe the cache
clean! (includes writing back all dirty blocks!)
• Access cache with physical address?
– slow, but fixes the aliasing problem in the cache
• Virtually indexed, physically tagged
– Index into the cache using the virtual index
• This gets a set of tags
– Compare the Physical page number with the tags to check for a cache hit.
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
Virtual Index/ Physical Tag
Virtual address
Virtual page Page offset
index
TLB
tag
tag
tag
tag
PPN
Block
offset
PPN
PPN
PPN
PPN
Page offset
tag
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Cache
Set0 tag
Set0 tag
Set1 tag
Set1 tag
Set2 tag
Set2 tag
Tag
cmp
Tag
cmp
Dan Ernst
What about writes?
• Since Virtual Memory is just like a “cache” for the disk, we have to
make a decision on how to handle writes (stores)
• Due to the extremely long delay to disk, virtual memory systems use:
Write-Back ( AKA “Copy-Back” )
• Each Page has a “dirty bit” which indicates that it has been written to
• When a page is evicted from memory, it is written back to the disk or
not based on that bit
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
How do we find it on disk?
• That is not a hardware problem! 
• Most operating system partition the disk into logical devices (C: , D: ,
/home, etc.)
• They also sometimes have a separate area to support the disk portion
of virtual memory
– Swap partition on UNIX machines
– You then index into the correct page in the swap partition.
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
OS support for Virtual memory
• It must be able to modify the page table register, update page table
values, etc.
– To enable the OS to do this, AND not the user program, we have different
execution modes for a process – one which has executive (or supervisor or kernel
level) permissions and one that has user level permissions.
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
Example Question
Consider a virtual memory system with the following parameters:
– 32-bit virtual address space (byte-addressed)
– 4 KB page size
– 28-bit physical address space (byte-addressed)
What is the:
a) number of bits needed to specify the virtual page number?
b) number of bits needed to specify the physical page number?
CS 352 : Computer Organization and Design
University of Wisconsin-Eau Claire
Dan Ernst
Descargar

370 lecture - UWEC Computer Science Department