第7章虚拟内存管理ppt课件.ppt

第七章虚拟内存管理 对于需要将程序一次性装入内存才能运行的存储管理方案来说 其缺点是明显的 一方面 当一个参与并发执行的进程运行时 其整个程序必须都在内存 若进程的程序比内存可用空间还大 该程序将无法装入内存运行 另一方面 程序被装入内存后 便一直驻留在内存直至程序运行结束才释放内存 这就会使一些需要尽快运行的作业无法被装入运行 更严重的是 若进程因I O而长期等待或程序暂时不执行的时候 它将一直占有内存资源 导致内存不能得到充分的利用 虚拟内存管理就是为了解决上述问题而产生的 这种技术把内存和外存结合起来 为用户程序提供一个容量远大于物理存储器的虚拟存储空间 用户程序可以先只装入一部分就开始执行 以后根据执行的具体情况再依次请求装入剩下的部分 直至整个程序都执行完毕 这就从逻辑上扩充了内存容量 有效地解决了上述问题 本章介绍虚拟内存管理的相关知识 首先介绍虚拟内存管理的一些基本概念 然后分别阐述几种典型的虚拟内存管理方法 请求分页管理方式 请求分段管理方式和请求段页式管理方式 2020 3 27 2 7 1虚拟存储基本概念7 2请求分页管理方式7 3请求分段管理方式7 4请求段页式管理方式 2020 3 27 3 7 1虚拟存储基本概念 7 1 1虚拟存储的引入7 1 2虚拟存储实现技术 2020 3 27 4 7 1 1虚拟存储的引入 在上一章中 我们介绍的分配管理技术是针对实际物理内存空间的 这一类管理技术具有两个特性 1 程序的装入是一次性的 即在程序运行之前 要求一次性地将程序所有内容都装入内存 而不管程序的执行目前是否需要这些全部内容 2 程序被装入内存后 便一直驻留在内存直至程序运行结束 也不管程序的执行目前是否真正需要某一内容 一次性和驻留性这两个特性使得这一类管理技术表现出内存利用率低 系统吞吐量小等明显缺点 因此 我们就自然地思考 如果可以否定一次性和驻留性 也许可以提出一种改进的存储管理技术 以提高内存利用率和系统吞吐量 程序的一次性和驻留性是否可以否定 程序局部性原理回答了这一问题 它说明程序的一次性与驻留性都是不必要的 这样就可以提出改进的存储管理技术 即虚拟存储 2020 3 27 5 7 1 1虚拟存储的引入 一 程序局部性原理早在1968年 P Denning就在长期的研究中发现了程序的局部性原理 它是指程序在执行过程中的一个较短时间内 所执行的指令地址会较集中地出现在某一部分 呈现出程序局部性现象 2020 3 27 6 7 1 1虚拟存储的引入 程序局部性现象说明 在一个较短的执行时间间隔内 程序只执行程序的一部分 而不会执行程序的全部内容 同时 执行访问的存储空间也局限于某一区域 而不会遍历所有存储空间 这就是程序局部性原理 程序局部性原理体现在时间局部性和空间局部性两个方面 1 时间局部性 2 空间局部性 2020 3 27 7 7 1 1虚拟存储的引入 1 时间局部性时间局部性是指程序中的一条指令执行后可能会再次执行 或某个数据被访问后也可能再次被访问 这主要是由程序中存在大量的循环操作导致的 2 空间局部性空间局部性是指程序在一段时间内所访问的地址可能集中在 定的范围内 这主要是由于程序中存在大量的顺序执行 程序局部性原理可以说明 程序的一次性与驻留性都是不必要的 2020 3 27 8 7 1 1虚拟存储的引入 二 虚拟存储的基本思想因为内存空间的有限性 系统无法全部装入比它大的程序并执行相应进程 如果系统要运行比内存空间大的进程 可以在进程执行时只调入当前所需要的部分程序 而不用把全部程序都调入内存 以后在执行的过程中根据需要装入其它部分 程序运行过程中暂不需要的部分程序也没有必要始终驻留在内存中 可以将它们移出到外存以释放空间来装入其它需要的程序部分 这样 就可以将内存和比内存大的多的外存两者结合起来使用 利用调入 调出等操作的支持 形成了一个比内存空间大得多的 逻辑的虚拟内存空间 这就是虚拟存储器 总之 虚拟存储是一种实现虚拟存储器的技术 这一技术通过离散化存储 以程序的子部分为单位分配和装入内存 请求调入 即根据进程执行的需要来调入某些程序子部分 置换 即将暂不需要的程序子部分调出到外存以释放空间 等功能 来构造一个比内存空间大得多的 虚拟内存空间 该空间的逻辑容量由外存和内存容量之和决定 而运行速度接近于内存速度 从而从逻辑上扩充了内存容量 2020 3 27 9 7 1 1虚拟存储的引入 三 虚拟存储的特性虚拟内存管理技术是在内存存储管理技术的基础上改进得到的 它与上一章叙述的物理内存存储管理技术之间既有继承 更体现出明显的区别 从中可以看出虚拟存储具有程序分配方式的非连续性 程序调入方式的多次性 程序驻留方式的交换性以及总体表现出的存储管理虚拟性等特性 表7 1虚拟内存存储管理与物理内存存储管理的比较 2020 3 27 10 7 1 2虚拟存储实现技术 虚拟存储在实现时 首先需要将程序逻辑地址空间离散化 即将程序划分为若干子部分 并以程序的子部分为单位来分配内存 因此 虚拟存储的实现必须以非连续分配管理方式为基础 具体而言 可以将程序划分为页 段或段页结合 然后请求调入 置换等功能都将基于相应的非连续分配管理方式来具体实现 至此 虚拟存储器的实现技术可以分为三种 采用以分页管理方式为基础的请求分页管理方式以分段管理方式为基础的请求分段管理方式以段页式管理方式为基础的请求段页式管理方式 2020 3 27 11 7 1 2虚拟存储实现技术 一 请求分页管理方式请求分页管理方式是在分页管理方式的基础上 增加了请求调页 页面置换等功能而形成的 它允许只装入若干页面的用户程序和数据 便可启动运行 以后 再通过调页功能和页面置换等功能 陆续地把将要运行的页面调人内存 同时把暂不运行的页面换出到外存上 置换时以页面为单位 请求分页管理方式需要系统提供的硬件机制主要有 请求分页的页表机制 以分页管理方式中的页表机制为基础 增加若干字段来构造 用于记录任一页面在内存的位置 外存的位置 是否被修改等信息 缺页中断 每当下一步要访问的页面尚未被调入内存时 便产生一个缺页中断 以请求系统调入所缺的页面 地址变换机制 在请求分页管理方式中 用于实现程序逻辑地址到内存物理地址的转换 2020 3 27 12 7 1 2虚拟存储实现技术 二 请求分段管理方式请求分段管理方式是在分段管理方式的基础上 增加了请求调段 分段置换等功能而形成的 它允许开始时只装入若干段的用户程序和数据 即可启动运行 以后 再通过调段功能和分段置换等功能 将暂不运行的段调出 同时调入即将运行的段 置换时以段为单位进行 请求分段管理方式需要系统提供的硬件机制主要有 请求分段的段表机制 以分段管理方式中的段表机制为基础 增加若干字段来构造 用于记录一个程序的任一段在内存的位置 外存的位置 存取方式 是否被修改等信息 缺段中断 每当下一步要访问的段尚未被调入内存时 便产生一个缺段中断 以请求系统调入所缺的段 地址变换机制 用于实现请求分段管理方式下的从程序逻辑地址到内存物理地址的转换 2020 3 27 13 7 1 2虚拟存储实现技术 三 请求段页式管理方式请求段页式管理方式结合了请求分页和请求分段两种管理方式的优点 外存中的程序用分段方法来分配和管理 而内存中的进程则用分页方法来分配和管理 使得一个段可以装载到若干不连续的空闲物理块中 请求段页式管理方式是在段页式管理方式的基础上 增加了请求调页 请求调段 段 页置换等功能 请求段页式管理方式需要系统提供的硬件机制有 请求分页的页表机制 请求分段的段表机制 缺段中断机构 地址变换机构等 2020 3 27 14 7 2请求分页管理方式 7 2 1请求分页分配基本思想7 2 2请求分页分配管理7 2 3页面分配7 2 4页面置换7 2 5抖动处理 2020 3 27 15 7 2 1请求分页分配基本思想 请求分页分配方式的基本思想可描述为如下过程 1 首先 内存空间被划分成若干等长的物理块 并对块编号 同时 程序仍然被分为若干与物理块等长的页面 也对其编号 2 在进程开始执行之前 不是将程序包含的所有页面一次性地全部装入内存 而是将进程当前需要的一部分页面装入内存 使得进程可以开始执行 3 在进程运行过程中 如果所访问的页面在内存 则对其管理与分页存储管理情形相同 若发现所要访问的数据或指令不在内存 便会产生缺页中断 到外存找到包含所需数据或指令的页面 并动态地将其装入到内存的空闲块中 在动态装入一个页面时 若发现内存无空闲块或分配给该进程的物理块已用完 则从已在内存的若干页面中选出一个将其淘汰 释放所占的物理块后将新的页面装入其中 进程继续运行 被淘汰的页面如果刚才在内存被修改过 还需要回写到外存 以保留最新的内容 系统反复进行这样的过程 直至进程运行结束 从上面的基本过程可以看出 请求分页分配方式在许多方面与分页分配方式是一致的 但由于允许程序装入否定了一次性 这种方式显得更加复杂 2020 3 27 16 7 2 1请求分页分配基本思想 1 页表需要提供一个页表机制来记录任一页面在内存的位置 外存的位置 是否被修改等信息 这一页表比分页分配管理中的页表要复杂 需要重新设计 2 页面分配策略内存中允许装入多个进程 每一进程占有一部分物理块 问题是对这多个进程 为每一进程分配多少物理块才合适 采用何种分配方式才更合理 即需要一个合适的页面分配策略 3 缺页中断进程运行若发现所要访问的数据或指令不在内存 便会产生缺页中断 到外存寻找包含所需数据或指令的页面 这时 缺页中断该如何处理 2020 3 27 17 7 2 1请求分页分配基本思想 4 地址变换一个页面不管是一开始就被装入内存 还是以后动态地装入内存 都需要解决地址变换问题 5 页面置换在动态装入一个页面时 若发现内存当前无空闲块或分配给该进程的物理块已用完 则需要从已在内存的若干页面中选出一个将其淘汰 以释放所占的物理块 这时 需要考虑 具体在什么范围内选择页面 并采用何种算法来实现页面的淘汰 这就需要设计出合适的页面置换算法 6 抖动处理请求分页分配方式由于否定了程序装入的一次性 程序可以在装入一部分页面后就开始运行 这时 可能会遇到缺页的问题 若缺页过多 就会对系统的性能产生不好的影响 抖动就是由缺页过多导致的一种主要的不良后果 这时需要考虑系统应该提供怎样的抖动处理方法 2020 3 27 18 7 2 1请求分页分配基本思想 请求分页分配管理需要用到页表 页面分配策略 缺页中断 地址变换 抖动处理等的支持 这些管理手段之间的逻辑关联是 在为程序分配内存时 需要用到页面分配策略 在程序装入时 需要用到页表和地址变换机制的支持 在进程运行时 需要用到页表 地址变换 缺页中断以及页面置换的支持 地址变换需要用到页表 页面置换需要由缺页中断启动 并需要页表和地址变换的支持 页面分配策略也与页面置换相关 系统出现的抖动现象又与页面分配策略和页面置换等密切相关 2020 3 27 19 7 2 1请求分页分配基本思想 为程序分配内存阶段 程序装入阶段 图7 2请求分页分配管理的关键技术 进程运行阶段 页面分配策略 页表 地址变换 缺页中断 页面置换 抖动 2020 3 27 20 7 2 2请求分页分配管理 请求分页分配管理与分页分配管理在管理手段上有相同之处 如同样使用内存空间使用表来描述内存所有物理块目前使用状况 为内存分配服务 我们在下面着重介绍需要专门设计的地方 由请求分页存储分配的思想可以看出 它是利用软硬件相结合的方式来实现存储管理的 因此协调好软硬件之间的功能至关重要 为实现其存储管理功能 系统必须提供必要的硬件支持 其中最重要的是页表 缺页中断和地址变换机制 2020 3 27 21 7 2 2请求分页分配管理 一 页表机制页表是请求分页分配管理中最重要的一种数据结构 其作用是将程序地址空间的逻辑地址转换成内存空间的物理地址 因为请求分页分配方式允许只将程序的一部分调入内存 还有一部分放在外存磁盘空间上 所以在构造请求分页分配方式下的页表时 需要在分页分配方式的页表的基础上 增加一些字段 在请求分页分配管理中 页表需要包括 页号 中断位 内存块号 外存地址 访问位 修改位等字段 如图7 3所示 图7 3请求分页分配管理中的页表结构 2020 3 27 22 7 2 2请求分页分配管理 页号和内存块号 定义同分页存储管理 这两个字段为进行地址变换提供必要的信息 中断位 驻留位 内存标志位 用来表示该页是在内存还是在外存 当需要访问一个页面时 根据该位来判断要访问的页面是否在内存 若不在内存则产生缺页中断 该位取值为0或1 例如 1表示该页己在内存 0表示该页不在内存 外存地址 用来指明该页在外存中的地址 供页面调入和保存时使用 所以通常记录的是外存物理块号 访问位 用来记录该页面在一段时间内被访问的次数 或是最近已有多长时间未被访问 访问位用来支持页面置换算法 决定淘汰哪一页 只要该页中的任一指令或数据被访问过一次 该位值就加l 一般情况下 为便于处理 该位也可用一位来表示 当该位取值大于0表示该页被访问过 若该位取值为0 表示该页未曾被访问 修改位 用于记录该页面在被调入内存后是否被修改过 该位的值决定了在该页面被置换时是否需要回写到外存 由于内存中的页面在外存上都有相应的副本 因此 为减少磁盘写的次数 若一个内存页面末被修改 则在该页面被调出时就不需要将该页面的内容写到外存 反之 若该页面被修改 则必须将该页面的当前内容重新写到外存上 覆盖外存对应的物理块 以完成最新内容的保存 该位取值为0或1 2020 3 27 23 7 2 2请求分页分配管理 二 缺页中断机制 1 缺页中断基本思想在请求分页存储管理中 每当所要访问的页面不在内存 便要产生一个缺页 PageFault 中断 操作系统接到此中断信号后 就运行缺页中断处理程序 根据页表中给出的外存地址 将该页调入内存 使进程继续运行下去 缺页中断是一个比较特殊的中断 与一般的中断相比 它同样需要经过保存CPU现场 转缺页中断处理程序进行处理 恢复CPU现场等几个环节 但也体现出明显的特殊之处 其特殊性主要体现在如下两个方面 它在指令的执行期间就产生和处理中断 程序执行过程中 一条指令的执行可能产生多个缺页中断 例如 假设要执行指令MOVEXTOY 若指令本身跨了两个页面 X和Y又分别各是一个数据块 其中X跨了两个页面 Y也跨了两个页面 这样执行该条指令则要产生6次缺页中断 如图7 4所示 2020 3 27 24 7 2 2请求分页分配管理 图7 4产生6次缺页中断的指令 2020 3 27 25 7 2 2请求分页分配管理 三 地址变换机制请求分页存储管理的地址变换机制 是在分页分配管理的地址变换机制基础上 增加了实现虚拟存储的缺页中断 页面调入调出等功能而形成的 假设地址变换机制中设置了快表 对给定的一个逻辑地址 页号 页内偏移量 其地址变换过程为 首先在快表中查找页表 若在快表中找到所需要的页表项时 就将快表中相应的块号与逻辑地址中的页内位移量拼接得到物理地址 并修改页表项中访问位的值 对于写指令还要改变修改位的值 如果快表中没有所需的页表项 则到内存中去查找页表 从对应页表项中的中断位判断该页面是否已在内存 如果该页面在内存中 此时需将此页的页表项写入快表 若快表已满 应按某种算法置换出快表中的某一页表项 然后再将新页表项写入快表 同时形成物理地址 即用相应的块号与逻辑地址中的页内位移量拼接得到物理地址 并修改页表项中访问位的值 对于写指令还要改变修改位的值 如果该页面尚末调入内存 产生缺页中断 然后将之从外存调入 如果内存中没有空闲块 则由操作系统根据页面置换算法淘汰某个页面 然后再将该页面调入 接着 修改页表 将此页的页表项写入快表 最后再形成物理地址 2020 3 27 26 7 2 2请求分页分配管理 图7 5请求分页存储管理的地址变换过程 2020 3 27 27 7 2 4页面置换 7 2 4 1页面置换范围 1 局部置换局部置换是指 当一个进程的运行发生缺页中断时 操作系统只从该进程在内存的页面中选择出一个页面进行淘汰 释放出对应的物理块 而不能用到别的进程获得的物理块 即被置换的页面只能是该进程本身的页面 2 全局置换全局置换是指 当一个进程的运行发生缺页中断时 操作系统可以从所有当前位于内存的页面中选择出一个页面进行淘汰 释放出对应的物理块 而不管被选中的页面是否属于该进程 即被置换的页面可以是任何一个进程的页面 2020 3 27 28 7 2 4页面置换 7 2 4 2典型页面置换算法页面置换算法的作用是 在需要置换页面时 决定应该置换出哪一个页面 以保证进程能正常运行 你会如何设计页面置换算法 2020 3 27 29 7 2 4页面置换 一 最佳置换算法 OPT 最佳置换算法 OPT Optimal 也叫理想淘汰算法 最佳页面算法等 是由Belady于1966年提出的一种理想状态下的页面置换算法 其基本思想是 总选择那些以后不再需要的或最远的将来才会用到的页面进行淘汰 显然 这种页面置换算法的效果最好 缺页率 即产生缺页中断的次数与访问的页面总数之比 也最低 但它需要事先精确地知道每一页面的下次访问时间 也就是说要求系统具有预测未来的能力 因此实际上是无法做到的 仅具有理论上的意义 但正因为它的效果是理论上最好的 所以可将之作为其它置换算法的评价基准 如果一个页面置换算法的缺页率与最佳置换算法的相近 则说明该算法选择适当 2020 3 27 30 7 2 4页面置换 下面是一个采用最佳置换算法的例子 设一进程的页面访问序列为 4 3 2 1 4 3 5 4 3 2 1 5 该进程事先已经分配到3个物理块 进程运行时先将4 3 2前三个页面装入内存 以后 访问次数t 1时 进程需要访问页面1 但它目前不在内存 产生1次缺页中断 根据最佳置换算法 将页面2淘汰 这是因为将在很长时间内用不到页面2 而页面4和页面3会在紧接的访问中被用到 依此类推 完成所有的页面置换 如表7 2所示 表中 表示产生了1次缺页中断 进程访问所有页面后 共产生了4次缺页中断 即缺页率为4 9 表7 2最佳置换算法 2020 3 27 31 7 2 4页面置换 二 先进先出置换算法 FIFO 先进先出置换算法 FIFO FirstInFirstOut 的基本思想是 总选择进入内存时间最长的页面并淘汰之 这是最早出现的 可用于实际的置换算法 该算法在实现时 可以将所有页面按照进入内存的次序排成一个队列 并设置一个替换指针指向队头页面 当需要进行页面淘汰时 替换指针指向的即为当前最先进入内存的页面 该页面被选中淘汰 然后修改指针 当调入一个新页面之后 将它排入队尾 在一定程度上 因为程序结构的顺序性 通常最早调入内存的页面以后不再被访问的可能性最大 因此FIFO置换算法是有其合理性的 但实际情况并不完全如此 例如 经常会出现某些页面 由于含有全局变量 常用函数等程序段 它们在进程的整个生命周期中会被频繁访问 根据FIFO置换算法 这些页面会被反复调入 调出 这显然是不合理的 2020 3 27 32 7 2 4页面置换 仍用上面的页面访问序列 采用FIFO置换算法的页面置换情况如表7 3所示 进程访问所有页面后 共产生了6次缺页中断 即缺页率为6 9 表7 3先进先出置换算法 2020 3 27 33 7 2 4页面置换 三 最近最少使用置换算法 LRU 1 LRU置换算法的思想最近最少使用置换算法 LRU LeastRecentlyUsed 也称最近最久未使用算法 是最佳置换算法的一种近似算法 根据局部性原理 刚被访问过的页面 它马上还要被访问的可能性很大 反之 如果某一页面在过去一段时间里不曾被访问 则它在最近的将来一段时间内被使用的可能性也不会大 这样 就可以用 最近的过去 作为 最近的将来 的近似 LRU算法的基本思想是 在产生缺页时 总选择距现在开始的过去最长时间内没有被访问过的页面 并将其先调出 2020 3 27 34 7 2 4页面置换 仍用上面的页面访问序列例子 采用LRU置换算法得到的页面置换情况如表7 5所示 进程访问所有页面后 共产生了7次缺页中断 即缺页率为7 9 表7 5最近最少使用置换算法 2020 3 27 35 7 2 5抖动处理 抖动 又称颠簸 是指由于系统缺页过于频繁而导致的一种反复调入调出页面的现象 抖动现象发生时 页面在内存与外存之间被频繁地调入 调出 也就是说 系统的大多数时间都在完成页面的调入 调出 而真正用于进程任务的时间相对过少 抖动严重影响了系统的效率 甚至可能使系统全面崩溃 因此操作系统应该具有相应的处理功能 2020 3 27 36 7 3请求分段管理方式 7 3 1请求分段分配基本思想7 3 2请求分段分配管理 2020 3 27 37 7 3 1请求分段分配基本思想 请求分段管理方式是在分段管理方式的基础上 增加了请求调段 分段置换等功能而形成的 请求分段分配方式的基本思想可描述为如下过程 程序根据自身的逻辑结构分为若干段 段有段号 内存空间根据段来动态划分 在进程开始执行之前 允许只装入若干段的用户程序和数据 即可启动运行 在进程运行过程中 如果所访问的段在内存 则对其管理与分段存储管理情形相同 若发现所要访问的段不在内存 便会产生缺段中断 到外存找到该段并动态地将其调入内存中 在调入一个段时 先检查内存中是否有足够的空闲空间 若有则直接将该段调入 否则 将内存中的一些段淘汰 释放所占内存空间后将新的段装入其中 进程继续运行 被淘汰的内存段若被修改过 须将修改的段写入外存 以保留最新的内容 系统反复进行这样的过程 直至进程运行结束 请求分段分配方式在许多方面与分段分配方式是一致的 由于增加了虚拟存储的实现 它比分段分配方式将更为复杂 但其虚拟存储的实现又类似于请求分页管理 因此可以借鉴请求分页管理技术来实现 2020 3 27 38 7 3 1请求分段分配基本思想 实现请求分段分配方式需要专门解决的问题有 请求分段的段表机制 需要提供一个段表机制来记录任一段在内存的位置 外存的位置 是否被修改等信息 这一段表比分段分配管理中的段表要复杂 需要重新设计 缺段中断 每当下一步要访问的段尚未被调入内存时 便产生一个缺段中断 以请求系统调入所缺的段 这时 缺段中断该如何处理 地址变换机制 用于实现请求分段管理方式下的从程序逻辑地址到内存物理地址的转换 2020 3 27 39 7 3 2请求分段分配管理 一 请求分段的段表机制在请求分段分配管理中 以段为单位进行内存和外存之间的信息交换 相应的段表机制以分段管理方式中的段表机制为基础 增加若干字段来构造 用于记录一个程序的任一段在内存的位置 外存的位置 存取方式 是否被修改等信息 请求分段的段表需要包括 段号 段长 段首地址 存取方式 访问位 修改位 存在位 增补位 外存始址等字段 如图7 12所示 图7 12请求分段分配管理中的段表结构