Background(背景)

1、Silberschatz, Galvin, and Gagne 1999 10.1Applied Operating System ConceptsModule 10: Virtual MemoryBackground（背景）背景）Demand Paging（请求页式）请求页式） Performance of Demand Paging（请求页式的性请求页式的性能）能） Page Replacement（页置换）页置换） Page-Replacement Algorithms（页置换算法）页置换算法） Allocation of Frames （页框的分配）页框的分配） Thrashing（颠

2、簸）颠簸） Other Considerations（其他考虑）其他考虑）Demand Segmenation（请求段式）请求段式）Silberschatz, Galvin, and Gagne 1999 10.2Applied Operating System ConceptsBackgroundVirtual memory separation of user logical memory from physical memory.（虚拟内存虚拟内存物理内存和用户逻辑内存的区分）物理内存和用户逻辑内存的区分） 局部性原理局部性原理(principle of locality) 时间局部性，

3、空间局部性时间局部性，空间局部性 Only part of the program needs to be in memory for execution （只有部分运行的程序需要在内存中）只有部分运行的程序需要在内存中）.Logical address space can therefore be much larger than physical address space（因此，逻辑地址空间能够比物理地址空因此，逻辑地址空间能够比物理地址空间大）间大）. Need to allow pages to be swapped in and out（必须允许必须允许页面能够被换入和换出）页面能

4、够被换入和换出）.Virtual memory can be implemented via（虚拟内存能够通过以下虚拟内存能够通过以下方法来实现）方法来实现）: Demand paging （请求页式）请求页式） Demand segmentation（请求段式）请求段式）Silberschatz, Galvin, and Gagne 1999 10.3Applied Operating System Concepts问题的提出问题的提出为了在内存空间运行超过内存总容为了在内存空间运行超过内存总容量的大作业，或者同时运行大量量的大作业，或者同时运行大量作业，解决的方法是作业，解决的方法是从逻辑

5、上扩从逻辑上扩充内存容量充内存容量，这就是虚拟存储技，这就是虚拟存储技术所要解决的主要问题术所要解决的主要问题Silberschatz, Galvin, and Gagne 1999 10.4Applied Operating System Concepts程序、数据、堆栈的大小可以超过内存的大程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换要时在内存和磁盘之间动态交换以以CPU时间时间和和外存空间外存空间换取昂贵内存空间，换

6、取昂贵内存空间，这是操作系统中的资源转换技术这是操作系统中的资源转换技术虚拟存储器的基本思想虚拟存储器的基本思想Silberschatz, Galvin, and Gagne 1999 10.5Applied Operating System Concepts虚拟存储器的基本概念虚拟存储器的基本概念局部性原理局部性原理 在一段时间内，程序的执行仅局限于某个部分；相应地，它所在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：局部性规律呢？原因可以归

7、结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。仍是顺序执行的。子程序调用子程序调用将会使程序的执行由一部分内存区域转至另一部分将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多程序中存在许多循环结构循环结构，循环体中的指令被多次执行。，循环体中的指令被多次执行。程序中还包括许多对程序中还包括许多对数据结构数据结构的处理，如对连续的存储空间的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。数

8、组的访问，往往局限于很小的范围内。Silberschatz, Galvin, and Gagne 1999 10.6Applied Operating System Concepts时间局部性时间局部性：如果程序中的某条指令一旦：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量局限性的典型原因是在程序中存在着大量的循环操作。的循环操作。空间局部性空间局部性：一旦程序访问

9、了某个存储单：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元元，则在不久的将来，其附近的存储单元也最有可能被访问。也最有可能被访问。 即程序在一段时间即程序在一段时间内所访问的地址，可能集中在一定的范围内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。内，其典型原因是程序是顺序执行的。局部性表现局部性表现Silberschatz, Galvin, and Gagne 1999 10.7Applied Operating System Concepts虚拟存储的基本原理虚拟存储的基本原理根据局部性原理，一个作业在运行之前根据局部性原理，一个作业在运行之前，没有必

10、要把全部作业装入内存，而仅，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂先装入内存便可启动运行，其余部分暂时留在磁盘上时留在磁盘上 Silberschatz, Galvin, and Gagne 1999 10.8Applied Operating System Concepts程序在运行时如果它所要访问的页程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行（段）已调入内存，便可继续执行下去；下去；如果程序所要访问的页（段）尚未如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此调入内存

