Why Virtual Memory Virtual Memory CS 740 1 VM uses main memory efficiently October 23 2007 2 VM simplifies memory management Topics 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 Each process gets the same linear address space z motivation z mechanisms 3 VM protects address spaces Accelerating translation with TLBs 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 15 740 F 07 1 15 740 F 07 2 Levels in Memory Hierarchy Motivation 1 DRAM a Cache for Disk Smaller faster and costlier per byte storage devices 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 costcost effective manner the bulk of the data must be stored on disk 4 MB 300 SRAM 3 8 GB 300 DRAM Larger slower and cheaper per byte storage devices 1 TB 300 Disk L5 15 740 F 07 4 Page 1 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 740 F 07 DRAM vs SRAM as a Cache 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 DRAM vs disk is more extreme than SRAM vs DRAM 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 vs 4X improvement for page mode vs regular accesses to DRAM cache size addressing for disk is based on sector address not memory address z main memory is 1000X larger than an SRAM cache Line size Associativity Replacement policy if associative Write through or write back What would the impact of these choices be on SRAM Disk DRAM 15 740 F 07 5 SRAM cache Object Name X X Data 0 D 243 1 X J 17 105 N 1 Examples virtual memory Lookup Table 0 1 CPU Cache Location 7 Load 0xf0 Data Object Name D 0 0 243 X J N 1 1 1 17 105 X most Cray machines early PCs nearly all embedded Memory systems phones PDAs etc Store 0x10 2 Use indirection to look up actual object location 15 740 F 07 A System with Physical Memory Only Cache Tag hit time miss latency tag overhead 6 Locating an Object in a Cache 1 Search for matching tag miss rate N 1 N 1 CPU s load or store addresses used directly to access memory 15 740 F 07 8 Page 2 15 740 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 Page Table MMU 0 1 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 Physical Addresses Virtual Addresses CPU Load 0xf0 P 1 CPU N 1 Disk 15 740 F 07 9 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 Interrupt processor OS resumes suspended process P 1 N 1 15 740 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 Cache Cache Memory I O Memory I Obus bus 2 DMA Transfer I O I O controller controller Memory Memory disk Disk 11 Physical Addresses Locality to the Rescue 1 Initiate Block Read Reg 0 1 Disk 10 Servicing a Page Fault Processor Processor 0 1 Page Table MMU Load 0x05 Store 0xf8 Address Translation the hardware converts virtual addresses into physical addresses via an OS managed lookup table page table 1 Processor signals controller Memory z OS has full control over placement etc Programs with better temporal locality will have smaller working sets If working set size main memory size disk Dis k Good performance after initial compulsory misses If working set size main memory size 15 740 F 07 12 Page 3 Thrashing Performance meltdown where pages are swapped copied in and out continuously 15 740 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 Virtual Address Space for Process 1 Virtual Address Space for Process 2 0 Address Translation VP 1 VP 2 0 PP 2 N 1 PP 7 0 VP 1 VP 2 Physical Addres s Space DRAM Virtual Address Space for Process 1 e g read only library code PP 10 Virtual Address Space for Process 2 M 1 N 1 15 740 F 07 13 0xc0000000 Each program has similar virtual address space Kernel virtual memory User stack created at runtime execve maps PTEs to the appropriate location in the executable binary file PP 2 N 1 PP 7 0 VP 1 VP 2 Physical Addres s Space DRAM e g read only library code PP 10 M 1 N 1 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 SUP READ Memory mapped region for shared libraries Run time heap created at runtime by malloc The text and data sections are copied page by page on demand by the virtual memory system Read write segment data bss 0x08048000 15 VP 1 VP 2 0 Page tables with permission bits Code stack and shared libraries always start at the same address 0x40000000 Address Translation 15 740 F 07 Process i Loading 0 14 Simplifying Linking and Loading Linking Virtual page can be mapped to any physical page 0 Read only segment init text rodata Unused VP 0 VP 1 VP 2 No No Yes Yes …
View Full Document
Unlocking...