CPS110: Page replacementReplacementReview of replacement algorithmsSlide 4LRULRU approximationsSlide 7ClockSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Paging outSlide 16Slide 17Slide 18Hardware page table infoMMU algorithmHardware page table entriesSlide 22Slide 23Application’s perspectiveGeneral idea for Project 2CPS110: Page replacementLandon CoxReplacementThink of physical memory as a cacheWhat happens on a cache miss?Page faultMust decide what to evictGoal: reduce number of missesReview of replacement algorithms1. RandomEasy implementation, not great results2. FIFO (first in, first out)Replace “oldest” page (that came in longest ago)Popular pages often come in earlyProblem: doesn’t consider last time used3. OPT (optimal)Replace the page that won’t be needed for longest timeProblem: requires knowledge of the futureReview of replacement algorithmsLRU (least-recently used)Use past references to predict futureEvict “coldest” pageExploit “temporal locality”Problem: expensive to implement exactlyWhy?Either have to keep sorted listOr maintain time stamps + scan on evictionUpdate info on every access (ugh)LRULRU is just an approximation of OPTCould try approximating LRU insteadDon’t have to replace coldest pageJust replace a cold pageLRU approximationsClock algorithm, or FIFO-second-chanceWhat can the hardware give us?“Reference bit” for each PTESet each time page is accessedWhy is this done in hardware?May be slow to do in softwareLRU approximationsClock algorithm, or FIFO-second-chanceWhat can the hardware give us?“Reference bit” for each PTESet each time page is accessedWhat do “cold” pages look like to OS?Clear all bitsCheck later to which are setClockTime 0: clear reference bit for page...Time t: examine reference bitSplits pages into two classesThose that have been touched latelyThose that haven’t been touched latelyClearing all bits simultaneously is slowSample them to spread work out over timeClockBBAACCDDEEPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVP= Resident virtual pagesPhysical page 0Physical page 0Physical page 1Physical page 1Physical page 2Physical page 2Physical page 3Physical page 3Physical page 4Physical page 4ClockBBAACCDDEEPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPWhen you need to evict a page:Physical page 0Physical page 0Physical page 1Physical page 1Physical page 2Physical page 2Physical page 3Physical page 3Physical page 4Physical page 41) Check physical page pointed to by clock handClockBBAACCDDEEPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPWhen you need to evict a page:Physical page 0Physical page 0Physical page 1Physical page 1Physical page 2Physical page 2Physical page 3Physical page 3Physical page 4Physical page 42) If reference=0, page hasn’t been touched in a while. Evict.ClockBBAACCDDEEPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPWhen you need to evict a page:Physical page 0Physical page 0Physical page 1Physical page 1Physical page 2Physical page 2Physical page 3Physical page 3Physical page 4Physical page 43) If reference=1, page has been accessed since last sweep. What to do?ClockBBAACCDDEEPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPPPVPWhen you need to evict a page:Physical page 0Physical page 0Physical page 1Physical page 1Physical page 2Physical page 2Physical page 3Physical page 3Physical page 4Physical page 43) If reference=1, page has been accessed since last sweep. Set reference=0. Rotate clock hand. Try next page.ClockDoes this cause an infinite loop?No.First sweep sets all to 0, evict on next sweepWhat about new pages?Put behind clock handSet reference bit to 1Maximizes chance for page to stay in memoryPaging outWhat can we do with evicted pages?Write to backing store (e.g., disk, also known as “swap space”)When don’t you need to write to disk?Disk already has data (page is clean)Can recompute page content (zero page)Paging outWhy set the dirty bit in hardware?If set on every store, too slow for softwareWhy not write to disk on each store?Too slowBetter to defer workYou might not have to do it! (except in 110)Paging outWhen does work of writing to disk go away?If you store to the page againIf the owning process exits before evictionProject 2: other work you can deferInitializing a page with zeroesTaking faultsPaging outFaulted-in page must wait for disk writeCan we avoid this work too?Evict clean (non-dirty) pages firstWrite out (“clean”) pages during idle periodsProject 2: don’t do either of these!Hardware page table infoWhat should go in a PTE?Physical page #Physical page #ResidentResidentProtection(read/write)Protection(read/write)DirtyDirtyReferenceReferenceWhat bits does a MMU need to make access decisions?Set by OS to control translation. Checked by MMU on each access.“page frame number”PFNSet by OS. Checked by MMU on each access.Set by OS to control access. Checked by MMU on each access.R, WSet by MMU when page is modified. Used by OS to see if page is modified.Set by MMU when page is touched. Used by OS to see if page has been referenced.MMU needs to know if resident, readable, or writable.Do we really need a resident bit?No, if non-resident, set R=W=0.MMU algorithmif (VP # is invalid || non-resident || protected){ trap to OS fault handler}else{ physical page = pageTable[virtual page].physPageNum physical address = {physical page}{offset} pageTable[virtual page].referenced = 1 if (access is write) { pageTable[virtual page].dirty = 1 }} Project 2: infrastructure performs MMU functionsNote: P2 page table entry definition has no dirty/reference bitsHardware page table entriesDo PTEs need to store disk block nums?NoOnly the OS needs this (the MMU doesn’t)What per page info does OS maintain?Which virtual pages are validLocations of virtual pages on backing storeHardware page table entriesDo we really need a dirty bit?Claim: OS can emulate at a reasonable overhead.How can OS emulate the dirty bit?Keep the page read-onlyMMU will fault on a storeOS/you now know that the page is dirtyDo we need to fault on every store?No. After first store, set page writableWhen do we make it read-only again?When it’s clean (e.g. written to disk and paged in)Hardware page table entriesDo we really need a reference bit?Claim: OS can
View Full Document