11、（称为缺页或缺段），此时应利用时应利用OSOS所提供的所提供的请求调页（段请求调页（段）功能，将它们调入内存，以使进功能，将它们调入内存，以使进程能继续执行下去。程能继续执行下去。虚拟存储的基本原理虚拟存储的基本原理Silberschatz, Galvin, and Gagne 1999 10.9Applied Operating System Concepts如果内存已满，无法再装入新的页（段），如果内存已满，无法再装入新的页（段），则还须再利用页（段）的则还须再利用页（段）的置换功能置换功能，将内存，将内存中暂时不用的页（段）调出至磁盘上，腾出中暂时不用的页（段）调出至磁盘上，腾出足够的内

12、存空间后，再将所要访问的页（段足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们内存容量，将比实际内存容量大得多，人们把这样的存储器称为把这样的存储器称为虚拟存储器虚拟存储器。虚拟存储的基本原理虚拟存储的基本原理Silberschatz, Galvin, and Gag

13、ne 1999 10.10Applied Operating System Concepts虚拟存储器的特征虚拟存储器的特征l离散性离散性：指在内存分配时采用离散的分配方：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。式，它是虚拟存储器的最基本的特征。l多次性多次性：指一个作业被分成多次调入内存运：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。存即可。多次性是虚拟存储器最重要的特征。l对换性对换

14、性：指允许在作业的运行过程中在内存：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。和外存的对换区之间换进、换出。l虚拟性虚拟性：指能够从逻辑上扩充内存容量，使：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。用户所看到的内存容量远大于实际内存容量。Silberschatz, Galvin, and Gagne 1999 10.11Applied Operating System Concepts虚拟存储器实现方式虚拟存储器实现方式1)请求分页系统请求分页系统：在分页系统的基础上，增加了：在分页系统的基础上，增加了请求调页功请求调页功能和页面置换功能能和页面置

15、换功能所形成的页式虚拟存储系统。它允许所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，就只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。面置换到外存上，置换时以页面为单位。2)请求分段系统：请求分段系统：在分段系统的基础上，增加了在分段系统的基础上，增加了请求调段请求调段和分段置换功能和分段置换功能所形成的段式虚拟存储系统。它允许只所形成的

16、段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。段调出，同时调入将要运行的段，置换以段为单位。3)请求段页式系统：请求段页式系统：它是在段页式系统的基础上，增加了它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统请求调页和页面置换功能所形成的段页式虚拟存储系统。Silberschatz, Galvin, and Gagne 1999 10.12Appl

17、ied Operating System ConceptsDemand PagingBring a page into memory only when it is needed（只有只有在一个页需要的时候才把它换入内存）在一个页需要的时候才把它换入内存）. Less I/O needed（需要很少的需要很少的I/O） Less memory needed （需要很少的内存需要很少的内存） Faster response（快速响应）快速响应） More users（多用户）多用户）Hardware Support invalid reference（无效的访问）无效的访问） abort（中止中

18、止） not-in-memory（不在内存）不在内存） bring to memory（换换入内存）入内存）Silberschatz, Galvin, and Gagne 1999 10.13Applied Operating System Concepts请求分页存储管理方式请求分页存储管理方式它是在纯分页系统的基础上，增加了它是在纯分页系统的基础上，增加了请求请求调页功能调页功能、页面置换功能页面置换功能所形成的页式虚所形成的页式虚拟存储系统，它是目前常用的一种虚拟存拟存储系统，它是目前常用的一种虚拟存储器的方式。储器的方式。l取页取页-将哪部分装入内存将哪部分装入内存l置页置页-将调入的

19、页放在什么地方将调入的页放在什么地方l淘汰淘汰-内存不足时，将哪些页换出内存内存不足时，将哪些页换出内存。Silberschatz, Galvin, and Gagne 1999 10.14Applied Operating System Concepts请求分页中的硬件支持请求分页中的硬件支持1)请求分页的页表机制请求分页的页表机制 它是在纯分页的页表机制上形成的，由于只它是在纯分页的页表机制上形成的，由于只将程序的一部分调入内存，还有一部分仍在将程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程磁盘上，故需在页表中再增加若干项，供程序序(数据数据)在换进、换出时参考

