第4章_存储管理

第4章存储器管理 存储管理指操作系统中的内存管理部分 任务是 记录哪些内存区域在使用 哪些空闲在进程需要时为进程分配内存 使用完毕后释放内存已被进程使用的内存区域如何保护在内存已无足够空间支持进程运行时 如何进行内外存的信息交换 存储器的功能是保存数据 存储器的发展方向是大容量和小体积 如 内存在访问速度方面的发展 DRAM SDRAM DDRAM RDRAM等 由于价格的一路走低 现在普通个人机的内存也达到了GM 但程序的增长速度和内存容量的增长速度几乎一样快帕金森定律 存储器有多大 程序就有多大 所以 即使是现代的计算机系统 存储容量极大 速度也飞快 内存管理的重要性丝毫没有削弱 对于一个单用户 单任务的操作系统的实现相对非常简单 支撑这种系统甚至不需要任何存储保护的硬件 在最严重的情况下即使内存崩溃也不会引起严重后果 对于一个多用户 多任务的操作系统的实现就复杂的多 支撑这种系统必需要有存储保护的硬件 单靠软件是无法胜任的 在要求具有高可靠性的条件下 内存崩溃会引起严重的后果 4 1程序的装入和链接的有关概念 用高级 汇编语言上机步骤 编译 链接 装入 编辑 得到如test cpp a asm等源文件 重定位 可执行文件平时驻留在外存上 需要执行时作为作业首先装载到内存 这种可执行文件在外存与内存格式一样吗 一样 意味着OS只要读入内存即可 绝对装入 所以 象JMPL1指令在变成可执行代码后 该指令的地址场的数据是固定的 这就意味该程序只能放在固定的地方 load 在多任务下OS无法保证执行程序在同一个位置 所以比如下次装在1000开始 一 程序的装入 重定位 可执行文件平时驻留在外存上 需要执行时作为作业首先装载到内存 一样 意味着OS只要读入内存即可 绝对装入 所以 象JMPL1指令在变成可执行代码后 该指令的地址场的数据是定 这就意味该程序只能放在固定的地方 一 程序的装入 重定位 可执行文件平时驻留在外存上 需要执行时作为作业首先装载到内存 一样 意味着OS只要读入内存即可 绝对装入 不一样 意味着OS只要读入内存时需要对地址场部分做调整 可重定位装入 该工作有OS中专门的程序负责 一般称为装载 装入 加载 程序 方法 执行的目标码相对与0编址 涉及到地址的操作指令地址场称为一个浮动项 在目标码文件的头上有一个浮动项说明表 表中给了浮动项的个数 每个浮动项在文件中的位置 相对于0的偏移量 OS的装载程序根据这些信息将本次分配的内存地址 浮动项的内容 浮动项的位置中 一 程序的装入 例 头部分 例 200 2 装入 1 头部分由OS读入 3 OS根据读入的头对内存浮动项装配 头部分 例 200 2 装入 1 头部分由OS读入 3 OS根据读入的头对内存浮动项装配 头部分 例 200 2 装入 1 头部分由OS读入 3 OS根据读入的头对内存浮动项装配 装入后 进程整体可以移动吗 动态运行装入方式 把装入模块装入内存后 并不立即把装入模块中的相对地址 逻辑地址 转换为相对地址 绝对地址 只有在执行的时候才把逻辑地址转换为绝对地址 通常需要重定位寄存器支持 CPU执行过程中的地址都是内存的物理地址 装入方式汇总 绝对装入方式可重定位装入方式动态运行时装入方式简单分析比较 4 1 2程序的链接 源程序经过编译后 可能会得到一组目标模块 各个模块都有自己的独立空间 从执行的角度看这些模块又是一个整体 各个模块所涉及的地址最终都要合并为统一的地址 静态链接 将一个程序运行中所有的目标文件 所需要的库文件等链接成一个可执行模块 对多用户 多任务系统显然有冗余 比如用户用sin x 则目标代码中都有这部分代码 装入到内存则也都有这部分代码 二 程序的链接 静态链接处理后将多个目标模块合并成为一个整体 装入时动态链接合并成为一个整体的过程在装入内存的时候才执行 在加载到内存之前各个模块仍然分离 运行时动态链接程序在执行过程中根据需要把各个模块链接起来 不需要的模块可以仍然留在外存上 链接方式汇总 静态链接方式装入时动态链接方式运行时动态链接方式简单的比较 4 2连续分配存储管理方式 因为程序的执行是根据指令计数器顺序执行 在执行本指令时 它已是下条指令的位置 跳转指令会自动置为跳转的目标地址 所以决定了程序必须占有连续的一段存储区 连续分配是指为一个用户程序分配一个连续的内存空间 4 2 1单一连续分配 1 内存分为两个区域 系统区 用户区 应用程序装入到用户区 可使用用户区全部空间 特点 适用于单用户 单任务的OS MS DOS的分布 2 静态与动态重定位静态重定位 在程序装入内存时由OS进行浮动项的定位此后不在变化 动态重定位 在程序装入内存时不进行装配 一般直接将程序装入内存 定位问题由系统提供的硬件解决 所以 前提是动态重定位问题需借助于硬件支持 否则无法解决 在为单用户 单任务设计的系统中一般不会有此硬件 如Intel8080 8086 8088 4 2 2固定分区分配 1 把内存划分为若干个固定的连续分区 分区大小相等 只适合于多个相同程序的并发执行 处理多个类型相同的对象 分区大小不等 多个小分区 适量的中等分区 少量的大分区 根据程序的大小 分配当前空闲的 适当大小的分区 分配策略 当作业到达时 选择适合作业要求的最小空闲区分给作业 若该分区不空 让其在该分区队列中等待 为了充分利用存储器 系统只维持一个等待存贮器的队列 任何时候 只要有一个分区变为空闲 队列中的一个作业就可装入运行 多输入作业队列 单输入作业队列 这种操作员在清晨设置好 以后不能再修改的固定分区的存储系统 曾经在IBMOS 360大型机上运行了许多年 多输入作业队列 单输入作业队列 管理 采用分区表 记录分区的大小和使用情况 4 2 3动态分区分配 一 分区分配的数据结构 分区表可同时记录空闲和占用情况 也可用两张表分别记录空闲 空闲分区表 与占用 使用分区表 表项数目随着内存的分配和释放而动态改变 对顺序组织 表容量就决定了分区的最大个数 用分区表记录使用情况 链表组织 顺序存储 二 分区分配算法分区分配算法 寻找某个空闲分区 其大小需大于或等于程序的要求 若是大于 则将该分区分割成两个分区 其中一个分区为要求的大小并标记为 占用 而另一个分区为余下部分并标记为 空闲 分区的先后次序通常是从内存低端到高端排列 分区释放算法 注意需要将相邻的空闲分区合并成一个空闲分区 依寻找空闲分区的方法分成 1 首次适应法 first fit 按分区的先后次序 从头查找 找到符合要求的第一个分区 特点 该算法的分配和释放的时间性能较好 较大的空闲分区可以被保留在内存高端 但随着低端分区不断划分而产生较多小分区 每次分配时查找时间开销会增大 3 最佳适应法 best fit 找其容量与要求最接近的空闲分区 特点 从个别来看 外碎片较小 但从整体来看 会形成较多外碎片 较大的空闲分区可以被保留 另外 为了能较快的定位空闲块 所以空闲分区表若以链表方式组织 则表应按空闲区大小递增排列 因此 在释放一个占用区时 应按区大小插入链中并可能有区合并 此时合并比较麻烦 2 下次适应法 next fit 按分区的先后次序 从上次分配的分区起查找 到最后分区时再回到开头 找到符合要求的第一个分区 特点 该算法的分配和释放的时间性能较好 使空闲分区分布得更均匀 但较大的空闲分区不易保留 4 2 4动态重定位分区分配 在多任务前提下 分配一个区后大部分情况下都是有剩余零头的 因此在一个新任务到达时 就有可能零头分区的和超过新任务要求的分区 但每一个空闲区容量都不够 一 紧凑将各个占用分区向内存一端移动 使各个空闲分区聚集在另一端 然后将各个空闲分区合并成为一个空闲分区 问题 紧缩后程序如何重新执行 没有重定位硬件支持是无法实现的 二 动态重定位 4 2 5PC微机中的存储管理 实方式 1 重定位机构四个段寄存器CS DS ES SS 每个16位 段大小 64K 16位表示段内地址 逻辑地址 段址 段内偏移物理地址 段地址左移4位 偏移 20位物理地址若程序不超过64K 可以写成COM格式的可执行文件 2 DOS存储管理接口通过DOS功能调用INT21H 涉及三个调用号 存储分配 48H 释放 49H 和改变分区大小 4AH 3 DOS存储管理数据结构与算法 1 存储分配以16字节为一个单位 称为节 所以最小分配单位是1节 2 内存格式 看成链表 链首指针 由DOS保存 给出了第一个内存结点位置 段地址 内存结点格式如下 tag 1字节 值为 M 或 Z 其中Z表示为链中最后一块 psp 2字节 psp在DOS中称为程序段前缀 占100H的字节 作用同OS中的PCB 这里记占用该内存的进程的PSP地址 若为0为空闲 size 2字节 内存块大小 以节为单位 保留部分 11字节 这样内存块的头正好1节 一个内存块的字节数为 size 1 16 3 有关算法讨论 B 若要将p所指的内存块分配出去x节 xtag p tag 构造分出的新块数据q size p size x 1 q psp 0 c p size x 修改原块数据p tag M p psp 当前运行进程的PSP地址 C 49H调用 参数 ES寄存器 待释放的内存段地址 p psp 0 D 48H调用 参数 BX申请量返回 成功 AX分配得到的段地址不成功 BX 内存中最大的内存块容量AL 08 AH 0 开始 maxsize 0firstblock NULLp DOS首块内存指针 p tag M 或 Z AL 07 格式错 返回 q p p psp 0 q tag Z p q 1 q size p tag M 或 Z C D A p q 1 q size q tag Z p tag M 或 Z p psp 0 q size p size 1q tag p tag n y q size maxsize n maxsize q size y q size 申请量 firstblock q firstblock NULL y y n n D B p firstblock p NULL y AL 08 容量不够 BX maxsize n 返回 申请量 p size n q p size 1 pq size p size 1 申请量p size 申请量q psp 0 q tag p tagp tag M p psp 当前DOS的PSP地址 y AX p 1 结论 DOS中的存储管理的原理在课程中都有体现在实现时又不拘于基本的方法 链 释放空间 对换 1 引入 多个程序并发执行 在内存容量不够时 将暂时不能执行的进程 阻塞或就绪 放到外存 从而腾出内存空间 为了装入新进程 处理保存在外存中而目前到达就绪状态的进程 目的是加快已有进程的推进速度等 交换单位为整个进程的地址空间 常用于多道程序系统或小型分时系统中 与分区存储管理配合使用 又称作 对换 或 滚进 滚出 2 原理 暂停执行内存中的进程 选择一个处于阻塞 就绪 的进程 将它的整个进程的地址空间保存到外存的交换区中 在适当的时候 需将外存中由阻塞变为就绪的进程的地址空间读入到内存中 并将该进程送到就绪队列 3 特点 增加并发运行的进程数目 但换入和换出的控制增加处理机开销 4 外存考虑的问题 减少交换中传送的信息量 特别是对大程序 对外存交换区空间的管理不同于文件系统的管理思路 读写效率是首要的 空间的利用率次要 如采用SISC高速硬盘 设置专用对换区甚至考虑添加专有硬盘 在对换区中 进程映象一般使用连续的磁盘块暂存 总结上述几种内存管理方式 单一连续分配方式固定分区分配方式动态分区分配方式可重定位分区分配方式 进程必须整体进入内存且必须连续 共同的特点是 吞吐量低 不灵活 存储空间浪费 紧凑代价大 4 3分页存储管理方式 连续分配的问题 形成许多碎片紧凑带来开销 为解决以上问题 多任务的操作系统现在大多不在用连续分配的方式管理内存 而采用页式 段式或段页式的方式管理内存 目前市场上商业的操作系统大都采用了页式管理 硬件CPU常提供了多种支持 如Intel从80286开始 CPU就开始支持页式 段式或段页式 一个操作系统只能使用其中的一种 打破了原来要求进程连续存储于内存的要求 一 原理 例 16个字节内存 逻辑上分成两组 称为两个页 每页8字节 一 原理 例 16个字节内存 逻辑上分成两组 称为两个页 每页8字节 地址0100可理解为0页 页内地址为4 地址1101可理解为1页 页内地址为5 这样 一个物理上的一维地址在逻辑上成为了二维地址 页号 页内地址 因为是人为的划分 同样问题 也可以看成4页 每页4字节 页号为高二位 00 01 10 11 页内地址低二位 00 01 10 11 在页式管理中 将程序的逻辑地址空间分成页 Page 物理内存划分为固定的同样大小的页框 pageframe 程序加载时 分配其所需的全部页 这些页不必连续 固定 一个计算机系统的内存容量是固定的 一个页的容量在硬件设计时也是确定了的 二 程序装载在装入一个程序时 需找空闲页框 OS要将这些页框分配给装入的进程 进程地址空间的每个页占用一个页框 页框不要求连续 会出现什么新问题出现 三 页面管理中所需要的数据结构1 页框使用表 整个系统一张 描述物理内存空间的分配使用状况 组织 顺序 链表等都可以 2 进程页表 每个进程一张 给出了逻辑页号与物理页号的映射关系 3 请求表 整个系统有一张请求表 描述系统内各个进程页表的位置和大小 给出的是系统中所有进程的页面表地址 4 当前运行进程的进程页表地址 一般用一个称为页表寄存器的寄存器存储 在进程切换时 修改该寄存器 注意 以上术语除2 比较一致外 其它的并不统一 内存 1000 1001 1010 0 0 0 1 0 1 1 页框使用表 1000 进程id 10 32 100 11 请求表 页表地址 逻辑页号 物理页框 进程11的进程表 四 页面大小的选择通常几KB到几十KB 比较典型的是4K 8K 较小的页面 减小内碎片 但加大页表的长度 从而形成新的开销 较大的页面 减小页表的长度 加大内碎片 管理开销小 分页方式下是不是可以完全排除存储空间浪费现象 页面的大小是越大越好 还是越小越好 各自有什么缺点 五 地址变换机构支持逻辑上连续的目标程序在物理上已经不能保证连续 因此指令计数器从一个页到另一个页按PC的实方式就不能正确处理了 所以 支持页式管理的机器硬件上都有一套地址变换机构完成逻辑地址到物理地址的变换 任何改进往往可以分为两种情况 1 同样条件下的改进2 不同条件下的改进 六 基本地址变换机构 PC或地址场中的 逻辑地址 4 1 5 9 进程页表 越界中断 考虑这样一个问题 在硬件支持下 程序执行性能和传统的有变化吗 执行效果等价吗 执行速度会下降吗 每次内存操作需要两次访问内存 必然导致执行速度下降 对绝大部分系统 页表是利用内存存储的 因此进行一次内存操作需要两次访问内存 第一次读页表 第二次访问数据 如能将页表装在寄存器中访问就快得多 但如果将全部放在寄存器 则寄存器成本大的无法忍受 所以采用一种具有并行查找功能的 联想存储器 根据程序局部性原理 将页表的一部分放在里面 联想存储器的个数一般在8到32个 超过32个效果并不明显 七 具有快表的地址变换机构 联想存储器是什么东西 越界中断 八 两级和多级页表 现代计算机系统 CPU都支持非常大的逻辑地址空间 32 64位的地址空间 这样页表非常大 如果逻辑地址宽度为32位 假设页面大小为4K 212 页表项达1M 220 之多 每个页表项为3个BYTE 仅页表项就要占用3MB的连续内存空间 解决方法 两级页表当前需要的页表放在内存 其余的暂存于磁盘 1 两级页表结构 32位 第0页页表 第1页页表 1 2 4 页表 页框 内存 物理地址 0 5 页框地址 页目录地址寄存器 页目录 每个进程1个 目录位移 页内位移 页内地址 数据存取需通过3次访问内存 2 多级页表对于64位字长的机器 即使采用两级页表 进程表的项数仍然很大 例如SUN的SPARC处理器 支持3级页表 而Motorola的68030处理器甚至支持4级页表 九 反置页表 本次整理到此为止 以上方法 每个进程一张页表 页表按照进程的逻辑地址顺序排序 内容为物理块号 页框号 反置页表则按物理块号的顺序排序 内容为隶属的进程id及其页号 实例 IBMAS 100 IBMRISCSYSTEM6000等 在利用反置页表进行地址变换时 是利用进程id和页号 检索反置页表 实际上可利用联想存储器来检索 分页管理的方法 提高内存的利用率 对程序员是透明的 分段管理的方法 满足了程序员在编程和使用上的要求 适应软件开发上的要求 将程序的地址空间划分为若干个段 segment 程序加载时 分配其所需的所有段 内存分区 这些段不必连续 物理内存的管理采用动态分区 需要CPU的硬件支持 4 4分段存储管理 一 特点 1 方便编程按逻辑关系划分段 有独立的段名 逻辑地址均从0开始 程序通过分段 segmentation 划分为多个模块 如代码段 数据段 共享段 可以分别编写和编译 2 分段共享 可以按段为单位来进行共享3 分段保护 可以针对不同类型的段采取不同的保护4 动态链接 通过动态链接进行代码共享5 动态增长 二 段式管理的数据结构 进程段表 每个进程一张 描述组成进程地址空间的各段系统段表 系统内所有占用段空闲段表 内存中所有空闲段 可以结合到系统段表中 三 地址划分例 32位 后16位代表段内地址 每段64K 前16位代表段号 有64K个不同的逻辑段 如何划分取决于机器硬件设计 比如后半部分17 前15 则每个段最大可达128K 不同段最多为32K 三 段表 由段基址和段长组成 四 地址变换机构类似于页的变换 越界 8292 主存 存取一个数据访内存二次 五 分页和分段的主要区别 1 页是物理单位 而段是逻辑单位 分页是出于系统管理的需要 分段是出于用户应用的需要 因此 一条指令或一个操作数可能会跨越两个页的分界处 而不会跨越两个段的分界处 2 页大小是系统固定的 而段大小则通常不固定 3 逻辑地址表示 分页是一维的 各个模块在链接时必须组织成同一个地址空间 而分段是二维的 各个模块在链接时可以每个段组织成一个地址空间 一个模块 甚至一个子程序都能作为一个段 取决于编译如何处理 4 通常段比页大 因而段表比页表短 可以缩短查找时间 提高访问速度 六 共享 六 共享 段页式存储管理方式 结合分段和分页的优点 一 基本原理段内分页管理 逻辑地址 二 各种表格 每个进程一张段表 段表寄存器给出了当前运行进程的段表地址 进程的每个段都有一张该段的分页表 三 地址变换机构 存储一次数据三次访存 段表始址 段表长度 段表寄存器 逻辑地址 段超长 页表 段表 4 5虚拟存储器 目前各种存储器管理方式 共同的特点是要求将一个作业全部装入内存才能运行 因而难以适应 1 作业的尺寸大于实际内存的容量 2 有大量的作业等待运行 但实际内存容量不足只能装入很少一部分 解决此类问题 引入了虚拟存储 一 程序局部性原理 1 局部性原理 程序在执行过程中的一个较短时期内 所执行的指令地址和指令的操作数地址 分别局限于一定区域 表现为 时间局部性 即一条指令的一次执行和下次再执行 一个数据的一次访问和下次再访问都集中在一个较短时期内 空间局部性 即当前指令和邻近的几条指令 当前访问的数据和邻近的数据都集中在一个较小区域内 4 5虚拟存储器的引入 2 局部性原理的体现程序在执行时 大部分是顺序执行的指令 少部分是转移和过程调用指令 过程调用的嵌套深度一般不超过5 因此执行的范围不超过这组嵌套的过程 程序中存在相当多的循环结构 它们由少量指令组成 而被多次执行 程序中存在相当多对一定数据结构的操作 如数组 往往局限在较小范围内 二 虚存的含义在一个操作系统下 如果不要求用户程序实际占用的物理地址空间一定要大于或等于用户程序的逻辑地址空间 而且这种功能的实现对用户来说是透明的 则称该操作系统实现了虚拟存储管理技术 相应的用户进程空间称为虚存空间或虚地址空间 其大小由指令的有效地址的宽度决定 在虚拟存储管理下 用户的逻辑地址空间可远远大于物理空间 思想 借助于外存 硬盘 允许一个进程在其运行过程中部分地装入内存 三 虚拟存储的基本原理程序装入时 不需要将其全部读入到内存 而只需将当前需要执行的部分页 段 读入到内存 就可让程序开始执行 在程序执行过程中 如果需执行的指令或访问的数据尚未在内存 称为缺页或缺段 则发生缺页 段 中断 事先编好的中断程序将相应的页 段 调入到内存 然后继续执行程序 操作系统在内存紧张时 可暂时将不使用的页 段 调出保存在外存上 从而腾出空间 四 引入虚拟存储技术的好处可在较小的可用内存中执行较大的用户程序 可在内存中容纳更多程序并发执行 提供给用户可用的虚拟内存空间通常可远远大于物理内存 4 6请求分页存储器管理方式 在简单页式存储管理的基础上 增加请求调页和页面置换功能 是一种最常用的内存管理方式 一 请求分页中的硬件支持 1 页表机制 以第五章的基本页表为基础 增加换入 换出和保护所需信息 状态位P 存在位 区分对应页是否在内存 修改位M 页一旦被修改就置位 访问字段A 在一个间隔内被访问的次数或最后一次访问到现在的时间间隔 外存地址 若页不在内存 它在磁盘上的位置 保护位 该页是否可修改 2 缺页中断机构系统在硬件上提供缺页中断 在需要的页不在内存时 产生缺页中断 其余的工作由操作系统提供的缺页中断程序处理 中断的特殊性 缺页中断在指令执行期间产生然后进行处理 而不是在一条指令执行完毕之后 所缺的页面调入之后 重新执行被中断的指令 一条指令的执行可能产生多次缺页中断 共发生5次中断 2 地址变换机构 在原变换机构的基础上增加了缺页中断 程序请求访问页 开始 页号 页表长 检索快表 快表中找到 访问页表 修改访问位与修改位 形成物理地址 地址变换结束 页在内存 修改快表 2 地址变换机构 在原变换机构的基础上增加了缺页中断 中断响应 保留CPU现场 在外存中找该页 内存满 在内存中按淘汰算法选择一页或几页淘汰到外存 淘汰的页修改过 修改页写回外存 OS负责从外存读缺的页启动I O硬件将页从外存调入 修改页表 指令重执行 恢复CPU现场 缺页处理过程小结 1 硬件陷阱进入核心 保存PC到栈中 大多数机器将当前各种状态保存在特殊的寄存器中 2 启动一个汇编程序代码保存通用寄存器和其它重要的动态信息 以免被操作系统破坏 3 操作系统发现一个缺页时 查找需要哪个虚页 通常一个硬件寄存器含有该信息 4 一旦知道了发生缺页的虚拟地址 操作系统检查这个地址是否有效 如无效 向进程发一个信号或杀死进程 UNIX 若有效也没有保护错误发生 系统则从空闲页框中选一个页框分配 如果没有空闲页框 执行页面置换算法找一个页淘汰 5 若选择淘汰的页框不 脏 直接到 6 否则该页写回磁盘 并发生一次进程切换 暂停本进程 让其它进程运行到页面写完成 在这期间 该页框标志忙 以免被占用 6 页框 干净 后 操作系统查找磁盘上所需调入的页 通过磁盘操作策略将其装入 在这期间 产生缺页的进程仍然挂起 而其它正在运行的进程也依然在运行 8 恢复发生缺页指令以前的状态 程序计数器重新指向这条指令 7 当传送完成 磁盘发生中断 表明该页已经装入 更新页表有关项以表明正确的状态 9 缺页进程恢复 操作系统返回调用它的汇编语言例程 10 该例程恢复寄存器和其它重要的动态信息 回到用户空间继续执行 就好象缺页没有发生过一样 二 页面分配 1 保证进程能运行的最小页框取决于机器硬件结构 2 页面分配和置换策略 A 固定分配局部置换给每个进程分配固定数目的页框 当发生缺页中断时 只考虑从该进程所属的页框中调出旧的页面 从而换入新的页面 困难在于分配多少个页框合适 少了中断频繁 多了内存装入的进程减少 B 可变分配全局置换预分配给进程一定数目的页框 OS控制一定数量的空闲页框 在进程的执行过程中 发生缺页时 OS就分配给该进程一个空闲的页框 当空闲的页框用完时 OS可根据需要从其它的进程中调出一个页框 C 可变分配局部置换预分配给进程一定数目的页框 OS控制一定数量的空闲页框 在进程的执行过程中 发生缺页时 首先考虑从该进程所属的页框中调出旧的页面 若发现该进程频繁发生缺页中断 这时可分配新的页框给该进程 3 分配算法A 平均分配系统中可供分配的页框平均分配给进程 B 按比例分配按进程所需的页面数按正比例分配C 按优先权分配按进程的优先权分配 三 页面调入策略 B 预调页 在发生缺页需要调入某页时 一次调入该页以及相邻的几个页 A 请求调页 只调入发生缺页时所需的页面 优点 容易实现 缺点 外存I O次数多 开销较大 要求I O速度快 1 调入页面的策略 2 何处调页面外存通常分为文件区和交换区 通常外存交换区的I O效率比文件区的高 通过采取文件连续存放 加大物理块容量等措施 调入页面的来源 常用做法有 进程装入时 将其全部页面复制到交换区 以后总是从交换区调入 执行时调入速度快 要求交换区空间较大 凡只读页面或未被修改的页面 直接从文件区调入 换出时不必写回磁盘 下次仍从文件区调入 已被修改的页面 被置换时需调出到交换区 以后从交换区调入 UNIX方式 第一次需要该页面时 直接从文件区调入 而曾经运行过的页面 换出时放在对换区 下次调入时 应从对换区调入 在进程结束时 更新文件区内容 3 页面调入过程页面不在内存 缺页中断 查页表 得到外存物理块号 淘汰一页 如该页修改过 则要写回交换区 调入新页 修改页表 重性执行该指令 4 7页面置换算法 解决 需要调入页面时 选择内存中哪个或哪些物理页面被置换 目标 把未来不再使用的或在以后一段时间内较少使用的页面调出 通常只能在局部性原理指导下依据过去的统计数据进行预测 相反会有 抖动 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 7 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 3 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 3 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 3 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 4 2 3 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 4 2 3 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 3 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 3 1 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 1 1 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 2 1 1 1 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 1 1 1 1 1 1 1 1 一 最佳置换算法选择 未来不再使用的 或 在离当前最远位置上出现的 页面被置换 这是一种理想情况 是实际执行中无法预知的 因而不能实现 可用作性能评价的依据 缺页次数 1 0 7 1 1 1 1 1 1 1 1 1 6次置换 缺页率 9 20 9 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 1 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 1 7 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 1 2 0 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 1 2 0 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 1 2 0 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 2 3 1 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 2 3 1 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 3 0 2 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 3 0 2 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 4 3 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 0 4 3 二 先进先出页面置换算法选择建立最早的页面被置换 可以通过链表来表示各页的建立时间先后 性能较差 较早调入的页往往是经常被访问的页 这些页在FIFO算法下被反复调入和调出 例 3个页框 页面走势如下 701203042 4 2 0 这种页框数增多而中断次数反而增加的异常现象称为Belady异常 Belady给的数据 69年 012301401234 Belady异常 三 最近最久未使用LRU置换算法 原理 在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用 即 已经很久没有使用的页面很有可能在未来较长的一段时间内不会被用到 1 LRU算法描述在淘汰一个页面时 选择最近最久未使用的页面 例 70120304230321201701 2 如何记最近最久没使用的页 1 硬件每个页面一个寄存器 访问一个页最高位置1 每隔一个时间段所有寄存器右移一位 淘汰时选值最小的 在实际应用中成本太高以至无法实现 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 7 0 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 7 0 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 1 7 0 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 1 7 0 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 2 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 2 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 1 7 2 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 2 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 4 0 2 7 1 三 最近最久未使用LRU置换算法 2 栈式算法实际运算是一个队 访问的页不在队中则入队若在队中 则调到队尾 原在它后面的顺序前移淘汰总是队头 按此算法 在队头的总是相对最近最久未使用的 例子 47071012126 队头 队尾 7 1 6 0 2 问题 每次访问页表时都要更新 表中查找被访问的页 移动数据都非常费时 即使用硬件做 也非常费时 四 Clock置换算法 也称最近未使用算法 NRU NotRecentlyUsed 或二次机会算法 它是LRU和FIFO的折衷 每页一个访问位 一旦该页被访问则置1 置换时采用一个指针 从当前指针位置开始按地址先后检查各页 若该页的访问位是1 改为0 顺序看下一个页 直到找到一个访问位0的页面作为被置换页淘汰 若A都为1 则为FIFO 1 简单的Clock算法 2 改进型Clock置换算法每个页有访问位A和修改位M 开始两个都为0 一旦访问该页 A置1 修改该页 M置1 1 A 0M 0最近即没使用 也没修改 2 A 0M 1最近没使用 但已修改 3 A 1M 0最近使用过 但没修改 4 A 1M 1最近使用过 又修改过第1次找A 0M 0但不修改A 找到就为置换页 找不到 第2次顺序找A 0M 1 同时置A为0 找到就为置换页若没找到 则再按第1次的方