组成第十四讲：快速缓冲存储器.ppt

1、第七章 存储系统,7.1 存储系统的层次结构 7.2 高级缓冲存储器 7.3 虚拟存储器 7.4 相联存储器,7.1 存储系统的层次结构 1.主存和辅存的概念 2.主存和辅存在操作系统的控制下，通过软硬 件把主存和辅存统一成为一个整体，形成一个 存储层次。这个层次拥有接近于主存的速度和 辅存的容量，价格也接近于辅存的价格。 3.在CPU和主存之间有高速缓冲存储器cache， 这完全是由硬件来完成的。 Cache主存的 速度接近于cache，而容量与价格接近于主存。 Cache的速度接近于CPU。,1.三级结构的存储器系统：将高速缓缓冲存储器、主存储器和辅助（虚拟）存储器组成的统一管理、调度的一

2、体化三级结构的存储器系统。,3.三种存储器的比较,(1)高速缓存（Cache）：速度快，容量小，用于临时存放运行中的指令和少量数据；,(2)主存：速度、容量一般，用于临时存放运行中的大量程序和数；,(3)辅存：速度慢，容量大，用于永久存放大型程序软件和数据库。,4.采用三级结构的目的和方法,(1)Cache-主存层次：解决CPU与主存间速度不匹配问题，使系统具有主存容量和接近于Cache速度。采用地址映像方式，以字块为基本信息单位。,(2)虚拟存储器-主存层次：解决主存容量小、运行成本高的问题，使系统具有辅存容量和接近主存速度，且造价和运行成本低。采用地址变换方式，以段、页为基本信息单位。,局

3、部性原理、一致性原则和包含性原则 1.局部性原理三级结构存储器系统运行原理基础 (1)时间局部性：在较小的时间间隔内，最近被访问的指令和数据很可能再次被访问； (2)空间局部性：这些最近被访问的指令和数据往往集中在一小片存储区域中； (3)指令执行方式局部性：顺序执行较转移执行可能性大。,3.一致性原则：同时存放在三类存储器中的信息，在三类存储器中必须保持同值。,2.包含性原则：处在内层的存储器的信息一定包含 在各外层存储器中。即内层存储器中信息是外层存 储器所存信息的一小部分的副本。,Cache：一种容量小、速度快，用静态存储器器件实现的存储器。,作用：解决CPU与主存速度不匹配的问题，使系

4、统速度接近于CPU，容量接近于主存。,高速缓冲存储器（cache）,目前，组成主存的DRAM存取速度一般落后于CPU的处理速度，CPU访问主存时不得不插入等待周期来适应主存的速度，致使系统整体下降。 高速缓冲存储器Cache： 是为解决CPU和DRAM之间的速度匹配而采用的一项重要技术； 是发挥CPU高速高效的性能而设置的一种介于CPU和DRAM之间的高速小容量缓冲存储器； 存取速度要比主存快，由高速的SRAM组成； 全部功能由硬件实现，保证了其高速度。,高速缓冲存储器（cache）,cache的工作机制 cache基本原理 地址映象（映射）与地址变换 cache与主存数据的一致性 替换策略

5、高速缓冲器cache的构成,cache的工作机制,高速缓冲存储器cache的工作机制基于程序访问的局部性原则。 一个运行程序的代码大都顺序存放在地址连续的存储器中，与程序相关的数据在存储器中也相对集中。 程序运行时，尤其有循环程序段和子程序段时，在较短的时间区间内，常会对局部范围的存储器频繁访问，某存储单元被访问了，该单位可能会被再次访问，大多数存取又是在紧接着上次存取地址附近，而此范围之外的地址访问甚少。这种现象称程序访问的局部性。,cache的工作机制,根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不

6、必从主存储器取指令和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓冲存储器Cache。 Cache由高速的SRAM组成，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。,cache的工作机制,cache基本原理,Cache结构设计必须解决的问题： 如何存放，如何访问，如何替换，如何改写？ 数据块在Cache中存放在哪个位置？即定位问题（地址映象） 。如果一个块存放在某一Cache中，怎样确定并找到该块，即寻址问题（地址变换）。 不命中时将从主存储器中访问，并将该块调入Cache中，但是如果Cache中已无空闲空间，则势必将Cache中的某一块调出，但

7、应调出那一块，即替换问题。 在写访问时，写入Cache必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性。写操作失配时是否将访问块取入高层存储器。,cache基本原理,高速缓冲存储器包括： cache控制部件 cache存储器,cache基本原理,cache控制部件 包括： 主存地址寄存器 主存cache地址变换机构 替换控制部件 cache地址寄存器 控制部件均由硬件组成,cache基本原理,cache存储器 多采用与CPU相同类型的半导体集成电路制成的高速存储元件SRAM； 存取速度比主存快且与CPU接近； 整个cache存储器介于CPU和主存之间，直接

