操作系统原理第四章存储器管理ppt课件.pptVIP

第四章存储器管理 4 1存储器的层次结构4 2程序的装入和链接4 3连续分配方式4 4基本分页存储管理方式4 5基本分段存储管理方式4 6虚拟存储器的基本概念4 7请求分页存储管理方式4 8页面置换算法4 9请求分段存储管理方式 1 4 1存储器的层次结构 寄存器 高速缓存 主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴 掉电后它们存储的信息不再存在 而辅存的使用与管理放在设备和文件管理中介绍 在主存中 2 KB MB GB TB 3 4 5 6 存储器管理 指内存的管理 外存管理在文件部分讲述 单道程序系统 内存被划分成两部分 一部分供OS使用 一部分供当前正在执行的程序使用 多道程序系统 存储器的用户部分必须进一步地细分 以适应多个进程的要求 细分的任务由操作系统动态实现 这就是存储器管理 存储器管理的目的 一是方便用户使用 二是提高存储器的利用率 基本概念补充 7 1 存储器管理功能 主存的分配和回收 系统应能记住每个存储区的状态 实施存储器的分配 回收系统或用户释放的存储区 地址转换或重定位 实现逻辑地址到物理地址的变换 分为静态重定位和动态重定位主存共享与保护 使多道程序能动态地共享主存 最好能共享主存中的信息 保证进入主存的各道作业都在自己的存储空间内运行 互不干扰 由硬件和软件配合完成 主存扩充 借助于虚拟存储技术 为用户提供比主存空间大的地址空间 8 内存的每个存储单元都有一个编号 这种编号称为内存地址 或称为物理地址 绝对地址 内存地址的集合称为内存空间 或物理地址空间 例如 我们常说内存为 512MB要求用户用内存地址编程是非常困难的 尤其是在多道程序设计的环境中 不知道 2 地址映射 地址重定位 9 用户编程所用的地址称为逻辑地址 或程序地址 或虚地址 由逻辑地址组成的空间称为逻辑地址空间 或程序地址空间 我们把用户程序装入内存时 或在程序执行时 对有关指令或数据地址的修改称为从程序地址到内存地址的地址映射 或称为地址重定位 10 1100 11 地址映射的方式 静态地址映射 1 程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换 2 地址转换工作是在程序执行前由装入程序集中一次完成 假定程序装入内存的首地址为BR 程序地址为VR 内存地址为MR 则地址映射按下式进行 MR BR VR 12 把程序装入起始地址为1000的内存区 Movr1 500 1234 0 100 500 600 Movr1 1500 0 1000 1100 1500 1600 1234 作业的地址空间 存储空间 装入程序 13 静态映射优缺点 优点 不需要硬件的支持 简单易实现 成本低 缺点 程序必须占用连续的内存空间 一旦程序装入后不能移动 主存利用率低 难以做到程序和数据的共享 14 动态地址映射 重定位 动态地址重定位 在程序执行的过程中 每次将要访问的指令或数据逻辑地址转换为内存地址 动态映射方法 装入程序把程序和数据原样装入到已分配的存储区中 然后把这个存储区的起始地址送入重定位寄存器中 在程序执行时 再将相对地址转换成绝对地址 硬件支持 在动态地址重定位机构中 有一个基地址寄存器BR和一个程序地址寄存器VR 一个内存地址寄存器MR 转换过程 MR BR VR 15 把程序装入起始地址为1000的内存区 1234 0 100 500 599 作业的地址空间 0 1000 1100 1500 1599 1234 存储空间 1000 重定位寄存器 逻辑地址VR 物理地址MR MOVr1 500 MOVr1 500 16 动态地址映射的过程 程序装入内存后 它所占用的内存区的首地址由系统送入基地址寄存器BR中 在程序执行的过程中 若要访问内存 将访问的逻辑地址送入VR中 地址转换机构把VR和BR中的内容相加 并将结果送入MR中 作为实际访问的地址 17 动态重定位优缺点 优点 1 程序占用的内存空间是动态可变的 当程序从某个存储区移到另一个区域时 只需要修改相应的寄存器BR的内容即可 2 一个程序不一定要求占用一个连续的内存空间 可以部分地装入程序运行 4 便于多个进程共享同一个程序的代码 动态地址重定位的代价 1 需要硬件的支持 2 实现存储管理的软件算法较为复杂 18 4 2程序的装入和链接 可能产生 可执行程序文件 编译 链接 装入 二进制内存映像 程序处理步骤 编译 编译程序 负责检查语法错 涉及名空间 输入 源程序 输出 多个目标模块 链接 链接程序 负责将多个模块相关联 涉及逻辑地址空间 输入 多个目标模块 库函数 输出 装入模块 装入 装入程序 负责内存分配和地址映射 涉及内存空间 输入 装入模块 输出 可执行的二进制内存映像 过程或函数可能分别对应一个模块 19 4 1 2程序的链接 1 静态链接方式 StaticLinking 图4 3程序链接示意图 链接前 每个模块都有各自的相对起始地址0 链接后 每个模块使用同一个相对起始地址0 名空间 逻辑地址空间 在程序运行之前 先将各目标模块及它们所需的库函数 链接成一个完整的装入模块 又称为可执行文件 以后不再拆开 解决 对相对地址进行修改 变换外部调用符号 不要求 20 2 装入时动态链接 Load timeDynamicLinking 基本思想 源程序被编译生成的目标模块 是在装入内存时 边装入边连接 装入程序根据外部模块调用而逐个装入和连接 装入时动态链接方式有以下优点 便于修改和更新 各个模块的修改极易编译和连接 便于实现对目标模块的共享 将内存中的一个模块可以连接到多个程序中 已在内存的就不必重复装入 要运行的程序都必须在装入时 全部连接调入内存 21 3 运行时动态链接 Run timeDynamicLinking 动态链接方式 将对某些模块的链接推迟到执行时才实施 亦即 在执行过程中 当发现一个被调用模块尚未装入内存时 立即由OS去找到该模块并将之装入内存 把它链接到调用者模块上 特点如下 特点 凡在执行过程中未被用到的目标模块 都不会被调入内存和被链接到装入模块上 这样不仅可加快程序的装入过程 而且可节省大量的内存空间 三种链接方式的差别相当于 静态链接 上车 相当于进入内存 前集合起来装入时链接 上车后集合起来 有利于共享已在内存中的部分 运行时链接 开车后需要时集合起来 按需调入 22 4 2 1程序的装入 1 绝对装入方式 AbsoluteLoadingMode 程序中所使用的绝对地址 既可在编译或汇编时给出 也可由程序员直接赋予 编译程序生成的目标模块其逻辑地址与要装入内存的物理地址相同 缺点 单道程序可用 多道程序环境不能用 采用绝对地址装入 目前很少使用 23 2 可重定位装入方式 RelocationLoadingMode 图4 2作业装入内存时的情况 又称静态重定位 地址变换在装入时一次完成 其后不能移动 逻辑地址 相对地址 物理地址 绝对地址 LOAD1 12500 24 3 动态运行时装入方式 DenamleRun timeLoading 动态运行时装方式 装入内存后的所有地址都仍是相对地址 逻辑地址到物理地址的变换要推迟到程序真正执行时才进行 地址变换发生在程序执行过程中 即动态重定位 为使地址转换不影响程序执行速度 必须使用硬件支持 25 链接和装入的关系 一 静态链接会形成磁盘上的可执行文件 而装入时动态链接和运行时动态链接不会产生磁盘上的可执行文件 静态链接产生的可执行文件装入时内存是连续分配的 而地址映射既可采用可重定位装入方式 静态重定位 也可以采用动态运行时装入方式 动态重定位 26 链接和装入间的关系 二 装入时动态链接方式可以分别给每个装入模块分配一块内存区域 因而装入时各模块不一定连续存放 装入时的地址映射既可采用可重定位装入方式 静态重定位 链接后运行前一次性修改逻辑地址为物理地址 也可以采用动态运行时装入方式 动态重定位 运行时动态计算出逻辑地址到物理地址的映射 27 链接和装入间的关系 三 运行时动态链接方式一般情况下后装入的模块和原先已装入的模块是不连续存放的 运行时动态链接方式的地址变换不可能运行前一次性映射地址 即不可能采用静态重定位方法 而只能使用动态重定位的方法 28 链接和装入间的关系 四 链接 考虑格模块如何关联起来装入 考虑装在内存何处 以及如何进行地址变换 29 4 2连续分配方式 4 2 1单一连续分配 特征 最简单的一种存储管理方式 但只能用于单用户 单任务的操作系统中 常把内存分为系统区和用户区两部分 系统区仅提供给OS使用 通常是放在内存的低址部分 用户区是指除系统区以外的全部内存空间 提供给用户使用 30 4 2 2固定分区分配 1 划分分区的方法 分区大小相等 即使所有的内存分区大小相等 缺点 缺乏灵活性 大作业无法运行 小作业浪费空间 分区大小不等 即划分为小 中 大不等的固定分区 优点 灵活性好 分配方法 将用户空间划分为若干个固定大小的区域 在每个分区中装入一道作业 有几个分区 就有几道并发的作业 有空闲分区时 可调入一适当大小的作业 最简单的一种多道程序存储管理方法 31 2 内存分配 为了便于内存分配 将分区按照大小排队 并建立一个分区表 如图所示 当为作业分配空间时 分配程序按照此表检索以合适分区分配 否则 拒绝分配 缺点 空间浪费 图4 4固定分区使用表 32 4 2 3动态分区分配 1 分区分配中的数据结构 空闲分区表 2 空闲分区链 图4 5空闲链结构 分配思想 根据进程的实际需要 动态的为进程分配 切分 内存空间 及需要多大 分配多大 提高内存的利用率 33 未分配区表用空闲区链表表示 0 0 10k 10k 270k 0 0 730k 730k 100k 100k 100k 270k 空闲区链 head 空闲区大小 34 2 分区分配算法 首次适应算法FF 空闲分区按地址递增成链表 每次分配从链首依次查找一空间首次满足作业的空闲分区 再从该分区中切出与作业等量的空间分之 余者挂到链表中 若找不到满足作业空间要求的空闲分区 分配失败 优缺点 低地址部分将产生多个较小的空闲分区 碎片 增加分配开销 问题 如何从空闲分区表或链表中 选择一分区分配个作业 常用的算法如下 35 循环首次适应算法 该算法是由首次适应算法演变而成的 区别仅是从上次已分配分区的下一个分区依次查找首次满足作业的空闲分区 并从中划分出作业需要的分区 实现方法 起始循环指针 循环空闲分区 链 表 36 2 分区分配算法 最佳适应算法 空闲链表依照空间大小排列 每次从链首 小的在前 为作业找一个大小最合适的分区分配 缺点 最佳适应必将产生最小的空闲碎片 最坏适应算法 worstfit 总是挑选一个最大的空闲区分割给作业使用 其优点是可使剩下的空闲区不至于太小 产生碎片的几率最小 对中 小作业有利 同时最坏适应分配算法查找效率很高 37 3 分区分配操作 分配内存操作分配操作如左图所示 38 回收内存操作回收的分区有4种情况 与前 后 前后空分区相邻 如下图所示 图4 7内存回收时的情况 39 当回收分区与前后空闲分区均不相邻时 为回收分区建立一个空闲分区结点 并插入链表适当位置 回收分区 40 4 2 4可重定位分区分配 1 动态重定位的引入 动态回收碎片 将小而不可用的空闲分区拼接成较大的一个空闲分区 移动作业分区 必然要重定位 图4 8紧凑的示意 41 2 动态重定位的实现 作业在内存中仍保持逻辑地址 在执行时再实施重定位 具体过程如下图 图4 9动态重定位示意图 42 3 动态重定位分区分配算法 在动态分区算法增加了回收碎片的功能 图4 10动态分区分配算法流程图 43 作业4 1 1 在系统中采用可变分区存储管理 操作系统占用低地址部分的126KB 用户区的大小是386KB 若采用空闲分区表管理空闲分区 若分配时从高地址开始 对于下述的作业申请序列 作业1申请80KB 作业2申请56KB 作业3申请120KB 作业1完成 作业3完成 作业4申请156KB 作业5申请80KB 试用首次适应法处理上述作业 并回答下面问题 1 画出作业1 2 3进入内存后 内存分布情况 2 画出作业1 3完成后 内存的分布情况 3 画出作业4 5进入内存后 内存分布的情况 44 4 5基本分页存储管理方式 问题 由于为进程连续分配内存空间 将产生大量碎片 为了利用碎片必须将其合并 又需要系统开销 能否给进程离散 不连续 地分配内存空间 解决这些问题 离散分配 当前使用最多的内存分配方式是分页管理方式和分段管理方式 分页是页面为单位进行内存分配 分段方式是以段为单位进行内存分配 基本分页 段 存储管理方式 如果分页或分段存储管理方式中不具备页面或分段对换功能 将其称之为基本分页或基本分段存储管理方式 45 4 3 1页面与页表 1 页面与物理块 页面 将一个进程的逻辑地址空间分成若干个大小相等的片 称为页面或页 并为各页顺序编号为0 1 2 n 物理块 把内存空间分成与页面相同大小的若干个存储块 称为 物理 块或页框 frame 也同样为它们加以编号 如0 块 1 块等等 内存分配原理 在为进程分配内存时 以页面为单位给进程离散分配与页面数等量的物理块 并分别装入到相应的物理块中 全部装入 页内碎片 由于进程的最后一页经常装不满一块而形成了不可利用的碎片 称之为 页内碎片 46 举例 如左图所示 按照基本分页存储管理方式为进程分配内存空间 设页面大小为1KB 47 页面大小设定 在分页系统中的页面其大小应适中 且页面大小应是2的幂 通常为512B 8KB 页面大小利弊 若页面太小 内存碎片减小 从而减少了内存碎片的总空间 提高内存利用率 但另一方面也会使每个进程占用较多的页面 从而导致进程的页表过长 占用大量内存等 若页面较大 可以减少页表的长度 节省内存 但却又会使页内碎片增大 48 逻辑地址空间中的地址为A 页面大小为L 则有 P INT A L d A MODL 例 A 2170B L 1KB时 则有P 2 d 122 49 2 逻辑地址结构 最大页面数 220 1M个页面大小 212 4KB逻辑空间 0 232 1一维的 并针对程序员 50 3 页表分页存储管理方式按照进程页面的多少 为进程离散分配相同数量的物理块 为了记录每一页所分配的物理块 必须为每个进程建立一个页表每个进程一个页表 每个页面一个表项 表项 页号 0 1 2 n 块号 离散分配形成 存取控制 读写控制 51 页表示意图 图4 11页表的作用 52 基本分页系统多进程内存分配示意图 53 4 3 2地址变换机构 基本的地址变换机构 实现逻辑地址向物理地址的转换 由于页内地址与块内地址一一对应 所以地址转换关键是将逻辑地址中的页号转换为内存中的物理块号 转换机构设施 页表寄存器 存放进程页表在内存中的起地址和页表长度 进程不执行时放在PCB中 执行时调入寄存器中 物理地址寄存器 存放转换后的物理地址 内存地址 查找表项 表项地址 页表起始地址 页号 表项长度 地址转换过程如下图 图4 12分页系统的地址变换机构 54 55 例 说明运行进程的地址变换过程 如下图所示 进程程序地址空间共有7个页 每页的大小为1024 其对应的主存块在页表中已列出 假定页表在主存始址为500 若该程序从第0页开始运行 且现程序计数器内容为 0 100 程序计数器 逻辑地址 56 57 例 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 10 5块 试将逻辑地址7145 3412转换成内存地址 58 逻辑地址7145P 7145 2048 3W 7145mod2048 1001MR 5 2048 1001 11241逻辑地址7145的内存地址是 11241 逻辑地址3412P 3412 2048 1W 3412mod2048 1364MR 9 2048 1364 19796逻辑地址3412的内存地址是 19796 59 2 具有快表的地址变换机构问题 两次访问内存 页表 数据 运行速度下降一半 解决方法 联想存储器 快表 存放当前访问的页表项 思路 将已访问的页号的页表项放入快表 方便下次访问 提高访问速度 争取一次访问内存 联想存储器 通常只要设定8 16个寄存器作为联想存储器 即可使程序执行速度大大提高 60 具有快表的地址变换过程示意图 图4 13具有快表的地址变换机构 61 4 3 3两级和多级页表 问题 现代的大多数计算机系统 都支持非常大的逻辑地址空间 232 264 在这样的环境下 页表就变得非常大 要占用相当大的内存空间 例如 对于一个具有32位逻辑地址空间的分页系统 规定页面大小为4KB即212B 则在每个进程页表中的页表项可达1兆个之多 而且还要求是连续的 解决办法 采用离散分配方式存放页表 使用对换方式调入 调出页表 62 1 两级页表 Two LevelPageTable 逻辑地址结构可描述如下 页面大小为4K 12位 每页包含1024个页表项 P2 占10位 总共有1024个分页 P1 占10位 63 图4 14两级页表结构 64 图4 15具有两级页表的地址变换机构 二级页表地址转换过程示意图 65 2 多级页表对于32位的机器 采用两级页表结构是合适的 但对于64位的机器 如果页面大小仍采用4KB即212B 那么还剩下52位 假定仍按物理块的大小 212位 来划分页表 则将余下的42位用于外层页号 此时在外层页表中可能有4096G个页表项 要占用16384