Memory Paging and ReplacementConcepts this LectureMultilevel PagingAddressing on Two-Level Page TableMultilevel Paging and PerformanceInverted Page TableSlide 7Inverted Page Table ImplementationSlide 9Slide 10Sharing PagesShared PagesProtectionPage ProtectionIntroduction to Demand Paging - Paging PoliciesDemand PagingDemand Paging ExamplePage ReplacementIssue: EvictionTerminologyPage Replacement StrategiesPrincipal of OptimalitySummaryCS 241 Fall 2007System Programming 1Memory Paging and ReplacementLawrence Angrave2Concepts this LectureTwo-Level Paging ExampleInverted Page Table Sharing and Protection Introduction to Demand Paging3Multilevel PagingAddress of Size 4Bytes in 32-bit ArchitectureAddress of Size 4Bytes In 32-bit ArchitectureMemory Space of Size 1 Byte4Addressing on Two-Level Page Table32-bit Architecture, 4096= 2^12 Bytes Page Size4K Page of Logical Memory has 4096 addressable bytesPage the Page Table with 4K pages as well 4K Page of Page Table has 1024 addressable 4byte addresses5Multilevel Paging and PerformanceSince each level is stored as a separate table in memory, converting a logical address to a physical one with a three-level page table may take four memory accesses. Why?6Inverted Page Table7Inverted Page Table004 006005 00640101101Page TableVirtual Address (004006)Physical Address (005006)58Inverted Page Table ImplementationTLB is same as beforeTLB miss is handled by softwareIn-memory page table is managed using a hash tableNumber of entries ≥ number of physical framesNot found: page faultHash tableVirtual pagePhysical page9Inverted Page Tableone entry for each real page of memory.entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.10Inverted Page TableDecreases memory needed to store each page table, but increases time needed to search table when a page reference occurs.Use hash table to limit the search to one -- or at most a few page-table entries.11Sharing PagesCode and data can be shared by mapping them into pages with common page frame mappings.Code and data must be position independent if VM mappings for the shared data are different.12Shared Pages13ProtectionCan add read, write, execute protection bits to page table to protect memory.Check is done by hardware during access.Can give shared memory location different protections from different processes by having different page table protection access bits.14Page Protection Legend: reference - page has been accessed valid - page exists resident - page is cached in primary memory dirty - page has been changed since page in15Introduction to Demand Paging - Paging PoliciesFetch Strategies When should a page be brought into primary (main) memory from secondary (disk) storage. Placement StrategiesWhen a page is brought into primary storage, where is it to be put? Replacement StrategiesWhich page now in primary storage is to be removed from primary storage when some other page or segment is to be brought in and there is not enough room.16Demand PagingAlgorithm Never bring a page into primary memory until its needed. Page fault Check if a valid virtual memory address. Kill job if not. If valid reference, check if its cached in memory already (perhaps for some other process.) If so, skip to 7). Find a free page frame. Map address into disk block and fetch disk block into page frame. Suspend user process. When disk read finished, add vm mapping for page frame. If necessary, restart process.17Demand Paging ExampleLoad MiFree framePagetableVMreffault18Page ReplacementFind location of page on disk Find a free page frame If free page frame use it Otherwise, select a page frame using the page replacement algorithm Write the selected page to the disk and update any necessary tables Read the requested page from the disk. Restart the user process. It is necessary to be careful of synchronization problems. For example, page faults may occur for pages being paged out.19Issue: EvictionHopefully, kick out a less-useful pageDirty pages require writing, clean pages don’tHardware has a dirty bit for each page frame indicating this page has been updated or notWhere do you write? To “swap space”Goal: kick out the page that’s least usefulProblem: how do you determine utility?Heuristic: temporal locality existsKick out pages that aren’t likely to be used again20TerminologyReference string: the memory reference sequence generated by a program. Paging – moving pages to (from) diskOptimal – the best (theoretical) strategyEviction – throwing something out Pollution – bringing in useless pages/lines21Page Replacement StrategiesThe Principle of Optimality Replace the page that will not be used again the farthest time in the future. Random page replacement Choose a page randomly FIFO - First in First Out Replace the page that has been in primary memory the longest LRU - Least Recently Used Replace the page that has not been used for the longest time LFU - Least Frequently Used Replace the page that is used least often NRU - Not Recently Used An approximation to LRU. Working Set Keep in memory those pages that the process is actively using.22Principal of Optimality Description: Assume that each page can be labeled with the number of instructions that will be executed before that page is first references, i.e., we would know the future reference string for a program. Then the optimal page algorithm would choose the page with the highest label to be removed from the memory. This algorithm provides a basis for comparison with other schemes. Impractical because it needs future referencesIf future references are knownshould not use demand paging should use pre paging to allow paging to be overlapped with computation.23SummaryTwo Level PagingInverted Page TableSharing/ProtectionIntroduction to Demand Paging Fetch PoliciesReplacement PoliciesPrinciple of
View Full Document
Unlocking...