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

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

Cache的速度接近于CPU。1.三级结构的存储器系统：将高速缓缓冲存储器、主存储器和辅助（虚拟）存储器组成的统一管理、调度的一体化三级结构的存储器系统。3.三种存储器的比较

(1)高速缓存（Cache）：速度快，容量小，用于临时存放运行中的指令和少量数据；

(2)主存：速度、容量一般，用于临时存放运行中的大量程序和数；

(3)辅存：速度慢，容量大，用于永久存放大型程序软件和数据库。4.采用三级结构的目的和方法

(1)Cache-主存层次：解决CPU与主存间速度不匹配问题，使系统具有主存容量和接近于Cache速度。采用地址映像方式，以字块为基本信息单位。

(2)虚拟存储器-主存层次：解决主存容量小、运行成本高的问题，使系统具有辅存容量和接近主存速度，且造价和运行成本低。采用地址变换方式，以段、页为基本信息单位。局部性原理、一致性原则和包含性原则1.局部性原理——三级结构存储器系统运行原理基础(1)时间局部性：在较小的时间间隔内，最近被访问的指令和数据很可能再次被访问；(2)空间局部性：这些最近被访问的指令和数据往往集中在一小片存储区域中；(3)指令执行方式局部性：顺序执行较转移执行可能性大。3.一致性原则：同时存放在三类存储器中的信息，在三类存储器中必须保持同值。

2.包含性原则：处在内层的存储器的信息一定包含在各外层存储器中。即内层存储器中信息是外层存储器所存信息的一小部分的副本。

Cache：一种容量小、速度快，用静态存储器器件实现的存储器。作用：解决CPU与主存速度不匹配的问题，使系统速度接近于CPU，容量接近于主存。高速缓冲存储器（cache）目前，组成主存的DRAM存取速度一般落后于CPU的处理速度，CPU访问主存时不得不插入等待周期来适应主存的速度，致使系统整体下降。高速缓冲存储器Cache：是为解决CPU和DRAM之间的速度匹配而采用的一项重要技术；是发挥CPU高速高效的性能而设置的一种介于CPU和DRAM之间的高速小容量缓冲存储器；存取速度要比主存快，由高速的SRAM组成；全部功能由硬件实现，保证了其高速度。高速缓冲存储器（cache）cache的工作机制cache基本原理地址映象（映射）与地址变换cache与主存数据的一致性替换策略高速缓冲器cache的构成cache的工作机制高速缓冲存储器cache的工作机制基于程序访问的局部性原则。一个运行程序的代码大都顺序存放在地址连续的存储器中，与程序相关的数据在存储器中也相对集中。程序运行时，尤其有循环程序段和子程序段时，在较短的时间区间内，常会对局部范围的存储器频繁访问，某存储单元被访问了，该单位可能会被再次访问，大多数存取又是在紧接着上次存取地址附近，而此范围之外的地址访问甚少。这种现象称程序访问的局部性。cache的工作机制根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不必从主存储器取指令和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓冲存储器Cache。Cache由高速的SRAM组成，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。cache的工作机制cache基本原理Cache结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？数据块在Cache中存放在哪个位置？即定位问题（地址映象）。如果一个块存放在某一Cache中，怎样确定并找到该块，即寻址问题（地址变换）。不命中时将从主存储器中访问，并将该块调入Cache中，但是如果Cache中已无空闲空间，则势必将Cache中的某一块调出，但应调出那一块，即替换问题。在写访问时，写入Cache必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性。写操作失配时是否将访问块取入高层存储器。cache基本原理高速缓冲存储器包括：cache控制部件cache存储器cache基本原理cache控制部件包括：主存地址寄存器主存－cache地址变换机构替换控制部件cache地址寄存器控制部件均由硬件组成cache基本原理cache存储器多采用与CPU相同类型的半导体集成电路制成的高速存储元件SRAM；存取速度比主存快且与CPU接近；整个cache存储器介于CPU和主存之间，直接接受CPU访问；CPU不仅与cache相接，而且与主存仍然保持通路。cache基本原理在主存－cache存储体系中，所有的程序和数据都在主存中，cache存储器只存放主存一部分程序块和数据块的副本，这种以块为单位的存储方式是基于计算机程序的局部性。从程序局部性可知，cache中的程序块和数据块使CPU要访问的内容在大多数情况下已经在cache存储器里，CPU读写操作主要在CPU和cache之间进行。cache基本原理cache的命中任何时候都有一些主存块处在Cache中。CPU访问存储体系时首先访问cache，送出访问单元的地址由地址总线打入cache存储器的主存地址寄存器MA；主存－cache地址变换机构从主存地址寄存器MA获取地址判断该单元内容是否已在cache中存放副本，如果副本已经在cache中了，称为命中；反之称不命中或命中失效。cache基本原理cache基本原理cache的命中率命中率指CPU所要访问的信息在Cache中的比率；所要访问的信息不在Cache中的比率称为失效率。增加cache的目的，就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此，cache的命中率应接近于1。由于程序访问的局部性，这是可能的。cache基本原理当命中时立即把访问地址变换成它在cache的地址，然后驱动cache存储体。当是读操作时，CPU从cache中直接读取信息；若是写操作，不但要把新内容写入cache存储器中，而且必须同时写入主存，使主存和cache内容同时修改，保证主存和副本内容一致，这种方法也叫直达法。cache基本原理有的机器考虑到当写入操作很频繁或者写入的是中间结果，每次写入主存很浪费时间，于是设计成每次只改写cache的内容并不立即修改主存中相应的单元，只有当cache中被写过的块要被新进入cache的信息块取代时才一次写回主存里，这种方法称回写法。cache基本原理如果CPU要访问的内容根本不在cache中，即“不命中”，那么CPU转去直接访问主存。若是读操作，CPU则从主存读取信息的同时，cache控制部件把该地址所在那块存储内容从主存一次调进cache存储器，以存储块为单位调入cache存储器可以提高下次访问的命中率。若是写操作，则处理就简单多了，很多计算机系统只向主存写入信息，不必同时把这个地址所在的存储内容再调入cache存储器中。cache基本原理直达法：优点：数据不会出现不一致缺点：对写操作没有高速缓存的作用回写法：优点：速度快缺点：存在数据不一致隐患cache基本原理对于共享一个主存的多处理机系统，因为处理机各自拥有cache存储器，所以必须采用写直达法将任何一个cache中修改的内容同时写入主存，保证其他cache向主存调用信息块时是修改过的而不是失效的信息。这点对于拥有多个处理机而共享一个主存的计算机系统特别重要。7.2高速缓冲存储器（cache）cache的工作机制cache基本原理地址映象（映射）与地址变换cache与主存数据的一致性替换策略高速缓冲器cache的构成地址映象(映射)与地址变换地址映象把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。地址变换信息按这种映象关系装入Cache后，执行程序时，将主存地址变换成Cache地址的变换过程叫做地址变换。地址映象和变换密切相关。地址映象(映射)与地址变换使用Cache的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的。这带来的另一好处是Cache的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到Cache的存在。地址映象(映射)与地址变换在高速缓冲存储器中把Cache和主存机械等分为相同大小的块，每一块是由若干个字（或字节）组成。例：某机主存容量为1MB，划分为2048块，每块512B；Cache容量为8KB，划分为16块，每块512B。块0块1块15Cache标记标记标记块0块1块2047主存m位

