CS 241 Fall 2007System Programming1Memory Paging and ReplacementLawrence Angrave2Concepts this LectureTwo-Level Paging ExampleInverted Page TableSharing and ProtectionIntroduction to Demand Paging3Multilevel PagingAddress of Size 4Bytes in32-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 inmemory, converting a logical address to aphysical one with a three-level page table maytake 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 pagestored in that real memory location, withinformation about the process that owns thatpage.10Inverted Page TableDecreases memory needed to store each pagetable, but increases time needed to searchtable when a page reference occurs.Use hash table to limit the search to one -- or atmost a few page-table entries.11Sharing PagesCode and data can be shared by mapping theminto pages with common page frame mappings.Code and data must be position independent if VMmappings for the shared data are different.12Shared Pages13ProtectionCan add read, write, execute protection bits to page tableto protect memory.Check is done by hardware during access.Can give shared memory location different protections fromdifferent processes by having different page tableprotection access bits.14Page ProtectionLegend: 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 - PagingPoliciesFetch StrategiesWhen should a page be brought into primary (main)memory from secondary (disk) storage.Placement StrategiesWhen a page is brought into primary storage, where isit to be put?Replacement StrategiesWhich page now in primary storage is to be removedfrom primary storage when some other page orsegment is to be brought in and there is not enoughroom.16Demand PagingAlgorithm Never bring a page into primary memory until its needed.Page faultCheck if a valid virtual memory address. Kill job if not.If valid reference, check if its cached in memory already (perhapsfor 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 diskFind a free page frameIf free page frame use itOtherwise, select a page frame using the page replacementalgorithmWrite the selected page to the disk and update any necessarytablesRead 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 beingpaged 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 hasbeen 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 referencesequence generated by a program.Paging – moving pages to (from) diskOptimal – the best (theoretical) strategyEviction – throwing something outPollution – bringing in useless pages/lines21Page Replacement StrategiesThe Principle of OptimalityReplace the page that will not be used again the farthest time in thefuture.Random page replacementChoose a page randomlyFIFO - First in First OutReplace the page that has been in primary memory the longestLRU - Least Recently UsedReplace the page that has not been used for the longest timeLFU - Least Frequently UsedReplace the page that is used least oftenNRU - Not Recently UsedAn approximation to LRU.Working SetKeep in memory those pages that the process is actively using.22Principal of OptimalityDescription:Assume that each page can be labeled with the number ofinstructions that will be executed before that page is firstreferences, i.e., we would know the future reference string fora program.Then the optimal page algorithm would choose the page with thehighest label to be removed from the memory.This algorithm provides a basis for comparison with otherschemes.Impractical because it needs future referencesIf future references are knownshould not use demand pagingshould use pre paging to allow paging to be overlapped withcomputation.23SummaryTwo Level PagingInverted Page TableSharing/ProtectionIntroduction to Demand PagingFetch PoliciesReplacement PoliciesPrinciple of
View Full Document