中科大操作系统原理与实现课件9_VirtualMemory2.pdf

《中科大操作系统原理与实现课件9_VirtualMemory2.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件9_VirtualMemory2.pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统原理与设计第9章 VM（虚存2）陈香兰中国科学技术大学计算机学院2009年09月01日.提纲Page ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Page Replacement IIFree page fr

2、ame is managed by OS using free-frame-listIWhat happens if there is no free frame?IPage replacementIover-allocationIno free frames;Iall memory is in useIPrevent over-allocation of memory by modifying page-faultservice routine to include page replacementIexample:.Page Replacement II.OutlinePage Repla

3、cementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Basic Page Replacement1.Find the location of the desired page on disk2.Find a free frame:IIf

4、 there is a free frame,use itIIf there is no free frame,use a page replacement algorithm toselect a victim frame3.Bring the desired page into the(newly)free frame;update thepage and frame tables4.Restart the process.Page Replacement.INO MODIFY,NO WRITTEN(to disk/swap space)IUse modify(dirty)bit to r

5、educe overhead of page transfersIonly modified pages are written to diskIThis technique also applies to read-only pagesIfor example,pages of binary codeIPage replacement completes separation between logicalmemory and physical memoryIlarge virtual memory can be provided on a smaller physicalmemoryIde

6、mand paging,to lowest page-fault rate,two major problemsIframe-allocation algorithmsIpage-replacement algorithms.Page Replacement Algorithms IIGOAL:to lowest page-fault rateIDifferent algorithms are evaluated by running it on aparticular string of memory references(reference string)andcomputing the

7、number of page faults on that stringIA reference string isa sequence of addresses referenced by a programIExample:IAn address reference string:0100 0432 0101 0612 0102 0103 0104 0101 0611 0103 01040101 0610 0102 0103 0104 0101 0609 0102 0105IAssuming page size=100 B,then its corresponding pagerefere

8、nce string is:1 4 1 6 1 6 1 6 1 6 1.Page Replacement Algorithms IIIhow many page faults?Idetermined by the number of page frames assigned to theprocessIif 3,then only 3 page faultsIif=1,11 pages faults.Graph of Page Faults Versus The Number of Frames.IIn all our examples,the reference string is1,2,3

9、,4,1,2,5,1,2,3,4,5Ianother one is7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1.OutlinePage ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Fi

10、rst-In-First-Out(FIFO)Algorithm I1.example 12.Reference string:1,2,3,4,1,2,5,1,2,3,4,5Iif 3 frames.First-In-First-Out(FIFO)Algorithm IIIif 4 framesIBeladys(贝莱迪)Anomaly:more frames more page faults.FIFO Illustrating Beladys AnomalyImore memory,better performance?MAY BE NOT!IBeladys anomaly.OutlinePag

11、e ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Optimal AlgorithmIReplace page that will not be used for longest period of timeI4 fra

12、mes example1,2,3,4,1,2,5,1,2,3,4,5IHow do you know this?IUsed for measuring how well your algorithm performs.Optimal Page Replacement.OutlinePage ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting A

13、lgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Least Recently Used(LRU)Algorithm IIReference string:1,2,3,4,1,2,5,1,2,3,4,5.Least Recently Used(LRU)Algorithm IIHOW to implement LRU replacement?1.Counter implementationIEvery page entry has a counter;every time page is referencedthrough th

14、is entry,copy the clock into the counterIWhen a page needs to be changed,look at the counters todetermine which are to change2.Stack implementation keep a stack of page numbers in adouble link form:IPage referenced:Imove it to the topIrequires 6 pointers to be changedINo search for replacementIstack

15、 example:.Least Recently Used(LRU)Algorithm III.OutlinePage ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.LRU Approximation Algorithm

16、s IIReference bitIWith each page associate a bit,initially=0IWhen page is referenced bit set to 1IReplace the one which is 0(if one exists)IWe do not know the order,however1.Additinal-Reference-Bits AlgorithmIreference bits+time ordering,for exampleI8 bitsIHW modifies the highest bit,onlyIperiodical

17、ly,right shift the 8 bits for each pageI00000000,.,01110111,.,11000100,.,11111111.LRU Approximation Algorithms II2.Second chance AlgorithmINeed 1 reference bit,modified FIFO algorithmIFirst,a page is selected by FIFOIthen,the reference bit of the page is checked:0replace it1not replace it,get a seco

18、nd chance with reference bit:10,and timecurrentIImplementation:Clock replacementIclock order.LRU Approximation Algorithms III.LRU Approximation Algorithms IV3.Enhanced Second-Chance AlgothmIreference bit+modify bitIFour page classes（访问位，修改位）I(0,0)best page to replaceI(0,1)not quite as goodI(1,0)prob

19、ably be used again soonI(1,1)probably be used again soon,and be dirtyIReplace the first page encountered in the lowest nonemptyclass.3.1 Scan for(0,0)3.2 Scan for(0,1),&set reference bits to 03.3 Loop back to step(a).OutlinePage ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptim

20、al AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.Counting AlgorithmsIKeep a counter of the number of references that have beenmade to each pageILFU Algorithm:replaces page with smallest countIMFU Algorithm:b

21、ased on the argument that the page withthe smallest count was probably just brought in and has yet tobe used.OutlinePage ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing Al

22、gorithmsAllocation of Frames小结和作业.Page-Buffeing Algorithms IIsystem commonly keep a pool of free framesIwhen replacement occurs,two frames are involvedIa free frame from the pool is allocated to the processIthe desired page is read into the frameIa viction frame is chosenIwritten out later and the f

23、rame is added to the free poolINO NEED to write out before read inIAn expansionImaintain a list of modified pagesIwhen a paging device is idle,select a modified page,write itout,modify bit0.Page-Buffeing Algorithms IIIAnother modificationIfree frame with old pageIthe old page can be reusedIless writ

24、e out and less read inIVAX/VMSIsome UNIX:+second chanceI.Allocation of Frames.1.minimum number of pagesIEach process needs minimum number of pagesIDetermined by ISA(Instruction-Set Architecture)IWe must have enough frames to hold all the different pagesthat any single instruction can referenceIExamp

25、le:IBM 3706 pages to handle SS MOVE instruction:Iinstruction is 6 bytes,might span 2 pagesI2 pages to handle fromI2 pages to handle to2.Two major allocation schemesIfixed allocation;priority allocation3.Two replacement policyIglobal vs.local.Fixed Allocation I1.Equal allocation For example,if there

26、are 100 frames and5 processes,give each process 20 frames.frame number for any process=mnm=total memory framesn=number of processes.Fixed Allocation II2.Proportional allocation Allocate according to the size ofprocesssi=size of process piS=sim=total number of framesai=allocation for pi=siS mIexample

27、:m=64S1=10S2=127a1=10137 64 5a2=127137 64 59.Priority AllocationIUse a proportional allocation scheme using priorities ratherthan sizeIIf process Pigenerates a page fault,Iselect for replacement one of its framesIselect for replacement a frame from a process with lowerpriority number.Global vs.Local

28、 AllocationIGlobal replacement process selects a replacement framefrom the set of all frames;one process can take a frame fromanotherIproblem:a process cannot control its own page-fault rateILocal replacement each process selects from only its ownset of allocated framesIproblem?.小结Page ReplacementBasic Page ReplacementFirst-In-First-Out(FIFO)AlgorithmOptimal AlgorithmLeast Recently Used(LRU)AlgorithmLRU Approximation AlgorithmsCounting AlgorithmsPage-Buffeing AlgorithmsAllocation of Frames小结和作业.谢谢！