第7章 存储系统.ppt

1 第七章存储系统 2 7 1存储系统的层次结构 CPU CACHE 主存 内存 辅存 外存 根据各种存储器的存储容量 存取速度和价格比的不同 将它们按照一定的体系结构组织起来 使所放的程序和数据按照一定的层次分布在各种存储器中 3 7 1存储系统的层次结构 图7 1三层次存储系统 4 1 主存和高速缓存之间的关系 Cache引入 为解决CPU和主存之间的速度差距 提高整机的运算速度 在CPU和主存之间插入的由高速电子器件组成的容量不大 但速度很快的存储器 Cache特点存取速度快 容量小 存储控制和管理由硬件实现Cache工作原理 程序访问的局部性在较短时间内由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内 数据分布不如指令明显 但对数组的访问及工作单元的选择可使存储地址相对集中 CPU与Cache之间的数据交换是以字为单位 而Cache与主存之间的数据交换是以块为单位 一个块是由若干字组成 是定长的 5 2 主存与辅存之间的关系 主存 半导体存储器组成 优 速度快缺 容量受限 单位成本高 断电丢失信息 辅存 光盘 磁盘 优 容量大 信息长久保存 单位成本低 缺 存取速度慢CPU正在运行的程序和数据存放在主存暂时不用的程序和数据存放在辅存 辅存只与主存进行数据交换 6 7 2高速缓冲存储器 组成 小容量的SRAM和高速缓存控制器组成 功能 将CPU当前快要用到的部分数据块由主存复制到容量小 速度快的SRAM中 由SRAM向CPU直接提供它所需要的数据 Cache存储器介于CPU和主存之间 它的工作速度数倍于主存 全部功能由硬件实现 由于转换速度快 软件人员丝毫未感到Cache的存在 这种特性称为Cache的透明性 Cache内部是用同主存内部同样大小的块组成 故由于Cache存储容量小 所以块的数目少 在Cache中 每一块外加有一个标记 指明它是主存的哪一块的副本 所以该标记的内容相当于主存中块的编号 块内字节数与主存相同 如图7 2 7 图7 2cache的基本结构 8 7 2 1Cache的组成和工作原理 标志块号块内地址 主存地址 主存 块号块内地址 Cache标记 Cache地址 比较器 替换算法 Cache数据 来 去CPU 来自CPU 不命中 命中 Cache满 访数据 修改标记 访标记 9 7 2 1Cache的组成和工作原理 命中率 CPU所要访问的信息在cache中的比率 命中率的高低与cache容量大小 程序的特征 cache的调度算法有关 cache存储器的平均存取时间计算如下 平均访问时间 h tc 1 h tc tM 其中tc为cache存储器的存取时间 h为命中率 tM为主存储器的存取时间 10 7 2 2Cache存储器组织1 地址映像为了把信息放到Cache存储器中 必须应用某种方法把主存地址定位到Cache中 称作地址映像 在信息按照这种映像关系 采用硬件方法实现 装人Cache后 执行程序时应将主存地址变换成Cache地址 这个变换过程叫做地址变换 地址的映像和变换是密切相关的 下面介绍几种基本地址映像方式 它们是直接映像 全相联映像和组相联映像等 11 1 直接映像在直接映像方式中 主存和Cache中字块的对应关系 如图7 3所示 直接映像函数可定义为 j imod2c其中j是Cache的字块号 i是主存的字块号 主存中有2m个块 字块大小为2b字 Cache中有同样大小的2c个块 在这种映像方式中主存的第0块 第2c块 第2c 1块 只能映像到cache的第0块 而主存的第1块 第2c 1块第2c 1十1块 只能映像到Cache 的第1块 12 直接映像的优点是实现简单 只需利用主存地址按某些字段直接判断 即可确定所需字块是否已在Cache存储器中 如图7 3 直接映像方式的缺点是不够灵活 即主存的2t个字块只能对应唯一的Cache存储器字块 因此 即使Cache存储器别的许多地址空着也不能占用 这使得cache存储空间得不到充分利用 并降低了命中率 13 14 例如某机主存为1MB 划分2048页 每页512B 共分0 127组 每组16页 Cache为8KB 划分16页 每页512B7位Cache主存主存地址0组7位4位9位1组主存页号Cache地址127组在访存时 只需比较两者标记 如相同则命中 15 2 全相联映像全相联映像方式是最灵活但成本最高的一种方式 如图7 4所示 它允许主存中的每一个字块映像到cache存储器的任何一个字块位置上 也允许从确实已被占满的Cache存储器中替换出任何一个旧字块 这是一个理想的方案 实际上由于它的成本太高而不能采用 不只是它的标记位数从t位增加到t c位 与直接映像相比 使Cache标记容量加大 主要问题是在访问Cache时 需要和Cache的全部标记进行 比较才能判断出所访主存地址的内容是否已在Cache中 由于Cache速度要求高 所以全部 比较 操作都要用硬件实现 通常由 按内容寻址的 相联存储器完成 见7 4相联存储器 所需逻辑电路甚多 以致无法用于Cache中 16 17 例如某机主存为1MB 划分2048页 每页512B Cache为8KB 划分16页 每页512B 11位Cache主存主存地址11位9位主存页号由于每个Cache页可以映射2048个主存页中的任一页 因此每页的Cache标记也需要11位 已表明它现在所映象的主存页号 18 3 组相联映像组相联映像方式是直接映像和全相联映像方式的一种折衷方案 组相联映像Cache组织如图7 5所示 组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间 当r 0时 它就成为直接映像方式 当r c时 就是全相联映像方式 Cache的命中率除了与地址映像的方式有关外 还与cache的容量有关 cache容量大 则命中率就高 但达到一定容量后 命中率的提高就不明显了 19 20 例如某机主存为1MB 划分2048页 每页512B 共分0 255组 每组8页 Cache为8KB 划分16页 每页512B 共为8组 每组2页 8位Cache主存主存页标记0组7位3位1位9位1组0组Cache地址1组7组255组访存时根据主存地址的中间4位 找到Cache页 并将其标记与主存页标记进行比较 判断是否是主存中的副本 即访问是否命中 21 2 Cache的读写操作 写贯穿 全写法 同时写入Cache和主存 保证主存和Cache内容相同 方法简单可靠 对Cache的更新同时要写主存 速度会受影响 写回法 先将更新内容写入Cache 并做标记 特定时间将Cache内容写入主存 省去不必要的立即回写操作 回写式系统机构比较复杂 写一次法 写命中与未命中的处理方法与写回法基本相同 只是第一次写命中是要同时写入主存 Pentium机的L2级Cache采用的是写回法 L1级数据Cache采用的是写一次法 22 3 替换算法当新的主存字块需要调人cache存储器而它的可用位置又已被占满时 就产生替换算法问题 先介绍两种替换算法先进先出 FIFO 算法和近期最少使用 LRU 算法 FIFO算法总是把一组中最先调入cache存储器的字块替换出去 它不需要随时记录各个字块的使用情况 所以实现容易开销小LRU算法是把一组中近期最少使用的字块替换出去 这种替换算法需随时记录cache存储器中各个字块的使用情况 以便确定那个字块是近期最少使用的字块 LRU替换算法的平均命中率比FIFO要高 并且当分组容量加大时 能提高LRU替换算法的命中率 LRU是最常使用的一种算法 其设计思想是把组中各块的使用情况记录在一张表上 如图7 6所示 并把最近使用过的块放在表的最上面 这种算法用硬件实现比较麻烦 经常采用修改型LRU算法 另外还有一种随机替换法 RAND 这种算法不考虑使用情况 在组内随机选择一块来替换 其性能比根据使用情况的替换算法要差些 23 高速缓冲存储器 续 2 替换算法常用的替换算法大致有以下两类 1 先进先出算法 FIFO FIFO按调入Cache的先后决定淘汰的顺序 即在需要更新时 总是淘汰最先调入Cache的页面内容 这种方法容易实现 系统开销少 但不一定合理 因为有些内容显然调入较早 但可能仍在使用 2 近期最少使用算法 LRU 为Cache各页建立一个LRU目录记用它的调用情况 当需要替换时将在最近一段时间内使用最少的页面内容予以替换 该算法命中率高 但较FIFO算法复杂 系统开销大 24 2 2 2 2 2 2 2 2 11 11 11 11 11 4 4 9 9 9 9 3 7 7 7 7 高速缓冲存储器之替换算法 续 例 设一个容量为4个块的全相联Cache 分别采用FIFO和LRU替换算法 假定访问的主存地址块号序列为2 11 2 9 7 6 4 3 画出每次访问后Cache中的内容变化情况 解 访问顺序12345678地址块号211297643块分配情况 FIFO 操作状态调进调进命中调进调进替换替换替换 续 25 高速缓冲存储器之替换算法 续 访问顺序12345678地址块号211297643近期最少使用 LRU 操作状态调进调进命中调进调进替换替换替换 2 2 2 2 2 2 4 4 11 11 11 11 6 6 6 9 9 9 9 3 7 7 7 7 26 7 2 3Cache的命中率 设NC表示Cache完成存取的总次数 Nm表示主存完成存取的总次数 h定义为命中率 则有h NC NC Nm 若tc表示命中时的Cache访问时间 tm表示未命中时的主存访问时间 1 h表示未命中率 则Cache 主存系统的平均访问时间ta为 ta htc 1 h tm设r tm tc表示主存慢于Cache的倍率 e表示访问效率则有e tc tm tc htc 1 h tm 1 h 1 h r 1 r 1 h 为提高访问效率 h接近1好 27 例题 CPU执行一段程序时 Cache完成存取的次数为1900次 主存完成存取的次数为100次 已知Cache存取周期为50ns 主存存取周期为250ns 求Cache 主存系统的效率和平均访问时间 解 h NC NC Nm 1900 1900 100 0 95r tm tc 250ns 50ns 5e 1 r 1 r h 1 5 1 5 0 95 83 3 ta tc e 50ns 0 833 60ns 28 7 2 4多层次Cache存储器1 指令Cache和数据Cache开始实现Cache时 是将指令和数据存放在同一Cache中的 后来随着计算机技术的发展和处理速度的加快 存取数据的操作经常会与取指令的操作发生冲突 从而延迟了指令的读取 发展的趋势是将指令Cache和数据Cache分开而成为两个相互独立的Cache 2 多层次Cache结构当芯片集成度提高后 可以将更多的电路集成在一个微处理器芯片中于是近年来新设计的快速微处理芯片都将Cache集成在片内 片内cache的读取速度要比片外Cache快得多 Pentium微处理器的片内包含有8KB数据Cache和8KB指令Cache Cache行的长度为32B 采取两路组相联组织 29 片内Cache的容量受芯片集成度的限制 一般在几十KB以内 因此命中率比大容量cache低 于是推出了二级Cache方案 其中第一级Cache L1 在处理器芯片内部 第二级Cache L2 在片外 其容量可从几十KB到几百KB 采用SRAM存储器 两级cache之间一般有专用总线相连 Pentium微处理器支持片外的第二级Cache 其容量为256KB或512KB 也是采用两路组相连方案 3 Cache的一致性问题 30 7 3虚拟存储器 1 虚拟存储器的名称和由来虚拟存储器只是一个容量非常大的存储器的逻辑模型 不是任何实际的物理存储器 它是借助磁盘等辅助存储器来扩大主存容量 使之为更大或更多的程序所使用 有了虚拟存储器 用户无需考虑所编程序在主存中是否放得下或放在什么位置等问题 产生 软件需要 芯片工艺及价格不能满足特点 1 将当前和常用到的内容放在主存中 其他还未用到的放在外存中 2 虚拟存储体系允许用户访问比实际存储空间大得多的地址空间 概念 位于主存 辅存的物理结构 由负责信息划分以及主存 辅存之间信息调动的辅助硬件和操作系统中的存储管理软件所组成的存储体系 管理方式 段式 页式 段页式 31 从原理角度看 主存 辅存层次和cache 主存层次有很多相似之处 它们采用的地址变换及映像方法和替换策略 从原理上看是相同的 虚拟存储系统所采取的映像方式同样有全相联映像 组相联映像和直接映像等 替换算法也多采用LRU算法 主存一辅存层次的信息传送单位可采用几种不同的方案 段 页或段页式 7 3 1段式管理方案段是利用程序的模块化性质按照程序的逻辑结构划分成的多个相对独立部分 例如过程 子程序 数据表 阵列等 段作为独立的逻辑单位可以被其他程序段调用 这样就形成段间连接 产生规模较大的程序 一般用段表来指明各段在主存中的位置 如图712所示 每段都有它的名称 用户名称或数据结构名或段号 段起点 段长等 段表本身也是主存储器的一个可再定位段 32 段式管理方案 段号起始位置有效位段长访问方式 以程序的逻辑结构所形成的段作为主存分配单位的存储器管理方式 段大小可以不相等 每个程序有一个段表 33 把主存按段分配的存储管理方式称为段式管理 段式管理系统的优点是段的分界与程序的自然分界相对应段的逻辑独立性 使它易于编译 管理 修改和保护 也便于多道程序共享 其缺点是容易在段间留下许多空余的零碎存储空间 造成浪费和段的起点和终点不定 7 3 2页式管理方案页式管理系统的信息传送单位是定长的页 主存的物理空间也被划分为等长的固定区域 称为页面 新页调人主存也很容易掌握 只要有空白页面就可 它比段式管理系统的空间浪费要小得多 页式管理系统的缺点正好和段式管理系统相反 由于页不是逻辑上独立的实体 所以处理保护和共享都不及段式来得方便 图713表示某个程序有5页 逻辑页号0 4 各页分别装入主存不连续的页面位置 用页表记录逻辑页号及其所对应的实主存页号 页表是由操作系统建立的 图713中逻辑页号013已分配实主存空间 所以装人位为l 34 页式管理方案 将虚拟空间和主存空间划分成大小固定的页 以页为分配单位的存储管理方式 页的大小随机器而异每道程序拥有一个页表页表自动生成 对程序员透明 35 36 37 3 段页式 将段式和页式管理方式结合起来 段页式将实际存储器机械等分成固定大小的页 程序则按模块分段 每段又分成与主存页面大小相同的页 段页式管理兼有段式和页式的优点 38 图7 16段页式存储举例 39 40 Pentium采用段页式地址转换机制 通过段地址查阅段表 将表中地址与位移地址相加后得到32位线性地址 然后通过页面转换得物理地址 页面转换是通过页目录和页表实现的 相当于H级页表 线性地址由页目录 10垃 页号 l位 和位移地址 l位 组成 页面大小为4KB Pentium还允许将页面大小设置为4MB 此时页面转换只要查一次页表即可 Pentium存储器结构有很大灵活性 根据其段表和页表是否设置可以有4种组合情况 1 无段表和无页表的存储器 非虚拟存储器其逻辑地址即为物理地址可减少复杂性 在高性能的控制机中经常被采用 2 无段表和有页表的存储器 页式虚拟存储器 此时存储器的管理和保护是通过页面转换实现的 3 有段表和无页表的存储器 段式虚拟存储器 4 有段表和有页表的存储器 段页式虚拟存储器 41 7 3 6存储管理部件 MMU 现代计算机一般都有辅助存储器 但具有辅存的存储系统不一定是虚拟存储系统 虚拟存储系统有两大特 1 允许用产用比主存空间大得多的空间来访问主存 2 每次访存都要进行虚实地址的转换 Pentium的虚拟地址被称为逻辑地址 其长度为48位 由16位段地址和32位位移地址构成 段地址中有2位用于存储保护 真正属于段地址的是14位 所以有效的逻辑地址为46位 即 14位十32位 虚拟空间为246 42 43 7 4相联存储器相联存储器不按地址访问存储器 而按所存数据字的全部内容或部分内容进行查找 或检索 例如 在虚拟存储器中 将虚地址的虚页号与相联存储器中所有行的虚页号进行比较 若有内容相等的行 则将其相应的实页号取出 这是按数据字的部分内容进行检索的例子80年代后 由于集成电路的迅速发展 才使得半导体相联存储器有条件作为商品上市 44 7 4相联存储器相联存储器除了应用于虚拟存储器与Cache中以外 还经常用于数据库与知识库中按关键字进行检索 从按地址访问的存储器中检索出某一单元 平均约进行m 2次操作 m为存储单元数 而在相联存储器中仅需要进行一次检索操作 因此大大提高了处理速度 近年来相联存储器用于一些新型的并行处理和人工智能系统结构中