Announcements 15 213 Autolab outage The course that gives CMU its Zip Virtual Memory October 14 2008 Topics The autolab machine was hacked on Saturday not the autolab programs but the underlying OS rebuilt and brought back online Monday Should not block your progress on shelllab all files needed were made available on class website under docs link fish machines are working fine Re submit tshlab if you finished before the outage as always there was a time gap between last backup and the breakin Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBs 2 lecture 14 ppt 15 213 S 08 Simple Addressing Modes Byte Oriented Memory Organization 00 0 FF F Normal R Mem Reg R Mem Reg R Register R specifies memory address movl ecx eax Programs Refer to Virtual Memory Addresses Conceptually very large array of bytes Actually implemented with hierarchy of different memory types System provides address space private to particular process Program being executed Program can clobber its own data but not that of others Compiler RunRun Time System Control Allocation Displacement D R Mem Reg R D Mem Reg R D Register R specifies start of memory region Constant displacement D specifies offset movl 8 ebp edx Where different program objects should be stored All allocation within single virtual address space 3 From class02 ppt 15 213 S 08 4 From class04 ppt 15 213 S 08 1 Lets think on this physical memory 00 0 FF So we add a level of indirection F One simple trick solves all three problems Each process gets its own private image of memory This fixes how to choose and others shouldn t mess w yours Implementation translate addresses transparently How does everything fit 32 bit addresses 64 bit addresses 16 000 000 000 000 000 000 16 quintillion bytes 4 000 000 000 4 billion bytes surprisingly it also fixes making everything fit add a mapping function to map private addresses to physical addresses do the mapping on every load or store How to decide which memory to use in your program appears to be a full sized private memory range How about after a fork This mapping trick is the heart of virtual memory What if another process stores data into your memory How could you debug your program 5 15 213 S 08 Address Spaces 6 15 213 S 08 A System Using Physical Addressing A linear address space is an ordered set of contiguous nonnegative integer addresses 0 1 2 3 CPU Physical address PA 4 A virtual address space is a set of N 2n virtual addresses addresses 0 1 2 NN 1 Main memory 0 1 2 3 4 5 6 7 8 A physical address space is a set of M 2m for convenience physical addresses addresses M 1 Data word 0 1 2 MM 1 Used by many embedded microcontrollers in devices like cars elevators and digital picture frames In a system based on virtual addressing each byte of main memory has a physical address and a virtual address or more 7 15 213 S 08 8 15 213 S 08 2 Why Virtual Memory A System Using Virtual Addressing 1 VM allows efficient use of limited main memory RAM Main memory CPU chip CPU Virtual address VA Address translation MMU 4100 0 1 2 3 4 5 6 7 Physical address PA 4 Use RAM as a cache for the parts of a virtual address space some non cached parts stored on disk some unallocated non cached parts stored nowhere Keep only active areas of virtual address space in memory transfer data back and forth as needed 2 VM simplifies memory management for programmers Each process gets a full private linear address space M 1 3 VM isolates address spaces Data word used by all modern desktop and laptop microprocessors 9 One process can t interfere with another s memory User process cannot access privileged information One of the great ideas in computer science 15 213 S 08 because they operate in different address spaces different sections of address spaces have different permissions 10 15 213 S 08 1 VM as a Tool for Caching DRAM Cache Organization Virtual memory is an array of N contiguous bytes DRAM cache organization driven by the enormous miss penalty think of the array as being stored on disk The contents of the array on disk are cached in physical memory DRAM cache DRAM is about 10x slower than SRAM Disk is about 100 000x slower than a DRAM Virtual memory Physical memory DRAM cache properties 0 VP 0 VP 1 Unallocated Cached 0 Empty Uncached VP 2n p 1 Unallocated Cached Uncached Cached Uncached Large page block size typically 4 8 KB Fully associative Empty PP 2m p 1 Highly sophisticated replacement algorithms Write back rather than write through Physical pages PP s cached in DRAM 15 213 S 08 12 Any virtual page can be placed in any physical page Requires a large mapping function different from CPU caches N 1 Virtual pages VP s stored on disk 11 PP 0 PP 1 Empty M 1 to get first byte though fast for next byte Too complicated and open ended to be implemented in hardware 15 213 S 08 3 Reminder MMU checks the cache A page table is an array of page table entries PTEs that maps virtual pages to physical pages Main memory CPU chip CPU How Page Tables Address translation Virtual address VA MMU 0 1 2 3 4 5 6 7 Physical address PA 4100 4 Per process kernel data structure in DRAM Physical page number or Valid disk address null PTE 0 0 1 1 0 1 0 0 PTE 7 1 M 1 Data word Physical memory DRAM VP 1 VP 2 VP 7 VP 4 VP 1 used by all modern desktop and laptop microprocessors 13 14 p p 1 If valid 0 then page not in memory page fault Virtual page offset VPO Physical page number or Valid disk address null PTE 0 0 Physical page number PPN Page table The VPN acts as index into the page table m 1 p p 1 Physical page number PPN 1 1 0 1 0 0 PTE 7 1 null 0 Physical page offset PPO Physical memory DRAM VP 1 VP 2 VP 7 VP 4 PP 0 PP 3 Virtual memory disk VP 1 Memory resident page table DRAM VP 2 VP 3 VP 4 VP 6 PHYSICAL ADDRESS 15 15 213 S 08 A page hit is a reference to a VM word that is in physical main memory 0 Virtual address Valid VP 4 Page Hits VIRTUAL ADDRESS Virtual page number VPN VP 3 VP 7 Address Translation with a Page Table n 1 VP 2 VP 6 15 213 S 08 Page table base register PTBR PP 3 Virtual memory disk null Memory resident page table DRAM One of the great ideas in computer science PP 0 15 213 S 08 16 VP 7 15 213 S 08 4 Page Faults Handling a Page Fault A page fault is caused by a reference to a VM …
View Full Document
Unlocking...