操作系统原理英文版课件：Chapter 9 Virtual Memory

《操作系统原理英文版课件：Chapter 9 Virtual Memory》由会员分享，可在线阅读，更多相关《操作系统原理英文版课件：Chapter 9 Virtual Memory（81页珍藏版）》请在装配图网上搜索。

1、Chapter 9 Virtual MemorySoutheast University9.2Operating System ConceptsChapter 9:Virtual MemorynBackgroundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System ExamplesSoutheast University9.3O

2、perating System ConceptsBackgroundnVirtual memory separation of user logical memory from physical memory.uOnly part of the program needs to be in memory for execution.uLogical address space can therefore be much larger than physical address space.uMore programs can be run at the same timeuLess I/O b

3、e needed to load or swapnVirtual memory can be implemented via:uDemand paging uDemand segmentationSoutheast University9.4Operating System ConceptsVirtual Memory That is Larger Than Physical MemorySoutheast University9.5Operating System ConceptsVirtual-address SpacenUsually design logical address spa

4、ce for stack to start at Max logical address and grow“down”while heap grows“up”uMaximizes address space useuUnused address space between the two is holeNo physical memory needed until heap or stack grows to a given new pageSoutheast University9.6Operating System ConceptsChapter 9:Virtual MemorynBack

5、groundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System ExamplesSoutheast University9.7Operating System ConceptsDemand PagingnBring a page into memory only when it is needed.uLess I/O neede

6、duLess memory needed uFaster responseuMore usersnPage is needed reference to ituinvalid reference abortunot-in-memory bring to memorySoutheast University9.8Operating System ConceptsValid-Invalid BitnWith each page table entry a validinvalid bit is associated(1 in-memory,0 not-in-memory)nInitially va

7、lidinvalid bit is set to 0 on all entries.nDuring address translation,if validinvalid bit in page table entry is 0 page fault.Southeast University9.9Operating System ConceptsPage Table When Some Pages Are Not in Main MemorySoutheast University9.10Operating System ConceptsPage FaultnIf there is ever

8、a reference to a page,first reference will trap to OS page faultnOS looks at another table to decide:uInvalid reference abort.uJust not in memory.nGet empty frame.nSwap page into frame.nReset tables,validation bit=1.nRestart instructionublock moveuauto increment/decrement locationSoutheast Universit

9、y9.11Operating System ConceptsSteps in Handling a Page FaultSoutheast University9.12Operating System ConceptsPerformance of Demand PagingnExtreme case start process with no pages in memoryuOS sets instruction pointer to first instruction of process,non-memory-resident-page faultuAnd for every other

10、process pages on first accessuPure demand pagingSoutheast University9.13Operating System ConceptsPerformance of Demand PagingnPage Fault Rate 0 p 1.0uif p=0 no page faults uif p=1,every reference is a faultnEffective Access Time(EAT)EAT=(1 p)x memory access+p(page fault overhead+swap page out+swap p

11、age in+restart overhead)Southeast University9.14Performance of Demand PagingnMemory access time=200 nanosecondsnAverage page-fault service time=8 millisecondsnEAT=(1 p)x 200+p(8 milliseconds)=200+p x 7,999,800nIf one access out of 1,000 causes a page fault,then EAT=8.2 microseconds.n This is a slowd

12、own by a factor of 40!Operating System ConceptsSoutheast University9.15Performance of Demand PagingnIf want performance degradation 200+7,999,800 x p 20 7,999,800 x p p .0000025n total memory sizeSoutheast University9.51Operating System ConceptsLocality In A Memory-Reference PatternSoutheast Univers

13、ity9.52Operating System ConceptsWorking-Set Modeln working-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)uif too small will not encompass entire locality.uif too large will e

14、ncompass several localities.uif =will encompass entire program.Southeast University9.53Operating System ConceptsWorking-Set Model(Cont.)nD=WSSi total demand frames nif D m ThrashingnPolicy if D m,then suspend one of the processes.Southeast University9.54Operating System ConceptsWorking-set modelSout

15、heast University9.55Operating System ConceptsKeeping Track of the Working SetnApproximate with interval timer+a reference bitnExample:=10,000uTimer interrupts after every 5000 time units.uKeep in memory 2 bits for each page.uWhenever a timer interrupts copy and sets the values of all reference bits

16、to 0.uIf one of the bits in memory=1 page in working set.nWhy is this not completely accurate?nImprovement=10 bits and interrupt every 1000 time units.What happens when page fault occurs?Southeast University9.56Operating System ConceptsPage-Fault Frequency SchemenEstablish“acceptable”page-fault rate

17、.uIf actual rate too low,process loses frame.uIf actual rate too high,process gains frame.Southeast University9.57Operating System ConceptsChapter 9:Virtual MemorynBackgroundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOth

18、er ConsiderationsnOperating-System ExamplesSoutheast University9.58Operating System ConceptsMemory-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 memory.nA file is initially read using demand paging.A page-sized portion

19、 of the 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 calls.nAlso allows several processes to map the same file allowi

