《C虚拟存储器》PPT课件.ppt

4.6 虚拟存储器的基本概念 前面所介绍的各种存储管理方式具有一个共同 的特点，即作业必须一次性全部装入主存空间后才 能运行，直至作业运行结束后才释放所占有的全部 主存资源。这样就会出现以下情况： 1当主存空间不能满足作业地址空间要求时，作业就不能装 入主存，无法运行。 2当有大量作业要求运行时，由于主存容量有限，只能将少 数作业装入主存运行，而其他作业留在辅存上等待。 4.6.1 虚拟存储器的引入 常规存储管理方式的特征是：一次性、驻留性。 局部性原理 早在1968年PDenning就指出过，程序在执行时将呈 现出局部性规律，即在一段时间内，程序的执行仅局限于某 个部分；相应地，它所访问的存储空间也局限于某个区域内 。那么程序出现局部性规律原因可以归结为以下几点： （1）程序在执行时，除了少部分的转移和过程调用指令外 ，大多数仍是顺序执行的。 （2）子程序调用将会使程序的执行由一部分内存区域转至 另一部分区域。但在大多数情况下，过程调用的深度都不超 过5。 （3）程序中存在许多循环结构，循环体中的指令被多次执 行。 （4）程序中还包括许多对数据结构的处理，如对连续的存 储空间数组的访问，往往局限于很小的范围内。 局部性原理：程序在执行时将呈现出局部性规律，即 在一较短的时间内，程序的执行仅局限于某个部分； 相应地，它所访问的存储空间也局限于某个区域。具 体地表现为： 时间的局限性，如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；某个数据被访问， 则不久以后该数据可能被再次访问。原因是在程序中 存在着大量的循环操作。 空间的局限性，一旦程序访问了某个存储单元，在 不久以后，其附近的存储单元也被访问，即程序在一 段时间内所访问的地址可能集中在一定的范围内。原 因是程序的顺序执行。 根据局部性原理，一个作业在运行之前，没有必要把全 部作业装入内存，而仅将那些当前要运行的那部分页面或段 ，先装入内存便可启动运行，其余部分暂时留在磁盘上。程 序在运行时如果它所要访问的页（段）已调入内存，便可继 续执行下去；但如果程序所要访问的页（段）尚未调入内存 （称为缺页或缺段），此时程序应利用OS所提供的请求调页 （段）功能，将它们调入内存，以使进程能继续执行下去。 如果此时内存已满，无法再装入新的页（段），则还须再利 用页（段）的置换功能，将内存中暂时不用的页（段）调出 至磁盘上，腾出足够的内存空间后，再将所要访问的页（段 ）调入内存，使程序继续执行下去。这样，便可使一个大的 用户程序在较小的内存空间中运行；也可使内存中同时装入 更多的进程并发执行。从用户角度看，该系统所具有的内存 容量，将比实际内存容量大得多，人们把这样的存储器称为 虚拟存储器。 3、虚拟存储器的定义 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑 上对内存进行扩充的一种存储器系统。实际上，用户所看到的 大容量只是一种感觉，是虚的，其逻辑容量由内存和外存容量 之和决定，其运行速度接近于内存的速度，而成本接近于外存 ，因而是一种性能非常优越的存储器管理技术，被广泛应用于 各类计算机中。 虚拟存储器的特征 1）离散性（基础） 2）多次性（一个作业分多次调入） 3）对换性（程序和数据的换入/换出） 4）虚拟性（逻辑上扩充内存容量） 4.6.2 虚拟存储器实现方式建立在离散分配基础上 1.分页请求系统： 在分页系统的基础上，增加了请求调页功能和页面置换 功能所形成的页式虚拟存储系统。它允许只装入若干页（而 非全部程序）的用户程序和数据，就可以启动运行，以后再 通过调页功能和页面置换功能，陆续把将要运行的页面调入 内存，同时把暂不运行的页面置换到外存上，置换时以页面 为单位。 2.请求分段系统： 在分段系统的基础上，增加了请求调段和分段置换功能 所形成的段式虚拟存储系统。它允许只装入若干段（而非全 部段）的用户程序和数据，就可以启动运行，以后再通过调 段功能和置换功能将不运行的段调出，同时调入将要运行的 段，置换以段为单位。 虚拟存储管理方式：为了满足用户对内 存的需要，进一步提高内存利用率，又 形成了多种虚拟存储管理方式。其方式 有： a.请求分页式管理方式 ； b.请求分段式管理方式； c.请求段页式管理方式。 动态页式管理是在分页存储管理基础上发展起来 的,增加了请求分页功能和页面置换功能实现虚拟存 储系统。 指导思想：在作业运行之前，不必把作业的整个地址 空间全部装入主存，而只要求当前需要的一部分装入 主存即可。这样，对作业地址空间，当其作业的大小 超过主存可用空间时，用页式存储管理实现虚拟存储 器管理。这个方案可以为每个用户提供一个虚拟存储 器，其虚拟空间比主存的空间大。这对编制大型程序 来说，带来了很多方便。 4.7请求分页存储管理方式(动态页式管理) 1 请求分页概念 请求分页技术当一个用户程序要调入内存时，不 是将该程序全部页面装入内存，而是只装入部分页面 到内存，就可启动程序运行，在运行的过程中，如果 发现要运行的程序或要访问数据不在内存，则向系统 发出缺页中断请求，系统在处理这个中断时，将在外 存相应的页调入内存，该程序继续运行。 为了实现请求分页，系统需要有： (1)页表机制、(2)缺页中断机构、(3)地址变换机构 (4)页面置换算法 （1）页表机制 状态位P:用于指示该页是否已调入内存，供程序访问时参考 ； 访问字段A:用于记录本页在一段时间内被访问的次数，或记 录本页最近已有多长时间未被访问，供选择换出页面时参考； 修改位M:表示该页在调入内存后是否被修改过，供置换页面 时参考； 外存地址:用于指示该页在外存上的地址，供调入页时使用 。 页号物理块号 状态位P 访问字段A 修改位M 外存地址 （2）缺页中断机构 在请求分页系统中，每当所要访问的页面不在内存时， 便产生一缺页中断，请求OS将所缺页调入内存。特点： 1)在指令执行期间产生和处理中断信号； 2)一条指令在执行期间，可能产生多次缺页中断 B: A: 指令 TO B Copy A 页面 6 5 4 3 2 1 地址变换机构 内存分配 1 最小物理块数的确定(由硬件结构和性能决定) 最小物理块数：能保证进程正常运行所需要的最小物理块数。 2 物理块的分配和置换 1)固定分配局部置换 2)可变分配全局置换 3)可变分配局部置换 3 物理块分配算法 1)平均分配 2)按比例分配 各进程的页面总和：S=(S1+S2+S3+Sn) 每个进程所能分配到的物理块：bi=(Sn/s)*m 3）考虑优先权的分配算法：一按比例；二按优先权 内存分配策略和分配算法 1、何时调入页面 1)预调页策略 系统根据作业（进程）运行的情况，预测哪些页将要运行，在 其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺 页中断。这种方法从表面上看起来很好，但系统无法预计系统中作 业的运行情况，难以实现。 2)请求调页策略 进程在执行的过程中，发现要执行的程序或处理的数据不在内 存，向系统提出调入相应程序的请求，系统响应用户的请求。 2、从何处调入页面文件区和对换区 1)系统拥有足够的对换区空间对换区 2)系统缺少足够的对换区空间对换区，文件区 3)UNIX方式对换区，文件区 调页策略 页面置换概念 抖动（或称颠簸）：如果分配给进程的存储块数 小于进程所需要的最小值，进程的运行将很频繁地产 生缺页中断的现象，即就是同一个页面频繁的在主、 外存之间入页和出页这种现象。 为了防止抖动的产生，在页面置换中，一方面要 采用合适的置换算法；另一方面在进行页面淘汰或置 换时，可以将缺页的进程锁住，不让其换出页面，从 而防止抖动的发生。另一个办法就是设置较大的内存 工作区。 4.8 页面置换算法 页面置换算法分类 (1)最佳置换算法（OPT算法） (2)先进先出算法（FIFO算法） (3)最近最久未使用（LRU）置换算法 (4) Clock置换算法 (5)其他置换算法：最少使用和页面缓冲 (1)最佳算法（OPT算法） 从内存中移出以后不再使用的页页面或选择最 长时间内不再被访问的页面予以淘汰。这样产生 的缺页中断次数最少，可获得最低的缺页中断率 。但是由于无法预知哪个页面是未来最长时间内 不被访问的，所以该算法只是一种理论上的算法. 注意：如果所访问的页还没装入内存，便将发 生一次缺页中断，访问过程中发生缺页中断的 次数就是缺页次数，而缺页次数除以总的访问 次数，就是缺页率。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 7 1 0 7 1 0 2 3 0 2 3 4 2 3 0 2 1 0 2 1 0 7 1 0 2 3 0 2 3 4 2 3 4 2 3 0 2 3 0 2 1 0 2 1 0 2 1 0 2 1 0 7 1 0 7 (2)先进先出算法（FIFO算法 ） 这种算法的基本思想是：总是先淘汰那些驻留 在内存时间最长的页面，即先进入内存的页面 先被置换掉。理由是：最先进入内存的页面不 再被访问的可能性最大。 这种算法实现起来比较简单。如下图所示 ： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 1 7 0 1 70 7 1 0 7 2 1 0 3 2 1 0 3 2 4 0 3 2 4 0 3 2 4 0 3 2 1 0 3 2 1 0 7 2 1 0 7 2 1 0 7 最早进入 最晚进入 采用FIFO算法还会产生一种奇怪现象，直观上，分 配给作业的物理块越多，进程执行时发生的缺页率就越 小，但对FIFO算法这个结论并不是绝对的。在某些情况 下，当分配的物理块数增多反而导致更多的缺页中断， 这种现象称为FIFO异常现象或称Belady现象，即在未给 进程或作业分足它所要求的页面数时，有时会出现分配的物 理块数增多，缺页次数反而增加的奇怪现象。（根本原因就 是没有考虑程序执行的动态特征） 某进程共有5页,依次访问页面的序列为 :1,2,3,4,1,2,5,1,2,3,4,5;当系统为该进程分配的物理块 数M=3时,缺页中断次数为9次,其缺页中断率为9/12=75%;但 是如果为进程分配的物理块数M=4时,缺页中断次数为10次, 其缺页中断率为10/12=83.3%; 123412555344 12341222533 1234111255 123444512345 12333451234 1222345123 111234512 123412512345 + + (“+”表示产生一次缺页中断) 当需要淘汰某一页时，算法选择离当前最近的一段时间 内最久没有使用过的页先淘汰。其理由是，如果某页被访问 了，则它可能马上还要被访问，反之如果该页很长时间未被 访问，则它在最近一段时间内也不会被访问。为了记录页面 自上次被访问以来所经过的时间,需要在页表中增加一个引用 位标志,在每次被访问后将引用位置0,重新计时。在发生缺页 中断需要调入新的页面时,通过检查页表中各页的引用位,选 择最长时间没有被访问过的页面淘汰,并且把主存中所有页面 的引用位全部清零,重新计时。因此,要实现LRU算法，需要 付出很大的系统开销。在实际系统中，经常采用LRU的近似算 法。 (3).最近最久未使用置换算法（LRU） LRU近似算法是在页表中为每一页增加一个引用位,当该页 被访问时,由硬件将它的引用位置为1,操作系统选择一个时间周期 T,每隔一个周期T,将页表中所有页面的引用位置0,这样在时间周 期T内,被访问的页面引用位为1,而没有被访问过的页面的引用位 仍为0。当产生缺页中断时,可以从引用位为0的页面中选择一页调 出,同时将所有页面的引用位全部置0。 实现：可利用一个特殊的栈来保存当前使用的各个页面的页面号 。每当进程访问某页面时，便将该页面的页面号从栈中移出，再 将它压入栈顶。因此，栈顶始终是最新被访问的页面的编号，而 栈底则是最近最久未使用页面的页面号。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 70 7 1 0 7 2 1 0 3 0 2 4 0 3 2 4 0 3 2 4 0 3 2 1 2 3 0 2 1 7 1 0 0 2 1 0 3 2 3 0 2 2 3 0 2 1 3 1 0 2 0 7 1 1 0 7 LRU近似算法 这种算法，只要在存储分块表（或页表）中设 一个“引用位”，当存储分块表中的某一页被访 问时，该位由硬件自动置1，并由页面管理软件 周期性把所有引用位置0。这样，在一个时间周 期T内，某些被访问过的页面其引用位为1，而 未被访问过的页面其引用位为0。 根据引用位的状态来判别各页面最近的使用情 况。当需要置换一页面时，选择其引用位为0的 页，如下图所示的算法。 LRU近似算法流程 图:LRU近似算法举例 返回本节 （4）最近最不常用法(LFU)：当需要淘汰时，应淘汰 被访问次数最少的页。一种简单的方法式为每一页设 置一个计数器，每当访问一页时，就把该页对应的计 数器加1，每隔一定的时间周期T,将所有计数器全部清 0。当发生缺页中断时，选择计数值最小的页，把它淘 汰，同时把所有计数器清0。 请求式分页存储管理性能分析举例 1程序设计的质量 2页面的大小 3分配的内存块数 4页面置换算法性能 图1 FIFO算法性能分析（m=3） 图2 FIFO算法性能分析（m=4 ） 图3 LRU算法性能分析（m=3） 图4 LRU算法性能分析（m=4） 返回本节 3 缺页中断率分析 (1)分配给作业的主存块数 (2)页面的大小 (3)程序编程方法 (4)页面调度算法 4.9 请求分段存储管理方式 1段表机制 2缺段中断机构 3请求式分段动态地址变换过程 4请求式分段存储管理的优、缺点 与请求分页系统类似，在分段的基础上增加请求调 段 功能和段置换功能，便可形成具有虚拟存储器功能的 请求分段系统。 为实现请求分段式存储管理,需要有一定的硬件和 相应的软件支持。所需要的硬件支持有,段表机制、缺 段中断机构以及地址变换机构等。 图:分段的逻辑地址空间 1段表 为了实现动态地址变换和存储保护，系统要为 每一个作业建立一张段表。段表是进行段调度 的主要依据。段表中的每一个表目对应着作业 地址空间的一个程序段，其一般格式为： 段 名 段 长 段的 基址 存取 方式 访问 字段 A 修 改 位 M 状 态 位 P 扩 充 位 辅 存 始 址 2缺段中断机构 在请求分段式存储管理中,当所要访问的段尚 未调入主存时,则由缺段中断机构产生一个缺段 中断信号,请求操作系统将所要访问的段调入主 存。处理过程如下: (1)空间分配; (2)修改段表; (3)新的段被装入后应让作业重新执行被中断的指令,这 时就能在主存中找到所要访问的段,可以继续执行下去 。 3请求式分段动态地址变换过 程 图4.28 请求式分段动态地址变换 4请求分段式存储管理的优缺点 请求式分段存储管理有如下优点： （1）可提供大容量的虚存 （2）允许动 态增加段的长度 （3）便于段的动态链接 （4）便于实现程序段的共享 （5）便于 实现存储保护 请求分段存储管理的缺点是进行地址变 换和实现紧 凑操作要花费处 理机时间 ， 为管理各分段要设立若干表格，需提供 额外的存储空间，而且也会像请求分页 存储管理一样出现系统抖动现 象。 一、选择题 1、页式虚拟存储管理的主要特点是（ ）。 A、不要求将作业装入到主存的连续区域 B、不要求将作业同时全部装入到主存的连续区域 C、不要求进行缺页中断处理 D、不要求进行页面置换 2、局部性有两种形式：时间局限性和（ ）。 A、指令局部性 B、数据局部性 C、空间局部性 D、以上全部 3、虚拟存储系统的基础是程序的局部性理论，此理论的基本含义是（ ）。 A、程序执行时对主存的访问是不均匀的 B、代码的顺序执行 C、变量的连续访问 D、以上全部 4、作业在执行中发生缺页中断，经操作系统处理后，应让其执行（ ）指令。 A、被中断的前一条 B、被中断的那一条 C、被中断的后一条 D、启动时的第一条 B C D B 1.在某个采用页式存储管理的系统中，现有J1、J2、J3共3个作业 同驻主存。其中J2有4个页面，被分别装入到主存的第3、4、6 、8块中。假定页面和存储块的大小均为1024字节，主存容量为 10KB。 1）写出J2的页面映像表； 2）当J