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 SinghWed, Nov 30, 2005Wed, Nov 30, 2005Topic: Topic: Virtual MemoryVirtual Memory2OutlineOutlineIntroductionIntroductionAddress TranslationAddress TranslationVM OrganizationVM OrganizationExamplesExamplesReading: 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 No4AddressingAddressingAlways a “congruence mapping”Always a “congruence mapping”Assume Assume 4GB VM composed of 24GB VM composed of 22020 4KB pages 4KB pages64MB 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 existEach is either in main memory or on diskEach is either in main memory or on diskCan 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 TranslationRPN = 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 MMMMFully 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 framesSimplest 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 faultAssume that PTE size is 4 bytesAssume that PTE size is 4 bytesThen whole table requires 4Then whole table requires 4222020 = 4MB of main = 4MB of main memorymemoryDisadvantage: 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 VMVMTo avoid tying down 4MB of physical memoryTo avoid tying down 4MB of physical memoryPut page tables in VMPut page tables in VMBring 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 4MBSlows 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 MMMMAnother solution to storage problemAnother solution to storage problemBreak 20-bit VPN into two 10-bit partsBreak 20-bit VPN into two 10-bit partsVPN = (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 faultStorage situation much improvedStorage situation much improvedAlways 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 nodesAllocated on demandAllocated on demandCan be anywhere in main memoryCan be anywhere in main memoryAccess time to PTE has doubledAccess time to PTE has doubled9Inverted Page TablesInverted Page TablesVirtual 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 spacesspacesless-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 significantIdeal (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 memoryNeed 4Need 416K = 64KB of main memory to store this ideal 16K = 64KB of main memory to store this ideal page tablepage tableStorage overhead = 0.1%Storage overhead = 0.1%Inverted page tableInverted page table implementations are implementations are approximations to this ideal page tableapproximations to
View Full Document