现代操作系统课件：Chapter3-PageRep

1、Modern Operating Systems Chapter 3 Page ReplacementZhang YangSpring 2013Content of the Lecturen3.4 Page Replacement AlgorithmsPaging PoliciesPage Replacement Algorithmsn1. OPTn2. FIFOn3. NRUn4. Second Chancen5. Clockn6. LRUn7. NFUn8. Agingn9. Working Setn10.WSClockPaging PoliciesnFetch Policy When s

2、hould a page be brought into primary (main) memory from secondary (disk) storage?nPlacement PolicyWhen a page is brought into primary storage, where is it to be put? nReplacement PolicyWhich page now in primary storage is to be removed from primary storage when some other page is to be brought in an

3、d there is not enough room?Placement PolicynDetermines where in real memory a process piece residesnFor pure segmentation systems:First-fit, next fit. are possible choices (a real issue) nFor paging (and segmentation with paging):The hardware decides where to place the page: the chosen frame locatio

4、n is irrelevant since all memory frames are equivalent (not an issue)Basic Page Replacement (1)1.Find location of page on disk 2.Find a free page frame 1)If there is a free page frame then use it 2)Otherwise, select a page frame using the page replacement algorithm 3)Write the selected page to the d

5、isk and update any necessary tables 3.Read the requested page from the disk. 4.Restart the user process. 6Basic Page Replacement (2)Issue: EvictionnHopefully, kick out a less-useful pageDirty pages require writing, clean pages dontnHardware has a dirty bit for each page frame indicating this page ha

6、s been updated or notWhere do you write? To “swap space”nGoal: kick out the page thats least usefulnProblem: how do you determine utility?Heuristic: temporal locality existsKick out pages that arent likely to be used againPage Replacement Algorithms (1)nGoal: Lowest page fault ratenEvaluate algorith

7、m by running it on a particular string of memory references (reference string)nCompute the number of page faults on that stringnMost page replacement algorithms operate on some data structure that represents physical memoryMight consist of a bitmap, one bit per physical pageMight be more involved, e

8、.g., a reference count for each page (more soon!)Free list consists of pages that are unallocatedPage Replacement Algorithms (2)nGraph of Page Faults Versus the Number of FramesPage Replacement Algorithms (3)nThe Optimal Algorithm (OPT or MIN)Selects for replacement that page for which the time to t

9、he next reference is the longest.nFirst-in First-Out (FIFO)Replace the page that has been in primary memory the longest nSecond ChanceVariant of FIFOnClockBetter implementation of second chancenNRUEnhanced second chancePage Replacement Algorithms (3)nLRUReplace the page that has not been used for th

10、e longest time nNFUSimulated LRUnAgingModified NFUnWorking Set Keep in memory those pages that the process is actively usingnWS ClockThe modified working set algorithm based on clock algorithmThe Optimal Algorithm (1)nBasic IdeaAssume that each page can be labeled with the number of instructions tha

11、t will be executed before that page is first references, i.e., we would know the future reference string for a program. Then the optimal algorithm would choose the page with the highest label to be removed from the memory. nIt can be shown that this algorithm results in the fewest number of page fau

12、lts. nThis algorithm provides a basis for comparison with other schemes. nImpractical because it needs future referencesThe Optimal Algorithm (2)nExample 12 references, 7 faultsFirst-in First-out (FIFO) (1)nReplace the page which has been in memory for the longest time nImplementation (FIFO queue)Ma

13、intain a list of allocated pagesWhen the length of the list grows to cover all of physical memory, pop first page off list and allocate itnWhy might FIFO be good?Maybe the page allocated very long ago isnt being used anymorenWhy might FIFO not be so good?Doesnt consider locality of reference!Suffers

14、 from Beladys Anomaly: Performance of an application might get worse as the size of physical memory increases!First-in First-out (2)nExample12 references, 9 faultsBeladys Anomaly (1)nBelady discovered more page frames might not always have fewer page faults. This is called Beladys anomaly. nA paging

15、 system can be characterized by three itemsThe reference string (pages referenced over time) of the executing processThe page replacement algorithmThe number of page frames available in memoryBeladys Anomaly (2)nExample12 references, 10 faultsAs the number of page frames increase, so does the fault

16、rate. The Second Chance Algorithm(1)nVariant of FIFO nOnly use one reference bit in the page table entry0 initially 1 When a page is referencednChoose “victim” to evictSelect head of FIFOIf the page has reference bit set, then nIts reference bit is cleared, and its arrival time is reset to the curre

