15 213 The course that gives CMU its Zip Virtual Memory March 18 2007 Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBs class16 ppt All About Memory How memory works Capacitors magnetic domains Row address column address row buffer supercell We covered this back in mid February What memory does Store stuff More formally fetch address data store address data The world is imperfect so fetch address data store address data 2 15 213 S 08 Complaints This kind of memory has problems It has finite size Each system has only one memory A single program might need more memory than is available If we will run multiple programs each program needs a simple way to know which memory it should use Programmer A doesn t want mistakes made by Programmer B to inflict un debuggable random crashes on her We need a way to stop programs from accidentally using the wrong memory But it s the only kind of memory we have 3 15 213 S 08 Happiness via Mathematics One simple trick solves all three problems Imagine per process private memories process id fetch address data process id store address data This would fix how to share and don t use the wrong memory Surprisingly it also fixes finite size Implementation is a little different process id map process address physical address mfetch fetch map address data mstore store map address data This mapping trick is the heart of virtual memory 4 15 213 S 08 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 physical address and a virtual address or more 5 15 213 S 08 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 6 15 213 S 08 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 7 15 213 S 08 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 User process cannot access privileged information 8 Because they operate in different address spaces Different sections of address spaces have different permissions 15 213 S 08 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 9 Physical memory M 1 PP 2m p 1 Physical pages PP s cached in DRAM 15 213 S 08 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 This requires a large mapping function different from other caches Highly sophisticated replacement algorithms 10 Too complicated and open ended to be implemented in hardware Write back rather than write through 15 213 S 08 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 VP 2 VP 7 VP 4 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 11 VP 7 15 213 S 08 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 VP 2 VP 7 VP 4 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 12 VP 7 15 213 S 08 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 VP 2 VP 7 VP 4 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 13 VP 7 15 213 S 08 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 VP 2 VP 7 VP 3 PP 0 PP 3 Virtual memory disk VP 1 VP 2 VP 3 VP 4 VP 6 14 VP 7 15 213 S 08 Servicing a Page Fault 1 Processor signals disk 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 Interrupts 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 15 disk Disk disk Disk 15 213 S 08 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 number or Valid disk address null PTE 0 0 1 1 …
View Full Document
Unlocking...