4.4Pagereplacementalgorithms

《4.4Pagereplacementalgorithms》由会员分享，可在线阅读，更多相关《4.4Pagereplacementalgorithms（28页珍藏版）》请在装配图网上搜索。

1、14.4 Page replacement algorithms2Page replacement algorithmsAlso seen in:lCPU cachelWeb server cache of web pageslBuffered I/O(file)caches3Optimal page replacementPage fault occurs.Scan all pages currently in memory.Determine which page wont be needed(referenced)until furthest in the future.Replace

2、that page.Not really possible.(But useful as a benchmark.)Depends on code as well as data.4Algorithms we will discuss:OptimalNRUFIFOSecond chanceClockLRUNFUAgingWorking setWSClock5NRU(not recently used)Bits set by hardware after every memory referenceCleared only by software(OS)R bits set when page

3、is referenced(read or write)M bits set when page is modified(written)Periodically(after k clock interrupts),R bits are cleared6NRU page categoriesNot referenced,not modifiedNot referenced,modified(only occurs when#4s R bit is cleared during clock interrupt)Referenced,not modifiedReferenced,modifiedN

4、RU algorithm:remove random page from lowest numbered non empty category7NRU algorithm evaluationSimpleEfficientNot optimal but adequate8FIFO page replacementQueue pages as they are requested.Remove page at head(front)of queue.lOldest page is removed first+simple/efficient-might remove a heavily used

5、 page9Second chance page replacementInspect R bit of oldest pagelRecall:R bits are set when page is referenced(read or write);periodically(after k clock interrupts),R bits are cleared.lIf R=0 then page is old&unused so replace itlElse Clear R bit Move page from head to tail of FIFO(treating it as a

6、newly loaded page)Try a different page10Second chance page replacementload timepage11Clock page replacementCircular list instead of queueClock hand points to oldest pageIf(R=0)thenlPage is unused so replace itElselClear RlAdvance clock hand(very similar to second chance queue instead of list)12Clock

7、 page replacement13LRU(least recently used)page replacementA page recently used is likely to be used in the near future.A page not used in ages is not likely to be used in the near future.Algorithm:l“age”the pages Maintain a queue of pages in memory.Recently used at front;oldest at rear.Every time a

8、 page is referenced,it is removed from the queue and placed at the front of the queue.This is slow!14LRU in hardwareImplementation#1:l64 bit counter,C,incremented after every instructionlEach page also has a 64 bit counterlWhen a page is referenced,C is copied to its counter.lPage with lowest counte

9、r is oldest.15LRU in hardwareImplementation#2:lGiven n page frames,let M be a nxn matrix of bits initially all 0.lReference to page frame k occurs.lSet all bits in row k of M to 1.lSet all bits in column k of M to 0.lRow with lowest binary value is least recently used.16LRU in hardware:implementatio

10、n#2 exampleoldest17NFU(Not Frequently Used)Hardware doesnt often support LRU.Software counter associated w/each page initially set to 0.At each clock interrupt:lAdd R bit(either 0 or 1)to the counter for each page.Page with lowest counter is NFU.18NFU problemIt never forgets!So pages that were frequ

11、ently referenced(during initialization for example)but are no longer needed appear to be FU.Solution(called“aging”):lShift all counters to right 1 bit before R bit is added in.lThen R bit is added to MSb(leftmost bit)instead of LSb(rightmost bit).lPage w/lowest value is chosen for removal.19NFU w/ag

12、ingShift to rightMSb=R20Differences between LRU and NFULRU updated after every instruction so its resolution is very fine.NFU is coarse(updated after n instructions execute between clock interrupts).lA given page referenced by n-1 instruction is given equal weight to a page referenced by only 1 inst

13、ruction(between clock interrupts).ln/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.21Working set page replacement algorithmDemand paging=start up processes with 0 pages and only load whats needed.Lo

14、cality of reference=during any phase of execution,the process references only a relatively small fraction of its pages.Working set=set of pages that a process is currently using.Thrashing=causing a page fault every few instructions.22Working setsWorking set model=make sure a page is in memory before

15、 the process needs it.la.k.a.prepagingw.s.=set of pages used in the k most recent memory references.23Working set algorithmUses current virtual time(CVT)=amount of CPU time a process has actually used since it started.T is a threshold on CVTR and M bits as before;clock interrupt24Working set algorit

16、hm(greatest age/least virtual time)and choose that one if no better candidate exists.age=current virtual time(i.e.,time of last use)If no suitable candidate exists,pick one at random.25WSClock page replacementPrevious WS algorithm requires entire page table be scanned at each page fault.WSClock:lSim

17、ple,efficient,widely used.lUses circular list of page frames.26WSClock page replacementAt each page faultLoop once through page table:Examine PTE pointed to by clock hand.If r bit=1 thenclear r bit;advance clock hand;goto loopelseIf agetIf page is clean then use this page!Else write dirty page to di

18、sk;advance clock hand;goto loopIf write scheduled,wait for completion and used that page.Else pick a victim at random.27WSClock page replacementclear r bit and advance clock hand.Replace old and advance.28Summary of page replacement algorithmsIn practice,random page replace typically performs better than FIFO but worse than LRU.