《操作系统原理》PPT课件.ppt

1 第二章存储管理 2 1存储管理基础2 2基本存储管理方法2 3可变分区存储管理方法2 4内存扩充技术2 5纯分页的存储管理2 6请求分页系统2 7段式存储管理2 8段页式存储管理2 9Linux存储管理 2 存储器可分为 内存储器和外存储器 内存储器 可以被CPU直接访问 外存储器 不可以被CPU直接访问 外存与CPU之间只能够在输入输出控制系统的管理下 进行信息交换 3 2 1存储管理基础 2 1 1虚拟地址与物理地址 4 内存储器是由一个个存储单元组成 一个存储单元可存放若干个二进制的位 bit 8个二进制位被称为一个字节 Byte 内存中的存储单元按一定顺序进行编号 每个单元所对应的编号 称为该单元的单元地址 物理地址 绝对地址 实地址 内存中存储单元的地址 物理地址可直接寻址 逻辑地址 相对地址 虚地址 用户的程序经过汇编或编译后形成目标代码 目标代码通常采用相对地址的形式 其首地址为0 其余指令中的地址都相对于首地址来编址 不能用逻辑地址在内存中读取信息 5 6 地址重定位 地址重定位 地址映射 将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址 当程序装入内存时 操作系统要为该程序分配一个合适的内存空间 由于程序的逻辑地址与分配到内存物理地址不一致 而CPU执行指令时 是按物理地址进行的 所以要进行地址转换 7 2 1 2地址定位方式 1 固定定位方式 由程序员在编写程序时或由编译连接程序对源程序进行编译连接时 直接指定程序在执行时访问的实际存储器地址的方式称为固定定位方式 此种定位方式一般只适合于单板机或单用户系统 在多道程序环境下 应保证各个作业的地址互不重叠 这就比较困难了 8 9 2 静态重定位方式 源程序经编译和连接后生成目标代码中的地址是以0为起始地址的相对地址 当需要执行时 由装入程序运行重定位程序模块 根据作业在本次分配到的内存起始地址 将可执行目标代码装到指定内存地址中 并修改所有有关地址部分的值 修改的方式是对每一个逻辑地址的值加上内存区首地址 或称基地址 值 10 11 静态重定位的特点 1 静态重定位是在程序运行之前完成地址重定位工作的 2 静态重定位由软件实现 无须硬件提供支持 3 实行静态重定位时 地址重定位工作是在程序装入时被一次集中完成的 4 绝对地址空间里的目标程序与原相对地址空间里的目标程序面目已不相同 因为前者进行了地址调整 5 实施静态重定位后 若用户程序在内存中做了移动 那么程序指令中的地址就不再反映所在的存储位置了 除非重新进行地址重定位 12 3 动态重定位方式 采用动态重定位方式 将程序在装入内存时 不必修改程序的逻辑地址值 程序执行期间在访问内存之前 再实时地将逻辑地址变换成物理地址 动态重定位要靠硬件地址变换机构实现 当程序开始执行时 系统将程序在内存的起始地址送入地址变换机构中的基地址寄存器BR中 在执行指令时 若涉及到逻辑地址 则先将该地址送入虚拟地址寄存器VR 再将BR和VR中的值相加后送入地址寄存器MR 并按MR中的值访问内存 MR BR VR 13 14 2 2基本存储管理方法 2 2 1单一连续分区存储管理 基本思想 内存分为两个区域 系统区 用户区 应用程序装入到用户区 可使用用户区全部空间 最简单 适用于单用户 单任务的OS 单用户系统在一段时间内 只有一个进程在内存 15 特点 1 系统总是把整个用户区分配给一个用户使用 2 实际上 内存用户区又被分为 使用区 和 空闲区 两部分 在操作系统中 把分配给用户 但又未使用的区域称为 内部碎片 3 由于任何时刻内存的用户区中只有一个作业运行 因此这种系统只使用于单用户的情况 4 进入内存的作业 独享系统中的所有资源 包括内存中的整个用户区 16 特点 5 由于整个用户区都分配给了一个用户使用 因此作业进入用户区后 没有移动的必要 采用这种存储分配策略时 将对用户程序实行静态重定位 6 实行静态重定位 并不能阻止用户有意无意地通过不恰当地指令闯入操作系统所占用的存储区域 如何阻止对操作系统的侵扰 就是所谓的 存储保护 问题 用于存储保护的专用寄存器 界限寄存器 17 存储保护过程 在用户态下 对内存的每一次访问 都要在硬件的控制下 与界限寄存器中的内容进行比较 一旦发现该访问的地址小于界限寄存器中的地址 就会产生 地址越界 中断 阻止这次访问的进行 优点 易于管理 便于用户的了解和使用 缺点 由于每次只能有一个作业进入内存 故它不适用于多道程序设计 整个系统的工作效率不高 资源利用率底下 只要作业比用户区小 那么在用户区里就会形成碎片 造成内存储器资源的浪费 若用户作业的相对地址空间比用户区大 那么该作业就无法运行 18 2 2 2固定分区存储管理 把内存区固定地划分为若干个大小相等 和不等 的连续分区 每个分区装一个且只能装一个作业 分区的划分原则一般由系统操作员或操作系统决定 分区一旦划分结束 在整个执行过程中每个分区的长度和内存的总分区个数将保持不变 分区大小相等 只适合于多个相同程序的并发执行 处理多个类型相同的对象 分区大小不等 多个小分区 适量的中等分区 少量的大分区 根据程序的大小 分配当前空闲的 适当大小的分区 19 固定分区 大小相同 固定分区 多种大小 20 内存分配 为了便于内存分配 通常将分区按大小进行排队 并为之建立一张分区说明表 其中各表项包括每个分区的起始地址 大小及状态 是否已分配 当有一用户程序要装入时 由内存分配程序检索该表 从中找出一个能满足要求的 尚未分配的分区 将之分配给该应用程序 然后将该表项中的状态置为 已分配 若未找到大小足够的分区 则拒绝为该用户程序分配内存 21 22 地址重定位与存储保护 固定分区存储管理中 每个分区只允许装入一个作业 作业在运行期间没有必要移动自己的位置 因此 应该对程序实行静态重定位 在固定分区存储管理中 不仅要防止用户程序对操作系统形成的侵扰 也要防止用户程序与用户程序之间形成侵扰 因此必须在CPU中设置一对专用的寄存器 用于存储保护 将两个专用寄存器分别起名为 下界寄存器 和 上界寄存器 23 存储保护过程 当进程调度程序调度某个作业进程运行时 就把该作业所在分区的低边界地址装入到低界限寄存器 高边界地址装入到高界限寄存器 作业运行时 对内存的每一次访问 都要在硬件的控制下 与两个界限寄存器中的内容进行比较 一旦发现该访问的地址小于界限寄存器中的地址 就会产生 地址越界 中断 阻止这次访问的进行 24 固定分区存储管理的特点 1 它是最简单的 具有 多道 色彩的存储管理方案 2 当把一个分区分配给某个作业时 该作业的程序将一次性的全部被装入到分配给它的连续分区里 25 优点 易于实现 开销小 缺点 内碎片造成浪费 小作业不能有效地利用分区空间 分区总数在系统生成时确定 固定 限制了并发执行的程序数目 如果到达作业的尺寸比任何一个分区的长度都大 那么它就无法得到运行 固定分区方式的评价 26 2 3可变分区存储管理 基本思想 内存不是预先划分好的 而是当作业装入时 根据作业的需求和内存空间的使用情况来决定是否分配 若有足够的空间 则按需要分割一部分分区给该进程否则令其等待主存空间优点 没有内碎片 缺点 有外碎片 27 外部碎片问题 作业A 16KB 空闲区 236KB 空闲区 220KB 作业B 100KB 空闲区 120KB 作业C 70KB 空闲区 50KB 空闲区 100KB 作业D 75KB 空闲区 25KB 内碎片 占用分区之内未被利用的空间外碎片 占用分区之间难以利用的空闲分区 通常是小空闲分区 28 2 3 1空闲存储区表 管理空闲内存区的数据结构可采用链接法和连续线性表格法 下面举一个连续线性表格管理空闲内存的方法 如采用链接法 就需要在表项中增加一个指向下一个空闲区的指针 每一个空闲分区用一个map结构管理 structmap unsignedm size 空闲分区的长度char m addr 空闲分区的起始地址 structmapcoremap N 各个空闲分区按起始地址由低到高顺次登记在空闲存储区表中 m size为0的表项是空白表项 它们集中在表的后部 29 在系统初始阶段 拥有一块很大的内存空白区 这时空闲存储区表coremap中只需有一项登记该空闲区 其余的coremap表项为空白项 即m size皆为零 30 以后随着很多作业的不断申请内存和释放内存 整个存储空间将出现许多大小不等的区域 存储区表和实际的内存空间就可能变成如图所示的情况 31 2 3 2首次适应算法 1 分配算法 采用首次适应法为作业分配大小为size的内存空间时 总是从表的起始端的低地址部分开始查找 当第一次找到大于或等于申请大小的空闲区时 就按所需大小分配给作业 如果分配后原空闲区还有剩余空间 就修改原存储区表项的m size和m addr 使它记录余下的 零头 如果作业所需空间正好等于该空闲区大小 那么该空闲区表项的m size就成为0 接下来要删除表中这个 空洞 即将随后的各非零表项依次上移一个位置 32 char malloc mp size structmap mp unsignedsize registerchar a registerstructmap bp for bp mp bp m size bp if bp m size size a bp m addr bp m addr size if bp m size size 0 do bp bp 1 m addr bp m addr while bp 1 m size bp m size return a return 0 33 2 回收算法 当某一作业释放以前所分配到的内存时 就要将该内存区归还给系统 使其成为空闲区而可被其他作业使用 释放区与原空闲区相邻情况可归纳为如图所示的4种情况 34 仅与前空闲区相连 合并前空闲区和释放区构成一块大的新空闲区 并修改空闲区表项 该空闲区的m addr不变 仍为原前空闲区的首地址 修改表项的长度域m size为原m size与释放区长度之和 与前空闲区和后空闲区都相连 将三块空闲区合并成一块空闲区 修改空闲区表中前空闲区表项 其起始地址m addr仍为原前空闲区起始地址 其大小m size等于三个空闲区长度之和 这块大的空闲区由前空闲区表项登记 接下来还要在空闲区表中删除后项 方法是将后项以下的非空白表项顺次上移一个位置 35 仅与后空闲区相连 与后空闲区合并 使后空闲区表项的m addr为释放区的起始地址 m size为释放区与后空闲区的长度之和 与前 后空闲区皆不相连 在前 后空闲区表项中间插入一个新的表项 其m addr为释放区的起始地址 m size为释放区的长度 为此 先要将后项及以下表项都下移一个位置 36 若采用首次适应法 则其分配算法简单且合并相邻空闲区也很容易 该算法的实质是尽可能利用存储区低地址部分的空闲区 而尽量在高地址部分保存较大的空闲区 以便一旦有分配大的空闲区的要求时 容易得到满足 其缺点是由于查找总是从表首开始 前面的空闲区往往被分割得很小 能满足分配要求的可能性较小 查找次数就较多 系统中作业越多 这个问题就越严重 37 2 3 3循环首次适应算法 把空闲表设计成顺序结构或链接结构的循环队列 各空闲区仍按地址从低到高的次序登记在空闲区的管理队列中 同时需要设置一个起始查找指针 指向循环队列中的一个空闲区表项 循环首次适应法分配时总是从起始查找指针所指的表项开始查找 第一次找到满足要求的空闲区时 就分配所需大小的空闲区 修改表项 并调整起始查找指针 使其指向队列中被分配的后面的那块空闲区 下次分配时就从新指向的那块空闲区开始查找 38 2 3 3循环首次适应算法 循环首次适应法的实质是起始查找指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空闲区 它们已合并成为大的空闲区可能性较大 比起首次适应法来 在没有增加多少代价的情况下却明显地提高了分配查找的速度 释放算法基本同首次适应法一样 首次适应法和循环首次适应法不仅可用于内存的分配和释放 也可用于进程图像交换的辅存空间的分配和释放 其管理空闲区的数据结构也相同 39 2 3 4最佳适应算法 所谓最佳适应算法就是在所有大于或等于要求分配长度的空闲分区中挑选一个最小的分区 在分割后 所余下的剩余存储区最小或等于零 因此 该算法的空闲区利用率高 较大的空闲区被保存下来 空闲存储区管理表的组织方法可以采用顺序结构 也可采用链接结构 如采用顺序结构 空闲分区按地址由小到大的顺序登记在表中 分配时需要搜索所有的空闲分区 以在其中挑出一个满足分配大小的最小的分区 此种管理结构的释放算法可用顺序结构的首次适应法 40 2 3 4最佳适应算法 当采用链接结构时 空闲区也可按由小到大的非递减次序排列 分配时总是从最小的第一项开始 这样第一次找到的满足条件的空闲区必定是最合适的 平均而言 只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区 但寻找较大空闲区比较费时 采用按存储区大小排序的链接表会降低释放算法的效率 由于空闲区是按大小而不是按地址序号排序的 因此释放回收空闲区时要在整个链表上寻找地址相邻的前 后空闲区 合并后又要插入到合适的位置 因此释放算法比前两种算法耗时得多 41 2 3 5最差适应算法 最差适应法所分割的空闲存储区是所有空闲分区中的最大的一块 在实施最差适应法时 空闲区管理表项一般以m size由大到小的次序组织成一个链接表 因此查找分割的总是最大的第一个空闲存储区 实现最差适应法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表 采用按存储区大小顺序排列的链接表的形式虽然释放一个空闲块时速度较慢 但分配效率是一切算法中最高的一种 42 可变分区存储管理的特点 1 作业一次性的全部装入到一个连续的存储分区中 2 分区是按照作业对存储的需求划分的 因此在可变分区管理中 不会出现内部碎片这样的存储浪费 3 为了确保作业能够在内存中移动 要由硬件支持 实行指令地址的动态重定位 43 可变分区存储管理的缺点 1 仍然没有解决小内存运行大作业的问题 2 虽然避免了内部碎片造成的存储浪费 但有可能出现极小的分区暂时分配不出去的情形 引起外部碎片 3 为了形成大的分区 可变分区存储管理通过移动程序来达到分区合并的目的 然而程序的移动是很花费时间的 增加了系统在这方面的开销 44 2 3 6多重分区 可变分区存储管理算法是按作业对存储的需求分配存储区的 因而消除了固定分区内部的剩余碎片 但随着存储区的分配和释放过程的进行 在各个被分配出去的分区之间会存在很多的空闲区 这就是 外部碎片 有时 当一个作业要装入运行 但分配不到一个够用的空闲分区 尽管这时内存中所有外部碎片的总和远大于作业所申请的空间 如采用 紧凑 技术重新安排内存中各个作业的位置 以使零碎的空闲区集中起来 这是一个极其耗时的过程 一般很少采用这种策略 45 否 否 是 是 46 2 3 6多重分区 有些系统采用多重分区技术 在作业的运行过程中可以申请附加的分区 以装入一个或多个子程序 新申请的空闲分区也无需与作业的现有分区相邻接 采用多重分区技术可以提高外部碎片的利用率 也便于多个作业共享分区的代码和数据 这只要在共享的作业中包含某个共享的分区即可 多重分区系统应当采用动态重定位技术 但存储管理的复杂性也增加了 为了实现存储保护 在多重分区系统中要设置多对界地址寄存器 以使现运行作业对每一个分区的访问都不会越界 47 2 4内存扩充技术 在基本的存储管理系统中 当一个作业的程序地址空间大于内存可用空间时 该作业就不能装入运行 当并发运行作业的程序地址空间总和大于内存可用空间时 多道程序设计的实现就会碰到很大的困难 内存扩充技术就是借助大容量的辅存在逻辑上实现内存的扩充 以解决内存容量不足的问题 48 2 4 1覆盖 overlay 引入 其目标是在较小的可用内存中运行较大的程序 原理 覆盖技术就是将一个大程序按程序的逻辑结构划分成若干个程序 或数据 段 并将不会同时执行 从而就不必同时装入内存的程序段分在一组内 该组称为覆盖段 这个覆盖段可分配到同一个称为覆盖区的存储区域 将程序的必要部分 常用功能 的代码和数据常驻内存 可选部分 不常用功能 在其他程序模块中实现 平时存放在外存中 覆盖文件 在需要用到时才装入到内存 不存在调用关系的模块不必同时装入到内存 从而可以相互覆盖 即不同时用的模块可共用一个分区 49 注 另一种覆盖方法 100K A 20K 占一个分区 20K B 50K D 20K 和E 40K 共用一个分区 50K F 30K 和C 30K 共用一个分区 30K 50 缺点 对用户不透明 增加了用户负担 编程时必须划分程序模块和确定程序模块之间的覆盖关系 增加编程复杂度 从外存装入覆盖文件 以时间延长来换取空间节省 覆盖不需要任何来自操作系统的特殊支持 由用户程序自己控制所以 覆盖通常限于用在微机和其他内存容量有限的或缺乏对更先进技术的硬件支持的系统中 51 2 4 2交换 swapping 引入 让单一连续分区存储管理能具有 多道 的效果 中心思想 将作业信息都存放在辅存上 根据单一连续分区存储管理的分配策略 每次只让其中一个进入内存投入运行 当运行中提出输入输出请求或分配的时间片用完时 就把这个程序从内存储器 换出 到辅存 把辅存里的另一个作业 换入 内存运行 这样从宏观上看 系统中同时就有几个作业处在运行之中 为了减少在主存和辅存间传输的数据量 可以只将原作业的一部分保存到辅存中去 只要释放的主存空间刚好够装入下一个运行作业就行 在以后的适当时间 作业移出的部分可装入到原来的存储区中继续运行下去 这种技术称之为交换技术 也叫 滚进滚出 52 53 优点 增加并发运行的程序数目 并且给用户提供适当的响应时间 编写程序时不影响程序结构缺点 对换入和换出的控制增加处理机开销 程序整个地址空间都进行传送 没有考虑执行过程中地址访问的统计特性 交换技术的优缺点 54 交换与覆盖的比较 与覆盖技术相比 交换技术不要求用户给出程序段之间的逻辑覆盖结构 交换发生在进程或作业之间 而覆盖发生在同一进程或作业内 覆盖只能覆盖那些与覆盖段无关的程序段 55 2 4 3虚拟存储器 在现代的计算机系统中 一个作业即使不全部装入主存 也同样能正确运行 因为 在一个程序中一般都有相当数量的出错处理子程序 在正常的运行过程中很少执行到这些程序 程序中一般都含有类似then和else的彼此互斥的部分 在程序的一次执行中往往只选择其中的一条路径执行 程序中的初始化部分一般只执行一次 初始化工作完成后 这些代码就没有存放在主存中的必要 56 2 4 3虚拟存储器 从运行的时间角度来分析 在一段时间内 作业一般不会执行到所有程序段的指令和存取绝大部分数据 它往往相对集中地访问某些区域中的指令和数据 这就是程序运行的 局部性原理 在主存中可只装入最近经常要访问的某些区域的指令和数据 剩余部分就暂时不必装入 等到以后要访问到它们时再调入内存 如果主存较紧张 必要时可将已不大访问的信息调出内存 再执行调入操作 这样 程序运行时所需要的实际内存就可以远小于程序的虚拟地址空间 57 由于作业的指令和数据可以存放在外存中 用户的程序就不受实际内存大小的限制 好像计算机系统向用户系统提供了容量极大的 主存 而这个大容量的 主存 是靠存储管理的软件和硬件通过大容量的辅存作为后援存储器扩充而获得的 是程序设计员感觉到的 而实际上并不存在的存储器 故称虚拟存储器 采用虚拟存储器技术究竟可运行多大的程序呢 当然也不能无限大 它受到以下两个条件的限制 58 指令地址字长的限制 地址字长决定了程序所能访问的虚拟地址空间的大小 如对于32位字长的地址字可构成4GB的虚拟地址空间 存放程序指令和数据的外存储器的大小 这种外存叫做交换设备 存放程序指令和数据的外存区域称为交换区 采用虚拟存储管理策略 在作业运行时就要由地址映像机构将程序的逻辑地址转换成内存的物理地址 此外 还要决定将虚拟地址空间中的哪一部分装入主存 装入主存的位置以及当主存中的空闲区不够时将哪一部分空间的内容调至交换区中 这些都是虚拟存储管理中要解决的新的技术问题 59 2 5纯分页的存储管理 可变分区存储管理 连续分配存储空间 分页式存储管理 打破了 连续 的禁锢 把对存储的管理大大推进了一步 分页式存储管理是将固定分区方法与动态重定位技术结合在一起的一种存储管理方案 它需要硬件的支持 60 2 5 1分页存储管理的基本思想 作业的虚拟地址空间划分成若干长度相等的页 page 也称虚页 每一个作业的虚页都从0开始编号 主存也划分成若干与虚页长度相等的页架 frame 也称页框或实页 主存的页架也从0开始编号 程序装入时 每一个虚页装到主存中的一个页架中 这些页架可以是不连续的 需要CPU的硬件支持 61 例 62 把用户程序按逻辑页划分成大小相等的部分 称为页 从0开始编制页号 页内地址是相对于0编址 用户程序划分 例 页的大小为4K相对地址5188 对应数对 1 1092 相对地址9200 对应数对 2 1008 63 2 5 2地址变换 在分页系统中 页的大小都是2的整数次幂 这样分页地址中的地址结构如下 31 12 11 0 虚拟地址字的页内偏移部分占据低n个二进制位 使2n刚好等于页的大小 这样安排便于硬件直接截取高位部分的页号和低位部分的页内偏移值 64 例 某系统的地址结构长为16位 相对地址3000的二进制位表示如下 块尺寸1KB 对应数对 2 952 块尺寸256字节 对应数对 11 184 65 程序的虚拟地址空间是连续的 但程序的虚页可以分配到主存中不连续的空闲页架中 故分页系统需要在主存中开辟一个页表区域来建立每一个作业的虚页号到内存的页架号之间的映射关系 系统还需要建立一个总页表来记录各个作业页表的起始地址和长度 并将当前运行进程的页表起始地址和长度存放在页表控制寄存器中 66 每一个作业的页表空间可以是连续的 也可以是不连续的 但连续的页表空间管理方便 存取速度也快 连续的页表要分配的空间本身又相当于一个小分区 故可采用前面讨论的分区分配和释放算法 连续的页表空间同时也带来了页表分区之间的存储区碎片问题 但由于一个作业的页表空间比作业本身的程序和数据空间小得多 故这个问题相对来说并不严重 67 基本的地址变换机构 页表保存在内存中 硬件设置一个专用寄存器 页表寄存器 每当进程调度时 把调度到进程的页表起始地址和页表长度 即页表表项的数目 放入寄存器中 68 地址转换过程 1 由硬件自动将虚拟地址字分成虚页号和页内偏移两部分 2 由页表控制寄存器中页表起始地址和虚拟地址字中的虚页号查找页表 对应虚页号的页表表项地址为 页表起始地址 虚页号 页表表项长度 3 将页表中取出的页架号和虚拟地址字中的页内偏移值装入地址寄存器 根据地址寄存器中的地址值访问主存 页表控制寄存器中的 长度 起到存储保护的作用 每个相对地址中的页号都不能大于该长度 否则出错 69 70 例 若在分页式存储管理中 建立了某个作业的页 块对应关系为 第0页放在第0块 第1页放在第3块 第2页放在第1块 如下所示 已知块的尺寸为1KB 块 求相对地址1023 1024 3000 所对应的绝对地址 解 1023 10231024 30723000 1976 71 缺点 1 页表放在内存 增加了系统在存储上的开销 2 降低了CPU的访问速度 因为每次对某一地址的访问 首先要访问内存中的页表 形成绝对地址后 才能进行所需要的真正访问 72 2 5 3具有快表的地址变换机构 考虑到大多数程序在一次调度运行时 倾向于在少数页面中进行频繁的访问 这被称为程序的 局部性 原理 因此实际系统中的做法是采用内存页表与快速寄存器组相结合的解决方案 并且利用程序局部性原理 只用极少数几个快速寄存器来构成快速寄存器组 这时把快速寄存器组单独起名为 快表 主存中的页表有时也称为慢表 73 快表由CPU中的高速cache或联想寄存器构成 联想寄存器是一种按内容进行并行查找的一组快速寄存器 当在其输入端有一个输入值页号p时 在联想寄存器中存放页号为p的那一项就立即选中 并输出其变换值页架号b 由于访问联想寄存器比访问主存快得多 故极大地提高了地址变换速度 74 地址的映射 快表中存放的是页表内容的一部分 在进行地址变换时 变换机构根据虚拟地址字中的页号同时查找快表和慢表 一旦在快表中查到虚页号 就用输出的页架号和虚拟地址字中的偏移地址构造主存物理地址 否则 就用慢表中查到的页架号构造主存物理地址 同时还用慢表的该表项更新快表 这就可能需要按某一算法淘汰快表中某一表项 以便下次再访问该页的过程能在快表中进行 75 76 由于成本关系 快表不可能做的很大 通常只存放16 512个页表项 这对于中 小型作业来说 已有可能把全部页表项放在快表中 但对于大型作业 则只能将其一部分页表项放入其中 据统计 快表中如含有8个表项时 平均命中率为85 含有16个表项时 平均命中率为97 因此在配备联想寄存器的页式管理系统中 多一级地址变换不会明显减慢程序的执行速度 77 2 5 4空闲内存页的管理 在页式管理系统中 需要一张表记录主存中每个页的使用情况和当前空闲页的总数 由于主存页总数很多 且页的大小相等 故可用位图描述各页的状态 在位图中用一个二进制位对应于主存中的一个页 该位为0表示对应页空闲 为1表示对应页已分配 位图中每一个字节可表示8页的状态 如设页面大小为4KB 对于32MB的主存空间 只需要1KB大小的位表 78 位图 页框号 字节号 8 位号字节号 页框号 8 位号 页框号 8 79 在分配空闲页时 可一次取出位图中的一个字 如该字内容非全1 即表示其中必对应有空闲页 接下来就可确定空闲页的位置 为了提高在位图上检索空闲页的速度 可在表头增设一个起始查找位置指针 位图中在起始查找指针之前的所有字 或字节 都不含有空闲位 另外 设置一个循环查找指针的算法也不错 释放算法很简单 只要在位图中的对应位上置0即可 但如设置起始查找指针 则可能要修改指针值 也可使用顺序或链接结构的栈来管理空闲页 栈中每一个单元指示一个空闲页 采用这种方法所需的存储空间比位图大许多 但分配空闲页时速度快很多 80 分页式存储管理的特点 1 内存事先被划分成相等尺寸的页框 它是进行存储分配的单位 2 用户作业的相对地址空间按照页框的尺寸划分成页 3 由于相对地址空间中的页可以进入内存中的任何一个空闲页框 并且分页式存储管理实行的是动态重定位 因此它打破了一个作业必须占据连续存储空间的限制 作业在不连续的存储区里 也能够得到正确的运行 81 1 平均每个作业要浪费半页大小的存储页 2 作业虽然可以不占据连续的存储区 但是每次仍然要求一次全部进入内存 因此 如果作业很大 其存储需求大于内存 那么仍然存在小内存不能运行大作业的问题 缺点 82 补充 两级和多级页表 现代的大多数计算机系统 都支持非常大的逻辑地址空间 232 264 在这样的环境下 页表就变得非常大 要占用相当大的内存空间 例如 对于一个具有32位逻辑地址空间的分页系统 规定页面大小为4KB即212B 则在每个进程页表中的页表项可达1兆个之多 又因为每个页表项占用一个字节 故每个进程仅仅其页表就要占用1MB的内存空间 而且还要求是连续的 83 补充 两级和多级页表 可以采用这样两个方法来解决这一问题 采用离散分配方式来解决难以找到一块连续的大内存空间的问题 只将当前需要的部分页表项调入内存 其余的页表项仍驻留在磁盘上 需要时再调入 84 1 两级页表 Two LevelPageTable 对于要求连续的内存空间来存放页表的问题 可利用将页表进行分页 并离散的将各个页面分别存放在不同的物理块中的办法来加以解决 同样也要为离散分配的页表再建立一张页表 称为外层页表 OuterPageTable 在每个页表项中记录了页表页面的物理块号 85 逻辑地址结构可描述如下 86 两级页表结构 87 88 上述对页表施行离散分配的方法 虽然解决了对大页表无需大片存储空间的问题 但并未解决用较少的内存空间去存放大页表的问题 换言之 只用离散分配空间的办法并未减少页表所占用的内存空间 解决方法是把当前需要的一批页表项调入内存 以后再根据需要陆续调入 在采用两级页表结构的情况下 对于正在运行的进程 必须将其外层页表调入内存 而对页表则只需调入一页或几页 89 2 多级页表对于32位的机器 采用两级页表结构是合适的 但对于64位的机器 如果页面大小仍采用4KB即212B 那么还剩下52位 假定仍按物理块的大小 212位 来划分页表 则将余下的42位用于外层页号 此时在外层页表中可能有4096G个页表项 要占用16384GB的连续内存空间 必须采用多级页表 将外层页表再进行分页 也是将各分页离散地装入到不相邻接的物理块中 再利用第2级的外层页表来映射它们之间的关系 对于64位的计算机 如果要求它能支持2 1844744TB 规模的物理存储空间 则即使是采用三级页表结构也是难以办到的 而在当前的实际应用中也无此必要 90 2 6请求分页系统 虚拟存储器的引入 1 常规存储器管理方式的特征 一次性 作业在运行前一次性的全部装入内存 2 驻留性 作业装入内存后 便一直驻留在内存中 直到作业运行结束 91 2 6 1请求分页的基本原理 其基本思想是对于每一个运行作业 只装入当前运行需要的一部分页面集合 该集合又称 工作集 当作业运行时需要访问其他不在主存中的虚页时 硬件产生 缺页中断 如主存资源紧张 可在原先装入主存的页面中选择一个或多个页 将其换出到辅存中 再把所需的页调入主存 请求式分页系统将主存和辅存这两级存储器融合成逻辑上统一的整体 故在这种系统中能运行比可用主存更大的作业或在相同容量的主存中并发运行更多的作业 92 与分页式存储管理的比较 相同点 1 内存分成页框 2 作业虚地址空间分虚页 3 任一页可装入任一空闲页框 不同点 1 作业全部进入外存 运行时 并不把整个作业全部装入 而是只装入目前要用的若干页 2 运行过程中 虚地址转换为数对 页号 页内位移 根据页号查页表时 如果该页在内存 那么有真实的页框号与之对应 运行就能够进行下去 93 与分页式存储管理的比较 续 如果该页不在内存 那么无真实块号与之对应 表明 缺页 运行无法继续下去 此时 就要根据该页的地址把它从外存调入 以保证程序运行 请求分页式 当程序运行中需要某一页时 再把它从辅存调入内存 94 请求分页机构 在请求分页系统中控制这种能在主存和辅存间自动交换页面 对用户透明的机构称为虚拟存储系统的请求分页机构 该机构的主要功能如下 执行地址变换操作 将程序虚拟地址转化为物理地址 这部分工作由硬件实施 缺页时自动触发页面中断机构 缺页中断与普通的外设中断不同 一般中断只能在一条完整的指令执行结束后才能得到响应 而缺页中断可以发生在一条指令的执行中间 如果一条指令要访问多个页面 如对于间接访问指令和数据传送指令 还能引起多个缺页中断 缺页中断处理子程序 其中包括页面的调出和调入 这部分工作在软件控制下完成 95 在请求分页系统中 由于作业的虚页可能驻留在主存中 也可能驻留在辅存中 因此在页表中要扩充表项的内容 使之包含辅存地址 以便在发生缺页时请求分页机构可以将辅存中的虚页调入主存 这样 每一个页表项结构为 虚页号 内存页架号 辅存地址和状态 其中状态字段含有该页当前是在主存还是在辅存的标志 此外 在该字段中还可包括访问位和修改位等 地址变换 96 页表机制 1 状态位P 用于指示该页是否已调入内存 2 访问字段A 用于记录本页再一段时间内被访问的次数 或记录本页最近已有多长时间未被访问 供选择换出页面时参考 3 修改位M 表示该页在调入内存后是否被修改过 4 外存地址 用于指出该页在外存的地址 97 缺页中断机构 在地址映射过程中 在页表中发现所要访问的页不在内存 则产生缺页中断 操作系统接到此中断信号后 就调出缺页中断处理程序 根据页表中给出的外存地址 将该页调入内存 使作业继续运行下去 如果内存中有空闲页框 则分配一页 将新调入页装入内存 并修改页表中相应页表项目的驻留位及相应的内存页框号 若此时内存中没有空闲页框 则要淘汰某页 若该页在内存期间被修改过 则要将其写回外存 98 CPU 页表始址长度 页表控制寄存器 内存 越界中断 页表 快表 物理地址 缺页异常 地址变换机构 99 开始 页号 页表长度 检索快表 命中 访问页表 页在内存 修改快表 修改访问位和修改位 形成物理地址 地址变换结束 地址越界 保留CPU现场 内存满 选择一页换出 OS命令CPU从外存读缺页 启动I O硬件 缺页中断处理 是 是 是 是 否 否 否 否 该页是否修改过 从外存找到缺页 将该页写回外存 将一页从外存换入内存 修改页表 100 2 6 2页面淘汰 页面淘汰问题 页面置换 要从辅存上把需要的页面调入内存 但内存中已没有空闲页框可供分配使用 那么就必须从内存中选择一页 然后把它调出内存 以便为即将调入的页面让出块空间 页面置换是由缺页中断引起的 但是缺页中断不一定都引起页面置换 101 页淘汰 在内存中选中了一个淘汰的页面 如果该页面在内存时未被修改过 那么就可以直接用调入的页面将其覆盖掉 如果该页面在内存时被修改过 那么就必须把它写回到磁盘 以便更新该页在辅存上的副本 一个页面的内容在内存时是否被修改过 这样的信息可以通过页表表目反映出来 102 抖动 或 颠簸 现象 抖动 进程块频繁的换入换出当操作系统取进一页时 它必须扔出一页 如果一块正好在将要被用到之前扔出 操作系统又不得不几乎立即把它取回来 太多的这类操作会导致 系统抖动 处理器的大多数时间都用于交换页 而不是执行指令 改进抖动的许多复杂但有效的算法 从本质上看是 操作系统试图根据最近的历史来猜测在不远的将来最可能用到的页 103 页面淘汰算法 功能 需要调入页面时 选择内存中哪个物理页面被置换 目标 把未来不再使用的或短期内较少使用的页面调出 通常只能在局部性原理指导下依据过去的统计数据进行预测 104 页面走向 一个程序执行过程中页面的变化序列称为 页面走向 105 缺页中断率 假定一个作业运行的页面走向中涉及到的页面总数为A 其中有F次缺页 必须通过缺页中断把它们调入内存 我们定义 f F A称f为 缺页中断率 106 1 最佳 Optimal 置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法 其所选择的被淘汰页面 将是以后永不使用的 或许是在最长 未来 时间内不再被访问的页面 采用最佳置换算法 通常可保证获得最低的缺页率 107 假定系统为某进程分配了三个物理块 并考虑有以下的页面号引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 进程运行时 先将7 0 1三个页面装入内存 以后 当进程要访问页面2时 将会产生缺页中断 此时OS根据最佳置换算法 将选择页面7予以淘汰 108 2 先进先出 FIFO 页面置换算法 选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 并且有Belady现象 109 举例 页面走向 3个内存块 缺页计数 缺页中断率 f 9 12 75 FIFO算法着眼点 认为随时间推移 在内存中呆得最长得页面 被访问得可能性最小 110 如果在内存中分配4个页面 则缺页情况如下 12次访问中有缺页10次 111 2 最近最少使用 LRU 置换算法 最近最久未使用算法的着眼点是在要进行页面淘汰时 检查这些淘汰对象的被访问时间 总是把最长时间未被访问过的页面淘汰出去 选择内存中最久未使用的页面被置换 这是局部性原理的合理近似 性能接近最佳算法 但由于需要记录页面使用时间的先后关系 硬件开销太大 该算法赋予每个页面一个访问字段 用来记录一个页面自上次被访问以来所经历的时间t 当必须淘汰一个页面时 选择现有页面中其t值最大的 即最近最久未使用的页面予以淘汰 112 举例 页面走向 3个内存块 缺页计数 缺页中断率 f 10 12 83 113 可以设置一个从中间可以出队的非严格意义上的队列 队列中的每一个单元对应于一个内存页 每次访问一个页面时将对应单元从队列中抽出 重新排到队尾去 淘汰的页从队列头取 这样 经常要访问的页总是排在靠近队列的尾部 而排在队首位置上的页就是最长时间没有被访问过的页 114 假定现有一进程所访问的页面的页面号序列为 4 7 0 7 1 0 1 2 1 2 6 115 实现该算法的主要困难是如果每执行一条访问主存的指令时都要执行队列的操作 并且该操作是用软件实现的话 其时间开销是不可忍受的 减少算法时间复杂性的方法之一是用硬件实现队列结构和操作 方法之二是不必在每一条访问内存指令都执行队列操作 可以每过一个时间间隔 如时钟中断 执行一次 116 另一种全部用硬件实现的LRU算法是对于n个页面设置一个n n的矩阵 矩阵初始时全为0 当k页被访问时 硬件置k行的所有位为1 再置k列的所有位为0 任何时刻 二进制值为最小的一行所对应的页是最近最久不用的页 图2 15为含有4个页面 访问序列是0123210323的情况下 每访问一页后矩阵的状态 117 访问序列是0123210323 118 4 最近未使用淘汰算法 NUR NotUsedRecently 是一种低开销的近似于LRU的淘汰算法 其主要思想是淘汰最近一段时间内未曾访问过的某一页面 该算法的一个实施不仅能考虑最近未曾访问过的页 还能优先挑选页面数据未曾修改过的页 这样可减少将淘汰页写回辅存的开销 如采用这种算法 要为每一项增设两个硬件位 访问位和修改位 当该页未访问过或没修改过时对应位为0 反之为1 访问位和修改位不一定要设在页表中 初始时所有页的访问位和修改位都清0 当访问某页时 该页的访问位置1 当某页的数据被修改后 将该页的访问位和修改位都置1 119 系统将主存中各个使用页组织成一个循环队列 并设置一个循环检测指针 当需要淘汰一页时 从指针指向的页开始 顺次考察各页的使用情况 如其访问位为1 则将该位清0 如访问位为0 但修改位为1 则将修改位置0 还应当更新辅存对应页 不断重复这个过程 直到找到访问位和修改位都为0的页 将其作为淘汰页 按照这个算法 最新读过的页在第一轮的循环检测中不会被选中 最近写过的页在第一 二轮循环检测中不会被选中 这样不仅实现了NUR算法 而且给予修改过的页两次机会 120 NUR算法的另一种实现是不在检测时清0 而是系统每过一个适当的时间 将所有页的访问位置0 这样在两次清0之前 内存中各页的使用状态可能有4种 即序号访问位修改位 序号访问位修改位100201310411 121 1类 A 0 M 0 表示该页最近既未被访问 又未被修改 是最佳淘汰页 2类 A 0 M 1 表示该页最近未被访问 但已被修改 并不是很好的淘汰页 3类 A 1 M 0 最近已被访问 但未被修改 该页有可能再被访问 4类 A 1 M 1 最近已被访问且被修改 该页可能再被访问 122 对于采用同一种淘汰算法 影响系统缺页中断率的主要因素是分配给一个作业的页面数目 虽然在主存中运行的作业数越多 每个作业分配到的页架越多 系统的运行性能就越好但内存并不总是充足有余的廉价资源 实践证明 工作集中页面少于某一个数时 作业的缺页中断次数会急剧增加 即会发生页面抖动现象 而高于这个数 作业的缺页中断次数不会明显减少 这个页面数范围称为页面的工作集 123 工作集不仅与作业的特征 如程序大小 结构 访问数据的规律有关 也与作业运行的时间段有关 系统可根据一个进程的缺页中断率估计出合适的工作集大小 并根据运行情况给予调整 如在某一段时间内 系统中很多作业所能分配到的页面数小于工作集时 应当挂起某些作业 将其所占用的主存空间分配给优先级高的作业 以避免抖动现象的发生 124 按淘汰页面的选择范围分 有两种淘汰策略 一种是淘汰的页从整个主存也即所有的作业所占用的页面中选择 这称为全局淘汰算法 另一种是从本作业所占用的页面中选择 称为局部淘汰法 在讨论页面淘汰算法时 还未曾考虑淘汰页的选择范围 淘汰页的选择范围对选择不同的淘汰算法和硬件的配置影响很大 全局算法一般工作得比局部算法好 因为这种算法可以在很多进程之间动态地分配页面 但支持全局算法的硬件开销较大 算法运行的时间也较大 有些算法 如采用n n位矩阵的NUR算法 就不大可能在采用全局淘汰策略时被采用 125 补充 内存分配策略和分配算法 物理块的分配策略 在请求分页系统中 可采取两种内存分配策略 即固定和可变分配策略 在进行置换时 也可采取两种策略 即全局置换和局部置换 于是可组合出以下三种适用的策略 1 固定分配局部置换 FixedAllocation LocalReplacement 2 可变分配全局置换 VariableAllocation GlobalReplacement 3 可变分配局部置换 VariableAllocation LocalReplacemen 126 1 固定分配局部置换 FixedAllocation LocalReplacement 这是指基于进程的类型 交互型或批处理型等 或根据程序员 程序管理员的建议 为每个进程分配一定数目的物理页架 在整个运行期间都不再改变 采用该策略时 如果进程在运行中发现缺页 则只能从该进程在内存的n个页面中选出一页换出 然后再调入一页 以保证分配给该进程的内存空间不变 127 2 可变分配全局置换 VariableAllocation GlobalReplacement 在采用这种策略时 先为系统中的每个进程分配一定数目的物理页架 而OS自身也保持一个空闲页架队列 当某进程发现缺页时 由系统从空闲页架队列中 取出一个页架分配给该进程 并将欲调入的 缺 页装入其中 这样 凡产生缺页 中断 的进程 都将获得新的页架 仅当空闲页架队列中的页架用完时 OS才能从内存中选择一页调出 该页可能是系统中任一进程的页 这样自然又会使那个进程的页架减少 进而使其缺页率增加 128 3 可变分配局部置换 VariableAllocation LocalReplacemen 它同样是基于进程的类型或根据程序员的要求 为每个进程分配一定数目的页架 但当某进程发现缺页时 只允许从该进程在内存的页面中选出一页换出 这样就不会影响其它进程的运行 如果进程在运行中频繁发生缺页中断 则系统须再为该进程分配若干附加的页架 直至该进程的缺页率减少到适当程度为止 反之 若一个进程在运行过程中的缺页中断率特别低 则此时可适当减少分配给该进程的页架数 但不应引起其缺页率的明显增加 129 补充 调页策略 1 何时调入页面 预调页策略如果进程的许多页是存放在外存的一个连续区域中 则一次调入若干个相邻的页 会比一次调入一页更高效些 可采用一种以预测为基础的预调页策略 将那些预计在不久以后便会被访问的页面 预先调入内存 2 请求调页策略当进程在运行中需要访问某部分程序和数据时 若发现其所在的页面不在内存 便立即提出请求 由OS将其所需页面调入内存 130 2 从何处调入页面 在请求分页系统中的外存分为两部分 用于存放文件的文件区和用于存放对换页面的对换区 通常 由于对换区是采用连续分配方式 而文件区是采用离散分配方式 故对换区的磁盘I O速度比文件区的高 这样 每当发生缺页请求时 系统应从何处将缺页调入内存 可分成如下三种情况 1 系统拥有足够的对换区空间 这时可以全部从对换区调入所需页面 以提高调页速度 为此 在进程运行前 便须将与该进程有关的文件 从文件区拷贝到对换区 131 2 系统缺少足够的对换区空间 这时凡是不会被修改的文件 都直接从文件区调入 而当换出这些页面时 由于它们未被修改而不必再将它们换出 以后再调入时 仍从文件区直接调入 但对于那些可能被修改的部分 在将它们换出时 便须调到对换区 以后需要时 再从对换区调入 3 UNIX方式 由于与进程有关的文件都放在文件区 故凡是未运行过的页面 都应从文件区调入 而对于曾经运行过但又被换出的页面 由于是被放在对换区 因此在下次调入时 应从对换区调入 由于UNIX系统允许页面共享 因此 某进程所请求的页面有可能已被其它进程调入内存 此时也就无须再从对换区调入 132 补充 页式管理方式中有效访问时间的计算方法 有效访问时间 EffectiveAccessTime EAT 是指给定逻辑地址找到内存中对应物理地址单元中数据所花的总时间 基本分页系统中 如果没有快表 访问内存一次需要的时间为t 有效访问时间分为 查页表找到对应的页表表项所花的时间t 通过对应的物理地址访问一次内存所花时间t 所以 EAT t t 2t 若有快表 设快表TLB的查找需要时间为 访问一次内存需要的时间为t 命中率为 则有效访问时间分为 查页表项的平均时间为 t 1 通过对应的物理地址访问一次内存所花时间为t 所以EAT t 1 t 2t t 133 典型例题 页面走向为 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 分配页面数为3时 试计算FIFO LRU和OPT页面淘汰算法的缺页中断数及缺页中断率各是多少 解 134 FIFO 1T 12T 123T 234T 234 341T 415T 156T 562T 621T 621 213T 137T 376T 376 762T 621T 621 213T 136T 缺页中断率 16 20 80 LRU 1T 12T 123T 234T 342 421T 215T 156T 562T 621T 612 123T 237T 376T 763 632T 321T 312 123 236T 缺页中断率 15 20 75 135 0PT 1T 12T 123T 124T 124 124 125T 126T 126 126 126 326T 376T 376 376 326T 321T 321 321 621T 缺页中断率 11 20 55 136 某程序页面走向为4 3 2 1 4 3 5 4 3 2 1 5 运行时 分别实行FIFO和LRU页面淘汰算法 试就3个内存块和4个内存块的情形 求出各自的缺页中断率 并分析对于FIFO是否会发生异常现象 置换算法举例 137 FIFO算法 3个页面 页面走向 3个内存块 缺页计数 缺页次数 9 f 9 12 138 FIFO算法 4个页面 页面走向 4个内存块 缺页计数 缺页次数 10 f 10 12 139 LRU算法 3个页面 页面走向 3个内存块 缺页计数 缺页次数 10 f 10 12 140 LRU算法 4个页面 页面走向 4个内存块 缺页计数 缺页次数 8 f 8 12 141 例题 请求分页系统中 假设某进程的页表内容如下表所示 页面大小为4KB 一次内存的访问时间是100ns 一次快表的访问时间是10ns 处理一次缺页的平均时间为108ns 已含更新TLB和页表的时间 进程的驻留集大小固定为2 采用最近最少使用置换算法 LRU 和局部淘汰策略 假设 1 TLB初始的时候为空 2 地址转换时先访问TLB 若TLB未命中 再访问页表 忽略访问页表之后的TLB更新时间 3 有效为为0表示页面不在内存 产生缺页中断 缺页中断处理后 返回到产生缺页中断的指令处重新执行 142 设有虚拟地址访问序列2362H 1565H 25A5H 请问 1 依次访问上述三个虚拟地址 各需要多少时间 给出计算过程 2 基于上述访问序列 虚地址1565H的物理地址是多少 请说明理由 143 例 作业 的页面映象表如下图所示 一页 一块 1024字节 问 指出页表中中断位 访问位 修改位 辅存地址的含义 当执行到 单元的指令 时