第5章存储管理.ppt

第5章存储管理 存储管理的功能分区存储管理覆盖与交换技术页式管理段式与段页式管理局部性原理和抖动问题 第5章存储管理 5 1存储管理的功能存储器是计算机系统的重要资源之一 因为程序 数据和各种控制用的数据结构都必须占用一定的存储空间存储器分两类 主存储器 简称主存或内存 辅助存储器 简称辅存或外存 5 1存储管理的功能 存储器的层次结构高速缓存Cache少量的 非常快速 昂贵 易变的内存RAM若干兆字节 中等速度 中等价格 易变的磁盘数百兆或数千兆字节 低速 价廉 不易变的 5 1存储管理的功能 由操作系统协调这些存储器的使用重要性 直接存取要求内存速度尽量快到与CPU取指速度相匹配 大到能装下当前运行的程序与数据 否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥 5 1存储管理的功能 内存 由顺序编址的块组成 每块包含相应的物理单元 用来存放当前正在运行程序的代码及数据 是程序中指令本身地址所指的 即程序计数器所指的存储器内存可分为 系统区 用于存放操作系统用户区 用于装入并存放用户程序和数据CPU要通过启动相应的输入输出设备后才能使外存与内存交换信息 5 1存储管理的功能 5 1 1虚拟存储器虚拟存储器是存储管理的核心概念实验表明 在一个进程的执行过程中 其大部分程序和数据并不经常被访问 因此 存储管理系统将不经常被访问的程序和数据放在外存 待需要访问时再调入内存 问题 进程中一部分在内存 另一部分在外存 如何实现 它们的地址如何安排 5 1 1虚拟存储器 用户程序的处理过程通常 由用户编写的源程序 首先要由编译程序编译成CPU可执行的目标代码 然后由链接程序把一个进程的不同程序段链接起来以完成所要求的功能 显然 对于不同的程序段 应具有不同的地址 用户程序的多级处理过程 源程序 编译程序或汇编程序 目标模块 链接程序 装配模块 装配程序 装配阶段 编译阶段 内存中可执行代码 5 1 1虚拟存储器 如何安排目标代码的地址 按照物理存储器中的位置赋予实际物理地址优点 CPU执行目标代码的速度高问题 由于存储器的容量限制 将减少内存并发执行的进程数对于较大进程 当其所要求的总内存容量大于内存容量时 将无法执行由于编译程序必须清楚内存使用情况 并且一个进程的不同程序段要连续存放 从而造成编译程序非常复杂 5 1 1虚拟存储器 如何安排目标代码的地址方法 将源程序编译后链接到虚拟地址空间地址空间和存储空间名空间 用汇编语言或高级语言编写程序时 总是通过符号名来访问某一单元 称程序中由符号名组成的空间为名空间 虚拟地址 逻辑地址或相对地址 用户的源程序经过汇编或编译后形成目标代码 目标代码通常采用相对地址的形式 其首地址为0 其余指令中的地址都相对于首地址而编址 称为虚拟地址 不能用逻辑地址在内存中读取信息 5 1 1虚拟存储器 物理地址 绝对地址或实地址 内存中存储单元的地址 可直接寻址 地址变换为了保证CPU执行指令时可正确访问存储单元 需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址 这一过程称为地址映射 由源程序到实际存放该程序指令或数据的内存物理位置的变换如图5 1所示 源程序 具有相对地址的目标程序 可执行代码 内存中 地址空间 名字空间 存储空间 图5 1地址变换与物理存储器 5 1 1虚拟存储器 虚拟存储器 是指进程中的目标代码 数据等的虚拟地址组成的虚拟空间虚拟存储器不考虑物理存储器的大小和信息存放的实际位置每个进程都拥有自己的虚拟存储器虚拟存储器的容量由计算机的地址结构和寻址方式确定假设CPU给出的有效地址长度为k字节 按字节寻址 则逻辑空间 虚存空间 大小为2k个字节 k 18 则容量为218 256KBk 24 则容量为224 16MBk 32 则容量为232 4GB 5 1 1虚拟存储器 虚拟存储器的具体实现在硬件支持下 软硬件相互协作 将内存和外存结合起来统一使用 通过这种方法把内存扩充 使用户在编制程序时不受内存限制 实现虚拟存储地址变换 建立虚拟地址与内存地址的关系大容量的外存储器的支持 5 1存储管理的功能 5 1 2地址变换内存空间是一维线性空间虚拟空间是一维或多维线性空间问题 如何将几个虚存空间变换到唯一的内存虚拟空间的划分与计算机系统结构有关例如 VAX 11型机中虚拟空间的划分 如图5 2 系统空间进程空间 分为程序区和控制区 图5 2虚拟空间的划分 5 1 2地址变换 问题 如何将几个虚存空间变换到唯一的内存虚拟地址映射为内存地址原因 当程序装入内存时 操作系统要为该程序分配一个合适的内存空间 由于程序的虚拟地址与分配到内存物理地址不一致 而CPU执行指令时 是按物理地址进行的 所以要进行地址变换 实现地址变换方法静态地址重定位动态地址重定位 5 1 2地址变换 1 静态地址重定位当用户程序被装入内存时 一次性实现虚拟地址到物理地址的转换 以后不再转换 一般在装入内存时由装配程序完成 静态地址重定位 Load1 500 12345 0 100 500 700 Load1 500 12345 0 5100 5500 5700 5000 进程A的地址空间 进程A的存储空间 优点 简单易实现无需硬件支持缺点 不能再移动只能连续分配共享困难无法实现虚拟存储 5 1 2地址变换 2 动态地址重定位在程序运行过程中 在CPU访问内存之前 将要访问的程序或数据地址转换成内存地址 即 在逐条指令执行时完成地址映射 动态地址重定位由硬件地址映射机制来完成一个或多个基地址寄存器BR一个或多个程序虚拟地址寄存器VR指令或数据的内存地址MA BR VR 动态重定位过程如图5 3 图5 3动态地址重定位 5 1 2地址变换 2 动态地址重定位优点可以对内存进行非连续分配 显然 同一进程的各分散程序段 可分散存放 只需增加几对寄存器 提供了实现虚拟存储器的基础易于实现共享缺点需要附加硬件支持算法复杂 5 1存储管理的功能 5 1 3内外存数据传输的控制要实现内存扩充 在程序执行过程中 内存与外存之间必须经常交换数据 其控制方法有 用户程序自己控制 覆盖技术操作系统控制 交换技术 5 1 3内外存数据传输的控制 覆盖技术覆盖技术要求用户清楚地了解程序的结构 并指定各程序段调入内存的先后次序覆盖技术不能实现虚拟存储器交换技术交换方式 由操作系统将内存中处于等待状态的进程换出内存 而将处于就绪状态进程换入内存请求调入方式 在执行时 当所要访问的程序或数据段不在内存中 则操作系统自动从外存将其调入预调入方式 由操作系统预测在不远的将来会访问的那些程序段和数据段部分 并在它们被访问之前 系统选择适当时机将它们调入内存 5 1存储管理的功能 5 1 4内存的分配与回收内存管理要为每一个进程分配内存空间 当执行结束时 要及时收回该进程所占用的内存资源 因此 为了有效合理利用内存 设计内存的分配与回收方法时 必须考虑以下内容 分配结构 登记内存使用情况 供分配程序使用的表格与链表放置策略 确定调入内存的程序和数据在内存中的位置 5 1存储管理的功能 5 1 4内存的分配与回收交换策略 当需要将某个程序段和数据调入内存时 若内存不足 决定将某些信息调出内存的策略调入策略 决定外存中的程序段和数据段什么时间按什么方式装入内存 即与内外存数据传输控制方式有关回收策略 包括回收时机 对所回收的内存空闲区和已存在的内存空闲区的调整 5 1存储管理的功能 5 1 4内存信息的共享与保护内存共享 两个或多个进程共用内存中相同区域目的 节省内存空间 提高内存利用率实现进程通信 数据共享 共享内容 代码共享 要求代码为纯代码数据共享 5 1存储管理的功能 5 1 5内存信息的共享与保护内存保护目的为多个程序共享内存提供保障 使在内存中的各程序 只能访问它自己的区域 避免各程序间相互干扰和破坏 特别是当一道程序发生错误时 不致于影响其他程序的运行 保护系统程序区不被用户侵犯 有意或无意的 不允许用户程序读写不属于自己地址空间的数据 系统区地址空间 其他用户程序的地址空间 5 1 5内存信息的共享与保护 常用的内存信息保护方法有硬件法 软件法和软硬结合3种上下界保护法 每个进程设置一对上下界寄存器 上下界寄存器中存放了被保护程序和数据段的起始地址和终止地址 在程序执行时 进行访址合法性检查 即检查地址是否在所规定的范围内 如图5 4 5 1 5内存信息的共享与保护 图5 4上 下界寄存器保护法 5 1 5内存信息的共享与保护 保护键法 为每一个被保护存储块分配一个单独的保护键 而在程序状态字中则设置相应的保护键开关字段 对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配 保护键可设置成对读写同时保护或只对读 写进行保护 5 1 5内存信息的共享与保护 图5 5保护键保护法 5 2分区存储管理 分区管理是把内存划分为若干个大小不等的区域 除操作系统占用一个区域外 其余由各并发进程共享 分区管理是满足多道程序设计的最简单的一种存储管理方法 它允许多个用户程序同时存在系统内存中 即共享内存空间 5 2分区存储管理 5 2 1分区管理基本原理基本原理 每一个进程占据一个分区 以连续存放该进程的程序和数据 按分区的时机 分区管理分为 固定分区动态分区 5 2 1分区管理基本原理 1 固定分区法固定分区法 是将内存区固定地划分为若干个大小不等的区域 分区划分的原则由一般系统操作员或操作系统决定 分区一旦划分结束 在整个执行过程中就保持不变 5 2 1分区管理基本原理 内存管理 设置分区说明表分区说明表 说明各分区号 分区大小 起始地址以及是否空闲 分区状态 如图5 6 a 内存分配 每个区分配一个进程内存回收 简单缺点 内存利用率不高 图5 6固定分区法 5 2 1分区管理基本原理 2 动态分区法动态分区法 事先不划定分区的大小 而是在作业的处理过程中 根据作业或进程对内存大小的要求来划分内存区域初始分配 采用动态分区法 在系统初启时 除了操作系统中常驻内存部分外 只有一个空闲区 随后 分配程序将该区依次划分给调度选中的作业或进程 如图5 7 图5 7内存初始分配情况 随着进程的执行 会出现一系列的分配和释放 图5 8内存分配变化过程 2 动态分区法 内存管理分区说明表 说明各分区号 分区大小 起始地址 分区状态可用分区表 每个表目记录一个空闲分区 如图5 9 a 可用分区自由链 利用每个空闲区的头几个单元存放本空闲区的大小及下一个空闲区的起始地址 将所有的空闲区链接起来 然后 系统再设置一个自由链首指针指向第一个空闲区 如图5 9 b 内存资源请求表 描述各作业或进程请求内存资源大小的情况 如图5 9 c 图5 9可用表 自由链及请求表 5 2 2分区的分配与回收 1 固定分区的分配与回收固定分区的分配存储管理程序根据请求表查询分区说明表 从中找到一个满足要求的空闲区 并将其分配给申请者 如图5 10固定分区的回收当进程执行完毕 不再需要内存资源时 管理程序将对应分区状态置为空闲即可 图5 10固定分区分配算法 5 2 2分区的分配与回收 2 动态分区的分配与回收需要解决3个问题如何根据要求寻找合适的空闲区分配给程序分配空闲区后 如何更新可用表或自由链内存资源释放后 如何与相邻块链接合并 更新可用表或自由链动态分区的分配 从可用表或自由链中找空闲区最先适应法最佳适应法最坏适应法 1 最先适应法 当接到内存申请时 查可用表或自由链 找到第一个不小于请求的空块 将其分割并分配 特点 简单 快速分配可用表或自由链的数据结构 空白区按起始地址大小递增排序如果请求分配的容量为S 则从X1开始比较 直至Xi S为止 然后 从Xi中分配S 剩余部分保留在空白区表中原来的位置或合并 如图5 11优点 算法简单 查找速度快缺点 小的空白区集中在链的前端 图5 11最先适应算法 2 最佳适应法 当接到内存申请时 在可用表或自由链中找到一个不小于请求的最小空闲区进行分配 特点 用最小空间满足要求可用表或自由链的数据结构 空白区按其容量大小递增排列 即 X1 X2 X3 Xn设请求分配的容量为S 则从X1开始比较 直至S Xi 然后 从Xi中减去S 如有剩余 则将空白区插入适当位置 否则 S Sn 则分配失败 剩余空白区的处理 如果Xi S G 参数 则Xi全部给作业 否则 Xi S插入适当位置 看起来最佳 实际怎么样 2 最佳适应法 优点只要查找一半的表格便能找到最佳适应的空白区若空白区的容量正合适 则它必被选中若没有正合适的空白区 则选一个能满足要求的最小空白区缺点碎片问题 3 最坏适配算法 当接到内存申请时 在可用表或自由链中找到一个不小于请求的最大空块进行分配 特点 当分割后空闲块仍为较大空块可用表或自由链的数据结构 空白区按其容量大小递减连接起来 即 X1 X2 X3 Xn如果请求分配的容量为S 并且X1 S 则从X1中分配S 如果有剩余部分 将其插入适当位置 如果并且X1 S 则分配失败 3 最坏适配算法 优点只比较S和X1 就能判断能否满足要求X1分配后剩下的空白区可能比较大 仍能满足一般要求缺点各空白区比较均匀地减少 工作一段时间后就不能满足对于较大空白区的分配要求 5 2 2分区的分配与回收 3 动态分区的回收与拼接当作业或进程执行结束时 存储管理程序要收回已使用完毕的空闲区 并将其插入空闲区可用表或自由链 回收或分配时 空闲区可能需要拼接合并 具体如图5 12 图5 12空闲区的合并 5 2 3有关分区管理其他问题的讨论 1 关于虚存的实现无法实现虚拟存储器2 关于内存扩充使用覆盖或交换技术实现内存扩充3 关于地址变换和内存保护动态分区 采用动态重定位实现地址变换内存保护 上下界寄存器 保护键 1 上下界寄存器和地址检查机构当作业被调度运行时 作业在内存中的上下界地址送上下界寄存器 每次内存访问时 地址检查机构作越界检查 作业程序须是绝对地址或静态可浮动的 CPU 主存 下界寄存器 上界寄存器 True True 地址A falsefalse 程序性中断 3 分区的保护措施 2 基址寄存器 长度寄存器和动态地址转换机构当作业被调度运行时 将作业所占内存基址及长度送基址 长度寄存器 每次内存访问时 先看访问地址是否小于长度 然后 基址进行访存 用户程序代码是动态浮动的 CPU 主存 基地址寄存器 长度寄存器 True 地址A false 程序性中断 5 2 3有关分区管理其他问题的讨论 4 分区管理的主要优缺点优点实现内存共享 有助于多道程序设计 提高资源利用率硬件支持少 算法简单 易于实现缺点产生碎片 经过一段时间的分配回收后 内存中存在很多很小的空闲区 它们每一个都很小 不足以满足分配要求 这些空闲区称为碎片 降低了内存的有效利用作业或进程的大小受分区大小控制 除非采用覆盖和交换技术无法实现各分区间的信息共享 5 3覆盖与交换技术 在多道环境下用来扩充内存的方法覆盖技术 主要用于早期的操作系统交换技术 在现代操作系统中仍具有较强的生命力 5 3覆盖与交换技术 5 3 1覆盖技术覆盖 是指把程序划分成若干个功能相对独立的程序段 按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 覆盖技术要求程序员提供一个清楚的覆盖结构 即程序员必须完成把一个程序划分成不同的程序段 并规定好它们的执行和覆盖顺序的工作举例说明 图5 13覆盖示例 5 3覆盖与交换技术 5 3 2交换技术交换 是指先把内存中暂时不用的程序或数据写入外存交换区 以释放内存空间 再从外存交换区中调入指定的程序或数据到内存来 并让其执行交换与覆盖的区别交换主要是在进程或作业之间进行覆盖主要是在同一个作业或进程内进行 并且只能覆盖那些与覆盖程序段无关的程序段 5 4页式管理 5 4 1页式管理的基本原理基本原理页 将各进程的虚拟空间划分成若干个长度相等的页片 将内存空间按页的大小划分成片或页面分配 将进程的页不连续地分布到内存页面 页表 将页式虚地址与内存页面物理地址建立一一对应页表 页式管理的基本原理 用户程序划分把用户程序按逻辑页划分成大小相等的部分 称为页 页号从0开始 页内地址是相对于0编址 用户程序的划分是由系统自动完成的 对用户是透明的 页长的划分和内存外存之间数据传输速度以及内存大小有关 一般 每个页长的大小为2的整数次幂 通常为1 4K 地址的高位部分为页号 低位部分为页内地址 逻辑地址 内存空间 物理地址 按页的大小划分为大小相等的区域 称为片或页面内存分配 以页为单位进行分配 并按作业的页数多少来分配 逻辑上相邻的页 物理上不一定相邻回收 当进程结束时 系统回收它的所有物理页 页式管理的基本原理 因页式方法中逻辑地址与物理地址之间失去自然联系 故要通过页表来表示对应关系 页式管理中 因逻辑地址与物理地址之间失去自然联系 故要通过页表来表示对应关系 5 4页式管理 5 4 2静态页面管理静态页面管理方法是在作业或进程开始执行之前 把该作业或进程的程序段和数据全部装入内存的各个页面中 并通过页表和硬件地址机构实现虚拟地址到内存物理地址的地址映射 5 4 2静态页面管理 1 内存页面分配与回收分配 需要页表 请求表 存储页面表 1 页表页表PMT 每个进程都建立了一个页表 页表给出虚拟地址号和具体内存块号相应的关系页表在内存中占有一个固定的存储区 页表区 页表的大小由进程或作业的长度决定 图5 15基本页表示例 1 内存页面分配与回收 2 请求表请求表 用于确定作业或进程的虚拟空间的各页在内存中的实际对应位置整个系统一张表 每个作业或进程对应一个表目 包括该作业或进程的页表起始地址 页表长度 状态信息等 1 内存页面分配与回收 3 存储页面表整个系统一张 存储页面表指出内存各页面是否已被分配出去 以及未分配页面的总数方法 位示图法 在内存中划分一块固定区域 每个单元的每个比特代表一个页面 用1表示该页面已被分配空闲页面链法 队首页面的第一个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针 其他页面的第一个单元分别指向下一个空闲页面的指针 图5 17位示图 5 4 2静态页面管理 2 分配算法计算一个作业或进程所需要的总页面数查存储页面表 看看是否还有N个空闲页面如果有相应空闲页面 则设置页表 将页表始址 页表长度等填入请求表搜索空闲页面表 分配N个空闲页面 将页号和页面号填入页表如图5 18所示 图5 18页面分配算法流图 5 4 2静态页面管理 3 地址转换由硬件动态地址转换机构将虚拟地址映射成内存物理地址才能正确访存 动态地址变换机构 页表 存放虚拟页与物理页面的对应关系 PCB表中有指针指向页表 1 8 5 3 0 4 9 8 7 6 5 4 3 2 1 0 3 2 1 0 逻辑空间 物理空间 页表 页号 地址结构逻辑地址 p 页号 d 页内位移 物理地址 f 页面号 d 页内位移 p INT 线性逻辑地址 页面大小 d 线性逻辑地址 p 页面大小 4 3 2 1 0 页号 动态地址变换机构 页面大小的考虑将页面大小取成2的k次幂 k是正整数 获取p和d的除法或乘法只要通过位移实现 页面大小为2的k次幂的地址转换原理如下 Pd 页表始地 f nk 10 fd nk 10 页表 动态地址变换机构 p 页表 地址越界 L 比较 P L p p 快表 P d 物理地址 页表地址寄存器 页表长度寄存器 逻辑地址 地址映射机制 举例 1 设每个页面长度为1KB 即1024B 某进程的页表如图5 19所示 请简述执行下述指令的地址变换过程 100LOAD1 2500 图5 19页号与页面号 解 执行指令100LOAD1 2500的地址变换过程为 1 取指令首先根据该指令的逻辑地址100 得到相应的虚拟页式地址为 0 100 然后查页表得到其页面号为2 计算出物理内存地址为2 1024 100 2148因此 从内存地址为2148单元中取出指令执行 2 取数据首先根据数据的虚拟地址2500 得到相应的虚拟页式地址为 2 452 然后查页表得到其页面号为8 计算出物理内存地址为8 1024 452 8644因此 从内存地址为8644单元中取出数据 放入寄存器1中 该地址变换过程如图5 20所示 图5 20地址变换 3 地址变换 取一个指令或数据至少要访问内存两次以上由于页表是驻留在内存的某个固定区域中 而取指令或数据必须经过页表变换才能得到实际物理地址 一次访问页表 以确定所取数据或指令的物理地址另一次是根据地址取数据或指令为了提高速度 采用高速联想寄存器 CPU有一个用于页号 块转换的联想存储器 将页表存入联想存储器的地址 其转换原理如下 Pd nk 10 fd nk 10 P2 f2 P1 f1 P f Pm fm 关键字值 高速联想存储器 Pd nk 10 fd nk 10 P2 f2 P1 f1 P f Pm fm f 页表始地 页表 联想存储器 联想存储器可以看成是页表的cache 采用 双管齐下 命中率 选用8 12项组成的联想存储器 并采用适当的替换策略 在联想存储器中匹配成功的可能性可达80 90 等效访问时间 设访存时间为750ns 搜索联想存储器的时间为50ns 命中率为80 则 80 750 50 20 750 50 750 950ns在进程被调度占用CPU时 将进程页表始址装入页表始地址寄存器 同时用新的页表内容替换联想存储器中的原内容 利用联想寄存器加速查表 5 4 3动态页式管理 连续性 离散性驻留性 交换性一次性 多次性虚拟存储器以CPU时间和外存空间换取昂贵内存空间 这是操作系统中的资源转换技术 5 4 3动态页式管理 虚拟存储技术问题的提出程序大于内存程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是 程序 数据 堆栈的大小可以超过内存大小 操作系统把程序当前使用的部分保留在内存 而把其它部分保存在磁盘上 并在需要时在内存和磁盘之间动态交换 X 60K 64K X 56K 60K X 52K 56K X 48K 52K 7 44K 48K X 40K 44K 5 36K 40K X 32K 36K X 28K 32K X 24K 28K 3 20K 24K 4 16K 20K 0 12K 16K 6 8K 12K 1 4K 8K 2 0K 4K 虚地址空间 物理地址空间 虚页 页框 000 1 15 000 1 14 000 1 13 000 1 12 111 0 11 000 1 10 101 0 9 000 1 8 000 1 7 000 1 6 011 0 5 100 0 4 000 0 3 110 0 2 001 0 1 010 0 0 110 在 不在内存 页表 虚地址8196 物理地址24580 5 4 3动态页式管理 虚拟存储技术程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性 表现在时间与空间两方面时间局部性 一条指令被执行了 则在不久的将来它可能再被执行空间局部性 若某一存储单元被使用 则在一定时间内 与该存储单元相邻的单元可能被使用 5 4 3动态页式管理 虚拟存储技术虚存 把内存与外存有机的结合起来使用 从而得到一个容量很大的 内存 这就是虚存实现思想 当进程运行时 先将一部分程序装入内存 另一部分暂时留在外存 当要执行的指令不在内存时 由系统自动完成将它们从外存调入内存工作 5 4 3动态页式管理 动态页式管理思想 在作业或进程开始执行之前 不一次性地将其程序段和数据段全部装入内存 而只装入被认为经常反复执行和调用的部分 其他部分则在执行过程中动态装入方法分为 请求页式管理预调入页式管理 5 4 3动态页式管理 两种管理的调入方式不同请求页式管理 当需要执行某条指令而又发现它不在内存时 或当执行某条指令需要访问其他数据或指令时 这些指令和数据不在内存中 从而发生缺页中断 系统将外存中相应的页面调入内存预调入页式管理 系统对那些在外存中的页进行调入顺序计算 估计出这些页中指令和数据的执行和被访问顺序 并按此顺序将它们顺次调入和调出内存 请求页式管理原理 基本工作原理在进程开始运行之前 不是装入全部页面 而是装入一个或零个页面 之后根据进程运行的需要 动态装入其它页面 当内存空间已满 而又需要装入新的页面时 则根据某种算法淘汰某个页面 以便装入新的页面 必须解决的问题只有一部分在内存中 作业是否能运行 如何发现要访问的虚页是否在内存中 如果所需的虚页不在内存中 从何处装 装到何处 内存已满怎么办 扩充页表表项 页号页面号改变位 查看此页是否在内存中被修改过 引用位 表示该页最近是否被访问过 根据引用位来决定淘汰哪一页 由不同的算法决定 状态位 表示该页是在内存还是在外存外存地址 请求页式管理原理 缺页中断在地址映射过程中 在页表中发现所要访问的页不在内存 则产生缺页中断 操作系统接到此中断信号后 就调出缺页中断处理程序 根据页表中给出的外存地址 将该页调入内存 使作业继续运行下去 如果内存中有空闲页面 则分配一页 将新调入页装入内存 并修改页表中相应页表项目的状态位及相应的页面号 若此时内存中没有空闲页面 则要淘汰某页 若该页在内存期间被修改过 则要将其写回外存 请求页式管理原理 图5 23动态页式管理流程图 5 4 4请求页式管理中的置换算法 常用的置换算法随机淘汰算法 随机选择某个用户的页面 并将其换出轮转置换算法 循环换出内存可用区内的一页先进先出置换算法 FIFO 选择在内存中驻留时间最长的页并淘汰之 最近最久未使用页面置换算法 LRU 选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 理想置换算法 最佳页面算法OPT 淘汰以后不再需要的或最远的将来才会用到的页面 常用的置换算法性能分析 例1 计算缺页次数某程序在内存中分配3个页面 初始为空 页面走向为4 3 2 1 4 3 5 4 3 2 1 5 FIFO432143543215页1432143555211页243214333522页34321444355xxxxxxx xx 共缺页中断9次 先进先出置换算法 FIFO LRU432143543215页1432143543215页243214354321页34321435432xxxxxxx xxx共缺页中断10次 最近最久未使用页面置换算法 LRU OPT432143543215页1432111555211页243333333555页34444444444xxxx x xx 共缺页中断7次 理想置换算法 最佳页面算法OPT 例2 计算缺页次数与缺页率 某程序在内存中分配m页初始为空 页面走向为1 2 3 4 1 2 5 1 2 3 4 5 当m 3 m 4时缺页中断分别为多少 用FIFO算法 当进程分得3个页面是 执行过程中内存页面变化如下图所示 由图可知 共缺页9次 其缺页率为9 12 75 当进程分得4个页面是 执行过程中内存页面变化如下图所示 由图可知 共缺页10次 其缺页率为10 12 83 3 FIFO算法的Belady现象 Belady现象 FIFO页面置换算法会产生异常现象 当分配给进程的物理页面数增加时 缺页次数反而增加 原因 根本没有考虑程序执行的动态特性 图5 24FIFO算法的Belady现象 地址越界保护 设置页表长度寄存器 查页表前 先检查页号是否越界 操作访问保护 在每个页表项中增设一存储保护域 用于说明对该页的访问权限 每一个对该页存储的访问都首先比照是否满足该页访问权限的说明 满足则访问 否则报错 5 4 5存储保护 举例 设为每一页表项增加三位 R位表示读权限 W位表示写权限 E位表示执行权限RWE000不可进行任何操作001可以执行 不可以读写010只可以写011100101110111 5 4 6页式管理的优缺点 优点有效解决了碎片问题动态页式管理提供了内存与外存统一管理的虚存实现方式 提高了方便了用户 系统效率缺点要求有相应的硬件支持 如地址变换机构增加了系统开销 如缺页中断置换算法如选择不当 可能会造成抖动 5 5段式与段页式管理 5 5 1段式管理的基本思想段式管理的基本思想逻辑上 程序按内容或过程 函数 关系分成段 每段有自己的名字 一个作业或进程所包含的段对应于一个二维线性虚拟空间物理上 以段为单位分配内存采用虚拟存储技术 只把那些经常访问的段驻留内存 而把那些在将来一段时间内不被访问的段放入外存 待需要时自动调入的方法实现二维虚拟存储器 5 5段式与段页式管理 5 5 2段式管理的实现原理1 段式虚存空间用户程序划分按程序自身的逻辑关系划分为若干个程序段 每个程序段都有一个段名 且有一个段号 段号从0开始 每一段也从0开始编址 段内地址是连续的 段式虚拟地址包括两部分 段号和段式地址 0 116 N 5 5 2段式管理的实现原理 2 段式管理的内存分配与释放在作业或进程执行过程中动态进行分配与释放内存划分内存空间被动态的划分为若干个长度不相同的区域 这些区域被称为物理段 每个物理段由起始地址和长度确定 内存分配以段为单位分配内存 每一个段在内存中占据连续空间 内存随机分割 需要多少分配多少 但各段之间可以不连续存放 2 段式管理的内存分配与释放 段表它记录了段号 段的首 地 址和长度之间的关系 每一个程序设一个段表 段号 0 1 2 段表的作用 作业空间 MAIN 0 0 30K 0 0 0 20K 10K 15K X 1 D 2 S 3 段表 30K 40K 20K 80K 10K 120K 15K 150K 段长 基址 段号 0 1 2 3 内存空间 MAIN 0 X 0 D 0 S 0 0 40K 80K 120K 150K 2 段式管理的内存分配与释放 1 内存中有足够的空闲区满足要求空闲块管理 采用和动态分区管理相同的空闲区管理方法内存的分配算法最先适应法最佳适应法最坏适应法内存回收 采用和分区管理相同的内存回收方法 2 段式管理的内存分配与释放 2 内存中没有足够的空闲区满足要求置换算法 可以采用动态页式管理的淘汰算法FIFO算法LRU算法若需要调入的某段长度大于被淘汰的一段程序或数据的长度 则再淘汰 直到满足要求缺段中断处理过程如图5 29所示 图5 29缺段中断处理过程 5 5 2段式管理的实现原理 3 段式管理的地址变换段式地址变换机构 实现虚地址到物理地址转换 1 段表 扩充内容 实现虚拟存储状态位或内外位 在 不在内存 是否可共享 存取方式 读 写 执行 用于存取保护 访问位 是否访问过 改变位 是否修改过 增补位 固定长 可扩充 图5 30段表 3 段式管理的地址变换 2 动态地址变换段表区 在内存中给出一块固定区域存放段表硬件支持 一对寄存器段表始址寄存器 用于保存正在运行进程的段表的始址 段表长度寄存器 用于保存正在运行进程的段表的长度 Cl Cb 比较 比较 B d 段表 S Cl 快表 物理地址 段表始址寄存器 段表长度寄存器 逻辑地址 L B S L B 地址越界 d L d L 地址映射及存储保护机制 地址越界 地址越界 比较 2 动态地址变换 图5 31段式地址变换过程 3 段式管理的地址变换 取一个指令或数据至少要访问内存两次以上由于段表是驻留在内存的某个固定区域中 而取指令或数据必须经过段表变换才能得到实际物理地址 一次访问段表 以确定所取数据或指令的物理地址另一次是根据地址取数据或指令为了提高速度 采用高速联想寄存器用途 保存正在运行进程的段表的子集 部分表项 特点 按内容并行查找快表项目 段号 段始址 段长度等 5 5 2段式管理的实现原理 4 段的共享与保护由于段是按逻辑意义来划分的 可以按段名访问 因此段式管理可以方便实现内存信息共享与内存保护 段的共享共享 内存中只保留一个副本 供多个用户使用段的共享 只要用户使用相同的段名 在段表中填入相关信息即可实现共享 图5 32段式系统中共字内存副本 5 5 2段式管理的实现原理 4 段的共享与保护段的保护地址越界保护法 利用段表中的段长项与虚拟地址中的段内相对地址比较 若段内相对地址大于段长 再查段表中的 增补位 看是否允许段动态增长 若可以 则继续 否则产生越界中断处理 按出错处理 存取方式控制保护法 优点 内外存统一管理的虚存实现允许动态增加段的长度便于共享便于实现动态链接缺点 需要硬件支持 提高了机器成本有碎片问题每段的长度受内存可用区大小的限制 5 5 3段式管理的优缺点 5 5 4段页式管理的基本思想 段式管理反映了程序的逻辑结构 有利于段的动态增长 段的共享与保护等页式管理有效克服了碎片 提高了存储器的利用率段页式管理结合了二者优点 克服了二者的缺点一般只用于大型机系统中 5 5 5段页式管理的实现原理 1 虚地址的构成逻辑程序按段划分 物理内存按页划分内存划分 按页式存储管理方法内存分配 以页为单位进行分配虚拟地址 由3部分组成 段号S 页号p和页内相对地址d 31 20 19 16 页号P 页内地址W 编号0 15 相对地址0 4096 虚拟地址段号 段内位移 段号 页号 页内位移记做 S P d 段号S 8 15 编号0 2