计算机系统结构第四章ppt课件.ppt

第四章存贮体系 4 1存贮体系的形成与性能4 2虚拟存贮器4 3高速缓冲存贮器 1 1 存贮体系的形成与性能 从用户的角度来看 存储器的三个主要指标是 容量 速度 价格 每位价格 存贮容量 SM W l m其中W 存贮体的字长 位或字节 l 每个存贮体的字数 m 并行工作的存贮体个数 2 存贮器的速度可用访问时间TA 存贮周期TM 频宽 也称带宽 BM来描述 访问时间TA 存贮器从接到访存申请 到信息被读到数据总线上所需的时间 存贮周期TM 连续启动一个存贮体所需要的时间间隔 一般比TA大 速度 3 频宽 存储器频宽 存储器可提供的数据传送速率 即每秒钟传送的信息位数最大频宽BM 存储器连续访问时能提供的带宽 单体最大频宽 BM W TMm个存储体并行工作的最大带宽 BM W m TM其中W 存贮体的字长 位或字节 m 并行工作的存贮体个数 每位价格c C SM其中C 总价格 SM 位数 4 这三个指标相互矛盾 5 2 并行主存系统频宽的分析 频带宽度 单位时间内所能访问的数据量 字长为W位的单体主存 最大频宽BM W TM 6 最大频宽BM 4W TM m为一个主存字所包含的CPU字数 7 CPU字在主存中可按模m交叉编址 m为分体体数 Mi体的编址模式为 m i j 其中i 0 1 2 l 1 j 0 1 2 m 1 8 并行主存系统 能并行读出多个CPU字的单体多字和多体单字或多体多字的交叉存贮系统 多体单字与单体多字比较 前者花费的器件和总价格并不比后者多多少 但其实际频宽却可以比较高 为单体单字的m倍 单体多字方式要求可并行读出的m个字必须是地址顺序的且处于同一主存单元 而多体单字则可并行读出地址不连续的主存字 多体单字方式的各存贮体可以同时启动也可以分时启动 9 采用多种存贮器技术 构成存贮层次 3 存贮体系的形成与分支 10 一般来说 Cache 主存 层次 由Cache和主存贮器构成 主要目的 提高存贮器速度 主存 辅存 层次 由主存和磁盘存贮器构成主要目的 扩大存贮器容量 11 Cache 主存 层次的实现 主要借助于辅助硬件 从CPU看 速度是CACHE的 容量是主存的 12 主 辅存 层次的实现 主要借助于辅助软硬件 从整体上看 速度是主存的 容量是辅存的 13 主要由软件实现 硬件为辅 Cache 主存 与 主存 辅存 层次的区别 14 4 程序局部性原理 程序的局部性 时间上的局部性和空间上的局部性 时间局部性指的是 在最近的未来要用到的信息很可能是现在正在使用的信息 空间局部性指的是 在最近的未来要用到的信息很可能是与现在正在使用的信息在程序空间上是相邻或相近的 15 16 5 存贮体系的性能参数 存贮系统的单位容量平均价格 计算公式 总希望每位平均价格能接近于C2 辅存 为此应使 S2 S1 其中 Ci为Mi的每位价格 Si为Mi的以位计算的存贮容量 每位价格C 命中率H 等效访问时间TA 17 命中率定义 在M1存贮器中访问到的概率 存贮系统的等效访问时间 TA HT1 1 H T2 N1 M1的访问次数 N2 M2的访问次数 当命中率H 1时 T T1 18 存贮系统的访问效率e 存贮系统的访问效率主要与命中率和两级存贮器的速度之比有关 例 假设T2 5T1 在命中率H为0 9和0 99两种情况下 分别计算存贮系统的访问效率 解 当H 0 9时 e1 1 0 9 5 1 0 9 0 72当H 0 99时 e2 1 0 99 5 1 0 99 0 96 19 4 2虚拟存贮器 VirtualMemory 1961年英国曼彻斯特大学Kilburn等人提出 70年代广泛地应用于大中型计算机系统中 Kilburn 特点 虚拟存贮器指的是 主 辅存 层次 它能使计算机具有辅存的容量 接近于主存的速度和辅存的每位成本 使得程序员可以按比主存大得多的空间来编制程序 即按虚存空间编址 20 虚拟存贮器管理方式地址的映象和变换方法页面替换算法及其实现方法提高主存命中率的方法 本节概述 21 1 虚拟存贮器管理方式 地址变换 在程序运行时 把虚地址变换成主存实地址 根据地址映象和变换方法不同 有三种虚拟存贮器 段式虚拟存贮器 页式虚拟存贮器 段页式虚拟存贮器 虚存通过增设地址映像表机构来实现程序在贮存中的定位 这种定位技术是把程序分割成较小的段或页 用相应的映像表机构来指明该程序的某段或某页是否装入主存 22 段式虚拟存储贮器地址映象方法 每个程序段都从0地址开始编址 长度可长可短 可以在程序执行过程中动态改变程序段的长度 23 由用户程序号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移D相加就能得到主存实地址 地址变换方法 24 段式虚拟存贮器的主要优点 1 程序的模块化性能好 2 便于程序和数据的共享 3 便于实现信息保护 段式虚拟存贮器的主要缺点 1 地址变换所花费的时间比较长 做两次加法运算 2 主存贮器的利用率往往比较低 3 对辅存 磁盘存储器 的管理比较困难 段式虚拟存贮器的主要优缺点 25 段式存贮分配算法 首先分配法 最佳分配法 26 页式虚拟存贮器把虚拟地址空间划分成一个个固定大小的块 每块称为一页 把主存贮器的地址空间也按虚拟地址空间同样的大小划分为页 页是一种逻辑上的划分 它可以由系统软件任意指定 虚拟地址空间中的页称为虚页主存地址空间中的页称为实页 页式虚拟存贮器 27 一个主存地址A由两部分组成 实页号p和页内偏移d 一个虚地址Av由三部分组成 程序号U 虚页号P和页内偏移D 28 虚页号 实页号 页表 29 每个程序使用一个基址寄存器 通过程序号U可找到与这个程序对应的基址寄存器 从中读出页表起始地址 访问这个页表地址 把得到的主存页号p与虚地址中的页内偏移直接拼接起来得到主存实地址 30 页式虚拟存贮器的主要优点 1 主存贮器的利用率比较高 2 页表相对比较简单 3 地址变换的速度比较快 4 对磁盘的管理比较容易 页式虚拟存贮器的主要缺点 1 程序的模块化性能不好 2 页表很长 需要占用很大的存储空间 例如 虚拟存储空间4GB 页大小1KB 则页表的容量为4M字 31 段页式虚拟存贮器用户程序按段编写 每个程序段分成几个固定大小的页 32 段页式虚拟存贮器的地址变换方法 1 先查段表 得到该程序段的页表起始地址和页表长度 2 再查页表找到要访问的主存实页号 3 最后把实页号p与页内偏移d拼接得到主存的实地址 段页式虚拟存贮器的地址变换 33 2 地址映像和变换 地址映象 是指某一数据在主存中的地址与在虚存中的地址两者之间的对应关系 页面争用 实页冲突 两个以上的虚页想要进入主存中同一页面位置的现象 映象方式的选择应考虑能否尽量减少实页冲突概率 34 每道程序任何虚页可映像到任何实页位置 全相联映像 每道程序的任何虚页可以映像装入到任何实页位置 主存 虚存 35 地址变换过程 把某用户虚地址中U与P拼接起来 相联访问目录表 读出主存实页号p 把p与多用户虚地址中的D拼接得到主存实地址 如果相联访问失败 发出页面失效请求 目录表 用一个小容量高速存贮器存放页表 36 目录表的主要优点 与页表放在主存中相比 查表速度快 不用设置装入位 目录表的主要缺点 可扩展性比较差 主存储器容量增加时 目录表的造价高 速度降低 37 对虚拟存储器来说这个虚地址也仅是辅存的逻辑地址 辅存的实地址如下 外部地址变换 虚拟存储器中还有虚拟地址到辅存实地址的转换 外页表内页表 38 外部地址变换过程 在操作系统中 把页面失效当作一种异常故障来处理 每个用户程序有一张外页表 虚拟地址空间中的每一页 在外页表中都有对应的一个存储字 每一个存储字除了磁盘存储器的地址之外 至少还包括一个装入位 39 3 页面替换算法 随机法 Random RAND法 先进先出法 First InFirst Out FIFO法 近期最少使用法 LeastRecentlyUsed LRU法 最优替换算法 OPTOPTimalreplacemantalgorithm 40 页面替换发生时间 当发生页面失效时 要从磁盘中调入一页到主存 如果主存所有页面都已经被占用 必须从主存储器中淘汰掉一个不常使用的页面 以便腾出主存空间来存放新调入的页面 评价页面替换算法好坏的标准 一是命中率要高 二是算法要容易实现 41 随机算法 RANDRandomalgorithm 用随机数确定要替换的块 特点 算法简单 容易实现 未利用历史信息 未反映程序的局部性 命中率低 先进先出算法 FIFOFirst InFirst Out 替换最早装入主存的页 特点 比较容易实现 利用了历史信息 没有反映程序的局部性 最先调入主存的页面 很可能也是经常要使用的页面 42 近期最少使用算法 LFULeastRecentlyUsed 依据各块使用的情况 选择最近最少使用的块替换 特点 既充分利用了历史信息 又反映了程序的局部性 实现起来非常困难 最优替换算法 OPTOptimalreplacemant 是一种理想化的算法 用来作为评价其它页面替换算法好坏的标准 在虚拟存储器中 一般采用FIFO和LRU两种算法 43 举例说明 设有一道程序 有1至5共五页 执行时的页地址流 即执行时依次用到的程序页页号 为 2 3 2 1 5 2 4 5 3 2 5 2若分配给该道程序的主存有3页 分别采用FIFO和LRU替换算法表示这3页的使用和替换过程 44 时间t123456789101112页地址流232152453252 先进先出FIFO 调进 调进 调进 命中 替换 替换 替换 替换 命中 命中 替换 替换 2 2 3 2 3 2 2 3 1 3 1 5 5 1 2 5 2 4 2 4 5 2 4 3 3 4 2 3 4 5 3 5 2 命中 命中 命中 命中3次 近期最少使用LRU 2 调进 2 3 调进 2 3 2 命中 2 3 1 调进 2 1 5 替换 5 1 2 命中 2 5 4 替换 2 4 5 命中 5 4 3 替换 3 5 2 替换 3 2 5 命中 5 2 3 命中 命中 命中 命中 命中 命中 命中5次 2 45 存储单元替换时应注意防止出现颠簸现象 即调入一块时将另一块调出 紧接着又需要访问刚刚调出块的数据 而将该块调入时又将上一块调出 即颠簸 例2 一个循环程序 依次使用P1 P2 P3 P4四个页面 分配给这个程序的主存页面数为3个 FIFO LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示 颠簸 46 在FIFO和LRU算法中 总是发生下次就要使用的页面本次被替换出去的情况 这就是 颠簸 现象 说明命中率与页地址流有关 47 例3 对于一个全相联Cache 假定访问的地址块号序列为1 2 3 4 1 2 5 1 2 3 4 5 在FIFO替换方式下 分别写出分配给程序的主存页面是3页和4页的情况下 其队列的变化情况 并得出结论 48 结论 FIFO算法不是堆栈型算法 主存页数增加 命中率反而下降 49 4 堆栈型替换算法 定义 对任意一个程序的页地址流作两次主存页面数分配 分别分配m个主存页面和n个主存页面 并且有m n 如果在任何时刻t 主存页面数集合Bt都满足关系 Bt m Bt n 则这类算法称为堆栈型替换算法 堆栈型算法的基本特点 随着分配给程序的主存页面数增加 主存的命中率也提高 至少不下降 50 5 虚拟存储器工作的全过程 51 6 提高虚拟存贮器等效访问速度的措施 造成虚拟存储器速度降低的主要原因 1 要访问主存储器须先查段表或页表 2 可能需要多级页表 快慢表 快表TLB TranslationLookasideBuffer 采用一个小容量的高速的相关存储部件 用来存放当前最经常用到的那一部分页表 采取按内容相联方式进行访问 慢表 当快表中查不到时 从存放在主存储器中的慢表中查找 按地址访问 用软件实现 快表与慢表也构成了一个两级存储系统 52 快表的内容包括两部分即虚地址与实地址的对应关系 53 散列函数 目的 把相联访问变成按地址访问 从而加大快表容量 采用散列变换实现快表按地址访问避免散列冲突 采用相等比较器 地址变换过程 相等比较与访问存储器同时进行 54 散列 Hashing 函数 Ah H Pv 55 1 程序执行过程中的页地址流分布情况 2 所采用的页面替换算法 3 页面大小 4 主存储器的容量 5 所采用的页面调度算法 以下 对后三个因素进行分析 7 影响主存命中率的主要因素 56 页面大小为某个值时 命中率达到最大 页面大小与命中率的关系 当页面大小增大时 造成的浪费也要增加 当页面大小减小时 页表和页面表在主存储器中所占的比例将增加 S 分配给某道程序的贮存容量 57 主存容量与命中率的关系 主存命中率H随着分配给该程序的主存容量S的增加而单调上升 在S比较小的时候 H提高得非常快 随着S的逐渐增加 H提高的速度逐渐降低 当S增加到某一个值之后 H几乎不再提高 58 页面调度方式与命中率的关系 请求式 当使用到的时候 再调入主存 预取式 在程序重新开始运行之前 把上次停止运行前一段时间内用到的页面先调入到主存储器 然后才开始运行程序 可以避免在程序开始运行时 频繁发生页面失效的情况 如果调入的页面用不上 浪费了调入的时间 占用了主存资源 59 4 3高速缓冲存贮器 Cache 基本工作原理地址映象与变换方法 60 1基本工作原理 CPU速度与主存速度差异 Cache全部用硬件调度 对所有程序员都是透明的 从CPU看 速度是CACHE的 容量是主存的 61 Cache存贮器基本结构 Cache存储体 地址转换部件 替换部件 62 2Cache 主存地址映象与变换方法 地址映象 把存放在主存中的程序按照某种规则装入到Cache中 并建立主存地址与Cache地址之间的对应关系 地址变换 当程序已经装入到Cache之后 在实际运行过程中 把主存地址变换成Cache地址 在选取地址映象方法要考虑的主要因素 地址变换的硬件容易实现 地址变换的速度要快 Cache空间利用率要高 发生块冲突的概率要小 63 全相联映象 全相联 主存中的任一块可以被映像到Cache中的任意一个位置 Cache常包含几百个块 主存常包含几百万个块 优点 命中率较高 Cache的存储空间利用率高 缺点 线路复杂 成本高 速度低 64 直接映象 1 主存与缓存分成同样大小的块 2 主存容量应是缓存容量的整数倍 将主存空间按缓存的容量分成区 主存中每一区的块数与缓存的总块数相等 主存中某区的一块存入缓存时只能存入缓存中块号相同的位置 直接相联的地址映象规则 直接映象公式 b AmodC B b Cache的块号A 主存的块号C B Cache的块数 65 循环分配 直接映象 主存中的每一块只能被放置到Cache中唯一的一个位置 优点 线路简单 缺点 命中率低 66 组相联映象方式 组相联的映象规则 1 主存与缓存分成相同大小的块 2 主存容量是缓存容量的整数倍 将主存空间按缓存的大小分成区 主存中每一区的组数与缓存的组数相同 3 组间直接相联 组内全相联 67 组相联 主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置 68 组相联是直接映象和全相联的一种折衷 组间直接相联 组内全相联 69 组相联映象方式的优点 块的冲突概率比较低 块的利用率大幅度提高 块失效率明显降低 组相联映象方式的缺点 实现难度和造价要比直接映象方式高 70 段相联映象方式 段相联映象方式也是全相联与直接相联的一个折中方案 71 由于多个用户对主存的共享 就有多个用户程序和系统软件存于主存中 要防止由于一个用户程序出错而破坏其他用户的程序和系统软件 还要防止一个用户程序不合法地访问不是分配给它的主存区域 为此 系统应提供存贮保护 4 5主存保护 存贮保护主要包括两个方面 存贮区域保护非虚拟存储区域保护虚拟存储区域保护访问方式保护 72 非虚拟存储区域保护 对于不是虚拟存储器的主存系统可采用界限寄存器方式 由系统软件经特权指令设置上 下界寄存器为每个程序划定存储区域 禁止越界访问 由于用户程序不能改变上 下界的值 所以它如果出现错误 也只能破坏该用户自身的程序 侵犯不到别的用户程序及系统软件 界限寄存器方式只适用于每个用户占用一个或几个连续的主存区域 73 虚拟存储系统存储区域保护 在虚拟存储系统中 由于一个用户程序的各页能离散地分布于主存中 不