计算机操作系统第六章节.ppt

《计算机操作系统第六章节.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第六章节.ppt（295页珍藏版）》请在三一办公上搜索。

1、第六章 虚拟存储器,各种存储器管理方式，都要求将一个作业一次性全部装入内存中才能运行，一旦装入内存，一直驻留在内存直到运行完毕，这就引发了两种情况：（1）长作业由于要求的内存空间超过了内存实际大小，不能被装入内存从而无法运行。,第六章 虚拟存储器,（2）内存有限，致使大量的作业留在外存上等待。解决的方法：一种方法是从物理上增加内存容量；另一种方法是从逻辑上扩充内存容量，本章主要介绍的问题。,第六章 虚拟存储器,6.1 虚拟存储器的基本概念6.2请求分页存储管理方式6.3页面置换算法6.4请求分页系统的性能分析6.5请求分段存储管理方式总结 作业练习 练习答案,本章主要目录,6.1虚拟存储器的基

2、本概念,6.1.1 虚拟存储器的引入一、局部性原理二、虚拟存储器的定义6.1.2 虚拟存储器的实现方式一、分页请求系统二、请求分段系统6.1.3 虚拟存储器的特征,常规存储管理方式的特征：（1）一次性：作业在运行前需一次性的全部装入内存，正是该特征导致了上述两种情况的发生。此外，许多作业在每次运行时，并非全部的程序和数据都要用到。一次性全部装入其全部程序，是对内存空间的浪费。,6.1虚拟存储器的基本概念,（2）驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。一次性和驻留性，使许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，使得一些需要运行的作业无法装入运行。一次

3、性及驻留性是否是程序运行所必须的呢？,6.1虚拟存储器的基本概念,一、局部性原理1968年P.Denning指出，程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅限于某个部分，它所对应的内存空间也局限于一段区域。他提出了几个论点：,6.1.1 虚拟存储器的引入,（1）程序在执行时，除少数转移和过程调用指令外，大多数情况下是顺序执行的。（2）过程调用会使程序的执行流程由一部分内存区域转至另一部分区域。实际应用中，过程调用的深度一般不超过5，即程序在一段时间内，都局限在这些过程的范围内运行。,6.1.1 虚拟存储器的引入,（3）程序中存在许多循环结构，多次执行。（4）程序还包括许多

4、对数据结构(数组)的处理，局限于很小的范围内。局限性还体现在以下两个方面：,6.1.1 虚拟存储器的引入,（1）时间局限性。程序中的某条指令一旦执行，不久后该指令可能再次执行，某个数据结构被访问不久以后，该数据结构可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。,6.1.1 虚拟存储器的引入,（2）空间局限性。一旦程序访问了某个存储单元，不久后，其附近的存储单元也被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内。典型原因是程序的顺序执行。,6.1.1 虚拟存储器的引入,二、虚拟存储器的定义基于局部性原理，一个作业(程序)在运行前，没有必要全部装入内存，仅将

5、当前要运行的那部分页面或段，先装入内存即可启动运行。,6.1.1 虚拟存储器的引入,其余部分暂时留在外存上，程序在运行时如果所要访问的页或段已调入内存，则可继续运行，若尚未调入内存即缺页或缺段，程序利用OS提供的请求调页或段功能，将它们调入内存，使进程继续执行下去。,6.1.1 虚拟存储器的引入,若内存已满，无法再装入新的页或段，再利用页或段的置换功能，将内存中暂时不用的页或段调出至外存上，腾出足够的内存空间后，再将要访问的页或段调入内存，使程序继续执行下去。,6.1.1 虚拟存储器的引入,如此下去，可使一个大的用户程序在较小的内存空间中运行，也可使内存中同时装入更多的进程并发执行。从用户角度

6、看，该系统所具有的内存空间，比实际容量大得多，这样的存储器称为虚拟存储器。,6.1.1 虚拟存储器的引入,所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体说，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。(所谓虚拟存储器是一个地址空间，是进程访问的逻辑地址空间，而不是物理的主存空间。),6.1.1 虚拟存储器的引入,用户所看到的大容量只是一种感觉，是虚的，其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储管理技术，被广泛应用于各类计算机系统中。,6.1.1

