15 213 The course that gives CMU its Zip Virtual Memory October 14 2008 Topics Address spaces Motivations for virtual memory Address translation Accelerating translation with TLBs lecture 14 ppt Announcements Autolab outage 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 2 as always there was a time gap between last backup and the breakin 15 213 S 08 Byte Oriented Memory Organization 0 00 F FF 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 Run Time System Control Allocation Where different program objects should be stored All allocation within single virtual address space 3 From class02 ppt 15 213 S 08 Simple Addressing Modes Normal R Mem Reg R Register R specifies memory address movl ecx eax Displacement D R Mem Reg R D Register R specifies start of memory region Constant displacement D specifies offset movl 8 ebp edx 4 From class04 ppt 15 213 S 08 Lets think on this physical memory 0 00 How does everything fit F FF 32 bit addresses 4 000 000 000 4 billion bytes 64 bit addresses 16 000 000 000 000 000 000 16 quintillion bytes How to decide which memory to use in your program How about after a fork What if another process stores data into your memory 5 How could you debug your program 15 213 S 08 So we add a level of indirection 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 appears to be a full sized private memory range surprisingly it also fixes making everything fit Implementation translate addresses transparently add a mapping function to map private addresses to physical addresses do the mapping on every load or store This mapping trick is the heart of virtual memory 6 15 213 S 08 Address Spaces A linear address space is an ordered set of contiguous nonnegative integer addresses 0 1 2 3 A virtual address space is a set of N 2n virtual addresses 0 1 2 N 1 A physical address space is a set of M 2m for convenience physical addresses 0 1 2 M 1 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 A System Using Physical Addressing CPU Physical address PA 4 Main memory 0 1 2 3 4 5 6 7 8 M 1 Data word Used by many embedded microcontrollers in devices like cars elevators and digital picture frames 8 15 213 S 08 A System Using Virtual Addressing Main memory CPU chip CPU Virtual address VA Address translation MMU Physical address PA 4100 4 0 1 2 3 4 5 6 7 M 1 Data word One of the great ideas in computer science 9 used by all modern desktop and laptop microprocessors 15 213 S 08 Why Virtual Memory 1 VM allows efficient use of limited main memory RAM 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 3 VM isolates address spaces One process can t interfere with another s memory User process cannot access privileged information 10 because they operate in different address spaces different sections of address spaces have different permissions 15 213 S 08 1 VM as a Tool for Caching Virtual memory is an array of N contiguous bytes think of the array as being stored on disk The contents of the array on disk are cached in physical memory DRAM cache Virtual memory VP 0 VP 1 VP 2n p 1 Unallocated Cached Uncached Unallocated Cached Uncached Cached Uncached 0 0 Empty Empty PP 0 PP 1 Empty N 1 Virtual pages VP s stored on disk 11 Physical memory M 1 PP 2m p 1 Physical pages PP s cached in DRAM 15 213 S 08 DRAM Cache Organization DRAM cache organization driven by the enormous miss penalty DRAM is about 10x slower than SRAM Disk is about 100 000x slower than a DRAM to get first byte though fast for next byte DRAM cache properties Large page block size typically 4 8 KB Fully associative Any virtual page can be placed in any physical page Requires a large mapping function different from CPU caches Highly sophisticated replacement algorithms 12 Too complicated and open ended to be implemented in hardware Write back rather than write through 15 213 S 08 Reminder MMU checks the cache Main memory CPU chip CPU Virtual address VA Address translation MMU Physical address PA 4100 4 0 1 2 3 4 5 6 7 M 1 Data word One of the great ideas in computer science 13 used by all modern desktop and laptop microprocessors 15 213 S 08 How Page Tables A page table is an array of page table entries PTEs that maps virtual pages to physical pages 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 null 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 14 VP 7 15 213 S 08 Address Translation with a Page Table VIRTUAL ADDRESS Page table base register PTBR n 1 p p 1 Virtual page number VPN Valid Virtual page offset VPO Physical page number PPN Page table The VPN acts as index into the page table If valid 0 then page not in memory page fault 0 m 1 p p 1 Physical page number PPN 0 Physical page offset PPO PHYSICAL ADDRESS 15 15 213 S 08 Page Hits A page hit is a reference to a VM word that is in physical main memory Physical page Virtual address number or Valid disk address null PTE 0 0 1 1 0 1 0 0 PTE 7 1 null 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 16 VP 7 15 213 S 08 Page Faults A page fault is caused by a reference to a VM word that is not in physical main memory Example An instruction references a word contained in VP …
View Full Document
Unlocking...