页面置换算法课件.ppt

1、第五章 虚 拟 存 储 器第五章第五章 虚拟存储器虚拟存储器第五章 虚 拟 存 储 器本章要点本章要点（1/2） 目标：目标：了解虚拟存储器的相关概念和技术。了解虚拟存储器的相关概念和技术。 虚拟存储的基本概念虚拟存储的基本概念 为什么要引入虚拟存储器？ 虚拟存储器是如何扩充内存容量的？ 虚拟存储器具有哪些特征？每种特征的具体含义是什么？它们相互之间存在着什么样的关系？它们与离散分配之间又存在着什么样的关系？ 实现虚拟存储器的关键技术是什么？这些技术的实现需要得到哪些硬件支持和软件支持？ 第五章 虚 拟 存 储 器 请求分页系统的基本原理请求分页系统的基本原理 为实现虚拟存储器，必须扩充表项的

2、内容，除了内存块号和存取权限字段以外，页表中还必须增加哪些字段，为什么要增加这些字段？ 请求分页系统的地址变换也必须通过地址变换机构进行，请求分页系统的地址变换机构，是在基本分页系统的地址变换机构的基础上增加了哪些功能而形成？ 常用的页面置换算法有哪些？ 为什么LRU算法具有比较好的性能？它的主要缺点是什么？可用什么方法实现LRU近似算法？本章要点本章要点（2/2）第五章 虚 拟 存 储 器5.1 5.1 虚拟存储器概述虚拟存储器概述 5.2 5.2 请求分页存储管理方式请求分页存储管理方式 5.3 5.3 页面置换算法页面置换算法 5.4 5.4 “抖动抖动”与工作集与工作集5.5 5.5

3、请求分段存储管理方式请求分段存储管理方式 本章内容本章内容第五章 虚 拟 存 储 器5.1 5.1 虚拟存储器概述虚拟存储器概述第五章 虚 拟 存 储 器5.1 虚拟存储器概述虚拟存储器概述 简单存储器管理方式，都要求将一个作业全部装入内存方能运行。于是出现以下两种情况： 有的作业很大，所要求的内存空间超过了内存的总容量； 有大量的作业要求运行，但由于内存容量不足，难以容纳所有的作业。 解决方法：解决方法： 从物理上增加内容容量 从逻辑上扩充内存容量第五章 虚 拟 存 储 器5.1.1 常规存储管理方式的特征常规存储管理方式的特征和局部性原理和局部性原理 简单存储器的特征简单存储器的特征 一次

4、性：一次性：作业必须一次性全部装入内存才能开始运行，这是一种对内存空间的浪费。 驻留性：驻留性：作业装入内存后，便一直驻留在内存直至作业运行结束，占据了宝贵的内存资源 一次性及驻留性带来的问题：一次性及驻留性带来的问题： 会使许多在进程运行时不用的或暂时不用的程序（数据）占据大量的内存空间; 使一些需要运行的作业无法装入运行。1、常规存储器管理方式的特征、常规存储器管理方式的特征第五章 虚 拟 存 储 器 问题的提出问题的提出(P.Denning) 程序在执行时将呈现出局部性局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。 论点论点 程序在执

5、行时，大多数情况下是顺序执行的 过程调用将会使程序的执行轨迹由一部分区域转至另一区域，但调用深度通常不超过5 程序中存在许多循环结构，它们虽由少数指令构成，但多次执行 程序中对数据结构的处理，往往都局限于很小的范围内 2、局部性原理、局部性原理一次性及驻留性是一次性及驻留性是否是程序运行时所否是程序运行时所必需的？必需的？第五章 虚 拟 存 储 器 局部性的表现方式局部性的表现方式 时间局部性时间局部性 ：一个数据结构被访问，不久可能再次被访问。典型原因： 程序中存在大量的循环操作 空间局部性：空间局部性：一段时间访问的地址可能集中在一定范围 。典型原因：程序顺序执行2、局部性原理、局部性原理