20、。在请求分页系在换进、换出时参考。在请求分页系统中的每个页表项如图所示。统中的每个页表项如图所示。页号 物理块号 状态位P 访问字段A 修改位M 外存地址Silberschatz, Galvin, and Gagne 1999 10.15Applied Operating System Concepts状态位（存在位状态位（存在位P）：用于指示该页是否已调入内存，供程用于指示该页是否已调入内存，供程序访问时参考。序访问时参考。访问字段访问字段A：用于记录本页在一段时间内被访问的次数，或用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面最近已有多长时间未

21、被访问，提供给置换算法选择换出页面时参考。时参考。修改位修改位M：表示该页在调入内存后是否被修改过。由于内存表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。存上，以保证外存中所保留的始终是最新副本。外存地址外存地址：用于指出该页在外存上的地址，通常是物

22、理块号：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。，供调入该页时使用。请求分页中的硬件支持请求分页中的硬件支持Silberschatz, Galvin, and Gagne 1999 10.16Applied Operating System Concepts请求分页中的硬件支持请求分页中的硬件支持2）缺页中断机构）缺页中断机构在请求分页系统中，每当所要访问的页面不在内在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求存时，便要产生一缺页中断，请求OS将所缺页调将所缺页调入内存。与一般中断的主要区别在于：入内存。与一般中断的主要区别在于：缺页中断机构在

23、指令执行期间产生和处理中断信缺页中断机构在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理号，而一般中断在一条指令执行完后检查和处理中断信号。中断信号。缺页中断返回到该指令的开始重新执行该指令，缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可能产生多次缺页中断。Silberschatz, Galvin, and Gagne 1999 10.17Applied Operating System Concepts请求分页中的硬件支持请求分页

24、中的硬件支持3)地址变换机构地址变换机构 请求分页系统中的地址变换机构，是在分页请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页出一页的功能等等，下图给出了请求分页系统的地址变换过程。系统的地址变换过程。Silberschatz, Galvin, and Gagne 1999 10.18Applied Operating System Concepts 缺

25、页中断处理缺页中断处理 是 否 是 是 否 产生缺页中产生缺页中 否否 是 断请求调页断请求调页 开始（程序请求访问一页开始（程序请求访问一页)越界中断越界中断CPU检索快表检索快表页表项是否在快表中？页表项是否在快表中？访问页表访问页表页是否在内存中？页是否在内存中？修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址 地址变换结束地址变换结束保留保留CPU现场现场 从外存中找到缺页从外存中找到缺页 页号页号页表长度？页表长度？ 内存满否？内存满否？选择一页换出选择一页换出 该页是否被修改？该页是否被修改？ 将该页写回外存将该页写回外存 将一页从外存换入内存将一页从外

26、存换入内存 修改页表修改页表 CPU从外存读缺页从外存读缺页 启动启动I/O硬件硬件 Silberschatz, Galvin, and Gagne 1999 10.19Applied Operating System ConceptsSteps in handling a page faultLoad M 0Free frameOperatingsystemPagetable1reference6 Restart instruction5 Reset page table3 page is on backing store2 trapPhysical memory4 bring in mis

27、sing pageSilberschatz, Galvin, and Gagne 1999 10.20Applied Operating System ConceptsSteps in handling a page fault1.we check an internal table(usually kept with the process control block) for this process,to determine whether the reference was a valid or invalid memory access.2.if the reference was

28、invalid, we terminate the process. If it was valid,but we have not yet brought in that page,we now page it in.3.we find a free frame(by taking one from the free-frame list,for example)4.we schedule a disk operation to read the desired page into the newly allocated frame.5 when the disk read is compl

29、ete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory6. We restart the instruction that was interrupted by the illegal address trap.the process can now access the page as though it had always been in memorySilberschatz, Galvin, and Gagn

30、e 1999 10.21Applied Operating System ConceptsWhat 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 pag

31、e faults（找出一个导致最小缺页数的算找出一个导致最小缺页数的算法）法）.Silberschatz, Galvin, and Gagne 1999 10.22Applied Operating System Concepts页面调入策略页面调入策略 为能使进程运行，必须事先将一部分要执行的为能使进程运行，必须事先将一部分要执行的程序和数据调入内存程序和数据调入内存1)调入页面的时机调入页面的时机 预调页策略：预调页策略： 是一种主动的缺页调入策略，即将那些预计在不是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，久的将来会被访问的程序或数据所在的页面，预先

