操作系统英文教学课件：Chapter 9 Virtual Memory

1、9.2Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nBackgroundnDemand Paging, herenCopy-on-Write, herenPage Replacement, herenAllocation of Frames, here nThrashing, here9.3Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nTo

2、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.4Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nInstruction

3、s must be loaded into memory before execution.nSolutions in chapter 8:lProgram entire Physical memorynSometimes, jobs may be too big or too many. How to expand the main memory?lPhysically? COST TOO HIGH!lLogically?9.5Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2

4、005nVirtual memory: Why and How?lSome code may get no, or only little, opportunity of execution,4for example, code for error handlerslSome data may get no opportunity of accesslLocality of reference (程序的局部性原理), 1968, Denning4Temporal locality (时间局部性)4Spatial locality (空间局部性)lIdea: partly loading (部分

5、装入)、demand loading(按需装入)、replacement (置换)9.6Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nVirtual Memory (虚拟存储器)l是指具有请求调度功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统lLogical size:4从系统角度看：内存容量外存容量4从进程角度看：地址总线宽度范围内；内存容量外存容量lSpeed: close to main memorylCost per bit: close to

6、secondary storage (disks)9.7Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nThe virtual address space of a process refers to the logical (or virtual) view of how a process is stored in memory.lTypically: 0 xxx & exist in contiguous memorynIn fact, the physical

7、memory are organized(partitioned) in page frames & the page frames assigned to a process may not be contiguousMMU9.8Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nVirtual memory separation of user logical memory from physical memory.lOnly part of the program n

8、eeds to be in memory for executionlLogical address space can therefore be much larger than physical address space9.9Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005lAllows address spaces to be shared by several processeslAllows for more efficient process creatio

9、n9.10Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nVirtual memory can be implemented by some ways, for example :lDemand paging lDemand segmentation9.11Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nDo not load the entir

10、e program in physical memory at program execution time.nWhen Page is needed reference to itlinvalid reference abortlnot-in-memory bring to memorynBring a page into memory only when it is neededlLess I/O neededlLess memory needed lFaster responselMore users9.12Silberschatz, Galvin and Gagne 2005Opera

11、ting System Concepts 7th Edition, Feb 22, 2005nSwapper VS. PagerlA swapper manipulates the entire processeslLazy swapperNever swaps a page into memory unless the page will be neededSwapper that deals with individual pages is a pager9.13Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th

12、 Edition, Feb 22, 2005nWith each page table entry, a validinvalid bit is associated(v in-memory, i not-in-memory)nExample of a page table snapshot:vvvviii.Frame #valid-invalid bitpage table9.14Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nInitially validinval

13、id bit is set to i on all entriesnDuring address translation, if validinvalid bit in page table entry is i page fault9.15Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 20059.16Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nIf

14、 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.Swap page into frame4.Reset tables5.Set validation bit = v6.Restart the instruction

15、 that caused the page fault9.17Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 20059.18Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nContext save (保存现场) Before OS handling the page fault, the state of the process must be save

16、dlExample: record its register values, PCnContext restore (恢复现场) The saved state allows the process to be resumed from the line where it was interrupted.nNOTE: distinguish the following 2 situationlIllegal referenceThe process is terminatedlPage faultLoad in or pager in9.19Silberschatz, Galvin and G

17、agne 2005Operating System Concepts 7th Edition, Feb 22, 2005nPage replacement find some page in memory, but not really in use, swap it out.lalgorithmlperformance want an algorithm which will result in minimum number of page faults.nSame page may be brought into memory several times.9.20Silberschatz,

18、 Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nPage Fault Rate 0 p 1.0lif p = 0 no page 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.21Silber

19、schatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nMemory access time = 200 nanosecondsnAverage page-fault service time = 8 millisecondsnEAT = (1 p) x 200 + p (8 milliseconds) = (1 p) x 200 + p x 8,000,000 = 200 + p x 7,999,800nIf one access out of 1,000 causes a page f

20、ault, then p = 0.001, EAT = 8.2 microseconds. n This is a slowdown by a factor of ( 8.2 microseconds /200 nanoseconds) =40!9.22Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nIf we want performance degradation 10%, thenEAT = 200 + p * 7, 999, 800 200 (1 + 10%)

21、= 220p * 7, 999, 800 20 p total memory size9.56Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 20059.57Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nThe working-set model is based on the assumption of locality.n working-set w

22、indow a fixed number of page references Example: 10,000 instructionnWorking set (工作集):lThe set of pages in the most recent page references.lAn approximation of the programs locality.9.58Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nWorking set size:lWSSi(work

23、ing set of Process Pi) = total number of pages referenced in the most recent lVaries in time, depend on the selection of 41. if too small will not encompass entire locality42. if too large will encompass several localities43. if = will encompass entire program9.59Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22, 2005nFor all processes in the system, currentlylD = WSSi total demand frames nif D m ThrashingnPolicy if D m, then suspend one of the processes9.60Silberschatz, Galvin and Gagne 2005Operating System Concepts 7th Edition, Feb 22