7、 虚拟存储器的引入,是建立在离散分配存储管理方式的基础上，采用下述方式实现的：一、请求分页系统它是在纯分页(静态页面管理)系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统。,6.1.2 虚拟存储器的实现方式,只装入少数页面的程序（及数据），便可启动运行。随后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。要实现以上功能，系统应提供以下硬件支持：,6.1.2 虚拟存储器的实现方式,（1）请求分页的页表机制。是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构。（2）缺页中断机构。每当用户程序

8、要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页面调入内存。,6.1.2 虚拟存储器的实现方式,（3）地址变换机构 是在纯分页的地址变换机构的基础上发展形成的。要实现请求调页还应得到OS的支持，在实现请求调页功能时，是由OS将所需的页从外存调入内存，在实现置换功能时，也是由OS将内存的某些页调至外存。,6.1.2 虚拟存储器的实现方式,二、请求分段系统是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。它允许只装入若干段而非所有段的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能，将暂不运行的段调出，同时调入即将运行的段，置换是以段为

9、单位进行的。,6.1.2 虚拟存储器的实现方式,要实现请求分段，系统提供的硬件支持：（1）请求分段的段表机制。是在纯分段的段表机制基础上，增加若干项而形成的。（2）缺段中断机构。每当用户程序所要访问的段尚未调入内存时，产生一缺段中断，请求OS将所缺的段调入内存。,6.1.2 虚拟存储器的实现方式,（3）地址变换机构。是在纯分段的地址变换机构的基础上发展形成的，实现请求调段和置换功能也需得到OS的支持。目前，不少虚拟存储器是建立在段页式系统基础上的，通过分段系统的基础上增加请求调页和页面置换功能，形成了段页式虚拟存储器系统。,6.1.2 虚拟存储器的实现方式,最基本的特征是离散性，在此基础上又形

10、成了多次性及对换性，其表现出来的最重要特征是虚拟性。,6.1.3 虚拟存储器的特征,1、离散性是指在内存分配时采用离散分配方式，是其它几个特征的基础。没有离散性，就不可能实现虚拟存储器。因为一个作业需分多次调入内存。,6.1.3 虚拟存储器的特征,若采用连续分配方式时，需将作业装入一个连续的内存区域中，为此，需事先为它一次性地申请足够大的内存空间，以便将整个作业先后分多次装入内存。,6.1.3 虚拟存储器的特征,这样，一方面使一部分内存空间都处于暂时或永久空闲状态，造成内存资源的严重浪费。另一方面，不可能使一个大作业运行在一个小的内存空间中。,6.1.3 虚拟存储器的特征,即无法实现虚拟存储器

11、功能。只有采用离散分配方式，且仅在需要调入某部分程序和数据时，才为它申请内存空间，以避免浪费内存空间，也才有可能实现虚拟存储器功能。,6.1.3 虚拟存储器的特征,2、多次性是指一个作业被分成多次地调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可，以后运行到哪一部分时再将它调入。,6.1.3 虚拟存储器的特征,多次性是虚拟存储器最重要的特征，任何其它的存储管理方式，都不具有这一特征。所以，虚拟存储器是具有多次性特征的存储器系统。,6.1.3 虚拟存储器的特征,3、对换性是指允许在作业的运行过程中换进、换出，即在进程运行期间，允许将那些暂不使用的程

12、序和数据，从内存中调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换入），甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进、换出能有效地提高内存利用率。可见，虚拟存储器具有对换性特征。,6.1.3 虚拟存储器的特征,4、虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量，这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要目标。,6.1.3 虚拟存储器的特征,虚拟性是以多次性和对换性为基础的，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至外存时，才有可能实现虚拟存储器；多次性和对换性又

13、必须建立在离散分配的基础上。,6.1.3 虚拟存储器的特征,6.2 请求分页存储管理方式,6.2.1 请求分页中的硬件支持一、页表机制二、缺页中断机构三、地址变换机构6.2.2 页面分配一、最小物理块数二、页面分配和置换策略三、分配算法6.2.3 页面调入策略一、何时调入页面二、从何处调入页面三、页面调入过程,请求分页存储管理方式是建立在纯分页基础上的，是目前常用的一种实现虚拟存储器的方式。它换进、换出的基本单位是固定长的页面。请求分段方式的换进、换出基本单位是段，其长度是可变的，其每段的分配方式是动态分区分配方式。,6.2 请求分页存储管理方式,需要有页表机制、缺页中断机构及地址变换机构。一