块…字0字1字511地址映象(映射)与地址变换由于Cache的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的哪一块的副本（拷贝）。块0块1块15Cache标记标记标记块0块1块2047主存m位

块…字0字1字511地址映象(映射)与地址变换标记的有效位每个标记设置有一个有效位。机器加电启动时，Reset信号将所有标记的有效位置“0”，即无效。程序执行过程中，Cache不命中时，逐步将指令块或数据块从主存调入Cache中的某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或数据时，可直接从Cache中取指令或数据。字块0字块1字块Lm-1~~~~.........标记Cache012r-1

标记有效位地址映象(映射)与地址变换因刚加电时所有标记位都为“0”，开始执行程序时，命中率较低。另外Cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。地址映象(映射)与地址变换基本的地址映象方式：直接映象全相连映象组相连映象地址映象(映射)与地址变换直接映射方式这是一种多对一的映射关系，一个主存块只能映象到Cache的一个特定块位置上去。在这种映象方式中：主存的第0块，第16块，第32块，…，只能映象到Cache的第0块；而主存的第1块，第17块，第33块，…，只能映象到Cache的第1块；……地址映象(映射)与地址变换直接映象7位Cache地址4位9位主存地址7位4位9位11位9位主存地址地址映象(映射)与地址变换直接映象的地址变换方法地址映象(映射)与地址变换优点：实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在Cache中。缺点：不够灵活，主存的多个字块只能对应唯一的Cache字块，因此，即使Cache别的地址空着也不能占用。Cache存储空间得不到充分利用，降低了命中率。地址映象(映射)与地址变换全相联映象方式块0块1块15Cache标记标记标记标记标记标记.........块0块1块15块16块17块31块2047主存TagCache地址4位9位11位9位主存地址允许主存中的每一个字块映象到Cache的任何一个字块位置上，最灵活但成本最高的一种方式。地址映象(映射)与地址变换全相联映象的地址变换方法地址映象(映射)与地址变换全相联映象的地址变换方法的优缺点：优点：灵活，块冲突概率小。只有当Cache中全部装满后，才有可能出现块冲突；缺点：要作相联搜索，速度慢，代价高。地址映象(映射)与地址变换这只是一个理想的方案。两个原因使其实际上很少采用：标记位数从7位增加到11位，使Cache标记容量加大；访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在Cache中。由于Cache速度要求高，通常由“按内容寻址”的相联存储器完成，所需硬件逻辑电路很多，以至于无法用于cache中。实际的Cache组织则是采取各种措施来减少所需比较的地址数目。地址映象(映射)与地址变换组相联映射方式组间全相联，组内直接映像直接映象和全相联映象方式的一种折衷方案。地址映象(映射)与地址变换注意：当Cache只有一个组并且每组16块时，此时为直接映像；当Cache有16组并且每组一个块时，则为全相联映像。8位3位9位1位3位9位7.2高速缓冲存储器（cache）cache的工作机制cache基本原理地址映象（映射）与地址变换cache与主存数据的一致性替换策略高速缓冲器cache的构成cache与主存数据的一致性cache中存放的是主存中部分信息的副本。为了保证CPU存取的数据准确无误，要求cache中每一个地址上的数据与主存中相应存储单元的数据保持完全相同，这种性质称cache与主存数据的一致性。写直达法和回写法是常见的保持数据一致性的算法。cache与主存数据的一致性cache与主存数据的不一致的情况：CPU从cache读入数据重新写入修改后的新数据时；主存数据修改。例如多处理机系统，其中一个cache内容修改后立即用写直达法写入主存又导致主存数据可能与其他cache的副本不一致。又例如，计算机的DMA访问直接修改了主存数据，也可能造成与cache数据的不一致性。cache与主存数据的一致性通常采用的处理办法有：主存监视法：利用硬件机构使cache控制器能监视所有设备对主存的操作或访问，凡对主存的写入也立即对cache中相应单元进行拷贝，从而保证数据的一致性设置“不可cache区”：即在主存中开辟一块存储区域，该区域数据不能调入cache，不受cache控制器管理，但其他设备进入的数据只能直接写入该区域。所以不会产生与cache中数据的不一致性。“不可cache区”可以通过BIOS设置程序来设置。7.2高速缓冲存储器（cache）cache的工作机制cache基本原理地址映象（映射）与地址变换cache与主存数据的一致性替换策略高速缓冲器cache的构成替换策略在主存－cache存储体系工作过程中，主存和cache存储器之间信息以块为单位调度，信息块的长度取决于主存的结构设计，主存常设计成多体交叉存储结构。当信息块需要调入cache存储器而cache存储器中已经占满信息时，cache存储器的替换控制部件将按一定的替换策略淘汰cache中旧有的一块信息，被更新的旧信息块应该是下一段时间内估计是最少使用的，然后用新的信息块覆盖掉。替换策略常用的替换策略有两种：

