CPE 631 Memory Electrical and Computer Engineering University of Alabama in Huntsville Aleksandar Milenkovic milenka ece uah edu http www ece uah edu milenka Virtual Memory Topics Why virtual memory Virtual to physical address translation Page Table Translation Lookaside Buffer TLB AM LaCASA 2 Another View of Memory Hierarchy Upper Level Regs Instructions Operands Cache Thus far Next Virtual Memory AM LaCASA Faster Blocks L2 Cache Blocks Memory Pages Disk Files Tape Larger Lower Level 3 Why Virtual Memory Today computers run multiple processes each with its own address space Too expensive to dedicate a full address space worth of memory for each process Principle of Locality AM LaCASA allows caches to offer speed of cache memory with size of DRAM memory DRAM can act as a cache for secondary storage disk Virtual Memory Virtual memory divides physical memory into blocks and allocate them to different processes 4 Virtual Memory Motivation Historically virtual memory was invented when programs became too large for physical memory Allows OS to share memory and protect programs from each other main reason today Provides illusion of very large memory AM LaCASA sum of the memory of many jobs greater than physical memory allows each job to exceed the size of physical mem Allows available physical memory to be very well utilized Exploits memory hierarchy to keep average access time low 5 Mapping Virtual to Physical Memory Program with 4 pages A B C D Any chunk of Virtual Memory assigned to any chuck of Physical Memory page Virtual 0 Memory A 4 KB B 8 KB C 12 KB D AM LaCASA Disk Physical Memory 0 4 KB 8 KB D B 12 KB 16 KB A 20 KB C 24 KB 28 KB 6 Virtual Memory Terminology Virtual Address Virtual Address Space LaCASA address of word in physical memory Memory mapping or address translation AM collection of such addresses Memory Physical or Real Address address used by the programmer CPU produces virtual addresses process of virtual to physical address translation More on terminology Page or Segment Block Page Fault or Address Fault Miss 7 Comparing the 2 levels of hierarchy Parameter L1 Cache Virtual Memory Block Page 16B 128B 4KB 64KB Hit time 1 3 cc 50 150 cc Miss Penalty Access time Transfer time 8 150 cc 6 130 cc 2 20 cc 1M 10M cc Page Fault 800K 8M cc 200K 2M cc Miss Rate 0 1 10 0 00001 0 001 Placement DM or N way SA Fully associative OS allows pages to be placed anywhere in main memory Address Mapping AMReplacement Write Policy LaCASA 25 45 bit physical address to 14 20 bit cache address 32 64 bit virtual address to 2545 bit physical address LRU or Random HW cntr LRU SW controlled WB or WT WB 8 Paging vs Segmentation Two classes of virtual memory Pages fixed size blocks 4KB 64KB Segments variable size blocks 1B 64KB 4GB Hybrid approach Paged segments a segment is an integral number of pages Code AM LaCASA Data Paging Segmentation 9 Paging vs Segmentation Pros and Cons Page Segment Words per address One Two segment offset Programmer visible Invisible to AP May be visible to AP Replacing a block Trivial all blocks are the same size Hard must find contiguous variable size unused portion Memory use inefficiency Internal fragmentation unused portion of page External fragmentation unused pieces of main memory Efficient disk traffic Yes adjust page size to Not always small segments balance access time transfer few bytes and transfer time AM LaCASA 10 Virtual to Physical Addr Translation Program operates in its virtual address space AM LaCASA virtual address inst fetch load store physical HW mapping address inst fetch load store Physical memory incl caches Each program operates in its own virtual address space Each is protected from the other OS can decide where each goes in memory Combination of HW SW provides virtual physical mapping 11 Virtual Memory Mapping Function Virtual Address 31 10 9 Virtual Page No 0 Offset translation Physical Address AM LaCASA 29 10 9 0 Phys Page No Offset Use table lookup Page Table for mappings Virtual Page number is index Virtual Memory Mapping Function Physical Offset Virtual Offset Physical Page Number P P N or Page frame PageTable Virtual Page Number 12 Address Mapping Page Table Virtual Address virtual page no offset Page Table Valid Page Table Base Reg index into Page Table AM LaCASA Access Rights Physical Page Number physical page no offset Physical Address 13 Page Table A page table is an operating system structure which contains the mapping of virtual addresses to physical locations Each process running in the operating system has its own page table AM LaCASA There are several different ways all up to the operating system to keep this data around State of process is PC all registers plus page table OS changes page tables by changing contents of Page Table Base Register 14 Page Table Entry PTE Format Valid bit indicates if page is in memory OS maps to disk if Not Valid V 0 Contains mappings for every possible virtual page Page Table AM LaCASA V A R P P T Valid Access Rights Physical Page Number V A R P P T P T E If valid also check if have permission to use page Access Rights A R may be Read Only Read Write Executable 15 Virtual Memory Problem 1 Not enough physical memory Spatial Locality to the rescue AM LaCASA Only say 64 MB of physical memory N processes each 4GB of virtual memory Could have 1K virtual pages physical page Each page is 4 KB lots of nearby references No matter how big program is at any time only accessing a few pages Working Set recently used pages 16 VM Problem 2 Fast Address Translation AM LaCASA PTs are stored in main memory Every memory access logically takes at least twice as long one access to obtain physical address and second access to get the data Observation locality in pages of data must be locality in virtual addresses of those pages Remember the last translation s Address translations are kept in a special cache called Translation Look Aside Buffer or TLB TLB must be on chip its access time is comparable to cache 17 Typical TLB Format Virtual Addr AM LaCASA Physical Addr Dirty Ref Valid Access Rights Tag Portion of virtual address Data Physical Page number Dirty since use write back need to know whether or not to write page to disk when replaced Ref Used to help calculate LRU on replacement Valid Entry is valid Access rights R read permission W write perm 18 Translation Look Aside Buffers TLBs usually small typically 128 256 entries Like any other cache the TLB can be fully associative set associative or direct mapped