第4章+存储器管理(1-2).ppt

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