操作系统第3章.ppt

第三章存储器管理目的与要求 了解连续存储分配 掌握页式存储管理 了解段 段页式管理 掌握虚存管理 了解各种页面替换策略及实用的综合策略 重点与难点 连续可变存储管理 页式存储管理 虚存管理系统内存访问过程 处理机 高速缓冲存储器 内部存储器 外部存储器 SRAM StaticRAM DRAM DynamicRAM 容量 小 大速度 快 慢价格 高 低 3 1存储器管理的基本概念3 1 1存储器的层次结构 1 逻辑地址和空间相对地址 名空间 源程序所限定的地址空间逻辑地址空间 目标程序的所限定地址空间 相对地址空间 3 重定位 存储空间 内存中所有存储单元的集合绝对地址 存储空间的地址 物理地址 2 存储空间和绝对地址 Load1 106Add1 108Store110 112345678 000100102104106108110 程序A的逻辑地址空间 Load1 1106Add1 1108Store1110 112345678 1000110011021104110611081110 程序A装入内存的绝对地址空间 装配程序 重定位 程序装入时 地址部分的调整过程 3 1 2重定位及其方式 4 重定位分类 静态重定位 静态重定位是由在程序运行之前 由连接装配程序完成 静态重定位 Load1 106Add1 108Store110 112345678 000100102104106108110 程序A的逻辑地址空间 Load1 1106Add1 1108Store1110 112345678 1000110011021104110611081110 程序A装入内存的绝对地址空间 装配程序 优点 无须增加硬件转换机构 只运行连接装配程序就可实现 缺点 它要求每个程序在内存分配一个连续的存储空间 且在程序的整个执行期间在内存中不能移动 否则程序不能正确执行 它要求用户必须事先确定作业所需的存储量 动态重定位 在程序执行过程中由硬件地址转换机构实现 Load1 106Add1 108Store110 112345678 000100102104106108110 程序A的逻辑地址空间 Load1 106Add1 108Store110 112345678 1000110011021104110611081110 程序A装入内存的绝对地址空间 动态重定位 重定位寄存器 1000 106 有效地址 优点 能使用户程序不要求分配连续的存储空间 分页 分段 能使用户程序在执行程序过程中 可以动态申请附加存储空间并可在内存中移动 有利于程序段共享 提高内存的利用率 缺点 需要附加的动态的重定位硬件的支持 实现存储管理的软件比较复杂 3 1 3存储管理的功能 4 内存容量扩充 2 地址影射 地址转换 完成地址重定位工作 实现虚拟地址到物理地址转换 3 存储共享和保护 内存中既有操作系统又有多道用户程序 它们共享内存 避免各用户程序相互干扰 特别是防止用户程序破坏操作系统 必须提供存储保护 1 内存的分配和回收 逻辑扩充 交换技术覆盖技术虚拟存储技术 通过存储分配记录表记忆每个存储区域的使用状态 按照确定的算法实施存储分配 回收内存 1 静态分配 静态分配一般采用静态重定位方式 通过装配程序把目标模块进行连接 装入到内存中 并分配所需的全部存储空间 优点 存储管理简单 缺点 在多道程序系统中不能有效地共享内存 使用不方便 2 动态分配 动态分配往往采用动态重定位方式 程序在存储空间的初始位置在装入时确定 但允许在其执行过程中根据需要申请附加内存 释放不在需要的部分存储空间 优点 能够接受不可预测的分配和释放存储空间的请求 实现动态分配和回收存储空间 操作系统能根据内存使用的实际情况将已装入内存的程序在内存中移动 缺点 实现相对复杂 3 1 4存储分配方式 3 1 5虚拟存储器 操作系统在硬件的支持下 对内存和外存实施统一管理 达到 扩充 内存容量的目的 扩充的部分叫做 虚拟内存 虚拟内存的实现方法 虚拟存储技术允许把每道程序的一小部分装入内存 而其余部分放在外存 程序就可以运行 限制 处理器寻址大小的限制 外存容量大小的限制 硬件支持 具有一个存取速度快 容量足够大的外存 硬盘 具有一定容量的内存 具有重定位转换机制 内存空间安排 特点 任一时刻内存只有一道作业 该作业连续存放于内存中 一 管理方法 操作系统 用户程序 0 a a 1 n 3 2连续空间分配3 2 1单道连续分配 界地址寄存器 主存 A a CPU true false 地址A 终止程序运行 越界检查机构 用户程序每访问一次主存 越界检查机构将访问的地址与界地址寄存器中的值比较 若越界 则终止其执行 二 覆盖 overlap 操作系统 固定区 4k 覆盖区 6k 覆盖区 10k A 4k E 10k D 6k C 4k B 6k F 8k 因内存小于作业的程序空间而引入覆盖 将用户空间划分成一个固定区和多个覆盖区 主程序放固定区 依次调用的子程序则放在同一个覆盖区 操作系统提供覆盖系统调用函数 由用户编程序时考虑调用 基本思想 将处于等待状态 等I O 或就绪 等CPU 状态的进程从主存换出到辅存 把将要执行的进程移入主存 三 交换 交换要花费较长的时间 I O缓冲区对于交换的影响 特点 任一时刻内存可有多道作业 每道作业连续存放于内存 操作系统 U1 Un 一 分区的划分方法 将用户内存空间分成长度固定的若干块 分区大小相等分区大小不等 用户空间 3 2 2多道固定分区管理 1 上下界寄存器和地址检查机构 当作业被调度运行时 作业在内存中的上下界地址送上下界寄存器 每次内存访问时 地址检查机构作越界检查 作业程序须是绝对地址或静态可浮动的 CPU 主存 下界寄存器 上界寄存器 True True 地址A falsefalse 程序性中断 地址访问保护有两种方式 2 基址寄存器 长度寄存器和动态地址转换机构 当作业被调度运行时 将作业所占内存基址及长度送基址 长度寄存器 每次内存访问时 先看访问地址是否小于长度 然后 基址进行访存 用户程序代码是动态浮动的 CPU 主存 基地址寄存器 长度寄存器 True 地址A false 程序性中断 二 作业调度 OS 4k 6k 12k OS 4k 6k 12k 7k 3k 4k 5k 3k 4k 1k 2k 5k 6k 7k 10k 11k 8k 多队列法 单队列法 三 存储碎片内部碎片 内存某存储区间大于其存放作 内零头 业空间的部分 外部碎片 内存某存储区间容不下要运行 外零头 的作业时 一 管理方法 特点 多道 连续 但不固定划分内存 3 2 3多道连续可变划分法 1 系统设置两张存储管理表 已分分区表 UBT 和空闲分区表 FBT 分别描述和管理系统中的已分配的分区和空闲分区 已分分区表UBT 空闲分区表FBT 2 系统设置一个空闲块队列 初始状态时队列中只有一个连续的空闲块 作业到达后 以某种策略分配空间 作业撤离时 将释放的空间加入空闲队列 状态位 指针 已分配分区的边界标志 状态位 指针 空闲分区的边界标志 FREE 举例 假设任一时间段内 内存中每一作业的运行时间相等 作业到来次序所需存储量运行时间 160KB10s 2100KB5s 330KB20s 470KB8s 550KB15s OS 040256 J1 J2 J3 J4 J5 分配 分配策略按分区链的不同方式包括最佳适应法 最大适应法 首次适应法 在找到合适的空闲块后 从其中适合作业大小的空间分给作业 而剩余部分挂入空闲队列 F 空闲块集合 size k 为块k的大小 size v 为用户所需空间 1 如果 k F 均有size k size v 3 F F k 4 如果size k size v 为存储分配基本单位大小 则将k分给用户 5 否则将k分成k1 k2 其中size k1 size v F F k2 首次适应法 FirstFit 搜索F时 选择所碰到的第一个满足作业要求的空闲存储块分配给用户 最大适应法 LargestFit 在F中选出满足作业要求的最大块分给用户 或称最差满足法WorstFit 最佳适应法 BestFit 在F中选出所有满足作业要求的存储块中最小的一块分给用户 分析 队列结构 查找时间 回收合并 缺点和改进 BestFit 按大小递增 n 2 n 易产生过多的小空闲分区 LargestFit 按大小递减 1 n 易发生最大分区过小 FirstFit 按地址递增 n 2 n 2 小分区易集中在队列前端 增加开始查找指针 回收 当作业结束时 收回作业所占空间 将此块链入空闲队列 若空闲队列中原来有与此块的相邻块 则把这些块合并成一个大连续块 紧致 拼接 通过移动作业位置可以将零散的空闲块连接成大块 要求作业动态可浮动 Bitmap数组 1 1 1 0 0 1 0 0 0 0 1 0 0 3 2 1 4 12 空闲队列头 二 可用空间管理除用队列表示可用空闲块外 也可以用数组登记可用空闲块 数组项 用户空间总量 基本分配单位 进行紧致的时机选择方案 1 当有作业完成释放分区时立即进行 2 当某作业申请分配存储空间 没有足够大的空闲分区 但总空闲分区之和又大于申请空间大小时进行 连续存储空间分配各方法的比较 碎片过多 当 大 作业来临处理办法也不理想 一 空间安排用户进程空间 地址 叫逻辑空间 地址 内存空间 地址 叫物理空间 地址 用相同长度为单位对逻辑空间等分出的每个区域叫页 对物理空间等分出的区域叫页帧 对外存交换区等分出的每个区域叫块 特点 作业 进程 分成页面 内存也划分成页面 将作业 进程 页面不连续地分布到内存页面 3 3不连续空间分配3 3 1页式管理 回收 当进程结束时 系统回收它的所有物理页帧入空闲队列 二 动态地址转换机构因页式方法中逻辑地址与物理地址之间失去自然联系 故要通过页表 并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存 分配 初始时 所有页帧都在空闲队列中 当用户进程被创建时 系统按需要量从空闲队列获得相应量的页帧 1 8 5 3 0 4 9 8 7 6 5 4 3 2 1 0 3 2 1 0 逻辑空间 物理空间 页表 一 页表页表放在系统空间的页表区 存放逻辑页与物理页帧的对应关系 PCB表中有指针指向页表 页号 p 线性逻辑地址 页面大小 d 线性逻辑地址 p 页面大小 4 3 2 1 0 页号 二 地址结构 逻辑地址 页号p 页内位移d nk 10 物理地址 页帧号f 页内位移d nk 10 三 页面大小的考虑将页面大小取成2的k次幂 k是正整数 获取p和d的除法或乘法只要通过位移实现 页面大小为2的k次幂的地址转换原理如下 Pd 页表基地址 f nk 10 fd nk 10 页表 CPU有一个用于页号 页帧号转换的联想存储器 将页表存入联想存储器的地址 其转换原理如下 Pd nk 10 fd nk 10 P2 f2 P1 f1 P f Pm fm 四 联想存储器 快表 关键字值 地址转换的一般过程 联想存储器可以看成是页表的cache Pd nk 10 fd nk 10 P2 f2 P1 f1 P f Pm fm f 页表基地址 页表 联想存储器 快表 在进程被调度占用CPU时 将进程页表基址装入页表基地址寄存器 同时用新的页表内容替换联想存储器中的原内容 命中率 选用8 12项组成的联想存储器 并采用适当的替换策略 在联想存储器中匹配成功的可能性可达80 90 等效访问时间 设访存时间为750ns 搜索联想存储器的时间为50ns 命中率为80 则 80 750 50 20 750 50 750 950ns 三 可用空间管理一般步骤若可用页帧总数小于作业总页数 则拒绝分配 结束 取作业的下一页P 分配一可用帧F 并将P的内容抄到F中 将F抄到页P的页表项中 若所有页已处理完 则结束 否则转到2 当作业撤离时 根据页表项中记录的页帧号 回收页帧到可用队列中 四 共享与保护通过页表可以使几个逻辑空间指向同一个物理空间 实现程序共享 举例 EDIT1 EDIT2 EDIT3 DATA1 EDIT1 EDIT2 EDIT3 DATA2 EDIT1 EDIT2 EDIT3 DATA3 3 4 6 1 3 4 6 7 3 4 6 10 OS DATA1 EDIT1 01234567891011 EDIT2 EDIT3 DATA2 DATA3 P1P2P3 页表 存储保护 越界保护 设置页表长度寄存器 查页表前 先检查页号是否越界 89页 操作访问保护 在每个页表项中增设一存储保护域 用于说明对该页的访问权限 每一个对该页存储的访问都首先比照是否满足该页访问权限的说明 满足则访问 否则报错 举例 设为每一页表项增加三位 R位表示读权限 W位表示写权限 E位表示执行权限 RWE000不可进行任何操作001可以执行 不可以读写010只可以写011100101110111 页式管理 对用户而言不自然 3 3 2段式管理 段式管理的特点 按作业的自然段将其逻辑空间分成若干段 作业以段为单位分配内存 一 空间安排 用户作业逻辑空间为二维空间 由若干自然段组成 逻辑地址 段号 段内偏移 记做S d 编译及装配时把所有地址记成 s d 的形式 物理内存空间管理 与多道可变划分法相同 系统以段为单位分配物理内存 主程序 子程序1 子程序2 栈 数据 逻辑空间 子程序2 主程序 栈 数据 OS 子程序1 物理空间 二 动态地址转换 保护码 段长 本段基地址 段表 由如下格式的段表项组成 作业每段由一个段表项表示 段表放于系统空间 进程PCB表中存有段表始地址 基地址 段表长度 段表基地址寄存器 段表长度寄存器 段号 保护码 段长 段基地址 保护码 段长 段基地址 S d 段表基址 段表长度 PA 越界 地址转换过程 LA 联想存储器 三 共享 若共享的段引用自身的某个地址 则各进程必须用同一段号来共享这一段 J1 0段 SQRT J2 SQRT 1段 逻辑空间 物理空间 0段 SQRT 1段 对于用户而言 段页式管理与段式相同 用户逻辑地址只涉及段号与段内位移 对于物理内存管理而言 它与页式系统相同 系统内的逻辑地址 段号 段内位移 段号 页号 页内位移 记做 S P d 特点 将作业分成若干段 每段用页式管理实现内存分配 一 空间安排 3 3 3段页式管理 作业空间的内部表示 主程序子程序数据 保护码长度页表基址 OS 段表 页表 主存 作业 段表 页表 二 动态地址转换 段号 页号 保护码 页帧号 S p d 段表基址 段表长度 越界 f fd 段表 页表 快表 三 保护与共享保护与段式管理相同 共享则可以以页为单位 也可以共享页表 等效访问时间 设访存时间为750ns 搜索联想存储器的时间为50ns 命中率为95 则95 750 50 5 750 50 750 750 875ns 段表 主程序子程序数据 作业1 主程序子程序数据 作业2 段表 页表 OS 主存 放 连续存放 单道连续分配 多道连续固定分配 多道连续可变分配 不连续存放 页式存储 段式存储 段页式存储 系统为进程提供一个比物理内存大得多的虚拟存储空间 逻辑空间大小不在物理内存大小的限制 逻辑空间的容量由系统的有效地址长度决定 假设地址长度为32位 按字节寻址 则逻辑空间 虚存空间 大小为232个字节 3 4虚存目的 提供用户进程一个巨大的虚拟存储空间 手段 利用外存 磁盘 实现此虚空间 3 3 1虚存的基本思想 实现该虚空间的基本方法是 在页式 段式 段页式 管理的基础上 仅将进程的一部分页 段 放于主存 页 段 表项中注明该页或段是否在主存 程序执行时 如果访问的页 段 不存在主存 根据页 段 表项的指示 将其从外存调入主存 如果此时无可用的内存空间 则先淘汰若干页帧或段 内存进程虚存 进程页表 外存交换区 外存执行文件 页式虚存示意 交换区 SWAP 进程刚建立时 页面所在辅存即程序文件所在的辅存位置 但程序文件中一般包含有程序的二进制目标码及数据初始值和初值为0的工作区 后两者在回写时不能写入程序文件 因此引入了交换区 一 页表项结构 合法位 置该位表示该页在内存 修改位 置该位表示该页被修改过 在释放或淘汰时应写回外存 页类型 零页时 表示该页在分配物理页帧时应清0页帧空间 回写swap区页时 表示回写swap区 保护码 R W E保护说明 外存块号 该页所在外存的块号 页帧号 当在合法位置上时 代表该页所在内存的页帧号 3 4 2页式虚存管理 二 页表建立 分配pid给子进程 分配PCB空间 初始化PCB 进程标识 调度信息 分配子进程页表空间 复制父进程的程序区页表项 使程序共享 1 部分复制父进程页表 如UNIX的fork 初始化页表方法 在进程创建时建立页表 页表项在初始时 合法位 修改位及页帧号都未置上 复制父进程的数据区和栈区 为数据区和栈区分配swap空间 复制并修改数据区和栈区页表项内容 继承父进程对其他资源的访问现场 用父进程PCB中现场区初始化子进程的现场区 且使子进程fork 返回值为零 将子进程挂到就绪队列 返回子进程pid给父进程 为执行程序页面建页表项时 保护码为可执行 外存块号即该页所在文件的外存块号 不必回写 为所有初始数据页建页表项时 保护码为可读写 页类型说明为回写swap页 外存块号即该页所在文件的物理块号 待该页回写时 再分配swap区空间 改外存块号栏 为所有临时数据页建页表项时 保护码为可读写 页类型说明为零页 外存块号栏空 当第一次访问该页时 分配页帧并清0页帧 回写时 再分配swap区空间 填外存块号栏 2 用一个可执行的文件来初始化页表 在执行虚存访问指令时 由硬件合成物理地址 若能在联想存储器中获得该虚页的物理页帧号 则访问之 若要查当前进程页表 须先检查该页页表项的合法位 该位若置上 则从页表项中获得页帧号 否则要发一个页故障 pagefault 信息或叫做缺页中断 当缺页中断处理完后 重新执行访存指令 联想存储器中的页表项都是合法页的页表项 三 硬件动态地址转换 1 根据发生页故障的虚地址得到页表项 2 申请一个可用的页帧 根据所采用的替换策略可能需要引起淘汰某一页 3 检查页类型 若为零页 则将页帧清0 将页帧号填入页表项的页帧号一栏 置合法位为1 若非零页 则调用I O子系统将外存块号所指的数据读到可用页帧 将页帧号填入页表项中 合法位置1 结束 四 缺页处理 当硬件执行访存指令产生一个缺页中断时 进入缺页中断处理程序 五 页淘汰页淘汰可以发生在申请页帧时 而现代OS一般都定时进行页淘汰 如何选取被淘汰的页是由页面替换策略决定的 若已决定淘汰页P 则淘汰一页的主要工作有 1 查P页表项的修改位 若未修改 则合法位清0 将页帧送回空闲页帧队列 2 若已修改 则检查类型栏 3 若是零页或回写swap区页 则申请一块swap区空间 将P的外存块号置上 4 调用I 0子系统 将页帧上的数据写到外存块号所指的外存空间 合法位清0 将页帧送回空闲页帧队列 虚存的作用 解决主存空间不足 让更多的进程并发运行 提高系统的吞吐率 页故障引发 PageOut PageIn 访问辅存 必须防止系统发生抖动 控制页故障 3 4 3页面替换策略 页面替换策略中的基本概念驻留集 工作集 进程的合法页集合 访问串 进程访问虚空间的地址踪迹 举例 某进程依次访问如下地址 0100 0432 0101 0612 0102 0103 页式虚存管理以页为基本单位 只需页号即可 设页面大小为100 上述访问串可简化为1 4 1 6 1 1 页面替换策略分成两类 驻留集大小固定的替换策略 驻留集大小可变的替换策略 设驻留集大小为m s t 为t时刻的驻留集 r t 为t时刻访问的页号 t取0 1 t 指访存指令执行时刻 驻留集与pagingin out的关系 s 0 空 s t r t 1 s t s t r t 1 r t 1 s t s t ms t y r t 1 r t 1 s t s t m y s t 一 驻留集大小固定的替换策略 S t 1 其中y为被替换页 根据不同的选则的方法可形成不同的策略 一 FIFO替换算法 替换最早进入的页 举例 驻留集大小为3 访问串为 7 0 1 2 0 3 0 4 2 3 0 3 2 OOOOOOOOOO FIFO方法的特点 实现方便 不需要额外硬件 效果不好 有Belady奇异 Belady奇异 指替换策略不满足随着驻留集的增大 页中断数一定减少的规律 123412512345 OOOOOOOOO OOOOOOOOOO 123412512345 4 4 4 4 4 4 3 3 3 二 OPT Optimalreplacement 举例 驻留集大小为3 访问串为7 0 1 2 0 3 0 4 2 3 0 3 2 OOOOOOO 淘汰下次访问距当前最远的那些页中序号最小的页 OPT方法特点 最优的固定驻留集大小替换策略 不可实现 OPT策略对任意一个访问串的控制均有最小的时空积 进程所占空间与时间的乘积 由于需要预先得知整个访问串的序 故不能用于实践 仅作为一种标准 用以测量其他可行策略的性能 三 LRU LeastRecentlyUsed 淘汰上次使用距当前最远的页 举例 驻留集大小为3 访问串为7 0 1 2 0 3 0 4 2 3 0 3 2 OOOOOOOOO LRU策略是一种栈算法 对于相同的访问串 任意时刻满足 S m t 属于S m 1 t 的替换算法被称为栈算法 LRU策略中 当驻留集大小为m时 S m t 中保持着最近使用过的m个页帧 当驻留集大小为m 1时 S m 1 t 中保持着最近使用过的m 1个页帧 故S m t 属于S m 1 t 的LRU策略是栈算法 LRU策略的特点 要硬件配合 实现费用高 但效果适中 实现方法1 给每个页帧设一个计数器 每访问一页 对应页帧计数清0 其余页帧计数加1 淘汰计数最大的页帧 实现方法2 用类似栈的结构来管理和实现LRU 栈算法没有Belady奇异 设n m 对于栈算法有S m t S n t r t S n t 则r t S m t 因此 驻留集为n时出现的页中断一定会出现在驻留集为m时 LRU没有Belady奇异 四 实用方法1 兼顾FIFO和LRU策略为页帧在页表项中增加一位使用位 硬件每访存一次 即将对应页的使用位置1 操作系统页面管理程序定时将所有使用位清0 淘汰时任选一个使用位为0的页 操作系统选择淘汰页时 尽量避免选被修改过的页 因此 首先选择使用和修改位都为0的页 若没有 再选修改位为1 使用位为0的页 再选使用位为1 修改位为0的页 最后按FIFO选两者均为1的页 2 Clock置换算法 为每页设置一个访问位 再将内存中的所有页面通过链接指针链成一个循环队列 当某页被访问时 其访问位置1 置换算法在选择淘汰页时 需要检查访问位即可 如果是0就调出 否则将访问位清零 但不调出 直到查访到访问位为0为止 并将其淘汰 改进再增