14、、页表机制,6.2.1 请求分页中的硬件支持,请求分页系统中所需要的主要数据结构是页表。其基本作用是将用户地址空间中的逻辑地址变换为内存空间的物理地址。在页表中增加了若干项，供程序(数据)在换进、换出时参考。其页表项：,6.2.1 请求分页中的硬件支持,(1)状态位(存在位)P。用于指示该页是否已调入内存，供程序访问时参考。(2)访问字段A。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。,6.2.1 请求分页中的硬件支持,(3)修改位M表示该页在调入内存后是否被修改过。由于内存中的每一页在外存上都保留了一份副本，所以，若未被修改，在置换该页

15、时就不需将该页写回到外存上，若已被修改，则必须将该页重写到外存上，保证外存上始终是最新副本。,6.2.1 请求分页中的硬件支持,(4)外存地址。用于指出该页在外存上的地址，一般是物理块号，供调入该页时使用。,6.2.1 请求分页中的硬件支持,二、缺页中断机构 每当所要访问的页面不在内存时，系统便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断，要经历保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境几个步骤。,6.2.1 请求分页中的硬件支持,与一般的中断的区别：(1)一般中断是在指令执行期间产生和处理缺页中断信号。一般CPU每执行完一条指令后便去检查是否有中断请求

16、到达，有，则响应，否则，继续执行下一条指令。,6.2.1 请求分页中的硬件支持,缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。(2)一条指令在执行期间，可能产生多次缺页中断。,6.2.1 请求分页中的硬件支持,三、地址变换机构 请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，为实现虚拟存储器而增加了某些功能形成的。其过程如下图示：,6.2.1 请求分页中的硬件支持,在进行地址变换时，首先检索快表，从中找出要访问的页。若找到，则修改页表项中的访问位。对于写指令，还要将修改位置为1，然后利用页表项中给出的物理块号和页内地址，形成物理地址。,6.2.1

17、请求分页中的硬件支持,若在快表中未找到该页的页表项，则到内存中去查找页表，再从找到的页表项中的状态位P，了解该页是否调入内存。两种情况：,6.2.1 请求分页中的硬件支持,(1)该页已调入内存，则将该页的页表项写入快表，若快表已满时，应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项。(2)该页尚未调入内存，则产生缺页中断，请求OS从外存中把该页调入内存。,6.2.1 请求分页中的硬件支持,为进程分配物理块时，需解决三个问题：一，为保证进程能正常运行所需的最少物理块数的确定。二，为每个进程分配的物理块，其数目是固定的还是可变的。三，对不同的进程所分配的物理块数，是采取平均分配算法还是

18、根据进程的大小按比例予以分配。,6.2.2 页面分配,一、最小物理数 随着为每个进程所分配物理块数目的减少，会使进程执行中的缺页率提高，从而降低了进程的执行速度。为使进程有效地工作，应为它分配一定数目的物理块，能保证进程正常运行所需的最少物理块数。若少于此值时，进程将无法运行。,6.2.2 页面分配,进程所需的最小物理块数取决于指令的格式、功能和寻址方式。若是单地址指令且采用直接寻址方式，最少物理块数为2，一块存放指令的页面，另一块存放数据的页面。若采用间接寻址，至少要求三个物理块。功能强的机器需要的最少物理数可能要大。,6.2.2 页面分配,二、页面分配和置换策略 两种分配策略：固定和可变分

19、配策略 两种置换策略：全局置换和局部置换。组合出三种适用的策略：1、固定分配局部置换策略fixed allocation,local replacement,6.2.2 页面分配,为每个进程分配一固定页数的内存空间，在整个运行期间都不改变。若进程在运行中发现缺页时，只能从该进程在内存的n个页面中选出一页换出，再调入一页，以保证分配给进程的内存空间不变。,6.2.2 页面分配,但为每个进程分配多少个页面的内存难以确定。太少，频繁出现缺页中断，太多，内存中的进程数目减少，实现进程对换时，开销更多。,6.2.2 页面分配,2、可变分配全局置换variable allocation,global re

20、placement 最易于实现的一种页面分配和置换策略，广泛用于多个OS中。,6.2.2 页面分配,先为系统中的每个进程分配一定数目的物理块，而OS自身保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将要调入的缺页装入其中。,6.2.2 页面分配,即凡产生缺页的进程都将获得新物理块。只有当空闲物理块队列用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。,6.2.2 页面分配,3、可变分配局部置换variable allocation,local replacement 为每个进程分配一定数目的内存空间，当某进程发生缺页时，只允

