操作系统讲稿ch8.ppt

Ch8虚拟存储器管理技术 分页存储管理分段存储管理段页式存储管理 8 1基本概念 进程执行程序时要访问的是程序的指令和数据的逻辑地址 进程在处理机上才能运行 通过处理机实际访问指令和数据的主存地址 严格区分逻辑地址 相对地址 及逻辑地址空间和绝对地址 实际地址 及绝对地址空间 实存地址空间 虚拟地址 把一个运行进程访问的地址称为 虚拟地址 虚拟地址空间 一个运行进程可访问的虚拟地址集合 实地址 处理机可直接访问的主存的地址称为 实地址 实地址空间 计算机主存称为 实地址空间 动态地址映象机构 实现由虚拟地址到实际地址的转换 把程序的指令和数据所在的虚拟地址放入主存实地址中去 虚拟地址空间 虚存 实地址空间 主存 虚存地址空间大小取决于 指令中的地址长度 外存空间的大小 虚拟存储器 是一个地址空间 是进程访问的逻辑地址空间 而不是物理主存空间 最大虚拟地址空间往往取决于指令中的地址长度限制 因外存空间通常大于指令地址长度所限定的范围 虚存管理 由OS自动实现 对用户是透明的 决定把作业虚拟地址空间的哪一部分装入主存 放在主存的什么位置 主存空间不够时把哪一部分置换出主存 8 2分页存储管理 1 分页存储管理的基本规则2 分页系统的地址转换3 分页存储管理策略 4 分页存储管理技术性能分析5 页的共享和保护6 分页存储管理技术的软硬件实现 1 分页存储管理基本规则 等分主存 把主存划分成相同大小的存储块 页架 pageframe 页架大小固定不变 页架从0编号 页架号 用户逻辑地址空间的分页 逻辑地址空间划分成与页架大小相同的部分 页 逻辑页 虚页 不足一页的补齐一页 给页从0编号 页号 逻辑地址的表示 虚拟地址A 数对 p d p 页面号 d 虚拟地址在页面号p内相对地址 页内地址 页面大小L 则p A L d A MODLex L 1000 A 3456 逻辑地址 3 456 主存分配原则 系统以页架为单位把主存分给作业或进程 并且分给一个作业或进程的页架不一定是相邻和连续的 即作业可以按页为单位零散地放在主存不连续的页架中 页面与页架一一对应 对应关系由页表记录 页表 系统在作业装入主存时建立进程的同时建立的 记录各页面的调度情况 页表表目也称为页描述子 pagedescriptor 包括页号 状态 页架号 页面存储控制字段 页表起始地址b和表长L一般放在该作业进程的PCB中 当进程投入运行时先装入页表地址寄存器 分页系统中地址结构 虚拟地址 p d 在指令场中的物理表示 Ex IBM页号P页内地址d078192031p占12位 页面总数为212 4K d占12位 则页面大小为4K 页面尺寸应是2的幂 便于由指令地址场中给出的逻辑地址计算出其页面号p及页内地址d 若页面大小2i 把地址场从第i位分成两部分 高位部分表示的数即页面号p 低位部分表示的数即为页内地址d L 1K 1024 210 A 1005H p 4H d 5H1510900001000000000101 2 分页存储管理地址转换 直接映象的地址转换 图8 3进程被调度 该进程页表起始地址和表长送页表寄存器R L b 进程访问虚地址v 地址映象硬件把v p d 比较页面号p与页表长L 判断是否越界 页访问合法 按p索引页表 b p i 第p个页面对应页表表目 页描述子 页架号p i为表目长度 根据该表目中存储控制字段检验访问权限是否合法 硬件计算实际地址 页架号p 与d构成物理地址 p d 页表放在主存中系统表格区 主存页架数N 主存大小 页大小 最多可存放N个页面 必然还有未能调入主存的页面 即所有进程页表表目数之和 N 页表所占空间 页表表目数 每个表目长度l N l缺点 访问两次主存 页表 数据 处理机执行速度降低1 2 相关映象的地址转换 图8 4页表放在相关存储器 关联存储器 快表 相关页表相关存储器 硬件寄存器 且有一定的判断能力 实现按内容检索 虚拟地址v由硬件截成两部分 p d 用p与相关存储器中各表目同时比较 查得其所在表目 自动送出页架号p 再与d构成实地址 p d 处理机执行速度提高 但高速相关存储器很贵 相关映象与直接映象结合的地址转换 图8 5用8 16个高速相关存储器 存放正在运行进程当前最常用的部分页面的页描述子 页表的子集 全部页表存放在主存系统区 同时进行相关映象和直接映象 比较快表和主存页表 慢表 相关映象成功 就自动停止直接映象工作 否则由直接映象找出p 并与d构成实地址 同时把该表目送入相关存储器 相关映象与直接映象结合的地址转换 续 程序运行的局部性 时间局部性 刚被访问过的单元很快再被访问 空间局部性 刚被访问过的单元的邻近单元很快再被访问 由于程序运行的局部性特点 使相关存储器命中率达90 左右 速度约降低10 以下 Ex Z8000 16个表目 命中率96 NS32032 32个表目 命中率97 3 分页存储管理策略要解决的三个问题 何时取页 取页策略请求取页 当用到某页而不在主存时即缺页时取页 请求式分页存储管理 提前取页 预先装入主存一页或几页 提前页 取来的页面装入主存中哪个页架 置页策略一般装入主存任一个可用的页架中 当需调入一页 而主存已无可用的自由页架时 如何选择或腾出一个页架给新进入的页面 页面置换策略 页面淘汰策略 页面置换算法 页面淘汰算法 页的置换算法 当发生缺页 而主存中已无空闲页架时 需选一页淘汰 选取淘汰页的方法叫页的置换算法 抖动 刚被淘汰出去的页 不久又被访问 又需把它调入而将另一页淘汰出去 很可能又把刚调入的或很快要用的页淘汰出去了 如此反复更换页面 以至系统大部分机时花在页面的调度和传输上 系统的实际效率很低 这种现象称为 抖动 缺页率 f 缺页次数 访问页面总数 常见的页面置换算法 最佳置换算法OPT 先进先出置换算法FIFO 最近最少使用置换算法LRU 最近未使用置换算法NUR 工作集 最佳置换算法OPT OptimumStrategy 基本原则 淘汰在将来再也不被访问 或者是在最远的将来才能被访问的页 特点 无法预测作业将用到哪些页 所以此算法是无法实现的 理论上的算法 例 某进程分配页架数为3 其运行期间页面访问序列 A B C D A B E A B C D E 分析其按照OPT算法进行页面置换时的缺页情况 堆栈式算法 最佳置换算法OPT 先进先出置换算法FIFO first in first out 基本原则 选择最早进入主存的页面淘汰 理由 最早进入的页面其不再使用的可能性比最近调入的页面要大 实现简单 把进入主存的各页面按进入主存的时间次序构成队列 链表或表格 总是淘汰队头的页面 缺点 只有按照线性顺序访问地址空间时才是理想的 否则效率不高 异常现象 对于一些特定的访问序列 随分配页架数增加 缺页频率反而增加 先进先出置换算法FIFO 最近最少使用置换算法LRU LeastRecentlyUsed 基本原则 选择最近一段时间内最长时间没有被访问过的页面淘汰 基本理由 认为过去一段时间里不曾被访问过的页 在最近的将来也可能不再会被访问 实现困难 需为每个页设置一个特定单元 记录上次访问后到现在的时间量t 并选择t最大的页淘汰 无论硬件还是软件实现开销都很大 实际应用 近似算法NUR 最近最少使用置换算法LRU 最近未使用置换算法 NotusedRecently NUR 页表扩充 为每个页面设置两个硬件位 访问位和修改位 访问位 0 该页尚未被访问过 1 该页已经被访问过修改位 0 该页尚未被修改过 1 该页已经被修改过基本原则 淘汰最近未使用的页 且希望其在主存逗留期间页面内的数据未被修改过 过程 开始时所有页的访问位 修改位都为0 访问 修改时再置1 当选择淘汰页时 按照访问位0011的顺序淘汰 修改位0101周期性地对访问位清零 页面号页架号状态存储控制访问位修改位外页地址 页面描述子 分页存储管理技术性能分析 优点 可提供多个大容量的虚拟存储器 作业的地址空间不再受主存大小的限制 主存利用率大大提高 作业中不常用的页不会长期驻留在主存 当前运行用不到的信息也不必调入主存 能实现多道作业同时运行 方便用户 大作业也无须考虑覆盖问题 缺点 缺页中断处理增加系统开销页面的调入调出增加I O系统的负担此外页表等占用空间且需要管理 存在页内零头 解决 尽可能减少缺页中断次数 程序质量 尽可能使编出的程序具有高度的局部性 则执行时可经常集中在几个页面上进行访问 减少缺页率 页面大小 页面大 页表小 省空间且查找快 缺页次数相对也少 一次换页的时间长 页内零头空间浪费的可能性较大 页面小则相反 主存容量 一个程序运行时遇到缺页中断的次数 是和分配给该道程序的主存容量 页架数 成反比的 但当主存容量达到某个值时 缺页次数减少不再明显 多数程序都有一个确定值 拐点 图8 17淘汰算法 在淘汰页选择范围选择最合适的置换算法 程序运行的局部特性 进程对主存的访问不是均匀的 而是高度地表现出其局部性 时间局部性 指某个位置 数据或指令 最近被访问了 那么往往很快又要被再次访问 借助于循环 经常用到的变量和子程序等程序结构实现 空间局部性 指一旦某个位置最近被访问了 那么它附近的位置也要被访问 采用顺序的指令串 线性的数据结构 如数组或常用变量彼此相近存放 来实现 程序在某段时间对整个地址空间各页的访问集中在少数几页 一个页面中也不是均匀的 而是集中于页面中的较少部分 1 编写高质量的程序 选择适当的数据结构 增强程序访问的局部性 ex 数组在主存中存放顺序与使用顺序的一致性 二维数组清零 法1 intA 512 512 法2 intA 512 512 for j 0 j 512 j for i 0 i 512 i for i 0 i 512 i for j 0 j 512 j A i j 0 A i j 0 若页长为512 行优先存放 法1发生512 512 262144次缺页 法2只发生512次缺页 加强编译程序和装入程序的效能 编译程序 能把程序代码和程序的数据分离开来 减少常用的程序纯代码被换出的机会 装入程序 应将纯代码部分装入同一页或几页中 切不要把纯代码部分与非纯代码或数据部分放入同一页中 以减少那些常用子程序所在的页被换出的机会 2 页架分配 主存的分配 提前分配 目的 解决当程序刚一被启动时所引起的大量的持续的缺页 方法 启动前提前把该进程的最初的工作集装入主存 问题 1 系统有无能力主动装入某个指定的页面 而不是只能在缺页请求发生时才能将该页装入 可以 2 将哪些页提前装入 估计 最少页架数 指为保证一条指令能完整地执行 进程应分得的起码的页架数 随计算机结构的不同而不同 这取决于该机器的指令格式和寻址方式 Ex PDP 8 单地址指令立即寻址 需要1个页架OPdata直接寻址 至少需要2个页架OP直接地址data间接寻址 至少需要3个页架OP间接地址直接地址dataPDP 11 传送指令长度可能大于一个字 且间接寻址 至少需要6个页架 指令 2 源地址间址 2 目标地址间址 2 页架分配 续 局部分配 局部淘汰 仅在一个作业自己所占用的全部页架中挑选页面淘汰 所以进程所占页架数不变全局分配 全局淘汰 对整个主存范围内的页面进行挑选 固定页面 不能被换出或某段时间不能被换出的页面 固定页标志 长期固定和短期固定 分配算法 平均分配 系统中全部页架数m在n个进程间平均分配 设 m 95 n 6 m n 95 6 15 6 5每个进程分得15个页架 还有5个留作公用页架缓冲区 根据作业大小按比例分配 设 每个进程的虚存大小 即作业大小 为Si 则S Si主存可用页架数m 则Pi分的页架数ai Si S m且ai 最少页架数考虑进程优先级 提高高优先级进程分配比例 或允许高优先级进程淘汰低优先级进程的页面 全局分配 3 页面的大小 页面大小 大页面 增加页内碎片 增加缺页频率 小页面好 小页面 增加主存页架数 更多页表空间 大页面好 缺页时 读入一页总的传送时间 总的延迟时间 80 90 数据块传送时间 大页面好 结论 理论和实践 页面尺寸以小些为好 P145 表8 1 又一种页面置换算法 工作集 根据 程序行为的局部性 目标 降低缺页频率 缩短等待调页时间 提高系统效率 工作集 是进程在某段时间里实际要访问的页面的集合 保证程序有效运行 工作集必须在主存中 工作集的确定原则 依据程序过去的行为来估计它未来的行为 因为程序运行的局部化特点决定了工作集变化是缓慢的 进程在时间t的工作集 一个运行进程在t w到t这个时间间隔内所访问的页的集合成为该进程在时间t的工作集 记为W t w 变量w称为工作集窗口尺寸 工作集所包含的页面数称为工作集尺寸 记为 W t w 或 W W是t的函数 t不同 工作集不同 所含页面数 工作集尺寸不同 所含页面也可能不同 W是w的函数 W 是w的非降函数 且满足蕴含特性 即 W t w W t w a 其中a 0 工作集 续 问题 工作集窗口尺寸w的选取 过大 甚至把整个作业地址空间全部包含在内 就失去了虚存的意义 过小 引起频繁缺页 降低了系统效率 工作集尺寸 W t w 的确定 从t1起 将所有的页面访问位全清零 特权指令 在t1 w t2时 记下全部访问位为 1 的页面 则这些页的集合可看成t2时的工作集 结论 把缺页的间隔时间控制在合理的范围 使分给进程的页架数保持在上下限之间 拐点附近 5 页面的共享和保护 共享 使共享进程的逻辑地址空间中的页指向相同的页架号 其中放有共享数据或例程 实现 共享某页的所有作业对应页描述子拉成链表正共享的页 锁 在主存中 引用次数 公共页表 被共享的页面独立组成 页表中对应表目用指针指向 问题 分页对用户透明 要共享的数据或代码是否分在一页 在不同的共享作业中地址是否一致 进程A的页表页架0页架1进程B的页表页架2页架3页架4页架5主存进程C的页表 B C共享页架3的数据 A B共享页架1中的例程 共享数据页面 共享例程页面 信息保护 对共享页面提供附加保护措施 如对共享信息的操作权限 读 写 执行 实现 存储保护键 锁 钥匹配技术页表扩充 存取控制位 2位 表示该作业对该页可执行 允许读 允许写状态位 2位 描述正在装入的页架的状态标志断开 该页不在主存 CPU不能对它进行访问连接 该页已分配页架 但正在进行数据的输入输出操作 此时CPU不能对其访问 但通道可以 可寻址 该页在主存中就绪 CPU可以对其进行访问 页面号页架号状态存储控制访问位修改位外页地址 页面描述子 6 分页存储管理中的软硬件 操作系统需建立和管理的基本数据库 进程表 整个系统的进程PCB集合 包含 进程名 存储保护键 该进程的页表起始地址 页表长度 或作业大小 以及状态信息等内容 存储分块表 整个系统设置一个存储分块表 该表指出主存中各页架的状态是已分配还是可用 页面映象表 页表 每个进程设置一个页表 存放页面与页架的对应关系 放在主存 文件映象表 用以指出各进程的虚拟空间 以文件形式存于外存中 各页在外存中存放的地址和状态信息 分页机构的构成 硬件 分页地址变换硬件部分 中断处理硬件部分 软件 缺页中断处理程序 分页存储管理的软硬件配合过程 分页地址变换机构硬件 地址寄存器中虚地址 p d 实地址 p d 硬件执行指令 产生缺页中断 中断处理 缺页中断处理硬件 保护现场 PSW IP CS保留 CPU控制转给缺页中断处理程序 中断向量送IP CS 缺页中断处理程序 保护断点现场 分配页架 分页策略 可能淘汰页面被修改过则需回写 读入虚页 维护数据库 恢复现场 返回断点执行 页表表目扩充 通常页表表目逻辑上包含如下信息 外页地址 该页在磁盘等外存上的地址 页面号页架号状态存储控制访问位修改位外页地址 页面描述子 分段存储管理 1 分段存储管理基本概念2 地址转换3 段的动态连接4 虚拟存储管理中的存储保护问题5 分段存储管理的优缺点 8 3分段存储管理 方法 按程序模块来划分段 并按这些段来分配主存 段 定义为一组逻辑信息的集合 如子程序 数组和数据区等 通常以文件形式存于文件系统中 1 分段存储管理基本概念 进程的逻辑地址空间 程序员为每个段给出段名 二维逻辑地址空间 段名 段内地址 编译或汇编之后系统为每个段给出一个内部段名 段号 二维虚地址空间 段号s 段内相对地址w 程序的地址结构 S W Ex 段号S段内地址W078151631S 0 FF W 0 FFFF 主存分配 以段为单位 每一段分配一块连续的主存分区 一个进程的各段所分到的主存分区不要求是相邻连续的分区 段表和段表地址寄存器 每个作业一个段表内容 段号 段的长度 段在主存中的起始地址 段的状态位 访问位 修改位 扩充位 段在外存的地址等组织 段号从小到大排列 包含该进程的全部段 生命期 作业调入时为进程建立段表 撤消进程时清除此进程的段表 段表地址寄存器 存放运行进程的段表在主存中起始地址 调度时从PCB中读取 2 地址转换 图8 8 逻辑地址 s w b s l 段表查找 s在主存中的起始地址s s w 要访问的主存实际地址 段号段长段起始地址状态位存储控制访问位修改位扩充位外存地址 3 段的动态连接 分段时实现容易 因按程序段分段 静态连接 程序运行时 连接装配程序把作业调用的各个子程序和数据段连接成可运行的目标模块 一维线性连续地址空间 相对地址空间 且进行重定位 用于分页和实存管理技术 动态连接 程序运行开始时 只将主程序段装配好并调入主存 其他各段的装配是在主程序段运行过程中逐步进行的 每当需要调用一个新段时 再将这个新段装配好 并与主程序段连接 间接字 间接寻址方式中 把包含直接地址的字称为间接字 连接间接字 包含 连接标志位 L的间接字称为连接间接字 L 1 该段尚未连接 L 0 该段已进行了连接L 直接地址连接中断 在具有段的动态连接功能的机器中 处理机执行到L 1的间接指令时产生连接中断 停止执行该间接指令 转去执行连接中断处理程序 等到处理完后再重新执行该间接指令 L 0时根据连接间接字中的直接地址去取数执行之 编译程序的连接准备工作 原则 语句访问本段单元时 直接寻址指令 访问外段单元时 间接寻址指令 为之在本段设置一个连接间接字 并置L 1 其直接地址场指向一个存放被访问段段名的本段单元地址 例 某MAIN函数中有CALL P 第3段 MAIN段 第3段 MAIN段 110CALL 1 3 668110CALL 1 3 668图 8 116681367266804188 6727 P 6727 P 第4段 P段 0188 连接中断处理 图8 11连接间接字取出被访问段段名和段内地址 是否在主存 作业活动符号表 系统的活动文件表 在 查段表 找出段号 修改连接间接字 段号 段内地址 L置0 返回断点执行原来的间接指令 不在 分配主存 读入主存 分配段号 修改主存分配表 重复上步 纯段和杂段 对于每个源程序 编译程序至少生成两个分开的目标段纯段 过程段 可再入的 执行中不允许修改 杂段 连接段 程序所有可能变更的数据 包括连接间接字和某些临时变量 内部变量等都放在杂段 编译后连接前PBR过程 段基址 寄存器LP连接 段基址 寄存器 K2ADD 1 LP K1K1 1 PBR K27 P 连接后PBR过程 段基址 寄存器LP连接 段基址 寄存器 K2ADD 1 LP K1K1 07K37 P K3 段的共享 段的动态连接功能使段的共享很容易地实现 共享段的段号在不同作业中可以不同 当共享段被调出主存后 必须在共享该段的每个作业段表中指示该段不在主存 当它移动后 也需修改每个段表中的对应表目 主存始址 共享段表 记录每个共享段的段名 段长 主存始址 标志 共享本段的作业数 共享该段的作业名 对应段号等 减少修改数量 每个共享该段的作业段表中对应表目指向共享段表对应表目即可 共享段 作业1的段表作业2的段表 段名段长主存始址标志共享本段的作业数作业名段号段名段长主存始址标志共享本段的作业数作业名段号 4 虚拟存储管理中的存储保护问题 多级存储保护体系 越界保护 页表长度 最大页号 段表长度 最大段号 页表地址寄存器 当访问某虚拟地址时 硬件自动将其页号 段号 和页表 段表 长度进行比较 分段环境下还要将段内地址与段表中该段的长度进行比较 如果合法才进行转换 否则产生越界中断信号 存取控制保护 控制各种共享类型的用户的访问权限 读 允许用户对该段 页内任何信息或其副本进行读操作 写 允许用户修改该段 页内任何信息直至撤消整个段 页 执行 用户可以执行该段 页程序 数据段 页除外 增加 用户可在段 页的末尾添加信息 但不允许修改已存在于段 页中的信息 存储保护键 I O通道对存储器的访问不通过段表 5 分段存储管理的优缺点 优点 便于处理变化的数据结构 段表中加一个增长标志位 0 该段不可增长 1 该段允许动态增长由越界中断处理程序根据动态增长位来判别 便于共享 欲共享作业的段表中有相应表目指向被共享段在主存中的起始地址 提供了虚存的功能 小内存分区运行大作业 可能需要存储器紧缩 提供了动态连接的便利 便于控制存取访问 缺点 存储紧缩 分段最大尺寸受到主存大小的限制 在外存中管理可变尺寸的分段较困难 提高了硬件成本 8 4段页式存储管理 基本概念 等份主存 主存 页架 编号 页架号进程的地址空间采用分段方式 按程序的自然逻辑关系把进程的地址空间分成若干段 外部段名 内部段名 每一段采用分页方法 每一段划分成若干页 大小同页架 每一段为自己段的各页依次编以连续的页号 不足补齐逻辑地址结构 V s p d 段号 页号 页内地址 段号S页号p页内地址d0781516202131256段 32页 2K主存分配 以页架为单位分配给每个进程 段表 页表 段表地址寄存器 系统为每个进程建立一个段表 为其段表中每个段建立一个页表 用段表地址寄存器指示进程段表起始地址 段表表目给出该段页表起始地址及页表长度 段页式存储管理中的地址转换 图8 13无相关存储器 直接映象硬件 段表地址寄存器给出段表基址b 段号s 该段在段表中表目地址 读段表表目 该段页表起始地址s 硬件 页表基址s 页号p 该页在页表中表目地址 读页表表目 该页对应的页架号p 硬件 页架号p 与页内地址d 绝对地址 主存地址 有相关存储器 相关映象以段号s 页号p为索引 同时比较相关存储器的各表目 匹配 判断访问合法性 不合法 停止转换 发中断信号 合法 页架号p 与页内地址d 绝对地址 主存地址不匹配 由直接映象找出页架号 并把有关信息装入快表 进程表 段表 页表 页架的关系见图8 14段页式存储管理算法 地址转换见图8 15段页式存储管理的优缺点 优点 虚存管理功能 无紧缩问题 无页外碎片 便于处理变化的数据结构 段可动态增长 便于共享 动态连接 便于控制存取访问 缺点 增加硬件成本 增加软件复杂性和管理开销 存在页内碎片 8 7高速缓冲存储器 三级存储结构 CPU 缓冲存储器 主存 图8 18缓存 隐藏存储器Cache 不参与主存储器编址 对用户是透明的 不属于虚拟存储技术 Cache的组织 典型容量 4K 8K16K 32K读双字指令速度 主存1100ns 高速缓存120ns 处理机150 300ns构成 缓存 缓存目录 缓存控制器 缓存组织 缓存 和主存 分成若干块 每个块64字节 缓存空间分区 行号 每个区2K 32块 列号0 31 4KB 2个区 8KB 4个区 16KB 8个区 高速缓冲存储器 续 4K缓存的缓存目录 32个表目 区 2区每个缓存块对应一个缓存目录的表目 列号0 31 主存地址行号11bits 指示该块在主存中的行号 每一行