6、sum = 0;for (i = 0; i n; i+)sum += ai;return sum;第五章 虚 拟 存 储 器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 是进一步完善主存-辅存存储层次，解决主存容主存容量量提出的。 实现思想：实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动将它们从外存调入内存。3、虚拟存储器的基本工作情况、虚拟存储器的基本工作情况第五章 虚 拟 存 储 器 什么是虚拟存储？什么是虚拟存储？ 定义：定义：具有请求调入功能和置换

7、功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来使用，构成容量很大的“内存”。 目的：目的：提高内存利用率1、虚拟存储器定义、虚拟存储器定义5.1.2 虚拟存储器的定义和特征虚拟存储器的定义和特征第五章 虚 拟 存 储 器 虚拟存储器管理应解决以下问题：虚拟存储器管理应解决以下问题： 主存和辅存的统一管理问题 逻辑地址到物理地址的转换问题 部分装入部分装入和部分对换部分对换问题 把哪一部分装入内存 何时把页面装入 装入内存什么位置 当内存没有空间时淘汰哪个页面1、虚拟存储器定义、虚拟存储器定义第五章 虚 拟 存 储 器 多次性多次性：指一个作业中的程序和数据允许被

8、分成多次调入内存运行，这是虚拟存储器最重要的特征。 对换性对换性：指允许作业中的程序和数据在作业运行过程中换入、换出。 虚拟性虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器表现出的最重要特征，是实现虚拟存储器的最重要的目标。 虚拟性是以多次性多次性和对换性对换性为基础，多次性和对换性是建立在离散分配离散分配的基础上。2、虚拟存储器的特征、虚拟存储器的特征第五章 虚 拟 存 储 器5.1.3 虚拟存储器的实现方法虚拟存储器的实现方法实现虚拟存储的典型过程实现虚拟存储的典型过程 虚拟存储器管理的技术支持虚拟存储器管理的技术支持 必须有相应的硬件支持，用

9、以实现虚拟分页和虚拟分段存储管理； 操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。第五章 虚 拟 存 储 器 在简单分页基础上，增加了请求调页功能、页面置换功能。 置换时以页面页面为单位进行 系统提供的硬件支持：系统提供的硬件支持： 请求分页的页表机制； 缺页中断机构； 地址变换机构。 实现请求分页的软件：实现请求分页的软件： 请求调页软件 页面置换软件1、请求分页系统、请求分页系统 第五章 虚 拟 存 储 器 在分段的基础上，增加了请求调段功能、分段置换功能 置换时以段段为单位进行 系统提供的硬件支持：系统提供的硬件支持： 请求分段的段表机制； 缺段中断机构； 地址变换机

10、构。 实现请求分段的软件：实现请求分段的软件： 请求调段软件 段置换软件2、请求分段系统、请求分段系统 第五章 虚 拟 存 储 器5.2 5.2 请求分页存储管理方式请求分页存储管理方式第五章 虚 拟 存 储 器5.2 请求分页存储管理方式请求分页存储管理方式 建立在基本分页存储管理之上，是目前比较常用的一种虚拟存储管理技术第五章 虚 拟 存 储 器5.2.1 请求分页中的硬件支持请求分页中的硬件支持1、请求页表机制、请求页表机制 在请求分页系统中所需要的主要数据结构是请求页表。 作用：作用：将用户地址空间中的逻辑地址变换为内存空间的物理地址。 请求分页系统中的每个页表项如下图所示：页号页号

11、物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 指示该页是否指示该页是否已调入内存已调入内存记录本页在一段时间内被访记录本页在一段时间内被访问的次数，或记录本页最近问的次数，或记录本页最近已有多长时间未被访问，供已有多长时间未被访问，供选择换出页面时参考选择换出页面时参考该页在调入内存后是否被修该页在调入内存后是否被修改过，供置换页面时参考改过，供置换页面时参考指出该页在外存上的地址，指出该页在外存上的地址，供调入该页时参考供调入该页时参考第五章 虚 拟 存 储 器2、缺页中断机构、缺页中断机构 缺页中断机构缺页中断机构 与一般中断相同的处理步骤：保护CP