21、许从该进程在内存的页面中选出一页换出，不会影响其它进程的执行。,6.2.2 页面分配,三、分配算法 固定分配时，如何将系统中可供分配的所有物理块分配给各个进程：1、平均分配算法 将系统中所有可供分配的物理块，平均分配给各个进程，貌似公平，实不公平，因为，它并未考虑到各进程本身的大小。,6.2.2 页面分配,2、按比例分配算法 根据进程的大小按比例分配物理块，若系统中n个进程，每个进程的页面数为si其总和：S=,6.2.2 页面分配,假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有 bi=bi应该取整，它必须大于最小物理块数。,6.2.2 页面分配,3、考虑优先权的分配算

22、法 把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程。另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。,6.2.2 页面分配,一、何时调入页面（调入时机）可采用：1、预调页策略 系统对那些在外存上的页进行调入顺序计算，估计出执行的顺序，并按此将它们顺次调入和调出内存。,6.2.3 页面调入策略,2、请求调页策略 当进程运行中需要访问某部分程序和数据时，发现其所在的页面不在内存，需立即提出请求，由系统将其页面调入内存。该页是一定会被访问的，目前的虚拟存储器中，大多采用此策略。,6.2.3 页面调入策略,二、从何处调入页面 请求分页系统中，把外存分为两部分：一

23、部分是文件区，存放文件；另一部分是对换区，存放对换页面。,6.2.3 页面调入策略,对换区的磁盘I/O速度比文件区的高。当发生缺页请求时，系统从何处将缺页调入内存，分三种情况：(1)系统拥有足够的对换区空间，可全部从对换区调入所需页面，以提高调页速度。在进程运行前，须将与该进程有关的文件，从文件区拷贝到对换区。,6.2.3 页面调入策略,(2)系统缺少足够的对换空间，凡不被修改的文件，都直接从文件区调入，当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入，对于那些可能被修改的部分，将它们换出时，须调到对换区，以后需要时再从对换区调入。,6.2.3 页面调入策

24、略,(3)UNIX方式，由于与进程有关的文件都放在文件区，凡是未运行过的页面，都应从文件区调入，运行过后而被换出的页面，放在对换区，在下次调入时，从对换区调入。,6.2.3 页面调入策略,在UNIX中允许页面共享，所以，某进程所请求的页面有可能已由其它进程调入内存，系统无须再从对换区调入。,6.2.3 页面调入策略,三、页面调入过程 当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，由中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。,6.2.3 页面调入策略,该程序通过查找页表，得到该页所在外存的物理块号。若此时内存未满，则启动磁盘I/O将所缺的页调入内存，然后修

25、改页表。若内存已满，则须先按照某种置换算法，从内存中选出一页准备换出。,6.2.3 页面调入策略,若该页未被修改过，可不必将该页写入磁盘。若此页已被修改，则必须将它重新写入磁盘。然后再将缺页调入内存，并修改页表中的相应页表项，将其存在位置为1，再将此页表项写入快表中。,6.2.3 页面调入策略,在将缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。,6.2.3 页面调入策略,6.3页面置换算法,6.3.1 最佳置换算法和先进先出算法一、最佳置换算法二、先进先出页面置换算法6.3.2 最近最久未使用LRU置换算法一、LRU算法的描

26、述二、LRU算法的硬件支持6.3.3 Clock置换算法一、简单的Clock置换算法二、改进型Clock置换算法6.3.4 其它置换算法一、最少使用LFU置换算法二、页面缓冲算法PFL影响缺页中断率的因素,进程运行过程中，若其所要访问的页面不在内存，而内存已无空闲空间时，系统必须从内存中调出一页程序或数据送磁盘的对换区中。将哪个页面调出，须根据一定的算法来确定。,6.3页面置换算法,选择换出页面的算法称为页面置换算法Page-Replacement Algorithms。算法的好坏影响系统的性能，不适当的算法会导致进程发生“抖动”Thrashing。即刚被换出的页很快又被重新调入，调回内存不久

