第四章-存储管理

操作系统原理 第四章存储管理 2 2020 4 12 简介 操作系统中的存储管理主要是指对主存的管理 主存即内存 是指处理机可以直接存取指令和数据的存储器 主存是现代操作系统进行操作的中心 是计算机系统中的一种重要资源 作为系统资源管理程序的操作系统 必须对主存施以有效 精心的管理 多道程序设计技术出现后 对存储管理提出了更高要求 一方面 要使主存得到充分 有效的利用 另一方面要为用户提供方便的使用环境 3 2020 4 12 4 1存储器管理的基本概念 4 1 1存储管理研究的课题计算机的存储设备可以分为三个层次 高速昂贵而易变 断电后信息丢失 的高速缓存和寄存器 数量很少 速度快 价格高且易变的主存储器 RAM 速度较低 价格低廉 但不易变的辅存如软 硬磁盘 光盘等 4 2020 4 12 4 1存储器管理的基本概念 目前关于存储管理的主要研究课题归纳为四个方面存储分配问题 重点是研究存储共享和各种分配算法 记住主存各个位置的状态 哪些空间已分配 哪些空间设置相应的数据结构记录分配 按一定的策略为用户作业分配内存 实施分配 当用户作业申请时 按需分配 修改相应的表格 回收内存 作业完成 退出主存 修改相应的分配表格 地址再定位问题 研究各种地址变换机构 以及静态和动态再定位方法 地址重定位 地址映射 5 2020 4 12 4 1存储器管理的基本概念 存储保护问题 研究保护各类程序 数据区的方法 为多个程序共享内存提供保障 使在内存中的各道程序 只能访问它自己的区域 避免各道程序间相互干扰 特别是当一道程序发生错误时 不致于影响其他程序的运行 通常由硬件完成保护功能 由软件辅助实现 存储扩充问题 主要研究虚拟存储器问题及其各种调度算法 一方面需要提高主存利用率 共享主存 另一方面为用户提供一个远远大于主存的地址空间 6 2020 4 12 4 1存储器管理的基本概念 4 1 2地址再定位1 地址空间和存储空间地址空间 逻辑空间 一个目标程序所限定的地址范围 成为该作业的地址空间 是虚的概念 相对地址 逻辑地址 地址空间的地址都是相对于起始地址0为基准量的 称为相对地址 绝对地址 物理地址 指存储控制部件能识别存储单元的号 存储空间 物理空间 所有内存中实际的物理存储单元的集合 存储空间是一个 实 的物体 7 2020 4 12 4 1存储器管理的基本概念 0 x 0 1MB 8 2020 4 12 4 1存储器管理的基本概念 2 地址的再定位一个逻辑地址空间的程序装入到物理地址空间的时候 由于两个空间不一致 需要进行地址变换 或称地址映射 即地址的再定位 地址再定位有静态再定位和动态再定位两种 静态再定位是在程序执行之前进行地址再定位 通常由装配程序完成 9 2020 4 12 4 1存储器管理的基本概念 例现有一个作业A 它需要20K空间 两次运行分别被装入主存中的不同地址 作业的地址空间 0K 20K 主存 100K 120K 作业的地址空间 0K 20K 主存 120K 140K 10 2020 4 12 4 1存储器管理的基本概念 优点 容易实现 无需硬件支持 只要求程序本身时可再定位的 缺点 程序经地址再定位后就不能再移动了 因而不能重新分配内存 不利于内存的有效利用 程序在存储空间中只能连续分配 不能分布在内存的不同区域 若干用户很难共享内存中的同一程序 如若共享同一程序 则各用户必须使用自己的副本 11 2020 4 12 4 1存储器管理的基本概念 动态再定位是在程序执行期间 在每次存储访问之前进行的 作业在存储空间中的位置是装入时确定的 但在运行时允许 搬家 和附加存储空间 12 2020 4 12 4 1存储器管理的基本概念 优点 在执行过程中 用户程序在内存中可以移动 这有利于内存的充分利用 程序不必连续存放在内存中 可以分散在内存的若干个不同区域 这只需增加几对基址 限长寄存器 每对寄存器对应一个区域 若干用户可以共享同一程序 缺点 需要附加的硬件支持 实现存储管理的软件算法比较复杂 13 2020 4 12 4 1存储器管理的基本概念 4 1 3虚拟存储器概念的引入虚拟存储器的提出VirtualStore VS 1 解决小内存运行大作业问题连续区 分区的管理 分页式管理中 如作业长大于内存的用户区长 将无法运行该作业 因为作业一次全装入主存 在多道环境下 要求内存放入多个作业 问题更为突出 2 用户扩大内存的要求 以便有效地支持多道系统和大型程序的需要由于内存硬件价格贵 因此利用VS 可以从逻辑上扩充主存 14 2020 4 12 4 1存储器管理的基本概念 3 程序的访问局部性时间的局部性 刚刚访问的部分 可能马上还要访问 例如程序中有大量的循环语句 空间的局部性 被访问部分的邻近区域 可能马上就要被访问 程序的顺序性 程序段的互斥性 不是每个程序段在执行时同时都运行到 15 2020 4 12 4 1存储器管理的基本概念 虚拟存储器的定义让用户编程使用的地址范围决定的虚存空间 远远大于实际的内存空间 对用户而言 它是一个比主存大得多的地址空间 可以按它来编程 而不必考虑主存的不足 对OS而言 是用各种表格机构构造的一个虚拟存储器 16 2020 4 12 4 1存储器管理的基本概念 VS的基本实现原理利用表格为用户构造一个虚拟空间 作为实现VS的机构 利用大容量的外存 存放进入VS中的信息 是VS的硬件基础 主存作为VS中的程序和数据得以运行的缓冲区 在内 外存之间信息调度 硬件提供动态地址转换机构 注VS的容量由虚拟地址结构决定 也受外存容量的限制 17 2020 4 12 4 2早期的存储管理 4 2 1单一连续分配每个进程所需的空间分配到主存一块连续区 早期的单道成批处理或个人微机OS或专用OS多用 目的 解决成批作业自动接续问题 不提供共享主存功能 分配方法将主存分为二块连续区 系统区 存放OS和用户区 存放用户程序 系统设置一个界限寄存器 Fenceregister 指出OS区和用户区的界限 当用户程序地址小于边界地址时 产生越界中断 由装入程序每次装入一个作业到用户区 剩余的用户区空间浪费掉 采用静态重定位 18 2020 4 12 4 2早期的存储管理 特点单道运行 独占资源 浪费了内存碎片 资源利用率低 简单 OS可以小到1KB 一般几十KB 不需复杂的硬 软件支持 缺少灵活性 大作业不能在小内存运行 分配给用户作业的空间 19 2020 4 12 4 2早期的存储管理 4 2 2分区分配分区分配是能满足多道程序设计需要的一种最简单的存储管理技术 分区管理法也称界地址存储管理法 通常 按照分区的划分方式 又可分为固定式分区 可变式分区 可再定位式分区和多重分区 1 固定式分区法思想 预先将主存用户区划成大小不等若干分区 分区的个数和长度保持固定 每个分区只装入一个作业 分区的个数等于作业的道数 固定分区是实现多道程序设计最简单的一种技术 20 2020 4 12 4 2早期的存储管理 分区的分配和释放作业都必须规定最大的存储量 OS设立一张分区说明表 指明块号 位置 长度和状态 装入一个作业时 由再定位装入程序按作业的内存需求量在表中找一个够大的未分配分区 用静态再定位方式装入作业 修改状态标志 回收时 将分区状态置0 即释放 21 2020 4 12 4 2早期的存储管理 22 2020 4 12 4 2早期的存储管理 存储保护设立上界寄存器和下界寄存器分别存放当前运行作业的分区最小绝对地址和最大绝对地址 当访问的地址小于上界或下界时产生越界中断 优点可以共享主存 提高主存利用率 程序一次性装入主存 由于静态再定位 程序不能移动 23 2020 4 12 4 2早期的存储管理 缺点分区内部碎片大 浪费内存 例现有四个作业 其作业长度分别为1K 9K 23K 33K 总计长度为66K 为它们分配分区长分别为4K 12K 28K 44K 共占88K 浪费了22K 作业长度大于分区最大长度 无法分配 这种方式适于能掌握作业大小 数量的系统及中型机以上的OS 如IBMOS MFT 任务数固定的多道程序设计系统 24 2020 4 12 4 2早期的存储管理 2 可变式分区法为了解决固定分区的内部碎片问题 在固定分区管理技术上设计了可变分区管理 适用于多道系统 可变式分区法也就是动态划分存储器的分区方法 它是在作业装入和处理过程中建立的分区 并且要使分区的容量能正好适应作业大小 在作业进入系统前 根据作业的大小来申请所需存储容量 然后由系统实施分配 系统为了管理主存分区分配情况 需建立两张表 分别登记已分配区和未分配区的分区容量 位置和状态信息 25 2020 4 12 4 2早期的存储管理 可变分区的分配思想新作业装入主存时 找一个足够大的空闲区 按作业长度划分 剩余仍为一个小空闲区 释放时 与相邻的空闲区合并 26 2020 4 12 4 2早期的存储管理 可变分区管理的数据结构线性表结构OS设立二张表 已分配区表和空闲区表 未分配区表 27 2020 4 12 4 2早期的存储管理 链表结构 一种利用存储分块自身存放信息即分区附加数据集 并由链指针按照一定算法链接起来 空闲区链结构 28 2020 4 12 4 2早期的存储管理 可变分区的管理 分配与回收分配的步骤按作业长度找一个够大的空闲区 划出作业长度 多余仍为空闲区 修改空闲区表 填写已分配区表 释放的步骤查看已分配区表 根据释放的地址 长度 得对应表项 该项状态置0 空白项 将释放区记入未分配表中空项 状态置为可用空间 与相邻区合并 29 2020 4 12 4 2早期的存储管理 合并邻接空闲区有四种情况合并上邻接区 合并下邻接区 上下两邻接区均可合并 上下两邻接区均不可合并 30 2020 4 12 4 2早期的存储管理 可变分区的分配算法最先适应法 firstfit FF 找能满足需求的第一个空闲区 即可分配 剩余部分仍留在空闲区表中 可把空闲区表按地址大小由小到大排列 优点释放时 若有相邻区 易于合并 先分配低地址空间 保留高地址较大的的空间 以备大作业分配 31 2020 4 12 4 2早期的存储管理 最佳适应法 BFBestfit 找能满足作业需要的最小分区分配 将空闲区按长度由小到大排列 即X1 X2 X3 Xn 其中Xi为第i分空闲区长度 S为作业的需要量 则从X1顺序比 直到S Xi 从Xi中分配 若Xn不能分 则失败 如Xi S 剩余的插入合适位置 32 2020 4 12 4 2早期的存储管理 优点平均查到一半时 即可以找到最佳空闲区 若有Xi S 必被选中 保留与S相差大的空闲区 每次分相差小的空闲区 缺点碎片太小 无法利用 分配 回收查找费时 合并不易 要对各空闲区计算最高地址 然后比较 找邻接区 费时 合并后 要插入合适位置也费时 33 2020 4 12 4 2早期的存储管理 最坏适应法 worstfit 每次总是选最大的空闲区分配 将空闲区按长度由大到小排列 X1 X2 X3 Xn 若X1 S 从X1中分X1 S 0 剩余的插入合适位置 X1不够大 失败 优点分配速度快 只比较X1长度 即可确定分配 X1分配后 剩余仍较大 可满足以后的需求 缺点各区都均等地减小 不能满足大作业需要 34 2020 4 12 4 2早期的存储管理 35 2020 4 12 4 2早期的存储管理 3 可再定位式分区分配碎片 内存中无法被利用的小的空闲分区 可再定位式分区分配即浮动分区分配 是解决碎片问题的简单而有效的方法 其基本思想是移动所有被分配了的分区 使之称为一个连续区域 而留下一个较大的空白区 由于程序涉及到基址寄存器 访问内存指令 访问参数表或数据结构 所以一个作业移动位置后 通常无法保证程序在新位置上能够正确运行 为此 应解决程序的可再定位 浮动 问题 36 2020 4 12 4 2早期的存储管理 37 2020 4 12 4 2早期的存储管理 解决程序的可再定位 浮动 问题的方法 使用模块装入程序 将程序的装配模块重新装入到指定位置 并从头开始执行 缺点花费较多的处理机时间 如果程序已经执行了一段时间 必须从头开始 否则将引起混乱 动态再定位技术 当一个作业装入与其地址空间不一致的存储空间时 可在访问指令或数据时 通过再定位寄存器 或称浮动寄存器 来自动修改访问存储器的地址 因此 一个作业再主存中移动后 只需要改变再定位寄存器的内容即可 38 2020 4 12 4 2早期的存储管理 可再定位分区分配算法和固定式 或可变式 分区分配算法基本相同 问题是何时进行靠拢 一般有两种时机的选择当某个分区内的作业一完成 就立即靠拢 这样的靠拢操作是比较频繁的 由于实施程序的移动要花费较多的处理机时间 因此应尽可能减少靠拢操作的次数 在为某一作业请求一个分区时 当时内存没有足够大的空白区 但各空白区之和可以满足该作业存储要求 此时须进行靠拢操作 这样的靠拢次数要少得多 从而可以节省处理机时间 39 2020 4 12 4 2早期的存储管理 分配算法流程图 请求分配一个大小为xKB的分区 有大于xKB的空白区吗 空白区的总和 xKB 执行靠拢操作并修改状态表 此时无法分配 返回一个分区号 分配一个分区并修改状态表 N N Y Y 40 2020 4 12 4 2早期的存储管理 4 多重分区分配通常一个作业由一些相对独立的程序段和数据段组成 如主程序 子程序 数据组等 这些程序段中的每一个在逻辑上必须是连续的 但是相应的各分区不要求是连续的 采用多重分区分配方案 作业可以在其执行期间申请附加的分区 优点 可使存储空间的利用率提高 缺点 作业分段越多 分区越小 存储器过碎 造成没有较大的空白区 实现多重分区要求更多的硬件支持 管理也比较复杂 41 2020 4 12 4 2早期的存储管理 5 分区的保护措施存储保护是为了防止一个作业有意或无意的破坏操作系统或其他作业 通常采用界限寄存器或者存储保护键两种方法 界限寄存器定位寄存器和界限寄存器 利用定位寄存器的值 存储空间首址减去地址空间首址的值 和界限寄存器的值进行存储访问检查 界限寄存器的值存放作业地址空间的大小 上下限寄存器 每次访主存时 其地址值与上限寄存器值 物理地址的最高地址 和下限寄存器值 最低物理地址 比较 若大于上限或小于下限时则中断访问主存 42 2020 4 12 4 2早期的存储管理 上下界寄存器进行存储保护 基址寄存器进行存储保护 43 2020 4 12 4 2早期的存储管理 存储保护键将主存静态分成若干块 一般是等分为1k 2k大小分块 每块都指定一个单独的保护键 保护键由保护字和保护方式组成 保护方式分为写保护 读写保护两种 而保护字由一组代码组成 每个作业赋于一个不同代码并存入该作业的程序状态字中 访问主存时用此代码 钥匙 与保护键进行匹配检查 先进行保护方式检查 若是写保护 则对一切读指令都不进行匹配检查允许访问主存 但对写指令必须进行匹配检查 若是读写保护 则对任何指令都进行匹配检查 匹配检查是用作业代码钥匙与主存的代码锁相比较 若相同则允许访问主存 否则作为访问主存出错被中断 一般系统都将操作系统的程序状态字 PSW 钥匙置为0 它具有万能钥匙之功效 可访问任一主存块 44 2020 4 12 4 2早期的存储管理 45 2020 4 12 4 2早期的存储管理 6 分区分配方案的评价优点对多道程序设计 实现了存储的共享 更有效地使用了处理机和I O设备 从而使系统的吞吐量和作业周转时间得到了相应的改善 高了主存利用率 可变式分区高于固定式分区 可定位式分区更高 实现存储保护的措施比较简单 多重分区分配方案能实现对子数据 程序段的共享 46 2020 4 12 4 2早期的存储管理 缺点 主存仍不能充分利用 存在严重碎片问题 可重定位分区分配除外 不能实现对主存的扩充 作业大小受到主存可用空间的限制 和单一连续分配一样 要求一个作业在执行之间必须全部装入内存 因此在主存中可能包含从未使用过的信息 采用靠拢方法 虽然能解决碎片问题 但有时需移动大量信息 从而损失了处理机时间 除多重分区外 几个共行作业之间不能共享存入主存的单一信息副本 47 2020 4 12 4 3分页存储管理 可再定位 即浮动 式分区分配技术 使用这种分配技术可以消除碎片 使一些零散的空白区汇合成较大的连续的空白区 提高主存的利用率 但是 各作业分区的靠拢花费了较多的处理机时间 并不可取 这是由于我们提出了每个作业占有的存储空间必须是连续的 避开这一要求 就引进了分页存储管理技术 48 2020 4 12 4 3分页存储管理 4 3 1分页原理用户作业地址空间起点与分区的物理位置无关 所以作业的地址空间通常从0开始 分页存储管理就是从逻辑地址空间到物理地址空间的一种变换 即f L S 其中 L S分别表示逻辑地址空间和物理地址空间 页框 物理块 将主存按2n划成位置固定 长度相等的块 称为页框 pageframe 或物理页 如1KB PC机为4KB一页 对页框进行统一编号0 1 2 n 1 称为块号 页框号 页架号 物理页号 绝对页号 页框是分配内存的基本单位 49 2020 4 12 4 3分页存储管理 页面 页 作业的虚拟地址空间也按同样长度分成页面 虚页 虚拟页面 对其统一编号0 1 2 m 1 称为页面号 虚页号 逻辑页号 相对页号 一个作业的逻辑地址空间的所有页面是邻接的 而变换到物理存储空间的各块可以不邻接 逻辑地址空间和物理地址空间的对应关系由称为页面变换表的PMT指出 PMT也简称为页表 50 2020 4 12 4 3分页存储管理 在分页存储管理方式中 系统以页框为单位把主存分给进程 并且每个进程分给的各页框不一定相邻和连续 页表的作用是实现从页号到物理块号的地址映射 每一个进程对应一张页表 一个页表表项的数目等于其所记录的进程逻辑地址空间的页面数 CPU中设立一个页表地址寄存器 例作业A的地址空间为11KB 按4KB分页 分为0 1 2页 51 2020 4 12 4 3分页存储管理 逻辑地址空间 52 2020 4 12 4 3分页存储管理 页面变换表 页面变换表保证了作业的正确执行 53 2020 4 12 4 3分页存储管理 4 3 2地址变换机构1 动态地址变换机构DAT考察计算机系统指令LR1 D2 X2 B2 其中 X2 B2 D2为第二操作数域使用的变址寄存器 基址寄存器和位移量 R1是第一操作数域的通用寄存器 指令格式为图 54 2020 4 12 4 3分页存储管理 指令的第二操作数的有效地址为E2 X2 B2 D2 该指令的有效地址占24位 因此 逻辑地址空间最大可达224 16MB 假定页面大小为4KB 于是逻辑地址空间可达4096个页面 每个页面4096个字节 24位有效地址自然地被划分为两部分 前12位为页号 后12位为页内地址 55 2020 4 12 4 3分页存储管理 动态地址变换机构自动地将所有地址划分为页号和页内地址两部分 利用PMT表将页号代之以块号 得到要使用的物理存储地址 56 2020 4 12 4 3分页存储管理 每个作业都有一个页面变换表 通常各作业的页面变换表放在操作系统的一个工作区中 由页面变换地址寄存器 PMTAR 指出作业的页面变换表的起始地址 当处理机执行一个新作业或恢复一个旧作业时 只要修改PMTAR的内容 使之指向要执行作业的PMT起始地址即可 57 2020 4 12 4 3分页存储管理 操作系统用 0 4KB 块2 块4 块7 4160 PMTAR PMT 页面和块之间的关系 58 2020 4 12 4 3分页存储管理 2 高速页面变换寄存器为了实现从作业地址空间到物理地址空间变换 可采用硬件的高速寄存器来实现 3 联想存储器页面变换表存放在主存 由操作系统实施管理 在作业执行时 每条指令的执行都必须进行地址变换 每条指令必须两次访问存储器 一次把页号变成物理块号 一次进行实际存取所要的数据或指令 增加了指令执行的机器时间 影响了计算机的速度 采用高速寄存器方法 如果作业地址空间较大 所需存储器较多 花费较高 59 2020 4 12 4 3分页存储管理 因此采用一种折衷办法来解决这一矛盾 即把高速寄存器作为DAT的辅助机构来实行地址变换 这些寄存器连同管理它们的硬件构成了一个容量较小的存储器 称之为联想存储器 也称快表 在联想存储器中 存放正运行作业当前最常用的页号和相应块号 具有并行查询能力 60 2020 4 12 4 3分页存储管理 输入寄存器 输出寄存器 61 2020 4 12 4 3分页存储管理 在采用联想存储器的系统中 通常采用 双管齐下 的方针 既按给出的页号检索联想存储器中的相应块号 同时按PMT表进行查找块号 同时进行 如果在联想存储器中 检索到所要块号 立即停止PMT表的查找 利用联想存储器给出的块号访问主存 如果联想存储器检索不到需要的块号 将PMT表查找到的页号以及所对应的块号填入联想寄存器内的空白单元中 如没有空白单元 根据某种规则淘汰一个单元内容后填入 62 2020 4 12 4 3分页存储管理 例设CPU访问内存要200ns 访问快表一次要40ns 命中率为90 求一次访问内存的平均时间是多少 比慢表访问下降了多少 解访问内存的平均时间为 40 200 0 9 200 200 0 1 216 40 256 ns 不用快表 每取一指令或数据要用400ns 则 400 256 400 36 63 2020 4 12 4 3分页存储管理 例CPU访问慢表为100ns 访问快表为20ns 希望把进行一次访问内存存取指令的或数据的时间控制在140ns 求此时快表的命中率 解设命中率为X 列方程 100 20 X 100 100 1 X 14080X 60X 75 所以 命中率至少要75 64 2020 4 12 4 3分页存储管理 4 3 3分页存储管理算法为实现分页储存管理 在软件方面应建立如下表格 并由操作系统实施管理 作业表 JT 整个系统一张表 每个作业在作业表中对应一个表目 包括该作业的页表地址 页表长度和状态信息 当作业调度程序调度到某个作业时 如果存储要求可以得到满足 就在此表上进行登记 当作业轮到处理时 就从此表把页表始址和页表长度送到控制寄存器中 65 2020 4 12 4 3分页存储管理 存储分块表 MBT 整个系统一张表 该表中每一表目对应一个存储块 记录了该块的状态 已分配或空闲 页面变换表 PMT 每个作业一张表 页面变换表 用于该作业的地址变换 该作业有多少页面就有多少表目 表目内记录对应的存储块号 66 2020 4 12 4 3分页存储管理 3600 作业1的PMT 4160 作业2的PMT 3820 作业3的PMT 67 2020 4 12 4 3分页存储管理 请求分配xKB的地址空间 计算所需块数NN xKB 4KB 有N个可用的块 本次无法分配 在作业表中找空表目置页表长度 N 状态 已分配 分配该作业的PMT表 并在作业表中登记该PMT的始址 检查内存分块表 分配N个可用存储块 在每块的状态栏内填入作业序号 再将存储块号填入PMT表 返回 分页存储分配算法流程图 68 2020 4 12 4 3分页存储管理 4 3 4分页存储管理方案的评价分页存储管理方案不必像浮动分区法那样执行费时的靠拢操作 消除了碎片 便于多道程序设计 提高了处理机和主存的利用率 缺点 采用动态地址变换会增加计算机成本和降低处理机的速度 各种表格要占用一定容量的主存空间 而且还要花费一部分处理机时间用来建立和管理这些表格 碎片虽然消除 但每个作业的最后一页一般不能充分利用 存储扩充问题仍然没有解决 69 2020 4 12 4 4请求分页存储管理 4 4 1请求分页原理基本原理将作业的地址空间按同等大小划分成页面 虚页 将主存空间划分成同样大小的页框 实页 将页面不是全部装入主存 而是装入一部分 作业运行时 至少装入一个页面 每次访问的页面如果不在主存中 就从辅存中调入主存 70 2020 4 12 4 4请求分页存储管理 请求分页存储中 必须解决几个问题 1 如果一个作业不把它的整个地址空间同时全部装入主存 那么该作业是否能开始运行并运行一段时间 2 在作业运行一段时间后 必然要访问到没有装入的页面 也就是说 要访问的虚页不在实存 那么 这个问题系统是怎样发现的 3 如果系统已经发现某虚页不在实存 就应将其装入实存 问题是从何处装入 装入到何处 如果实存空间已满怎么办 71 2020 4 12 4 4请求分页存储管理 1 一个作业的地址空间不同时全部装入主存时 这个作业可以开始运行不能运行一段时间 因为作业在运行期间的各个阶段 多数作业只使用全部地址空间的一部分 程序的局部性 顺序执行的指令和线性结构的数据 如数组 它们通常被限定在某一连续区域 一旦某一位置被访问后 那么它附近的位置很快也会被访问 作业被调度投入运行前 通常只装入其虚页0到实存 作业所需其它各页 根据请求而被装入 这就保证了一个作业在运行前可以不必装入该作业的全部地址空间 72 2020 4 12 4 4请求分页存储管理 2 在PMT中增加一个状态位 规定该位为0表示该页已装入主存 该位为1表示该页不在主存 当地址变换机构检测到虚页的状态位为1时 表示该页不在主存 规定由硬件产生缺页中断 转入中断处理程序 虽然这不是用户程序的错误 但它是属于程序中断 73 2020 4 12 4 4请求分页存储管理 地址空间 74 2020 4 12 4 4请求分页存储管理 3 当发现虚页不在实存时 引起缺页中断 利用中断处理程序完成该页的装入 中断处理程序把所需页面装入实存后 修改PMT的状态位 然后重新执行该指令 将某一页从实存移到辅存称为 出页 从辅存调入实存称为 入页 入页和出页的操作称为 分页 操作 在请求分页系统中 从实存中刚刚移走某个页面后 根据请求马上又调入该页 这种反复进行入页和出页的现象称为 抖动 也叫做系统颠簸 它浪费了大量的处理机时间 所以应尽可能避免 抖动 的发生 75 2020 4 12 4 4请求分页存储管理 执行一条指令 形成有效地址 计算页号 该页在实存吗 取数据完成该指令 取下一条指令 缺页中断入口 有空闲的实页吗 取出保存的页号 找出磁盘地址 入页 修改PMTMBT表 重新执行被中断的指令 出页 修改PMTMBT C 1 复制到辅存 硬件 软件 Y Y Y N N N 76 2020 4 12 4 4请求分页存储管理 4 4 2页面置换算法通常一个置换算法的效能与作业运行过程中访问地址空间的变化规律密切相关 而这个规律难以预测 因此 人们对不同类型的作业 从不同角度 提出了许多不同的置换算法 1 先进先出算法 First inFirst out FIFO 先进先出算法的基本思想是 总是淘汰那些驻留在主存时间最长的页面 即先到主存的页面先被淘汰 理由是 最早调入主存的页面 其不再被访问的可能性最大 这种算法实现起来比较简单 该算法只是在按线性顺序访问地址空间的情况下才是理想的 否则效率不高 77 2020 4 12 4 4请求分页存储管理 2 替换指针 指向最老的页 6 替换指针 指向最老的页 78 2020 4 12 4 4请求分页存储管理 2 最近最久未用置换算法 LRU 基本思想 如果某一页被访问了 那么它很可能马上又被访问 反之 如果某一页很久没有被访问 那么最近也不再会被访问 这种思想来源于程序设计的局部化程度 实质是 当需要置换一页时 选择在最近一段时间最久未用的也予以淘汰 实现这种技术 是通过周期性地对 引用位 进行检查 并利用它来记录一页面自上次被访问以来所经历的时间t 淘汰时选择t最大的页 最近最久未用置换算法简称LRU LeastRecentlyUsed 算法 它能够比较普遍地适用于各类类型的程序 但是实现起来比较困难 79 2020 4 12 4 4请求分页存储管理 3 LRU近似算法需要在存储分块表MBT 或页表PMT 中设一 引用位 当存储分块表中的页被访问时 该位由硬件自动置 1 而由页面管理软件周期地 设周期为T 把所有应用位置 0 这种算法比较简单 易于实现 缺点是 周期T的大小不易确定 另外 如果缺页中断刚好发生在系统对所有引用位重置 0 之后 则几乎所有块的引用位为 0 因此也有可能把常用的页淘汰出去 80 2020 4 12 4 4请求分页存储管理 入口 替换指针前进一步指向下一存储块 其引用位 0 选择该页淘汰 返回 置引用位 0 LRU近似算法的流程 81 2020 4 12 4 4请求分页存储管理 替换指针 6 替换指针 LRU近似算法例 82 2020 4 12 4 4请求分页存储管理 4 第二次机会页面替换算法思想 为了避免FIFO可能会把经常使用的页替换出去的问题 我们可以对它做一个简单的修改 对最老页面的R位进行检查 如果R位是0 那么这个页既老又没用 应该被立刻替换掉 如果是1 就清除这个位 把这个页放到页链表的尾端 修改它的装入时间让它就像刚装入的一样 然后继续搜索 83 2020 4 12 4 4请求分页存储管理 A 0 B 3 C 7 D 8 E 12 F 14 G 15 H 18 第一个装入的页 最近装入的页 a 页面按先进先出的顺序排列 A 0 B C 7 D 8 E 12 F 14 G 15 H 18 A被像新装入的页面一样对待 b 在时间20发生页面故障并且A的R位已经设置时的页面链 20 第二次机会页面替换算法 84 2020 4 12 4 4请求分页存储管理 5 时钟页面替换算法 CLC算法 把所有的页面保存在一个类似钟表表面的环形链表中 有一个表针指向最老的页面 在发生缺页中断时 该算法首先检查表针指向的页面 如果它的R位是0就淘汰掉这个页 并把新页插入这个位置 然后把表针前移一个位置 如果R位是1就清除R位并把表针前移一个位置 重复这个过程直到找到一个R位为0的页为止 A B C D E F G H I J K L 时钟页面替换算法 85 2020 4 12 4 4请求分页存储管理 4 4 3性能分析请求分页存储管理方案消除了对主存实际容量的限制 能使更多的作业按多道同时执行 从而提高了系统效率 由于页面的调入 调出要增加I O的负担 而且影响系统的效率 早期的计算机系统中 为扩充主存的容量 采用请求分页存储管理方案实现虚拟存储系统 尽管要增加系统开销 也是必要的 但是 在今天硬件成本急剧下降 存储技术不断进步的形势下 是否仍采用请求分页存储管理是一个值得讨论的问题 86 2020 4 12 4 4请求分页存储管理 为尽可能地减少缺页中断的次数 应从程序设计的质量 页面的大小 主存的容量以及页面置换算法等几方面考虑 程序设计的质量主要指程序局部化程度 包括时间局部化和空间局部化 时间局部化是指一旦某个位置 数据或指令 被访问了 它常常很快又要再次被访问 可通过循环 经常用到的变量和子程序等程序结构来实现 空间局部化是指一旦某个位置被访问到 那么它附近的位置很快也要用到 可通过尽量采用顺序的指令列 线性的数据结构来实现 设计请求分页存储系统 页面大小也是重要参数 87 2020 4 12 4 4请求分页存储管理 提供虚拟存储系统之后 每个作业只要分到一块主存空间就可以执行了 从表面上看 这增加了可同时运行的作业数 但实际上是低效的 一个作业的执行所产生的缺页中断的次数是存放页面的实际存储容量的函数 当主存容量增加时 缺页中断次数减少 到一定程度后 中断减少次数不明显 试验分析表明 对所有程序来说 要使其有效地工作 它在主存中的页面数应不低于它的总页面数的一半 P121图4 26存储容量与缺页中断次数的关系 88 2020 4 12 4 4请求分页存储管理 现在讨论运行的程序和页面置换算法的关系 例设页面走向为P 4 3 2 1 4 3 5 4 3 2 1 5 主存容量M 3 置换算法采用FIFO P行表示页面走向 M行表示主存页面号 标 表示新调入页面 加圆圈表示下一时刻被淘汰 F行表示是否引起缺页中断 缺页次数F 9 缺页率f 9 12 75 89 2020 4 12 4 4请求分页存储管理 例设页面走向为P 4 3 2 1 4 3 5 4 3 2 1 5 主存容量M 4 置换算法采用FIFO P行表示页面走向 M行表示主存页面号 标 表示新调入页面 加圆圈表示下一时刻被淘汰 F行表示是否引起缺页中断 缺页次数F 10 缺页率f 10 12 83 90 2020 4 12 4 4请求分页存储管理 例设页面走向为P 4 3 2 1 4 3 5 4 3 2 1 5 主存容量M 3 置换算法采用LRU P行表示页面走向 M行表示主存页面号 标 表示新调入页面 加圆圈表示下一时刻被淘汰 F行表示是否引起缺页中断 缺页次数F 10 缺页率f 10 12 83 91 2020 4 12 4 4请求分页存储管理 例设页面走向为P 4 3 2 1 4 3 5 4 3 2 1 5 主存容量M 4 置换算法采用LRU P行表示页面走向 M行表示主存页面号 标 表示新调入页面 加圆圈表示下一时刻被淘汰 F行表示是否引起缺页中断 缺页次数F 8 缺页率f 8 12 67 92 2020 4 12 4 4请求分页存储管理 4 4 4请求分页存储管理方案的评价请求分页存储管理保留了分页存储管理的全部优点 特别是它解决了消除碎片的问题 优点提供了大容量的多个虚拟存储器 作业地址空间不再受实存容量的限制 更有效地利用了主存 一个作业的地址空间不必全部同时都装入主存 只装入其必要部分 其它部分根据请求装入 或者根本就不装入 错误处理程序等 更加有利于多道程序的设计 从而提高了系统效率 方便了用户 特别是大作业用户 93 2020 4 12 4 4请求分页存储管理 缺点 为处理缺页中断 增加了处理机时间的开销 即请求分页系统是用时间的代价换取了空间的扩大 可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动 为防止系统抖动所采取的各种措施会增加系统的复杂性 94 2020 4 12 4 5分段存储管理 对于模块化程序和变化的数据结构的处理 以及不同作业之间对某些公共子程序或数据块的共享等问题的解决 都存在着较大的困难 程序人员一般都希望把信息按内容和逻辑关系分成段 每个段都有自己的名字 且可以根据名字来访问相应的程序段或数据段 95 2020 4 12 4 5分段存储管理 4 5 1分段原理 016003400100060 容量 存取权限 状态 始址 3460 3800 4000 96 2020 4 12 4 5分段存储管理 在分段存储管理系统中 可以用类似于分页管理用过的地址变换机构 实现分段管理的地址变换 使用的是段变换表SMT 它把作业地址空间变换为物理存储空间 作业地址空间的段与主存中的段大小相等 地址变换是在作业执行过程中由硬件自动完成的 97 2020 4 12 4 5分段存储管理 请求访问S段中的B单元 段S在实存吗 B S段容量 在访问权限之内 置访问位为1 若为写访问 则置改变位为1 求段的始址L 加上段内地址B 便得实存地址A L B 返回访问地址 保护中断 越界中断 缺段中断 由处理机产生 由分段管理机构实现 98 2020 4 12 4 5分段存储管理 4 5 2段变换表作业的地址空间被划分成若干段 每个段定义一个完整逻辑信息 从0开始编址 分页的作业是单一线性地址空间 分段作业的地址空间就是二维的 由 段名 段内地址 两个部份组成 页 是信息的物理单位 段 是信息的逻辑单位 从形状来说 页面大小固定 段的长度却不定 99 2020 4 12 4 5分段存储管理 从透明度上看 页面对于用户是不可知的 它仅仅用于对主存的管理 分段则对用户是可见的 分段可在编程或编译时即已确定和划分 分页管理实现单段式虚拟存储系统 而分段存储管理实现多段式虚拟存储系统 指令和数据的单元地址均由两部分构成 一是表示段名的段号S 一是段内位移量W 即段内地址 段与段之间不再连续 100 2020 4 12 4 5分段存储管理 地址转换过程由控制寄存器找出正在运行作业的段表首址 利用有效地址中段号2作为进入段表的索引 得到该段在主存中的首址6K 根据段内位移W与段长比较结果 判断是否有越界 若有产生越界中断 取段保护方式检查指令是否符合存取方式 若不符合产生保护中断 将段内位移量W 100与段首址6K相加得出主存的物理地址6244 按物理地址6244访问 101 2020 4 12 4 5分段存储管理 地址转换过程如图所示 102 2020 4 12 4 5分段存储管理 4 5 3分段存储管理方案的评价优点消除了碎片 通过靠拢可移动任何段的位置 修改SMT表的起始地址 从而可将零散的空白区合并成一个较大的空白区 用于装入某一较大的段 提供了大容量的虚存 允许动态增加段的长度 容易处理变化的数据结构便于动态装入和链接 当两个或两个以上的作业要使用同一子程序时 在实存上就要有两个或两个以上的程序副本 造成浪费 通过分段管理和动态连接 可以做到几个作业共享一个程序 便于实现存储保护 103 2020 4 12 4 5分段存储管理 作业1的SMT 作业2的SMT 两个作业对SQRT的共享 104 2020 4 12 4 5分段存储管理 缺点进行地址变换和实现靠拢操作要花费处理机时间 为管理各分段 要设立若干表格 提供附加的存储空间 在辅存上管理可变长度的段比较困难 段的最大长度受到实存容量的限制 会出现系统抖动现象 105 2020 4 12 4 6段页式存储管理 用分段方法来分配和管理虚存 用分页方法来分配和管理实存 在段页管理系统中 每一段不再占有连续的实存空间 而被划分为若干个页面 段页存储管理实际上是对页面进行分配和管理的 因此有关段的靠拢 辅存管理以及段长限制等问题都得到很好的解决 而分段的优点 如允许动态扩大段长 分段的动态链接 段的共享 段的保护措施等却被保留下来 这一存储管理技术在大 中型计算机中已获得了广泛的应用 106 2020 4 12 4 6段页式存储管理 4 6 1段页式存储管理的实现一 实现原理1 一个作业的地址空间被分成若干段 每段又被分成若干固定大小的页面 2 段末部分未占满一页的也算一页 如图所示 这就解决了外零头问题 107 2020 4 12 4 6段页式存储管理 3 段页式地址结构是由段号S 页号P 页内地址W三部分组成 这种地址结构如下图所示 4 段号长度ns 确定了作业的最大段数2ns 页号P的占位数np确定了每个分段的最大页数为2np 而段内位移W的占位数nw确定了每页的最大容量2nw 例IBM370系统中 最多有256段 ns 8 每个分段最多16页 np 4 每页最大4K nW 12 108 2020 4 12 4 6段页式存储管理 5 系统为每一个作业建立了一张段表 并为每个段建立了一张页表 段表的地址部分指向相应页表的首址 L0 L3 页表 109 2020 4 12 4 6段页式存储管理 二 段页式的地址转换过程1 由控制寄存器中查出段表起始址 2 根据段表首址及虚地址中段号S查段表 并根据段描述符知相应段信息 3 若段不在主存产生缺段中断 4 若操作不符存取方式 产生违例中断 5 由页号与页表大小比较 若页号超过页表长度 则产生越界中断 6 由页表始址及页号查页表