os_ch5虚拟存储器

1 第五章虚拟存储器 5 1虚拟存储器概述5 2请求分页存储管理方式5 3页面置换算法5 4抖动与工作集5 5请求分段存储管理方式 2 问题 1 大进程能否运行在小的内存空间上 2 如何在有限的内存空间上运行更多的进程 3 5 1虚拟存储器概述 1 常规存储器管理方式的特征 1 一次性 2 驻留性 4 2 局部性原理 局部性原理 principleoflocality 指程序在执行过程中的一个较短时期 所执行的指令地址和指令的操作数地址 分别局限于一定区域 还可以表现为 时间局部性 一条指令的一次执行和下次执行 一个数据的一次访问和下次访问都集中在一个较短时期内 空间局部性 当前指令和邻近的几条指令 当前访问的数据和邻近的数据都集中在一个较小区域内 5 局部性原理的具体体现程序在执行时 大部分是顺序执行的指令 少部分是转移和过程调用指令 过程调用的嵌套深度一般不超过5 因此执行的范围不超过这组嵌套的过程 程序中存在相当多的循环结构 它们由少量指令组成 而被多次执行 程序中存在相当多对一定数据结构的操作 如数组操作 往往局限在较小范围内 6 保证进程执行需要的部分程序和数据驻留内存 一段时间内进程都能顺利执行 结论 7 5 1 2虚拟存储器的定义 1 虚拟存储器的定义 所谓虚拟存储器 是指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种存储器系统 其逻辑容量由内存容量和外存容量之和所决定 其运行速度接近于内存速度 而每位的成本却又接近于外存 用户感觉上的 由实际内存和部分外存构成的存储空间称为 虚拟存储器 8 2 虚拟存储器的特征 多次性对换性虚拟性 9 实现虚拟存储器必须解决好以下有关问题 主存辅存统一管理问题 逻辑地址到物理地址的转换问题 部分装入和部分对换问题 10 虚拟存储器的概念图 11 5 1 3虚拟存储器的实现方法 1 请求分页系统 1 硬件支持 请求分页的页表机制 它是在纯分页的页表机制上增加若干项而形成的 作为请求分页的数据结构 缺页中断机构 即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断 以请求OS将所缺的页调入内存 地址变换机构 它同样是在纯分页地址变换机构的基础上发展形成的 2 实现请求分页的软件 12 2 请求分段系统 1 请求分段的段表机制 2 缺段中断机构 3 地址变换机构 13 5 2请求分页存储管理方式 在简单页式存储管理的基础上 增加请求调页和页面置换功能 请求分页要解决的问题作业是否可以装入部分运行 局部性原理运行之后 若访问到没有装入的作业 如何发现 修改进程页表增加缺页中断需要将不在内存的作业装入内存 内存已满如何装入 如何调出 置换算法 14 5 2 1请求分页中的硬件支持 1 页表机制需要在进程页表中添加若干项标志位 状态位P 内存页和外存页 修改位M访问字段A 在近期内被访问的次数 或最近一次访问到现在的时间间隔外存地址 外存位置 调入时的依据 15 2 缺页中断机构 由处理器的地址变换机构产生缺页中断 然后调用操作系统提供的中断处理例程 16 缺页中断的特殊性 缺页中断在指令执行期间产生和进行处理 而不是在一条指令执行完毕之后 所缺的页面调入之后 重新执行被中断的指令 一条指令的执行可能产生多次缺页中断 如 COPYA B若指令本身和两个操作数A B都跨越相邻外存页的分界处 则产生6次缺页中断 17 3 地址变换机构 由逻辑地址检索页表 根据对应页表项的标志位判断 若在内存中 则直接形成物理地址 如不在内存中 产生缺页中断 从对应页表项的外存地址 从外存找到该页 内存满 则选择页面换出 否则从外存直接调入内存 完成地址转换 18 演示 19 20 5 2 2内存分配 1 最小物理块数的确定是指能保证进程正常运行所需的最小物理块数 当系统为进程分配的物理块数少于此值时 进程将无法运行 进程应获得的最少物理块数与计算机的硬件结构有关 取决于指令的格式 功能和寻址方式 21 2 物理块的分配策略 在请求分页系统中 可采取两种内存分配策略 即固定和可变分配策略 在进行置换时 也可采取两种策略 即全局置换和局部置换 1 固定分配局部置换 FixedAllocation LocalReplacement 2 可变分配全局置换 VariableAllocation GlobalReplacement 3 可变分配局部置换 VariableAllocation LocalReplacemen 22 3 物理块分配算法 1 平均分配算法 将系统中所有可供分配的物理块 平均分配给各个进程 2 按比例分配算法 根据进程的大小按比例分配物理块的算法3 考虑优先权的分配算法 把内存中可供分配的所有物理块分成两部分 一部分按比例地分配给各进程 另一部分则根据各进程的优先权 适当地增加其相应份额后 分配给各进程 23 5 2 3页面调入策略 1 调入页面的时机 1 预调页策略 在发生缺页需要调入某页时 一次调入该页以及相邻的几个页 优点 提高调页的I O效率 缺点 基于预测 若调入的页在以后很少被访问 则效率低 常用于程序装入时的调页 2 请求调页策略 只调入发生缺页时所需的页面 优点 容易实现 缺点 对外存I O次数多 开销较大 24 2 从何处调入页面 1 对换区 系统拥有足够的对换区空间 这时可以全部从对换区调入所需页面 以提高调页速度 2 文件区 对换区 凡是未被修改的页面 都直接从文件区读入 而被置换时不需调出 已被修改的页面 被置换时需调出到交换区 以后从交换区调入 节省交换区空间 3 UNIX方式 由于与进程有关的文件都放在文件区 凡是未运行过的页面 都应从文件区调入 而对于曾经运行过但又被换出的页面 从对换区调入 25 3 页面调入过程 1 在磁盘上寻找所需页面 2 寻找空闲块 如果有空闲块 就用它 否则 就利用页面置换算法选择一个替换的块 把该块写到磁盘上 并相应地修改页表和存储块表 3 把所需页面读入内存 刚刚得到的空闲块 修改页表和存储块表 4 重新启动该用户进程 26 27 4 缺页率 进程运行过程中 访问页面成功次数为S 访问页面失败次数为F 进程运行过程中的缺页率为 f F F S缺页率影响因素 1 页面大小 2 进程分配的物理块的书面 3 页面置换算法 4 程序固有特性 28 5 3页面置换算法 功能 需要调入页面时 选择内存中哪个物理页面被置换 称为replacementpolicy 目标 把未来不再使用的或短期内较少使用的页面调出 通常只能在局部性原理指导下依据过去的统计数据进行预测 29 最佳算法 OPT optimal 先进先出算法 FIFO 最近最久未使用算法 LRU LeastRecentlyUsed 轮转算法 clock 最不常用算法 LFU LeastFrequentlyUsed 页面缓冲算法 pagebuffering 30 5 3 1最佳置换算法和先进先出置换算法 1 最佳置换算法 Optimal 选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 理想情况 是实际执行中无法预知的 不能实现 可用作性能评价的依据 31 置换算法举例 某程序在内存中分配三个页面 初始为空 页面走向为4 3 2 1 4 3 5 4 3 2 1 5 32 33 2 先进先出算法 FIFO 选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 并且有Belady现象 34 35 Belady现象 采用FIFO算法时 如果对一个进程未分配它所要求的全部页面 有时就会出现分配的页面数增多 缺页率反而提高的异常现象 Belady现象的描述 一个进程P要访问M个页 OS分配N个内存页面给进程P 对一个访问序列S 发生缺页次数为PE S N 当N增大时 PE S N 时而增大 时而减小 Belady现象的原因 FIFO算法的置换特征与进程访问内存的动态特征是矛盾的 即被置换的页面并不是进程不会访问的 36 Belady现象的例子 进程P有5页程序访问页的顺序为 1 2 3 4 1 2 5 1 2 3 4 5 如果在内存中分配3个页面 则缺页情况如下 12次访问中有缺页9次 37 如果在内存中分配4个页面 则缺页情况如下 12次访问中有缺页10次 38 5 3 2最近最久未使用算法 LRU LeastRecentlyUsed 1 基本思想选择内存中最久未使用的页面被置换 这是局部性原理的合理近似 性能接近最佳算法 但由于需要记录页面使用时间的先后关系 硬件开销太大 39 2 硬件支持1 寄存器为了记录某进程在内存中各页的使用情况 须为每个在内存中的页面配置一个移位寄存器 可表示为 R Rn 1Rn 2Rn 3 R2R1R0 40 图4 29某进程具有8个页面时的LRU访问情况 41 2 一个特殊的栈 把被访问的页面移到栈顶 于是栈底的是最久未使用页面 图4 30用栈保存当前使用页面时栈的变化情况 42 43 5 3 3轮转算法 clock 每页有一个使用标志位 usebit 若该页被访问则置userbit 1 置换时采用一个指针 从当前指针位置开始按地址先后检查各页 寻找usebit 0的页面作为被置换页 指针经过的userbit 1的页都修改userbit 0 最后指针停留在被置换页的下一个页 1 简单的Clock置换算法也称最近未使用算法 NRU NotRecentlyUsed 它是LRU 最近最久未使用算法 和FIFO的折衷 44 45 46 47 2 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面 1类 A 0 M 0 表示该页最近既未被访问 又未被修改 是最佳淘汰页 2类 A 0 M 1 表示该页最近未被访问 但已被修改 并不是很好的淘汰页 3类 A 1 M 0 最近已被访问 但未被修改 该页有可能再被访问 4类 A 1 M 1 最近已被访问且被修改 该页可能再被访问 48 5 3 4其它置换算法 1 最少使用 LFU LeastFrequentlyUsed 置换算法2 页面缓冲算法 PBA PageBufferingAlgorithm 49 1 最少使用算法 LFU LeastFrequentlyUsed 选择到当前时间为止被访问次数最少的页面被置换 每页设置访问计数器 每当页面被访问时 该页面的访问计数器加1 发生缺页中断时 淘汰计数值最小的页面 并将所有计数清零 50 2 页面缓冲算法 pagebuffering 被置换页面的选择和处理 用FIFO算法选择被置换页 把被置换的页面放入两个链表之一 如果页面未被修改 就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表 它是对FIFO算法的发展 通过被置换页面的缓冲 有机会找回刚被置换的页面 51 需要调入新的物理页面时 将新页面内容读入到空闲页面链表的第一项所指的页面 然后将第一项删除 空闲页面和已修改页面 仍停留在内存中一段时间 如果这些页面被再次访问 只需较小开销 而被访问的页面可以返还作为进程的内存页 当已修改页面达到一定数目后 再将它们一起调出到外存 然后将它们归入空闲页面链表 这样能大大减少I O操作的次数 52 5 3 5访问内存的有效时间 具有快表的请求分页管理方式的内存访问操作 1 被访问页在内存中 对应页表项在快表中EAT t 2 被访问页在内存中 对应页表项不在快表中EAT t t 2 t 3 被访问页不在内存中EAT t t 2 t 53 5 4抖动和工作集 抖动 颠簸 Thrashing 页面在内存与外存之间频繁调度 以至于调度页面所需时间比进程实际运行的时间还多 此时系统效率急剧下降 甚至导致系统崩溃 这种现象为颠簸 演示 54 原因 a页面淘汰算法不合理b分配给进程的物理页面数太少 55 解决方法工作集模型 56 1 常驻集 residentset 常驻集指虚拟页式管理中给进程分配的物理页面数目 57 常驻集与缺页率的关系 每个进程的常驻集越小 则同时驻留内存的进程就越多 可以提高并行度和处理器利用率 另一方面 进程的缺页率上升 调页的开销增大 进程的常驻集达到某个数目之后 再给它分配更多页面 缺页率不再明显下降 该数目是 缺页率 常驻集大小 曲线上的拐点 curve 58 常驻集大小的确定方式 固定分配 fixed allocation 常驻集大小固定 各进程平均分配 根据程序大小按比例分配 优先权可变分配 variable allocation 常驻集大小可变 按照缺页率动态调整 性能较好 增加算法运行的开销 59 2 工作集策略 workingsetstrategy 1968年由Denning提出 目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小 工作集是一个进程执行过程中所访问页面的集合 可用一个二元函数W t 表示t是执行时刻 是一个虚拟时间段 称为窗口大小 windowsize 它采用 虚拟时间 单位 阻塞时不计时 大致可以用执行的指令数目 或处理器执行时间来计算 工作集是在 t t 时间段内所访问的页面的集合 W t 指工作集大小即页面数目 演示 60 61 工作集的性质 随 单调递增 W t W t a 其中a 0 利用工作集进行常驻集调整的策略 记录一个进程的工作集变化 定期从常驻集中删除不在工作集中的页面 总是让常驻集包含工作集 62 5 5请求分段存储管理方式 5 5 1请求分段中的硬件支持段表机制需要在进程段表中添加若干项 标志位 存在位 presentbit 修改位 modifiedbit dirtybit 增长位 该段是否增长过 在虚拟页式中没有该位 访问统计 如使用位 usebit 存取权限 如读R 写W 执行X外存地址 63 2 缺段中断机构