27、又马上调出内存，如此反复，频繁地更换页面，把大部分时间花费在完成页面置换的工作上，称该进程发生了“抖动”。颠簸,6.3页面置换算法,一个好的置换算法，理论上，应将以后不会被访问的页面换出，或把在较长时间内不会被访问的页面换出。,6.3页面置换算法,两种极端的算法，前者具有最好的性能，却难于实现，后者是性能最差的算法，却是最直观的算法，实际应用很少。一、最佳置换算法optimal 该算法是由Belady于1966年提出的，它所选择的被淘汰页面，将是永不使用的，或是在最长时间内不再被访问的页面。,6.3.1 最佳置换算法和先进先出算法,对于固定分配方式，该算法可获得最低的缺页率。由于无法预知一个进

28、程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，所以，该算法是无法实现的。但可用它去评价其它算法。假定系统为某进程分配了三个物理块，并有以下的页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,6.3.1 最佳置换算法和先进先出算法,进程运行时先将7,0，1三个页面装入内存，以后，当访问页面2时，产生缺页中断，OS根据最佳置换算法，选择页面7予以淘汰，因为页面0在第5次时被再访问，页面1在第14次再被访问，而页面7要在第18次时被再访问时才需调入。,6.3.1 最佳置换算法和先进先出算法,再访问0页面时，则不会产生缺页中断，而当进程访问页

29、面3时，又引发页面1被淘汰，以此类推，直至进程完成，其运行过程中只发生了6次页面置换。如图：,6.3.1 最佳置换算法和先进先出算法,缺,缺,缺,缺,缺,缺,6.3.1 最佳置换算法和先进先出算法,二、先进先出页面置换算法 最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即在内存中驻留时间最长的页面。,6.3.1 最佳置换算法和先进先出算法,该算法实现简单，只须把调入内存的页面，按先后次序链接一个队列，并设置一个指针，称为替换指针，它总是指向最老的页面。但与进程实际运行的情况不一定相符。因为某一个进程中，有些页面经常被访问，它在内存中的时间可能是最长的，有可能会被淘汰掉。,6.3.1 最

30、佳置换算法和先进先出算法,例：系统分配三个物理块，某进程有引用页面号串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1若采用先进先出置换算法，共发生了12次置换。如：,6.3.1 最佳置换算法和先进先出算法,缺,缺,缺,缺,缺,缺,缺,缺,缺,缺,缺,缺,6.3.1 最佳置换算法和先进先出算法,Belady现象陷阱现象：分配的页面数增多，缺页次数反而增加。正常情况，例：一进程分配3个页框，页面访问次序：7,0，1,2，0,3，0,4，2,3，0,3，2,1，2,0，1缺页12次若分配4个页面，发生9次缺页另一情况，例：一进程分配3个页框，访问串：1,2，3,4，

31、1，,2，5,1，2,3，4,5，产生9次缺页，若分配4个页框，产生10次。原因：没有考虑程序执行的动态特征。,6.3.1 最佳置换算法和先进先出算法,一、LRU(least recently used)算法的描述 该算法是根据程序执行时所具有的局部属性来考虑的，即那些刚被使用过的页面，可能马上还要被使用，而那些在较长时间里未被使用的页面，一般说可能不会马上被使用到。,6.3.2 最近最久未使用LRU置换算法,根据页面调入内存后的使用情况，用“最近的过去”作为“最近的将来”的近似。即LRU是选择最近最久未使用的页面予以淘汰。,6.3.2 最近最久未使用LRU置换算法,该算法赋予每个页面一个访问

32、字段，用来记录一个页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。,6.3.2 最近最久未使用LRU置换算法,例：对页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1利用LRU算法进行页面置换，其结果如图：,6.3.2 最近最久未使用LRU置换算法,缺,缺,缺,缺,缺,缺,缺,缺,缺,6.3.2 最近最久未使用LRU置换算法,二、LRU算法的硬件支持 LRU对各种类型的程序都能适用，但实现复杂，须利用一些硬件支持解决一些问题：(1)一个进程在内存中的各个页面各有多久时间未被进程访问(

33、2)如何快速地知道哪一页是最近最久未使用的页面。,6.3.2 最近最久未使用LRU置换算法,1、寄存器 用于记录某进程在内存中各页的使用情况，需为每个在内存中的页面配置一个移位寄存器，表示为：R=Rn-1 Rn-2 Rn-3 R2 R1 R0,6.3.2 最近最久未使用LRU置换算法,进程访问某物理块时，将相应的寄存器的Rn-1位(最高位)置成1，定时信号将每隔一定时间将寄存器右移一位。若把n位寄存器的数看作一个页符号的整数，则具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图：,6.3.2 最近最久未使用LRU置换算法,6.3.2 最近最久未使用LRU置换算法,2、堆栈 利用一

