计算机操作系统ppt课件.ppt

存储器管理 1 5 1程序的装入和链接5 2连续分配存储管理方式5 3覆盖和对换5 4分页存储管理方式 离散分配方式 5 5分段存储管理方式作业 本章主要目录 返回开始 2 一个计算机系统由计算子系统 存储子系统和I O子系统组成 出于性能与价格的权衡考虑 存储子系统通常由多种不同的存储介质共同构成 3 寄存器 内存 外存 粗层次图 寄存器 Cache 内存 盘交换区 辅存 联机外存 海存 脱机外存 细层次图 Cache还可以再分三层 片内一级和二级 片外Cache 外存 自顶向下 存取速度越来越慢 成本越来越低 容量越来越大 存取频度越来越低 4 任一程序对计算机的使用 首先是对内存的使用 先装入内存 然后是对处理机的使用 再后才是通过处理机实现对I O设备与文件等其他资源的使用 5 内存是指用来存放当前正在运行的程序的代码和数据及其数据的 是程序中指令本身地址所指的 亦即程序计数器所指的 亦即CPU取指时所用地址所隐含访问的那个存储层次 内存并不是绝对不可缺少的 但内存的存在可以达到性能与价格的更好权衡操作系统内存管理功能的大部分内容 是为了解决内存速度与容量不足的问题 它实现的是与硬件相关和应用无关的内容 6 帕金森Parkinson定律 存储器有多大 程序就会有多大 程序的增大正好填满增大的存储器 7 计算机领域 历史总是在重复自身 当最简单的存储管理方案不再用于台式机时 这些方案仍被一些掌上电脑 嵌入式系统和智能卡系统所采用 8 内存管理的功能和任务硬件相关和应用无关的内容 1 如何才能使用户和用户程序不涉及内存物理细节 操作系统 编译程序和硬件共同完成 2 如何为用户程序完成程序装入工作 操作系统在编译程序的配合下完成 3 如何提高内存利用率和弥补用户对内存容量要求与内存实际容量之间的差距 4 如何解决内存速度与CPU速度不匹配的问题 5 如何满足系统和用户的安全要求 内存保护6 如何满足用户程序的动态扩缩要求7 共享8 代价 9 5 1 1装入方式一 绝对装入方式二 可重定位装入方式三 动态运行时装入方式5 1 2程序的链接程序的装入一 静态链接二 装入时动态链接三 运行时动态链接 5 1程序的装入和链接 返回本章目录 10 存储器管理 主存储器 又称内部存储器 处理机存储器 存储器管理 讨论的主要对象就是主存储器 BACK 返回本节目录 NEXT 11 许多操作系统之间最明显的区别特征之一是所使用的存储管理方法不同 主存储器管理技术分为两大类 实存储器管理和虚拟存储器管理 本章研究常用的几种实存储管理技术 下章将讨论虚拟存储管理技术 BACK 返回本节目录 NEXT 12 实存储管理技术 分连续分配和离散分配 连续分配又分 单一连续 固定分区 可变分区和动态重定位可变分区 离散分配分 分页 分段和段页式 虚拟存储管理技术 请求分页 请求分段和段页虚拟式 对每一种管理方式从以下五个方面来理解并掌握 分配 去配 释放或回收 地址重定位 保护 防止地址越界和控制正确存取 和共享 13 整个计算机系统的功能很大程度上取决于主存储器的结构组织和实现方法 就主存的功能而言 首先是存放系统和用户程序的指令和数据 每一项信息都存放在主存的特定位置上 BACK 返回本节目录 NEXT 14 信息在主存是按 位 存放的 为了能对信息进行访问 要对这些位置进行编号 这些编号称为地址 以什么为单位进行编址呢 早期的计算机中 存储器是按字组织 每个字分配一个地址 目前多数计算机以字节为单位进行编址 BACK 返回本节目录 NEXT 15 为了更多的存放并更快地处理用户信息 目前许多计算机把存储器分为三级 高速缓冲存储器 主存储器和外部存储器 用户的程序在运行时应存放在主存中 所以把那些不马上使用的程序 数据放在外部存储器 又称次级存储 中 当用到时再把它们读入主存 BACK 返回本节目录 NEXT 16 主存储器管理中的研究课题 单道程序阶段 人们研究了覆盖技术来解决用户作业空间大于实际的主存空间的矛盾 多道程序系统出现后 主存容量不足的矛盾更为突出 由于多道程序共享主存 所以对主存的管理工作又出现了如何在各程序间分配主存空间的问题 同时还要考虑如何防止各程序有意无意地互相干扰和破坏的问题 BACK 返回本节目录 NEXT 17 再者 程序是相对编址的可浮动的程序 这些程序被装入主存时就需重定位 综上所述 目前关于主存储器管理的主要研究课题归纳为四个方面 BACK 返回本节目录 NEXT 18 1 主存分配 是存储管理研究的主要内容 本章将研究各种主存分配算法 以及每种算法所要求的数据结构 但不涉及某个具体的存储管理系统的程序 读者只要掌握了算法 了解其数据结构 就可以编写一个程序模块了 BACK 返回本节目录 NEXT 19 2 地址映象或重定位 主要研究各种软件和硬件的地址转换技术和机构 3 存储保护 研究如何保护各程序区中信息不被破坏和偷窃 BACK 返回本节目录 NEXT 20 4 存储器扩充 用存储管理软件来实现逻辑上的扩充 即所谓的虚拟存储技术 BACK 返回本节目录 NEXT 21 如何使一个用户程序到内存中去执行 分如下几步 1 编译 Compile 转换成机器指令 将符号地址转换为内存地址 2 链接 Link 将各模块中的相对地址统一转换成相对于该程序起址的位移 3 装入 Load本节 简要地讲述了程序的链接和装入过程 BACK 返回本节目录 NEXT 22 库 链接程序 装入模块 装入程序 内存 第一步编译 第二步链接 第三步装入 编译程序产生的目标模块 BACK 返回本节目录 NEXT 23 5 1 1程序的装入单个目标模块 是如何装入内存的 三种方式 1 绝对装入方式 程序中使用绝对地址 只适用于单道程序环境 2 可重定位方式 根据内存当时的实际使用情况 装入到内存的适当位置 与目标模块中的地址不一致时 要进行转换 装入时一次完成 又称静态重定位 不允许程序在运行时在内存中移动 3 动态运行时装入方式 装入内存后 并不立即转换地址 而是到真正执行时才进行转换 需要重定位寄存器 BACK 返回本节目录 NEXT 24 一 绝对装入方式absoluteloadingmodeP119二 可重定位装入方式relocatableloadingmode BACK 返回本节目录 NEXT 25 可重定位装入程序 根据内存的当前使用情况 将程序装入到内存的某个位置 把有效地址 相对地址 与本程序在内存中的起始地址相加 得到正确的物理地址 BACK 返回本节目录 NEXT 26 指令地址和数据地址同样都要进行修改 我们把装入时对程序中的指令和数据地址进行修改的过程称为重定位 即进行地址转换 这种地址变换若只是在装入时一次完成的 称为静态重定位 staticrelocatingaddress 用在早期的单用户单任务系统中 BACK 返回本节目录 NEXT 27 三 动态运行时装入方式dynamicrun timeloading绝对装入方式 只能将程序装入到内存中事先指定的地址 多道程序环境下 不可能事先知道每一道程序在内存中的位置 该方式只适合于单道程序环境 BACK 返回本节目录 NEXT 28 可重定位装入方式 可将程序装入到内存中的任何允许的地方 可用于多道程序环境 但它不允许程序在运行时 在内存中移动 因为 程序在内存中移动 要求相应地改变它们的物理地址 必须对程序和数据的地址 绝对地址 进行修改 才能正常运行 BACK 返回本节目录 NEXT 29 但在多进程并发运行中 程序在内存中的位置 需要经常进行改变 这种情况下 应采用动态运行时装入方式 BACK 返回本节目录 NEXT 30 动态运行时的装入程序 将程序装入内存后 并不立即把程序中的相对地址转换为绝对地址 而是当程序真正执行时才进行转换 这叫动态重定位 dynamicrelocatingaddress 需要硬件支持 BACK 返回本节目录 NEXT 31 5 1 2程序的链接链接是将一组目标模块及它们所需的库函数 装配成一个装入模块 必须将目标模块中的相对地址和外部调用符号转换成装入模块中的统一的相对地址 方法有三种 静态链接 装入时动态链接和运行时动态链接 BACK 返回本节目录 NEXT 32 静态链接 程序运行前链接成装配模块 以后不再拆开 即事先进行链接 装入时动态链接 目标模块在装入内存时 边装入边链接 运行时动态链接 程序执行中需要该模块时 才对它进行链接 33 一 静态链接三个目标模块A B C 长度分别为L M和N A中有语句CallB B中有语句CallC B和C都是外部调用符号 P120若将A B C链接装配成一个目标模块 应如下处理 BACK 返回本节目录 NEXT 34 1 对相对地址进行修改一般 由编译程序产生的目标模块 其起始地址为0 A的地址为0 每个模块中的地址是相对于0的 链接成一个目标程序后 B和C的起始地址不再是0 而是L和L M 须修改B和C中的相对地址 即B中所有的相对地址加上L C中的所有相对地址加上L M BACK 返回本节目录 NEXT 35 2 变换外部调用符号将每个模块中所用的外部调用符号 变换为相对地址 即把CallB中的B 起始地址 变换为L 把CallC中的C变换为L M BACK 返回本节目录 NEXT P120 36 先进行链接而形成的一个完整的装入模块 称为可执行文件 一般不再拆开它 运行时直接装入内存 这种事先进行链接 以后不再拆开的链接方式 称为静态链接方式 BACK 返回本节目录 NEXT 37 二 装入时动态链接load timedynamiclinking是指 程序编译形成若干个目标模块 在装入内存时 边装入边链接 即在装入一个目标模块时 发生一个外部模块调用 将引起装入程序去找相应的外部目标模块 并将它装入内存 BACK 返回本节目录 NEXT 38 它的优点 1 便于软件版本的修改和更新采用装入时动态链接方式 可比较容易的修改或更新各个目标模块 而静态链接方式下 形成的装入模块 要重新打开装入模块来修改 一般是不可能的 BACK 返回本节目录 NEXT 39 2 便于实现目标模块共享采用装入时动态链接的方式 一个目标模块可链接到几个应用模块 而采用静态链接方式 每个应用模块都必须含有该目标模块的拷贝 BACK 返回本节目录 NEXT 40 三 运行时动态链接run timedynamiclinking动态装入方式 可将一个程序装入到内存的任何位置 但装入模块的结构是静态的 表现在 一是在进程 程序 的整个运行期间 装入模块是不改变的 再者 每次运行时的装入模块是相同的 BACK 返回本节目录 NEXT 41 实际上 每次要运行的模块可能是不相同的 但事先无法知道本次要运行哪些模块 只能把所有可能要运行的模块 装入时全部链接在一起 每次执行时的装入模块是相同的 这种方式是低效的 如 错误处理模块 若在程序整个运行期间 一直不出现错误 便不会用到该模块 BACK 返回本节目录 NEXT 42 为避免上述情况 出现了运行时动态链接方式 该方式将某些目标模块的链接 延迟到执行时再进行 即在执行过程中 发现一个被调用模块尚未装入内存中时 由OS找到该模块 装入内存 并链接到调用者模块上 BACK 返回本节目录 NEXT 43 5 2 1单一连续分配5 2 2固定分区分配一 划分分区的方法二 内存分配5 2 3动态分区分配一 分区分配中的数据结构二 分区分配算法三 分区分配操作5 2 4动态重定位分区分配一 紧凑二 动态重定位三 动态重定位分区分配算法 5 2连续分配存储管理方式 返回本章目录 44 连续分配是指程序在内存中要占一个连续的内存空间 两种方式 1 单一连续分配方式单道环境中 内存分为系统区和用户区 适于单用户 单任务OS中 BACK 返回本节目录 45 2 分区式分配方式进一步分为 1 固定分区式 2 动态分区 又称可变分区 分区式要求将一个用户程序分配到一个连续的内存空间中 可能会产生一些不可利用的内存零头 碎片 BACK 返回本节目录 NEXT 46 5 2 1单一连续分配采用这种存储管理方式 内存分为两个分区 1 系统区 低址部分 驻留OS BACK 返回本节目录 NEXT 47 2 用户区 系统区以外的全部内存空间 提供给用户用的 为防止OS受到用户程序的破坏 设置一个保护机构 基址寄存器和界限寄存器 存放该程序的逻辑地址范围 以此来实现数据保护 BACK 返回本节目录 NEXT 48 BACK 返回本节目录 NEXT 早期的大型机和小型机 现在很少用了 掌上计算机和嵌入式系统 早期的个人计算机MSDOS 49 5 2 2固定分区分配 fixedpartition 定长分区或静态分区 固定分区式分配 最早用于多道程序环境的存储管理方式 60年代的IBM 360的MFT系统中 它将内存空间划分为若干个固定大小的区域 每个分区中可装入一道作业 BACK 返回本节目录 NEXT 50 一 划分分区的方法1 分区大小相等缺点 碎片 hole 空洞 或称零头 该方式 主要用于利用一台计算机去控制多个相同对象 所需的内存空间大小相等 的场合 BACK 返回本节目录 NEXT 51 2 分区大小不等在内存中划分多个较小的分区 适量的中等分区和少量的大分区 系统初次启动时 系统操作员根据当天的作业情况把主存储器划分成大小不等但数目固定的分区 BACK 返回本节目录 NEXT 52 二 内存分配实现内存分配 由小到大建立一张分区使用表 主存分配表 每个分区要登记一个表项 包含分区的起始地址 大小及状态 是否已分配 BACK 返回本节目录 NEXT 53 固定分区存储管理的主存分配表 54 由内存分配程序检索该表 找出一个满足要求的 尚未分配的分区 将它分配该程序 修改分区使用表中该分区表项中的状态 若找不到大小足够的分区 则拒绝为该用户程序分配内存 BACK 返回本节目录 NEXT 55 0 30 45 75 125 225 固定分区分配表 A B C 15 30 50 a 分区说明表 b 存储空间分配情况 BACK 返回本节目录 NEXT 56 固定分区的缺点 无法装入大作业 覆盖技术有碎片 57 数据库 在多道固定分区情况下 操作系统的存储分配模块和存储释放模块都要用到关于主存分区情况的说明信息 以及这些存储区的使用状况信息 即存储管理的数据库 常被称为存储分块表 其中包含三项信息 BACK 返回本节目录 NEXT 58 1 大小 是指该存储块的大小 以字节为单位 2 位置 指该存储块在主存中的起始地址 3 状态 表明该存储块是否已被使用 还有一项信息 区号 起存储键作用 未包含在表格中 BACK 返回本节目录 NEXT 59 存储分块表是存储分配和释放这两个模块的数据库 在程序中这个表用相应语言的数据类型来表示 在Pascal中用一维数组表示 数组元素是记录结构 数组下标是分区的序号 描述如下 BACK 返回本节目录 NEXT 60 typeN integer Entry recordsize integer location integer status boolean endvarMBT array 1 N ofEntry BACK 返回本节目录 NEXT 61 固定分区的存储分配算法和可变分区的分配算法是一样 所使用的分配算法要求是查表时间要短 且分区内的碎片浪费要最少 最好是最佳适应法和最先适应分配算法的结合 MBT中的各分区按分区大小排序 最小分区在表头 BACK 返回本节目录 NEXT 62 5 2 3动态分区分配 可变分区分配variablepartition 根据进程的实际需要 动态地为之分配连续的内存空间 要解决如下问题 1 分区分配中所用的数据结构 2 分区的分配算法 3 分区的分配和回收操作 BACK 返回本节目录 NEXT 63 一 分区分配中的数据结构记录内存的使用情况 已分配区表和未分配区表 形式 1 空闲分区表 可用表为内存中每个尚未分配出去的分区登记一个表项 每个分区的表项包含分区序号 分区始址 分区大小及状态等信息 缺点 表格自身要占用空间 BACK 返回本节目录 NEXT 64 2 空闲分区 双向 链 自由链 自由主存队列在每个分区的起始部分 设置一些用于控制分区分配的信息 及通过 前 后向指针将所有的分区链接成一个双向链 若某一分区被分配出去后 应把状态位由0改为1 此时 前 后向指针失去意义 BACK 返回本节目录 NEXT 65 空闲分区表 空闲分区链 BACK 返回本节目录 NEXT 66 二 分区分配算法从空闲分区表或空闲分区链中 选择一个分区分配给作业的算法 1 首次适应算法FF最先适应算法FirstFit以空闲分区链为例 FF要求空闲分区链以地址递增的次序链接 BACK 返回本节目录 NEXT 67 该算法 优先利用内存中低址部分的空闲分区 在高址部分的空闲分区很少被利用 保留了高址部分的大空闲区 为以后到达的大作业分配大的内存空间创造了条件 BACK 返回本节目录 NEXT 68 缺点 是低址部分不断被划分 会留下许多碎片 每次查找又都从低址部分开始 增加了查找的时间开销 BACK 返回本节目录 NEXT 69 2 循环首次适应算法 nextfit NF 下次适配算法该算法为进程分配内存空间时 从上次找到的空闲分区的下一个空闲分区开始查找 直至找到第一个满足要求的空闲分区 并从中划出一块与请求的大小相等的内存空间分配给作业 BACK 返回本节目录 NEXT 70 需设置一个起始查寻指针 以指示下一次开始查寻的空闲分区 并采用循环查找方式 即若最后一个 链尾 空闲分区 其大小不能满足要求时 返回到第一个空闲分区 从头开始查寻 找到所需分区后 要相应调整起始查寻指针 BACK 返回本节目录 NEXT 71 该算法 能使内存中的空闲分区更均匀 减少了查找的开销 但不利于大作业的调入 Bays 1977 的仿真程序证明下次适配算法的性能略低于首次适配算法 BACK 返回本节目录 NEXT 72 3 最佳适应算法 bestfit BF 所有的空闲分区 按大小递增的顺序形成空闲分区链 缺点是 碎片会更小 4 最坏适应算法 worstfit WF 空闲分区按大小递减的次序排列 BACK 返回本节目录 NEXT 73 特点 总挑选满足作业要求的最大的分区分配给作业 使剩下的部分也比较大 可继续使用 缺点 当再有大作业时 可能得不到满足 BACK 返回本节目录 NEXT 74 5 快速适应算法 quickfit 又称分类搜索法 将分区根据经常用到的大小分类 相同容量的分区单独成为一个空闲链 系统建立管理索引表 进行分配时分区不进行分割 合并分区时算法复杂 分配时以进程为单位 一个分区只属于一个进程 有碎片 是典型的以空间换时间的作法 75 模拟实验表明 在减少时空代价上 最先适应和最佳适应都比最坏适应更好 在空间代价上 最先适应或最佳适应都不能明确说是最好 但最先适应一般更快 最先适应对某些系统更好 最佳适应对于另外一些系统更好 76 6 伙伴系统 Buddy Knuth 1973年 每个分区大小均为2k次幂 1 k m 最大空闲块为2m个单位 最小空闲块为20个单位 建立k个空闲链表 时间代价上比分类搜索法差 比顺序算法好空间代价上比分类搜索法好 比顺序算法差适用于多处理机系统 7 哈希算法 77 三 分区分配操作1 分配内存设请求的分区大小为u size 分区的大小表示为m size 若m size u size size 将整个分区分配给请求者 否则 从该分区中划分出与请求的大小相等的内存空间分配给请求者 余下的部分留在空闲分区链或空闲分区表 最后 将分配区的首址返回调用者 流程图 P125 BACK 返回本节目录 NEXT 78 2 回收内存有四种情况 1 回收区与插入点的前一个分区相邻接 2 回收分区与插入点后的一分区邻接 3 回收区同时与插入点的前 后两个分区邻接 4 回收区前后没有空闲分区与它相邻时 流程图示 P125 BACK 返回本节目录 NEXT 79 使用可变分区存储管理的系统 IBM的OS MVT 80 5 2 4动态重定位分区分配一 紧凑 拼接 紧缩或澄清 连续分配中 会出现 外部碎片 或 外零头 解决的方法是 拼接 或 紧凑 BACK 返回本节目录 NEXT 81 时机 一 在某个分区回收时立即进行拼接 系统中总只有一个连续的空闲区 频率过大 开销加大 二 当找不到足够大的空闲区且空闲区的总容量可满足作业要求时进行拼接 管理复杂 图示 P127 BACK 返回本节目录 NEXT 82 注意 紧凑后的用户程序在内存中的位置发生了变化 必须对程序和数据的地址进行修改 变换 即进行重定位 二 动态重定位动态运行时装入方式 程序中的相对地址转换为物理地址的任务 要到程序执行时才进行 BACK 返回本节目录 NEXT 83 系统中增加一个重定位寄存器 存放程序在内存中的起始地址 程序执行时 真正访问的地址是相对地址与重定位寄存器中的地址相加得到的 BACK 返回本节目录 NEXT 84 地址变换过程是在程序执行时 随着对每条指令和数据的访问而自动进行的 称为动态重定位 当程序发生了移动 只需置换重定位寄存器中的起始地址 P128 BACK 返回本节目录 NEXT 85 三 动态重定位分区分配算法与动态分区分配算法相似 区别在于 该算法中 增加了 紧凑 功能 动态重定位分区分配算法框图 P128 BACK 返回本节目录 NEXT 86 总结 固定分区分配采用静态地址重定位 运行时使用绝对地址 由加载程序进行地址越界检查 可变分区分配采用动态地址重定位 由硬件完成 硬件设置两个专用控制寄存器 基址寄存器和限长寄存器 但都会出现碎片 87 练习 88 四 分区的保护连续分配方式中 为防止一个用户作业破坏操作系统或其他用户 常采用界限寄存器或保护键的方法来进行分区的保护 1 界限寄存器 一对上 下限寄存器或一对基址 限长寄存器 存放正在执行的作业在内存中的结束地址和起始地址 或起始地址和长度 每当进行内存访问时 硬件自动将所访问的内存地址与界限寄存器的值进行比较 若发生地址越界 则产生越界中断 89 2 保护键 每个分区分配一个单独的保护键 相当于一把锁 同时为每个进程分配一个相应的保护键 相当于一把钥匙 每当进行内存访问时 都要检查钥匙和被访问单元的锁是否匹配 若不匹配 则发生保护性中断 90 5 3覆盖Overlay和对换 Swapping 5 3 0覆盖技术 Overlay 5 3 1多道程序环境下的对换5 3 2对换空间的管理5 3 3进程的换出与换入一 进程的换出二 进程的换入 返回本章目录 BACK 主存不足的存储管理技术 91 覆盖技术 覆盖技术是针对大程序 小空间 装不下的问题而提出的 其思想是对一个程序 仅将其中在执行期间的任何时刻都需要的过程和数据 在该程序开始执行时装入并一直保存在内存 而该程序中的其他代码和数据则只在需要时装入 且不同时执行的代码或数据相互覆盖 需要事先设计并确定好所有代码和数据的位置 主程序和覆盖驱动程序常驻内存 程序员必须正确设计覆盖结构和编程 覆盖一般只用于不采取虚存技术的系统 92 5 3对换 对换 交换 技术 最早是CTSS中实现的 该系统是单用户系统 在内存中只允许一道作业运行 其它作业都在外存的后备队列中 每次只调入一个作业到内存 运行一个时间片后 将它调出 再调入下一个作业 BACK 返回本节目录 NEXT 93 5 3 1多道程序环境下的对换多道程序环境下 一方面 内存中的某些进程被阻塞 却仍占据大量的空间 甚至所有进程都被阻塞 使CPU停止等待 另一方面 外存上有许多作业 因无内存而不能进入内存 BACK 返回本节目录 NEXT 94 为解决这种问题 增设了对换设施 所谓 对换 或 交换 是指 UNIX中 设置一对换进程 由它将内存中暂时不能运行的进程 调出到磁盘上 又将磁盘上具备运行条件的进程 调入内存 BACK 返回本节目录 NEXT 95 WINDOWS中 若一个进程调入内存时 发现内存不足时 由系统将老进程调出到磁盘上 这种不是完全的对换 因为对换本身是用户的行为 由用户决定是否进行对换及对换出哪个进程 不是系统的行为 BACK 返回本节目录 NEXT 96 对换可以整个进程为单位 称为 整体对换 或 进程对换 一般用于分时系统中 对换以 页 或 段 为单位进行 称为 页面对换 或 分段对换 统称 部分对换 本节 介绍进程对换 第六章将主要介绍部分对换 要实现进程对换 应先实现如下三种功能 BACK 返回本节目录 NEXT 97 5 3 2对换空间 外存空间 的管理具有对换功能的OS 一般把外存分为 文件区和盘对换区 前者存放文件 采用离散分配方式 后者存放从内存换出的进程 采用简单的连续分配方式 BACK 返回本节目录 NEXT 98 要管理对换区的空闲块 系统配置相应的数据结构 空闲分区表或空闲分区链 表中的每个表目包含 对换分区首址和对换区长度 以盘块为单位 BACK 返回本节目录 NEXT 99 对换区的分配 采用连续分配方式 分配算法可采用 首次适应算法 循环首次适应算法和最佳或最坏适应算法 其分配和回收操作同前 BACK 返回本节目录 NEXT 100 5 3 3进程的换出与换入系统内核发现内存不足时 调用对换程序或唤醒对换进程 实现进程的换入与换出 一 进程的换出将内存中的某些进程调至对换区 步骤 BACK 返回本节目录 NEXT 101 1 选出被换出的进程首先选择处于阻塞或睡眠状态的进程 从中选择优先级最低的进程换出 也可同时考虑进程在内存中的驻留时间 若已无阻塞进程 选择优先级最低的就绪进程换出 同样要考虑驻留时间 BACK 返回本节目录 NEXT 102 2 换出过程只能换出非共享的程序和数据段 对于共享的程序段和数据段 对每个段的引用计数执行减1操作 若其值不为0 表示有进程需要它 不能被换出 若值为0 表示该程序段或数据段 已不被其它进程需要 可将它们换出 BACK 返回本节目录 NEXT 103 要申请对换空间 对进程控制块和内存分配表等进行修改 若此时 还有可换出的进程 继续上述过程 直到内存中无阻塞进程为止 BACK 返回本节目录 NEXT 104 二 进程的换入找出 就绪且换出 的进程 有多个时 选择换出时间最长的进程作为换入进程 再根据进程的大小申请内存 1 申请成功 直接换入进程 2 申请失败 先将内存中的某些进程换出 再将该进程换入 BACK 返回本节目录 NEXT 105 若还有可换入的进程 继续执行上述的过程 直到所有 就绪且换出 状态的进程全部换入或已无法获得足够大的内存来换入进程为止 BACK 返回本节目录 NEXT 106 5 4分页存储管理方式 5 4 1分页存储管理的基本方法一 页面和物理块二 页表三 页面大小的选择5 4 2地址变换机构一 基本的地址变换机构二 具有快表的地址变换机构5 4 3两级和多级页表一 两级页表二 多级页表结构5 4 4反置页表 返回本章目录 107 若允许将一个进程直接分散地分配到许多不相邻的分区中基于这一思想产生了离散分配方式 根据离散分配时所用基本单位的不同 分为三种 BACK 返回本节目录 NEXT 108 1 分页存储管理该方式中 用户程序的 逻辑 地址空间被划分成若干个固定大小 一个系统中只能有一种大小的页面 的区域 称为 页 或 页面 一般大小是1KB 同时 将内存空间 物理地址空间 也分成若干个物理块 页和块的大小相等 BACK 返回本节目录 NEXT 109 这样 可将用户程序的任一页放在内存中的任一块中 实现了离散分配 内存中的碎片大小绝不会超过一页 分页是为实现离散分配方式 以提高内存利用率 仅仅是由于系统管理的需要 而不是用户编程的需要 BACK 返回本节目录 NEXT 110 2 分段存储管理它把用户程序的地址空间分成若干个大小不等的段 由编译程序在对源程序进行编译时 根据信息的性质来划分 每段定义一组相对完整的逻辑信息 如 C程序中可为全局变量 函数的代码部分 函数的局部变量等 分别建立各自的段 存储分配时 以段为单位 这些段在内存中是不相邻接的 也实现了离散分配 BACK 返回本节目录 NEXT 111 3 段页式存储管理这是分页和分段相结合的产物 兼备两者的优点 BACK 返回本节目录 NEXT 112 5 4 1分页存储管理的基本原理一 页面和物理块分页存储管理方式中 将一个进程的逻辑地址空间分成若干个大小相等的片 称为页面或页 BACK 返回本节目录 NEXT 113 内存空间也等分成与页相同大小的若干个存储块 称为物理块或页框frame 又称页帧 两者都进行编号 都从0开始 进程调入内存时 以块为单位将进程中的若干页分别装入多个可以不相邻接的块中 进程的最后一页一般装不满一块 形成了不可利用的碎片 称为 页内碎片 BACK 返回本节目录 NEXT 114 系统建立一张主存物理块表 记录所有的物理块 现代系统大多采用位示图的方法 每次分配时 先检查空闲块数能否满足用户进程的要求 115 分页存储管理方式中的 变换或物理 地址结构 含有两部分 两部分构成的地址为32位 0 11为页内地址 即每页大小为4KB 12 31位为页号 地址空间最多允许有1MB页 对某一机器 地址结构是一定的 BACK 返回本节目录 NEXT 116 给定一个逻辑地址为A 页面大小为L 则页号P和页内地址d可按下式求得 这一步是由机器硬件实现的 P INT A L d A modL如 若系统的页面大小为1KB 设A 2170B 可求得 P 2 d 122 BACK 返回本节目录 NEXT 117 这是用除的方法可将逻辑地址转换成页号和页内地址 效率太低了 为此规定页的大小必须是2的幂 可把地址从第几位分开成两部分 高位部分所表示的数是页号 低位部分所代表的数是页内地址 采用页面大小是2的幂的优点是省去除法 由硬件自动把地址场中的数拆成两部分来决定对应的页号和页内地址 118 二 页表分页系统中 允许将进程的每页离散地存储在内存的任一物理块中 系统要保证进程的正确运行 即能在内存中找到每个页面所对应的物理块 需要为每个进程建立一张页面映射表PMT 简称页表 BACK 返回本节目录 NEXT 119 进程地址空间内的所有页 0 n 1 依次 0 n 1 在页表中有一页表项 记录了相应页在内存中对应的物理块号 配置了页表后 进程执行时 通过查找页表 即可找到每页在内存中的物理块号 页表是实现从页号到物理块号的地址映射 BACK 返回本节目录 NEXT 120 一般在页表的表项设置一存取控制字段 对该存储块中的内容进行保护 若存取控制字段仅一位时 表示该存储块的内容是允许 读 写 还是只读 若存取控制位是二位 可表示 读 写 只读和只执行等存取方式 BACK 返回本节目录 NEXT 121 三 页面大小的选择分页系统中的页面大小是由机器的地址结构决定的 确定地址结构时 若选择的页面小 若选择的页面大 可减少页表长度 提高换进换出的效率 但会使页内碎片增大 一般 页面的大小选择适中 大小是2的幂 在 间 即在512B 4 8 KB之间 BACK 返回本节目录 NEXT 122 5 4 2地址变换机构 这是与连续分配方式的根本区别将逻辑地址 变换为物理地址 页内地址和物理地址是一一对应 因为是同样大小的 的 所以 地址变换机构的任务是 将逻辑地址中的页号 转换为内存中的物理块号 页面映射表的作用就是用于实现从页号到物理块号的变换 所以 地址变换任务是借助于页表完成的 BACK 返回本节目录 NEXT 123 一 基本的地址变换机构页表由一组专门的寄存器来实现的 一个页表项用一个寄存器 现代计算机的页表都比较大 页表项的总数可达几千甚至几十万个 不可能用寄存器实现 所以 页表都是驻留在内存中 BACK 返回本节目录 NEXT 124 系统设置一个页表寄存器PTR Page TableRegister 存放页表在内存的始址和页表的长度 未执行时 页表的始址和长度是存放在PCB中的 当调度到该进程时 才将它们装入到页表寄存器中 所以 单处理机系统中 系统允许并发运行多个进程时 只需一个页表寄存器即可 BACK 返回本节目录 NEXT 125 进程要访问某逻辑地址中的数据时 分页地址变换机构会自动地将有效地址 相对地址 分为页号和页内地址两部分 再以页号为索引去检索页表 查找操作由硬件执行 在执行检索之前 先将页号与页表长度进行比较 若页号大于或等于页表长度 表示越界错误 产生一中断 BACK 返回本节目录 NEXT 126 若未出现越界错误 则将页表始址 从0开始 与页号和页表项长度的乘积相加 得到该表项在页表中的位置 于是 可从中得到该页的物理块号 将之装入物理地址寄存器中 再将逻辑地址寄存器中的页内地址直接送入物理地址寄存器的块内地址字段中 即完成了地址的变换 BACK 返回本节目录 NEXT 127 页表寄存器 越界中断 逻辑地址L 块号 页号 物理地址 页表 0 2 1 3 分页系统的地址变换机构 BACK 返回本节目录 NEXT 练习 128 二 具有快表的地址变换机构页表是存放在内存中的 CPU每次存取一个数据时 要访问两次内存 第一次 访问内存中的页表 从中找到该页的物理块号 将此块号与页内偏移量W拼接形成物理地址 第二次 根据第一次所得数据物理地址 从中获得数据或向此地址写入数据 由此 计算机的处理速度降低近1 2 BACK 返回本节目录 NEXT 129 为了提高地址变换速度 可在地址变换机构中 增设一个具有并行查寻能力的特殊高速缓冲存储器 又称联想存储器 associativememory 或快表 IBM系统中又取名为TLB translationlookasidebuffer 转换检测缓冲区 用来存放当前访问的那些页表项 BACK 返回本节目录 NEXT 130 地址变换 CPU给出有效地址后 由地址变换机构自动将页号p送入高速缓冲存储器 并将此页号通过并行匹配与快表中的所有页号进行比较 若其中有与此相匹配的页号 则表示所要访问的页表项在快表中 可以直接读出该页所对应的物理块号 并送物理地址寄存器中 BACK 返回本节目录 NEXT 131 若在快表中未找到相应的页表项 这时 还必须再访问内存中的页表 找到后 把从页表项中读出的物理块号送地址寄存器 同时 将此页表项存入快表中的一个寄存器单元中 要重新修改快表 此时 若快表已满 OS将一个不再需要的页表项将它换出 BACK 返回本节目录 NEXT 132 页表寄存器 逻辑地址L 越界中断 页号 块号 页号 块号 页表 快表 物理地址 具有快表的地址变换机构 BACK 返回本节目录 NEXT 133 一般 联想存储器不能很大 通常只能存放16 512个页表项 其数目也不能太多 对中 小型作业而言 有可能已经把全部页表项都放在快表中了 对大型作业 只能将一部分页表放入其中 配置联想存储器的效率 决定于对它访问时的命中率 如 BACK 返回本节目录 NEXT 134 检索联想存储器的时间为20ns 访问内存的时间为100ns 若能在联想存储器中检索到CPU给出的页号 则CPU为了存取一个数据 总共需要的时间t1 120ns 若不能在联想存储器中找到该页号 则总共需要时间t2 220ns 若假定访问联想存储器的命中率分别为0 50 80 90 98 时 其有效访问时间 分别如下表 BACK 返回本节目录 NEXT 135 一般的访问联想存储器的命中率为80 90 所以 由于增设了联想存储器 而使访问数据的时间 比单周期的访问时间要延长40 22 但若不引入联想存储器 其时间要延长一倍 BACK 返回本节目录 NEXT 136 5 4 3两级和多级页表现代的大多数OS 都支持非常大的逻辑地址空间 232 264 页表要占用相当大的内存空间 如 32位逻辑地址空间的分页系统中 规定页面大小为4KB 每个页表中的页表项可达1MB 每个页表项占用4个字节 页表就要占用4MB的内存空间 而且还是连续的 是不可能满足的 如何解决 BACK 返回本节目录 NEXT 137 1 对页表所需的内存空间 采用离散分配方式 来解决难以找到一块连续的大内存空间的问题 2 只将当前需要的部分页表项调入内存 其余的页表项仍留在磁盘上 需要时再将它们调入内存 BACK 返回本节目录 NEXT 138 一 两级页表Two LevelPageTable针对难以找到大的连续空间的问题 用将页表进行分页的方法 将它们分别放在不同的物理块中 要为离散分配的页表再建立一张页表 称为外层页表 在每个页表项中记录了页表页面的物理块号 BACK 返回本节目录 NEXT 139 如 对32位逻辑地址空间 页面大小为4KB时 采用一级页表结构 有20位的页号 页表项有1兆个 采用两级页表结构 对页表进行分页 每页中包含1024个页表项 有1024个页表分页 即 外层页表中的外层页内地址p2为10位 外层页号p1也为10位 此时的逻辑地址结构如下 BACK 返回本节目录 NEXT 140 外层页号 外层页内地址 页内地址 0 11 12 11 21 22 31 BACK 返回本节目录 NEXT 141 外部页表 内存空间 第0页页表 第1页页表 第n页页表 0 0 0 0 0 1 1 1 1 1 n 1023 1023 1023 1468 115 114 6 4 两级页表结构 BACK 返回本节目录 NEXT 142 从上知 页表的每个表项中存放的是进程的某页在内存中的块号 在外层页表的每个页表项中 存放的是某页表分页的首址 可用外层页表和页表两级页表 实现从进程的逻辑地址到物理地址的变换 BACK 返回本节目录 NEXT 143 在地址机构中设置一个外层页表寄存器 存放外层页表的始址 用逻辑地址中的外层页号 作为外层页表的索引 找到指定页表分页的首址 再用p2作为指定页表分页的索引 找到指定的页表项 其中含有该页的块号 用该块号和页内地址d即可构成访问内存的物理地址 如图示 BACK 返回本节目录 NEXT 144 逻辑地址 外部页号 外部页内地址 页内地址 物理地址 外部页表 页表 具有两级页表的地址变换机构 BACK 返回本节目录 NEXT 145 上述对页表施行离散分配的方法 解决了对大页表无需大片存储空间的问题 但并未解决用较少的内存空间去存放大页表的问题 即只用离散分配空间的方法并未减少页表所占用的内存空间 BACK 返回本节目录 NEXT 146 用较少的内存存放大页表 唯一的方法是把当前所需要的页表项调入内存 再根据需要调入其它页表项 若采用两级页表结构 对正在运行的进程 须将其外层页表调入内存 而对页表只须调入一页或几页 在外层页表项中 增设一个状态位s 其值为0 表示该页表分页尚未调入内存 其值为1 说明已在内存 进程运行时 地址变换机构根据逻辑地址中的p1 去查找外层页表 若所找到的页表项中的状态位为0 则产生一中断信号 请求OS将该页表分页调入内存 BACK 返回本节目录 NEXT 147 二 多级页表结构32位机器 采用两级页表结构是合适的 64位机器 若页面大小仍采用4KB 则还剩下52位 假定还按物理块的大小 1024个页表项 来划分页表 则将有余下的42位用于外层页号 此时 每个页表分页将达1MB 10位 外层页表仍有4G 32位 个页表项 要占用16GB的连续内存空间 即不管怎样划分 其结果都是不能接受的 BACK 返回本节目录 NEXT 148 所以 必须采用多级页表 将16GB的外层页表再进行分页 将各个分页离散地分配到不相邻接的物理块中 再利用第2级的外层页表来映射它们之间的关系 一般采用四级以上页表结构 BACK 返回本节目录 NEXT 149 5 4 4反置页表 倒排页表 分页系统中为每个进程配置一张页表 进程逻辑地址空间中的每一页 在页表中都对应有一个页表项 现代OS中 一般允许一个进程的逻辑地址空间非常大 所以 有很多页表项 从而占用很多内存空间 为减少页表占用的内存空间引入了反置页表 BACK 返回本节目录 NEXT 150 一般页表的表项是按页号进行排序 页表项中的内容是物理块号 而反置页表是为每一个物理块设置一个页表项并将它们按物理块的号数排序 其中的内容则是页号及其隶属进程的标识符 BACK 返回本节目录 NEXT 151 利用反置页表进行地址变换时 是用进程标识符和页号 检索反置页表 若检索完整个页表都未找到与之匹配的页表项 表明此页尚未调入内存 对于具有请求调页功能的存储器系统 此时产生请求调页中断 若无此功能 则表示地址出错 若检索到与之相匹配的表项 则该表项的序号i便是该页所在的物理块号 所以 可将该块号与页内地址一起 构成物理地址送内存地址寄存器 BACK 返回本节目录 NEXT 152 5 5 1分段存储管理方式的引入5 5 2分段系统的基本原理一 分段二 段表三 地址变换机构四 分页和分段的主要区别5 5 3共享与保护5 5 4段页式存储管理方式一 基本原理二 地址变换过程 5 5分段存储管理 返回本章目录 153 推动存储管理方式从固定分区到动态分区 发展到分页存储管理的主要动力 是提高内存利用率 分段存储管理方式的引入 是为了满足用户在编程和使用上的要求 分段管理方式已成为所有存储管理方式的基础 5 5 1分段存储管理的引入 BACK 返回本节目录 NEXT 154 主要的意义 1 方便编程一般 一个作业是由若干个段组成 用户希望能把自己的作业按照逻辑关系划分为若干个段 每个段都有自己的名字和长度 要访问的逻辑地址是由段名 段号 和段内偏移量 段内地址 决定 是二维空间 每个段都从0开始编址 BACK 返回本节目录 NEXT 155 所以 用户程序在执行中可用段名和段内地址进行访问 如 Load1 A Store1 B 前一条指令表示将分段A中D单元内的值读入寄存器1中 后一条指令表示将寄存器1的内容 存入B分段的C单元中 BACK 返回本节目录 NEXT 156 2 分段共享在实现程序和数据的共享时 都是以信息的逻辑单位为基础的 如 共享某个例程序和函数 单独成一个段 分页系统中的每一页只是存放信息的物理单位 本身并无完整的意义 不便于实现信息共享 但段却是信息的逻辑单位 为了实现段的共享 存储管理要与用户程序分段的组织方式相适应 BACK 返回本节目录 NEXT 157 3 分段保护多道程序环境下 为防止其它程序对某程序在内存中的数据的破坏 必须采取保护措施 对内存中信息的保护 同样是对信息的逻辑单位进行保护 所以 采用分段的组织和管理方式 对于实现保护功能 是有效和方便的 BACK 返回本节目录 NEXT 158 4 动态链接源程序编译后形成若干目标程序 经过链接以形成可执行程序 都能执行 这种在装入时进行的链接称为静态链接 动态链接是指作业要运行之前先将主程序所对应的目标程序装入内存并启动运行 当运行过程中又需要调用某段时 才将该段 目标程序 调入内存并进行链接 可见 动态链接也是以段作为管理