8、接受CPU访问； CPU不仅与cache相接，而且与主存仍然保持通路。,cache基本原理,在主存cache存储体系中，所有的程序和数据都在主存中，cache存储器只存放主存一部分程序块和数据块的副本，这种以块为单位的存储方式是基于计算机程序的局部性。 从程序局部性可知，cache中的程序块和数据块使CPU要访问的内容在大多数情况下已经在cache存储器里，CPU读写操作主要在CPU和cache之间进行。,cache基本原理,cache的命中 任何时候都有一些主存块处在Cache中。 CPU访问存储体系时首先访问cache，送出访问单元的地址由地址总线打入cache存储器的主存地址寄存器MA；

9、 主存cache地址变换机构从主存地址寄存器MA获取地址判断该单元内容是否已在cache中存放副本，如果副本已经在cache中了，称为命中；反之称不命中或命中失效。,cache基本原理,cache基本原理,cache的命中率 命中率指CPU所要访问的信息在Cache中的比率； 所要访问的信息不在Cache中的比率称为失效率。 增加cache的目的，就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此， cache的命中率应接近于1。 由于程序访问的局部性 ，这是可能的。,cache基本原理,当命中时立即把访问地址变换成它在cache的地址，然后驱动cache存储体。 当是读操作

10、时，CPU从cache中直接读取信息； 若是写操作，不但要把新内容写入cache存储器中，而且必须同时写入主存，使主存和cache内容同时修改，保证主存和副本内容一致，这种方法也叫直达法。,cache基本原理,有的机器考虑到当写入操作很频繁或者写入的是中间结果，每次写入主存很浪费时间，于是设计成每次只改写cache的内容并不立即修改主存中相应的单元，只有当cache中被写过的块要被新进入cache的信息块取代时才一次写回主存里，这种方法称回写法。,cache基本原理,如果CPU要访问的内容根本不在cache中，即“不命中”，那么CPU转去直接访问主存。 若是读操作，CPU则从主存读取信息的同时

11、，cache控制部件把该地址所在那块存储内容从主存一次调进cache存储器，以存储块为单位调入cache存储器可以提高下次访问的命中率。 若是写操作，则处理就简单多了，很多计算机系统只向主存写入信息，不必同时把这个地址所在的存储内容再调入cache存储器中。,cache基本原理,直达法： 优点：数据不会出现不一致 缺点：对写操作没有高速缓存的作用 回写法： 优点：速度快 缺点：存在数据不一致隐患,cache基本原理,对于共享一个主存的多处理机系统，因为处理机各自拥有cache存储器，所以必须采用写直达法将任何一个cache中修改的内容同时写入主存，保证其他cache向主存调用信息块时是修改过的

12、而不是失效的信息。 这点对于拥有多个处理机而共享一个主存的计算机系统特别重要。,7.2 高速缓冲存储器（cache）,cache的工作机制 cache基本原理 地址映象（映射）与地址变换 cache与主存数据的一致性 替换策略 高速缓冲器cache的构成,地址映象(映射)与地址变换,地址映象 把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。 地址变换 信息按这种映象关系装入Cache后，执行程序时，将主存地址变换成 Cache地址的变换过程叫做地址变换。 地址映象和变换密切相关。,地址映象(映射)与地址变换,使用Cache的动力在于它的高速，因此也要求这个地址变换过

13、程尽可能地快，故此过程是以硬件完成的。 这带来的另一好处是Cache的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到Cache的存在。,地址映象(映射)与地址变换,在高速缓冲存储器中把Cache和主存机械等分为相同大小的块，每一块是由若干个字（或字节）组成。 例：某机主存容量为1MB，划分为2048块，每块512B；Cache容量为8KB，划分为16块，每块512B。,地址映象(映射)与地址变换,由于Cache的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的哪一块的副本（拷贝）。,地址映

14、象(映射)与地址变换,标记的有效位 每个标记设置有一个有效位。 机器加电启动时，Reset信号将所有标记的有效位置“0”，即无效。 程序执行过程中，Cache不命中时，逐步将指令块或数据块从主存调入Cache中的某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或数据时，可直接从Cache中取指令或数据。,地址映象(映射)与地址变换,因刚加电时所有标记位都为“0”，开始执行程序时，命中率较低。 另外Cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。,地址映象(映射)与地址变换,基本的地址映象方式： 直接映象 全相连映象 组相连映象,地址映象(映射)与地址变换,直

15、接映射方式 这是一种多对一的映射关系，一个主存块只能映象到Cache的一个特定块位置上去。 在这种映象方式中： 主存的第0块，第16块，第32块，只能映象到Cache的第0块； 而主存的第1块，第17块，第33块，只能映象到Cache的第1块；,地址映象(映射)与地址变换,直接映象,7位,地址映象(映射)与地址变换,直接映象的地址变换方法,地址映象(映射)与地址变换,优点： 实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在Cache中。 缺点：不够灵活，主存的多个字块只能对应唯一的Cache字块，因此，即使Cache别的地址空着也不能占用。Cache存储空间得不到充分利用