12、U环境、分析中断原因、转入中断处理程序进行处理、恢复CPU环境等几个步骤。 缺页中断和一般的中断相比有如下区别：缺页中断和一般的中断相比有如下区别：1）缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号；2）缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行 ；3）一条指令在执行期间，可能产生多次缺页中断。第五章 虚 拟 存 储 器2. 缺页中断机构缺页中断机构 图 5-1 涉及6次缺页中断的指令 页面B：A：654321指令copy ATO B 对硬件的要求：对硬件的要求： 系统中的硬件机构应能够保存多次中断时的状态，并保证

13、最后能够返回到中断前产生缺页中断的指令处，继续执行。第五章 虚 拟 存 储 器图图 5-2 请求分页中的地址变换过程请求分页中的地址变换过程 3、地址变、地址变换机构换机构 第五章 虚 拟 存 储 器5.2.2 请求分页中的内存分配请求分页中的内存分配 页面分配原则页面分配原则 缺页中断、I/O中断频繁会降低运行效率，因此应尽可能减少缺页中断的次数。 为进程分配物理块时要考虑的问题：为进程分配物理块时要考虑的问题： 保证进程正常运行所需要的最少物理块； 为进程分配的物理块数目是固定的还是可变的 为进程分配物理块数是采取平均分配算法，还是根据进程的大小比例予以分配。第五章 虚 拟 存 储 器 是

14、指能保证进程正常运行所需最小物理块数最小物理块数。 当系统为进程分配的物理块数少于此值时，进程将无法运行。 每个进程的最小页框数是由计算机结构体系所定义的，最大数是由有效的物理内存所定义的。 PDP-11的移动指令包括多个字，因此指令本身可能会跨2页。另外，它的两个操作数可能是间接引用，所以总共需要6个物理块。 IBM 370 MVC指令。因为指令是从存储器地址到存储器地址，需要花费6个字节，并且会跨2个页面。要移动的字符块和将要移至的区域也都会跨2个页面。这种情况就要求有6个页框。1、最小物理块数的确定、最小物理块数的确定 第五章 虚 拟 存 储 器 分配策略：分配策略：固定和可变分配策略。

15、 置换策略：置换策略：全局置换和局部置换。 三种适用的内存分配策略三种适用的内存分配策略： 固定分配局部置换(Fixed Allocation, Local Replacement) 可变分配全局置换(Variable Allocation, Global Replacement) 可变分配局部置换(Variable Allocation, Local Replacement)2、内存分配策略、内存分配策略 第五章 虚 拟 存 储 器 固定分配局部置换固定分配局部置换 固定分配：固定分配：为每个进程分配固定固定数目的物理块，整个运行期间不再改变。 局部置换：局部置换：如果进程在运行中发现缺页，

16、则只能从在内存中分配给该进程的固定物理块中选出一页换出，然后再调入一页。 难点：难点：为每个进程分配多少物理块难以确定 太少，频繁缺页中断，降低系统吞吐量。 太多，内存驻留进程减少，可能造成资源空闲，而且实现进程对换时，会花费更多的时间。2、内存分配策略、内存分配策略 第五章 虚 拟 存 储 器 可变分配全局置换（易于实现）可变分配全局置换（易于实现） 可变分配：可变分配：先为系统中的每个进程分配一定数目的物理块，在进程运行期间可以适当增减，而OS自身也保持一个空闲物理块队列。 全局置换：全局置换：当某进程发现缺页，由系统从空闲的物理块队列中，取出一物理块分配该进程，并将欲调入的缺页装入其中。

