COMP 206: Computer Architecture and ImplementationOutlineCharacteristicsAddressingAddress TranslationSingle-Level, Direct Page Table in MMSingle-Level Direct Page Table in VMMulti-Level Direct Page Table in MMInverted Page TablesTranslation Lookaside Buffer (TLB)TLB MissesDirty Bits and TLB: Two SolutionsVirtual Memory Access TimeVirtual Memory Access Time (2)Virtual Memory Access Time (3)Page SizeSegmentation and PagingExample 1: Alpha 21264 TLBExample 2: Hypothetical Virtual Mem1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghMon., Nov. 17, 2003Mon., Nov. 17, 2003Topic: Topic: Virtual MemoryVirtual Memory2OutlineOutlineIntroductionIntroductionAddress TranslationAddress TranslationVM OrganizationVM OrganizationExamplesExamplesReading: HP3 Section 5.10 Reading: HP3 Section 5.10 For background: Refer to PH (Comp. Org.)For background: Refer to PH (Comp. Org.)3CharacteristicsCharacteristicsCache-MM MM-diskAccess time ratio ("speed gap") 1:5 - 1:15 1:10000 - 1:1000000Hit time 1-2 cycles 40-100 cyclesHit ratio 0.90-0.99 0.99999-0.9999999Miss (page fault) ratio 0.01-0.10 0.00000001-0.000001Miss penalty 10-100 cycles 1M-6M cyclesCPU during block transfer blocking/non-blocking task switchingBlock (page) size 16-128 bytes 4Kbytes - 64KbytesImplemented in hardware hardware + softwareMapping Direct or set-associative Page table ("fully associative")Replacement algorithm Not crucial Very important (LRU)Write policy Many choices Write backDirect access to slow memory Yes No4AddressingAddressingAlways a congruence mappingAlways a congruence mappingAssume Assume 4GB VM composed of 24GB VM composed of 22020 4KB pages 4KB pages64MB DRAM main memory composed of 16384 page frames (of 64MB DRAM main memory composed of 16384 page frames (of same size)same size)Only those pages (of the 2Only those pages (of the 22020) that are not empty actually exist) that are not empty actually existEach is either in main memory or on diskEach is either in main memory or on diskCan be located with two mappings (implemented with tables)Can be located with two mappings (implemented with tables)Virtual address = (virtual page number, page offset)VA = (VPN, offset)32 bits = (20 bits + 12 bits)Physical address = (real page number, page offset)PA = (RPN, offset)26 bits = (14 bits + 12 bits)5Address TranslationAddress TranslationRPN = fRPN = fMM(VPN)(VPN)In reality, VPN is mapped to a page table entry (PTE)In reality, VPN is mapped to a page table entry (PTE)which contains RPN …which contains RPN …… … as well as miscellaneous control information (e.g., valid bit, as well as miscellaneous control information (e.g., valid bit, dirty bit, replacement information, access control)dirty bit, replacement information, access control)VA  PA(VPN, offset within page)  (RPN, offset within page)VA  disk address6Single-Level, Direct Page Table in Single-Level, Direct Page Table in MMMMFully associative mapping:Fully associative mapping:when VM page is brought in from disk to MM, it may when VM page is brought in from disk to MM, it may go into any of the real page framesgo into any of the real page framesSimplest addressing scheme: one-level, direct Simplest addressing scheme: one-level, direct page tablepage table(page table base address + VPN) = PTE or page fault(page table base address + VPN) = PTE or page faultAssume that PTE size is 4 bytesAssume that PTE size is 4 bytesThen whole table requires 4Then whole table requires 4222020 = 4MB of main = 4MB of main memorymemoryDisadvantage: 4MB of main memory must be Disadvantage: 4MB of main memory must be reserved for page tables, even when the VM reserved for page tables, even when the VM space is almost emptyspace is almost empty7Single-Level Direct Page Table in Single-Level Direct Page Table in VMVMTo avoid tying down 4MB of physical memoryTo avoid tying down 4MB of physical memoryPut page tables in VMPut page tables in VMBring into MM only those that are actually neededBring into MM only those that are actually needed““Paging the page tables”Paging the page tables”Needs only 1K PTEs in main memory, rather Needs only 1K PTEs in main memory, rather than 4MBthan 4MBSlows down access to VM pages by possibly Slows down access to VM pages by possibly needing disk accesses for the PTEsneeding disk accesses for the PTEs8Multi-Level Direct Page Table in Multi-Level Direct Page Table in MMMMAnother solution to storage problemAnother solution to storage problemBreak 20-bit VPN into two 10-bit partsBreak 20-bit VPN into two 10-bit partsVPN = (VPN1, VPN2)VPN = (VPN1, VPN2)This turns original one-level page table into a This turns original one-level page table into a tree structuretree structure(1st level base address + VPN1) = 2nd level base (1st level base address + VPN1) = 2nd level base addressaddress(2nd level base address + VPN2) = PTE or page fault(2nd level base address + VPN2) = PTE or page faultStorage situation much improvedStorage situation much improvedAlways need root node (1K 4-byte entries = 1 VM page)Always need root node (1K 4-byte entries = 1 VM page)Ned only a few of the second level nodesNed only a few of the second level nodesAllocated on demandAllocated on demandCan be anywhere in main memoryCan be anywhere in main memoryAccess time to PTE has doubledAccess time to PTE has doubled9Inverted Page TablesInverted Page TablesVirtual address spaces may be vastly larger (and Virtual address spaces may be vastly larger (and more sparsely populated) than real address more sparsely populated) than real address spacesspacesless-than-full utilization of tree nodes in multi-level direct less-than-full utilization of tree nodes in multi-level direct page table becomes more significantpage table becomes more significantIdeal (i.e., smallest possible) page table would Ideal (i.e., smallest possible) page table would have one entry for every VM page actually in have one entry for every VM page actually in main memorymain memoryNeed 4Need 416K = 64KB of main memory to store this ideal 16K = 64KB of main memory to store this ideal page tablepage tableStorage overhead = 0.1%Storage overhead = 0.1%Inverted page tableInverted page table implementations are implementations are approximations to this ideal page tableapproximations to this ideal