CS241 System ProgrammingMemory Management (III)ContentAdministrativeTranslation Lookaside Buffer (TLB)TLB FunctionPage Mapping HardwarePage Mapping ExamplePage Mapping Example: next referenceBits in a TLB EntryPaging Implementation IssuesSoftware-Controlled TLBIssuesEffective Access TimeSummaryCS241 System ProgrammingMemory Management (III)Klara NahrstedtLecture 304/7/20064/7/2006CS 241 - System Programming, Klara Nahrstedt2Content z Paging Implementation z TLB – Translation Look-aside Bufferz Inverted Page Tables4/7/2006CS 241 - System Programming, Klara Nahrstedt3Administrative z MP4 is posted, due April 17, 2006z Quiz 8 is April 7, 2006Translation Lookaside Buffer (TLB)offsetVirtual address...PPage#...PPage#...PPage#...PPage # offsetVPage #TLBHitMissRealpagetableVPage#VPage#VPage#Physical addressTLB Functionz If a virtual address is presented to MMU, the hardware checks TLB by comparing all entries simultaneously (in parallel). z If match is valid, the page is taken from TLB without going through page table. z If match is not valid– MMU detects miss and does an ordinary page table lookup.– It then evicts one page out of TLB and replaces it with the new entry, so that next time that page is found in TLB.Page Mapping HardwareP DF DP→F0101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)PAssociative LookupP FFirstPage Mapping Example004 006009 006004→0090101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)4Associative Lookup1 127193637FirstTable organized byLRU4 9Page Mapping Example: next reference004 006009 006004→0090101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)4Associative Lookup1 124193937FirstTable organized byLRUBits in a TLB Entryz Common (necessary) bits– Virtual page number: match with the virtual address– Physical page number: translated address– Valid– Access bits: kernel and user (nil, read, write)z Optional (useful) bits– Process tag– Reference– Modify– Cacheablez Includes parts of PTE– Example: x86virtual pagePaging Implementation Issuesz TLB can be implemented using– Associative registers– Look-aside memory – Content-addressable memoryz TLB hit ratio (Page address cache hit ratio)– Percentage of time page translation found in associative memorySoftware-Controlled TLBz On a miss in TLB, VM software– Write back if there is no free entry– Check if the page containing the PTE is in memory– If no, perform page fault handling– Load the PTE into the TLB– Restart the faulting instructionz On a hit in TLB, the hardware checks valid bit– If valid, pointer to page frame in memory– If invalid, the hardware generates a page faultz Perform page fault handlingz Restart the faulting instructionzExample: SPARC, MIPS, Alpha, HP-PA, IA-64, PowerPCIssuesz What TLB entry to be replaced?– Random– Pseudo Least Recently Used (LRU)z What happens on a context switch?– Process tag: change TLB registers and process register– No process tag: Invalidate the entire TLB contentsz What happens when changing a page table entry?– Change the entry in memory– Invalidate the TLB entryEffective Access Timez TLB lookup time = ε time unitz Memory cycle = m µsz TLB Hit ratio = αz Effective access time (Eat)– Eat = (m + ε)α+ (2m + ε)(1 – α)– Eat = 2m + ε – mα4/7/2006CS 241 - System Programming, Klara Nahrstedt14Summary z TLB allows for rapid mapping of virtual addresses to physical addresses without going through the page table z TLB management possible in
View Full Document