计算机组织与结构Ch6存储器-Luke.ppt

第6章 存储器 2 第6章目标 掌握层次存储器组织的概念 理解层次存储器的每一级对系统性能的影响 以及如何衡量系统性能 掌握cache存储 虚拟存储 分段 分页和地址转换的概念 3 6 1介绍 存储器是基于存储程序的计算机的核心 本章重点学习存储器的组织及原理 这对于系统性能分析是至关重要 4 6 2存储器类型 两种主存储器 随机存储器 RAM 和只读存储器 ROM 两种类型的RAM 动态RAM DRAM 和静态RAM SRAM 动态RAM由电容器组成 电容器内的电荷随着时间会缓慢丢失 所以它们必须每隔几微秒刷新一次 以阻止数据丢失 由于DRAM设计简单 所以被称为是 便宜的 存储器 5 6 2存储器类型 SRAM通常由D触发器构成 SRAM是非常快的存储器 它不需要像DRAM那样刷新 Cache存储器就是用SRAM构造的 这个我们在后面会详细讨论 ROM也不需要刷新 实际上 它需要很少的电荷来保存信息 ROM用于永久性存储 或者即使当系统关闭后数据仍能保持的半永久存储 6 6 3存储器层次 通常 较快的存储器比较慢的存储器成本高 为了以最少的花费获得最好的性能 存储器以层次方式组织 容量小 速度快的存储部件放在CPU中 较大的 较慢的主存通过数据总线来访问 更大的永久存储器以磁盘的形式或磁带驱动形式存在于远离CPU的位置 7 6 3存储器层次 这种分层存储组织结构被认为是一种金字塔形 8 6 3存储器层次 为了存取数据 CPU首先向它最近的存储器发送请求 通常是cache 如果数据不在cache中 就要询问主存 如果数据不在主存中 就要去询问磁盘 一旦确定了数据的位置 数据和它附近的许多数据单元就被取到cache存储器中 9 6 3存储器层次 相关概念命中 hit CPU请求的数据就驻留在要访问的存储器层中 缺失 miss CPU请求的数据不在要访问的存储器层中 命中率 hitrate 访问某个特定的存储器层时 CPU不到所需数据的百分比 缺失率 missrate 访问某个特定的存储器层时 CPU找不到所需数据的百分比 缺失率 1 命中率 命中时间 hittime 是某个特定的存储器层中 CPU取得所请求数据需要的时间 缺失损失 misspenalty CPU处理一次缺失事件所需时间 其中包括利用新的数据取代上层存储器中的某个数据块所需时间 再加上将所需数据传递给处理器所需的附加时间 10 6 3存储器层次 一个完整的数据块在命中后被复制 根据局部性原理 一旦字节被访问 它附近的数据元素很快也会被访问 局部性的三种形式 时间局部性 最近访问的数据易于在不久的将来再次被访问 空间局部性 对存储器地址空间的访问形成団簇的集中倾向 顺序局部性 访问存储器的指令趋于被顺序访问 11 6 4Cache存储器 cache存储器是通过把最近使用过的数据存放在临近CPU的位置而不把它存储在主存中来提高存取速度 虽然cache比主存小很多 但它的存取速度比主存快很多 和主存不同 主存是通过地址来访问 而cache是靠内容来访问的 所以常常称cache为内容可寻址存储器 因此 并不是cache存储器越大越好 容量太大则查找数据的时间就会很长 12 6 4Cache存储器 主存储器和cache的存储空间都被划分成大小相同的数据块 主存储器的许多块映射到cache的一个块 Cache中的不同块由标记域 tagfield 来区分 存储器地址被划分为多个域 field 如标记域 字域 块域等 这些域为较大的主存和较小的cache存储器之间提供多对一映射关系 命中过程 根据主存地址中的块域找到数据在cache中的位置判别有效位 validbit 比较cache中的标记与主存地址的标记域根据字域找到所需访问的字 13 6 4Cache存储器 最简单的cache映射模式是直接映射 在cache中的N个块和主存中的X个块组成的直接映射 映射关系 Y XmodN 如果cache有10个块 cache的第7块可能含有主存中的第7 17 27 37 块 一旦主存的一个块被复制到cache的对应块中 就要为cache块设置一个有效位 validbit 指示系统该块中含有有效数据 如果没有有效位会发生什么情况 14 6 4Cache存储器 下图是cache的一个示意图 块0含有来自主存储器的多个字 并用标记00000000来进行身份识别 块1用11110101来标记 其它的两个块是无效的 15 6 4Cache存储器 一个存储器地址被分成的每一个域的大小依赖于cache的大小 假如存储器由214个字组成 cache有16 24个块 并且每个块有8个字 这样 存储器就分成了214 23 211个块 主存地址域的划分 4位用于块域 3位用于字域 左面剩下的全部用于标记域 16 6 4Cache存储器 根据上面例子 假如一个程序产生了地址1AA 在14位二进制当中 这个数字是00000110101010 这个地址的开始7位是标志域 接着的4位是块域 并且后3位表明块中的字 17 6 4Cache存储器 如果随后该程序产生的地址是1AB 它将在块0101中寻找数据 字位于快内011位置 然而 如果该程序产生地址3AB 则地址1AA装入的块将会从cache中取出 而用与3AB相关的信息来置换 18 6 4Cache存储器 假如一个程序产生了一系列的存储地址 如1AB 3AB 1AB 3AB cache将持续的取出 并且进行块的替换 在这种极端情况下 cache理论上的优点就不存在了 这是直接映射cache的主要缺点 设计的其它的cache映射方案阻止了这种系统颠簸 19 6 4Cache存储器 不为存储块设置明确的基于主存储器地址的cache位置 我们可以允许一个块存放在cache中的任何块中 用这种方式 在任何块被取走之前 cache必须是填满的 这就是全关联cache的工作原理 一个存储地址仅被分成两个域 标记域和字域 20 6 4Cache存储器 如前面例子 假如有一个14位存储地址和一个拥有16个块的cache 每一个块的大小是8个字 则存储地址格式是 当搜索cache时 并行的搜索所有的标记 来快速检索数据 这需要特殊的 造价高的硬件 21 6 4Cache存储器 回忆一下 无论何时另一个存储器内容需要那个块时 直接映射cache都将把该块删除 对于全相连的cache当中 不存在这种映射关系 所以我们必须设计一种算法来决定哪一个块应该从cache中删除 被删除的块是牺牲块 有许多种方法选择牺牲块 我们将会简要讨论 22 6 4Cache存储器 组关联cache兼备直接映射cache和全关联cache的思想 一个N路固定相连cache映射想直接映射cache 因为一个存储器内容映射到cache中的一个特殊位置 与直接映射cache不同 一个存储内容映射到一组cache块 和全相连cache的工作方式相似 不映射整个cache 存储内容能够映射到的仅是cache空间的子集 23 6 4Cache存储器 在组关联cache中 每一组的cache块数目根据系统的总体设计变化 例如 一个二路的组相连cache能够被概念化成下面的概要图来说明 每一组都含有两个不同的块 24 6 4Cache存储器 在组关联cache映射中 存储内容被划分为三个字段 标志 组 和字 如下所示 像直接映射cache一样 word字段选择cache块中的字 标志字段唯一的标识存储地址 Set字段决定存储块映射到的组 25 6 4Cache存储器 假设我们有一个214字节的主存这个存储器映射到一个拥有16个块 每个块有8个字的一个2路组相连cache 因为这是一个2路cache 每一组由2块组成 有8组 这样 需要3位用于set 3位用于word 余下的左边8位用于tag 26 6 4Cache存储器 对于全关联和组关联cache 当需要从cache中取出一个块时 调用一种置换策略 一个最优置换策略能够预测将来哪一个块最长时间不需使用 虽然执行最优置换算法是不可能的 但是可以作为评价任何其它算法的参考和标准 27 6 4Cache存储器 我们选择的置换策略依赖于我们试图去优化的局部性 常常 我们对时间局部性感兴趣 最近最久未使用算法 LRU 保持跟踪最后一次被评估的块 并且取出最长时间未使用的块 这种方法的缺点是它的复杂性 LRU不得不为每一个块保持访问史 这最终降低了cache的速度 28 6 4Cache存储器 先进先出 FIFO 是一种广泛应用的cache替换策略 在FIFO中 已经在cache中的块最长 不管它是何时被最后使用的 随机置换策略 顾名思义 它随机选取块并且用一个新块替换它 随机置换当然可能取出一个将经常用到或很快就用到的块 但它从来都不会颠簸 thrashes 29 6 4Cache存储器 层次存储器的性能是用它的有效访问时间 EAT 衡量的 EAT是一种考虑命中率和存储器的逐级相关存取时间的加权平均值 一个两级存储器的EAT计算公式如下 EAT H AccessC 1 H AccessMM 其中 H是cache的命中率 AccessC和AccessMM分别是cache和主存的存取时间 30 6 4Cache存储器 例如 考虑一个系统 这个系统主存的存取时间是200ns cache的存取时间是10ns 并且命中率是99 EAT是 0 99 10ns 0 01 200ns 9 9ns 2ns 11ns 这个决定有效存取时间的等式可以扩展到任意级的存储器系统 31 6 4Cache存储器 Cache置换策略必须考虑脏块 dirtyblock 尤其当它们在cache中已经被更新时 脏块一定要再被写回存储器 写策略决定了如何做 有两种类型的写策略 写通 writethrough 和回写 writeback 在每一次写时 写通同时更新cache和主存 32 6 4Cache存储器 仅当块被选中替换时 回写 也称为copyback 才更新存储器 写通的缺点是对于每一次cache写存储器必须更新 这就降低了更新的访问时间 这种降低常常是可以忽略的 因为大多数的存取都是读 不是写 回写的优点是通信量被最小化 但是它的缺点是存储器不总是与cache中的值一致 对于多用户系统 常会发起问题 33 6 5虚拟存储器 凭借着提供较快的存储器存取速度 Cache存储器提高了性能 凭借着提供较大的存储容量 不增加主存的成本 虚拟存储器提高了性能 磁盘驱动器的一部分是为扩展主存服务的 如果一个系统使用页式技术 虚拟存储分区主存储器成各自管理的页桢 当不立即需要它们时 它们就被写道磁盘上 34 6 5虚拟存储器 物理地址是物理存储的实际存储地址 程序产生被存储管理者映射到物理地址的虚拟地址 当逻辑地址需要从磁盘中引入页时 缺页就发生了 当分页过程导致小的 不可用的存储器地址簇时 存储破碎就发生了 35 6 5虚拟存储器 主存和虚拟存储器被分成相等大小的页 一种处理过程需要的整个地址空间 在主存中不立即需要 一些部分可能在磁盘上 而其它的可能在主存中 进一步说 分配给进程的页不必连续存储 或者部分页在磁盘上 或者在存储器中 用这种方法 任何时候 仅仅需要的页在存储器中 不需要的页存储在磁盘当中 36 6 5虚拟存储器 关于每一页的位置的信息 既不在磁盘上 也不在存储器中 而是保留在一种称为页表的数据结构中 如下所示 对于每一活动过程 都有一个页表 37 6 5虚拟存储器 当一种操作产生一个虚拟地址时 操作系统就把它翻译成一个物理存储地址 为了完成这一操作 虚拟地址被分成俩个字段 页字段 和偏移量字段 页字段决定地址的页位置 偏移量表明页中的地址位置 通过在页表中查找 逻辑页码被翻译成一种物理页帧 38 6 5虚拟存储器 如果逻辑地址在页表中的有效位是零 这意味着页不在存储器中 要到磁盘上去存取 这是页发生了错误 如果必要 页需要从存储器中取出 并且被磁盘上检索的页所取代 有效位被设置成1 如果有效位是1 虚拟页的数字被物理桢的数字所取代 把偏移量加到物理桢的数字 来存取数据 39 6 5虚拟存储器 如一个例子 假如一个系统拥有一个8K空间的虚拟地址和一个4K空间的物理地址 系统是用位寻址 我们有213 210 23的虚拟页 虚拟地址13位 8K 213 3位用于页字段 10位用于偏移量 因为页的大小是1024 一个物理存储地址需要12位 开始的两位用于页桢 尾随的10位是偏移量 40 6 5虚拟存储器 假如我们有下面的页表 Whathappens当CPU产生地址545910 10101010100112时 会发生什么 41 6 5虚拟存储器 地址10101010100112转化成物理地址为010101010011因为通过再也表中查找 页字段101被桢的数字01取代 42 6 5虚拟存储器 当CPU产生地址10000000001002时会发生什么 43 6 5虚拟存储器 我们早就说过有效存取时间 EAT 需要考虑存储器的所有级 这样 在计算当中 虚拟存储器也是一个因素 我们也不得不考虑页表的存取时间 假如一个主存的存取需要200ns 页的出错率为1 它花费10ms从磁盘中装入一页 我们有 EAT 0 99 200ns 200ns 0 01 10ms 100 396ns 44 6 5虚拟存储器 即使没有页错误 EAT将是400ns 因为存储器总是读两次 第一次存取页表 第二次从存储器中装入页 因为页表的读始终都是一样的 所以保持它们在一个特殊的称为翻译旁视缓冲 TLB 的寄存器中 是有意义的 TLBs是一种特殊相关寄存器 这种寄存器将虚拟页的映射存储到物理页 下一张幻灯片展示这些部件是如何协调工作的 45 6 5虚拟存储器 46 6 5虚拟存储器 虚拟存储器的另一种方法是使用分段 不将存储器分成相等大小的页 虚拟地址空间被分成可变长度的段 常常在程序员的控制之下 通过段表的入口 一个段被定位 它含有段的存储位置和一个表明它大小的界限 发生缺页时 操作系统在存储器中寻找一个足够大的位置存放从磁盘中检索到的段 47 6 5虚拟存储器 分页和分段都会引起碎片 分页产生的是内部碎片 因为一个进程不可能恰好需要一页当中含有的全部地址空间 这样 许多页含有存储器中未用过的碎片 分段产生的是外部碎片 在进行分段配置和解除分段时 存储器中的自由空间块会变得残缺不完整 最后导致有许多长度较小的自由空间块都不足以存放一整段程序 4