操作系统英文教材课件第9章

1、9.1X.J.Lee 2017Operating Systems9.2X.J.Lee 2017Operating SystemsCHAPTER OBJECTIVESnTo describe the benefits of a systemnTo explain the concepts of , , and nTo discuss the principle of the model9.3X.J.Lee 2017Operating SystemsChapter 9: Virtual Memory背景背景请求式分页请求式分页页替换页替换帧分配帧分配抖动抖动9.4X.J.Lee 2017Opera

2、ting Systems9.1 BackgroundnIn many cases, the entire program is not needed. 在许多情况下，（加载）整个程序是没必要的在许多情况下，（加载）整个程序是没必要的nThe ability to execute a program that is only partially in memory would confer many benefits: 允许程序部分加载即可运行会有许多好处：允许程序部分加载即可运行会有许多好处：A program would no longer be constrained by the amo

3、unt of physical memory.More programs could be run at the same time, with a corresponding increase in CPU utilization and throughput.Less I/O would be needed to load or swap each user program into memory, so each user program would run faster.9.5X.J.Lee 2017Operating SystemsnVirtual memory separation

4、 of user logical memory from physical memory. 虚拟存储虚拟存储用户逻辑存储与物理存储分离用户逻辑存储与物理存储分离 （部分加载部分加载+ +交换交换）Only part of the program needs to be in memory for execution. 仅部分程序必须在内存，以使其运行仅部分程序必须在内存，以使其运行Logical address space can therefore be much larger than physical address space. 从而逻辑地址空间远大于物理地址空间从而逻辑地址空间远大于

5、物理地址空间Allows address spaces to be shared by several processes. 允许地址空间被多个进程共享允许地址空间被多个进程共享Allows for more efficient process creation. 允许更有效的进程创建允许更有效的进程创建9.6X.J.Lee 2017Operating SystemsnVirtual memory can be implemented via:Demand paging 请求式分页请求式分页Demand segmentation 请求式分段请求式分段However, segment-repla

6、cement algorithms are more complex than are page-replacement algorithms because the segments have variable sizes.但是，段的替换算法比页替换算法复杂，因为段的大小不同但是，段的替换算法比页替换算法复杂，因为段的大小不同paged segmentation 段页式段页式9.7X.J.Lee 2017Operating Systems9.8X.J.Lee 2017Operating Systems9.2 Demand Paging 请求式分页9.9X.J.Lee 2017Operatin

7、g SystemsnA demand-paging system is similar to a paging system with swapping. 请求式分页系统类似于请求式分页系统类似于分页系统对换分页系统对换But we use a lazy swapperpager (页调度程序页调度程序)nSwapper vs Pagerpager never swaps a page into memory unless that page will be needed.swapper manipulates entire processes.9.10X.J.Lee 2017Operatin

8、g SystemsBasic Concepts 基本概念nBring a page into memory only when it is needed. 仅仅当必需的当必需的时时候加候加载载一个一个页页面面Less I/O neededLess memory needed Faster responseMore usersnPage is needed reference to itinvalid reference abortnot-in-memory bring to memory9.11X.J.Lee 2017Operating SystemsnValid-Invalid Bit 有效

9、位有效位“valid” the associated page is both legal and in memory.“invalid” the page either is not valid(that is ,not in the logical address space of the process),or is valid but is currently on the disk.9.12X.J.Lee 2017Operating SystemsInitially validinvalid bit is set to 0 on all entries.During address

10、translation, if validinvalid bit in page table entry is 0 page fault .1111000Frame #valid-invalid bitpage table9.13X.J.Lee 2017Operating SystemsPage Table When Some Pages Are Not in Main Memory9.14X.J.Lee 2017Operating SystemsnPage Fault 缺缺页页If there is ever a reference to a page, first reference wi

