A System Using Physical Addressing 15 213 The course that gives CMU its Zip Virtual Memory October 25 2006 CPU Physical address PA 4 Main memory 0 1 2 3 4 5 6 7 8 Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBs M 1 Data word Used by many digital signal processors and embedded microcontrollers in devices like phones and PDAs PDAs class16 ppt A System Using Virtual Addressing Main memory CPU chip CPU 15 213 F 06 2 Virtual address VA Address translation MMU Physical address PA 4100 4 0 1 2 3 4 5 6 7 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 addresses 0 1 2 NN 1 A physical address space is a set of M 2m for convenience physical addresses addresses M 1 Data word 0 1 2 MM 1 One of the great ideas in computer science Used by all modern desktop and laptop microprocessors 3 15 213 F 06 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 as a Tool for Caching 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 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 2 VM simplifies memory management Each process gets the same linear address space VP 0 VP 1 One process can t interfere with another z Because they operate in different address spaces VP 2n p 1 User process cannot access privileged information 15 213 F 06 Uncached Cached Uncached 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 Large page block size typically 4 8 KB Fully associative Empty Empty PP 2m p 1 M 1 N 1 Physical pages PP s cached in DRAM 15 213 F 06 A page table is an array of page table entries PTEs 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 z Any virtual page can be placed in any physical page PP 0 PP 1 Page Tables DRAM cache properties Empty 6 DRAM Cache Organization 0 Cached Uncached Virtual pages VP s stored on disk z Different sections of address spaces have different permissions 5 Unallocated Unallocated Cached 3 VM protects address spaces Physical memory 0 Highly sophisticated replacement algorithms null VP 2 VP 7 VP 4 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM Write back rather than write through Physical memory DRAM VP 1 PP 0 VP 2 VP 3 VP 4 VP 6 7 15 213 F 06 8 VP 7 15 213 F 06 Page Hits Page Faults A page fault is caused by a reference to a VM word that is not in physical main memory A page hit is a reference to a VM word that is in physical main memory Physical page number or Valid disk address null PTE 0 0 Virtual address 1 1 0 1 0 0 PTE 7 1 null Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 4 Physical memory DRAM VP 1 PP 0 Physical page number or Valid disk address null PTE 0 0 Virtual address PP 3 1 1 0 1 0 0 PTE 7 1 Virtual memory disk VP 1 Memory resident page table DRAM Example A instruction references a word contained in VP 3 a miss that triggers a page fault exception VP 2 VP 2 VP 7 VP 4 Virtual memory disk null VP 1 Memory resident page table DRAM VP 3 VP 4 VP 2 VP 3 VP 4 VP 6 VP 6 VP 7 15 213 F 06 9 VP 7 10 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 1 Processor signals controller When the offending instruction restarts it executes normally without generating an exception Physical page number or Valid disk address null PTE 0 0 Virtual address 1 1 1 0 0 0 PTE 7 1 Physical memory DRAM VP 1 PP 0 VP 2 VP 7 VP 3 Memory resident page table DRAM Read block of length P starting at disk address X and store starting at memory address Y 2 Read occurs PP 3 null 15 213 F 06 Servicing a Page Fault Page Faults cont PP 3 Virtual memory disk VP 1 Direct Memory Access DMA Under control of I O controller 3 Controller signals completion VP 2 VP 3 VP 4 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 VP 6 11 VP 7 15 213 F 06 12 15 213 F 06 Allocating Virtual Pages Locality to the Rescue Virtual memory works because of locality 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 DRAM VP 1 VP 2 VP 7 VP 3 1 1 1 0 0 0 PTE 7 1 PP 0 At any point in time programs tend to access a set of active virtual pages called the working set set PP 3 Virtual memory disk If working set size main memory size VP 1 Memory resident page table DRAM Good performance after initial compulsory misses VP 2 VP 3 If working set size main memory size VP 4 VP 5 VP 6 VP 7 13 15 213 F 06 2 VM as a Tool for Memory Mgmt Key idea Each process has its own virtual address space Programs with better temporal locality will have smaller working sets Thrashing Performance meltdown where pages are swapped copied in and out continuously 15 213 F 06 14 Simplifying Sharing and Allocation Sharing code and data among processes Simplifies memory allocation sharing linking and loading Map virtual pages to the same physical page PP 7 Memory allocation 0 Virtual Address Space for Process 1 Address Translation 0 VP 1 VP 2 PP 2 15 0 VP 1 VP 2 0 e g read only library code Address Translation 0 VP 1 VP 2 PP 2 Virtual Address Space for Process 2 M 1 15 213 F 06 16 Physical Address Space DRAM N 1 PP 7 PP 10 N 1 Virtual page can be mapped to …
View Full Document
Unlocking...