17、nt time. nIt is put onto the end of the list of pages.Select next page in FIFO listKeep processing until reach page with zero reference bit and page that one outThe Second Chance Algorithm(2) Figure 3-15. Operation of second chance. (a) Pages sorted in FIFO order. (b) Page list if a page fault occur

18、s at time 20 and A has its R bit set. The numbers above the pages are their load times.The Clock Algorithm (1) nBetter implementation of second chanceThe Clock Algorithm (2) nImplementation: circular queueThe Clock Algorithm (3) nExample A page fault occurs, because page 727 is currently not in main

19、 memory.The Clock Algorithm (4) nExample (ctd.)0The Clock Algorithm (5) nExample (ctd.)00The Clock Algorithm (6) nExample (ctd.)Not-Recently-Used (NRU) (1)nEnhanced second chancenReplace the page which is not used recentlynUse the referenced (R) & modified (M) bits in the page table entryR bit i

20、s set when the page is referenced (read or written)M bit is set when the page is modified (contents changed - written)Not-Recently-Used (NRU) (2)nInitially, all pages haveReferenced Bit = 0Modified Bit = 0nPeriodically (e.g. whenever a timer interrupt occurs) clear the referenced bitCant clear modif

21、ied bit: needed to indicate which pages need to be flushed to disk nCategorize each page.Class 0:Referenced = 0Modified = 0Class 1:Referenced = 0Modified = 1Class 2:Referenced = 1Modified = 0Class 3:Referenced = 1Modified = 1Not-Recently-Used (NRU) (3)nAlgorithm: remove a page from the lowest non-em

22、pty classSelect a page at random from that class nRandomly choose a victim page from class 0 why?nIf none, randomly choose a page from class 1 why?nIf none, randomly choose a page from class 2 why?nIf none, randomly choose a page from class 3 why?Not-Recently-Used (NRU) (4)nImplementationHardwarenR

23、& M bits are set by hardware on every memory referenceSoftwarenR & M bits in the page table entry is modified at page faultsnEasy to understand and implementnPerformance adequate (though not optimal)Least Recently Used (LRU) (1)nApproximate OPT under certain assumptionsnBased on principal of

24、 “Locality of Reference”A page that has been used in the near past is likely to be used in the near future. nReplace the page which has been unused for the longest timeKeep track of when pages are referenced to make a better decisionUse past behavior to predict future behaviornLRU uses past informat

25、ion, while OPT uses future informationLeast Recently Used (LRU) (2)nExample12 references, 10 faultsnQuestion: When does LRU work well, and when does it not?LRU Issues (1)nDoes not suffer from Beladys anomaly (also OPT)12 references, 8 faults nQuestion: Anomalies cannot occur, why?LRU Issues (2)nCan

26、be done but very expensive. But how can we implement this?nImplementation #1 (Software)Keep a linked list of all pagesOn every memory reference, move that page to the front of the listThe page at the tail of the list is replaced“on every memory reference.”nNot feasible in softwarePage 6Page 7Page 1P

27、age 2HeadTail (LRU)LRU Issues (3)nBut how can we implement this? without requiring every access to be recorded?nImplementation #2 (Hardware)MMU (hardware) maintains a 64-bit counter CIncrement C after every memory page referenceAfter memory reference, the counter value is stored in the PTE of the pa

28、ge that was just referenced.Find page with lowest counter to evictLRU Issues (4)nImplementation #3 (Hardware)LRU hardware maintains a matrix of n x n bits for a machine with n page frames. n When page frame K is referenced: (i) Set row K to all 1s. (ii) Set column K to all 0s.n The row whose binary

29、value is smallest is the LRU page.nExample: see figure 3-17nFew computers have the necessary hardware to implement full LRULinked-list method impractical in hardwareCounter-based method could be done, but its slow to find the desired pagenWhat if we dont have hardware support?Software simulatedFigur

30、e 3-17 LRU using a matrix pages referenced in order 0,1,2,3,2,1,0,3,2,3Least Recently Used Issues (5)Not Frequently Used (NFU) (1)nSimulated LRUnThere is a software counter for each page. At each clock interrupt , the OS looks at each pageIf the Reference Bit is setnAdd the R bit to a software count

