6.004-17,Virtual memory: mapping, protection, contexts

MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L17 – Virtual Memory 1 6.004 – Spring 20094/9/09Virtual Memory You heard me right, kid. TERABYTES of main memory! modified 4/23/09 10:54 Quiz #3 Tomorrow! L17 – Virtual Memory 2 6.004 – Spring 20094/9/09Lessons from History… There is only one mistake that can be made in computer design that is difficultto recover from—not having enough address bits for memory addressing and memory management. Gordon Bell and Bill Strecker speaking about the PDP-11 in 1976 A partial list of successful machines that eventually starved to death for lack of address bits includes the PDP 8, PDP 10, PDP 11, Intel 8080, Intel 8086, Intel 80186, Intel 80286, Motorola 6800, AMI 6502, Zilog Z80, Cray-1, and Cray X-MP. Hennessy & PattersonWhy? Address size determines minimum width of anything that can hold an address: PC, registers, memory words, HW for address arithmetic (BR/JMP, LD/ST). When you run out of address space it’s time for a new ISA! L17 – Virtual Memory 3 6.004 – Spring 20094/9/09Top 10 Reasons for aBIG Address Space 10. Keeping Micron and Rambus in business.9. Unique addresses within every internet host. 8. Generating good 6.004 quiz problems.7. Performing 32-bit ADD via table lookup6.Support for meaningless advertising hype 5. Emulation of a Turing Machine’s tape.4. Bragging rights at geek parties. 3.Isolating ISA from IMPLEMENTATION•details of HW configuration shouldn’t enter into SW design 2.Usage UNCERTAINTY •provide for run-time expansion of stack and heap 1.Programming CONVENIENCE •create regions of memory with different semantics: read-only, shared, etc. •avoid annoying bookkeeping L17 – Virtual Memory 4 6.004 – Spring 20094/9/09Squandering Address Space Address Space CODE, large monolithic programs (eg, Office, Netscape).... • only small portions might be used • add-ins and plug-ins • shared libraries/DLLs •••STACK: How much to reserve? (consider RECURSION!) HEAP: N variable-size data records... Bound N? Bound Size? OBSERVATIONS: • Can’t BOUND each usage... without compromising use. • Actual use is SPARSE • Working set even MORE sparse L17 – Virtual Memory 5 6.004 – Spring 20094/9/09Extending the Memory Hierarchy So, we’ve used SMALL fast memory + BIG slow memory to fake BIG FAST memory. Can we combine RAM and DISK to fake DISK size at RAM speeds? VIRTUAL MEMORY•use of RAM as cache to much larger storage pool, on slower devices • TRANSPARENCY -VM locations "look" the same to program whether on DISK or in RAM. • ISOLATION of RAM size from software. CPUFAST STATIC"CACHE"DYNAMICRAM"MAINMEMORY"3x-20x"SecondaryStorage"DISK104x-105xL17 – Virtual Memory 6 6.004 – Spring 20094/9/09Virtual Memory ILLUSION: Huge memory (232 bytes? 264bytes?) ACTIVE USAGE: small fraction (224 bytes?) HARDWARE: • 230 (1 G) bytes of RAM • 237 (128 G) bytes of DISK... ... maybe more, maybe less! ELEMENTS OF DECEIT: • Partition memory into “Pages” (2K-4K-8K) • MAP a few to RAM, others to DISK• Keep “HOT” pages in RAM. CPURAMMMUVA PA Memory Management Unit L17 – Virtual Memory 7 6.004 – Spring 20094/9/09Demand Paging Basic idea: •Start with all of VM on DISK (“swap area”), MMU “empty” •Begin running program… each VA “mapped” to a PA Reference to RAM-resident page: RAM accessed by hardware Reference to a non-resident page: traps to software handler, which Fetches missing page from DISK into RAMAdjusts MMU to map newly-loaded virtual page directly in RAM If RAM is full, may have to replace (“swap out”) some little-used page to free up RAM for the new page. •Working set incrementally loaded, gradually evolves… “Bean – get in here immediately! And bring a mop!” L17 – Virtual Memory 8 6.004 – Spring 20094/9/09Simple Page Map Design FUNCTION: Given Virtual Address, • Map to PHYSICAL address OR• Cause PAGE FAULT allowing page replacement Virtual Page # Physical Page # Why use HIGH address bits to select page? ... LOCALITY. Keeps related data on same page. PAGEMAP XXXDRVirtual Memory Physical Memory PPNPage Index Page Map 1100110L17 – Virtual Memory 9 6.004 – Spring 20094/9/09Virtual Memory vs. Cache MAINMEMORY AMem[A]BMem[B]TAG DATA =?PAGEMAP PHYSICAL MEMORY VPAGE NO. OFFSCache: •Relatively short blocks •Few entries: scarce resource •miss time: 3x-20x hit times Virtual memory: •disk: long latency, fast xfer miss time: ~105 x hit time write-back essential! large pages in RAM •lots of entries: one for each page •tags in page map, data in physical memory L17 – Virtual Memory 10 6.004 – Spring 20094/9/09Virtual Memory: the VI-1 view PAGEMAP XXXDRVirtual Memory Physical Memory Pagemap Characteristics: • One entry per virtual page! • RESIDENT bit = 1 for pages stored in RAM, or 0 for non-resident (disk or unallocated). Page fault when R = 0. • Contains PHYSICAL page number (PPN) of each resident page • DIRTY bit says we’ve changed this page since loading it from disk (and therefore need to write it to disk when it’s replaced) 1111000PPNL17 – Virtual Memory 11 6.004 – Spring 20094/9/09Virtual Memory: the VI-3 view int VtoP(int VPageNo,int PO) { if (R[VPageNo] == 0) PageFault(VPageNo); return (PPN[VPageNo] << p) | PO; }/* Handle a missing page... */void PageFault(int VPageNo) { int i; i = SelectLRUPage(); if (D[i] == 1) WritePage(DiskAdr[i],PPN[i]); R[i] = 0; PPN[VPageNo] = PPN[i]; ReadPage(DiskAdr[VPageNo],PPN[i]); R[VPageNo] = 1; D[VPageNo] = 0; }Virtual Page # Physical Page # Problem: Translate VIRTUAL ADDRESS to PHYSICAL ADDRESS Multiply by 2P, the page size L17 – Virtual Memory 12 6.004 – Spring 20094/9/09The HW/SW Balance IDEA:•devote HARDWARE to high-traffic, performance-critical path •use (slow, cheap) SOFTWARE to handle exceptional cases HARDWARE performs address translation, detects page faults: •running program interrupted (“suspended”); •PageFault(…) is forced; •On return from PageFault; running program continues int VtoP(int VPageNo,int PO) { if (R[VPageNo] == 0)PageFault(VPageNo); return (PPN[VPageNo] << p) | PO; }/* Handle a missing page... */void PageFault(int VPageNo) { int i = SelectLRUPage(); if (D[i] == 1) WritePage(DiskAdr[i],PPN[i]); R[i] = 0; PA[VPageNo] = PPN[i]; ReadPage(DiskAdr[VPageNo],PPN[i]); R[VPageNo] = 1; D[VPageNo] = 0; }hardware software L17 – Virtual Memory 13 6.004 – Spring 20094/9/09Page Map Arithmetic PAGEMAP PHYSICAL MEMORY DRPPNVPageNo PO11101pvPPageNo POm(v + p)bits in virtual address (m + p)bits in physical address 2vnumber of VIRTUAL pages 2mnumber of PHYSICAL pages 2pbytes per physical page 2v+pbytes in virtual memory 2m+pbytes in physical memory (m+2)2vbits in the page mapTypical page size: 1K – 8K bytes Typical (v+p): 32 (or more) bits Typical (m+p): 30 – 32 bits (1G – 4G) Wait… if v equals m, why have a pagemap at all? L17 – Virtual Memory 14 6.004 – Spring 20094/9/09Example: Page Map Arithmetic Virtual Page # PhysPg # SUPPOSE...32-bit Virtual address 212 page size (4 KB) 230 RAM max (1 GB) THEN:# Physical Pages = ___________ # Virtual Pages = _____________ # Page Map Entries = _________ # Bits In pagemap = __________ Use SRAM for page map??? OUCH! 218= 256K 220220= 1M 20*22020M 011 1231011 1229122018L17 – Virtual Memory 15 6.004 – Spring 20094/9/09RAM-Resident Page Maps SMALL page maps can use dedicated RAM… gets expensive for big ones! SOLUTION: Move page map to MAIN MEMORY: Virtual Address Physical Memory virtual page number physical page number Physical memory pages that hold page map entries PROBLEM:Each memory references now takes 2 accesses to physical memory! +Page Tbl Ptr L17 – Virtual Memory 16 6.004 – Spring 20094/9/09Translation Look-aside Buffer(TLB)PROBLEM: 2x performance hit… each memory reference now takes 2 accesses! SOLUTION: CACHE the page map entries IDEA:LOCALITY in memory reference patternsSUPER locality in reference to page map VARIATIONS: •sparse page map storage •paging the page map! TLB: small, usually fully-associative cache for mapping VPNPPNVirtual Address Physical Memory virtual page number physical page number +Page Tbl Ptr TLB hit TLB miss L17 – Virtual Memory 17 6.004 – Spring 20094/9/09Example: mapping VAs to PAs Suppose •virtual memory of 232 bytes •physical memory of 224 bytes •page size is 210 (1 K) bytes 1.How many pages can be stored in physical memory at once? 2.How many entries are there in the page table? 3.How many bits are necessary per entry in the page table? (Assume each entry has PPN, resident bit, dirty bit)4.How many pages does the page table require? 5.What’s the largest fraction of VM that might be resident? 6.A portion of the page table is given to the left. What is the physical address for virtual address 0x1804?VPN | R D PPN ----+--------0 | 0 0 7 1 | 1 1 9 2 | 1 0 0 3 | 0 0 5 4 | 1 0 5 5 | 0 0 3 6 | 1 1 2 7 | 1 0 4 8 | 1 0 1 … 224-10= 21422216223 bytes = 213 pages 1/28VPN=6PPN=2PA=0x804 L17 – Virtual Memory 18 6.004 – Spring 20094/9/09ContextsAcontext is a mapping of VIRTUAL to PHYSICAL locations, as dictated by contents of the page map: PAGEMAPXXXDRVirtual MemoryPhysical MemorySeveral programs may be simultaneously loaded into main memory, each in its separate context: Virtual Memory 1Virtual Memory 2PhysicalMemory“Context switch”: reload the page map! map1map2L17 – Virtual Memory 19 6.004 – Spring 20094/9/09Contexts: A Sneak PreviewVirtual Memory 1Virtual Memory 2PhysicalMemory1. TIMESHARING among several programs --• Separate context for each program • OS loads appropriate context into pagemap when switching among pgms 2. Separate context for OS “Kernel” (eg, interrupt handlers)... • “Kernel” vs “User” contexts • Switch to Kernel context on interrupt; • Switch back on interrupt return. HARDWARE SUPPORT: 2 HW pagemaps Every application can be written as if it has access to all of memory, without considering where other applications reside. First Glimpse of a VIRTUAL MACHINE L17 – Virtual Memory 20 6.004 – Spring 20094/9/09Rapid Context Switchingphysical Virtual Address Physical Memory Context & Virtual page number physical page number +Page Tbl Ptr TLB hit TLB miss Context # Add a register to hold index of current context. To switch contexts: update Context # and Page Tbl Ptr registers. Don’t have to flush TLB since each entry’s tag includes context # in addition to virtual page number L17 – Virtual Memory 21 6.004 – Spring 20094/9/09Using Caches with Virtual Memory CACHEMMUCPUDYNAMICRAMDISKCACHEMMUCPUDYNAMICRAMDISKPhysicalCache Tags match physical addresses •Avoids stale cache data after context switch •SLOW: MMU time on HIT VirtualCache Tags match virtual addresses •Problem: cache invalid after context switch •FAST: No MMU time on HIT L17 – Virtual Memory 22 6.004 – Spring 20094/9/09Best of both worlds OBSERVATION: If cache line selection is based on unmapped page offset bits, RAM access in a physical cache can overlap page map access. Tag from cache is compared with physical page number from MMU. Want “small” cache index go with more associativity CACHECPUDYNAMICRAMMMUDISKL17 – Virtual Memory 23 6.004 – Spring 20094/9/09Alternative memory structures? Maybe we’re hung up on the simple “address space” model. Some alternatives:•Segments: named contiguous regions (Multics, x86, …) •Objects: Cons cells, arrays, … (LISP machines, 432, … … …) •URIs (web) •Triples/relations (LEAP, SAIL, RDF, …) •Associations•Etc etc etc Take a familiar model (viz, RAM). Virtualize it. All of these, and more, have been tried – with occasional success. But for the most part, we gravitate to that most venerable of Computer Science traditions: L17 – Virtual Memory 24 6.004 – Spring 20094/9/09SummaryExploiting locality on a large scale… •Programmers want a large, flat address space… … but they’ll use it sparsely, unpredictably! •Key: Demand Page sparse working set into RAM from DISK •IMPORTANT: Single-level pagemap, arithmetic, operation… Access loaded pages via fast hardware path Load virtual memory (RAM) on demand: page faults •Various optimizations… Moving pagemap to RAM, for economy & size Translation Lookaside Buffer (TLB), to regain performance Moving pagemap to DISK (or, equivalently, VM) for economy & size •Cache/VM interactions: can cache physical or virtual locations Semantic consequence: •CONTEXT: a mapping between V and P addresses – we’ll see again! Challenge: Alternative models •Will we just use bigger addresses when we outgrow our current ISAs?