17、当空闲物理块用完时，OS从内存中任选一页调出（任意进程）。2、内存分配策略、内存分配策略 第五章 虚 拟 存 储 器 可变分配局部置换可变分配局部置换 根据进程的类型或程序员的要求，为每个进程分配一定数目的物理块。 当某进程发生缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。 如果进程在运行中频繁地发生缺页中断，则系统再为该进程分配附加的物理块；反之，若一个进程在运行中缺页频率低，则此时适当减少分配给该进程的物理块。2、内存分配策略、内存分配策略 第五章 虚 拟 存 储 器 平均分配算法：平均分配算法：物理块平均分配给各进程； 缺点：缺点：未考虑到进程本身的大小

18、，不公平。 按比例分配算法：按比例分配算法：按进程大小的比例分配物理块； n为系统内的进程数；Si为i进程的页面数；m为可用的物理块总数；i进程能分到的物理块数为bi 考虑优先权的分配算法：考虑优先权的分配算法：按照作业的重要性、紧迫性进行分配。 一般将可供分配的物理块分为两部分：一部分按比例分配；另一部分按优先权适当增加份额。 在重要的实时系统中，则可能是完全按优先级为各进程分配物理块。 3、物理块分配算法、物理块分配算法 mssbiiniiss1第五章 虚 拟 存 储 器5.2.3 页面调入策略页面调入策略 应解决从何时调入何时调入页面、从何处调入何处调入页面以及如何如何调入调入的问题！1

19、、何时调入页面、何时调入页面 预调页策略：预调页策略：根据空间局部性，将不久之后便会被访问的程序或数据所在的页面，预先调入内存。 特点：特点：预调页的成功率仅有50%。 主要用于进程的首次调入。 请求调页策略：请求调页策略：进程在运行时，发现其所访问的程序页面不在内存，请求系统将所需页面调入内存。 特点：特点：系统开销大；易实现。虚拟存储器大多采用此策略。第五章 虚 拟 存 储 器 2、从何处调入页面、从何处调入页面 系统有足够的存储空间，这时可以全部从对换区对换区调入所需页面，以提高调页的速度。 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区文件区调入；但对于那些可能被修

20、改的部分，在将它们换出时，便须调到对换区，以后需要时再从对换区对换区调入。 UNIX方式，凡是未运行过的页，都应从文件区文件区调入。对于曾经运行过而又被换出的页面，从对换区对换区调入。第五章 虚 拟 存 储 器 缺页中断处理程序通过查找页表，得到该页所在外存的物理块号。 如果此时内存空闲，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。 如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出； 如果该页未被修改过，可不必将页写入磁盘；但如果该页已被修改，则必须将它重新写入磁盘，然后再将缺页调入内存，并修改页表中的相应表项，再将此页表项写入快表中。据修改后的页表形成去访问数