11、ll trap to OS page fault对一个页面的首次访问将自陷到操作系统缺页对一个页面的首次访问将自陷到操作系统缺页9.15X.J.Lee 2017Operating SystemsOS checks an internal table to decide: OS 检查内置页表以确定检查内置页表以确定Invalid reference abort(terminate the process).Valid,Just not in memory page it in.Get empty frame. 获取空闲帧获取空闲帧Swap page into frame. 对换页面到该帧对换页面

12、到该帧Reset tables, validation bit = 1. 重置页表，有效位置重置页表，有效位置1Restart instruction 重启指令重启指令9.16X.J.Lee 2017Operating SystemsSteps in Handling a Page Fault9.17X.J.Lee 2017Operating SystemsnPure demand paging 纯请求式分页纯请求式分页Never bring a page into memory until it is required.对于任何一个页面，仅当必需时才加载到内存对于任何一个页面，仅当必需时才加

13、载到内存9.18X.J.Lee 2017Operating SystemsnTheoretically, some programs may access several new pages of memory with each instruction execution 理论上，某些程序每次执行指令可能访问多个理论上，某些程序每次执行指令可能访问多个新新内存页内存页one page for the instruction and many for data一个指令页，多个数据页一个指令页，多个数据页possibly causing multiple page faults per inst

14、ruction.每条指令可能引起多个也错误每条指令可能引起多个也错误Fortunately, programs tend to have locality of reference幸运的是，程序倾向于访问幸运的是，程序倾向于访问9.19X.J.Lee 2017Operating SystemsnThe hardware to support demand paging请请求式分求式分页页的硬件支持的硬件支持Page table 页表页表valid-invalid bit, protection bits 有效位、保护位有效位、保护位Secondary memory 辅存辅存swap space

15、 对换空间对换空间9.20X.J.Lee 2017Operating SystemsnWhat happens if there is no free frame?Page replacement 页页替替换换find some page in memory, but not really in use, swap it out.寻找内存中某些并未真正使用中的页面，将其对换出去寻找内存中某些并未真正使用中的页面，将其对换出去Algorithm 算法算法Performance 性能性能want an algorithm which will result in minimum number of

16、 page faults.寻求一种算法：该算法导致最小的缺页数寻求一种算法：该算法导致最小的缺页数9.21X.J.Lee 2017Operating SystemsSame page may be brought into memory several times.同一页面可能会多次被加载到内存同一页面可能会多次被加载到内存9.22X.J.Lee 2017Operating SystemsPerformance of Demand Paging请求式分页的性能nPage Fault Rate 0 p 1.0if p = 0 no page faults if p = 1, every refe

17、rence is a fault9.23X.J.Lee 2017Operating SystemsnEffective Access Time (EAT) 有效有效访问时间访问时间EAT = (1 p) x ma + p x Page-fault service timeMathe memory access time, now ranges from 10 to 200 nanoseconds.Page-fault service timepage fault overhead + swap page out + swap page in + restart overhead9.24X.J.

18、Lee 2017Operating SystemsnExampleMemory access time = 100 nanosecondsAn average page-fault service time=25 millisecondsEAT(in nanoseconds) = (1 p) x ma + p x Page-fault service time = (1 p) x 100 + p x 25,000,000 =100+24,999,900 x p The EAT is directly proportional to the page-fault rate.If we want

19、less than 10-percent degradation,we needx p x p p total memory size9.66X.J.Lee 2017Operating SystemsLocality In A Memory-Reference Pattern9.67X.J.Lee 2017Operating SystemsWorking-Set Model 工作集模型nworking-set window working-set window a fixed number of page references Example: 10,000 instructionWorkin

20、g-set model9.68X.J.Lee 2017Operating Systemsnworking setWSi (working set of Process Pi) =total number of pages referenced in the most recent (varies in time)if too small will not encompass entire locality.if too large will encompass several localities.if = will encompass entire program.nD = WSSi total demand frames if D m ThrashingPolicy: if D m, then suspend one of the processes.9.69X.J.Lee 2017Operating SystemsPage-Fault Fr