操作系统04_存储管理

第四章存储器管理 引言4 1程序的装入和链接4 2连续分配方式4 3基本分页存储管理方式4 4基本分段存储管理方式4 5虚拟存储器的基本概念4 6请求分页存储管理方式4 7页面置换算法4 8请求分段存储管理方式 存储组织 存储器的功能是保存数据 存储器的发展方向是高速 大容量和小体积 内存在访问速度方面的发展 DRAM SDRAM DDR DRDRAM DDR2 XDR SRAM等 硬盘技术在大容量方面的发展 接口标准 存储密度等 存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构 其依据是访问速度匹配关系 容量要求和价格 寄存器 内存 外存 结构 寄存器 缓存 内存 外存 结构 存储层次结构 快速缓存 SRAM内存 DRAM SDRAM DDR DRDRAM DDR2 XDR等 外存 软盘 硬盘 光盘 磁带等 微机中的存储层次组织 访问速度越慢 容量越大 价格越便宜 最佳状态应是各层次的存储器都处于均衡的繁忙状态 存储管理的功能 存储分配和回收 分配和回收算法及相应的数据结构 地址变换 可执行文件生成中的链接技术程序加载 装入 时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护 代码和数据共享地址空间访问权限 读 写 执行 存储器扩充 重定位 实现逻辑地址 相对地址 到物理地址 绝对地址 的映射 逻辑地址 应用程序经编译后形成目标程序 再经过链接后形成可装入程序 这些程序的地址都是从0开始 程序中的其他地址都是相对于起始地址计算的 这些地址为相对地址 物理地址 主存中一系列存储信息的物理单元的地址 重定位概念 4 1程序的装入和链接 编辑 编译 链接 装入 运行 4 1 1程序的装入 1 绝对装入 编译后 装入前已产生了绝对地址 内存地址 装入时不再作地址重定位 绝对地址的产生 1 由编译器完成 2 由程序员编程完成 对 1 而言 编程用符号地址 2 可重定位装入 静态重定位 地址转换在装入时一次完成 由软件实现 重定位装入程序完成 缺点 不允许程序在运行中在内存中移动位置 0 1000 2500 5000 LOAD1 2500 LOAD1 2500 365 365 10000 11000 12500 15000 作业地址空间 内存空间 图4 2 3 动态运行时装入在装入后不能移动 该情况一般在执行时才完成相对 绝对地址的转换且有硬件的支持 能保证进程的可移动性 4 1 2程序的链接 1 静态链接a 对相对地址的修改b 变换外部调用符号2 装入时动态链接a 便于修改和更新b 便于实现对目标模块的共享3 运行时动态链接 模块ACALLB RETURN 模块BCALLC RETURN 模块CRETURN 0 L 1 0 M 1 0 N 1 a 目标模块 模块AJSRL RETURN 模块BJSRL M RETURN 模块CRETURN 0 L 1 L L M 1 L M L M N 1 b 装入模块 4 2连续分配方式 单一连续分配用于单用户 单任务中分区式分配固定式可变式可重定位分区分配 4 2 1单一连续分区 内存分为两个区域 系统区 用户区 应用程序装入到用户区 可使用用户区全部空间 最简单 适用于单用户 单任务的OS 优点 易于管理 缺点 对要求内存空间少的程序 造成内存浪费 程序全部装入 很少使用的程序部分也占用内存 4 2 2固定分区 特点 有n个分区 则可同时装入n个作业 任务 一 分区大小 相等 不相等 不相等利用率更高 二 内存分配 数据结构将分区按大小排序 并将其地址 分配标识作记录例 dos的MCB三 特点 简单 有碎片 内零头 分区说明表 24K 32K 64K 128K 256K 分配情况 4 2 3可变式分区 一 数据结构1 空闲分区表2 空闲分区链 二 分配算法1 首次适应算法FF 要求 分区按低址 高址链接特点 找到第一个大小满足的分区 划分 有外零头 低址内存使用频繁 2 循环首次适应算法 从1中上次找到的空闲分区的下一个开始查找 特点 空闲分区分布均匀 提高了查找速度 缺乏大的空闲分区 3 最佳适应算法分区按大小递增排序 分区释放时需插入到适当位置 三 分区分配 分配算法 4 7内存回收时的情况 回收 1 上邻空闲区 合并 改大小 2 下邻空闲区 合并 改大小 首址 3 上 下邻空闲区 合并 改大小 4 不邻接 则建立一新表项 例 在计算机系统中 按地址排列的内存中的空闲区大小是 10K 4K 20K 18K 7K 9K 12K 15K 对于连续的段请求 12K 10K 9K 使用循环适应算法和最佳适应算法将找出哪些空闲区 解 循环适应算法 20K 18K 9K最佳适应算法 12K 10K 9K 4 2 4可重定位分区分配 1 动态重定位的引入连续式分配中 总量大于作业大小的多个小分区不能容纳作业 紧凑通过作业移动将原来分散的小分区拼接成一个大分区 作业的移动需重定位 是动态 因作业已经装入 紧凑 2 动态重定位的实现 0 100 2500 5000 2500 10000 10000 10100 12500 15000 作业J 处理机一侧 存储器一侧 重定位寄存器 相对地址 图4 10动态分区分配算法 4 2 5对换 1对换的引入将阻塞进程 暂时不用的程序 数据换出 将具备运行条件的进程换入 类型 整体对换 进程对换 解决内存紧张部分对换 页面对换 分段对换 提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度 因此 对换区一般采用连续分配 采用数据结构和分配回收类似于可变化分区分配 3换出与换入换出1 选出被换出进程 因素 优先级 驻留时间 进程状态2 换出过程 对于共享段 计数减1 是0则换出 否则不换修改PCB和MCB 或内存分配表 换入 1 选择换入进程 优先级 换出时间等 2 申请内存 3 换入 4 3基本分页存储管理 连续分配引起 碎片碎片问题的解决 紧凑方式消耗系统开销 离散分配分页 分段 段页 1 页面页面和物理块 逻辑空间和内存空间页面大小页太大 页内碎片大 页太小 页表可能很长 换入 出效率低2 地址结构3112110逻辑地址A 页大小L 页内偏移d 4 3 1页面与页表 例 L 1000B 则第0页对应0 999 第1页对应1000 1999 设A 3456 则P INT 3456 1000 3 d 3456 mod1000 456故A 3456 3 456 一般来说 页面尺寸应该是2的幂 这样的优点是可以省去除法 由硬件自动把地址场中的数拆成两部分来决定对应的页号和页内地址 例 页的大小为1KB 则逻辑地址4101的页号 页内地址可这样定 1K 1024 210 页内地址位数为10 4101 212 22 20 逻辑地址字如下 0001000000000101 页号 页内地址 故A 4101 4 5 3 页表 用户程序 页表 页号 块号 内存 4 2地址变换机构 基本任务 逻辑地址 物理地址的映射 页号 块号通过页表来完成页内地址 块内地址无需转换一 基本地址变换机构 越界保护每个进程对应一页表 其信息 如长度 始址 放在PCB中 执行时将其首地址装入页表寄存器 需要考虑的问题 页表放在哪里 整个系统的页表空间有多大 直接映像的分页系统对系统效能的不利影响 影响执行速度 因为CPU至少要访问两次主存才能存取到所要数据 基本的地址变换机构 页表驻留在内存中 系统中设置一个页表寄存器存放页表在内存中的始址和页表的长度 缺点 两次访问主存 速度降低近1 2 2 具有快表的地址变换机构 不具快表 则需两次访问内存 1 访页表 2 得到绝对地址内容有快表 速度提高 快表贵 不能太多 2 具有快表的地址变换机构 例 有一页式系统 其页表存放在主存中 如果对主存的一次存取需要1 5 s 试问实现一次页面访问的存取时间是多少 如果系统加有快表 平均命中率为85 当页表项在快表中时 其查找时间忽略为0 试问此时的存取时间是多少 答 若页表存放在主存中 则要实现一次页面访问需两次访问主存 一次是访问页表 确定所存取页面的物理地址 称为定位 第二次才根据该地址存取页面数据 页表在主存的存取访问时间 1 5 2 3 s 增加快表后的存取访问时间 0 85 1 5 1 0 85 2 1 5 1 725 s 4 3 3两级和多级页表 页表可能很大 将其离散存放在不同页块中 建一 外部页表 来管理这些离散页表块 相当于单级页表中的页表寄存器 一般应常驻内存 每项记录页表始址 且增加存在位 64位机器页表一般 3级 最外层页表常驻 1 某系统采用页式存储管理策略 拥有逻辑空间32页 每页2K 拥有物理空间1M 1 写出逻辑地址的格式 2 若不考虑访问权限等 进程的页表有多少项 每项至少有多少位 3 如果物理空间减少一半 页表结构应相应作怎样的改变 2 已知某分页系统 主存容量为64K 页面大小为1K 对一个4页大的作业 其0 1 2 3页分别被分配到主存的2 4 6 7块中 1 将十进制的逻辑地址1023 2500 3500 4500转换成物理地址 2 以十进制的逻辑地址1023为例画出地址变换过程图 练习 1 1 系统拥有逻辑地址空间32页 则逻辑地址中页号需用5位描述 每页2K 则页内地址用11位描述 2 进程页表项数为32 另外页表项中只给出页所对应的物理块号 1M的物理空间可分为29个内存块 故每个页表项至少有9位 3 如果物理空间减少一半 则页表中页表项数不变 每项的长度可减少1位 2 1 逻辑地址1023 1023 1024 得页号0 页内地址1023 查页表的相应块号2 故物理地址为2 1024 1023 3071逻辑地址2500 2500 1024 得页号2 页内地址452 查页表的相应块号6 故物理地址为6 1024 452 6596逻辑地址3500 3500 1024 得页号3 页内地址428 查页表的相应块号7 故物理地址为7 1024 428 7596逻辑地址4500 4500 1024 得页号4 页内地址404 因页号大于页表长度产生越界中断 4 4基本分段存储管理 4 4 1引入每个段可有其逻辑意义及功能 使得便于 1 方便编程 2 分段共享 3 分段保护 4 动态链接 5 动态增长 如数据段的增长 4 4 2分段系统的基本原理 分段基本思想 按程序的逻辑结构 将程序的地址空间划分为若干段 各段大小可不相同 在进行存储分配时 以段为单位 这些段在内存中可以不相邻接 分段地址中的地址具有如下结构 3116150 2 段表 图4 16利用段表实现地址映射 图4 17分段系统的地址变换过程 3 地址变换机构 4 分页和分段的主要区别 1 页是信息的物理单位 段是逻辑单位 2 页长度固定 段长度不固定 由用户指定 3 一维与二维 4 4 3信息共享 图4 18分页系统中共享editor的示意图 图4 19分段系统中共享editor的示意图 段式管理的优缺点优点 程序的各段可独立编译 修改一个过程不会影响其它无关过程 可采用不同的保护措施 段只包含一种类型的对象 可以有针对这种特定类型的合适的保护 便于共享某些段 常见的例子是共享库 如图形库 缺点 段长受限制 段长不定会出现空闲区上内存的浪费 段是作为一个整体调入调出 操作时间长 4 4 4段页式存储管理方式 基本原理面对用户程序的地址空间 采用段式分割内存分为长度相等的若干块将每段划分为页 也常与内存块相等 分页优点 提高内存利用率分段优点 方便用户 易于共享 保护 动态链接 图4 20作业地址空间和地址结构 图4 21利用段表和页表实现地址映射 2 地址变换过程 图4 22段页式系统中的地址变换机构 例 对于下表所示段表 请将逻辑地址 0 137 1 4000 2 3600 5 230 转换成物理地址 4 5虚拟存储器的基本概念 4 5 1虚拟存储器的引入 1 常规存储器管理方式的特征 一次性 指全部装入 2 驻留性 指驻留在内存不换出 2 局部性原理时间局部性 如循环执行空间局部性 如顺序执行 3 虚拟存储器具有请求调入功能和置换功能 能从逻辑上对内存容量进行扩充的一种存储系统 实质 以时间换空间 但时间牺牲不大 4 5 2虚拟存储器的实现方式 需要动态重定位一 请求分页系统以页为单位转换需硬件 1 请求分页的页表机制 2 缺页中断 3 地址变换机构需实现请求分页机制的软件 置换软件等 二 请求分段系统以段为单位转换 1 请求分段的段表结构 2 缺段中断 3 地址变换机构需实现请求分段机制的软件 置换软件等 4 5 3虚存特征 1 离散性 部分装入 若连续则不可能提供虚存 无法支持大作业小内存运行2 多次性 局部装入 多次装入 3 对换性 4 虚拟性 4 6请求分页存储管理方式 4 6 1请求分页中的硬件支持 1 页表机制 2 缺页中断机构 图4 23涉及6次缺页中断的指令 缺页中断机构 可在指令执行期间产生 转入缺页中断处理程序 3 地址变换机构 图4 24请求分页中的地址变换过程 4 6 2内存分配策略和分配算法 一 最小物理块数不同的作业要求不同 如 允许间接寻址 则至少要求3个物理块 MovA B 二 页面分配和置换策略 1 固定分配局部置换 缺点 难以确定固定分配的页数 少 置换率高 多 浪费 2 可变分配全局置换3 可变分配局部置换根据进程的缺页率进行页面数调整 进程之间相互不会影响 三 分配算法 1 平均分配算法2 按进程大小比例分配算法 3 考虑优先权分配算法 4 6 3页面调入策略 1 调入时机 预调 根据空间局部性 目前 成功率 50 请求调入 较费系统开销各有优劣2 从何处调页 对换区 全部从对换区调入所需页面 快文件区 修改过的页面换出到对换区 稍慢UNIX方式 未运行过的页面 都应从文件区调入 曾经运行过但又被换出的页面 从对换区调入 对共享页 应判断其是否在内存区 3 页面调入过程 4 7页面置换算法 4 7 1最佳置换算法和先进先出置换算法 1 最佳 Optimal 置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法 其所选择的被淘汰页面 将是以后永不使用的 或许是在最长 未来 时间内不再被访问的页面 假定系统为某进程分配了三个物理块 并考虑有以下的页面号引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 图4 25利用最佳页面置换算法时的置换图 2 先进先出 FIFO 页面置换算法 图4 26利用FIFO置换算法时的置换图 4 7 2最近最久未使用 LRU 置换算法 1 LRU LeastRecentlyUsed 置换算法的描述 图4 27LRU页面置换算法 2 LRU置换算法的硬件支持 1 寄存器 为了记录某进程在内存中各页的使用情况 须为每个在内存中的页面配置一个移位寄存器 可表示为 R Rn 1Rn 2Rn 3 R2R1R0 图4 28某进程具有8个页面时的LRU访问情况 2 栈 图4 29用栈保存当前使用页面时栈的变化情况 4 7 3Clock置换算法 1 简单的Clock置换算法 图4 30简单Clock置换算法的流程和示例 2 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面 1类 A 0 M 0 表示该页最近既未被访问 又未被修改 是最佳淘汰页 2类 A 0 M 1 表示该页最近未被访问 但已被修改 并不是很好的淘汰页 3类 A 1 M 0 最近已被访问 但未被修改 该页有可能再被访问 4类 A 1 M 1 最近已被访问且被修改 该页可能再被访问 其执行过程可分成以下三步 1 从指针所指示的当前位置开始 扫描循环队列 寻找A 0且M 0的第一类页面 将所遇到的第一个页面作为所选中的淘汰页 在第一次扫描期间不改变访问位A 2 如果第一步失败 即查找一周后未遇到第一类页面 则开始第二轮扫描 寻找A 0且M 1的第二类页面 将所遇到的第一个这类页面作为淘汰页 在第二轮扫描期间 将所有扫描过的页面的访问位都置0 3 如果第二步也失败 亦即未找到第二类页面 则将指针返回到开始的位置 并将所有的访问位复0 然后重复第一步 如果仍失败 必要时再重复第二步 此时就一定能找到被淘汰的页 4 7 4请求分页系统的性能分析 请求分页系统是目前最常用的一种存储方式 但运行中产生的缺页情况会影响速度和系统性能 而缺页率的高低往往与进程所占用的物理块数有关 因此本节分析缺页率对系统性能的影响 以及应为每个进程所分配的物理块数目 1 缺页率与有效访问时间有效访问时间 1 p t p f其中 p为缺页率 t为内存访问时间 f为缺页中断时间 说明 现代计算机系统 内存访问时间在10ns到数百ns之间 以100ns为例计算 缺页中断时间包括三部分 1 缺页中断服务时间 2 将缺页读入的时间 3 进程重新执行时间 由于CPU时间很快 所以 1 3 可以不超过1ms 2 则包括寻道时间 旋转时间和数据传送时间 大体需要24ms 代入上式得 有效访问时间 1 p 0 1 s p 25000 s 0 1 24999 9 p如果缺页率p 0 001 即在1000次的页面访问中 仅发生一次缺页 则有效访问时间约为25 s 与无缺页相比 速度降低至1 250 如果希望在缺页时有效访问时间延长不超过10 则有0 11 0 1 24999 9 p则p 0 01 24999 9 0 0000004 结论 有效访问时间直接比例与缺页率 改善请求分页系统的性能 需要保持非常低的缺页率 同时提高I O的速度 2 抖动 是这样一种系统状态 即系统花在页面替换上的时间远远大于执行进程的时间 抖动产生的原因 由于分配给进程的页面数大小少于进程所需要的最低页面数 导致出现接连不断的缺页中断 引起抖动 CPU利用率与多道程序度的关系 多道程序度指在内存中并发执行的程序数目 两者关系如下 在低度情况下 CPU利用率呈线性变化关系 随着度的上升 CPU利用率也逐渐上升 最终上升到一个最大值 若在这种情况下 进一步增加度 则系统发生抖动 且CPU利用率将迅速恶化 结论 系统可以利用CPU利用率与多道程序度进行比较的方法检测抖动 一旦发生抖动 可以通过减少多道程序度的方法来消除 例 考虑一个请求分页系统 它采用全局置换策略和平均分配内存块的算法 即若有m个内存块和n个进程 则每个进程分得m n个内存块 如果该系统测得如下CPU和对换盘利用率 请问能否用增加多道程序度数来增加CPU的利用率 为什么 1 CPU利用率为13 盘利用率为97 2 CPU利用率为87 盘利用率为3 1 CPU利用率为13 盘利用率为3 答 1 此时发生抖动现象 增加多道程序度会进一步增加缺页率 使系统性能进一步恶化 所以不能用增加多道程序度数来增加CPU的利用率 2 CPU利用率已经相当高 盘利用率却相当低 即进程的缺页率很低 此时应适当增加多道程序度数来增加CPU的利用率 3 CPU利用率相当低 盘利用率也相当低 表示内存中可运行的程序数不足 此时应增加多道程序度数来增加CPU的利用率 4 8请求分段存储管理方式 4 8 1请求分段中的硬件支持 1 段表机制 在段表项中 除了段名 号 段长 段在内存中的起始地址外 还增加了以下诸项 1 存取方式 2 访问字段A 3 修改位M 4 存在位P 5 增补位 6 外存始址 2 缺段中断机构 图4 31请求分段系统中的中断处理过程 3 地址变换机构 图4 32请求分段系统的地址变换过程 4 8 2分段的共享与保护 1 共享段表 图4 33共享段表项 2 共享段的分配与回收 1 共享段的分配 在为共享段分配内存时 对第一个请求使用该共享段的进程 由系统为该共享段分配一物理区 再把共享段调入该区 同时将该区的始址填入请求进程的段表的相应项中 还须在共享段表中增加一表项 填写有关数据 把count置为1 之后 当又有其它进程需要调用该共享段时 由于该共享段已被调入内存 故此时无须再为该段分配内存 而只需在调用进程的段表中 增加一表项 填写该共享段的物理地址 在共享段的段表中 填上调用进程的进程名 存取控制等 再执行count count 1操作 以表明有两个进程共享该段 2 共享段的回收 当共享此段的某进程不再需要该段时 应将该段释放 包括撤在该进程段表中共享段所对应的表项 以及执行count count 1操作 若结果为0 则须由系统回收该共享段的物理内存 以及取消在共享段表中该段所对应的表项 表明此时已没有进程使用该段 否则 减1结果不为0 则只是取消调用者进程在共享段表中的有关记录 3 分段保护 越界检查2 存取控制检查 只读 只执行 读 写3 环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据 一个程序可以调用驻留在相同环或较高特权环中的服务 典型问题分析 1 设作业 的页面映象表如下图所示 一页 1KB 页号块号中断位访问位修改位辅存地址 问 指出页表中中断位 访问位 修改位 辅存地址的含义 当执行到 单元的指令 时 系统是怎样进行地址变换 即 在主存的哪个单元中 当执行到 单元指令 时 会发生什么现象 1 中断位 也称状态位 表示该页是否已调入内存 访问位 记录本页在一段时间内被访问次数 修改位 表示该页调入内存后是否修改过 辅存地址 指出该页在辅存上的地址 2 设页号为P 页内地址为d 逻辑地址为A 页面大小为L 则 P INT A L d A modL当执行到 单元的指令 时 系统地址变换如下 L 1024B A 1800 则P INT 1800 1024 1 d 1800 mod1024 776故A 1800 1 776 查页表第1页在第5块 所以物理地址为 5896 3 当执行到 单元指令 时 系统地址变换如下 L 1024B A 3600 则P INT 3600 1024 3 d 3600 mod1024 528故A 3600 3 528 查页表第