32、调入内存。由于预测的准确率不高（预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于），所以这种策略主要用于进程的首次调入进程的首次调入。有的系统将预调页策略用于请求调页，有的系统将预调页策略用于请求调页，Silberschatz, Galvin, and Gagne 1999 10.23Applied Operating System Concepts页面调入策略页面调入策略请求调页策略：请求调页策略： 是指当进程在运行中发生缺页时，就立即提是指当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策

33、略。但这种策略拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁在调页时须花费较大的系统开销，如需频繁启动磁盘启动磁盘I/O。Silberschatz, Galvin, and Gagne 1999 10.24Applied Operating System Concepts页面调入策略页面调入策略2)从何处调入页面从何处调入页面 在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区（连续分配）的磁盘，对换

34、区（连续分配）的磁盘I/O速度比文件区（离散分配）速度比文件区（离散分配）要高。要高。在在UNIX系统中，对于从未运行过的页面，都应从硬盘文件系统中，对于从未运行过的页面，都应从硬盘文件区调入；对于曾经运行过而又被换出的页面，可以从对换区区调入；对于曾经运行过而又被换出的页面，可以从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。此时就无须再从对换区调入。Silberschatz, Galvin, and Gagne 1999 10.25Applied Operating System ConceptsPe

35、rformance of Demand PagingA page fault cause the following sequence to occur: 1. Trap to the operating system 2.Save the user registers and process state 3.Determine that the interrupt was a page fault 4. Check that the page reference was legal and determine the location of the page on the disk 5.Is

36、sue a read from the disk to a free frame: a.Wait in a queue for this device until the read request is serviced. b. Wait for the devices seek and/or latency time c. Begin the transfer of the page to a free frame 6. While waiting,allocate the cpu to some other user(cpu scheduling operation) Silberscha

37、tz, Galvin, and Gagne 1999 10.26Applied Operating System ConceptsPerformance of Demand Paging7.Interrupt from the disk(I/O completed)8.Save the registers and process state for the other user(if step 6 executed)9.Determine that the interrupt was from the disk10. Correct the page table and other table

38、s to show that the desired page is now in memory11.Wait for the cpu to be allocated to this process again12. Restore the user registers,process state,and new page table,then resume the interrupted instruction.Silberschatz, Galvin, and Gagne 1999 10.27Applied Operating System ConceptsPerformance of D

39、emand Paging以上步骤并不是在任何情况下都会发生的以上步骤并不是在任何情况下都会发生的这里主要的动作是：这里主要的动作是：处理缺页中断处理缺页中断从磁盘读入所需的页从磁盘读入所需的页重新开始被中断的进程重新开始被中断的进程其中最大的一部分时间为从磁盘读入所需其中最大的一部分时间为从磁盘读入所需的页的页Silberschatz, Galvin, and Gagne 1999 10.28Applied Operating System Conceptsl假定作业假定作业Ji共有共有m页，系统分配给它的主存块页，系统分配给它的主存块为为n块，这里块，这里mn。开始时，主存没有装入任开始时，

40、主存没有装入任何一页的信息。如果作业何一页的信息。如果作业Ji在运行中成功访问在运行中成功访问的次数为的次数为S，不成功的访问次数为不成功的访问次数为F(产生缺页产生缺页中断的次数中断的次数)，则作业执行过程中总的访问次，则作业执行过程中总的访问次数为数为A.A=S（成功访问的次数）成功访问的次数）+F（不成功的访不成功的访问次数）问次数）作业作业Ji执行过程中的缺页率执行过程中的缺页率f=F/A。 缺页率缺页率Silberschatz, Galvin, and Gagne 1999 10.29Applied Operating System ConceptsPerformance of De

41、mand PagingPage Fault Rate 0 p 1.0（缺页率缺页率0 p 1.0） if p = 0 no page faults （如果如果p = 0 ，没有缺页）没有缺页） if p = 1, every reference is a fault（每次访问都缺每次访问都缺页）页）Effective Access Time (EAT)（有效存取时间）有效存取时间）EAT = (1 p) x memory access+ p (page fault overhead+ swap page out + swap page in + restart overhead)Silbers

