[SOLVED] CS algorithm cache Carnegie Mellon

Carnegie Mellon
Chapter 9: Virtual Memory
1

Carnegie Mellon
Today
Address spaces
VM as a tool for caching
VM as a tool for memory management VM as a tool for memory protection
Address translation
2

Carnegie Mellon
A System Using Physical Addressing
Main memory
0: 1:
Physical address 2:
CPU 4
(PA)
3:
4: 5: 6: 7: 8:
M-1:
Data word
Used in simple systems like embedded microcontrollers in devices like cars, elevators, and digital picture frames
3

Carnegie Mellon
A System Using Virtual Addressing
CPU Chip
Main memory
0: 1: 2: 3: 4: 5: 6: 7: 8:
M-1:
Virtual address (VA)
Physical address (PA)
4
CPU
MMU
4100
Data word
Used in all modern servers, desktops, and laptops One of the great ideas in computer science
4

Carnegie Mellon
Address Spaces
Linear address space: Ordered set of contiguous non-negative integer
addresses:
{0, 1, 2, 3 }
Virtual address space: Set of N = 2n virtual addresses {0, 1, 2, 3, , N-1}
Physical address space: Set of M = 2m physical addresses {0, 1, 2, 3, , M-1}
Clean distinction between data (bytes) and their attributes (addresses)
Eachobjectcannowhavemultipleaddresses
Every byte in main memory:
one physical address, one (or more) virtual addresses
5

Carnegie Mellon
Why Virtual Memory (VM)? Uses main memory efficiently
Use DRAM as a cache for the parts of a virtual address space Simplifies memory management
Each process gets the same uniform linear address space
Isolates address spaces
One process cant interfere with anothers memory
User program cannot access privileged kernel information
6

Carnegie Mellon
VM as a Tool for Caching
Virtual memory is an array of N contiguous bytes stored on disk.
The contents of the array on disk are cached in physical memory (DRAM cache)
These cache blocks are called pages (size is P = 2p bytes)
VP 0 VP 1
0
Virtual memory
Physical memory
Unallocated
Cached
Uncached
Unallocated
Cached
Uncached
Cached
Uncached
0
PP 0 PP 1
PP 2m-p-1
Empty
Empty
Empty
VP 2n-p-1
M-1
Virtual pages (VPs) stored on disk
Physical pages (PPs) cached in DRAM
N-1
7

Carnegie Mellon
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
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
8