虚拟存储器(2)ppt课件

从根本上提高内存利用率的手段 页式存储管理 分页存储管理的基本思想 一 进程图像等分成若干页面内存按同样大小等分成若干页框例 32位机器 配置1G内存 页面大小4K 问 进程虚地址空间占多少页 内存有多少页框 分页存储管理的基本思想 二 一个页面占据一个页框同一个进程在主存中占据的页框不必连续页表 登记进程的页面在主存占据的页框号 每个进程拥有一张页表 进程运行时页表全部驻留主存问 页表何时被创建 系统何时会对页表进行修改 用页表进行地址映射 例 设某台计算机的页面长4k 右图是现运行进程pa的页表 问 1 逻辑地址为5K的代码在内存中的起始地址2 页表有多少表项 占多少内存 实现地址变换的硬件逻辑 假设进程执行时需要访问逻辑地址n 简单分页系统的地址变换过程如下 整个过程由硬件的地址变换机构自动完成 将逻辑地址n分成页号p和页内位移量s 根据页号查找页表 页表起始地址a存放在页表控制寄存器中 确定包含n单元的页面在内存中的存放位置 页框号t 3用页框号t取代逻辑地址中的页号部分p 实现下面的计算 物理地址 页框号 页长 页内位移 之后将结果送MAR访问主存 解决页表容量过大的问题 二级页表IntelPentium sSolution 总的思路 将页表进行分页 用页目录中的表项记录页表在主存中位置 页目录 页表的页表页目录占一个页框有了二级页表之后 页表不用占据连续的存储空间 甚至不用100 驻留内存请画出最小的程序的二级页表最重要的 页表的内容 容量 大大地减少了 MMU支持二级页表时逻辑地址 MMU支持二级页表时逻辑地址分三部分页目录号页号页内偏移量 例 长度为128M的进程之页表长度为128k字节 32页求进程的二级页表 31张页表不必连续存放在内存只有进程最近一段时间内使用的页表才需要驻留内存 解决了页表内存消耗过大的问题 页表内存消耗巨大问题的解决方案之二 PowerPC sSolution 反向页表 InvertedPageTable 反向页表中每一项对应于一个主存页而不是虚页 在这种方法中 系统维护一张反向页表 在这张表中每一项对应于一个主存页而不是虚页 系统使用一个简单的散列 hash 函数将虚地址的页号部分映射到散列表中的某一项 其中登记着一根指向反向页表表项的指针 由于散列表和反向页表中的每一项对应于一个主存页框 因此 无论有多少个进程 支持多少虚页 页表 反向页表 的容量是固定的 512M的主存只需要128K个反向页表表项 熟悉散列表的读者一定知道 多个页号的hash函数运算结果可能会相同 即多个虚地址页面可能会被映射到同一个主存页框 系统可以利用链接管理技术来处理hash冲突 只要hash函数选择的好 同一个hash结果对应的反向页表链会很短 只有一到两项 空闲内存区的管理 位示图 bitmap 操作系统使用位示图登记内存中物理页面的分配情况 内存的每个物理页面对应于一个bit 0相应的页框空闲可供使用 1该页框中已存入其它进程的逻辑页面 当进程需要内存空间时 操作系统扫描位示图寻找值为0的bit 并将这些bit对应的主存页框分配给该进程 进程运行结束或出于某种原因释放内存空间时 操作系统找到所释放的所有页框 在bit图中将它们对应的bit改为0 离散的代价 访存时间加倍 简介 原则上 每个虚存访问可能引起两次主存访问 一次取相应的页表项 一次取想要的数据 因此简单的页式存储方案会导致存储器访问时间加倍 为克服这个问题 系统可以在CPU和主存之间配一组特殊的高速cache 用来存放现运行进程的页表表项 这种Cache是联想寄存器 它可以按内容进行并行查找 当输人端有一个输人值 页号p时 其中存放页号为p的那一项立即被选中 并输出其变换值 页框号t Cache的访问速度远远高于主存 它的引入大大提高了地址变换的速度 但由于成本关系 价格非常昂贵 联想寄存器不可能做得很大 一般而言 联想寄存器中只能够存放CPU最近用过的少数页表表项 随着进程的运行 系统会经常运行置换算法以淘汰联想寄存器中不经常使用的部分 配备了联想寄存器的系统在每次地址变换时 根据页式地址中的页面号同时查找主存页表和联想寄存器 转换后备缓冲区TLB 若TLB中存在相匹配的页号 系统可以直接从TLB中读出页框号送MAR以形成物理地址 否则 系统等待主存页表的查询结果 页框号 形成物理地址的同时将页框号送TLB 若TLB已满 需首先运行置换算法淘汰某个页面 内存访问时间加倍问题的解决 转换后备缓冲区 TLB CPU和主存之间的联想寄存器 作为高速cache 存放CPU在最近一段时间内经常访问的页表表项 TLB高速缓存的硬件特性 按内容查表 并发地用待查找的内容与每个表项匹配 若命中 一个访问周期内就可以得到逻辑页面在主存中的地址若不命中 等待左侧页表的查询结果 形成物理地址的同时将页框号送TLB 保证TLB始终存放CPU最近使用的页面页面置换算法注 TLB又称为快表 或联想寄存器组 虚拟存储器 思想来源 实际上绝大多数进程在运行时并非用到全部程序 因此 进程在运行时图像全部驻留主存显然是不必要的 1961年英国曼彻斯特大学提出虚拟存储器的概念 使用硬盘中的swap分区作为主存的辅助存储器 存放所有进程的图像 主存中只存放CPU最近需要使用的信息 用页式管理实现虚拟存储 缺页 缺页事件 CPU所访问的信息内存中不存在计算机使用中断处理缺页事件硬件 当前指令访问的数据 或CPU下一条待执行的指令不在内存 产生缺页中断软件 操作系统 中断处理程序在swap分区中找到包含CPU所需访问的数据 指令 的逻辑页面 将其装入内存页框 完整的页表的结构 1 状态位P 指示该页是否已调入内存 2 访问字段A 记录本页在一段时间内被访问的次数或最近未被访问的时间 3 修改位M 表示该页在调入内存后是否被修改过 若修改过 则换出时需重写至外存 4 外存地址 指出该页在外存上的地址 缺页中断的产生 地址变换查页表时 发现表项的状态位为0 地址变换机构 开始 页号 页表长度 CPU检索快表 N N Y 页表项在快表中 访问页表 页在内存 修改访问位和修改位 修改页表 形成物理地址 地址变换结束 越界中断 程序请求访问一页 Y N 缺页中断处理 Y 页面置换 缺页中断时 若此时无空页 操作系统必须从主存中选择一页进行淘汰以便为即将被调人的页让出空间 这就是页面替换 也称页面置换 替换算法 目标 淘汰最近最不可能访问的页1最优页面替换算法 Optimal OPT选择下次访问距当前时间最长的页面进行置换 无法实现 2FIFO3最近最久未使用算法 LRU选择主存页面中上次访问时间距今最长的页面予以淘汰 硬件实现的代价太大 4其它 最佳置换算法例 假定系统为某进程分配了3个物理块 进程运行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5 开始时3个物理块均为空 计算采用最佳置换页面淘汰算法时的缺页率 7 12 注 实际上这种算法无法实现 因页面访问的未来顺序很难精确预测 但可用该算法评价其它算法的优劣 先进先出置换算法例题 1 假定系统为某进程分配了3个物理块 进程运行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5 开始时3个物理块均为空 计算采用先进先出页面淘汰算法时的缺页率 9 12 先进先出置换算法例题 2 假定系统为某进程分配了4个物理块 进程运行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5 开始时4个物理块均为空 计算采用先进先出页面淘汰算法时的缺页率 10 12 先进先出置换算法 注 1 该算法的出发点是最早调入内存的页面 其不再被访问的可能性会大一些 2 该算法实现比较简单 对具有线性顺序访问的程序比较合适 而对其他情况效率低 3 先进先出算法存在一种异常现象 即在某些情况下会出现分配给的进程物理块数增多 缺页次数有时增加 有时减少的奇怪现象 这种现象称为Belady现象 如上几例 LRU最近最久未使用算法 选择到当前时间为止访问次数最少页面淘汰 该算法要求为每页设置一个访问计数器 每当页被访问 该页的访问计数器加1 发生缺页中断时 淘汰计数值最小的页面 并将所有计数器清零 最近最久未使用算法 注 该算法的出发点 如果某个页面被访问了 则它可能马上还要访问 反之 如果很长时间未被访问 则它在最近一段时间也不会被访问 该算法的性能接近于最佳算法 但实现起来较困难 因为要找出最近最久未使用的页面 必须为每一页设置相关记录项 用于记录页面的访问情况 并且每访问一次页面都须更新该信息 这将使系统的开销加大 所以在实际系统中往往使用该算法的近似算法 该算法的近似算法实现 方法1 利用一特殊的栈保存当前使用的页号 每当进程访问某页面时 把被访问页面移到栈顶 于是栈底的页面就是最久未使用的页面 方法2 为每个页面设立一个寄存器记录页面的访问情况 每当进程访问某页面时 将该页面对应寄存器的最高位置1 系统定期将寄存器右移一位并将最高位补0 于是寄存器数值最小的页面是最久未使用的页面 最近最久未使用算法例 假定系统为某进程分配了3个物理块 进程运行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5 开始时3个物理块均为空 计算采用最近最久未使用页面淘汰算法时的缺页率 10 12 简单Clock置换算法 NRU NotRecentlyUsed算法 该算法是LRU和FIFO的折衷 该算法要求为每页设置一个访问位 并将内存中的所有页链接成一个循环队列 当某页被访问时 系统将其访问位设置为1 置换时采用一个指针 从当前指针位置开始按序检查各页 若访问位为0则选择该页换出 若访问位为1则将其设置为0 最后指针停留在被置换页的下一页上 替换指针 2 改进型Clock置换算法 该算法即考虑页面的使用情况 又考虑置换代价 被淘汰页面以修改位为0者为佳 改进型Clock置换算法的细节 由访问位A和修改位M可以组成下面四种类型的页框 1类 A 0 M 0最近没有被访问 也没有被修改 2类 A 0 M 1最近没有被访问 但被修改 3类 A 1 M 0最近被访问过 但没有被修改 4类 A 1 M 1最近被访问过 被修改 改进型Clock置换算法的实现 显然第1类页面是最佳淘汰页面 应尽量避免淘汰第4类页面 算法执行的步骤如下 1从current指针开始扫描内存页框 寻找第1类页面予以替换 2如果第1步操作失败 重新扫描 寻找第2类页面 对扫描过程中途径的所有页帧A位清0 3如果第2步也失败 指针将回到原来的位置 并且所有的页帧使用位均为0 重复第1步 必要时重复第2步 这一次一定可以找到淘汰页 最近被访问过的页面 4 页面缓冲算法 该算法是对FIFO算法的发展 通过建立置换页面的缓冲 就有机会找回刚被置换的页面 从而减少系统I O的开销 页面缓冲算法用FIFO算法选择被置换页 选择出的页面不是立即换出 而是放入两个链表之一 如果页面未被修改 就将其归入到空闲页面链表的末尾 否则将其归入已修改页面链表末尾 这些空闲页面和已修改页面会在内存中停留一段时间 如果这些页面被再次访问 只需将其从相应链表中移出 就可以返回进程 从而减少一次I O开销 缺页时 系统需调页 则将新页读入到空闲页面链表的第一个页面中 然后将其从该链表中移出 当已修改的页面达到一定数目后 再将它们一起写入磁盘 然后将它们归入空闲页面链表 这样能大大减少I O操作的次数 虚拟存储器技术的理论基础 技术的可行性分析 该技术的引入不会使程序执行速度降低许多 程序执行时呈现局部性规律 指令局部性 1程序在执行时 除少数跳转语句外 其余仍是顺序操作 即CPU下一步要访问的是本条指令之后的指令 2一般 子程序调用的深度不会超过5 即一段时间内 内存中驻留5个正在执行中的子程序就可以满足一段时间内CPU对指令的访问需求 数据局部性 1进程对数组等数据结构进行访问会持续一段时间 即在一段时间内 进程所访问的数据仅限于与数组相关的一组变量 工作集 程序在时刻t的前 时间单位中所访问的页面集合称为程序的工作集W t 根据程序的局部性原理 程序在执行时将首先相对稳定地工作在某个工作集中 其中包含所有需访问的指令和数据 当程序运行于新旧段落的转折期时 工作集将巨增以容纳新的页面 经过一段时间的调整 工作集的大小降低 直到它仅包含来自新段落的页面 驻留集 驻留集是进程在主存中的图像 在虚拟存储器中进程的驻留集会随时间而变化 1驻留集包含工作集时 进程才能运行下去2为减少内存的消耗 os应周期性地从驻留集中移去不在工作集中的页面 3因为驻留集不可能包含全部进程图像 因此会出现要访问的内容在磁盘中的情况 称为缺页 一般 频繁发生缺页时 进程一定工作在两个逻辑段落过渡的时刻 驻留集的管理 操作系统应该为进程分配多少个页 内存分配策略 固定分配可变分配替换范围 局部替换全局替换 三 请求分页中的页面调入策略 1 调入策略决定什么时候将一个页面由外存调入内存 从何处将页面调入内存 何时调入页面预调页策略 将那些预计在不久便被访问的页预先调入内存 这种调入策略提高了调页的效率 减少了I O次数 但由于这是一种基于局部性原理的预测 若预调入的页面在以后很少被访问 则造成浪费 故这种方式常用于程序的首次调入 请求调页策略 当进程运行中访问的页出现缺页时 则发出缺页中断 提出请求调页 由OS将所需页调入内存 这种策略实现简单 应用于目前的虚拟存储器中 但易产生较多的缺页中断 且每次调一页 系统开销较