先进先出策略－FIFO策略总是更换掉当前cache中最先进入的信息块这种方法控制简单，实现容易近期最少使用策略－LRU策略替换策略近期最少使用策略－LRU策略：遵循的规则是新信息块替代的是当前cache存储器中被使用次数最少的，即最不活跃的那块信息；使用LRU方法的cache存储器每一个字块都要附设一个计数器记录被使用的情况，每当cache中的一块信息被命中时，比命中块计数值低的信息块均加1，而命中块计数器清0；显然，这种技术方法各信息块的计数值总是不相同的。替换策略一旦不命中情况发生时，新信息块从主存调入cache存储器替换计数值最大的那片存储区，新信息块计数值为0，其余信息块计数均加1，保证了那些活跃的信息块－－经常被命中或最近被命中的信息块计数值要小，而近来越来越不活跃的信息块计数值越大；LRU策略是目前使用较多的一种策略，能够有效的提高命中率。替换策略无论FIFO策略还是LRU策略，其实最先被调入cache的信息块或最近最少使用的信息块都不能肯定是最近将绝不会使用，所以替换策略不能作为最合理最优秀的。但是研究表明，FIFO和LRU策略明显地提高了cache存储器的命中率，可以达到百分之九十左右，其中LRU策略的命中率比FIFO更高一些。替换策略Cache的命中率反映了CPU需要访问的数据在cache中能直接找到的概率。影响命中率的因素有：替换策略cache的结构因素包括cache高速缓冲存储器大小、传送块的大小若cache的存储容量越大，保存副本越多，命中率就越高访问程序和数据