15 213 The course that gives CMU its Zip Virtual Memory November 2 2007 Topics class19 ppt Motivations for virtual memory Address translation Accelerating translation with TLBs 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 2 15 213 F 07 Motivation 1 DRAM a Cache for Disk The full address space is quite large 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 To access large amounts of data in a cost effective manner the bulk of the data must be stored on disk 8 GB 300 1 TB 300 4 MB 300 SRAM 3 DRAM Disk 15 213 F 07 Levels in Memory Hierarchy Smaller faster and costlier per byte storage devices Larger slower and cheaper per byte storage devices L5 4 L0 registers L1 on chip L1 cache SRAM L2 L3 L4 CPU registers hold words retrieved from L1 cache 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 local secondary storage local disks Main memory holds disk blocks retrieved from 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 DRAM vs disk is more extreme than SRAM vs DRAM access latencies DRAM is 10X slower than SRAM disk is 100 000X slower than DRAM importance of exploiting spatial locality first byte is 100 000X slower than successive bytes on disk vs 4X improvement for page mode vs regular accesses to DRAM cache size main memory is 1000X larger than an SRAM cache addressing for disk is based on sector address not memory address SRAM 5 DRAM Disk 15 213 F 07 Impact of These Properties on Design If DRAM was to be organized similar to an SRAM cache how would we set the following design parameters Line size Associativity Replacement policy if associative Write through or write back What would the impact of these choices be on 6 miss rate hit time miss latency tag overhead 15 213 F 07 Locating an Object in a Cache Cache 1 Search for matching tag SRAM cache Object Name X X Tag Data 0 D 243 1 X J 17 105 N 1 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 Data N 1 15 213 F 07 A System with Physical Memory Only Examples most Cray machines early PCs nearly all embedded systems phones PDAs etc Memory Store 0x10 0 1 CPU Load 0xf0 N 1 CPU s load or store addresses used directly to access memory 8 15 213 F 07 A System with Virtual Memory Examples Memory laptops servers modern PCs etc Page Table MMU Virtual Physical Addresses 0 Addresses 1 0 1 Store 0x10 CPU Load 0xf0 P 1 N 1 Disk Address Translation the hardware converts virtual addresses into physical addresses via an OS managed lookup table page table 9 15 213 F 07 Page Faults Similar to Cache Misses What if an object is on disk rather than in memory Page table entry indicates that the virtual address is not in memory An OS trap handler is invoked moving data from disk into memory current process suspends others can resume OS has full control over placement etc Page Table MMU Virtual Physical Addresses 0 Addresses 1 CPU Memory 0 1 Load 0x05 Store 0xf8 P 1 N 1 Disk 10 15 213 F 07 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 11 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 07 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 12 Thrashing Performance meltdown where pages are swapped copied in and out continuously 15 213 F 07 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 13 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 07 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 14 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 07 Simplifying Linking and Loading 0xc0000000 Linking User stack created at runtime 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 Loading 15 Kernel virtual memory Run time heap created at runtime by malloc execve maps PTEs to 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 0x08048000 virtual memory system 0 Unused Memory invisible to user code esp stack ptr brk Loaded from executable file 15 213 F 07 3 VM as a Tool for Memory Protection Extend PTEs with permission bits Page fault handler checks these before remapping If violated send process SIGSEGV segmentation fault Page tables with permission bits Process i SUP READ WRITE Yes No VP 0 No Yes Yes VP 1 No Yes Yes VP …
View Full Document
Unlocking...