1、第第6章章存储器2第第6章章 目标目标 掌握层次存储器组织的概念。理解层次存储器的每一级对系统性能的影响，以及如何衡量系统性能。掌握cache存储、虚拟存储、分段、分页和地址转换的概念。36.1 介绍介绍 存储器是基于存储程序的计算机的核心。本章重点学习存储器的组织及原理，这对于系统性能分析是至关重要。46.2存储器类型存储器类型 两种主存储器：随机存储器（RAM）和只读存储器（ROM）。两种类型的 RAM：动态RAM(DRAM)和静态RAM(SRAM)。动态RAM由电容器组成，电容器内的电荷随着时间会缓慢丢失，所以它们必须每隔几微秒刷新一次，以阻止数据丢失。由于DRAM 设计简单，所以被称为
2、是“便宜的”存储器。56.2存储器类型存储器类型 SRAM通常由D 触发器构成。SRAM 是非常快的存储器，它不需要像DRAM那样刷新。Cache存储器就是用SRAM构造的，这个我们在后面会详细讨论。ROM也不需要刷新，实际上，它需要很少的电荷来保存信息。ROM用于永久性存储，或者即使当系统关闭后数据仍能保持的半永久存储。66.3存储器层次存储器层次 通常，较快的存储器比较慢的存储器成本高。为了以最少的花费获得最好的性能，存储器以层次方式组织。容量小、速度快的存储部件放在CPU中，较大的、较慢的主存通过数据总线来访问。更大的永久存储器以磁盘的形式或磁带驱动形式存在于远离CPU的位置。76.3存
3、储器层次存储器层次 这种分层存储组织结构被认为是一种金字塔形：86.3 存储器层次存储器层次 为了存取数据，CPU首先向它最近的存储器发送请求，通常是cache。如果数据不在cache中，就要询问主存。如果数据不在主存中，就要去询问磁盘。一旦确定了数据的位置，数据和它附近的许多数据单元就被取到cache存储器中。96.3存储器层次存储器层次 相关概念 命中（命中（hit），），CPU请求的数据就驻留在要访问的存储器层中。缺失缺失(miss)，CPU请求的数据不在要访问的存储器层中。命中率命中率(hit rate)：访问某个特定的存储器层时，CPU不到所需数据的百分比。缺失率缺失率(miss r
4、ate)：访问某个特定的存储器层时，CPU找不到所需数据的百分比。缺失率=1 命中率。命中时间命中时间(hit time)，是某个特定的存储器层中，CPU取得所请求数据需要的时间。缺失损失缺失损失(miss penalty)，CPU处理一次缺失事件所需时间，其中包括利用新的数据取代上层存储器中的某个数据块所需时间，再加上将所需数据传递给处理器所需的附加时间。106.3存储器层次存储器层次 一个完整的数据块在命中后被复制，根据局部性原理，一旦字节被访问，它附近的数据元素很快也会被访问。局部性的三种形式：时间局部性-最近访问的数据易于在不久的将来再次被访问。空间局部性-对存储器地址空间的访问形成団
5、簇的集中倾向。顺序局部性-访问存储器的指令趋于被顺序访问。116.4 Cache存储器存储器 cache 存储器是通过把最近使用过的数据存放在临近CPU的位置而不把它存储在主存中来提高存取速度。虽然cache比主存小很多，但它的存取速度比主存快很多。和主存不同，主存是通过地址来访问，而cache是靠内容来访问的，所以常常称cache为内容可寻址存储器。因此，并不是cache 存储器越大越好，容量太大则查找数据的时间就会很长。126.4 Cache存储器存储器 主存储器和cache的存储空间都被划分成大小相同的数据块。主存储器的许多块映射到cache的一个块。Cache中的不同块由标记域(tag
6、 field)来区分。存储器地址被划分为多个域(field)，如标记域、字域、块域等，这些域为较大的主存和较小的cache存储器之间提供多对一映射关系。命中过程：根据主存地址中的块域找到数据在cache中的位置 判别有效位(valid bit)比较cache中的标记与主存地址的标记域 根据字域找到所需访问的字136.4 Cache存储器存储器 最简单的cache 映射模式是直接映射。在cache 中的N个块和主存中的X个块组成的直接映射，映射关系：Y=X mod N。如果cache有10 个块,cache的第7块可能含有主存中的第7、17、27、37.块。一旦主存的一个块被复制到cache的对
7、应块中，就要为cache块设置一个有效位(valid bit)，指示系统该块中含有有效数据。如果没有有效位会发生什么情况如果没有有效位会发生什么情况?146.4 Cache存储器存储器 下图是cache的一个示意图。块0含有来自主存储器的多个字,并用标记 00000000来进行身份识别。块1用11110101来标记。其它的两个块是无效的。156.4 Cache存储器存储器 一个存储器地址被分成的每一个域的大小依赖于cache的大小。假如存储器由214 个字组成，cache 有16=24 个块，并且每个块有8个字。这样，存储器就分成了214/2 3=211 个块。主存地址域的划分：4位用于块域，
8、3位用于字域，左面剩下的全部用于标记域：166.4 Cache存储器存储器 根据上面例子，假如一个程序产生了地址1AA，在14位二进制当中，这个数字是00000110101010。这个地址的开始7位是标志域，接着的4位是块域，并且后3位表明块中的字。176.4 Cache存储器存储器 如果随后该程序产生的地址是1AB，它将在块 0101中寻找数据中寻找数据，字位于快内011位置位置。然而，如果该程序产生地址3AB，则地址1AA 装入的块将会从cache中取出，而用与3AB 相关的信息来置换。186.4 Cache存储器存储器 假如一个程序产生了一系列的存储地址，如 1AB,3AB,1AB,3A
9、B,.cache 将持续的取出，并且进行块的替换。在这种极端情况下，cache理论上的优点就不存在了。这是直接映射cache的主要缺点。设计的其它的cache映射方案阻止了这种系统颠簸。196.4 Cache存储器存储器 不为存储块设置明确的基于主存储器地址的cache 位置，我们可以允许一个块存放在cache中的任何块中。用这种方式，在任何块被取走之前，cache必须是填满的。这就是全关联cache的工作原理。一个存储地址仅被分成两个域：标记域和字域。206.4 Cache存储器存储器 如前面例子，假如有一个14位存储地址和一个拥有16个块的cache，每一个块的大小是8个字。则存储地址格式
10、是:当搜索cache时，并行的搜索所有的标记，来快速检索数据。这需要特殊的、造价高的硬件。216.4 Cache存储器存储器 回忆一下，无论何时另一个存储器内容需要那个块时，直接映射cache都将把该块删除。对于全相连的cache当中，不存在这种映射关系，所以我们必须设计一种算法来决定哪一个块应该从cache中删除。被删除的块是牺牲块。有许多种方法选择牺牲块，我们将会简要讨论。226.4 Cache存储器存储器 组关联cache兼备直接映射cache和全关联cache的思想。一个N路 固定相连cache 映射想直接映射cache，因为一个存储器内容映射到cache中的一个特殊位置.与直接映射c
11、ache不同,一个存储内容映射到一组cache块,和全相连cache的工作方式相似.不映射整个cache,存储内容能够映射到的仅是cache空间的子集.236.4 Cache存储器存储器 在组关联cache 中，每一组的cache块数目根据系统的总体设计变化.例如,一个二路的组相连cache 能够被概念化成下面的概要图来说明.每一组都含有两个不同的块.246.4 Cache存储器存储器 在组关联cache映射中,存储内容被划分为三个字段:标志,组,和字,如下所示.像直接映射cache一样,word字段选择cache块中的字,标志字段唯一的标识存储地址.Set字段决定存储块映射到的组.256.4
12、 Cache存储器存储器 假设我们有一个214字节的主存 这个存储器映射到一个拥有16个块，每个块有8个字的一个2路组相连cache.因为这是一个2路cache,每一组由2块组成,有8组.这样,需要3位用于 set,3位用于word,余下的左边8位用于tag:266.4 Cache存储器存储器 对于全关联和组关联cache，当需要从cache中取出一个块时，调用一种置换策略。一个最优置换策略能够预测将来哪一个块最长时间不需使用。虽然执行最优置换算法是不可能的，但是可以作为评价任何其它算法的参考和标准。276.4 Cache存储器存储器 我们选择的置换策略依赖于我们试图去优化的局部性常常,我们对
13、时间局部性感兴趣。最近最久未使用算法(LRU)，保持跟踪最后一次被评估的块，并且取出最长时间未使用的块.这种方法的缺点是它的复杂性:LRU不得不为每一个块保持访问史,这最终降低了cache的速度.286.4 Cache存储器存储器 先进先出(FIFO)是一种广泛应用的cache替换策略.在FIFO中,已经在cache 中的块最长，不管它是何时被最后使用的.随机置换策略，顾名思义:它随机选取块并且用一个新块替换它.随机置换当然可能取出一个将经常用到或很快就用到的块,但它从来都不会颠簸(thrashes)。296.4 Cache存储器存储器 层次存储器的性能是用它的有效访问时间(EAT)衡量的.E
14、AT 是一种考虑命中率和存储器的逐级相关存取时间的加权平均值.一个两级存储器的EAT计算公式如下:EAT=H AccessC+(1-H)AccessMM.其中，H 是cache的命中率，AccessC 和AccessMM 分别是cache和 主存的存取时间.306.4 Cache存储器存储器 例如,考虑一个系统，这个系统主存的存取时间是200ns，cache 的存取时间是10ns，并且命中率是 99%.EAT 是:0.99(10ns)+0.01(200ns)=9.9ns+2ns=11ns.这个决定有效存取时间的等式可以扩展到任意级的存储器系统.316.4 Cache存储器存储器 Cache 置
15、换策略必须考虑脏块(dirty block)，尤其当它们在cache 中已经被更新时.脏块一定要再被写回存储器。写策略决定了如何做。有两种类型的写策略，写通(write through)和回写(write back)。在每一次写时，写通同时更新cache和主存。326.4 Cache存储器存储器 仅当块被选中替换时，回写(也称为copyback)才更新存储器。写通的缺点是对于每一次cache写存储器必须更新，这就降低了更新的访问时间。这种降低常常是可以忽略的，因为大多数的存取都是读，不是写。回写的优点是通信量被最小化，但是它的缺点是存储器不总是与cache中的值一致，对于多用户系统，常会发起问
16、题。336.5虚拟存储器虚拟存储器 凭借着提供较快的存储器存取速度，Cache存储器提高了性能。凭借着提供较大的存储容量，不增加主存的成本，虚拟存储器提高了性能。磁盘驱动器的一部分是为扩展主存服务的。如果一个系统使用页式技术，虚拟存储分区主存储器成各自管理的页桢,当不立即需要它们时，它们就被写道磁盘上。346.5虚拟存储器虚拟存储器 物理地址是物理存储的实际存储地址.程序产生被存储管理者映射到物理地址的虚拟地址.当逻辑地址需要从磁盘中引入页时，缺页就发生了.当分页过程导致小的，不可用的存储器地址簇时，存储破碎就发生了.356.5虚拟存储器虚拟存储器 主存和虚拟存储器被分成相等大小的页.一种处理
17、过程需要的整个地址空间，在主存中不立即需要.一些部分可能在磁盘上,而其它的可能在主存中.进一步说,分配给进程的页不必连续存储或者部分页在磁盘上，或者在存储器中.用这种方法,任何时候，仅仅需要的页在存储器中,不需要的页存储在磁盘当中.366.5虚拟存储器虚拟存储器 关于每一页的位置的信息,既不在磁盘上，也不在存储器中,而是保留在一种称为页表的数据结构中(如下所示).对于每一活动过程，都有一个页表.376.5虚拟存储器虚拟存储器 当一种操作产生一个虚拟地址时,操作系统就把它翻译成一个物理存储地址.为了完成这一操作,虚拟地址被分成俩个字段:页字段,和偏移量字段.页字段决定地址的页位置，偏移量表明页中
18、的地址位置.通过在页表中查找，逻辑页码被翻译成一种物理页帧.386.5虚拟存储器虚拟存储器 如果逻辑地址在页表中的有效位是零,这意味着页不在存储器中，要到磁盘上去存取.这是页发生了错误.如果必要,页需要从存储器中取出，并且被磁盘上检索的页所取代,有效位被设置成1.如果有效位是1,虚拟页的数字被物理桢的数字所取代.把偏移量加到物理桢的数字，来存取数据.396.5 虚拟存储器虚拟存储器 如一个例子,假如一个系统拥有一个8K 空间的虚拟地址和一个4K 空间的物理地址，系统是用位寻址.我们有 213/210=23的虚拟页.虚拟地址13位(8K=213)3位用于页字段，10位用于偏移量,因为页的大小是1
19、024.一个物理存储地址需要12 位,开始的两位用于页桢，尾随的10位是偏移量.406.5虚拟存储器虚拟存储器 假如我们有下面的页表.What happens 当CPU产生地址 545910=10101010100112时，会发生什么？416.5虚拟存储器虚拟存储器 地址10101010100112 转化成物理地址为010101010011 因为通过再也表中查找，页字段 101 被桢的数字01取代.426.5虚拟存储器虚拟存储器 当CPU 产生地址10000000001002时会发生什么？436.5虚拟存储器虚拟存储器 我们早就说过有效存取时间(EAT)需要考虑存储器的所有级.这样,在计算当中
20、，虚拟存储器也是一个因素,我们也不得不考虑页表的存取时间.假如一个主存的存取需要200ns,页的出错率为1%,它花费10ms 从磁盘中装入一页.我们有:EAT=0.99(200ns+200ns)0.01(10ms)=100,396ns.446.5虚拟存储器虚拟存储器 即使没有页错误,EAT将是 400ns，因为存储器总是读两次:第一次存取页表,第二次从存储器中装入页.因为页表的读始终都是一样的，所以保持它们在一个特殊的称为翻译旁视缓冲(TLB)的寄存器中，是有意义的.TLBs 是一种特殊相关寄存器，这种寄存器将虚拟页的映射存储到物理页.下一张幻灯片展示这些部件是如何协调工作的下一张幻灯片展示这
21、些部件是如何协调工作的.456.5虚拟存储器虚拟存储器466.5虚拟存储器虚拟存储器 虚拟存储器的另一种方法是使用分段.不将存储器分成相等大小的页,虚拟地址空间被分成可变长度的段,常常在程序员的控制之下.通过段表的入口，一个段被定位,它含有段的存储位置和一个表明它大小的界限.发生缺页时,操作系统在存储器中寻找一个足够大的位置存放从磁盘中检索到的段.476.5虚拟存储器虚拟存储器 分页和分段都会引起碎片.分页产生的是内部碎片，因为一个进程不可能恰好需要一页当中含有的全部地址空间.这样,许多页含有存储器中未用过的碎片.分段产生的是外部碎片,在进行分段配置和解除分段时，存储器中的自由空间块会变得残缺
22、不完整，最后导致有许多长度较小的自由空间块都不足以存放一整段程序。486.5虚拟存储器虚拟存储器 大的页表是笨重的并且速度慢,但是由于它的均匀的存储映射,使得页操作很快.分段允许快速存取段表,但是分段载入开销也很大.分页和分段可以结合起来，通过在可变长段中安排定长页来继承两种方式的优点.每一个段都有一个页表.这意味着一个存储地址将有三个字段,一个用于段,另一个用于页,第三个用于偏移量.496.6一个真实领域的例子一个真实领域的例子 Pentium系列处理器支持分页和分段,并且它们还可以用在各种结合当中，包括不分页不分段，分段不分页，和不分段分页.处理器支持两级cache(L1 and L2),
23、都有一个32字节大小的块.L1 cache紧挨着处理器,而L2 cache 位于处理器和存储器之间.L1 cache分为两部分:一个指令cache(I-cache)和一个数据cache(D-cache).下一张幻灯片将简要说明这种组织下一张幻灯片将简要说明这种组织.506.6 一个真实领域的例子一个真实领域的例子51 计算机存储器层次结构组织起来,最小最快的存储器在顶部，最大最慢的存储器在底部.Cache 存储器使得主存储器较快的存取,而虚拟存储器使用磁盘存储给人一种主存很大的错觉.Cache 将主存储器块映射到cache存储器块.虚拟存储器将页桢映射到虚拟页.有三种常见类型的cache:直接映射,全关联和组关联.第第6章章 结论结论52 全关联和组关联cache,还有虚拟存储器,都要建立置换策略.置换策略包括LRU,FIFO,or LFU.这些策略需考虑对于脏块要做如何处理.所有的虚拟存储器必须处理碎片,分页存储产生内部碎片,分段存储产生外部碎片.第第6章章 结论结论53End of Chapter 6
