第六章 存储管理.ppt

西安理工大学高科学院李杨Emai 2099007 第六章存储管理 6 1存储管理的基本概念6 2单道程序下的存储管理6 3分区存储管理6 4分页存储管理6 5分段存储管理6 6段页式存储管理6 7虚拟存储器的实现 6 1存储管理的基本概念 存储器是计算机系统的重要资源之一 因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间 因此 存储管理直接影响系统性能 存储器由内存 primarystorage 和外存 secondarystorage 组成 本章讨论的主要是内存管理问题 6 1 1存储管理的对象和目标 存储管理主要针对主存储器中用户区域进行管理 同时 也包括对辅存储器的管理 操作系统核心 用户区域 快速缓存DataCacheTLB TranslationLookasideBuffer 变换索引缓冲区 内存 DRAM SDRAM等外存 软盘 硬盘 光盘 磁带等 存储层次结构 存储管理的目的 充分利用内存 为多道程序并发执行提供存储基础尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节系统能够解决程序空间比实际内存空间大的问题 6 1 2存储管理的基本功能 存储分配和回收 按照一定的算法把某一空闲的主存区分配给作业或进程以及回收系统或用户释放的空间 地址变换 将程序地址空间中使用的逻辑地址变换成主存中的地址的过程程序加载 装入 时的重定位技术可执行文件生成中的链接技术进程运行时硬件和软件的地址变换技术和机构 存储共享和保护 保证用户程序 或进程映象 共享主存中的数据 并且在各自的存储区域内操作 互不干扰 代码和数据共享地址空间访问权限 读 写 执行 存储器扩充 使用户程序的大小和结构不受主存容量和结构的限制 由应用程序控制 覆盖 由OS控制 交换 整个进程空间 虚拟存储的请求调入和预调入 部分进程空间 6 1 3存储分配方式 直接分配方式 程序员在编写程序时 或编译程序对源程序进行编译时 所用的就是实际的存储地址 前提 事先确定一个作业在主存中的位置 缺点 存储空间的利用率不高 对用户使用不方便 静态分配 在作业装入内存时才确定它们在内存中的位置 并在其整个运行期间不能在内存中移动 也不能再申请内存空间 前提 一个作业装入内存时必须分配其要求的全部存储量 并且退出前不释放 缺点 在多道程序系统中不能有效地共享存储器资源 动态分配 在作业装入内存时才确定它们在内存中的位置 但在其整个运行期间可以再申请内存空间 也可在内存中移动 一个作业已占有的存储区不再需要时 可以归还给系统 所谓存储分配 主要是讨论和解决多道作业之间共享主存的存储空间的问题 需要解决的问题 When How 或是把一个作业的全部或是部分信息分配在主存中 解决存储分配的问题 有三种方式 目前绝大多数系统都采用的是静态或动态存储分配方式分析用户程序的主要处理阶段 编辑 形成源文件编译 形成目标模块链接 由多个目标模块或程序库生成可执行文件装入 构造PCB 形成进程 使用物理地址 运行 建立的进程在CPU在执行装入阶段 程序必须装到内存才能运行 这需要装入程序根据内存的使用情况和分配策略 将上述装入模块放入分到的内存中 这时 可能要进行地址映射 重定位 6 1 4地址重定位 直接分配方式 程序员在编写程序时 或编译程序对源程序进行编译时 所用的就是实际的存储地址 前提 事先确定一个作业在主存中的位置 缺点 存储空间的利用率不高 对用户使用不方便 静态分配 在作业装入内存时才确定它们在内存中的位置 并在其整个运行期间不能在内存中移动 也不能再申请内存空间 前提 一个作业装入内存时必须分配其要求的全部存储量 并且退出前不释放 缺点 在多道程序系统中不能有效地共享存储器资源 动态分配 在作业装入内存时才确定它们在内存中的位置 但在其整个运行期间可以再申请内存空间 也可在内存中移动 一个作业已占有的存储区不再需要时 可以归还给系统 所谓存储分配 主要是讨论和解决多道作业之间共享主存的存储空间的问题 需要解决的问题 When How 或是把一个作业的全部或是部分信息分配在主存中 解决存储分配的问题 有三种方式 6 1 4地址重定位 逻辑地址 相对地址 虚地址 用户的程序经过汇编或编译后形成目标代码 目标代码通常采用相对地址的形式 其首地址为0 其余指令中的地址都相对于首地址来编址 不能用逻辑地址在内存中读取信息 物理地址 绝对地址 实地址 内存中存储单元的地址 物理地址可直接寻址 地址映射 将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址 当程序装入内存时 操作系统要为该程序分配一个合适的内存空间 由于程序的逻辑地址与分配到内存物理地址不一致 而CPU执行指令时 是按物理地址进行的 所以要进行地址转换 内存的物理组织 物理地址 把内存分成若干个大小相等的存储单元 每个单元给一个编号 这个编号称为内存地址 物理地址 绝对地址 实地址 存储单元占8位 称作字节 byte 物理地址空间 物理地址的集合称为物理地址空间 主存地址空间 它是一个一维的线性空间 程序的逻辑结构 程序地址 用户编程序时所用的地址 或称逻辑地址 虚地址 基本单位可与内存的基本单位相同 也可以不相同 程序地址空间 逻辑地址空间 虚地址空间 用户的程序地址的集合称为逻辑地址空间 它的编址总是从0开始的 可以是一维线性空间 也可以是多维空间 重定位 地址映射 在可执行文件装入时需要解决可执行文件中地址 指令和数据 和内存地址的对应 由操作系统中的装入程序loader来完成 重定位的概念 重定位方法 地址映射的功能就是要建立虚实地址的对应关系 实现地址映射有三种方式 绝对装入 编程或编译时确定地址映射关系可重定位装入 静态地址映射 程序执行前 装入内存时一次性链接装入程序 动态装入 动态地址映射 处理机每次访问主存时 有动态地址变换机构 硬件 自动执行 绝对装入 绝对装入 编程或编译时确定地址映射关系编程时确定虚 实地址的关系是指在用机器指令编程时 程序员直接按物理内存地址编程 这种程序在系统中是不能做任何移动的 否则就会出错 优点 装入过程简单 缺点 过于依赖于硬件结构 不适于多道程序系统 静态装入 静态地址映射 在程序装入内存时完成从逻辑地址到物理地址的转换的 在一些早期的系统中都有一个装入程序 加载程序 它负责将用户程序装入系统 并将用户程序中使用的访问内存的逻辑地址转换成物理地址 如下图所示 优点 实现简单 不要硬件的支持 缺点 一个程序通常需要占用连续的内存空间 程序装入内存后不能移动 不易实现共享 动态装入 动态地址映射 动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的 系统中设置了重定位寄存器 由操作系统用特权指令来设置 比较灵活 动态地址映射是在执行时完成的 程序中不执行的程序就不做地址映射的工作 这样节省了CPU的时间 实现动态地址映射必须有硬件的支持 现代计算机系统中都采用动态地址映射技术 覆盖 overlay 引入 其目标是在较小的可用内存中运行较大的程序 常用于多道程序系统 与分区存储管理配合使用 原理 一个程序的几个代码段或数据段 按照时间先后来占用公共的内存空间 将程序的必要部分 常用功能 的代码和数据常驻内存 可选部分 不常用功能 在其他程序模块中实现 平时存放在外存中 覆盖文件 在需要用到时才装入到内存 不存在调用关系的模块不必同时装入到内存 从而可以相互覆盖 即不同时用的模块可共用一个分区 6 1 5覆盖与交换技术 注 另一种覆盖方法 100K A 20K 占一个分区 20K B 50K D 20K 和E 40K 共用一个分区 50K F 30K 和C 30K 共用一个分区 30K 交换 swapping 引入 多个程序并发执行 可以将暂时不能执行的程序或就绪状态的进程送到外存中 从而获得空闲内存空间来装入新程序 交换单位为整个进程的地址空间 常用于多道程序系统或小型分时系统中 与分区存储管理配合使用 又称作 对换 或 滚进 滚出 roll in roll out 程序暂时不能执行的可能原因 处于阻塞状态 低优先级 确保高优先级程序执行 原理 暂停执行内存中的进程 将整个进程的地址空间保存到外存的交换区中 换出swapout 而将外存中由阻塞变为就绪的进程的地址空间读入到内存中 并将该进程送到就绪队列 换入swapin 交换与覆盖区别 交换不需要程序员给出程序段之间的覆盖结构 而覆盖要求明确给出程序段之间的覆盖结构 交换是进程之间或作业之间进行 而覆盖主要在同一作业内来进程内进行内 同时覆盖程序段与被覆盖程序段之间是无关的 6 2单道程序环境下的存储管理 单用户连续存储管理又称单分区模式 适用于单用户情况 任何时刻主存储器中最多只有一道程序主存空间划分为系统区和用户区地址转换与存储保护 地址转换 物理地址 界限地址 逻辑地址多采用静态重定位 采用栅栏寄存器进行存储保护动态重定位 采用定位寄存器进行存储保护单用户连续存储管理的缺点 同单道程序的缺点 系统利用率低 6 3分区存储管理 分区存储管理是满足多道程序设计的最简单的一种存储管理方法 它允许多个用户程序同时存在系统内存中 即共享内存空间 原理 把内存分为一些大小相等或不等的分区 partition 除操作系统占用一个分区外 其余分区用来存放每个进程的程序和数据 特点 适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享 问题 可能存在内碎片和外碎片 内碎片 占用分区之内未被利用的空间外碎片 占用分区之间难以利用的空闲分区 通常是小空闲分区 按分区的时机 分区管理可以分为 固定分区法 作业执行前把内存固定地划分区域 动态分区法 在作业的处理过程中划分区域 6 3 1固定分区法 原理 分区大小可以不相等分区大小相等 适合于多个相同程序的并发执行 分区大小不等 多个小分区 适量的中等分区 少量的大分区 根据程序的大小 分配当前空闲的 适当大小的分区 分区个数不变 大小不变内存分配管理数据结构 分区说明表 分区号 分区大小 起始地址 分区状态 由内存分配程序检索分区说明表 找到符合要求的分区 固定分区 大小相同 固定分区 多种大小 固定式分区内存分配示意图 a 固定式分区说明表 b 固定分区分配操作 分配算法流程 存储保护与重定位 地址转换 每个分区 一道程序 对应一对界地址寄存器 上 下限寄存器 采用静态重定位方式 即由链接 装入程序完成 优缺点优点 简单 要求的硬件支持少 缺点 存在大的碎片 主存利用率低 存储保护类型界限保护 上界寄存器 下界寄存器或基址寄存器 限长寄存器 所有访问地址必须在上下界之间 每个进程都有自己独立的进程空间 如果一个进程在运行时所产生的地址在其地址空间之外 则发生地址越界 当程序要访问某个内存单元时 由硬件检查是否允许 如果允许则执行 否则产生地址越界中断 由操作系统进行相应处理 上下界保护 下界寄存器 存放程序装入内存后的开始地址 首址 上界寄存器 存放程序装入内存后的末地址判别式 下界寄存器 物理地址 上界寄存器 例 有一程序装入内存的首地址是500 末地址是1500 访问内存的逻辑地址是500 345 1200 下界寄存器 500上界寄存器 1500逻辑地址 装入内存的首地 物理地址1 500 500 1000500 1000 1500 2 345 500 845500 845 1500 3 1200 500 1700500 1700 1500 基址 限长寄存器保护 例 有一程序装入内存的首地址是500 末地址是1500 访问内存的逻辑地址是500 345 1200 基址寄存器 500限长寄存器 1000判别式 逻辑地址 限长寄存器1 500 1000 2 345 1000 3 1200 1000 6 3 2动态分区法 系统生成后 操作系统占用内存的一部分 一般在物理内存的开始处 比如 一个操作系统占20KB 装入系统后占用0 20KB的内存空间 剩下的部分作为一个空闲区 当一个用户程序 作业 进程 调入内存时 把这个空闲区的低地址部分的区域分配给它 如图所示 动态分区的分配算法 从可用表或自由链中找到一个足以容纳该作业的可用空白区 若这个空白区比所需求大 则将它分成2个部分 一部分成为已分配区 剩下部分仍为空白区 修改可用表或自由链 并回送一个所分配区的序号或该分区的始址 从空白区中寻找空闲空间是关键 寻找空白区方法的不同 分区分配是对可用表 或自由链 数据结构进行操作 空闲区表的组织有两种方法 按空闲区大小的升序 降序 组织 按空闲区首址升序 降序 组织 通常有3种寻找空白区的方法 最先适应法最佳适应法最坏适应法 最先匹配法 first fit 按分区起始地址的递增次序 从头查找 找到符合要求的第一个分区 该算法的分配和释放的时间性能较好 一旦找到大于或等于所要求内存长度的分区 则结束探索 最佳匹配法 best fit 按分区大小的递增次序 查找 找到符合要求的第一个分区 当申请空闲区时 存储管理程序从表头开始查找 当找到一个满足要求的空闲区时 停止查找 此时的空白区必定是最合适的 因为它是最接近于要求的大小 最坏匹配法 worst fit 按分区大小的递减次序 从头查找 找到符合要求的第一个分区 找到最大的空闲分区 最先适应算法流程 分配策略 最先适应法 最先适应法 首次适应算法 首次适应算法的表是按空闲区首址升序的 即空闲区表是按空闲区首址从小到大 方法组织的 分配时从表首开始 以请求内存区的大小逐个与空闲区进行比较 找到第一个满足要求的空闲后 若空闲区大小与请求区的大小相等 则将该空闲区分配给请求者 并撤消该空闲区所在表目 若大于请求区 就将该空闲区的一部分分配给请求者 然后 修改空闲区的大小和首址 切割空闲区有两种方法 从空闲区头开始或从空闲区尾开始空闲区大小50KB 首址156KB 申请34KB 分配策略 最佳适应法 最佳适应算法 空闲区表按空闲区大小升序方法组织 分配时 按申请的大小逐个与空闲区大小进行比较 找到一个满足要求的空闲区 就说明它是最适合的 即最佳的 分配策略 最坏适应法 最坏适应算法的空闲区表是按空闲区大小降序的方法组织的 从大到小的顺序 分配时总是取表中的第一个表目 若不能满足申请者的要求 则表示系统中无满足要求的空闲区 分配失败 否则 将从该空闲区中分配给申请者 然后修改空闲区的大小 并将它插入到空闲区表的适当位置 三种分配算法举例分析 这三种放置算法的优劣很难区分 要具体情况具体分析 例如 某时刻系统中有三个空闲区其大小和首址为 35KB 100KB 12KB 156KB 28KB 200KB 有一作业系列 JOB1 12KB JOB2 30KB JOB3 28KB 三种分配算法的比较 最先 首次 适应算法实质是尽可能地利用低地址部分的空闲区 而尽量地保证高地址部分的大空闲区 使其不被切削成小的区 其目的是保证在以有有大的作业的到来有足够大的空闲区来满足请求者 最佳适应算法若存储空间中有正好等于所要求大小的空白区 则必然被选中 若不存在这样的空白区 也只对稍大的空白区划分 而绝不会支划分一个很大的空白区 由于空白区一般不可能正好和要求的的相等 这往往使剩下的空白区都比较小 形成 碎片 寻找一个较大空白区时 要花费较多的时间 回收一个分区时 为了把它插入到空白区链中合适的位置上也要花费较大的代价 最坏适应算法克服了最佳适应算法把空闲区切割得太小的缺点 即每次分配时 总是将最大的空闲区切去一部分分配给请求者 其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区 避免了空闲区越分越小的问题 所以很好地利用了碎片 动态分区的回收算法 检查回收的分区是否与空白区邻接 如有则加以合并 使之成为一个连续的大空白区 修改可用表或自由链 空闲释放区与空闲区相邻有四种情况 空闲区与回收区邻接的情况 上临空闲区 将r合并到f1 f1 addr f1 size r sizef size下临空闲区 将r合并到f2 r addr r size r sizef2 size上 下临空闲区 f1 r f2合并到f1 f1 addr f1 size r size f2 sizef1 size撤消f2空闲区上 下都无空闲区 r作为一个空闲区 并插入到空闲区表的适当位置 碎片和紧缩技术 碎片 零头 内存中无法利用的小空闲区 有内 外零头之分 内存紧缩 compaction 将各个占用分区向内存一端移动 使各个空闲分区聚集在另一端 然后将各个空闲分区合并成为一个空闲分区 也称紧凑 拼接技术 对占用分区进行内存数据搬移占用CPU时间如果对占用分区中的程序进行 浮动 则其重定位需要硬件支持 紧缩时机 每个分区释放后 或内存分配找不到满足条件的空闲分区时 分区管理的主要优缺点优点 实现了多个作业或进程对内存的共享 要求的硬件支持少 管理算法简单 实现容易 缺点 内存利用率不高 主要是存储器可能有未用过的信息和碎片问题 作业的大小或进程大小受分区大小限制 难以实现各分区间的信息共享 6 4分页存储管理 问题的提出 分区存储管理的主要问题是碎片问题 在采用分区存储管理的系统中 会形成一些非常小的分区 最终这些非常小的分区不能被系统中的任何用户 程序 利用而浪费 造成这样问题的主要原因是用户程序装入内存时是整体装入的 为解决这个问题 提出了分页存储管理技术 分页的概念逻辑空间分页 程序地址空间分成大小相等的区域 称为页 每页都有一个编号 叫页号 从0开始编排 页面的大小是为2n 通常为1KB 2KB nKB等 内存空间分块 把内存也分成与页面大小相等的区域 称为内存块或物理块 同样从0开始编排 内存分配原则 当一个用户程序装入内存时 以块为单位进行分配 并且一个进程的若干页可分别装入物理上不相邻的内存块中 页大小的例子 计算机系统名页大小Atlas512个48位字Honeywell Multics1024个36位字IBM370 XA和370 ESA4KBVAX系列512BIBMAS 400512BDECAlpha8KBMIPS4KB 16MBUltraSPARC8KB 4MBPentium4KB 4MBPowerPC4KB 页式地址映射 地址变换机构 页式地址映射举例 1 虚地址以十进制数给出页号 INT 虚地址 页大小 位移量 虚地址mod页大小根据题意产生页表 以页号查页表 得到对应页装入内存的块号内存地址 块号 页大小 位移量 页式地址映射举例 例2 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 10 5块 试将虚地址7145 3412转换成内存地址 1 虚地址3412P INT 3412 2048 1W 3412mod2048 1364物理地址 9 2048 1364 19796 页式地址映射举例 2 虚地址7145P INT 7145 2048 3W 7145mod2048 1001物理地址 5 2048 1001 11241 页式地址映射举例 2 虚地址 逻辑地址 程序地址 以十六进制 八进制 二进制的形式给出 将虚地址转换成二进制的数 按页的大小分离出页号和位移量 低位部分是位移量 高位部分是页号 根据题意产生页表 将位移量直接复制到内存地址寄存器的低位部分 以页号查页表 得到对应页装入内存的块号 并将块号转换成二进制数填入地址寄存器的高位部分 从而形成内存地址 页式地址映射举例 例1 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 A 5块 试将虚地址0AFEH 1ADDH转换成内存地址 1 虚地址0AFEH0000101011111110P 1W 01011111110查页表0100101011111110物理地址 4AFEH 页式地址映射举例 2 虚地址1ADDH0001101011011101P 3 011 2W 01011011101查页表0010101011011101物理地址 2ADDH 例 设页长为1K 程序地址字长为16位 用户程序空间和页表如图 说明 在执行指令MOVr1 2500 时 地址转换步骤如下 取出程序地址字2500送虚地址寄存器VR 然后由硬件分离出页号P和页内地址W 实际上分离出页号和页内地址是一件很简单的事 因为页长为1K 所以页内地址占10位 0 9位 页号占6位 10 15位 所以硬件只要简单地取出VR寄存器中的高6位即为页号 低10位即为页内地址 当然我们通过计算可以得到P 2 W 452 根据页号P 2 硬件自动查该进程的页表 找到第2页对应的块号为7 将块号送到内存地址寄存器MR的高6位中 将VR中的W的值452复制到MR的低10位中 从而形成内存地址 系统就以MR中的地址访问内存硬件能自动分离出页号和页内地址 但我们只能通过计算才能得到 联想存储器 在页式存储技术中 我们可看到每访问一次内存 就要做两次访问内存的工作 即 查页表时要作一次访问内存的工作 然后是访问程序要求访问的内存 这样 存取速度降低一倍 将会影响整个系统的使用效率 采用相应技术加快页表的查询速度 在早期的计算机系统中为了加快查表的速度 增加一个具有并行查找能力的高速缓冲存储器 联想存储器 将表放在这个高速缓冲存储器中 快表 采用相应技术加快页表的查询速度 具有快表的地址变换机构联想寄存器 并行查询 空间大小 几K到几百K 部分表项 16 512个 快表与页表同时访问 地址映射过程如下 存储保护类型界限保护 上界寄存器 下界寄存器或基址寄存器 限长寄存器 所有访问地址必须在上下界之间 每个进程都有自己独立的进程空间 如果一个进程在运行时所产生的地址在其地址空间之外 则发生地址越界 当程序要访问某个内存单元时 由硬件检查是否允许 如果允许则执行 否则产生地址越界中断 由操作系统进行相应处理 访问方式保护 保护键 通过保护键匹配来判断存储访问方式是否合法 对于允许多个进程共享的存储区域 每个进程都有自己的访问权限 如果一个进程对共享区域的访问违反了权限规定 则发生操作越权 即读写保护 对每个内存区域指定一个键值和若干禁止的访问方式 进程中也指定键值 如果访问时键值不匹配而且是被禁止的访问方式 则出错 为解决页表规模过大占用内存空间的问题多级页表页表可以部分存放在内存中例 二级页表系统中 一次按逻辑地址的主存访问需要访问三次主存 一次访问页目录 一次访问页表 一次访问具体的数据反置页表块号 页号仅保存调入内存的页面信息 两级和多级页表 现代的大多数计算机系统 都支持非常大的逻辑地址空间 232 264 在这样的环境下 页表就变得非常大 要占用相当大的内存空间 例如 对于一个具有32位逻辑地址空间的分页系统 规定页面大小为4KB即212B 则在每个进程页表中的页表项可达1兆个之多 又因为每个页表项占用一个字节 故每个进程仅仅其页表就要占用4KB的内存空间 而且还要求是连续的 可以采用这样两个方法来解决这一问题 采用离散分配方式来解决难以找到一块连续的大内存空间的问题 只将当前需要的部分页表项调入内存 其余的页表项仍驻留在磁盘上 需要时再调入 两级页表 Two LevelPageTable 逻辑地址结构可描述如下 图4 14两级页表结构 具有两级页表的地址变换机构 多级页表对于32位的机器 采用两级页表结构是合适的 但对于64位的机器 如果页面大小仍采用4KB即212B 那么还剩下52位 假定仍按物理块的大小 212位 来划分页表 则将余下的42位用于外层页号 此时在外层页表中可能有4096G个页表项 要占用16384GB的连续内存空间 必须采用多级页表 将外层页表再进行分页 也是将各分页离散地装入到不相邻接的物理块中 再利用第2级的外层页表来映射它们之间的关系 对于64位的计算机 如果要求它能支持2 1844744TB 规模的物理存储空间 则即使是采用三级页表结构也是难以办到的 而在当前的实际应用中也无此必要 分页管理的优缺点 优点 它不要求连续存放 从而有效地解决了碎片问题 支持虚存缺点 要求有相应的硬件支持 DAT 缺页中断的产生增加了系统开销 处理缺页中断请求调页的算法不当 可能产生抖动现象存在 内碎片 问题 最后一页内总有部分空间得不到利用 不利于程序和数据的共享 6 5分段存储管理 问题的提出 前面介绍的几种存储管理技术中 提供给用户的逻辑地址空间是一维线形的 与内存的物理组织基本相同 但用户编写的程序逻辑结构却不是这样 通常 编写的程序由若干程序模块和数据模块组成 为了满足用户 程序员 在编程和使用等方面的需求 引入了分段存储管理技术 段式管理的基本思想 段式管理是基于分区式管理和页式管理的缺陷和不足而提出的一种更复杂的内存管理方式 分区式和页式管理时的进程地址空间结构是线性的 不同作业或进程之间共享公用子程序和数据变得非常困难 不能按名共享程序和数据 一个页内不能保证是逻辑上完整的子程序或数据块只能采用静态链接 一个用户程序往往由几个程序段 主程序 子程序和函数 所组成 把程序按内容或过程 函数 关系分段 每段有自己的名字 段号 每个段都从0开始编址 采用一段连续的地址空间 各段的长度可以不等 段式管理的程序地址结构段式管理把二维虚拟地址空间设计成段号S与段内相对地址D 段式虚拟地址空间包括 段名 段内地址段号之间无顺序关系 段长也不固定 每个段定义一组逻辑上完整的程序或数据 根据需要 段长可动态增长 段式管理的内存分配段式管理以段为单位分配内存 然后再通过地址映射机构把段式虚拟地址转换成实际的内存物理地址 只把那些经常访问的段驻留内存 而把那些将来一段时间内不被访问的段放入外存 等需要时自动调入内存中 段表和段表寄存器段式管理程序在进行初始内存分配之前 根据用户要求的内存大小为一个作业或进程建立一个段表 以实现动态地址变换和缺段中断处理及存储保护等 段表为每个逻辑段找出所对应的物理内存中块的位置段表通常放在内存 为了方便找到运行进程的段表 系统还要建立一个段表地址寄存器 段表在内存的起始地址和段表的长度 段表 段号 与段名一一对应始址 该段在内存或外存的物理地址长度 该段在内存或外存的实际长度存取方式 存取保护用 如PSW控制位与其相同可访问状态位 指出该段在内存或外存访问位 淘汰算法需要而设 如本段在一段时间内被访问的次数 修改位 本段进入内存后是否被修改过 如修改过 则本段被置换出内存时需写回外存 分页和分段的异同之处相同点 在内存中都不是整体连续 均通过地址映射机构将逻辑地址映射到物理内存 不同点 页是信息的物理单位 用户不需要把程序分页 完全是系统管理的要求 段是信息的逻辑单位 每一段在逻辑上是相对完整的一组信息 分段更好地满足了用户的需求 页的大小是固定的 且在同一系统中大小相等 段的大小因段而异 取决于用户编写的程序 分页的作业地址空间是一维的 分段的作业地址空间是二维的 分段存储管理的基本原理 1 段式管理的内存分配与释放段式管理中以段为单位分配内存 每段分配一个连续的内存区 同一进程所包含的各段之间不要求连续 内存分配与释放在作业或进程的执行过程中动态进行 段式管理时的内存分配要分两种情况 有无足够空闲区满足需求 段式管理中内存回收方法可以用动态分区管理时用的内存回收方法 内存的申请分2种情况 进程要求调入某段时 内存中有足够的空闲区满足该段的内存要求 动态分区式管理时所用的分配算法都可用来作为段式管理时的内存分配 如 最先适应法 最佳适应法 最坏适应法 内存中没有足够的空闲区满足该段的内存要求 此时根据给定的置换算法淘汰内存中一个或几个段 可以使用页式存储管理中的置换算法 如 FIFO置换算法 LRU算法及其近似算法 除了段的初始分配之外 段的动态分配是在处理器所要访问的指令和数据不在内存时产生缺段中断的情况下发生的 段的淘汰或置换算法实际上是缺段中断处理过程的一部分 段式管理的地址变换 段管理程序进行地址变换的步骤 把该进程的段表始址放入段表地址寄存器 由虚地址中的段号比较段表地址寄存器中的段表长度 若0 段号 用户程序的总段数 则访问合法 否则访问越界 由虚地址中的段号S为索引 查找段表 若该段在内存 则判断其存取控制方式是否有错和段内位移是是否超过段长 若都正确 则从段表相应表目中查出该段在内存的起始地址 并将其和段内相对地址D相加 从而得到实际内存地址 若该段不在内存 则产生缺段中断将处理器控制权交给内存分配程序 段式存储管理的地址转换 段号段始址段长 内存 段内位移大于段长发生中断 段超长中断 8292 段式地址映射举例 例 有一系统采用段式存储管理 其段表如下 试将下述虚地址转换成内存地址 2 2 500 3 3 400 4 4 112 5 5 32 试将下述虚地址转换成内存地址 段号段始址段长 2105001235020210090313505904193895 1 0 430 物理地址 210 430 640 段的共享与保护 段的共享 段是按逻辑意义来划分的 可以按段名访问 这极有利于段的共享 如果进程或作业需要共享内存中的某程序段或数据段 只要使用相同的段名 在段表中填入已在内存中的段的起始地址 并置以适当的读写控制权 就可以共享一个逻辑上完整的内存段信息 92 分段共享举例 内存 段的保护措施 利用段表和段长来实现段的保护存权的控制 在段表的 存取方式 工项设置权限 如R W E等 上述保护措施可提供一个多级的存储保护体系 段式管理的优缺点 优点 段式管理提供内外存统一管理的虚拟存储 段长可根据需要动态增加 这对那些需要增加或吸收新数据的来说 将是非常有好处的 便于具有完整逻辑功能的信息段进行共享 便于实现动态链接 缺点 处理机要为地址变换花费时间 要为表格提供附加的存储空间 为满足分段的动态增长和减少外零头 要采用拼接手段 分段的最大尺寸受到主存可用空间的限制 思考题 分段技术比分页更容易实现程序或数据的共享和保护 分段技术中 每一段在逻辑上是相对完整的一组信息 其共享是在段一级出现 这样 任何共享的信息就可单独成一段 同样 段中所有内容就可以用相同的方式进行使用 从而规定相同的保护权限 分页技术中 页是信息的物理单位 在一页中可能存在逻辑上相互独立的两组或多组信息 各有不同的使用方式和存取权限 因而 分页难于进行共享和保护 6 6段页式存储管理 问题的提出 为了获取分段在逻辑上的优点和分页在管理存储空间方面的优点 兼用分段和分页两种方法 即段页式存储管理 1 基本概念 1 段页式管理的基本思想 用分段方法来分配和管理虚拟存储器 而用分页方法来分配和管理主存 实存储器 一方面 可以保持分段地址空间所带来的优点 如允许分段动态扩展 可实现分段的动态链接 分段的共享 实施段保护措施等等 另一方面利用页式管理解决主存分区的拼接 辅存的管理以及对分段大小限制等问题 2 等分内存 把整个内存分成大小相等的内存块 内存块从0开始依次编号 3 地址空间分段 把用户程序分成若干段 每段有个段名 4 段内分页 页面的大小与内存块相同 每段的各个页面都分别从0开始依次编号 虚空间的最小单位是页而不是段 内存就被划分成为若干个页 且每段所拥有的程序和数据在内存中可以分开存放 分段大小也不再受内存可用区的限制 5 逻辑地址的构成逻辑地址由三分部构成 V S P W 6 内存分配以块为单位进行分配 7 段表 页表和段表寄存器为了实现从逻辑地址到物理地址的转换 为每个作业或进程建立一张段表段表中的段长 页表长度段表中的段内存始址 页表地址每个段拥有一张页表 段内的页号映射为内存中的物理块号 段表寄存器 作业段的长度和段表起始地址 段页式管理中段表 页表与内存的关系 段表 第0段页表 第2段页表 内存 段页式存储管理的地址转换 越界中断 段号页表长度页表始址 页号块号 地址变换过程 在段页式管理系统系统中 要对内存中指令或数据进行1次访问的话 至少需要访问3次以上的内存 第1次 由段表地址寄存器得段表始址后访问段表 第2次 访问页表得到所要访问的物理地址 第3次 访问段表和页表之后 本次访问真正需要访问的物理单元 快表或联想寄存器 在联想寄存器中 存放当前最常用的段号S 页号P和对应的内存页面与其它控制栏目 一个在联想寄存器中装有1 10左右的段号 页号及页面的段号式管理 可以通过快速联想寄存器找到90 以上的所要访问的内存地址 查询快表和段表的工作是同时开始的 当发现快表匹配时 段表的查找立即停止 如不匹配 查找段表 页表的过程继续 利用快表的段页式地址变换 物理地址 P P d 6 7虚拟存储器的实现 虚拟存储是一种借助于外存空间 从而允许一个进程在其运行过程中部分地装入内存的技术虚拟页式存储系统虚拟段式存储系统虚拟段页式存储系统 6 7 1概述 所谓虚拟存储器 是指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种存储器系统 其逻辑容量由内存容量和外存容量之和所决定 其运行速度接近于内存速度 而每位的成本却又接近于外存 可见 虚拟存储技术是一种性能非常优越的存储器管理技术 故被广泛地应用于大 中 小型机器和微型机中 虚拟存储器的特征 多次性 对换性3 虚拟性4 离散性 局部性原理 早在1968年 Denning P就曾指出 1 程序执行时 除了少部分的转移和过程调用指令外 在大多数情况下仍是顺序执行的 2 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域 但经研究看出 过程调用的深度在大多数情况下都不超过5 3 程序中存在许多循环结构 这些虽然只由少数指令构成 但是它们将多次执行 4 程序中还包括许多对数据结构的处理 如对数组进行操作 它们往往都局限于很小的范围内 局限性又表现在下述两个方面 1 时间局限性 如果程序中的某条指令一旦执行 则不久以后该指令可能再次执行 如果某数据被访问过 则不久以后该数据可能再次被访问 产生时间局限性的典型原因 是由于在程序中存在着大量的循环操作 2 空间局限性 一旦程序访问了某个存储单元 在不久之后 其附近的存储单元也将被访问 即程序在一段时间内所访问的地址 可能集中在一定的范围之内 其典型情况便是程序的顺序执行 6 7 2请求分页系统 请求分页的页表机制 它是在纯分页的页表机制上增加若干项而形成的 作为请求分页的数据结构 缺页中断机构 即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断 以请求OS将所缺的页调入内存 地址变换机构 它同样是在纯分页地址变换机构的基础上发展形成的 请求分页要解决的问题 1 如何发现执行的程序或访问的数据不在内存 2 程序或数据什么时候调入内存 调入策略 3 当一些页调入内存时 内存没有空闲内存时 将淘汰哪些页 淘汰策略 为了实现请求分页技术 页表应增加相应的内容 反映该页是否在内存 在外存的位置 在内存的时间的长短等 中断位 状态位 0表示该页在内存 1表示该页不在内存 如果不在内存 给出在辅存的地址引用位 0表示最近没有进程访问 1表示最近有进程访问修改位 0该页调入内存后没有修改 1表示该页调入内存后修改过 页表机制 地址变换机构 请求分页中的地址变换过程 内存分配策略和分配算法 1 最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数 当系统为进程分配的物理块数少于此值时 进程将无法运行 进程应获得的最少物理块数与计算机的硬件结构有关 取决于指令的格式 功能和寻址方式 对于某些简单的机器 若是单地址指令且采用直接寻址方式 则所需的最少物理块数为2 其中 一块是用于存放指令的页面 另一块则是用于存放数据的页面 如果该机器允许间接寻址时 则至少要求有三个物理块 对于某些功能较强的机器 其指令长度可能是两个或多于两个字节 因而其指令本身有可能跨两个页面 且源地址和目标地址所涉及的区域也都可能跨两个页面 2 物理块的分配策略 在请求分页系统中 可采取两种内存分配策略 即固定和可变分配策略 在进行置换时 也可采取两种策略 即全局置换和局部置换 于是可组合出以下三种适用的策略 1 固定分配局部置换 FixedAllocation LocalReplacement 2 可变分配全局置换 VariableAllocati