第4章 存贮体系

1 第4章存贮体系 现代计算机系统以存储器为中心 在计算机执行程序的整个过程中 存储器是各种信息存储和交换的中心 本章主要内容 存储体系的基本概念 并行主存系统的组成 虚拟存储器和Cache存储器工作原理 虚实地址的映像和变换 替换算法及其实现 影响性能的因素分析及有关软件功能分配中的一些问题 了解主存保护的方式 本章重点 段页式和页式虚拟存储器的原理 页式虚拟存储器的地址映像 LRU FIFO OPT替换算法页面替换过程模拟 LRU替换算法对页地址流的堆栈处理模拟及性能分析 Cache存储器的直接和组相连地址映像 用LRU替换算法进行块替换的硬件实现及替换过程模拟 Cache存储器的性能分析 2 4 1存贮体系的形成与性能4 2虚拟存贮器4 3高速缓冲存贮器 Cache 4 4主存保护 第4章存贮体系 3 4 1存贮体系的形成与性能 本节主要内容 领会发展存储体系的必要性及存储体系的两个分支 了解并行主存系统的各种组织方式 掌握并行主存系统的极限频宽和实际频宽的关系与计算 领会通过使用并行主存的计算机组成技术提高主存频宽的可能性 局限性以及发展存储体系的必要性 了解有关存储体系的性能参数及相关结论 4 4 1 1发展存储体系的必要性 一 计算机对存贮系统的要求是 高速度 大容量 低价格1 容量存贮器容量 SM W L mW为存贮体的字长 位或字节 L为每个存贮体的字数m为并行工作的存贮体的数量 2 速度访问时间TA 存贮器从接到访存读申请 到信息被读出到数据总线上所需的时间 存储周期TM 是连续启动一个存贮体所需要的时间 一般TM TA 频宽Bm 存储器每秒传递的位数或字节数 传送速率 分为最大频宽和实际频宽 最大频宽Bm是存储器连续访问时提供的频宽 单体Bm W TM多体Bm W m TM 5 3 价格 包括存储体及外围电路的价格 可用每位存储器价格表示 这三者之间的关系是矛盾的 二 发展存储体系的必要性1 单一工艺不能同时满足容量 速度 价格的要求 而由不同工艺存储器组成的存储器系统逻辑上又不是一个整体 如主存和辅存 2 由并行和重叠技术组成并行主存系统 可以提高主存频宽 但都不能更理想地改善存储器性能 6 4 1 2并行主存系统频宽的分析 主存系统的结构包括 单体单字存储器单体多字存储器多体单字存储器多体多字存储器 单体单字存储器 一次访问一个存储器字 存储器字与CPU字相同 Bm W TM要提高主存频宽Bm 在同样器件条件下 同样的TM 要提高字长W 图单体单字存贮器 7 单体多字存储器 主存在一个存储周期内可读出多个CPU字Bm k W TM要提高主存频宽Bm 在同样器件条件下 同样的TM 要提高字长W 多字应顺序读 图单体多字 k 4 存贮器 8 多体单字存储器 多个存储体 每个存储体一个存储字 Bm m W TM字在主存中按模m交叉编址 分低位交叉 高位交叉多字可以不是顺序的 无体冲突即可 图多体 m 4 交叉存贮器 9 在低位交叉中 Mj体的编址模式为 m i ji 0 l 1j 0 m 1i 存储单元在存储体中的坐标m 存储体数l 单体单元数 表模4低位交叉编址 m 4 j 0 1 2 3 图4个分体分时启动的时间关系 10 多体多字存储器 多个存储体 每个存储体有多个存储字 Bm m k W TM 并行主存系统 能并行读出多个CPU字的单体多字 多体单字 多体多字的交叉访问主存系统通称为并行主存系统 通过保持每位价格不变的情况下 使得主存的频宽得到较大的提高 结论 提高模m能提高Bm但并不理想 原因在于 1 总线并联负载过重 产生延迟 2 数据顺序性不好 转移指令等影响系统效率 11 转移指令 对频宽影响的分析 项目 通过一个模型分析 转移指令 对频宽的影响 目的 说明单纯靠提高模m来提高并行主存系统的频宽Bm是有限的 结论 必须从系统结构上改进 采用存储体系 内容 m个分体 处理机发出一串访存地址A1 A2 Aq组成一个申请队列 在每一个存储周期之前 这个队列被扫描 并从头截取A1 Ak个地址作为申请序列 截取原则 A1 Ak中没有2个或2个以上地址处在同一个分体中 取满足条件的最长序列 A1 Ak可能不是顺序编址 只要没有分体冲突即可 k是随机变量 且k m 系统效率取决于k的平均值 12 设P k 为申请序列长度为k的概率 k的平均值为 每个存储周期访问的平均字数 P k 与程序密切相关 转移指令影响最大 转移成功 后续指令全作废 转移概率 给定指令的下条指令地址为非顺序地址的概率 代入 13 用数学归纳法化简 若 0 则B m 为多体交叉存储 等比级数 若 1 则B 1 相当于单体单字 图m个分体并行存取的B f 曲线 如果 0 3时 m 4 8 16的差别不大 m取值再大 对系统效率也无法带来多大的好处 为降低转移概率 就要求在程序中尽量减少使用转移类指令 14 4 1 3存储体系的形成与分支 存储体系 有多种存储层次 对程序设计者而言 各层次是一个逻辑的整体 各层次之间的信息交换由辅助软硬件自动完成 1 主存 辅存存储层次 虚存存储器 程序员对应虚地址 程序地址 虚存容量 实际主存为物理地址 主存容量 对虚拟存储系统 应用程序员可用机器指令的地址码对整个程序统一编码 就像拥有对应地址码宽度的虚拟存储空间一样 而实际存储空间比它要小得多 用这种指令地址码给出的地址 称为虚地址 即虚拟主存地址 而实际主存的地址称为实际主存地址 物理地址 实地址 目前指令地址码可达24 32位 地址线宽度 这样 实存空间可达16M 4G 图主存 辅存存贮层次 15 2 Cache 主存存储层次 主存容量不够 引出虚拟存储器主存速度不够 引出高速缓冲存储器 cache 解决CPU与主存的速度问题 3个方法 在CPU中增设寄存器采用多体交叉并行存储器采用cache存储器 图Cache 主存存贮层次 16 3 多级存储层次 CPU产生一个连续的逻辑地址流 这些地址以某种方式分布于各个存储层次 并被变换到Mi的物理地址 若i 1 则地址必须逐级变换再送到CPU能直接访问的M1 一旦信息不在M1中 程序应挂起 因为Mi M1的定位及信息传送速度慢 当然 若M1是Cache时例外 图多级存贮层次 17 4 程序具有局部性 存储层次构成的主要依据 时间上的局部性 最近的未来要用到的信息可能是现在正使用的信息 因为程序存在循环 空间上的局部性 最近的未来要用到的信息可能与现在使用的信息在程序空间上是邻近的 因为程序是顺序存访的 18 4 1 4存储体系的性能参数 1 命中率 CPU产生的逻辑地址能在第一级存储器中访问到 命中 的概率 R1 在M1中命中的次数R2 未调到M1中的次数 命中率H与地址流预判算法容量有关 M1 M2 一级 二级 19 2 等效访问时间TA TA H TA1 1 H TA2 TAi为CPU访问Mi中的信息所需时间 希望TA TA1 访问效率e TA1 TA希望e 1设访问时间比r TA2 TA1则 e 1时 r大 即二级存储速度差异大 要求H高 e 1时 r小 即二即存储速度差异小 降低H的要求 图对于不同的r 命中率H与访问效率e的关系 20 4 2虚拟存贮器 虚拟存储器是主存 辅存存储层次的进一步发展和完善 主要是为了克服高速的主存容量满足不了要求而提出来的 它依据的原理是 访问的局部性原理 虚拟存储器又称虚拟存储系统 或虚拟存储体系 是1961年提出来的 它由主存储器和联机工作的外部存储器共同组成 21 1 虚拟存储器概念由主存 辅存存储层次 辅助硬件和操作系统存储管理软件组成的一种存储体系 2 虚拟存储器与cache存储器的区别 CPU Cache 主存 直接访问通道 3 虚拟存储器的主要问题 1 地址映像2 地址变换3 替换算法 22 4 2 1不同的虚拟存储管理方式虚拟存储器管理方式 按存储映象算法 有段式 页式和段页式三种1 段式管理 将主存按段分配基本思想 1 把程序在逻辑上分解成相对独立的段 模块 2 每个段都从0开始相对编址 3 以段为单位在主存 辅存之间调度 4 设置段基址 该段在主存中的起始地址 则段基址 段内相对位移 物理地址段表 每道程序一个 存放该程序各段装入主存的状况信息 段表本身也是一个段 一般常驻内存 段表基址寄存器 只有一组 存放各道程序的段表的有关信息 如表长 表起始地址 23 图段式管理的定位映象机构及其地址的变换过程 段式管理过程如图所示优点 分块编址 可并行编程 缩短编程时间 便于多道程序信息共享 如字程序 容易实现段保护缺点 段大小不定 主存贮器的利用率比较低 查表速度慢在主存中的起点随意 给主存分配带来困难 应建立一个主存管理 指明整个主存的使用情况 哪个区域已被占用 被谁用 哪个区域是空闲的 0段 1段 2段 3段 4段 5段 6段 0 0 0 3k 1 0 0 0 0 1k 1 2k 1 1k 1 2k 1 3k 1 4k 1 A道程序的程序空间 A 4 1 5k 多用户虚拟地址 程序号 段号 段内位移 0 1 N 1 7 A a 段表长度 段表基地址 段表基址寄存器 主存中最多可有N道程序 0 1 2 3 4 5 0 5k 1k 1 0 1 0 1 0 1k 3k 2k a 6 0 段名 段号 起始地址 装入位 段长 访问方式 0段 4段 2段 0 1k 5k 1k 2k 3k 实主存空间 A道程序的段表 1 2 2 5k 3 24 实主存空间的分配和回收为了对实主存的空间进行分配和回收 段式存贮器需要为操作系统配备一个实主存空间管理表 进行存贮管理 它包括占用区域表和可用区域表两部分 在分配主存空间时 可采用 首先分配 法和 最佳分配 法来进行 首先分配 法 顺序扫描可用区域表 当找到第一个不小于要调入段长度的可用区时 就立即进行分配 最佳分配 法 先扫描全部可用区域表 然后寻找一个可用区进行分配 使之分配后段间可用区零头最小 25 图4 12段式存贮分配算法 26 2 页式存贮管理方式 基本思想 1 将主存空间和程序空间都机械等分成大小相同的页面 2 让程序的起点必须处在主存中某一个页面位置的起点上 3 任一主存单元的地址np由实页号nv和页内位移nr两个字段组成 用户程序空间中的每一个虚地址由虚页号字段Nv 和页内位移字段Nr组成 页表 每道程序一个页表 用来表示各虚页是否已经调入主存 页表基址寄存器 只有一组 存放各道程序的页表的有关信息 如表长 表起始页 27 图页式管理的定位映象机构及其地址的变换过程 28 优点 1 主存贮器的利用率比较高 2 页表相对比较简单 3 地址映象和变换的速度比较快 4 对辅存的管理比较容易缺点 1 程序的模块化性能不好 2 页表很长 需要占用很多的存贮空间 29 3 段页式管理 段式和页式相结合基本思想 1 主存等分成固定大小的页 2 虚存中的程序按模块分段 每个段又分成与主存页面大小相同的页 3 每道程序通过一个段表和相应的页表进行定位 2次查表 多用户虚地址 段表基址寄存器 段表 页表 页内位移段页式与段式主要差别之一 段的起点不是任意的 要位于主存中页的起点 在虚存中 每访问一次主存 都要进行一次虚地址 实地址的转换 页表 段表 用于存储地址映像关系 实现地址变换 面向用户程序空间 虚地址 每道程序有一个 30 图段页式管理的定位映象机构及其地址的变换过程 段页式管理的优缺点 结合了页式与段式管理的优点段页式增加了地址变换的时间 因为需要两次访存 查段表和页表 所以必须加快段页式管理查表的速度 31 例1 IBM370系统采用段页式管理 主存地址24位 指令地址码长32位 虚地址格式为 虚地址 每个用户的虚存空间为224 16M 页 4K 用户数 256 用户页数 4K 每个用户虚存空间有一个段表 格式如下 页表长度 页表起点 0 3 4 7 8 28 29 31 30 P I 每个页表占一行 4个字节 页表第一个单元的实地址为21位右边加3个零 形成24位主存地址 P保护位 P 1为只读 I状态位 I 1此段不正常 不能用 每段有一个页表 格式如下 对应页面号在主存的页面位置应是12位实页面地址 形成24位地址 I装入位 I 1已装入 该道程序的段表起始地址存放在CPU中的一个控制寄存器中 即段表基址寄存器 8 8 4 12 4 21 32 例2 VAX 11采用页式管理 地址码长32位 字节编址 每页29 512字节 222 4M虚页 9 22 31 每个用户有231 2G的虚存空间 1位程序号 例3 Intel80386 8086 8088没有虚拟存储器功能 80386以上才有 80386有存储管理部件MMU 由分段部件和分页部件组成 80386有两种操作方式 1 实地址方式 与8086兼容 支持1M实存空间 每段216 64K 2 虚地址方式 保护方式 虚存空间246 64T 实存空间232 4G 1页4K 33 4 2 2页式虚拟存贮器构成 1 地址的映象和变换 多用户虚地址与主存实地址的组成 地址的映象 是将每个虚存单元按某种规则 算法 装入 定位于 实存 即建立多用户虚地址Ns与实主存地址np之间的对应关系 地址的变换 在执行时 多用户虚地址Ns如何变换成对应的实地址np 实页冲突 多个虚页想进入同一个实页 图虚实地址对应关系及空间的压缩 34 图全相联映象 全相连映象 每道程序的任何虚页可以映象装入到任何实页位置 如图 页表法 用页表作为是一种全相连映象方式 地址映象方式的选择应尽量降低实页冲突的概率 减少辅助地址映象的表硬件 降低成本 便于实现 并使地址变换速度要快 虚存空间往往远远大于实存空间 因此 虚拟存贮器都采用全相联的映象规则 35 问题 虚存空间对应2u个用户 程序 主存最多运行N个用户 每个程序的页表有2Nv 行 主存有2nv个实页 N道程序的所有页表共有N 2Nv 行 而装入位为1的有2nv行 因此有N 2Nv 2nv行的实页号字段无用 降低页表的空间利用率 解决办法 1 辅存地址替换法页表中装入位为0的行的实页号字段存放辅存地址 目的 调页时实现虚页号 辅存地址的变换 要求 辅存地址实存地址长度相差不多 2 相联目录表法压缩页表只存放装入位为1 已装入主存 的虚页与实页的对应关系 该表最多为2nv行 采用按内容访问的相联存储器 不用设置装入位 但2nv行也很多 一般不直接用目录表法 36 按地址访问的随机存储器在一个存储周期里只能按给出的一个地址访问器存储单元 按内容访问的相联存储器在一个存储周期里能将给定的内容同时与存储器全部单元的数据相比较 进行相联查找 图4 18目录表法 37 问题 如何解决页面失效 虚页未装入主存 解决办法 从辅存调页 1 辅存按信息块编址 块的大小等于页面的大小 辅存的地址格式为 2 建立外页表 存放每道程序用户虚页号与辅存地址的对应关系 实现外部地址变换 原先用于内部地址变换的页表可称为内页表 外页表每行对应一个虚页 每行中有装入位字段 表示对应的信息块是否已有海量存储器 如磁带 装入磁盘 为1表示装入 而为0时则需要重新装入 外页表的内容是在程序装入辅存时填好的 3 外页表放在辅存中 当某道程序初始运行时 把外页表的内容复制到内页表 辅存地址暂时占用实页号字段 当虚页装入主存后改为实页号 4 辅存调页速度慢 当发生页面失效需要辅存调页时 采取程序换道方式 提高处理机效率 5 可用软件方法实现查外页表 由多用户虚地址到辅存地址的变换 节省硬件成本 38 图虚地址到辅存实地址的变换 39 2 替换算法 页面失效 当处理机要用到的指令或数据不在主存时产生页面失效 虚存大 主存小 主存满时进行辅存调页产生实页冲突 要替换 替换算法 选择主存中哪个页作为被替换的页 替换算法确定依据 1 主存命中率高 2 算法便于实现 3 辅助软硬件成本低 常用替换算法 随机算法 Random RAND 先进先出算法 First InFirst Out FIFO 近期最少使用算法 LeastrecentlyUsed LRU 近期最久未用过算法 LRU 优先替换算法 OptionalOPT 堆栈型替换算法页面失效频率算法 PFF 40 1 随机 RAND 算法 方法 用随机数产生被替换页的页号 实现 产生随机数 特点 简单 易实现 没有历史信息 不反映程序局部性 命中率低 不用 41 2 先进先出 FIFO 算法 方法 选择最先调入主存的页面作为被替换的页面 主存页面表 记录主存所有实页的使用情况 为主存管理而设计的表 整个主存只有一个 页表针对用户程序空间 主存页面表针对主存空间 实现 1 在主存页面表中分配一个时间进度计数器字段 2 当某页调入主存时 该页的计数器清0 其它页的计数器都加1 3 计数器值最大的页是最先进入主存的 将被替换 特点 利用历史信息 但不反映程序的局部性 最先进入的页可能是现在经常使用的页 图4 20主存页面表 42 例 设有一道程序 有1至5共5页 执行时的页地址流 即执行时依次用到的程序页页号 为 2 3 2 1 5 2 4 5 3 2 5 2 若分配给该道程序的主存有3页 用FIFO替换算法对这3页的使用和替换过程用图示表示如下 图FIFO替换算法对页地址流的替换过程 43 3 近期最少使用 LRU 算法 方法 近期最少访问的页面作为被替换的页 实现 1 在主存页面表中分配一个访问次数计数器字段和一个时间进度计数器字段 2 某页面被访问时 页访问次数计数器加1 时间进度计数器清0 其他页时间进度计数器加1 某页调入主存时 该页的时间进度计数器清0 访问次数计数器清0 其它页的时间进度计数器加1 3 时间进度计数器 N N为近期的界限值 时 访问次数计数器的最小的页将被替换 特点 反映历史信息和程序局部性 但计数器需要很长 实现困难 不用 用其变形 近期最久未用过 算法 44 4 近期最久未用过 LRU 算法 方法 选择出近期最久未被用过的页面作为被替换的页 实现 1 在主存页面表中分配一个 使用位 初始为0 2 某页被访问时 使用位 由硬件置1 3 发生页面失效时a 若占用位不全为1 则进行辅存调页 b 若占用为全为1 则进行页面替换 此处的研究对象 4 使用位为0的页将被替换 5 若使用位全为1 则采用以下使用位修改方法 a 随机周期法 当使用位全为1时 由硬件自动将它们清0 b 定期扫描法 另配一个 未使用过计数器 Hs 定期扫描 每隔 t时间 使用位 若使用位为0 则 未使用过计数器 加1 使用位保持0 若使用位为1 则使用位和 未使用过计数器 清0 这样 未使用过计数器 值最大的页是最久未使用过的将被替换 使用位只反映一个 t内的页面使用情况 而Hs则反映了多个 t内的页面使用情况 特点 计数器硬件较少 主存页面表可用软硬件实现修改 根据 历史 预测 未来 45 对于LRU算法 用一个使用位和 未使用过计数器 Hs 来实现 每隔 t扫视所有的使用位 为0的使其的Hs位加1 为1的则置Hs为0 同时置使用位为0 当需要替换时 查找Hs的最大值 则是要替换出去的页 t 使用位为1 则由1变为0 Hs清零 使用位为0 Hs加1 注意 使用位反映的是 t时间间隔内的使用情况 而Hs反映的则是近期最少使用的情况 46 5 优化 OPT 算法 方法 根据未来实际使用情况将未来的近期里不用的页替换出去 实现 1 确定要替换的时刻t 2 找出主存中每个页将来要用到的时刻ti 3 ti t最大的页将被替换 特点 命中率高 但难于实现 必须运行一遍 才能知道未来的时刻ti 是理想算法 用于评价其它替换算法 页地址流 程序页号序列 47 图4 213种替换算法对同一页地址流的替换过程 例 用页地址流模拟替换过程 48 图4 22命中率与页地址流有关 命中率与页地址流有关 49 图4 23FIFO法的实页数增加 命中率反而有可能下降 命中率与主存页面数相关 50 若对主存页数n取不同值都模拟一遍 工作量太大 因此提出堆栈技术分析模型 6 堆栈型替换算法 是指一类算法 采用这种分配算法 分配给程序的主存页面数越多 虚页装入到主存中的机会也越多 因此命中率也可能越高 至少不应该下降 51 定义 对任意一个程序的页地址流 若替换算法满足下列条件 则该算法属于堆栈型的替换算法 式中 n 分配给该页地址流的主存页面数 实页数 Lt 在t时间点以前出现的不同页的页数 Bt n 在t时间点 主存分配n个实页的前提下 主存中虚页的不同页面的页面号集合 说明 LRU OPT算法是堆栈型算法 FIFO不是 因为在前面的例子中 B7 3 1 2 5 而B7 4 2 3 4 5 所以B7 3 不包含于B7 4 不满足条件 52 堆栈算法的实现 1 建立一个堆栈S 根据堆栈算法的包含性 必有 式中 St 在t时间点 Lt个不同页面号在堆栈中的有序集合 St 1 栈顶 St 2 次栈顶 2 页地址流A在时间t点的At页面是否命中 看St 1的前n个项是否有At 有则命中 堆栈型算法只需对页地址流模拟一次 即可求得在不同主存页数n时的命中率 即H n 模拟一次可得到St 1 St Lt 为确定系统给该程序分配主存页数提供依据 St 1 St 2 St 3 53 LRU算法堆栈调整过程 刚访问过的页号放在栈顶 最久未访问过的放在栈底 1 设t时间点要访问的页号为At 若At不属于堆栈 则At放在栈顶 其余各项下移 2 若At属于堆栈 则取出该页放在栈顶 其余各页下移 3 确定主存分配的页面数n 下移一位 St 1 1 St 1 m At 图1 下移一位 不动 St 1 1 St 1 k St 1 m 堆栈型算法的特点 1 一次模拟 就可求得不同主存页数的命中率 对某一页地址流而言 2 命中率随主存页数的增加而单调上升 54 图4 24使用LRU法对页地址流进行堆栈处理 55 由图4 24的St可确定对应这个页地址流和主存页数n取不同值时的命中率 只要对不同的n值 当At St 1 则命中 当 则不命中 例如 对n 4 其S5 5 1 2 3 因为A6 2 S5 所以命中 但对n 2 其S5 5 1 因为 所以不命中 这样就可算出各个n值的命中率H 如下所示 56 7 页面失效频率算法 PFF 一种动态算法 对LRU算法的改进 基于主存页数n增加 H单调上升 方法 根据各道程序运行中的主存页面失效率 由操作系统动态调节分给各道程序的实页数 实现 当主存页面失效率 X 某个值 时 增加改道程序的主存页数 当主存页面失效率 Y 某个值 时 减少改道程序的主存页数 特点 提高整个系统的主存命中率 提高整个系统的主存利用率 3 虚拟存贮器工作的全过程 58 虚拟存储器工作过程 访问主存 多用户虚地址主存地址页面失效 程序换道 辅存调页 辅存调页 多用户虚地址辅存地址辅存缺页 海量存储器调入 装入主存 I O处理机控制 辅存地址主存地址 查内页表 查外页表 主存页面表 替换算法 59 4 2 3页式虚拟存贮器实现中的问题 1 页面失效的处理 页面失效不能看作是一般的中断 应作为一种故障 立即响应 页面失效要程序换道 故应保存现场及恢复现场 采用后援寄存器 预判技术等 正确选择替换算法 避免指令跨页存放的页来回调度 进进出出 颠簸 正确选择分配给每道程序的页面数 以及每页的大小 60 2 提高虚拟存贮器等效访问速度的措施 缩短访主存的时间 等效访问速度公式TA HTA1 TA2 1 H 一方面要求能有很高的主存命中率 另一方面要求能有尽可能短的访主存时间 在段式或页式虚拟存储器中 要访问主存储器必须先查找段表或页表 在段页式虚拟存储器中 既要查找段表也要查找页表 这样主存储器的访问速度将降低2至3倍 因此要从加快内部地址变换的角度来提高性能 61 a快表与慢表方法 由于在一段时间内对页表的访问只是局限在少数几个存储字内 这样可以把经常访问的页面地址存放在一个小容量的高速存储器中 称为快表 将原先存放全部虚 实地址映象关系的表称为慢表 快表是满表的一部分 快表与慢表同时查找 在快表中找着则慢表结束 快表中没找着 则慢表继续找 同时把此页调入快表 按一定的算法 可是由于快表的容量比较小 命中率低 如果提高快表的容量 则它的查表速度会下降 62 图4 26经快表与慢表实现内部地址变换 63 图4 27减少快表的相联比较位数 省掉用户号 增加用户位 由于上述快表的比较位数较多 而且在一段时间内总是对应于同一个任务或同一个用户 它们的u值是不变的 所以可以让参加比较的位数少一些 以加快时间 64 b快表不采用相连存储器而采用按地址访问的存储器 查找的信息可以使用顺序查找法 对分查找法 散列查找法 对于快表来说 就是要把多用户虚页号Nv变换成快表地址A 函数关系是 A H Nv 65 图4 28经散列实现快表 为什么还需Nv 66 注意 虚拟存储器中的多用户虚地址的位数是固定的 以页式为例说明 IBM370 168计算机的虚拟存储器虚地址共长48位 页面大小为4K 每道程序最多允许有4K个页面 最多允许有16M个用户 用户号位占24位 在一段时间内最多允许有6个用户 所以IBM370 168采用如下方法实现快表 多用户u虚页号Nv 页内位移Nr 67 图4 29IBM370 168虚拟存贮器的快表 在快表的每个地址单元A中存放多个不同的虚页号与实页号的映象关系 68 总结 提高虚拟存储器等效访问速度的措施虚地址至主存地址的变换靠内页表 内页表容量大 一般存放在主存中 每次访问主存 都要多一次访问内页表 为缩短内部地址变换时间 可采用2种方法 a 用小容量快速随机存储器或寄存器来存放页表 b 增设快表 由硬件构成 按内容访问 是页表的一部分 保存当前正在使用的虚实地址映像关系 快表的命中率和查表速度有矛盾 命中率高 要求容量大 查表速度慢 散列方法 让内容与存放该内容的地址建立某种散列函数关系 散列函数表换由硬件实现 快表由按地址访问的高速存储器构成 容量比按内容访问的相联存储器构成的快表的容量大 散列冲突 虚地址经散列函数变换后得到一个单元地址 可该地址单元的内容却不是该虚地址对应的实页号 即出现一对多的情况 69 4 3高速缓冲存贮器 Cache Cache 弥补主存速度 在CPU与主存之间设置的高速 小容量存储器 构成Cache 主存存储层次 速度是Cache的 容量是主存的 70 4 3 1基本结构 Cache和主存等分成相同大小的块 访Cache时间是访主存时间的1 4 1 10 主存与辅存速度之比是1 1000 71 Cache结构特点 Cache操作分两部分 查表地址变换和访问Cache二者时间基本相近 50ns 但可以重叠 流水进行 Cache尽量靠近CPU 减小延迟 发挥Cache高速性 为解决Cache块失效 在CPU与主存之间设有直接通路 一般Cache块的大小等于在一个主存周期内主存所能访问到的字数 因此有Cache的主存系统都采用多体交叉存储器 如IBM370 主存模4交叉 每个分体8个字节宽 所以Cache每块32字节 72 4 3 2地址的映象与变换 地址映象 将每个主存块按什么规则装入Cache中 地址变换 将主存地址变换成Cache地址 块冲突 主存块要进入Cache中的位置已被其它主存块占用 要用替换算法 全相联直接组相联 常用映像方法 73 1 全相联映象和变换 地址映象 在主存中的任何一个块均可以装入到Cache中的任何一个块位置上 图4 33全相联映象规则 74 图4 34全相联映象的地址变换过程 地址变换 目录表 相联比较 用硬件实现 优点 块冲突概率低 缺点 目录表相联存储器大 成本越高 查表速度慢 75 2 直接映象及其变换 主存和Cache都机械等分成相同大小的块后 再将主存空间按物理Cache大小等分成区 地址映象 主存中第i块只能唯一映象到Cache中第imod2ncb Cache的块个数 块位置上 图4 35直接映象规则 76 图4 36直接映象的地址变换过程 地址变换 硬件实现 主存地址中直接产生Cache地址 标志表中比较区号 标志表存储器按地址访问 优点 省硬件 速度快 并行工作 缺点 块冲突率高 77 3 组相联映象及其变换 地址映象 组间直接映象 组内各块全相联映象 实现方法 整个Cache为一个区 主存按Cache大小分成若干个区 区内等分若干组 组内等分若干块 每块由若干个字组成 主存地址字段为 区号 组号 组内块号 块内地址 当组相联映象的组内块数等于Cache的总块数时 就成了全象联映象 当组内只有一个块时 就成了直接地址映像 所以 全相联映象和直接映象是组相联映象的两种极端 地址变换 每组一个目录表 组号直接使用 区号 块号相联比较 硬件实现 组间直接 组内块号全相联 79 图4 37组相联映象规则 80 图4 38组相联地址变换示意图 81 图4 39组相联地址变换的一种实现方式 采用一个按地址访问与按内容访问混合的存储器实现单体多字并行存储器 步骤 1 由q从2q中选出一个单元 同时读出2s个字 2 分别通过2S套外比较电路与主存地址的nd s 进行比较 3 将其中相符的s取出 拼加上q和nmr组成Cache地址nc 4 若都不符合 发生块实效 82 图4 40组相联映象的另一种方案 图4 41组相联另一种方案的地址变换过程 83 4 3 3替换算法的实现 特点 1 发生Cache块冲突时 要用替换算法进行替换 2 可采用与虚存一样的算法 FIFO LRU 3 Cache调块是微秒级 不用程序换道 算法用硬件实现 2种替换算法 1 堆栈法2 比较对法堆栈法 LRU算法硬件实现之一 LRU算法是堆栈型替换算法 栈顶是最近被访问过的页号 依次访问时间变久 栈底是近期最久未访问的页号 1 全相联映象 堆栈大 不适合用硬件实现 方法 设置一个堆栈 堆栈行数 Cache块总数 硬件实现 实现 a刚访问过的Cache块号与堆栈中的块号相联比较 b不想符 此块号入栈顶 其它下移一项 c相符 从栈中取出放入栈顶 此块号到栈顶的部分下移一项 d栈不满时发生块失效 按b做 e栈满后发生块失效 栈底的块号被替换 84 图4 43全相联映象LRU法经堆栈实现 需要有相联比较功能 2 组相联映象 堆栈小 适合用LRU硬件实现 方法 一组一个堆栈 堆栈行数 组内块数 堆栈法需要硬件有相联比较的功能 速度低 成本高 85 2ncb行 ncb位 全相联映象 组间直接 组内全相联 共有2q个堆栈 2s行 Nd S位 86 2 比较对法 LRU算法硬件实现之二 只用一般的门 触发器来实现LRU替换算法 方法 各块两两组和 每对接到一个触发器 用触发器状态表示两块被访问的远近次序 再经门电路就可找到被替换的块 实现 例如 有A B C三块 C为最久未被访问过 则可能的情况是ABC BAC TAB为 1 表示A比B更近被访问过 TAB为 0 表示B比A更近被访问过 因此 比较对触发器 与门 87 分析一下此方法实现时的一些情况 88 4 3 4Cache的写入策略和取算法1 写入策略Cache的地址变换和替换算法是全硬件实现的 Cache对应用程序员 系统程序员是透明的 Cache对CPUM之间的信息交换是透明的 Cache中的内容是主存中一小部分内容的副本 应与主存保持一致 但当发生写入操作时 主存与Cache内容一致性就成为问题 写入操作包括写Cache和写主存 主存可由CPU 通道 I O处理机写入 这就要采用一定的写入策略来解决 89 1 写入Cache命中时 解决主存内容跟踪问题a写回法 CPU只写入Cache 替换时才能把Cache内容送回主存 然后调新块 需要增加修改位 b写直达法 同时写入Cache和主存 单机系统一般采用写回法 节省成本 多机系统多采用写直达法 防止出错 2 Cache写不命中时 是否把写入主存的数据块取到Cache a不按写分配法 只写主存 不调入Cache b按写分配法 写主存 同时调入Cache 多机系统在写入时要保证各CPU的Cache与主存的一致性 采用播写法 控制共享信息和目录表 90 2 Cache的取算法 块调度策略 如何取块可提高命中率 按块取进法 一般采用 方法 Cache块失效时 调块 2 预取算法方法 在访问主存第i块时 预取第i 1块 何时取进该块 有两种方法 a恒预取 只要访问主存第i块 不论Cache是否命中 均预取第i 1块 b不命中时预取 访问主存第i块在Cache中不命中时 预取主存中第i 1块 预取块大小不宜超过256字节 预取命中率与块大小 预取开销有关 块太小预取效果不明显 91 4 4主存保护 1存储区域的保护 1 不能侵犯别的用户的区域 方法有 界限寄存器 页表保护 键式保护 2 保护自己的区域不受侵犯 保护操作系统 方法有 环式保护 2访问方式的保护 由于对信息有读 写 执行的使用方式 可以把他们结合实现访问方式的保护 92 对主存信息的使用可