31、er for each page & clear the bit. If the Reference Bit is not setnAdd the R bit to a software counter for each pagenRemove page with lowest counter valueNot Frequently Used (NFU) (2)nProblemSome page may be heavily usednIts counter is largeThe programs behavior changesnNow, this page is not used

32、 ever again (or only rarely)This algorithm never forgets!nThis page will never be chosen for replacement!Not Frequently Used (NFU) (3)nDifferences between LRU and NFU LRU updated after every instruction so its resolution is very fine.NFU is coarse (updated after n instructions execute between clock

33、interrupts).nA given page referenced by n-1 instruction is given equal weight to a page referenced by only 1 instruction (between clock interrupts).nn/2 references to a given page at the beginning of the interval are given equal weight with n/2 references to another page at the end of the interval.T

34、he Aging Algorithm (1)nModified NFU: NFU + forgettingnTake NFU butnAt each clock interruptRight shift the counters (divide by 2)Add the R bit to the left (MSB)nAs for NFU remove pages with lowest counternNote: this is different from LRU since the time granularity is a clock tick and not every memory

35、 reference!The Aging Algorithm (2)nThe aging algorithm simulates LRU in softwarenNote 6 pages for 5 clock ticks, (a) (e)Fetch PolicynWhen should a page be loaded into main memory?nDemand PagingPages are loaded on demand, not in advanceProcess starts up with none of its pages loaded in memory; page f

36、aults load pages into memorynPre-pagingLoad pages before process runsNeed a working set of pages to load on context switchesnFew systems use pure demand paging, but instead, does pre-pagingThrashing (1)nThrashing a process is busy swapping pages in and out. (spends more time paging than executing)nW

37、hy Thrashing?Too few page frames allocated to a process!Thrashing (2)nResults of ThrashingIf a process does not have “enough” pages, the page-fault rate is very high. This leads to:nLow CPU utilizationnOperating system thinks that it needs to increase the degree of multiprogrammingnAnother process a

38、dded to the systembringing more processes Solutions to ThrashingnApproach 1Working SetnProvide a process as many frames as it needsnApproach 2Page Fault Frequency (discussed later)nWorking SetA processs working set is the set of pages that it currently “needs”. (Dennings)Example (next page) Working

39、Set Example (1)nProgram ExecutionStart with main program (page 8)Main program loads the main loop (pages 4,5,6,7)Program executes in the main loop for 20 secondsThen routine 1 is called (page 1) which executes 2 secondsFinally routine 2 (pages 2, 3) is called to execute for 3 seconds12356784Routine

40、2Routine 1Main programMain loopWorking Set Example(2)nIn the previous example, the process needs pages 4, 5, 6, 7 for most of the time (20 seconds in a total of 25 seconds execution time)nIf these pages are kept in memory the number of page faults will decrease. Otherwise, thrashing may occurnRule:

41、Do not run a process if its working set can not be kept in memory Working Set Model(1)nThe working set is the set of pages used by the k most recent memory referencesnw(k,t) is the size of the working set at time tw(k, t) is a monotonically nondecreasing fucntion of k.The limit of w(k, t) is finitek

42、Working Set Model (2)nWhen a process first starts up, its working set growsnThen stabilizes by the principle of localitynGrows again when the process shifts to a new locality (transition period)Up to a point where the working set contains pages from two localitiesnThen decreases (stabilizes) after i

43、t settles in the new localityWorking Set Model(3)Working set sizetransition stableSum of both tWorking Set Model(4)n or k: working set window= a fixed number of page references, e.g. 1000 instructionsnApproximate working setThe set of pages of a process used in the last t secondsThe Working Set Algo

44、rithm (1)nBasic IdeaWhen a page fault occurs, find a page that is not in the working set and evict it.Working set: the set of pages used in the k most recent memory referencesnApproximationDrop the idea of counting back k memory references and use execution time.Current Virtual Time: The amount of C

45、PU time a process has actually used since it started is called its current virtual time.The working set of a process is the set of pages it has referenced during the past seconds of virtual time.The Working Set Algorithm (2)nWS algorithm in practiceOn each clock tick, clear all R bits and record pro

46、cess virtual time tWhen looking for eviction candidates, scan all pages of process in physical memorynIf R = 1Store t in LTU (last time used) of PTE and clear RnIf R = 0 If (t LTU) WS_Interval (i.e., w), evict the page (because it is not in working set)nElse select page with the largest differencePage ps age is the diff between the process virtual time and the time of ps last referenceThe Working Set Algorithm (3)nExample age = current virtual time time of la