Memory HardwareCS241 AdministrativeVinton Cerf Lecture, April 11, 11am, 1404 SCConcepts this LecturePaging Hardware - RegistersPaging - Caching the Page TablePaging Implementation IssuesPage Mapping HardwarePage Mapping HardwarePage Mapping HardwareTranslation Lookaside Buffer (TLB)TLB FunctionEffective Access TimeMultilevel Page TablesMultilevel Page TablesMultilevel PagingExample Addressing on a Multilevel Page Table SystemAddressing on Multilevel Page TableSummaryCS 241 Spring 2007System Programming1Memory HardwareLecture 30Klara Nahrstedt2CS241 Administrative Read Stallings Chapter 7 and 8 about Memory Management and VM LMP2 is on (Deadline April 16, but Part I has deadline April 9)3Vinton Cerf Lecture, April 11, 11am, 1404 SCDistinguished Lecture Series in Computer ScienceWednesday, April 1111:00am, 1404 SiebelDr. Vinton Cerf, Chief Internet Evangelist and VP at GoogleDr. Cerf is widely known as one of the founders of the Internet and as the co-designer of the TCP/IP protocol, the communications protocol that gave birth to the Internet and that is commonly used today. This talk will be more technical in nature than the Arnold O. Beckman Lecture that Dr. Cerf will deliver on Tuesday, April 10th, at 4pm in Foellinger. Computer Science faculty and students are encouraged to attend both talks.4Concepts this LecturePaging Hardware TLBMulti-Level PagingTwo-Level Paging Example5Paging Hardware - RegistersCan put page table in registers (small page table < 256).Registers must be changed at context switch.6Paging - Caching the Page TableCan cache page table in registers and keep page table in memory at location given by a page table base register.Page table base register changed at context switch time.7Paging Implementation IssuesCaching scheme can use associative registers, look-aside memory or content-addressable memory- TLB.Page address cache (TLB) hit ratio: percentage of time page found in associative memory. If not found in associative memory, must load from page tables: requires additional memory reference.8Page Mapping HardwareP DF DP-> F0101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)PAssociative Look UpP FFirst9Page Mapping Hardware004 006009 006004-> 0090101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)4Associative Look Up1 127193637FirstTable organized byLRU4 910Page Mapping Hardware004 006009 006004-> 0090101101Page TableVirtual Memory Address (P,D)Physical Address (F,D)4Associative Look Up1 124193937FirstTable organized byLRU11Translation Lookaside Buffer (TLB)offsetVirtual address...PPage#...PPage#...PPage#...PPage # offsetPhysical addressVPage #TLBHitMissRealpagetableVPage#VPage#VPage#12TLB FunctionIf a virtual address is presented to MMU, the hardware checks TLB by comparing all entries simultaneously (in parallel). If match is valid, the page is taken from TLB without going through page table. If match is not validMMU 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.13Effective Access TimeAssociative lookup time = ε time unit.Memory cycle -- m microsecond.Hit ratio -- α.Effective access time Eat = (1m+ε)α+(2m+ε)(1-α)Eat = 2m+ε-α.14Multilevel Page TablesSince the page table can be very large, one solution is to page the page tableDivide the page number into An index into a page table of second level page tablesA page within a second level page tableAdvantageNo need to keeping all the page tables in memory all the timeOnly recently accessed memory’s mapping need to be kept in memory, the rest can be fetched on demand15Multilevel Page TablesDirectory...pte.........dir table offsetVirtual addressWhat does this buy us? Sparse address spaces and easier paging16Multilevel Paging17Example Addressing on a Multilevel Page Table SystemA logical address (on 32-bit x86 with 4k page size) is divided into A page number consisting of 20 bitsA page offset consisting of 12 bits Divide the page number into A 10-bit page numberA 10-bit page offset18Addressing on Multilevel Page Table19SummaryPaging HardwareTLBMulti-level Paging Two Level
View Full Document