21、据的物理地址。3、页面调入过程、页面调入过程第五章 虚 拟 存 储 器 衡量指标衡量指标缺页率f 假定作业p共计n页，系统分配给它的主存块为m (m S，表示很少发生缺页 LS，表示频繁发生缺页 LS，表示磁盘与处理机均能达到它们的最大利用率 当多道程序度偏高，影响到处理机的利用率，则应选择挂起某些当前活动的进程，将它们对换至外存。 首先选择优先级最低的进程 其次选择优先级较低的进程 再选择并不十分重要、但却较大的进程 选择剩余执行时间最多的进程3、利用、利用“L=S”准则调节缺页率准则调节缺页率4、选择暂停的进程、选择暂停的进程第五章 虚 拟 存 储 器5.5 5.5 请求分段存储管理方式请

22、求分段存储管理方式 第五章 虚 拟 存 储 器 请求分段式管理需要请求段表机制、缺段中断机构以及地址变换机构。1、请求段表机制、请求段表机制 请求段表是请求分段管理方式的主要数据结构。请求分段的段表项如图所示。5.5.1 请求分段中的硬件支持请求分段中的硬件支持 段名段名段长段长段段基址基址存取存取方式方式访问访问字段字段A修改修改字段字段M存在存在位位P增补增补位位外存外存始址始址第五章 虚 拟 存 储 器 在请求分段系统中，采用的是请求调段策略。 进程访问的段不在内存，缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所缺的段调入内存。2、缺段中断机构、缺段中断机构 第五章 虚

23、 拟 存 储 器图图 5-12 请求分段系统中的中断处理过程请求分段系统中的中断处理过程2、缺段中断机构、缺段中断机构 第五章 虚 拟 存 储 器 缺段中段与缺页中段的区别：缺段中段与缺页中段的区别： 共同点：共同点：在一条指令的执行期间产生和处理中断，一条指令的执行期间可能产生多次缺段中断。 不同点：不同点：在请求分段存储管理方式中，不可能出现一条指令被分割在两个分段中的情况；也不可能有被传送的一组信息被分割在两个分段中的情况。2、缺段中断机构、缺段中断机构 第五章 虚 拟 存 储 器 在分段系统地址变换机构的基础上，增加了缺段中段的请求及其处理等功能形成的。 地址变换过程：地址变换过程：若

24、有缺段，则先将所缺的段调入内存，然后修改段表，再利用段表进行地址变换。3、地址变换机构、地址变换机构 第五章 虚 拟 存 储 器图图 5-13 请求分段系统的地址变换过程请求分段系统的地址变换过程访问swW段长？符合存取方式？段s在主存？修改访问字段，如写访问，置修改位为1形成访问主存地址(A)=(主存始址）+（位移量W)分段越界中断处理分段保护中断处理缺段中断处理访问sw是是是否否否3、地址变换机构、地址变换机构 第五章 虚 拟 存 储 器5.5.2 分段的共享与保护分段的共享与保护 实现分段共享，应配置相应的数据结构共享段表及对共享段的操作过程。 共享段表：共享段表：为了实现分段共享在系统

25、中配置的一张段表，所有各共享段都在共享段表中上有一个表项。表项中记录了共享段的段号和段长、内存起始地址、存在位等信息，并记录有共享此分段的每个进程的情况。第五章 虚 拟 存 储 器1、共享段表、共享段表 图 5-14 共享段表项 共享进程计数器共享进程计数器COUNT：记录有多少个进程需要共享该分段。 存取控制字段存取控制字段：说明不同的进程对该分段不同的存取权限。 段号段号：对于同一个共享段，不同的进程可以使用不同的段号去共享该段。第五章 虚 拟 存 储 器 共享段的分配：共享段的分配：只对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，并把共享段调放该区，同时将该区的始址填入该

26、进程的段表的相应项中，同时把count置为。 此后如有其它进程需要调用该共享段时，只需在调用进程的段表中，增加一个表项，填入该共享段的物理地址；在共享段的段表中，填上进程名、存取控制等。再执行count+1操作。 共享段的回收：共享段的回收：当共享此段的某进程不再需要它时，应将该段释放，修改该进程的段表及共享段段表。当count=0时，则由系统回收该共享段的物理内存。 2、共享段的分配与回收、共享段的分配与回收 第五章 虚 拟 存 储 器 分段保护的常用措施分段保护的常用措施 越界检查越界检查 将逻辑地址的段号与段表的长度（段表寄存器）比较 段内地址与（段表中）段长比较 存取控制检查存取控制检查 段表的“存取控制”字段中的访问方式： （1）只读；（2）只执行；（3）读写； 环保护机制环保护机制3、分段保护、分段保护 第五章 虚 拟 存 储 器 设置不同的环，并赋予不同的优先权，并规定低编号的环有较高的优先权。 程序根据其重要程度放在不同的环中。 在环系统中，程序的访问和调用应遵循下列原则： 一个程序可以访问驻留在相同环或较低特权环中的数据 一个程序可以调用驻留在相同环或较高特权环中的服务环保护机制环保护机制调用返回调用返回环0环1环2(a) 程序间的控制传输数据访问环0环1环2(b) 数据访问数据访问