11Virtual Address TranslationUsing TLBs to Speedup Address TranslationCache recently accessed page-to-frame translations in a TLB For TLB hit, physical page number obtained in 1 cycle For TLB miss, translation is updated in TLB Has better than 99% hit ratio !! (why?)Page Table120 910p o116 910f oPhysicalAddressesVirtualAddressesCPUCPUTLBfKey Valueppf?X12Dealing With Large Page TablesMulti-level pagingAdd additional levels ofindirection to the page tableby sub-dividing page numberinto k parts Create a “tree” of pagetablesThird-LevelPage Tablesp2oVirtual AddressFirst-LevelPage Tablep3Second-LevelPage Tablesp1p1p2p313Dealing With Large Page TablesMulti-level pagingExample: Two-level pagingSecond-LevelPage Table120 1016p1o116 10f oPhysicalAddressesVirtualAddressesCPUCPUFirst-LevelPage Tablepage tablep2fp1PTBRPTBRp2++++MemoryMemory14Virtual Address TranslationUsing Page Registers (aka Inverted Page Tables)Each frame is associated with a register containing Residence bit: whether or not the frame is occupied Occupier: page number of the page occupying frame Protection bitsPage registers: an example Physical memory size: 16 MB Page size: 4096 bytes Number of frames: 4096 Space used for page registers (assuming 8 bytes/register): 32Kbytes Percentage overhead introduced by page registers: 0.2% Size of virtual memory: irrelevant15Page RegistersTradeoffsAdvantages: Size of translation table occupies a very small fraction ofphysical memory Size of translation table is independent of VM sizeDisadvantages: We have reverse of the information that we need…. How do we perform translation ? Search the translation table for the desired page number16Inverted Page TablesSearching for a Virtual PageIf the number of frames is small, the page registers can beplaced in an associative memoryVirtual page number looked up in associative memory Hit: frame number is extracted Miss: results in page faultLimitations: Large associative memories are expensive Memory expansion is non-trivial17Dealing With Large Inverted PageTablesUsing Hash TablesUse a proven fast search technique: Hash TablesHash page numbers to find corresponding frame numbers in a“frame” table with one entry per page frameh(PID, p)120 9p o116 9f oPhysicalAddressesVirtualAddressesPTBRPTBRCPUCPUHashTableHashTablePIDInverted Page Table1 0page0MemoryMemory0fmax– 1fmax– 2runningrunningPID+18Searching Inverted Page TablesUsing Hash TablesPage registers are placed in an arrayPage i is placed in frame f(i) where f is an agreed-upon“hashing function”To lookup page i, perform the following: Compute f(i) and use it as an index into the table of pageregisters Extract the corresponding page register Check if the register contains i, if so, we have a hit Otherwise, we have a miss19Searching the Inverted Page TableUsing Hash Tables (Cont’d.)Minor complication Since the number of pages is usually larger than the number ofslots in a hash table, two or more items may hash to the samelocationTwo different entries that map to same location are said tocollideMany standard techniques for dealing with collisions Use a linked list of items that hash to a particular table entry Rehash index until the key is found or an empty table entry isreached …20Virtual Memory (Paging)The bigger pictureA process’s VAS is its context Contains its code, data, and stackCode pages are stored in a user’s file on disk Some are currently residing in memory; most arenotData and stack pages are also stored in a file Although this file is typically not visible to users File only exists while a program is executingOS determines which portions of a process’sVAS are mapped in memory at any one timeCodeCodeDataDataStackStackFile System(Disk)OS/MMUPhysicalMemory21Virtual MemoryPage fault handlingReferences to non-mapped pagesgenerate a page faultProgramP’sVASDiskCPUCPUPhysicalMemoryPageTable0Resume/initiate some other processMap the missing page into memoryRestart the faulting processPage fault handling steps:Service the faultBlock the running processRead in the unmapped page22Virtual Memory PerformancePage fault handling analysisTo understand the overhead of paging, compute theeffective memory access time (EAT)EAT = memory access time × probability of a page hit + page fault service time × probability of a page faultExample: Memory access time: 20 ns Disk access time: 25 ms Let p = the probability of a page faultEAT = 20(1–p) + 25,000,000pTo realize an EAT within 5% of minimum, what is the largestvalue of p we can tolerate?23Virtual MemorySummaryPhysical and virtual memory partitioned into equalsize unitsSize of VAS unrelated to size of physical memoryVirtual pages are mapped to physical framesSimple placement strategyThere is no external fragmentationKey to good performance is minimizing page
View Full Document
Unlocking...