南邮操作系统教程CH 04 存储管理

第四章存储管理 4 1概述4 2连续存储管理4 3分页式存储管理4 4分段式存储管理4 5虚拟存储 学习目标 虚拟设备多个进程和线程可以共享一个CPU多个进程和线程应该可以共享一个存储器多个进程和线程还可以共享一个IO设备 第5章 如何共享一个存储器 各进程 线程自己的数据有自己的执行区域 程序变成进程时是如何映射到那个区域去的 对各进程 线程在内存中的数据要加以保护 如何实施 为了更好地利用CPU 就应该让更多的进程 线程并发执行 如果内存不够用了怎么办 虚拟存储器 源代码的伪中间代码 intdemo inta 0 while a 2 a return0 代码执行时 这些行号需要改变吗 0demo 1inta 02loop 3temp a 24if temp 0 gotodone5a 6gotoloop7done 8return0 7 2 存储地址及地址转换 存储器使用的地址叫物理地址 绝对地址 其空间是由存储器地址总线扫描出来的空间 其大小取决于实际安装的主存容量 目标程序地址叫逻辑地址 相对地址 被限制从0开始编址 一个用户程序的逻辑地址集合称为该程序的逻辑地址空间 地址转换 重定位 地址映射 将程序的逻辑地址转成物理地址的过程 静态转换动态转换 执行步骤 编译链接 装载执行 程序执行步骤 地址转换时机 中间代码0 1 2 3 050K100K180K230K 50K 1 2 内存 静态地址转换 静态转换 当用户程序被装入内存时 一次性实现逻辑地址到物理地址的转换 以后不再转换 一般在装入内存时由软件完成 若编译时完成则需要程序员事先知道要装载的地址 1000 goto1200 0 100 200 300 goto200 a 逻辑地址空间 1100 1200 1300 物理地址空间 a 动态地址转换 动态转换 在程序执行过程中要访问数据时再进行地址变换 需要额外的硬件来记录程序装载的内存基址 1000 goto200 0 100 200 300 a 1100 1200 1300 a 逻辑地址空间 物理地址空间 CPUgoto200 1000 BR goto200 存储保护 使在内存中的各道进程 只能访问它自己的区域 避免进程内存空间重叠 特别是不能访问OS的内存空间 通常需要两个硬件支持 不需要转换地址 基址寄存器 BaseRegister 存放装载的起始地址限长寄存器 LimitRegister 存放的最大逻辑地址 0 x00000000 0 xFFFFFFFF OperatingSystem 进程 DRAM Base Limit CPU 逻辑地址 看管好用户进程 策略 将用户进程关在一个内存区域它不能自己切换到内核模式它不可以直接改变基址和限长寄存器的值它不可以随意更改中断控制它不可以访问其它进程的内存空间数据两个问题内存中的进程如何交互 内核模式和用户模式如何切换 连续存储管理 所谓连续 是指进程在主存里占用一块连续的空间 如果系统事先把内存用户区划分为若干分区 分区大小可以相等 也可以不等 一个进程占据一个分区 我们称其为固定分区存储管理 若内存不预先划分好 而是等进程装入时 根据进程的需求和内存空间的使用情况来决定是否分配 我们称其为可变分区存储管理 固定分区存储管理 存储分配 系统维护一张主存分配表 里面记载了内存的分区划分和使用状态 分配主存时总选择那些分区占用标志为0且长度小于等于进程所需空间的分区块 回收只要相应分区占用位置0即可 固定分区的地址转换和存储保护 静态转换 装入时检查绝对地址是否落在分区内动态转换 执行时检查 如下图所示 可变分区存储管理 存储分配 系统维护两张表 一张记录尚未分配的内存状态 另一张记录已分配的情况 初始状态已分配表为空 未分配表仅有一条记录 整个用户区就是空闲区 系统总是从空闲中选择一个足够容纳进程的分区分配 并将分配情况记在已分配表中 剩余的分区空间记录进未分配表 回收 将已分配表的标志改为 空 再将其加入未分配表中 空闲区表 已分配区表 某一时刻的分配状态 可变分区分配算法 首次适应分配第一个足够大的分区 可以从头开始查找 也可以从上次分配结束的地点开始查找最优适应查找整个分区表 分配最小的足够大的分区总是产生最小剩余分区 不浪费一个更大的空间 但会导致剩余分区太小难被再利用最坏适应查找整个分区表 分配最大的足够大的分区总是产生最大剩余分区 它可能比最优适应产生的剩余分区更容易利用 可变分区的地址转换和存储保护 基址 基址寄存器 逻辑地址 CPU 绝对地址 操作系统区 空闲分区1 用户进程1 空闲分区2 限长 限长寄存器 限长 越界 紧凑技术 碎片 问题经过一段时间的分配回收后 内存中存在很多很小的空闲块 它们每一个都很小 不足以满足分配要求 但其总和满足分配要求 这些空闲块被称为碎片 造成存储资源的浪费 解决方法 紧凑通过在内存移动进程 将所有小的空闲区域合并为大的空闲区域 使用静态地址转换的不可以使用紧凑 采用紧凑技术前要评估开销 紧凑技术的实现过程 进程4需要20K空间时没有足够大的空闲区 内部碎片和外部碎片 碎片内部碎片外部碎片都是 连续 惹得祸 把进程剪碎 P1 P2 P3 P4 0K 15K 38K 48K 68K 80K 110K 120K 固定分区 可变分区 P5 外部碎片 内部碎片 如何将逻辑地址空间分割 最自然的分割方法就是按段划分 通常一个进程都包含几个基本段 这些段可以在内存中分散存储 为了能找到它们 每个段都设有一个基址和一个限长 0 2 1 3 逻辑内存 内存 代码 数据 堆栈 附加 段式存储管理的地址转换和保护 每个程序段都有一个段号 段号从0开始 每一段也从0开始编址 段内地址是连续的 逻辑地址包括段号和段内位移 通过基址和限长可以找到段在内存的位置 一个进程所有段的这些值列表被称作 段表 段表可设置标志位决定该段的读写性 物理地址 逻辑地址中段号对应的段基址 段内位移 复习 如何将逻辑地址空间分割 将进程剪碎有很多种方法 最自然的分割方法就是按段划分 通常一个进程都包含几个基本段 为了标识指令和数据地址 给每一个段从0开始编一个号 同时在段内部给每一条指令和数据也编一个从0开始号码 0 2 1 3 逻辑内存 物理内存 代码 数据 共享 堆栈 复习 段式存储的逻辑地址 我们称这些编号为逻辑地址 前一部分表示段号 后一部分表示段内位移 段号和段内位移应该占多少位取决于系统和人为规定 在一个采用16位地址的计算机系统里 如果一个进程最多分成四段 那么段号就仅要占用2个二进制位即可 这些段在内存中离散存储 它们在内存中真实的地址叫物理地址 为了能定位这些离散段在内存中的位置 要把每个段在内存中的起始地址记录下来 同时要记录每个段可达的最大长度 这两个数值分别被记录在一个基址和一个限长寄存器之中 复习 段式存储管理的地址转换和保护 段式存储管理的逻辑地址包括段号和段内位移 每一个段都对应着基址和限长两个值 一个进程所有段的这些寄存器对的值列表被称作 段表 物理地址 逻辑地址中段号对应的段基址 段内位移限长寄存器的值用于存储保护 简单的分段实例 16位地址空间 段式地址转换实例 程序执行流程 PC 0 x240 得到下一条指令的逻辑地址 0 x240 段号 0 位移 0 x240物理地址 Base 0 x4000 0 x240 0 x4240从0 x4240获取指令 la a0 varx Move0 x4050 a0 MovePC 4 PC下一条指令的逻辑地址 0 x244 转换成物理地址 0 x4244 得到 jalstrlen Move0 x0248 ra returnaddress Move0 x0360 PC跳转到strlen函数部分 还处于第0段 为什么 Move0 x0 v0 MovePC 4 PC下一条指令的逻辑地址 0 x364 转换成物理地址 0 x4364 得到 lb t0 a0 a0的逻辑地址 0 x4050 段号 1 位移 0 x50 物理地址 0 x4800 0 x50 0 x4850LoadBytefrom0 x4850 t0 MovePC 4 PC 0 x240main la a0 varx0 x244jalstrlen 0 x360strlen li v0 00 x364loop lb t0 a0 0 x368beq r0 t1 done 0 x4050varxdw0 x314159 段式存储管理小结 每个进程都有一份段表 段表的地址保存在段表寄存器当中 进程切换的时候要保存 恢复进程的段表 存储共享通过让两个进程的段表的某一段指向相同的基址 可以实现数据和代码的共享存储保护段内的位移不可以超出该段的限长对于各段也应该设置相应的读写权限代码段应该是只读段数据段是读 写段共享段可以是只读 也可以是读 写存在的问题外部碎片问题对换 swap 以段为单位 成本较大 无法进行粒度控制分页机制可以解决上述问题 页式存储管理 将内存划分成固定大小的块 页框 逻辑地址也划分成相同大小的区 页面 于是也实现了将进程分散存储的目的 x86 Pentium的页框大小为4KB进程总是在装载最后一个页面时可能产生碎片 所以碎片大小不会超过一个页框 它属于内部碎片 页式存储管理的地址转换和保护 逻辑地址的页面号从0开始 每个页面的页内位移范围为0至4K 1 对x86CPU32位地址而言 每个进程都要记录每个逻辑页面所对应的物理块号 我们称这些值列表为 页表 同时设置一些标志位用于访问权限 读 写 读 写 有效和无效 物理地址 页框地址 页框号x页框长 页内位移存储保护 检查页号是否越界 为什么不检查页内位移的越界了 同时检查存取权限 在一个分页存储管理系统中 逻辑地址长度为16位 页面大小为4KB 现一逻辑地址为0 x2F6A 且第0 1 2页依次存在物理块10 12 14号中 问相应的物理地址是多少 解 页面大小 4KB 页内位移占12位 页号占4位0 x2F6A 0010111101101010页号 0010 2 其所对应的页框号 14故最后的物理地址为 0 xEF6A 习题15 p387 分段与分页的区别 对页表的讨论 页表就是一个页面号到页框号的索引 每个进程都有一个页表保存在内存里 所以导致每次访问一个指令或数据都要访问两次内存 为了解决这个问题 系统使用了一个高速缓冲区TLB缓存页表 称为 快表 每次仅当在快表中无法找到相应页号时才去访问内存中的页表 页表是要占用内存空间的 拿Windows2000和x86为例 页框大小为4KB 逻辑地址空间为4GB 即由1M个页面组成 如果每个页表项占4B 那么一个进程将要占用4MB的连续内存存放页表 开销巨大 把页框设大点 这样可以减少页表项 但增加了碎片 那设小点呢 解决方法 对页表空间进行再分页 两级页表 将页表占用的那部分连续内存再分页 实现了页表的分散存储 为了找到页号 先要把该页号所在的页表页找到 于是形成了两级页表 第一级为页目录表 该部分连续 第二级为页表 一个采用二级页表机制的地址格式如下 逻辑地址 1个页表最多被分成1K个页表页 1个页表页最多表示1K个页面 复习 页式存储管理 将内存划分成固定大小的块 页框 逻辑地址也划分成相同大小的区 页面 于是也实现了将进程分散存储的目的 逻辑地址的页面号从0开始 每个页面的页内位移范围为0至4K 1 对x86CPU32位地址而言 页面大小为4K 物理地址 页框地址 页框号x页框长 页内位移 两级页表的地址转换 页表页不必全部在内存中 甚至可以全部不在内存之中 仅当需要时才调入内存 在页目录表中增加一个特征位 用于记录该页表页是否调入内存 部分装入 地址分级的另一个例子 分段 分页 段页式存储管理 将进程逻辑地址空间按逻辑段划分 同时对每一段进行分页处理 物理内存仍然按照页框大小划分 反置页表 InvertedPageTable 先前我们说的页表内容是按页面号排序连续存放的 在进行逻辑地址转换时可以很快地以页面号索引到目的表项 因为这样 页表必须覆盖整个逻辑地址空间 但事实上很多逻辑地址是未被使用的 如果仅针对物理块进行索引将会减少很大一部分页表空间 IPT就是一个这样的页表 它仅为每一个物理块建立一个表项 该表项包含正在访问该页框的进程标识 页号 地址转换机构MMU MMU MemoryManagementUnit 完成逻辑地址到物理地址转换功能的低层硬件设施 主要功能有 以页式存储管理分例 管理页表基址寄存器分解逻辑地址访问页表如果页表不在内存当中或出现越界现象时 MMU发出缺页中断或越界中断管理快表TLB 缓冲技术 缓存 比访问原始数据速度更快的数据副本存储器 在下列情况时能提高访问速度常用到的数据在缓存中不常用到的数据访问代价不高评估缓存的技术指标 命中率 当要访问的数据全部在缓存当中 则称命中率为100 缓存解决的是低速和高速设备之间的瓶颈问题 是当代计算机领域提高计算机速度的基本手段 可以被缓冲的包括 内存数据 页表 文件 网络数据等 哪些数据更应该装进缓存 空间局部性 某个时间段内 访问的数据和代码都在相邻的存储区 所以应尽量把连续的数据内容装入上一级存储器时间局部性 最近被访问的数据和代码很可能被再次引用 所以应尽量把这部分内容装入上一级存储器 局部性原理分析 程序中只有少量分支和过程调用 大都是顺序执行程序往往包含若干循环 计算被限制在一个很小的相邻部分很少出现连续不断的过程调用序列 过程调用深度也被限制在一个小范围之内对连续访问数组这样的数据结构时 往往是对存储区中相邻位置的数据的操作程序中有些部分不是经常被使用到 如出错处理程序 相联存储器TLB 采用多级地址结构的存储管理机制势必引起访问内存次数的增多 如果发生缺页的话将需要访问IO设备 这样情况会更加糟糕 TLB TranslationLook asideBuffer 一种比主存访问速度快 但容量较小的高速缓冲区 利用它解决CPU运算速度快和主存访问速度相对慢之间的瓶颈问题 MMU对TLB的管理 如果访问TLB中的快表未命中 则MMU会访问主存中的页表如果主存页表有效则将条记入TLB如果主存页表失效则需要告诉OS缺页 请求帮助调页入主存 CPU 主存 TLB 转换 MMU 命中 缓存内容被改写了怎么办 直接写 对缓存数据修改的同时也修改下一级存储器中的相应内容 优点 易于实现 读数据未命中不会导致写操作缺点 处理器要等待数据写完后才能继续执行回写 只修改缓存中的数据 直到该数据要让出所占缓存空间时才修改下一级存储器中的相应内容 这些被修改过的数据叫脏数据 优点 处理器可先写缓存而不急于处理下一级存储器中的内容缺点 实现复杂 读数据未命中可能会导致回写操作 部分装入和部分对换 部分装入 进程运行时仅将部分装入主存 其它的先存在辅存之中 当需要这部分信息时才调入内存 部分对换 如果主存没有足够空间 便将主存中暂时不用的信息移到辅存上 辅存作为主存的扩充 对用户而言 好像计算机系统有一个容量巨大的存储器 即 虚拟存储器 层次存储结构下 TLB 主存 辅存构成了二级缓冲 请求分页式虚拟存储管理 仅装入立即使用的那些页面 执行过程中访问不在主存的页面时 则产生一个缺页中断 请求系统将其从辅存调入主存 主存空间不足时则将某些页面对换到辅存之上 每次对换的单位是什么 一个页面逻辑地址如何向物理地址转换 同分页存储管理机制一样查找页面时先访问哪里 第一级存储 TLB需要对换页面时应该选择哪些页面 根据不同的页面置换算法 如FIFO LRU 如果缓存未命中怎么办 到下一级存储去找 内存 磁盘 如果缓存中的数据被修改了怎么办 我们称这些数据为脏数据 使用回写技术 请页式虚存管理的页表 驻留标志 指示对应页是否已装入主存辅存地址 记录页面在辅存中的位置其它标志修改位 M 当一个页被修改后会置该位 该位被置也就意味着该页被调出主存时必须回写到辅存上 该位也称脏数据位 引用位 R 该页被引用时设置 用于页面置换算法 访问权限位 A 限定了该页的访问权限 R W R W 请求分页虚存管理地址转换过程 CPU 主存 命中 内存中的进程页表 命中 辅存 缺页中断处理 未命中 调页 装页并修改页表 OS 导致缺页的原因 强制性缺页页面从未被调入进过内存由部分装入导致 如何消除 预调 在这些页面被调用之前事先调入容量不足缺页内存空间不足所致怎么办 最直接的方法 增加物理内存 但有时并不有效 间接的方法 内存中存在多道并发进程 调整各进程的内存占用比例策略性缺页页面本在内存 但是中途过早地被OS按照某种算法选中并淘汰 为了避免这种缺页 应采用更好的页面置换算法 页面置换算法 置换 对换 是所有缓存都要考虑的问题对请页式虚存管理而言 置换单位是 页面 我们不希望页面经常在内存和辅存之间对换 那么经常使用的页面就不应该被置换出内存FIFO 先进先出 淘汰最早进入内存的页 也就是一个在内存中呆着最久的页公平算法 保证每个页面占用内存时间相等 但是如果用不常用的页替换掉经常使用的页 情况将变得相当糟糕OPT 最优置换 淘汰一个以后不再访问的页 或是距现在最长时间后再访问的页该算法的确是最优的 但是我们无法预测未来RANDOM 随机置换 每次都随机挑选一个页面淘汰 简单但是效率低下 页面置换算法 续 LRU 最近最少使用 淘汰最近一段时间里最久未被访问的那一页该算法依据局部性原理 在最近很少被访问的页面 在未来可能被引用的机率也不大使用一个特殊队列实现 队列存放当前内存中的页号 队列头指向最久未访问的页 队列尾指向最近访问的页 每执行一次页面访问就做一次队列调整 如果页面在内存中 则将该页调整到队列尾如果发生缺页 则淘汰队列头指向的那一页 页面置换算法的评估指标 缺页中断率f如果进程需要n页 内存页框有m块 1 m n 如果进程执行的过程中成功访问页面的次数为S 不成功的次数为F 则总的访问次数为A S Ff F A好的算法带来最低的缺页中断率影响缺页中断率的其它因素内存页框数页面大小程序特性 局部性要好 实例分析 FIFO 假设一进程分为4个页面 内存有3个页框 页号引用序列为 ABCABDADBCBFIFO的页面置换过程如下 FIFO 7次缺页中断在引用D时替换掉A是个错误的决定 因为下一个要访问的正是A B C B D A D B A C B A 实例分析 OPT 与FIFO相同的页面访问序列 ABCABDADBCBOPT的页面置换过程如下 OPT 5次缺页中断LRU对这个序列效果如何 在这里是相同的 但并不总是这样 B C B D A D B A C B A 考虑另一个页面引用序列 ABCDABCDABCDLRU的置换过程如下 现在和FIFO相同 OPT算法工作的很好 LRU什么情况下工作的糟糕 C B A D C B A D C B A D 2ndChance 二次机会 2ndChanceFIFO算法的改进 给一些可能经常访问的页面第二次驻留内存的机会 尽管它们是最早进入队列的页面 需要和页表中的 引用位 结合实现 引用位 为1 表示该页最近被访问过 要被淘汰时则再给它一次机会 移到队列尾部的同时把 引用位 清0 引用位 为0 说明该页既老又没用 它就是被淘汰的候选页面该算法会导致队列频繁的调动 若将其组织成循环队列 性能将提升 这样形成了一个仅有一根指针的钟面 我们称这种方法叫时钟算法 Clock 时钟页面置换 钟面就是页框中存放的页号的队列循环链表指针指向下一个将被置换的页面 该算法与 二次机会 相同 仅实现机制不同 若指针移动速度很慢 说明发生缺页中断较少 或是很快就找到了淘汰页面 若指针移动速度很快 说明发生了很多次缺页中断 或是大量 引用位 被置位该算法把页面分成了两类 年青的和年老的可以划分出更多的类吗 实例分析 Clock Page9use 1 Page19Use 1 Page1Use 0 Page45Use 1 Page191Use 1 Page556Use 0 Page13Use 0 Page67Use 1 Page33Use 1 Page222Use 0 下一个帧指针 n 0 1 2 3 4 5 6 7 8 一个页替换前的缓冲区状态 Page9use 1 Page19Use 1 Page1Use 0 Page45Use 0 Page191Use 0 Page727Use 1 Page13Use 0 Page67Use 1 Page33Use 1 Page222Use 0 n 0 1 2 3 4 5 6 7 8 page556被page727替换后的缓冲区状态 第1页框 改进的时钟算法 利用页表中的 引用位 和 修改位 可以将页面划分成四种不同类型的页面r 0 m 0 既没被引用也没被修改 淘汰的首选 r 1 m 0 被引用过 但未被修改r 0 m 1 没被引用过 但被修改r 1 m 1 既被引用过也被修改过因为对被修改过的页面进行置换还需要加上一个回写操作 所以这类页面最好稍后置换 扫描过程 先淘汰掉r 0 m 0的页面若未找到 则选择r 0 m 1的淘汰 并将所遇到的页位 引用位 清0若还未找到 则重新回到第一步开始操作 四种算法计算的结构曲线图 页面置换算法总结 OPT是最优秀的 但也是无法实现的 FIFO保证各页面在内存中的时间相等 但很有可能将经常用到的页面置换出去 LRU选择最近最少使用的页面淘汰 是OPT的近似算法 但是并不是每次工作的都如OPT一样优秀 2ndChance Clock给访问过的页面一次留在内存中的机会 需要和引用位结合使用Clock 利用引用位和修改位把页面划分成四种类别 先淘汰既老也无修改的页面 再淘汰老页面 同时将扫描过的页面引用位清零 至此就一定能找到一个符合条件页面淘汰 页面故障率 PFF 分布图 对于容量不足导致的缺页 可以动态的调节各进程所占的页框数 用一个页面故障率 PFF 来评估它 我们的目标是把PFF控制在一个合理的范围之内如果PFF过低 可以回收一些页框如果PFF过高 可以多分配一些页框给它那么如何分配页框呢 页框分配策略 OS如何给多个并发进程分配页框 固定分配 进程生命周期中 页框数保持不变可变分配 根据进程的执行情况动态更改其页框数固定分配缺乏灵活性 但可变分配增加了OS的开销页面置换观点 局部 与固定分配结合使用 发生缺页中断从进程的页框中选择一个淘汰 全局 与可变分配结合使用 OS保留若干空闲页框 缺页时从系统空闲页框中分配一个给进程 若无空闲页框 则从内存中选择一个淘汰 可能是其它进程的页面 通常使用可变分配 局部置换策