虚拟内存

1 .CS 61C: Great Ideas in Computer Architecture Lecture 23: Virtual Memory Krste Asanović & Randy H. Katz http:// inst.eecs.berkeley.edu /~ cs61c/fa17 1 Fall 2017 -- Lecture #23 11/15/17

2 .Agenda Virtual Memory Paged Physical Memory Swap Space Page Faults Hierarchical Page Tables Caching Page Table Entries (TLB) 2 Fall 2017 -- Lecture #23 11/15/17

3 .Agenda Virtual Memory Paged Physical Memory Swap Space Page Faults Hierarchical Page Tables Caching Page Table Entries (TLB) 3 Fall 2017 -- Lecture #23 11/15/17

4 .Virtual Machine 100’s of processes OS multiplexes these over available cores But what about memory? There is only one! We cannot just ”save” its contents in a context switch … 100+ Processes, managed by OS 4 Fall 2017 -- Lecture #23 11/15/17

5 .Virtual vs. Physical Addresses Processes use virtual addresses, e.g., 0 … 0xffff,ffff Many processes, all using same (conflicting) addresses Memory uses physical addresses (also, e.g., 0 ... 0xffff,ffff) Memory manager maps virtual to physical addresses Processor (& Caches) Control Datapath PC Registers (ALU) Memory (DRAM) Bytes ? Virtual Address Physical Address Many of these (software & hardware cores) One main memory 5 Fall 2017 -- Lecture #23 11/15/17

6 .Address Spaces Address space = set of addresses for all available memory locations Now , two kinds of memory addresses: Virtual Address Space S et of addresses that the user program knows about Physical Address Space S et of addresses that map to actual physical locations in memory H idden from user applications Memory manager maps between these two address spaces 6 Fall 2017 -- Lecture #23 11/15/17

7 .Conceptual Memory Manager Memory (DRAM) Concept: Real memory managers use more complex mappings. 7 Fall 2017 -- Lecture #23 11/15/17

8 .Responsibilities of Memory Manager Map virtual to physical addresses Protection: Isolate memory between processes Each process gets dedicate ”private” memory Errors in one program won’t corrupt memory of other program Prevent user programs from messing with OS’ memory Swap memory to disk Give illusion of larger memory by storing some content on disk Disk is usually much larger and slower than DRAM Use “clever” caching strategies 8 Fall 2017 -- Lecture #23 11/15/17

9 .Agenda Virtual Memory Paged Physical Memory Swap Space Hierarchical Page Tables Caching Page Table Entries (TLB) 9 Fall 2017 -- Lecture #23 11/15/17

10 .Memory Manager Several options Today “paged memory” dominates Physical memory (DRAM) is broken into pages Typical page size: 4 KiB+ page number (e.g., 20 Bits) offset (e.g., 12 Bits) Virtual address (e.g ., 32 Bits) 10 Fall 2017 -- Lecture #23 11/15/17

11 .Paged Memory Page N Page 2 Page 1 Page 0 Memory (DRAM) Page Table Page Table Page Table Each process has a dedicated page table. Physical memory non-consecutive. 11 Fall 2017 -- Lecture #23 11/15/17

12 .Paged Memory Address Translation OS keeps track of which process is active Chooses correct page table Memory manager extracts page number from virtual address Looks up page address in page table Computes physical memory address from sum of Page address and Offset (from virtual address) page table entry offset Virtual address (e.g. 32 Bits) page number offset Physical address Physical addresses may (but do not have to) have more or fewer bits than virtual addresses 12 Fall 2017 -- Lecture #23 11/15/17

13 .Protection Assigning different pages in DRAM to processes also keeps them from accessing each others memory Isolation Page tables handled by OS (in supervisory mode) Sharing is also possible OS may assign same physical page to several processes 13 Fall 2017 -- Lecture #23 11/15/17

14 .Write Protection Page N Page 2 Page 1 Page 0 Memory (DRAM) 0 0 1 Page Table 1 0 0 1 Page Table 0 Page Table Exception when writing to protected page ( e.g., program code ) W rite protected 14 Fall 2017 -- Lecture #23 11/15/17

