Why Virtual Memory 15 213 1 VM uses main memory efficiently The course that gives CMU its Zip Virtual Memory November 2 2007 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 Topics Motivations for virtual memory Address translation Accelerating translation with TLBs 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 z Because they operate in different address spaces z Different sections of address spaces have different permissions class19 ppt 15 213 F 07 2 Motivation 1 DRAM a Cache for Disk Levels in Memory Hierarchy The full address space is quite large Smaller faster and costlier per byte storage devices 32 bit addresses 4 000 000 000 4 billion bytes 64 bit addresses 16 000 000 000 000 000 000 16 quintillion bytes Disk storage is 100X cheaper than DRAM storage 1 TB of DRAM 30 000 1 TB of disk 300 SRAM 3 8 GB 300 DRAM Larger slower and cheaper per byte storage devices 1 TB 300 Disk L5 15 213 F 07 4 Page 1 CPU registers hold words retrieved from L1 cache L1 on chip L1 cache SRAM L2 L3 To access large amounts of data in a costcost effective manner the bulk of the data must be stored on disk 4 MB 300 L0 registers L4 off chip L2 cache SRAM L1 cache holds cache lines retrieved from the L2 cache memory L2 cache holds cache lines retrieved from main memory main memory DRAM Main memory holds disk blocks retrieved from local disks local secondary storage local disks Local disks hold files retrieved from disks on remote network servers remote secondary storage tapes distributed file systems Web servers 15 213 F 07 DRAM vs SRAM as a Cache Impact of These Properties on Design DRAM vs disk is more extreme than SRAM vs DRAM If DRAM was to be organized similar to an SRAM cache how would we set the following design parameters access latencies z DRAM is 10X slower than SRAM z disk is 100 000X slower than DRAM importance of exploiting spatial locality z first byte is 100 000X slower than successive bytes on disk Line size Associativity Replacement policy if associative Write through or write back vs 4X improvement for page mode vs regular accesses to DRAM cache size z main memory is 1000X larger than an SRAM cache addressing for disk is based on sector address not memory address What would the impact of these choices be on Disk DRAM SRAM 15 213 F 07 5 A System with Physical Memory Only Cache SRAM cache Object Name X X Tag Data 0 D 243 1 X J 17 105 N 1 15 213 F 07 6 Locating an Object in a Cache 1 Search for matching tag miss rate hit time miss latency tag overhead Examples most Cray machines early PCs nearly all embedded Memory systems phones PDAs etc 0 1 Store 0x10 CPU 2 Use indirection to look up actual object location virtual memory Lookup Table Cache Location Object Name D 0 0 243 X J N 1 1 1 17 105 X 7 Load 0xf0 Data N 1 N 1 CPU s load or store addresses used directly to access memory 15 213 F 07 8 Page 2 15 213 F 07 A System with Virtual Memory What if an object is on disk rather than in memory Examples Page Faults Similar to Cache Misses Memory laptops servers modern PCs etc Virtual Addresses Store 0x10 0 1 Page Table MMU 0 1 Page table entry indicates that the virtual address is not in memory An OS trap handler is invoked moving data from disk into memory z current process suspends others can resume Virtual Addresses CPU Load 0xf0 CPU P 1 Address Translation the hardware converts virtual addresses into physical addresses via an OS managed lookup table page table Direct Memory Access DMA Under control of I O controller 3 Controller signals completion 11 Interrupt processor OS resumes suspended process Physical Addresses 1 Initiate Block Read 15 213 F 07 Virtual memory works because of locality 3 Read Done At any point in time programs tend to access a set of active virtual pages called the working set set Cache Cache Memory I O Memory I Obus bus 2 DMA Transfer I O I O controller controller Memory Memory disk Disk N 1 Locality to the Rescue Processor Processor Reg P 1 10 Servicing a Page Fault 2 Read occurs 0 1 Disk 15 213 F 07 9 Read block of length P starting at disk address X and store starting at memory address Y Page Table MMU Load 0x05 Store 0xf8 0 1 N 1 Disk 1 Processor signals controller Memory z OS has full control over placement etc Physical Addresses Programs with better temporal locality will have smaller working sets If working set size main memory size disk Disk Good performance after initial compulsory misses If working set size main memory size 15 213 F 07 12 Page 3 Thrashing Performance meltdown where pages are swapped copied in and out continuously 15 213 F 07 2 VM as a Tool for Memory Mgmt Simplifying Sharing and Allocation Sharing code and data among processes Key idea Each process has its own virtual address space 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 VP 1 VP 2 PP 2 0 VP 1 VP 2 0 e g read only library code Virtual Address Space for Process 2 M 1 N 1 15 213 F 07 13 Kernel virtual memory User stack created at runtime Linking Each program has similar virtual address space Code stack and shared Memory mapped region for libraries always start at the shared libraries same address 0x40000000 15 PP 2 Physical Address Space DRAM N 1 0 VP 1 VP 2 e g read only library code PP 10 M 1 N 1 15 213 F 07 3 VM as a Tool for Memory Protection Memory invisible to user code Extend PTEs with permission bits Page fault handler checks these before remapping esp stack ptr If violated send process SIGSEGV segmentation fault Page tables with permission bits Loading VP 1 VP 2 14 Simplifying Linking and Loading 0xc0000000 Address Translation 0 PP 7 PP 10 Virtual page can be mapped to any physical page Virtual Address Space for Process 1 N 1 PP 7 Virtual Address Space for Process 2 Physical Address Space DRAM Address Translation 0 Process i brk Run time heap execve maps PTEs to created at runtime by malloc the appropriate location in the executable binary file Read write segment data bss The text and data sections are copied page Read only segment by page on demand by the init text rodata virtual memory system 0x08048000 0 SUP READ WRITE VP 0 No Yes No VP 1 …
View Full Document
Unlocking...