第7章存储系统

内容简介存储系统的层次结构高速缓冲存储器（cache）虚拟存储器相联存储器存储保护1第7章存储系统EmbeddedSystemLab.7.1存储系统的层次结构•三级存储系统及其存取方式–主存储器（内存）的特点•采取随机存取方式•工作速度快•具有较大的存储容量–外存储器•信息组织采取文件、数据块结构，采用顺序存取方式–顺序存取存储器（SAM）–直接存取存储器（DAM）•具有很大的存储容量，价格/位低•长久保存•许多外存储器的记录介质•具有机械机构，可靠性低于半导体存储器，需校验2CPUcache主存外存EmbeddedSystemLab.•Cache(高速缓冲存储器)主-辅存层次满足了存储器的大容量和低成本需求。在速度方面，计算机的主存和CPU一直保持了大约一个数量级的差距。显然这个差距限制了CPU速度潜力的发挥。设置高速缓冲存储器(cache)是解决存取速度的重要方法。在CPU和主存中间设置高速缓冲存储器，构成高速缓存(cache)-主存层次，要求cache在速度上能跟得上CPU的要求。cache-主存间的地址映像和调度吸取了比它较早出现的主-辅存存储层次的技术，不同的是因其速度要求高，不是由软、硬件结合而完全由硬件来实现。从CPU的角度看，cache-主存层次的速度接近于cache，容量与每位价格则接近于主存。因此，解决了速度与成本之间的矛盾。7.1存储系统的层次结构3EmbeddedSystemLab.cache容量最小，辅存容量最大各层次中存放的内容都可以在下一层次中找到。这种多层次结构已成为现代计算机的典型存储结构。三层次存储系统7.2高速缓冲存储器(cache)•主要概念•cache存储器工作原理–采用cache的依据–cache的基本结构–工作原理–地址映像、替换算法–cache与主存的一致性问题•cache存储器组织•cache存储器举例•多层次cache存储器5EmbeddedSystemLab.主要概念•用途：解决CPU与主存之间的速度匹配•片内Cache•片外Cache•Cache理论依据：程序与数据的局部性（时间、空间局部性）•访问命中：要访问的内容在Cache时6结构EmbeddedSystemLab.7.2.1cache存储器工作原理•对存储器访问的局部性•cache的基本结构•cache与主存的一致性问题7EmbeddedSystemLab.•对存储器访问的局部性–局部性~对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少。–对程序的访问局部性•在一个较短的时间间隔内，地址往往集中在存储器逻辑地址空间的很小范围内。程序地址的分布本来就是连续的，再加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问就自然地具有相对集中的倾向。–对数据的访问局部性•数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。8EmbeddedSystemLab.7.2.1cache存储器工作原理•Cache~根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，当程序运行时，不必从主存储器取指令和取数据，而访问这个高速存储器即可，所以提高了程序运行速度，这个存储器称作高速缓冲存储器(cache)。•cache存储器介于CPU和主存之间，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的9EmbeddedSystemLab.Cache存储器工作原理cache的基本结构10采用主存与cache分块映像方法若主存：2n个单元，B个字节/块，则块数：M=2n/BEmbeddedSystemLab.cache的“效率”•cache的容量和块的大小~是影响cache的效率的重要因素。通常用“命中率”来测量cache的效率。•命中率~指CPU所要访问的信息在cache中的比率•失效率~将所要访问的信息不在cache中的比率•一般来说，cache的存储容量比主存的容量小得多，但不能太小，太小会使命中率太低；•也没有必要过大，过大不仅会增加成本，而且当容量超过一定值后，命中率随容量的增加将不会有明显地增长。•但随着芯片价格的下降，cache的容量还是不断增大，已由几十K发展到几百K字节，甚至达到几M字节。Cache存储器工作原理11EmbeddedSystemLab.替换策略或替换算法•替换在从主存读出新的字块调入cache存储器时，如果遇到cache存储器中相应的位置已被其他字块占有，那么就必须去掉一个旧的字块，让位于一个新的字块。•替换算法这种替换应该遵循一定的规则，最好能使被替换的字块是下一段时间内估计最少使用的。这些规则称为替换策略或替换算法，由替换部件加以实现。Cache存储器工作原理12EmbeddedSystemLab.•Cache的写操作与主存内容的一致性–cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行写操作，就会遇到如何保持cache与主存的一致性问题。通常有两种写入方式：•标志交换(flag-swap)方式(“写回法”)–暂时只向cache存储器写入，并用标志加以注明，直到经过修改的字块被从cache中替换出来时才一次写入主存；–这种方式写操作速度快，但因在此以前，主存中的字块未经随时修改而可能失效。13EmbeddedSystemLab.cache与主存的一致性问题通过式写(write-through)（又称写直达法）•每次写入cache存储器时也同时写入主存，使cache和主存保持一致。•这种方式实现简单，且能随时保持主存数据的正确性。但是，有可能要增加多次不必要的向主存的写入。假如向cache存储器某一单元写入多少次，也要向主存相应单元写入多少次。另有一种写操作方法•当被修改的单元根本就不在cache存储器时，写操作直接对主存进行，而不写入cache存储器。Cache存储器工作原理14EmbeddedSystemLab.•为了说明标记是否有效，每个标记至少还应设置一个有效位•无效设置–当机器刚加电启动时，总机的reset信号或执行程序将所有标记的有效位置“0”，使标记无效。•有效设置–在程序执行过程中，当cache不命中时逐步将指令块或数据块从主存调入cache中的某一块，并将这一块标记中的有效位置“1”•访问命中–当再次用到这一块中的指令或数据时，肯定命中，可直接从cache中取指或取数。从这里也可看到，刚加电后所有标记位都为“0”，因此开始执行程序时，命中率较低。–另外cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。15EmbeddedSystemLab.标记有效设置7.2.2cache存储器组织•地址映像–直接映像–全相联映像–组相联映像•替换算法–先进先出(FIFO)算法–近期最少使用(LRU)算法。16EmbeddedSystemLab.1.地址映像•为了把信息放到cache存储器中，必须应用某种函数把主存地址映像到cache，称作地址映像。•在信息按照这种映像关系装入cache后，执行程序时，应将主存地址变换成cache地址，这个变换过程叫做地址变换。地址的映像和变换是密切相关的。•假设主存储器空间被分为–Mm(0)，Mm(1)，…，Mm(i)，…，Mm(2m-1)共2m个块，字块大小为2b个字；–cache存储空间被分为Mc(0)，Mc(1)，…，Mc(j)，…，Mc(2c-1)共2c个同样大小的块。17EmbeddedSystemLab.7.2.2cache存储器组织（1）直接映像•在直接映像方式中，主存和cache中字块的对应关系如图7.3所示。•优点–实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在cache存储器中。•缺点–不够灵活、Cache得不到充分利用,即使Cache其他页空闲，也将有一个主存页不能写入Cache.18EmbeddedSystemLab.地址映像图7.3直接映像cache组织•直接地址映像20•映像关系：•标记：组号注：页=块引例某机主存1MB，2048块，512B/块。Cache容量8KB，16块，512B/块EmbeddedSystemLab.•(2)全相联映像•全相联映像方式是最灵活但成本最高的一种方式，7.2.2cache存储器组织图7.4全相联映像cache组织21EmbeddedSystemLab.22优点主存的每一页可映像到Cache的任一页缺点：不能直接从主存地址码中提取Cache页号，需将主存页标记与Cache各页的标记逐个比较，直到符合的页为止（命中）。速度慢，失掉高速缓存作用。全相联映像引例某机主存1MB，2048块，512B/块。Cache容量8KB，16块，512B/块EmbeddedSystemLab.•(3)组相联映像组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组相联映像cache组织如图7.5所示。组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r=0时，它就成为直接映像方式；当r=c时，就是全相联映像方式。cache的命中率除了与地址映像的方式有关外，还与cache的容量有关。cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。7.2.2cache存储器组织23EmbeddedSystemLab.•主存和cache都分组，主存中一个组内的块数与cache中的分组数相同。•组间采用直接地址映射，而组内采用全相联地址映射。•组相联映射方法比直接地址映射灵活，比全相联地址映射速度快。•实际上，若组的大小为1时，就变成了直接映射；若组的大小为整个cache的尺寸时，就变成了全相联映射。24EmbeddedSystemLab.组相联图7.5组相联映像cache组织•特点–主存与Cache都分组，主存中一个组的块数与Cache中的分组数相同–如果cache只有一组则为全相联，如果cache每组一块，则为直接相联•映像关系：主存块号与Cach组号间直接映象，但Cach组内块号与主存块号间全相联–组间直接相联，组内字块全相联•主存地址–主存块标记：主存的组号=高7位：Cache组内块号26引例某机主存1MB，2048块，512B/块。Cache容量8KB，16块，512B/块组相联EmbeddedSystemLab.•当新的主存字块需要调入cache存储器而它的可用位置又已被占满时，就产生替换算法问题。–先进先出(FIFO)算法–近期最少使用(LRU)算法。•FIFO算法–总是把一组中最先调入cache存储器的字块替换出去，它不需要随时记录各个字块的使用情况，所以实现容易，开销小。27EmbeddedSystemLab.替换算法LRU算法•把一组中近期最少使用的字块替换出去。•这种替换算法需随时记录cache存储器中各个字块的使用情况，以便确定那个字块是近期最少使用的字块。•LRU替换算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。•LRU是最常使用的一种算法。其设计思想是把组中各块的使用情况记录在一张表上(如图7.6所示)。随机替换法(RAND)•这种算法不考虑使用情况，在组内随机选择一块来替换。•其性能比根据使用情况的替换算法要差些。替换算法28EmbeddedSystemLab.LRU算法替换登记表29EmbeddedSystemLab.30EmbeddedSystemLab.7.2.3cache存储器举例•82385cache控制器–实现80386微处理器相匹配的主存-cache存储系统的地址映像和变换的。–可全部映像80386的32位地址提供的4G(千兆)字节的地址空间，使CPU几乎无任何等待地读出数据，命中率可高达99%。–82385片内只含有cache控制器，cache数据保存在片外的SRAM中。•82385提供了两种地址映像方式：–直接映像–两路组相联映像。31EmbeddedSystemLab.7