42、chatz, Galvin, and Gagne 1999 10.30Applied Operating System ConceptsDemand Paging ExampleMemory access time = 1 microsecond （存取存取内存的时间）内存的时间）50% of the time the page that is being replaced has been modified and therefore needs to be swapped out（ 50%的时间，所置的时间，所置换的页被修改，因此需要被换出）换的页被修改，因此需要被换出）.Swap Pag

43、e Time = 10 msec （交换页的时间）交换页的时间）EAT = (1 p) x 1 + p (10) = 1 + 9P (in msec)Silberschatz, Galvin, and Gagne 1999 10.31Applied Operating System ConceptsPage ReplacementPrevent over-allocation of memory by modifying page-fault service routine to include page replacement（通过通过修改缺页服务例程，来包含页置换）修改缺页服务例程，来包含

44、页置换）.Use modify (dirty) bit to reduce overhead of page transfers only modified pages are written to disk（使使用修改（脏）位来防止页面传输过多用修改（脏）位来防止页面传输过多只有被修改的页面才只有被修改的页面才写入磁盘）写入磁盘）.Page replacement completes separation between logical memory and physical memory large virtual memory can be provided on a smaller p

45、hysical memory（页置换完善了逻辑内存和物理内存的划分页置换完善了逻辑内存和物理内存的划分在一个较小的在一个较小的物理内存基础之上可以提供一个大的虚拟内存物理内存基础之上可以提供一个大的虚拟内存.Silberschatz, Galvin, and Gagne 1999 10.32Applied Operating System ConceptsPage-Replacement AlgorithmsWant lowest page-fault rate（需要一个最需要一个最小的缺页率）小的缺页率）.Evaluate algorithm by running it on a parti

46、cular string of memory references (reference string) and computing the number of page faults on that string（通通过运行一个内存访问的特殊序列（访问序列过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数），计算这个序列的缺页次数）.Silberschatz, Galvin, and Gagne 1999 10.33Applied Operating System ConceptsPage-Replacement Algorithms在进程运行过程中，如果发生缺页，此时内存中又

47、在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行就必须从内无空闲块时，为了保证进程能正常运行就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定个页面调出，则须根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不适当。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生的算法可能会导致进程发生“抖动抖动”（Thrashing)Thrashing)。即刚被换出的页很快又被访问，需重新调入，导即刚被换出的页很快又被访问，需重新调入，导致系统频繁地更换

48、页面，以致一个进程在运行中把致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称大部分时间花费在完成页面置换的工作上，我们称该进程发生了该进程发生了“抖动抖动”（颠簸）。（颠簸）。Silberschatz, Galvin, and Gagne 1999 10.34Applied Operating System ConceptsPage-Replacement Algorithms从理论上讲，应将那些以后不再被从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。时间内不会再被访问的页面换出。

49、目前目前, ,存在多种置换算法存在多种置换算法, ,都是试图都是试图更接近理论上的目标。更接近理论上的目标。Silberschatz, Galvin, and Gagne 1999 10.35Applied Operating System ConceptsPage-Replacement Algorithms1.最佳算法最佳算法(OPT, optimal)2.最近最久未使用算法最近最久未使用算法(LRU,Least Recently Used)3.先进先出算法先进先出算法(FIFO) Belady现象现象4. LRU的的近似近似算法算法Silberschatz, Galvin, and Ga

50、gne 1999 10.36Applied Operating System Concepts页面置换算法页面置换算法 .最佳（最佳（Optimal）置换算法置换算法 它是一种理想化的算法，性能最好，但在实际上它是一种理想化的算法，性能最好，但在实际上难于实现。即难于实现。即选择那些永不使用的，或者是在最选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去长时间内不再被访问的页面置换出去。但是要确。但是要确定哪一个页面是未来最长时间内不再被访问的，定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评目前来说是很难估计的，所以该算法通常用来评价其它算法。

51、价其它算法。Silberschatz, Galvin, and Gagne 1999 10.37Applied Operating System Concepts页面置换算法页面置换算法最佳置换算法举例最佳置换算法举例例：假定系统为某进程分配了三个物理块，并考例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如如下页图所示，进程运行时先将下页图所示，进程运行时先将7，0，1三个页面装三个页面装入内存。当进程访问页面入内存。当进程访问页面2时，产生缺页中断，此时，产生缺页中断，

