[所有分类]第4章 存储管理.ppt

1 第4章存储管理 4 0本章学习目标4 1概述4 2单道环境下的存储管理4 3分区存储管理4 4纯分页存储管理4 5纯段式存储管理4 6虚拟存储器管理4 7段页式存储管理4 8虚拟存储管理的性能分析4 9小结 2 4 0本章学习目标 操作系统中的存储管理主要是指对主存的管理 主存 即内存 是指处理机可以直接存取指令和数据的存储器 近年来 存储器容量虽然一直在不断扩大 但仍不能满足现代软件发展的需要 因此 存储器仍然是一种宝贵而又紧俏的资源 3 在多道程序设计技术出现后 对存储管理提出了更高的要求 一方面 要使主存得到充分 有效地利用 另一方面又要为用户提供方便的使用环境 这两点正是本章的主要目的 4 本章学习目标 1 掌握存储管理基本知识 2 正确理解页式存储管理 段式存储管理和段页式存储管理 3 理解虚拟存储管理实现原理 4 理解局部性原理与工作集概念 5 4 1概述 程序和数据必须装入内存 即要占用一定的内存空间才能执行和使用 暂时不执行或不用的程序和数据可放在外存中 CPU不能直接访问外存 需通过I O设备实现内 外存信息交换 内存空间一般分为两部分 一部分是系统区 存放操作系统 标准子程序 例行程序和系统数据等 另一部分是用户区 用于存放用户的程序和数据等 如图4 1所示 6 存储管理主要是对用户区进行管理 其目的是充分利用内存 为多道程序并发执行提供存储基础 方便用户使用 7 存储管理的功能 1 存储分配2 地址映射3 存储保护4 内存扩充 8 4 1 1存储分配 在多道程序设计的环境中 当有作业进入计算机系统时 存储管理应能根据当时的内存分配状况 按作业要求分配给它适当的内存 当某个作业完成不再使用内存时 应回收占用的内存空间 以便供其他用户使用 9 内存分配按分配时机的不同 可分为两种方式 1 静态存储分配 指内存分配是在作业运行之前各目标模块连接后 把整个作业一次性全部装入内存 并在作业的整个运行过程中 不允许作业再申请其他内存 或在内存中移动位置 即 内存分配是在作业运行前一次性完成的 2 动态存储分配 作业要求的基本内存空间是在目标模块装入内存时分配的 但在作业运行过程中 允许作业申请附加的内存空间 或是在内存中移动 即 分配工作可以在作业运行前及运行过程中逐步完成 10 4 1 2地址映射1 物理地址和逻辑地址 1 内存空间 主存储器以字节为编址单位 容量为n的主存储器中 每个单元有唯一的编号 分别为 0 1 2 n 1 这个唯一的编号就是主存储器的物理地址 即绝对地址 11 内存地址的集合称为内存地址空间 或物理地址空间 简称内存空间 或物理空间 是一维线性空间 例如 某个系统 有64kb内存 则其内存空间编号为 0 1 2 3 65535 12 2 逻辑空间 用汇编语言或高级语言编写程序时 常常用符号名来访问某一单元 把源程序中由符号名组成的程序空间称为符号名空间 简称名空间 源程序经过汇编或编译后 形成目标程序 每个目标程序都是以0为基址顺序进行编址的 原来用符号名访问的单元用具体的数据 单元号取代 这样生成的目标程序占据一定的地址空间 称为作业的逻辑地址空间 简称逻辑空间 在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址 或相对地址 13 一个编译好的程序存在于它自己的逻辑空间中 运行时 要把它装入内存空间 如图4 2所示 一个作业在编译前 编译后及装入内存后不同空间的情形 14 15 由图4 2可以看出 该作业经过编译后 大小为300字节 逻辑地址空间为0 299 在作业的第100号单元处有指令MovRl 200 即把200号单元内的数据6817送入寄存器Rl 假如把作业装入到内存第1000 1299号单元处 由图4 2可以看出 若只是简单地装入第1000 1299号单元 执行MovRl 200 指令时 会把内存中200号单元的内容送入Rl 显然这样会出错 只有把1200单元的内容送入Rl才是正确的 所以作业装入内存时 需对指令和指令中相应的逻辑地址部分进行修改 才能使指令按照原有的逻辑顺序正确运行 16 2 地址重定位 在多道程序系统中 每个用户不可能用内存的物理地址来编写程序 程序在装入内存之前通常为逻辑地址形式 有时甚至在装入内存后 程序仍为相对地址形式 为了保证CPU执行程序指令时能正确访问存储单元 需要 将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址 这一过程称为地址映射或地址重定位 17 地址重定位的方式有两种 1 静态重定位 在装入一个作业时 把作业中的指令地址和数据地址全部转换成绝对地址 这种转换工作是 在作业开始前完成的 在作业执行过程中无需再进行地址转换 所以称为 静态重定位 如图4 3 a 所示 18 2 动态重定位 在装入一个作业时 不进行地址转换 而是直接把作业装到分配的主存区域中 在作业执行过程中 每当执行一条指令时都由硬件的地址转换机构转换成绝对地址 这种方式的地址转换是 在作业执行时动态完成的 所以称为 动态重定位 如图4 3 b 所示 19 图4 3静态地址映射和动态地址映射示意图 动态重定位 需要依靠硬件地址映射机制完成 一般需要硬件提供寄存器等资源 20 4 1 3存储保护 在多道程序系统中 内存中的许多用户或系统程序和数据段可供不同的用户进程共享 这种资源共享将会提高内存的利用率 但是 反过来 我们又要限制各进程只在自己的存储区活动 除了被允许共享的部分之外 各进程不能对别的进程的程序和数据段产生干扰和破坏 因此须对内存中的程序和数据段采取保护措施 主要有两方面 防止地址越界 防止操作越权 21 1 防止地址越界 每个进程都具有其相对独立的进程空间 如果进程在运行时所产生的地址超出其地址空间 则发生地址越界 地址越界可能侵犯其他进程的空间 影响其他进程的正常运行 也可能侵犯操作系统空间 导致系统混乱 因此 对进程所产生的地址必须加以检查 发生越界时产生中断 由操作系统进行相应处理 22 存储保护的手段可以采用硬件的方法 也可以采用软 硬件结合的方法 通常使用较为普遍的是界限寄存器保护法 主要有两种具体实施技术 上 下界保护 基址 限长保护方法 23 1 上 下界存储保护 是一种简单的存储保护技术 系统为每个作业设置一对上 下界寄存器 分别用来存放当前运行作业在内存空间的上 下边界地址 用它们来限制用户程序的活动范围 如图4 4 a 所示 某作业在内存的起始位置是20kb 结束位置是25kb 24 在作业运行过程中 每当要访问内存某单元时 检查经过重定位后产生的内存地址是否在上 下界寄存器所规定的范围之内 若在 则访问是合法的 可以进行 否则 产生越界中断 通知系统进行越界处理 25 2 基址 限长存储保护 系统可为每个作业设一个基址寄存器和一个限长寄存器 基址寄存器存放该作业在内存的首址 限长寄存器存放该作业的长度 如图4 4 b 所示 基址寄存器的值为20kb 限长寄存器的值为5kb 26 在作业运行时 每当要访问内存某单元时 检查指令中的逻辑地址是否超过限长寄存器的值 若不超过 则访问是合法 可以进行 否则 视为非法访问 27 2 防止操作越权 对于允许多个进程共享的公共区域 每个进程都有自己的访问权限 例如 有些进程可以执行写操作 而其他进程只能执行读操作等等 因此 必须对公共区域的访问加以限制和检查 1 对属于自己区域的信息 可读可写 2 对公共区域中允许共享的信息或获得授权可使用的信息 可读而不可修改 3 对未授权使用的信息 不可读 不可写 28 4 1 4内存扩充 为了提高系统运行多道程序的能力 并且使用户在编制程序时不受内存实际容量的限制 可以在硬件支持下 将外存作为主存的扩充部分供用户程序使用 这就是内存扩充 内存扩充可以使用户程序得到比实际内存容量大得多的 内存 空间 从而极大方便了用户 采用内存扩充技术 由操作系统处理内存与外存的关系 统一管理内 外存 向用户提供一个容量相当大的虚拟存储空间 这就是虚拟存储技术 29 为了实现存储管理的上述功能 人们研究并总结出来各种存储管理方案 根据能否实现虚拟存储 我们把存储管理方案分为两类 一类是实存管理 一类是虚拟存储器的管理 实存管理的提法是与虚拟存储管理技术相对应的 其特点是作业运行时 整个作业的逻辑地址空间必须全部装入内存 当作业尺寸大于主存可用空间时 该作业就无法运行 即实存管理无法实现虚拟存储器技术 30 常用的实存管理技术有 单一连续分配存储管理固定分区存储管理可变式分区存储管理纯分页存储管理纯分段存储管理 31 常用的虚拟存储管理技术有 虚拟分页存储管理虚拟分段存储管理段页式存储管理下面分别予以介绍 32 课堂练习P122 123 二 1 8 33 4 2单道环境下的存储管理1 单一连续分配 在单道环境下 无论是单用户系统或单道批处理系统 进程或作业执行时除了系统占用部分之外 可用内存区全部为一个进程或作业所占用 因此其管理较为简单 如图4 5所示 单一连续分配的内存在概念上可划分为三个区域 系统区 用户区 剩余空闲区 34 单一连续分配主要是指 内存只供一个用户进程使用 如果这个用户进程要求的内存资源大于内存可利用空间时 则系统会表示出错信息而使得该进程无法执行 当该用户进程要求的内存资源小于内存可利用空间时 则该用户进程可得到足够的内存资源 35 单一连续分配方式主要采用静态分配方式 即 作业或进程一旦进入内存后 就要等到该作业或进程执行结束后才能释放内存 因此 单一连续分配方式不支持进程大小不受内存容量限制的虚拟存储器的实现 如图4 6所示 36 主要优点是 管理简单 只需要很少的软件和硬件支持 且便于用户了解和使用 缺点 1 由于进程或作业所要求的存储量不会正好等于内存可用存储区容量 因而总有一部分空闲存储区得不到利用 2 由于作业或进程的所有程序和数据是一次装入内存的 其中的有些信息在执行过程中可能很少使用或从未使用 白白地占用存储空间 这也是造成存储器浪费的一个重要原因 2 单一连续分配优缺点 37 3 单一连续分配管理方式限制了用户程序和系统程序的可重入性 即内存中的程序和数据是不可能被共享的 因为系统只允许每次对一个作业或进程进行内存分配 4 单道程序管理的系统中 在个人计算机系统中 为了降低成本和减少复杂度 未对内存采取适当的保护措施 改进 38 4 3分区存储管理 分区管理是在单一连续管理的基础上发展起来的一种存储管理方法 是满足多道程序运行的最简单的存储管理方案 其基本思想是 将内存划分成若干个连续区域 称为分区 分区管理的基本原理是 给每一个内存中的进程划分一块适当大小的存储区 以连续存储各进程的程序和数据 使各进程得以并发执行 按分区的时机 分区管理分为固定分区和可变分区 39 4 3 1固定分区法 固定分区法就是 系统将内存划分为若干固定的分区 当作业申请内存时 系统为其选择一个适当的分区 并装入内存运行 分区一旦划分结束 在整个执行过程中每个分区的长度和内存的总分区个数将保持不变 系统对内存的管理和控制通过数据结构 分区说明表进行 分区说明表说明 各分区号 分区大小 起始地址和是否是空闲区 分区状态 内存的分配释放 存储保护以及地址变换等都通过分区说明表进行 40 图中 操作系统占用低地址部分的20K 其余空间被划分为4个分区 其中 1 2 3号分区已分配 4号分区未分配 41 固定分区的地址重定位采取静态地址重定位方法 固定分区的存储保护采用上 下界寄存器保护方式 固定分区存储管理的最大的优点是简单 要求的硬件支持少 软件算法也简单 缺点是容易产生内部碎片 即由于分区大小是事先固定的 因而可容纳作业的大小受到限制 而且当用户作业的地址空间小于分区的存储空间时 浪费了一些存储空间 改进 可变分区法 42 4 3 2可变分区法 与固定分区法相比 可变分区法在作业执行前并不建立分区 而是在作业装入内存时建立分区 使分区的大小正好与作业要求的存储空间相等 能有效解决固定式分区的内部碎片问题 是一种较为实用的存储管理方法 因为在系统运行过程中 内存中分区的数目和大小都是可变的 所以也叫动态分区 43 44 如图4 8所示 假设某系统采用可变式分区存储管理 在系统运行的开始 存储区被分为操作系统分区 40kb 和可分给用户的空闲区 216kb 当作业1 46k 进入内存后 分给作业1 46k 随着作业2 3 4的进入 分别分配32k 38k 40k 经过一段时间的运行后 作业1 3运行完毕 释放所占内存 此时 作业5进入系统 要求分配36k内存 如何为作业5分配内存呢 45 如图4 8 c 所示 此时 有三种方法可给作业5分配内存 从作业1释放的46k中 分36k给作业5 即分配空闲区1 从作业3释放的38k中 分36k给作业5 即分配空闲区2 从空闲的60k中 分36k给作业5 即分配空闲区3 到底采用哪种分配方法呢 这时 应考虑空闲分区的组织形式和采用的内存分配算法 46 1 空闲分区的组织形式 在可变式分区存储管理中 常把空闲区组成空闲分区表或空闲分区链表的形式 空闲分区表的组织类似于固定分区的分区说明表 包含空闲分区的起始位置和大小 因分区数目不定 故空闲分区表长度不定 采用空闲分区表要占用一定数量的存储单元存放此表 增加了系统的开销 47 空闲分区链表的组织是这样的 在每个空闲分区的起始部分开辟出一个单元 存放一个链表指针和该分区的大小 链表指针指向下一个空闲分区 系统中用一个固定单元作为空闲分区链表的链表头指针 指向第一块空闲分区首地址 最后一块空闲分区的链表指针存放链尾标志 因空闲分区链表组织时 空闲区的信息放在空闲区内 因此不会额外增加系统的开销 所以使用比较广泛的是空闲分区的链表组织形式 48 2 内存的分配和回收 在可变分区存储管理中 当作业要求一个Xk大小的存储空间时 系统从链表头指针开始依次检索空闲区 找到第一个大于等于Xk的空闲区 若系统中所有空闲区都小于Xk 则无法分配 若有空闲区等于Xk大小 则修改链表指针 取消该空闲区 并向用户返回该空闲区首地址 若该空闲区大于Xk 则将空闲区一分为二 一个为Xk 分给用户 另一个为余下部分 仍留在空闲区链表中 修改相应链表指针所指向的地址和空闲区大小 49 当某一个用户作业完成时 要释放所占内存 系统应进行回收 应该检查回收区与内存中前后空闲区是否相邻 若相邻 则应进行合并 形成一个较大的空闲区 并对相应的链表指针进行修改 若不相邻 应将空闲区插入到空闲区链表的适当位置 50 3 常用的分配算法 可变式分区中 对空闲区链表采用不同的组织形式 就对应不同的分配和回收算法 最先适应算法 最佳适应算法 最差适应算法 51 1 最先适应算法 思想是 把空闲分区按其所在存储空间中地址递增的顺序连接在一起 当用户申请一内存存储空间时 从空闲区链表的头指针开始查找 选择第一个满足要求的空闲分区 算法如图4 9所示 52 图4 9最先适应算法此算法最简单 可以快速作出分配决定 53 2 最佳适应算法 这种算法把空闲分区链表按分区大小由小到大进行组织 当有作业申请内存时 总是首先找到满足要求的最接近作业大小的空闲分区 此算法最节约空间 因为它尽量不分割大的空闲区 其缺点是 可能会形成很多很小的空闲区域 称作外碎片 54 3 最差适应算法 这种算法要求把空闲区按分区大小递减的顺序组织成空闲区链表 当用户申请一个存储区时 总是检查空闲区链表的第一个空闲区是够满足要求 若不满足 分配失败 若满足 则将空闲区分配给用户 然后修改和调整空闲区链表 55 该算法的优点是 可以避免形成碎片 缺点是 分割大的空闲区后 再遇到较大的申请时 无法满足的可能性较大 总之 上述三种算法各有特长 针对不同的请求队列 它们的效率和功能是不一样的 56 4 地址重定位和存储保护 可变分区法的 地址重定位 采用静态重定位 也可采用动态重定位 存储保护 采用基址 限长存储保护方式 57 5 碎片处理 所谓碎片是指 内存中出现的一些零散的小空闲区域 由于碎片都很小 因此无法再利用 出现 各个小空闲区总长度能够满足用户要求 而每个小空闲区都不能满足用户要求的现象 如果内存中碎片很多 会造成严重的存储资源浪费 解决碎片 可以移动所有的占用区域 使所有的空闲区合并成一片连续区域 这一过程称为紧凑 拼接 这一技术就是紧凑技术 拼接技术 紧凑带来很大的系统开销 58 6 可变分区存储管理的主要优缺点 优点 有效地解决了固定式分区的内部碎片问题 较有效地利用主存空间 提高了多个作业或进程对内存的共享 缺点 容易产生外部碎片问题 为解决外部碎片问题 可采用紧凑技术 但花费大量处理机时间 59 课堂练习P123 124 9 12 60 4 4纯分页存储管理 目前已讨论了单道存储管理和分区式存储管理方法 分区式管理方式尽管实现方式较为简单 但存在着严重的碎片问题 内存的利用率不高 再者 分区式管理时 由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放 进程的大小仍受分区大小或内存可用空间的限制 而且 分区式管理也不利于程序段和数据的共享 61 页式管理正是为了减少碎片 以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分 而把那些不经常执行的程序段和数据存放在外存待执行时调入 以提高内存利用率而提出来的 62 4 4 1基本原理1 内存划分 页式存储管理 将内存空间划分成等长的若干区域 每个区域称为一个物理块 有时也称内存块或块 内存的所有物理块从0开始编号 称作物理块号或内存块号 每个物理块内单元亦从0开始依次编址 称为块内地址 63 系统将用户程序的逻辑空间按照同样大小也划分成若干页面 称为逻辑页面 有时也简称为页 程序的各个逻辑页面从0开始依次编号 称作逻辑页号或相对页号 每个逻辑页面内单元也从0开始编址 称为页内地址 2 逻辑地址空间划分 64 对用户程序地址空间的分页是系统自动进行的 即对用户是透明的 由于页面尺寸选为2的整数次幂 故系统可将地址的高位部分定义成页号 低位部分定义成页内地址 例如 图4 10中 机器地址长为20位 若页面长度为210 则地址的10 19位表示页号 最多拥有210 1024个逻辑页 0 9位表示页内地址 即页长为210 1K 65 页面大小直接影响地址转换和页式存储管理的性能 如果页面太大 以至于和作业地址空间相差无几 这种方法就变成了可变分区方法的翻版 反之 如果页面太小 则增加了系统的开销 3 页面大小 页面尺寸一般取2的整数次幂 如29 210 211等 66 存储分配时 以块为单位 并按用户程序的页数多少进行分配 逻辑上相邻的页面在内存中不一定相邻 即 分配给用户程序的内存块不一定连续 4 内存分配 67 如果把一个作业的所有页面一次全部装入到内存块中 就把这种分页称之为纯分页存储管理 如果作业的所有页面并不是一次全部装入 而是根据作业运行时的实际要求装入 则把这种分页称为虚拟页式存储管理 本节先讨论纯分页存储管理 68 4 4 2实现方法1 建立页表 系统为每个用户程序建立一张页表 用于记录用户程序逻辑页面与内存物理块之间的对应关系 用户程序的地址空间有多少页 该页表里就登记多少行 且按逻辑页的顺序排列 页表存放在内存系统区内 69 2 建立空闲页面表系统中设立一张内存空闲页面表 记录内存物理页面空闲情况 用于内存分配和回收 70 3 内存分配算法 图4 12页面分配算法流程图 71 系统提供一对硬件寄存器 页表始址寄存器和页表长度寄存器 1 页表始址寄存器 用于保存正在运行进程的页表在内存的首地址 当进程被调度程序选中投人运行时 系统将其页表首址从进程控制块中取出送入该寄存器 2 页表长度寄存器 用于保存正在运行进程的页表的长度 当进程被选中运行时 系统将它从进程控制块中取出送入该寄存器 4 硬件支持 72 5 地址映射 73 具体步骤说明如下 1 地址映射机构把CPU给出的逻辑地址分为两部分 如执行指令LOAD1 2500时 逻辑地址2500 2 1024 452 因此页号p 2 页内地址d 452 这是假设页面大小为210情况下得到的结果 2 将逻辑页号p与页表长度比较 如果p大于页表长度 则为越界 发生越界中断 74 3 根据页表始址得到页表在内存的首地址 并根据逻辑页号p在页表中找到对应的物理页号 如果页号p 2 则相应物理页号为8 4 把物理页号与逻辑地址中的页内地址d拼在一起 形成访问内存的物理地址 在本例中 物理地址 1024 8 452 8644 75 4 4 3快表 从地址映射过程中可以看出 共需两次访问内存 第一次访问页表 得到数据的物理地址 第二次才是存取数据 增加了访问时间 76 为了提高存取速度 在分页地址变化机构中 加入一组高速缓冲存储器 用来存放当前作业的最常用的页号和与之相对应的物理块号 一般称这样的寄存器组为快表或联想存储器 快表因硬件成本较高 个数不宜太多 一般以8 16个单元组成 和页表具有并行查找能力 77 具有快表的地址映射过程 当处理机给出逻辑地址 p w 时 分页机构 一方面取出页号p 并根据p从页表中查找相应的内存块号b 另一方面自动把页号p送入快表 并和快表各单元进行比较 78 如与某单元页号相符 则 输出对应块号b 并与页内地址w形成物理地址进行访问 停止查找页表的工作 由于快表采用的是高速缓存 其访问速度比访问页表要快得多 如果在快表中查找不到 仍继续在页表中查找 并把查找到的页号p和块号b放到快表的空闲单元中 以备下次使用 如无空闲单元 则通常把最先装入的那个页号淘汰 以腾出位置 79 80 4 4 4存储保护 页式管理可以为内存提供两种方式的保护 地址越界保护 可由地址变换机构中的控制寄存器的值 页表长度 和所要访问的逻辑地址相比较完成 存取控制保护 通过页表 控制对内存信息的操作方式 以提供保护 即 在页表中增加相应的保护位即可 81 4 4 5优点与缺点 纯分页存储管理的 优点 有效解决了碎片问题 主存利用率高 内存分配与回收算法也比较简单 缺点 采用动态地址变换机制 既增加硬件成本也降低了处理机速度 82 课堂练习P124 125 14 16 83 4 5纯段式存储管理4 5 1纯段式管理的基本思想 通常情况下 一个作业 多个程序段 多个数据段 这要求链接装配程序将它们按一维线性地址排列 从而给程序和数据的共享带来不便 一般情况下 用户希望 按逻辑关系对作业分段 并能根据名字来访问程序段和数据段 纯段式存储管理 较好地解决了程序和数据的共享问题以及程序动态链接等问题 84 1 基本原理 内存空间被动态地划分为若干个长度不相同的区域 每个区域称作一个物理段 每个物理段在内存中有一个起始地址 称作段首址 将物理段中的所有单元从0开始依次编址 85 2 逻辑地址空间划分 用户程序按逻辑上有完整意义的段来划分 称为逻辑段 例如 主程序 子程序 数据等可各成一段 每段对应于一个过程 一个程序模块或一个数据集合 将一个用户程序的所有逻辑段从0开始编号 称为段号 将一个逻辑段中的所有单元从0开始编址 称为段内地址 整个地址空间就构成了二维地址空间 用户程序的逻辑地址由段号和段内地址两部分组成 86 3 内存分配 系统以段为单位进行内存分配 为每一个逻辑段分配一个连续的内存区 物理段 逻辑上连续的各个段在内存不一定连续存放 87 4 5 2实现方法1 建立段表 系统为每个用户程序建立一张段表 用于记录用户程序的逻辑段与内存物理段之间的对应关系 包括逻辑段号 内存首地址和物理段长度三项内容 用户程序有多少逻辑段 该段表里就登记多少行 且按逻辑段的顺序的排列 段表存放在内存系统区里 段表如图4 16所示 88 图4 16段表示意图 89 系统中设立一张内存空闲区表 记录内存中空闲区域情况 用于为段分配和回收内存 2 建立空闲区表 90 系统提供一对寄存器 段表始址寄存器和段表长度寄存器 1 段表始址寄存器 用于保存正在运行进程的段表在内存的首地址 当进程被调度程序选中投入运行时 系统将其段表首址从进程控制块中取出送入该寄存器 2 段表长度寄存器 用于保存正在运行进程的段表的长度 当进程被选中运行时 系统将它从进程控制块中取出送入该寄存器 3 硬件支持 91 如图4 17所示 先将逻辑地址中的段号与段表长度寄存器中的段表长度进行比较 若段号超过段表长度 则产生越界中断 否则 系统将根据段号和段表始址寄存器中的段表起始地址计算出该段在段表中的位置 从该位置中将获得该段存放在内存中的起始地址 然后 检查段内位移是否超过该段的段长 若超过则产生越界中断 否则 将该段在内存的起始地址与逻辑地址的段内位移相加就可得到要访问的物理地址 4 地址映射过程 92 93 例4 1 在一个纯段式存储管理系统中 其段表如表4 1所示 求如表4 2所示的逻辑地址对应的物理地址 单位 B 表4 1段表 表4 2逻辑地址 94 解 1 由表4 1知 段号为0的段的内存起始地址为210 段长为500 由表4 2知 逻辑地址的段内位移为430 因为430 500 所以该逻辑地址是合法的 其对应的物理地址为 210 430 640 2 由表4 1知 段号为1的段的内存起始地址为2350 段长为20 由表4 2知 逻辑地址的段内位移为10 因为10 20 所以该逻辑地址是合法的 其对应的物理地址为 2350 10 2360 95 3 由表4 1知 段号为2的段的内存起始地址为100 段长为90 由表4 2知 逻辑地址的段内位移为500 因为500 90 即逻辑地址的段内位移500已超过了段长90 所以该逻辑地址是非法的 产生越界中断 96 4 5 3段的共享与保护 段式存储管理可以 方便地实现内存信息的共享并进行有效的内存保护 这是因为 段是按逻辑意义来划分的 可以按段名访问的缘故 97 在多道程序环境下 许多应用程序 子程序是被多个用户所使用的 随着多窗口及各种工具软件的流行 被共用的程序和数据都在急剧增长 如果用户所使用的程序和数据都保留一个运行副本 那么空间的浪费太大 最好的办法是 只保留一个副本 供多个用户使用 称为共享 如果多个用户进程或作业需要共享某段程序或数据 可以使用不同的段名 在各自的段表中填入已在内存中的共享段的起始地址 并设置适当的读写控制权 就可以做到共享一个内存段的信息 1 段的共享 98 2 段的保护 在多道程序的情况下 为了保证段的共享并使程序顺利执行 必须实行对段的保护 一般有下列措施 1 利用段表及段长来实现段的保护 防止程序执行时地址越界 2 存取权限保护法 在段表中设有 存取权 一项 可对程序的访问权限进行各种必要的限制 3 存储保护键保护 由于I O通道对存储器访问是不经过段表的 因此有的机器还采用存储保护键保护 99 4 5 4分段与分页的区别 分页与分段存储管理系统虽然在很多地方相似 例如 它们在内存中都是离散的 都要通过地址映射机构将逻辑地址映射到物理内存中 但从概念上讲 两者是完全不同的 100 它们之间的区别如下 1 页是信息的物理单位 分页的目的是实现离散分配 消除内存的外碎片 提高内存利用率 段是信息的逻辑单位 每一段在逻辑上是一组相对完整的信息 2 页式存储管理的作业地址空间是一维的 而段式存储管理的作业地址空间是二维的 3 页的大小固定且由系统确定 是等长的 而段的长度不定 它是由具有相对完整意义的信息长度确定 4 分页的优点体现在内存空间的管理上 而分段的优点体现在地址空间的管理上 101 课堂练习P124 125 13 17 18 102 前几节介绍的各种存储管理方案有一个共同的问题 即 当一个参与并发执行的进程运行时 其整个程序必须都在内存 因而存在如下缺点 1 若一个进程的程序比内存可用空间还大 则该程序无法运行 2 由于程序运行的局部特性 一个进程在运行的任一阶段只需使用所占存储空间的一部分 因此 未用到的内存区域就被浪费 改进 虚拟存储管理 103 引进虚拟存储技术 其基本思想是 利用大容量的外存来扩充内存 产生一个比有限的实际内存空间大得多的 逻辑的虚拟内存空间 以便能够有效地支持多道程序系统的实现和大型作业运行的需要 从而增强系统的处理能力 4 6虚拟存储器管理 104 4 6 1虚拟存储器的概念 1 程序局部性原理 虚拟存储管理的效率与程序局部性程度有很大关系 根据统计 进程运行时 在一段时间内 其程序的执行往往呈现出高度的局部性 包括时间局部性和空间局部性 105 1 时间局部性 时间局部性是指 若一条指令被执行 则在不久的将来 它可能再被执行 在一段局部时间内 程序某一部分的数据或指令被重复性地访问 这对应于程序结构中的循环 子程序 常用到的变量及数据等 106 2 空间局部性 空间局部性是指 一旦一个存储单元被访问 那么它附近的单元也将很快被访问 在一局部存储空间中 指令或数据被接连访问到 这对应于程序结构中的顺序执行的指令 线性数据结构以及在相邻位置存放的数据或变量 107 众所周知的一些事实 1 进程的某些程序段在进程整个运行期间 可能根本不使用 如出错处理等 因而 没有必要先调入内存 2 互斥执行的程序段在进程运行时 根据条件只执行其中一段 如分支语句等 因而 各互斥段没有必要同时驻留内存 3 在进程的一次运行中 有些程序段执行完毕 从某一时刻起不再用到 因而 没有必要再占用内存区域 根据以上分析 可以看出 程序局部性原理是虚拟存储技术引入的前提 108 2 虚拟存储器管理 对于采用实存管理的方案 要求进程执行代码一次性装入内存 而且 一旦装入内存便一直驻留到进程运行结束 而采用虚拟存储技术 一个进程的程序可以多次分别装入内存 运行中 暂时不用部分可以换出内存 需用部分可以换进内存 且程序在内存中可以分散存放 109 所谓虚拟存储器 是指 当进程要求运行时 不是将它的全部信息装入内存 而是将其一部分先装入内存 另一部分暂时留在外存的存储器系统 进程在运行过程中 要使用的信息不在内存时 发中断 由操作系统将它们调入内存 以保证进程的正常运行 110 虚拟存储系统将内存与外存有机地结合在一起 从而得到一个容量很大的虚拟空间 使用户感到仿佛得到一个很大的内存 虚存虽然比内存要大得多 但不可能无限大 其大小要受到外存空间的限制 以及CPU地址所能表示范围的限制 有两种常见的虚拟存储管理方案 1 虚拟页式存储管理2 虚拟段式存储管理 111 课堂练习P125 19 22 112 4 6 2虚拟页式存储管理 又称为请求页式存储管理 请求页式的基本思想是 在进程开始执行之前 不是装入全部页面 而是只装入一个 甚至0个 页面 然后根据进程执行的需要 动态地装入其它页面 113 1 页表 页表中将增加若干项 状态位 又称中断位或特征位 指示该页在内存还是在外存 外存地址给出该页在外存的地址 修改位指示该页在内存驻留期间是否被修改过 为了帮助操作系统对要置换出内存的页面进行选择 在页表中还可以增加一个引用位 以反映该页最近的使用情况 一般说来 一个页表的表目通常可包括如下的数据内容 114 地址映射时 当从页表中查出此页信息不在内存 则发生缺页中断 暂停进程执行 CPU转去执行缺页中断处理程序 该程序负责把所需的页从外存调入内存 并把物理块号填入页表 更改状态位 返回继续执行被中断的进程 见图4 18所示 2 缺页中断处理 115 116 3 页面淘汰 当内存空间已被占满而又要调入新页时 必须把已在内存的某一页面淘汰掉 如果被淘汰的页面曾被修改过 还要将此页写回到外存 然后再换进新的页面 这一过程称为页面淘汰 页面淘汰可以在整个内存空间范围内进行 也可以只在一个进程空间范围内考虑 为了对有关算法作比较准确的评估 以下限在局部范围内考虑 并假定系统限定每个进程占有的最大页面数 当空间已满 而又有新的页面要装入时 则淘汰自己的一个页面而不能淘汰别的进程的页面 117 4 页面淘汰算法 用来选择被淘汰页面的算法称做页面淘汰算法 1 最佳淘汰算法 OPT 2 先进先出淘汰算法 FIFO 3 最近最久未使用淘汰算法 LRU 4 最近最少使用淘汰算法 LFU 118 1 最佳淘汰算法 OPT 该算法淘汰以后不再需要的 或者在最长时间以后才会用到的页面 这一算法是一种理想算法 不可能实现 但它可以作为衡量其它页面淘汰算法优劣的一个标准 119 该算法淘汰进入内存时间最长的页面 这是一种最简单的页面淘汰算法 在程序按线性顺序访问逻辑地址空间时 比较理想 否则 效率不高 特点是 遇到循环执行的程序段时 往往会把频繁访问的页面淘汰 FIFO算法有可能产生异常现象 即当分给一个进程的页面数增多时 缺页中断次数反而增加 所以 先进先出算法往往不单独使用 而是作为其它算法的一种辅助策略使用 2 先进先出淘汰算法 FIFO 120 该算法淘汰最后一次访问时间距当前时间间隔最长的页面 其出发点是用最近的过去估计最近的将来 一个已在内存的页面 如果在本次缺页中断前的最近一段时间内 未被使用的时间最长 那么将来它很可能不再被使用 故应淘汰 LRU算法的实现开销很大 需要有硬件支持 3 最近最久未使用淘汰算法 LRU 121 该算法淘汰最近一段时间内 访问次数最少的页面 这只要在页表中给每一页增设一个访问计数器即可实现 每当该页被访问时 访问计数器加1 而发生一次缺页中断时 则淘汰计数值最小的那一页 并将所有的计数器清零 4 最近最少使用淘汰算法 LFU 122 5 影响缺页中断次数的因素 1 分配给进程的物理块个数 一般 分配给进程的物理个数多 则缺页中断率就低 反之 缺页中断率就高 2 页面大小 页面尺寸大 则只需较小的页表 这样页表占用空间少且查表速度快 缺页中断也相应少些 但在页面调度时 换页时间较长 且空间浪费的可能性大 一般内碎片平均占二分之一页面 页面尺寸小 则正好相反 所以页面大小要根据计算机性能及用户要求等具体情况确定 3 程序本身的编制方法 4 页面淘汰算法的选择 123 6 虚拟分页存储管理性能分析举例 虚拟分页存储管理实现了虚拟存储功能 能使更多的作业投入运行 提高了系统效率 但缺页中断处理要付出相当大的代价 页面的调入 调出不仅增加I O的负担 也影响系统的效率 因此 应尽可能地减少缺页中断的次数 这需要从以下几个方面来考虑 1 程序设计的质量 2 页面的大小 3 分配的内存块数 4 页面淘汰算法性能 124 1 程序设计的质量 一般地说 我们总希望编制出的程序局部化程度较高 这样 程序执行时可经常集中在几个页面上进行访问 可减少缺页中断的次数 125 2 页面的大小 设计请求式分页存储系统时 页面大小也是一个重要参数 页面较大时 页表较小 占用较少的存储空间且查表速度较快 缺页中断次数少 但是在页面调度时 一次换页时间较长 页内碎片可能较大 浪费存储空间 页面小时 则情况正好相反 一般地 页面大小可根据系统实际情况来确定 它与计算机的性能及用户的要求有关 比较合适的页面大小通常为lk 2k或4k 126 3 分配的内存块数 从理论上说 在提供了虚拟存储系统之后 每个作业只要分到一块内存就可以执行了 其它各页可在程序执行过程中根据请求动态装入 但实际上 一个作业在执行时所产生的缺页中断次数与分配到的内存块数是有一定关系的 当分配到的内存块数增加时 一般说来 缺页中断次数减少 经过研究 人们得出结论 对所有程序来说 要使其有效地工作 应至少将总页面的一半装入到内存中 127 4 页面淘汰算法性能 由于页面淘汰算法依赖于运行中的具体程序 因此判断页面淘汰算法的好坏要考虑程序的行为 对于一个程序来说 我们认为执行踪迹是严格按顺序执行的一系列指令 地址踪迹是每个指令执行时所涉及的地址 而页面踪迹则是地址踪迹所依附的页面 把这些页面按执行的顺序列出来 便构成了页面走向 利用页面走向 可以刻划程序的执行性能 128 在这里 我们给出一个典型的页面走向序列 P 1 2 3 4 1 2 5 1 2 3 4 5 假定分配给该作业的主存块数m是固定的 分别是3块和4块 在此分别讨论 利用FIFO算法和LRU算法 缺页中断次数F及缺页率f 缺页率为 某段时间内 缺页中断次数与页面走向次数之比 例1 主存块数m 3 置换算法采用FIF0算法 缺页中断次数及缺页率如图4 19所示 129 在图4 19中 P行表示页面走向 M行表示在主存中的页面号 其中带有 的表示新调入页面 在M行的各列按调入的顺序排列 带有圆圈的数字表示下一时刻将被淘汰页面 F行表示是否引起缺页中断 带 号的表示引起缺页中断 从图4 19可以看出 缺页中断次数为F 9次 缺页率f 9 12 75 130 例2 设m 4 仍采用FIF0算法 缺页中断次数及缺页率如图4 20所示 131 可以算出 在分配给该作业的内存块数增加到4时 缺页中断次数由图4 19的9次反而增加到了F 10次 缺页率由75 增加到10 12 83 这就是FIF0算法的一种异常现象 随着分配的主存块数的增加 缺页中断次数不但没有降低 反而增加了 这与该算法完全不考虑程序的动态特征有关 132 例3 设m 3 采用LRU算法 缺页中断次数及缺页率如图4 21所示 由于采用LRU算法 M中各列按访问的时间顺序排列 最近被访问的页面在最上面 此时 缺页中断次数F 10 缺页率f 10 12二83 133 例4 设m 4 采用LRU算法 则缺页中断次数及缺页率如图4 22所示 由图4 22可以算出 当m 4时 缺页中断次数F 8次 缺页率为f 8 12 67 134 比较例3与例4 明显看出在LRU算法中 当分配给作业的主存块数增加时 缺页中断次数明显减少 缺页中断率明显降低 所以 LRU算法是一种较好的页面置换算法 总之 虚拟页式存储管理有纯分页存储管理的全部优点 解决了外部碎片问题 提供了大容量的虚拟存储器 更有效地利用了内存 方便了用户 特别是大作业用户 缺点是为了处理缺页中断 增加了处理机的开销 而且还可能导致抖动问题 系统频繁发生缺页中断 使系统的复杂性大大增加 135 课堂练习P125 126 23 26 28 29 136 4 6 3虚拟段式存储管理 又称为请求式分段存储管理 为了能实现虚拟存储 段式逻辑地址空间中的程序段在运行时并不全部装入内存 而是如同请求式分页存储管理 首先调入一个或若干个程序段运行 在运行过程中调用到哪段时 就根据该段长度在内存分配一个连续的分区给它使用 若内存中没有足够大的空闲分区 则考虑进行段的紧凑或将某段或某些段淘汰出去 137 虚拟段式存储管理的内存分配 类似于可变式分区存储管理 可采用最先适应算法 最佳适应算法 最差适应算法 其地址变换过程类似于请求式分页存储管理 但又有所不同 138 1 段表 段号 一个程序段在内存中的唯一标号 段长 该程序段的长度 状态位 该程序段是否在主存 引用位 该程序段是否最近被使用过 改变位 该程序段内容在内存中是否被修改过 存取权 R 是否允许读操作 W 是否允许写操作 E 是否允许执行此段中程序 A 增补位 是否允许在此段末尾续加信息 起始地址 若该程序段在主存 则存放该段在内存的起始地址 否则 存放该程序段在辅存的首地址 139 2 虚拟段式管理的动态地址变换过程 假设 主程序段在执行中要访问X程序段的Y单元 则动态地址变换过程如图4 21所示 这里给出的是简略图 实际上地址变换是比较复杂的 140 141 3 虚拟段式存储管理的优 缺点 虚拟段式存储管理有如下5优点 1 可提供大容量的虚存 这与请求式分页存储管理类似 一个作业运行时 内存只存放较少的段 在作业执行过程中 需要使用某段时再从辅存调入 若此时内存无空间 则需进行段的紧凑或是移出某些段 142 2 允许动态增加段的长度 对于一个较大的段 开始可以装入其中的一部分 当程序员企图往段中增加新的内容或扩大段的长度时 可以动态增加段的长度 因为段表中有一个增补位 当访问的地址大于段长时便产生越界中断 此时检查增补位 若为1 则可增加段长度 可通过紧凑或移去一些段的办法来实现 若增补位为0 表示不能增加段的长度 利用允许动态增长段的特性 很容易处理变化的数据结构 比如表格和数据段等 143 3 便于段的动态链接 一个作业可能由若干个程序段组成 在采用单一线性地址空间时 这些程序段要在执行之前完成链接和装配工作 产生出一个完整的连续空间 这称之为静态链接 这种工作不仅费时 有时甚至是徒劳的 因为在作业运行过程中 有的程序模块根本未被调用和执行过 为此 最好是在需要调用某程序段时 再把它链接到作业空间中 这就是所谓动态链接 由于请求式分段存储管理为用户提供的是二维地址空间 每个程序模块构成独立的分段 有自己的名字 这为实现了动态链接提供了基础 144 4 便于实现程序段的共享 进入内存中的程序段占据内存中的一个连续存储区 若多个作业要共享它 只需在它们各自的段表中填入该段的起始地址 设置上适当的存取权限即可 5 便于实现存储保护 在段表中规定了段的存取权限和段的长度 超出段长引起越界中断 违反存取权限引起存储保护中断 通过这种方法能防止一个用户作业侵犯另一用户作业 也可以防止对共享程序的破坏 145 虚拟段式存储管理的缺点 进行地址变换和实现紧凑操作要花费处理机时间 为管理各分段要设立若干表格 需提供额外的存储空间 而且也