34、个特殊的栈来保存当前使用的各个页面的页面号。当进程访问某页面时，将该页面的页面号从栈中移出，将它压入栈顶，所以，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未使用页面的页面号。假定有一进程访问的页面号的序列：4,7,0,7,1,0,1,2,1,2,6 进程访问时，栈中的变化情况如图：,6.3.2 最近最久未使用LRU置换算法,6.3.2 最近最久未使用LRU置换算法,一种LRU的近似算法一、简单的Clock置换算法（最近未用算法NUR）该算法只须为每页设置 一位访问位表示是否已使用过，再将内存中的所有页面都通过链接指针链成一个循环队列。,6.3.3 Clock置换算法,当某页被访问时，

35、其访问位被置为1。置换算法在选择一页淘汰时，只须检查其访问位，若是0，就选择该页换出，若为1，则重新将它复为0，暂不换出而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则返回队首再去检查第一个页面。,6.3.3 Clock置换算法,该算法：只有一位访问位，表示是否已经使用过，置换时是将未使用过的页面换出去，所以，又称为最近未用算法NUR(not used recently)，系统周期性地对引用位清零。二、改进型Clock置换算法 将一个页面换出时，若该页已被修改过，则须将它重新写到磁盘上，若未被修改过，则不必写回磁盘。,6.3.

36、3 Clock置换算法,改进型Clock算法中，增加了一个置换代价，利用一个修改位实现之。选择换出页面时，既要是最近未访问过的页面，又要是未被修改过的页面。,6.3.3 Clock置换算法,访问位A和修改位M组合成四种类型的页面：1类(A=0，M=0)表示该页最近既未被访问、又未被修改，是最佳淘汰页。2类(A=0，M=1)表示该页最近未被访问，但已被修改过，并不是很好的淘汰页。,6.3.3 Clock置换算法,3类(A=1，M=0)最近已被访问，但未被修改过，该页有可能再被访问。4类(A=1，M=1)最近已被访问且被修改，有可能会再被访问。内存中每个页必是其中一类页面，进行页面置换时，同时检查