52、此时时OS根据根据最佳置换算法最佳置换算法，页面，页面7将在第将在第18次才被次才被访问，是三页中将最久不被访问的页面，所以被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面淘汰。接着访问页面0时，发现已在内存中，而不时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了用最佳置换算法，只发生了6次页面置换次页面置换。Silberschatz, Galvin, and Gagne 1999 10.38Applied Operating System Concepts最佳（最佳（Optimal）置换算法置换

53、算法发生了发生了6次面置换，次面置换，9次缺页中断。次缺页中断。页面 引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 7 0 0 0 0 4 0 0 0 物 理 块 1 1 3 3 3 1 1 缺页 x x x x x x x x x 置换 Silberschatz, Galvin, and Gagne 1999 10.39Applied Operating System Concepts 先进先出（先进先出（FIFOFIFO）置换算法置换算法该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法

54、实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最直观，性能最差的算法。 页 面引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 0 0 0 3 3 3 2 2 2 1 1 1 0 0 物 理块 1 1 1 0 0 0 3 3 3 2 2 2 1 缺页 x x x x x x x x x x x x x x x 发生了 12 次页面置换，缺页次数 15 次。 Silberschatz, Galvin, and Gagne 1999 10.40Appli

55、ed Operating System Concepts 先进先出（先进先出（FIFO）置换算法置换算法BELADY 异常现象：对页面访问序列 1 2 3 4 1 2 5 1 2 3 4 5 ，物理块从 3 块增加到4块，缺页次数增加。 页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 2 2 2 1 1 1 3 3 物理块 3 3 3 2 2 2 4 缺页 x x x x x x x x x 发生了6次页面置换，缺页次数9次。 页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 5 5 5 5 4 4 2 2 2 2 1 1

56、1 1 5 3 3 3 3 2 2 2 2 物理块 4 4 4 4 3 3 3 缺页 x x x x x x x x x x 发生了6次页面置换，缺页次数10次。 Silberschatz, Galvin, and Gagne 1999 10.41Applied Operating System Concepts 最近最久未使用置换算法最近最久未使用置换算法该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一 个访问 字段， 用以记 录这个页 面自上 次被访 问以来 所经历 的时 间T，当 要淘汰 一个页 面时， 选择T 最 大的页 面。但 在实现 时需要 硬件的 支持 （ 寄 存

57、器 或 栈 ） 。 利 用LRU算 法 对 上 例 进 行 页 面 置 换 的 结 果 如 下 ： 页面引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 4 4 4 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 物 理 块 1 1 3 3 2 2 2 2 2 7 缺 页 x x x x x x x x x x x x 发 生 了9次 面 置 换 ， 缺 页 次 数12次 Silberschatz, Galvin, and Gagne 1999 10.42Applied Operating System ConceptsLea

58、st Recently Used (LRU) AlgorithmCounter implementation（计数器实现）计数器实现） Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter（每一个页表项每一个页表项 有一个时间域，给有一个时间域，给CPU增加增加一个计数器，每次访问内存，该计数器值加一个计数器，每次访问内存，该计数器值加1。如果某一。如果某一页被访问，则把计数器值拷贝到该页的时间域中）页被访问，则把计数器值

59、拷贝到该页的时间域中）. When a page needs to be changed, look at the counters to determine which are to change（当需要当需要进行页面置换时，查看页表中每一页的时间域，选择该进行页面置换时，查看页表中每一页的时间域，选择该值最小的页面换出去值最小的页面换出去.） 特点特点：每次内存访问时需增加一次写内存（写页表中某：每次内存访问时需增加一次写内存（写页表中某一页的时间域）；页面替换时需检索页表以找到时间域一页的时间域）；页面替换时需检索页表以找到时间域最小的页面。最小的页面。5435Silberschatz,

60、 Galvin, and Gagne 1999 10.43Applied Operating System ConceptsLRU Algorithm (Cont.)Stack implementation keep a stack of page numbers in a double link form（栈实现栈实现用一用一个双向链表实现一个记录页号的栈）个双向链表实现一个记录页号的栈）: Page referenced（被访问的页移到栈顶）被访问的页移到栈顶） 栈底的页是最近最少被访问的栈底的页是最近最少被访问的 No search for replacement（不用为置换进不用为置换