Virtual Memory Topics CPE 631 Memory Electrical and Computer Engineering University of Alabama in Huntsville Aleksandar Milenkovic milenka ece uah edu http www ece uah edu milenka Why virtual memory Virtual to physical address translation Page Table Translation Lookaside Buffer TLB AM 2 LaCASA Another View of Memory Hierarchy Why Virtual Memory Upper Level Regs Instructions Operands Cache Thus far Next Virtual Memory AM Blocks L2 Cache 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 Blocks Memory Pages Disk Files Tape LaCASA Faster AM Larger Lower Level 3 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 1 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 Mapping Virtual to Physical Memory Virtual Memory 0 sum of the memory of many jobs greater than physical memory allows each job to exceed the size of physical mem 4 KB 8 KB 12 KB Allows available physical memory to be very well utilized Exploits memory hierarchy to keep average access time low Memory Physical or Real Address More on terminology AM LaCASA 20 KB C 24 KB 6 L1 Cache Parameter address of word in physical memory Memory mapping or address translation A Comparing the 2 levels of hierarchy collection of such addresses 12 KB 16 KB 28 KB address used by the programmer CPU produces virtual addresses Virtual Address Space B 8 KB LaCASA Virtual Address 0 4 KB D Virtual Memory Terminology Physical Memory A B C D Disk AM 5 LaCASA Program with 4 pages A B C D Any chunk of Virtual Memory assigned to any chuck of Physical Memory page 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 process of virtual to physical address translation Address Mapping AM Replacement Page or Segment Block Page Fault or Address Fault Miss Write Policy 7 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 2 Paging vs Segmentation Pros and Cons Paging vs Segmentation Two classes of virtual memory Page 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 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 balance access time and transfer time Not always small segments transfer few bytes Data Paging AM Segment Words per address AM Segmentation 9 LaCASA 10 LaCASA 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 Virtual Memory Mapping Function Virtual Address Physical memory incl caches 31 10 9 Virtual Page No 0 Offset translation Physical Address 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 AM LaCASA 10 9 0 Phys Page No Offset Use table lookup Page Table for mappings Virtual Page number is index Virtual Memory Mapping Function 11 29 Physical Offset Virtual Offset Physical Page Number P P N or Page frame PageTable Virtual Page Number 12 3 Address Mapping Page Table Virtual Address virtual page no Page Table offset Page Table Valid Access Rights Physical Page Number Page Table Base Reg index into Page Table AM 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 physical page no offset 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 Physical Address 13 LaCASA 14 LaCASA Page Table Entry PTE Format Valid bit indicates if page is in memory LaCASA Not enough physical memory OS maps to disk if Not Valid V 0 Contains mappings for every possible virtual page Page Table AM Virtual Memory Problem 1 V A R P P T Valid Access Rights Physical Page Number V A R P P T P T E Spatial Locality to the rescue AM If valid also check if have permission to use page Access Rights A R may be Read Only Read Write Executable 15 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 4 VM Problem 2 Fast Address Translation AM Typical TLB Format 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 Virtual Addr AM 17 LaCASA Processor VA TLB Lookup miss Cache miss 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 Main Memory hit Data Translation AM AM LaCASA Ref TLB Translation Steps TLBs usually small typically 128 256 entries Like any other cache the TLB can