37、访问位和修改位，执行过程如下：,6.3.3 Clock置换算法,(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为选中的淘汰页。第一次扫描期间不改变访问位A。,6.3.3 Clock置换算法,(2)若第一步失败，开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个页面作为淘汰页。第二轮扫描期间，将所有经过的页面的访问位 置为0。,6.3.3 Clock置换算法,(3)若第二步也失败，将指针返回到开始的位置，并将所有的访问位复为0，然后，重复第一步，若再失败，再重复第二步，直到找到被淘汰的页。,6.3.3 Clock置换算法,一、

38、最少使用置换算法LFU(Least Frequently Used)最不经常使用页面先调度算法 该算法，为在内存中的每个页面设置一移位寄存器，每次访问时，对该页移位寄存器的最高位置为1，每隔一定时间T右移一次，用于记录该页面被访问的频率。,6.3.4 其它置换算法,置换时，选择在最近时期使用最少的页面(寄存器中各数位上的数字之和的最小值的页面，而不是寄存器中所存储的二进制数值的最小者)作为淘汰页。问题：T应该多大？,6.3.4 其它置换算法,二、页面缓冲算法PBA(Page Buffering Algorithm)该算法采用的可变分配和局部置换方式，置换算法采用FIFO，规定将一个被淘汰的页放

39、入两个链表中的一个。,6.3.4 其它置换算法,即：若页面未被修改，就将它直接放入空闲链表中，否则，便放入已修改页面的链表中。此时，页面在内存并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。,6.3.4 其它置换算法,空闲页面链表，是一个空闲物理块链表，其中的每个物理块都是空闲的，所以，可装入程序或数据，当需要读入一个页面时，利用空闲物理块链表中的第一个物理块来装入该页，当有一个未被修改的页需要换出时，实际上并不是将它换出内存，而是把它所在的物理块挂在自由页链表的末尾。,6.3.4 其它置换算法,置换一个已修改过的页面时，将其所在的物理块挂在修改页面的链表的末尾。这样，已被修改

40、的页面和未被修改的页面，都仍留在内存中，以后再访问这些页面时，花费较小的开销，即可使这些页面返回到该进程的驻留集中。只有当被修改页面达到一定数量时，再将它们一起写回到磁盘，减少了磁盘I/O的操作次数。,6.3.4 其它置换算法,另外，（1）随机淘汰算法。随机选择某个用户的页面进行置换。（2）轮转法，循环换出内存空间中的页，无论该页是否刚被换进或已换进内存很长时间。,6.3.4 其它置换算法,6.3.4 其它置换算法,影响缺页中断率的因素(1)分配给作业的主存块数。成反比。(2)页面的大小。反比。(3)作业本身的程序编制方法。(4)调度算法。,6.4 请求分页系统的性能分析,6.4.1 缺页率对

41、有效访问时间的影响6.4.2 工作集6.4.3 抖动产生的原因和预防方法一、抖动产生的原因二、抖动的预防,请求分页系统是目前最常用的一种存储管理方式，但其运行中产生的缺页会影响到系统的性能，而缺页率的高低又直接与每个进程所占用的物理块数目有关。本节主要分析缺页率对系统性能的影响，及应该为每个进程所分配的物理块数目，把缺页率保持在一个合理的水平。,6.4 请求分页系统的性能分析,大多数计算机系统，其存储器的访问时间ma(memory access)在10ns到数百ns之间。若不发生缺页，则系统有效访问时间就等于存储器的访问时间。,6.4.1 缺页率对有效访问时间的影响,若发生了缺页，就必须先从磁

42、盘上将该页调入内存，然后才能访问该页面上的数据。假定出现缺页的概率为p，缺页时须先调入该页，则这时，有效访问时间可表示为：有效访问时间=(1-p)ma+p缺页中断时间,6.4.1 缺页率对有效访问时间的影响,缺页中断时间主要由三部分组成：(1)缺页中断服务时间(2)将缺页读入的时间(3)进程重新执行时间,6.4.1 缺页率对有效访问时间的影响,一般，(1)和(3)不超过1ms，缺页读入内存的时间包括：寻道时间、旋转时间和数据传送时间三部分，一般有24ms。可知，缺页中断时间总计约25ms。未包括：进程可能等待的时间。,6.4.1 缺页率对有效访问时间的影响,可得公式：有效访问时间=(1-p)0

43、.1+p25000=0.1+24999.9p有效访问时间直接比例于缺页率。,6.4.1 缺页率对有效访问时间的影响,若在1000次的页面访问中，只发生一次缺页，即p=0.001，有效访问时间则为25s，若不发生缺页时，p=0，有效访问时间等于存储器的访问时间0.1 s。,6.4.1 缺页率对有效访问时间的影响,若在发生缺页时，要使有效访问时间延长不超过10%，则缺页率p:0.110.1+24999.9p 则p(0.01/24999.9)=0.0000004,6.4.1 缺页率对有效访问时间的影响,即在2500000次访问中，才发生一次缺页，从中可以看出，必须保持很低的缺页率，才能使有效访问时间

44、不超过10%，否则，会使程序的执行速度受到严重影响。,6.4.1 缺页率对有效访问时间的影响,缺页率，或者缺页的时间间隔与进程所分得的物理块数目有密切关系。缺页率随着物理块数目的减少单调地递增，并在所分到的物理块数目较少处，出现一个拐点。,6.4.2 工作集,在拐点下限以左时，再每增加一个物理块后都可明显地减少缺页率，过了拐点，在下限以右时，每增加一个物理块后，对缺页的时间间隔无明显影响，即对缺页率的改善不明显。(这个特定点随程序而改变，试验分析表明，每个程序来说，要使其有效的工作，它在主存中的页面数应不低于它的总页面数的一半。),6.4.2 工作集,一般而言，为进程所分配的物理块数，应取在该

45、曲线的拐点左右，若内存空间较充足，所取数目还可略大些。,6.4.2 工作集,缺页率,物理块数 n,上限,下限,0,6.4.2 工作集,形成曲线形状的原因，是由于缺页率的大小与进程运行时的所谓的工作集有关。关于工作集的理论是在1968年由Denning提出并推广的。Denning认为，程序在运行时对页面的访问是不均匀的，即往往在某段时间内的访问仅局限于较少的若干个页面，而在另一段时间内，又可能仅局限于另一些较少的页面。,6.4.2 工作集,若能预知程序在某段时间间隔内要访问哪些页面，并能将它们提前调入内存，将会大大降低缺页率，从而减少置换工作，提高CPU的利用率。,6.4.2 工作集,所谓工作集

46、是指，在某段时间间隔内，进程实际要访问的页面的集合。Denning认为，为使程序能有效地运行，较少地产生缺页，必须使程序的工作集全部在内存中，利用程序过去某段时间内的行为，作为程序在将来某段时间内的行为的近似。,6.4.2 工作集,具体地说，是把某进程在时间t的工作集记为w(t，)，把变量称为工作集“窗口尺寸”(windows size)(系统所分配的物理块数)。工作集可形象化的定义为：在时间t-到t之间所访问的一串页面 如图示：某进程访问页面的序列和当窗口尺寸分别为3、4、5时的工作集。,6.4.2 工作集,引用页序列,3,5,4,窗口大小,6.4.2 工作集,工作集w(t，)是二元函数。它

47、与时间有关，即在不同时间t的工作集的大小不同，所包含的页面数也不相同，它又与窗口尺寸有关。工作集w是窗口尺寸的非降函数(nondecreasing function)。即：w(t，)w(t，+1),6.4.2 工作集,正确选择工作集窗口的大小，对存储器的有效利用和系统的吞吐量的提高，将产生重要的影响。选择很大，能将一个进程的整个地址空间全部装入内存，不会产生缺页，但存储器不会得以充分地利用。,6.4.2 工作集,选择过小，会使进程在运行中频繁地产生缺页中断，反而，又降低了系统的吞吐量。所以，工作集的大小选择要适中，才能保持适当的缺页率。,6.4.2 工作集,不适当的提高多道程序度，会使得在内存

48、中引入过多的进程时，出现“抖动”现象。一、抖动产生的原因 请求分页系统中，每个进程只能分配到所需全部内存空间的一部分。,6.4.3 抖动产生的原因和预防方法,若进程A在运行过程中需要增加页面，便会产生中断。在采用全局置换策略时，它有可能被分配到一个原属B进程的物理块，用来装入新调入的页，而B进程在运行中还需要该物理块，也会产生中断，它又有可能会被分配到C进程的一个物理块。以此类推。而产生缺页中断的进程会一直处于等待状态，从而会导致就绪队列空。,6.4.3 抖动产生的原因和预防方法,而此时，调度程序一旦发现CPU空闲，又会引入新的进程参加运行，新进程进入内存时，又进一步加剧了进程的缺页情况，等待

49、页面调入/调出的进程数目随之增加，使CPU的利用率进一步下降，调度程序又去引入新的进程，如此恶性循环，使缺页率急剧上升，有效访问时间也急剧增加。,6.4.3 抖动产生的原因和预防方法,运行进程的大部分时间都用于进行页面的换入/换出，几乎不能完成任何有效的工作，这时的进程我们称处于“抖动”状态。,6.4.3 抖动产生的原因和预防方法,CPU的利用率，在开始阶段，随着程序度的提高，会随之提高，并在随后达到某一峰值，以后若继续增加多道程序度，就会产生抖动，从而导致CPU的利用率急剧下降。,6.4.3 抖动产生的原因和预防方法,多道程序度,CPU利用率,6.4.3 抖动产生的原因和预防方法,二、抖动的

50、预防 有多种方法可防止抖动的产生和扩展，通过调节多道程序度实现。1、采取局部置换策略 系统在采取可变分配方式的同时，又采取局部置换策略。,6.4.3 抖动产生的原因和预防方法,当某进程发现缺页时，仅在自己的内存空间范围内置换页面，不允许从其它进程获得新的物理块，即使有某个进程发生了抖动，也不会导致其它进程也产生抖动。,6.4.3 抖动产生的原因和预防方法,这种方法，不能从根本上防止抖动的产生，而在某进程发生抖动后，会长期地处于磁盘I/O的等待队列中，又会使其它进程缺页中断的处理时间增长，从而延长了有效的访问时间。,6.4.3 抖动产生的原因和预防方法,2、在CPU调度程序中引入工作集算法 引入