16、，降低了命中率。,地址映象(映射)与地址变换,全相联映象方式,允许主存中的每一个字块映象到Cache的任何一个字块位置上，最灵活但成本最高的一种方式。,地址映象(映射)与地址变换,全相联映象的地址变换方法,地址映象(映射)与地址变换,全相联映象的地址变换方法的优缺点： 优点：灵活，块冲突概率小。只有当Cache中全部装满后，才有可能出现块冲突； 缺点：要作相联搜索，速度慢，代价高。,地址映象(映射)与地址变换,这只是一个理想的方案。两个原因使其实际上很少采用： 标记位数从7位增加到11位，使Cache标记容量加大； 访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址

17、的内容是否已在Cache中。由于Cache速度要求高，通常由“按内容寻址”的相联存储器完成，所需硬件逻辑电路很多，以至于无法用于cache中。实际的Cache组织则是采取各种措施来减少所需比较的地址数目。,地址映象(映射)与地址变换,组相联映射方式 组间全相联，组内直接映像 直接映象和全相联映象方式的一种折衷方案。,地址映象(映射)与地址变换,注意： 当Cache只有一个组并且每组16块时，此时为直接映像； 当Cache有16组并且每组一个块时，则为全相联映像。,8位 3位 9 位,1位 3位 9 位,7.2 高速缓冲存储器（cache）,cache的工作机制 cache基本原理 地址映象（映

18、射）与地址变换 cache与主存数据的一致性 替换策略 高速缓冲器cache的构成,cache与主存数据的一致性,cache中存放的是主存中部分信息的副本。 为了保证CPU存取的数据准确无误，要求cache中每一个地址上的数据与主存中相应存储单元的数据保持完全相同，这种性质称cache与主存数据的一致性。 写直达法和回写法是常见的保持数据一致性的算法。,cache与主存数据的一致性,cache与主存数据的不一致的情况： CPU从cache读入数据重新写入修改后的新数据时； 主存数据修改。 例如多处理机系统，其中一个cache内容修改后立即用写直达法写入主存又导致主存数据可能与其他cache的副

19、本不一致。 又例如，计算机的DMA访问直接修改了主存数据，也可能造成与cache数据的不一致性。,cache与主存数据的一致性,通常采用的处理办法有： 主存监视法： 利用硬件机构使cache控制器能监视所有设备对主存的操作或访问，凡对主存的写入也立即对cache中相应单元进行拷贝，从而保证数据的一致性 设置“不可cache区”： 即在主存中开辟一块存储区域，该区域数据不能调入cache，不受cache控制器管理，但其他设备进入的数据只能直接写入该区域。所以不会产生与cache中数据的不一致性。 “不可cache区”可以通过BIOS设置程序来设置。,7.2 高速缓冲存储器（cache）,cach

20、e的工作机制 cache基本原理 地址映象（映射）与地址变换 cache与主存数据的一致性 替换策略 高速缓冲器cache的构成,替换策略,在主存cache存储体系工作过程中，主存和cache存储器之间信息以块为单位调度，信息块的长度取决于主存的结构设计，主存常设计成多体交叉存储结构。 当信息块需要调入cache存储器而cache存储器中已经占满信息时，cache存储器的替换控制部件将按一定的替换策略淘汰cache中旧有的一块信息，被更新的旧信息块应该是下一段时间内估计是最少使用的，然后用新的信息块覆盖掉。,替换策略,常用的替换策略有两种： 先进先出策略FIFO策略 总是更换掉当前cache中

21、最先进入的信息块 这种方法控制简单，实现容易 近期最少使用策略 LRU策略,替换策略,近期最少使用策略 LRU策略： 遵循的规则是新信息块替代的是当前cache存储器中被使用次数最少的，即最不活跃的那块信息； 使用LRU方法的cache存储器每一个字块都要附设一个计数器记录被使用的情况，每当cache中的一块信息被命中时，比命中块计数值低的信息块均加1，而命中块计数器清0； 显然，这种技术方法各信息块的计数值总是不相同的。,替换策略,一旦不命中情况发生时，新信息块从主存调入cache存储器替换计数值最大的那片存储区，新信息块计数值为0，其余信息块计数均加1，保证了那些活跃的信息块经常被命中或最

22、近被命中的信息块计数值要小，而近来越来越不活跃的信息块计数值越大； LRU策略是目前使用较多的一种策略，能够有效的提高命中率。,替换策略,无论FIFO策略还是LRU策略，其实最先被调入cache的信息块或最近最少使用的信息块都不能肯定是最近将绝不会使用，所以替换策略不能作为最合理最优秀的。 但是研究表明，FIFO和LRU策略明显地提高了cache存储器的命中率，可以达到百分之九十左右，其中LRU策略的命中率比FIFO更高一些。,替换策略,Cache的命中率反映了CPU需要访问的数据在cache中能直接找到的概率。 影响命中率的因素有： 替换策略 cache的结构因素 包括cache高速缓冲存储器大小、传送块的大小 若cache的存储容量越大，保存副本越多，命中率就越高 访问程序和数据的局部性 影响命中率的外部因素,7.2 高速缓冲存储器（cac