15 213 The course that gives CMU its Zip Virtual Memory October 25 2006 Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBs class16 ppt A System Using Physical Addressing CPU Physical address PA 4 Main memory 0 1 2 3 4 5 6 7 8 M 1 Data word Used by many digital signal processors and embedded microcontrollers in devices like phones and PDAs 2 15 213 F 06 A System Using Virtual Addressing Main memory CPU chip CPU Virtual address VA Address translation MMU Physical address PA 4100 4 0 1 2 3 4 5 6 7 M 1 Data word One of the great ideas in computer science Used by all modern desktop and laptop microprocessors 3 15 213 F 06 Address Spaces A linear address space is an ordered set of contiguous nonnegative integer addresses 0 1 2 3 A virtual address space is a set of N 2n virtual addresses 0 1 2 N 1 A physical address space is a set of M 2m for convenience physical addresses 0 1 2 M 1 In a system based on virtual addressing each byte of main memory has a virtual address and a physical address 4 15 213 F 06 Why Virtual Memory 1 VM uses main memory efficiently Main memory is a cache for the contents of a virtual address space stored on disk Keep only active areas of virtual address space in memory Transfer data back and forth as needed 2 VM simplifies memory management Each process gets the same linear address space 3 VM protects address spaces 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 5 15 213 F 06 1 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 Virtual memory VP 0 VP 1 VP 2n p 1 Unallocated Cached Uncached Unallocated Cached Uncached Cached Uncached 0 0 Empty Empty PP 0 PP 1 Empty N 1 Virtual pages VP s stored on disk 6 Physical memory M 1 PP 2m p 1 Physical pages PP s cached in DRAM 15 213 F 06 DRAM Cache Organization DRAM cache organization driven by the enormous miss penalty DRAM is about 10x slower than SRAM Disk is about 100 000x slower than a DRAM DRAM cache properties Large page block size typically 4 8 KB Fully associative Any virtual page can be placed in any physical page 7 Highly sophisticated replacement algorithms Write back rather than write through 15 213 F 06 Page Tables A page table is an array of page table entries PTEs that maps virtual pages to physical pages Kernel data structure in DRAM Physical page number or Valid disk address null PTE 0 0 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 4 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 8 VP 7 15 213 F 06 Page Hits A page hit is a reference to a VM word that is in physical main memory Physical page Virtual address number or Valid disk address null PTE 0 0 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 4 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 VP 7 9 15 213 F 06 Page Faults A page fault is caused by a reference to a VM word that is not in physical main memory Example A instruction references a word contained in VP 3 a miss that triggers a page fault exception Physical page Virtual address number or Valid disk address null PTE 0 0 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 4 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 10 VP 7 15 213 F 06 Page Faults cont The kernel s page fault handler selects VP 4 as the victim and replaces it with a copy of VP 3 from disk demand paging When the offending instruction restarts it executes normally without generating an exception Physical page Virtual address number or Valid disk address null PTE 0 0 1 1 1 0 0 0 PTE 7 1 null Memory resident page table DRAM Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 3 PP 3 Virtual memory disk VP 1 VP 2 VP 3 VP 4 VP 6 11 VP 7 15 213 F 06 Servicing a Page Fault 1 Processor signals controller Read block of length P starting at disk address X and store starting at memory address Y 2 Read occurs Direct Memory Access DMA Under control of I O controller 3 Controller signals completion 12 Interrupt processor OS resumes suspended process 1 Initiate Block Read Processor Processor Reg 3 Read Done Cache Cache Memory I O Memory I Obus bus 2 DMA Transfer I O I O controller controller Memory Memory disk Disk disk Disk 15 213 F 06 Allocating Virtual Pages Example Allocating new virtual page VP5 Kernel allocates VP 5 on disk and points PTE 5 to this new Physical memory location Physical page Valid PTE 0 0 number or disk address null 1 1 1 0 0 0 PTE 7 1 DRAM PP 0 VP 1 VP 2 VP 7 VP 3 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 5 VP 6 13 VP 7 15 213 F 06 Locality to the Rescue Virtual memory works because of locality At any point in time programs tend to access a set of active virtual pages called the working set Programs with better temporal locality will have smaller working sets If working set size main memory size Good performance after initial compulsory misses If working set size main memory size 14 Thrashing Performance meltdown where pages are swapped copied in and out continuously 15 213 F 06 2 VM as a Tool for Memory Mgmt Key idea Each process has its own virtual address space Simplifies memory allocation sharing linking and loading Virtual Address Space for Process 1 Virtual Address Space for Process 2 15 0 Address Translation 0 VP 1 VP 2 PP 2 N 1 PP 7 0 VP 1 VP 2 N 1 Physical Address Space DRAM e g read only library code PP 10 M 1 15 213 F 06 Simplifying Sharing and Allocation Sharing code and data among processes Map virtual pages to the same physical page PP 7 Memory allocation Virtual page can be mapped to any physical page Virtual Address Space for Process 1 Virtual Address Space for Process 2 16 0 Address Translation …
View Full Document
Unlocking...