计算机操作系统存储器管理.ppt

第四章 存储器管理 4 1程序的装入和链接 编辑 编译 链接 装入 运行图4 1 4 1 1程序的装入 1 绝对装入 编译后 装入前已产生了绝对地址 内存地址 装入时不再作地址重定位 绝对地址的产生 1 由编译器完成 2 由程序员编程完成 对 1 而言 编程用符号地址 2 可重定位装入 静态重定位 装入时完成 主要工作是对相对地址中的指令和数据地址的调整过程 例 图4 2问题 如何知道哪些位置需调整 链接时产生可装入模块的具体功能 0 1000 2500 5000 LOAD1 2500 LOAD1 2500 365 365 10000 11000 12500 15000 作业地址空间 内存空间 图4 2 4 1 1程序的装入 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单一连续分区 系统区用户区存贮保护一般不设置保护也可 因单任务 4 2 2固定分区 特点 有n个分区 则可同时装入n个作业 任务 一 分区大小 相等 不相等 不相等利用率更高 二 内存分配 数据结构将分区按大小排序 并将其地址 分配标识作记录例 dos的MCB三 特点 简单 有碎片 内零头 图4 4a 图4 4b 24K 32K 64K 128K 256K 分配情况 4 2 3可变式分区 比固定式分区有改善 一 数据结构1 空闲分区表2 空闲分区链 4 2 3可变式分区 比固定式分区有改善 二 分配算法1 首次适应算法FF 要求 分区按低址 高址链接特点 找到第一个大小满足的分区 划分 有外零头 低址内存使用频繁 2 循环首次适应算法 从1中上次找到的空闲分区的下一个开始查找 特点 空闲分区分布均匀 提高了查找速度 缺乏大的空闲分区 3 最佳适应算法分区按大小递增排序 分区释放时需插入到适当位置 4 2 3可变式分区 比固定式分区有改善 三 分区分配1 分配 图4 62 回收 1 上邻空闲区 合并 改大小 2 下邻空闲区 合并 改大小 首址 3 上 下邻空闲区 合并 改大小 4 不邻接 则建立一新表项 4 7内存回收时的情况 4 2 4可重定位分区分配 1 动态重定位的引入连续式分配中 总量大于作业大小的多个小分区不能容纳作业 紧凑通过作业移动将原来分散的小分区拼接成一个大分区 作业的移动需重定位 是动态 因作业已经装入 紧凑 2 动态重定位的实现 0 100 2500 5000 2500 10000 10000 10100 12500 15000 作业J 处理机一侧 存储器一侧 重定位寄存器 相对地址 图4 10动态分区分配算法 4 2 5对换 1对换的引入将阻塞进程 暂时不用的程序 数据换出 将具备运行条件的进程换入 类型 整体对换 进程对换 解决内存紧张部分对换 页面对换 分段对换 提供虚存支持2对换空间的管理外存对换区比文件区侧重于对换速度 因此 对换区一般采用连续分配 采用数据结构和分配回收类似于可变化分区分配 4 2 5对换 3换出与换入一 换出1 选出被换出进程 因素 优先级 驻留时间 进程状态2 换出过程 对于共享段 计数减1 是0则换出 否则不换修改PCB和MCB 或内存分配表 二 换入 1 选择换入进程 优先级 换出时间等 2 申请内存 3 换入 4 3基本分页存储管理 连续分配引起 碎片碎片问题的解决 紧凑方式消耗系统开销 离散分配分页 分段 段页 1 页面页面和物理块 逻辑空间和内存空间由机器的地址结构决定页太大 页内碎片大 页太小 页表可能很长 换入 出效率低2 地址结构3112110逻辑地址A 页大小L 设为1024 页内偏移dd AmodL如 A 2170B 则P 2 d 122 4 3 1页面与页表 3 页表 用户程序 页表 页号 块号 内存 4 2地址变换机构 完成 逻辑页号 物理块号的映射 由页表完成 一 基本地址变换机构 越界保护每个进程对应一页表 其信息 如长度 始址 放在PCB中 执行时将其首地址装入页表寄存器 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级 最外层页表常驻 例 某虚拟存储器的用户编程空间共32个页面 每页为1KB 内存为16KB 假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表 则逻辑地址0A5C H 所对应的物理地址为 125C 例 0A5C 0000 1010 0101 1100页号为2 对应块号为4 有 物理地址 0001 0010 0101 1100即 125C 4 4基本分段存储管理 即多重定位分区管理4 4 1引入每个段可有其逻辑意义及功能 使得便于 1 方便编程 2 分段共享 3 分段保护 4 动态链接 5 动态增长 如数据段的增长 4 4 2分段系统的基本原理 分段对用户而言 分段是2维的 段号 段内地址 段表 逻辑段 map 物理段地址变换机构 图4 16 4 17分页与分段 1 页是信息的物理单位 段是逻辑单位 2 页长度固定 段长度不固定 由用户指定 3 一维与二维 4 4 3共享 段式系统易于共享例 图4 18及4 19分页与分段共享比较可重入码 纯代码 各个进程应保留局部数据区 进程1 进程2 页表 页表 主存 分页系统中共享editor 分段系统中共享editor 4 4 4段页式存储管理 分页优点 提高内存利用率分段优点 方便用户 易于共享 保护 动态链接 一 段页式系统基本原理图4 20图4 21段号 段内页号 页内地址注意 对用户而言 仍然是二维编址 对系统而言 则是三维编址 4 4 4段页式存储管理 二 地址变换图4 22三次访内存操作 为提高速度 在地址变换机构中增设一高速缓冲寄存器 Cache 4 5虚拟存储器 4 5 1引入1 常规存储管理的特征 一次性 指全部装入 驻留性 指驻留在内存不换出 2 局部性原理时间局部性 如循环执行空间局部性 如顺序执行 3 虚拟存贮器具有请求调入功能和置换功能 能从逻辑上对内存容量进行扩充的一种存储系统 实质 以时间换空间 但时间牺牲不大 虚拟大小由 决定 4 5 2虚拟存储器的实现方式 需要动态重定位一 请求分页系统以页为单位转换需硬件 1 请求分页的页表机制 2 缺页中断 3 地址变换机构需实现请求分页机制的软件 置换软件等 二 请求分段系统以段为单位转换 1 请求分段的段表结构 2 缺段中断 3 地址变换机构需实现请求分段机制的软件 置换软件等 4 5 3虚存特征 1 离散性 部分装入 若连续则不可能提供虚存 无法支持大作业小内存运行2 多次性 局部装入 多次装入 3 对换性 4 虚拟性 4 6 1请求分页中的数据结构及硬件支持一 页表机制页表项 二 缺页中断机构 可在指令执行期间产生 如图4 23 转入缺页中断处理程序 三 地址变换机构比较简单分页机制 增加了中断处理 图4 24 4 6请求分页存储管理 图4 23涉及6次缺页中断的指令 4 6 2内存分配策略和分配算法 一 最小物理块数不同的作业要求不同 如 允许间接寻址 则至少要求3个物理块 MovA B 4 6 2内存分配策略和分配算法 二 页面分配和置换策略 1 固定分配局部置换 缺点 难以确定固定分配的页数 少 置换率高多 浪费 2 可变分配全局置换3 可变分配局部置换根据进程的缺页率进行页面数调整 进程之间相互不会影响 三 分配算法 1 平均分配算法2 按进程大小比例分配算法 3 考虑优先权分配算法 4 6 3页面调入策略 1 调入时机 预调 根据空间局部性 目前 成功率 50 请求调 较费系统开销各有优劣2 从何处调页 对换区 修改过的页被换出时入对换区 快文件区 稍慢对共享页 应判断其是否在内存区 3 页面调入过程 目的 减少对换量 提高系统性能4 7 1最佳置换算法和先进先出算法一 最佳置换算法 理论上的 4 7页置换算法 4 7页置换算法 目的 减少对换量 提高系统性能4 7 1最佳置换算法和先进先出算法二 FIFO 4 7 2最近最久未用LRU置换 一 算法描述将 最近的过去 作为 最近的将来 图4 27二 LRU算法的硬件支持 用来记录谁最近最久未访问 1 位移寄存器 定时右移 R Rn 1 R0图4 282 栈 当进程访问某页时 将其移出压入 栈顶 栈底 换出 图4 29 LRU 4 7 3clock置换 LRU近似算法 硬件消耗少 一 简单算法 设一访问位 图4 30循环扫描 每次扫描时将访问位复位 4 7 3clock置换 LRU近似算法 硬件消耗少 二 改进 A 0 M 0 4 7 4其它 一 最少使用 是频率 与LRU类似 记录访问次数 设置一个访问计数器 二 页面缓冲算法 特点 淘汰的页只是修改标志 若页被修改过 则在欲复盖它时回写 否则成批回写 在欲重访问该页时 若页换出则只需修改标志 补充 80386的页描述 4 8请求分段存储管理方式 段表 段名段长段基址存取方式访问字段A修改字段M存在位P增补位外存起址二 缺段中断机构 段不定长 处理起来比缺页中断复杂 图4 31三 地址变换机构图4 32 4 8 2分段的共享与保护 一 共享段表 整个系统一张 图4 331 共享进程计数 2 存取控制字段 3 段号 不同的进程可以使用不同的段号去共享段 4 8 2分段的共享与保护 二 共享段的分配与回收1 分配 第一次访问 分配内存 1 增加共享段表 2 修改进程段表 第二次访问 1 修改共享段表 2 修改进程段表 2 回收 1 count 0 2 count0 4 8 2分段的共享与保护 三 分段保护1 越界检查段号越界检查 段内偏移越界检查 2 存取控制检查 R R W E3 环保护机构 1 内环可访问外环数据 2 外环可请求内环服务 试验 实现LRU算法和FIFO算法要求给出任意的输入流 计算失效率 输入流长度 cache尺寸可定制 测试 Cache 5 从0 9可数字的任意排序 长度为30 例如 12568 36536 56892 70495 36745 87345 保护模式 虚地址和虚地址空间 虚地址 程序中的地址 如MOVEREG 2000内存管理单元 MMU 完成地址转换 图4 1 段机制和页机制 虚拟地址空间 二维 16k 4G 64T LDT8K GDT8K 线性地址空间 一维 4G物理地址空间 一维 4G 选择子 偏移量 段机制 31 31 0 15 0 0 页机制 31 0 线性地址 物理地址 段机制 段基地址段界限段属性以上三者存储在段描述符表中 图4 4 描述符 图4 5 图4 6 4 8 G 粒度位 0时 段长表示段格式的字节长度 即一个段最长可达1M字节 1时 段长表示段格式以4K字节为一页的页目录数 即一个段最长可达1M 4K 4GD 表示缺省操作数的大小 0操作数为16位 1为32位 P 存在位 描述段是否在内存S 表示该段是系统段 0 还是用户段 1 DPL 该段的特权级类型 数据段还是代码段A 该段是否被访问 3位 为0表示数据段 1表示代码段W 为0表示不可写 为1表示可写 R 该段可读否C 一致位 当C 1时 若当前进程特权级低于描述符特权级 且当前特权级保持不变 那么代码段只能执行 系统段类型 图4 10 门 用来控制访问在目标码段的入口点 类型调用门 将程序控制转移到一个更高特权级别任务门 切换任务中断门 中断处理陷阱门 陷阱处理TSS 任务状态段 包含了任务状态信息LDT 局部描述符表 门描述符 图4 11 段基址由选择器指出 描述符表 GDT包含系统中所有任务都可以用的描述符IDT包含任务门 中断门 陷阱门描述符LDT每任务一个 各任务也可有相同的描述符 以共享全局数据和代码每任务的LDT也用一个描述符来表示 即LDT描述符 在GDT中 选择器与描述符表寄存器 只有RPL大于等于相应的描述符DPL 描述符才能被存取 GDTR IDTR LDTR 无分页操作时 寻址过程 图4 17 在段选择器中装入16位数 32位偏移 根据段选择器中的索引值 描述符表寄存器 取出相应描述符 将描述符中的段基地址和32位偏移相加 形成32位物理地址 分页机制 线性地址转换为物理地址由CR0的PG位启用 状态和控制寄存器 图4 20 4 21 CR0 PE位 用于启动保护模式 CR2 保存最后一次出现页故障的全32位线性地址 CR3 目录表的物理地址 地址转换 图4 26 控制转移 若控制转移要求特权级发生变化 则必须通过门 调用门 为任务内特权级转移提供安全可靠的方法 小结 操作系统对虚拟存储器的实现是建立在硬件技术支持之上的 分页与分段的保护机制