15 .Where Do Page Tables Reside? E.g ., 32-Bit virtual address, 4-KiB pages Single page table size: 4 x 2 20 Bytes = 4-MiB 0.1% of 4-GiB memory But much too large for a cache! Store page tables in memory (DRAM) Two (slow) memory accesses per lw / sw on cache miss How could we minimize the performance penalty? Transfer blocks (not words) between DRAM and processor cache Exploit spatial locality Use a cache for frequently used page table entries … 15 Fall 2017 -- Lecture #23 11/15/17

16 .Paged Table Storage in DRAM Page Table Page Table Page Page Table Memory (DRAM) lw / sw take two memory references 16 Fall 2017 -- Lecture #23 11/15/17

17 .Blocks vs. Pages In caches, we dealt with individual blocks Usually ~64B on modern systems In VM, we deal with individual pages Usually ~4 KB on modern systems Common point of confusion: Bytes, Words, Blocks, Pages Are all just different ways of looking at memory! 17 Fall 2017 -- Lecture #23 11/15/17

18 .Bytes, Words, Blocks, Pages E.g.: 16 KiB DRAM, 4 KiB Pages (for VM), 128 B blocks (for caches), 4 B words (for lw / sw ) Page 3 Page 2 Page 1 Page 0 16 KiB Block 0 Block 31 Word 0 Word 31 1 of 1 Memory 1 of 4 Pages per Memory 1 of 32 Blocks per Page Can think of memory as: 4 Pages, or 128 Blocks, or 4096 Words, or 16,384 Bytes Can think of a page as: 32 Blocks, or 1024 Words 18 Fall 2017 -- Lecture #23 11/15/17

19 .19 Fall 2017 -- Lecture #23 11/15/17

20 .Agenda Virtual Memory Paged Physical Memory Swap Space Hierarchical Page Tables Caching Page Table Entries (TLB) 20 Fall 2017 -- Lecture #23 11/15/17

21 .Memory Hierarchy Disk Slow But huge How could we make use of its capacity (when running low on DRAM)? 21 Fall 2017 -- Lecture #23 11/15/17

22 .Aside … Why are Disks So Slow? 10,000 rpm (revolutions per minute) 6 ms per revolution Average random access time: 3 ms 22 Fall 2017 -- Lecture #23 11/15/17

23 .What About SSD? Made with transistors Nothing mechanical that turns Like “Ginormous” register file D oes not ”forget” when power is off Fast access to all locations, regardless of address Still much slower than register, DRAM Read/write blocks, not bytes Potential reliability issues 23 Fall 2017 -- Lecture #23 11/15/17

24 .Paged Memory Page N Memory (DRAM) Page Table Page Table Each process has a dedicated page table. Physical memory non-consecutive. V alid: page allocated DRAM/disk Disk 24 Fall 2017 -- Lecture #23 11/15/17

25 .Memory Access Check page table entry: Valid? Yes, valid  In DRAM? Yes, in DRAM: read/write data No, on disk: allocate new page in DRAM If out of memory, evict a page from DRAM Store evicted page to disk Read page from disk into memory Read/write data Not Valid allocate new page in DRAM If out of memory, evict a page Read/write data Page fault OS intervention 25 Fall 2017 -- Lecture #23 11/15/17

26 .Remember: Out of Memory Insufficient free memory: malloc() returns NULL $ gcc OutOfMemory.c ; ./ a.out failed to allocate > 131 TiBytes What’s going on? 26 Fall 2017 -- Lecture #23 11/15/17

27 .Write-Through or Write-Back? DRAM acts like “cache” for disk Should writes go directly to disk (write-through)? Or only when page is evicted? Which option do you propose? Implementation? 27 Fall 2017 -- Lecture #23 11/15/17

28 .Agenda Virtual Memory Paged Physical Memory Swap Space Hierarchical Page Tables Caching Page Table Entries (TLB) 28 Fall 2017 -- Lecture #23 11/15/17

29 .Size of Page Tables E.g., 32-Bit virtual address, 4-KiB pages Single page table size: 4 x 2 20 Bytes = 4-MiB 0.1% of 4-GiB memory Total size for 256 processes (each needs a page table) 256 x 4 x 2 20 Bytes = 256 x 4-MiB = 1-GiB 25% of 4-GiB memory! What about 64-bit addresses? How can we keep the size of page tables “reasonable”? 29 Fall 2017 -- Lecture #23 11/15/17