20、ng the pages in memory to be shared.Southeast University9.59Operating System ConceptsMemory Mapped FilesSoutheast University9.60Operating System ConceptsMemory-Mapped Shared Memory in WindowsSoutheast University9.61Example:linux mmapnFollowing link:uhttp:/ System ConceptsSoutheast University9.62Oper

21、ating System ConceptsChapter 9:Virtual MemorynBackgroundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System ExamplesSoutheast University9.63Operating System ConceptsAllocating Kernel MemorynT

22、reated differently from user memorynOften allocated from a free-memory pooluKernel requests memory for structures of varying sizes,fragmentation need to be taken care ofuSome kernel memory needs to be contiguousSoutheast University9.64Operating System ConceptsBuddy SystemnAllocates memory from fixed

23、-size segment consisting of physically-contiguous pagesnMemory allocated using power-of-2 allocatoruSatisfies requests in units sized as power of 2uRequest rounded up to next highest power of 2uWhen smaller allocation needed than is available,current chunk split into two buddies of next-lower power

24、of 2Continue until appropriate sized chunk availableSoutheast University9.65Operating System ConceptsBuddy System Allocator21KB kernel memory allocation requestFragmentation problemSoutheast University9.66Operating System ConceptsSlab AllocatornAlternate strategynSlab is one or more physically conti

25、guous pagesnCache consists of one or more slabsnSingle cache for each unique kernel data structureuEach cache filled with objects instantiations of the data structureSoutheast University9.67Operating System ConceptsSlab Allocator(Cont)nWhen cache created,filled with objects marked as freenWhen struc

26、tures stored,objects marked as usednIf slab is full of used objects,next object allocated from empty slabuIf no empty slabs,new slab allocatednBenefits include no fragmentation,fast memory request satisfactionSoutheast University9.68Operating System ConceptsSlab AllocationSoutheast University9.69Sla

27、b AllocationnFor example process descriptor is of type struct task_structuApprox 1.7KB of memoryuNew task-allocate new struct from cacheuWill use existing free struct task_structnSlab can be in three possible statesuFull all useduEmpty all freeuPartial mix of free and usednUpon request,slab allocato

28、ruUses free struct in partial slabuIf none,takes one from empty slabuIf no empty slab,create new emptyOperating System ConceptsSoutheast University9.70Operating System ConceptsChapter 9:Virtual MemorynBackgroundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapp

29、ed FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System ExamplesSoutheast University9.71Operating System ConceptsOther Issues-PrepagingnPrepaging uTo reduce the large number of page faults that occurs at process startupuPrepage all or some of the pages a process will need,before they

30、 are referenced(work set model)uBut if prepaged pages are unused,I/O and memory was wasteduAssume s pages are prepaged and of the pages is usedIs cost of s*save pages faults or than the cost of prepaging s*(1-)unnecessary pages?near zero prepaging loses Southeast University9.72Operating System Conce

31、ptsOther Issues Page SizenPage size selection must take into consideration:uFragmentation(?)utable size(?)uI/O overhead(?)uLocality(?)Southeast University9.73Operating System ConceptsOther Issues TLB Reach nTLB Reach-The amount of memory accessible from the TLBnTLB Reach=(TLB Size)X(Page Size)nIdeal

32、ly,the working set of each process is stored in the TLBuOtherwise there is a high degree of page faultsnIncrease the Page SizenProvide Multiple Page SizesuThis allows applications that require larger page sizes the opportunity to use them without an increase in fragmentationSoutheast University9.74O

33、perating System ConceptsOther Issues Program StructurenProgram structureuint A=new int10241024;uEach row is stored in one page uProgram 1 for(j=0;j A.length;j+)for(i=0;i A.length;i+)Ai,j=0;1024 x 1024 page faults uProgram 2 for(i=0;i A.length;i+)for(j=0;j A.length;j+)Ai,j=0;u1024 page faultsSoutheas

34、t University9.75Operating System ConceptsChapter 9:Virtual MemorynBackgroundnDemand PagingnCopy-on-WritenPage ReplacementnAllocation of Frames nThrashingnMemory-Mapped FilesnAllocating Kernel MemorynOther ConsiderationsnOperating-System ExamplesSoutheast University9.76Operating System ConceptsOperat

35、ing System ExamplesnWindows XPnSolaris Southeast University9.77Operating System ConceptsWindows XPnUses demand paging 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

36、 of pages the process is guaranteed to have in memorySoutheast University9.78Operating System ConceptsWindows XP(Cont)nA process may be assigned as many pages up to its working set maximumnWhen the amount of free memory in the system falls below a threshold,automatic working set trimming is performe

37、d to restore the amount of free memorynWorking set trimming removes pages from processes that have pages in excess of their working set minimumSoutheast University9.79Operating System ConceptsSolaris nMaintains a list of free pages to assign faulting processesnLotsfree threshold parameter(amount of

38、free memory)to begin pagingnDesfree threshold parameter to increasing pagingnMinfree threshold parameter to being swappingSoutheast University9.80Operating System ConceptsSolaris(Cont)nPaging 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 availableSoutheast University9.81Operating System ConceptsSolaris 2 Page Scanner