《operatingsystem《操作系统》ch09-virtualmemory.ppt》由会员分享，可在线阅读，更多相关《operatingsystem《操作系统》ch09-virtualmemory.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 9:Virtual Memory9.2Chapter ObjectivesnTo describe the benefits of a virtual memory systemnTo explain the concepts of demand paging,page-replacement algorithms,and allocation of page framesnTo discuss the principle of the working-set model9.3Content OverviewnBackgroundnDemand PagingnCopy-on-W
2、ritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System Examples9.49.1 BackgroundnVirtual memory separation of user logical memory from physical memory.lOnly part of the program needs to be in memory for executionlLogic
3、al address space can therefore be much larger than physical address spacelAllows address spaces to be shared by several processeslAllows for more efficient process creationnVirtual memory can be implemented via:lDemand paging lDemand segmentation9.5Virtual Memory That is Larger Than Physical MemoryV
4、irtual Memory That is Larger Than Physical Memory9.6Virtual-address Space9.7Shared Library Using Virtual Memory9.89.2 Demand PagingnBring a page into memory only when it is neededlLess I/O neededlLess memory needed lFaster responselMore usersnPage is needed reference to itlinvalid reference abortlno
5、t-in-memory bring to memorynLazy swapper never swaps a page into memory unless page will be neededlSwapper that deals with pages is a pager9.9Transfer of a Paged Memory to Contiguous Disk SpaceTransfer of a Paged Memory to Contiguous Disk Space9.10Valid-Invalid BitnWith each page table entry a valid
6、invalid bit is associated(v in-memory,i not-in-memory)nInitially validinvalid bit is set to i on all entriesnExample of a page table snapshot:nDuring address translation,if validinvalid bit in page table entry is I page faultvvvviii.Frame#valid-invalid bitpage table9.11Page Table When Some Pages Are
7、 Not in Main MemoryPage Table When Some Pages Are Not in Main Memory9.12Page FaultnIf there is a reference to a page,first reference to that page will trap to operating system:page fault1.Operating system looks at another table to decide:lInvalid reference abortlJust not in memory2.Get empty frame3.
8、Swap page into frame4.Reset tables5.Set validation bit=v6.Restart the instruction that caused the page fault9.13Page Fault(Cont.)nRestart instructionlblock movelauto increment/decrement location9.14Steps in Handling a Page Fault9.15Performance of Demand PagingnPage Fault Rate 0 p 1.0lif p=0 no page
9、faults lif p=1,every reference is a faultnEffective Access Time(EAT)EAT=(1 p)x memory access+p(page fault overhead +swap page out +swap page in +restart overhead )9.16Demand Paging ExamplenMemory access time=200 nanosecondsnAverage page-fault service time=8 millisecondsnEAT=(1 p)x 200+p(8 millisecon
10、ds)=(1 p x 200+p x 8,000,000 =200+p x 7,999,800nIf one access out of 1,000 causes a page fault,then EAT=8.2 microseconds.This is a slowdown by a factor of 40!9.17Process CreationnVirtual memory allows other benefits during process creation:-Copy-on-Write-Memory-Mapped Files(later)9.189.3 Copy-on-Wri
11、tenCopy-on-Write(COW)allows both parent and child processes to initially share the same pages in memoryIf either process modifies a shared page,only then is the page copiednCOW allows more efficient process creation as only modified pages are copiednFree pages are allocated from a pool of zeroed-out
12、 pages9.19Before Process 1 Modifies Page C9.20After Process 1 Modifies Page C9.21What happens if there is no free frame?What happens if there is no free frame?nPage replacement find some page in memory,but not really in use,swap it outlalgorithmlperformance want an algorithm which will result in min
13、imum number of page faultsnSame page may be brought into memory several times9.229.4 Page ReplacementnPrevent over-allocation of memory by modifying page-fault service routine to include page replacementnUse modify(dirty)bit to reduce overhead of page transfers only modified pages are written to dis
14、knPage replacement completes separation between logical memory and physical memory large virtual memory can be provided on a smaller physical memory9.23Need For Page Replacement9.24Basic Page Replacement1.Find the location of the desired page on disk2.Find a free frame:-If there is a free frame,use
15、it -If there is no free frame,use a page replacement algorithm to select a victim frame3.Bring the desired page into the(newly)free frame;update the page and frame tables4.Restart the process9.25Page Replacement9.26Page Replacement AlgorithmsnWant lowest page-fault ratenEvaluate algorithm by running
16、 it on a particular string of memory references(reference string)and computing the number of page faults on that stringnIn all our examples,the reference string is 1,2,3,4,1,2,5,1,2,3,4,59.27Graph of Page Faults Versus The Number of FramesGraph of Page Faults Versus The Number of Frames9.28First-In-
17、First-Out(FIFO)AlgorithmnReference string:1,2,3,4,1,2,5,1,2,3,4,5n3 frames(3 pages can be in memory at a time per process)n4 framesnBeladys Anomaly:more frames more page faults1231234125349 page faults1231235124510 page faults4439.29FIFO Page Replacement9.30FIFO Illustrating Beladys Anomaly9.31Optim
18、al AlgorithmnReplace page that will not be used for longest period of timen4 frames example 1,2,3,4,1,2,5,1,2,3,4,5nHow do you know this?nUsed for measuring how well your algorithm performs12346 page faults459.32Optimal Page Replacement9.33Least Recently Used(LRU)AlgorithmnReference string:1,2,3,4,1
19、,2,5,1,2,3,4,5nCounter implementationlEvery page entry has a counter;every time page is referenced through this entry,copy the clock into the counterlWhen a page needs to be changed,look at the counters to determine which are to change524312341254125312439.34LRU Page Replacement9.35LRU Algorithm(Con
20、t.)nStack implementation keep a stack of page numbers in a double link form:lPage referenced:4move it to the top4requires 6 pointers to be changedlNo search for replacement9.36Use Of A Stack to Record The Most Recent Page ReferencesUse Of A Stack to Record The Most Recent Page References9.37LRU Appr
21、oximation AlgorithmsnReference bitlWith each page associate a bit,initially=0lWhen page is referenced bit set to 1lReplace the one which is 0(if one exists)4We do not know the order,howevernAdditional-Reference bit4A timer4n bits Reference bits shiftnSecond chancelNeed reference bitlClock replacemen
22、tlIf page to be replaced(in clock order)has reference bit=1 then:4set reference bit 04leave page in memory4replace next page(in clock order),subject to same rules9.38Second-Chance(clock)Page-Replacement AlgorithmSecond-Chance(clock)Page-Replacement Algorithm9.39Counting AlgorithmsnKeep a counter of
23、the number of references that have been made to each pagenLFU Algorithm:replaces page with smallest countnMFU Algorithm:based on the argument that the page with the smallest count was probably just brought in and has yet to be used9.409.5 Allocation of FramesnEach process needs minimum number of pag
24、esnExample:IBM 370 6 pages to handle SS MOVE instruction:linstruction is 6 bytes,might span 2 pagesl2 pages to handle froml2 pages to handle tonTwo major allocation schemeslfixed allocationlpriority allocation9.41Fixed AllocationnEqual allocation For example,if there are 100 frames and 5 processes,g
25、ive each process 20 frames.nProportional allocation Allocate according to the size of process9.42Priority AllocationnUse a proportional allocation scheme using priorities rather than sizenIf process Pi generates a page fault,lselect for replacement one of its frameslselect for replacement a frame fr
26、om a process with lower priority number9.43Global vs.Local AllocationnGlobal replacement process selects a replacement frame from the set of all frames;one process can take a frame from anothernLocal replacement each process selects from only its own set of allocated frames9.449.6 ThrashingnIf a pro
27、cess does not have“enough”pages,the page-fault rate is very high.This leads to:llow CPU utilizationloperating system thinks that it needs to increase the degree of multiprogramminglanother process added to the systemnThrashing a process is busy swapping pages in and out9.45Thrashing(Cont.)9.46Demand
28、 Paging and Thrashing nWhy does demand paging work?Locality modellProcess migrates from one locality to anotherlLocalities may overlapnWhy does thrashing occur?size of locality total memory size9.47Locality In A Memory-Reference PatternLocality In A Memory-Reference Pattern9.48Working-Set Modeln wor
29、king-set window a fixed number of page references Example:10,000 instructionnWSSi(working set of Process Pi)=total number of pages referenced in the most recent (varies in time)lif too small will not encompass entire localitylif too large will encompass several localitieslif =will encompass entire p
30、rogramnD=WSSi total demand frames nif D m ThrashingnPolicy if D m,then suspend one of the processes9.49Working-set model9.50Keeping Track of the Working SetnApproximate with interval timer+a reference bitnExample:=10,000lTimer interrupts after every 5000 time unitslKeep in memory 2 bits for each pag
31、elWhenever a timer interrupts copy and sets the values of all reference bits to 0lIf one of the bits in memory=1 page in working setnWhy is this not completely accurate?nImprovement=10 bits and interrupt every 1000 time units9.51Page-Fault Frequency SchemenEstablish“acceptable”page-fault ratelIf act
32、ual rate too low,process loses framelIf actual rate too high,process gains frame9.529.7 Memory-Mapped FilesnMemory-mapped file I/O allows file I/O to be treated as routine memory access by mapping a disk block to a page in memorynA file is initially read using demand paging.A page-sized portion of t
33、he file is read from the file system into a physical page.Subsequent reads/writes to/from the file are treated as ordinary memory accesses.nSimplifies file access by treating file I/O through memory rather than read()write()system callsnAlso allows several processes to map the same file allowing the
34、 pages in memory to be shared9.53Memory Mapped Files9.54Memory-Mapped Shared Memory in WindowsMemory-Mapped Shared Memory in Windows9.559.8 Allocating Kernel MemorynTreated differently from user memorynOften allocated from a free-memory poollKernel requests memory for structures of varying sizeslSom
35、e kernel memory needs to be contiguous9.56Buddy SystemnAllocates memory from fixed-size segment consisting of physically-contiguous pagesnMemory allocated using power-of-2 allocatorlSatisfies requests in units sized as power of 2lRequest rounded up to next highest power of 2lWhen smaller allocation
36、needed than is available,current chunk split into two buddies of next-lower power of 24Continue until appropriate sized chunk available9.57Buddy System Allocator9.58Slab AllocatornAlternate strategynSlab is one or more physically contiguous pagesnCache consists of one or more slabsnSingle cache for
37、each unique kernel data structurelEach cache filled with objects instantiations of the data structurenWhen cache created,filled with objects marked as freenWhen structures stored,objects marked as usednIf slab is full of used objects,next object allocated from empty slablIf no empty slabs,new slab a
38、llocatednBenefits include no fragmentation,fast memory request satisfaction9.59Slab Allocation9.609.9 Other Issues-PrepagingnPrepaging lTo reduce the large number of page faults that occurs at process startuplPrepage all or some of the pages a process will need,before they are referencedlBut if prep
39、aged pages are unused,I/O and memory was wastedlAssume s pages are prepaged and of the pages is used4Is cost of s*save pages faults or than the cost of prepaging s*(1-)unnecessary pages?4 near zero prepaging loses 9.61Other Issues Page SizenPage size selection must take into consideration:lfragmenta
40、tionltable size lI/O overheadllocality9.62Other Issues TLB Reach nTLB Reach-The amount of memory accessible from the TLBnTLB Reach=(TLB Size)X(Page Size)nIdeally,the working set of each process is stored in the TLBlOtherwise there is a high degree of page faultsnIncrease the Page SizelThis may lead
41、to an increase in fragmentation as not all applications require a large page sizenProvide Multiple Page SizeslThis allows applications that require larger page sizes the opportunity to use them without an increase in fragmentation9.63Other Issues Program StructurenProgram structurelInt128,128 data;l
42、Each row is stored in one page lProgram 1 for(j=0;j 128;j+)for(i=0;i 128;i+)datai,j=0;128 x 128=16,384 page faults lProgram 2 for(i=0;i 128;i+)for(j=0;j 128;j+)datai,j=0;128 page faults9.64Other Issues I/O interlocknI/O Interlock Pages must sometimes be locked into memorynConsider I/O-Pages that are
43、 used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm9.65Reason Why Frames Used For I/O Must Be In MemoryReason Why Frames Used For I/O Must Be In Memory9.66Operating System ExamplesnWindows XPnSolaris 9.67Windows XPnUses demand paging
44、 with clustering.Clustering brings in pages surrounding the faulting page.nProcesses are assigned working set minimum and working set maximumnWorking set minimum is the minimum number of pages the process is guaranteed to have in memorynA process may be assigned as many pages up to its working set m
45、aximumnWhen the amount of free memory in the system falls below a threshold,automatic working set trimming is performed to restore the amount of free memorynWorking set trimming removes pages from processes that have pages in excess of their working set minimum9.68Solaris nMaintains a list of free p
46、ages to assign faulting processesnLotsfree threshold parameter(amount of free memory)to begin pagingnDesfree threshold parameter to increasing pagingnMinfree threshold parameter to being swappingnPaging is performed by pageout processnPageout scans pages using modified clock algorithmnScanrate is the rate at which pages are scanned.This ranges from slowscan to fastscannPageout is called more frequently depending upon the amount of free memory available9.69Solaris 2 Page ScannerEnd of Chapter 9