存储系统公开课课件.ppt

1、1第章存储系统 第第4 4章章 存储系统存储系统 24.1 存储系统及性能存储系统及性能4.1.1 存储系统的层次结构存储系统的层次结构 存储器的三个主要指标是：容量、速度和价格。存储器容量 SMWlm。其中，W为单个存储体的字长，l为单个存储体的字数，m为并行工作的存储体的个数。存储器的速度可以用访问时间TA、存储周期TM或频宽Bm来描述。Bm是存储器被连续访问时，可提供的数据传送速率。其单位为传送位数(字节数)/秒。存储器的价格可以用总价格C或每位价格c来表示。具有SM位的存储器每位价格 c=C/SM。第第4 4章章 存储系统存储系统 3 人们对存储器的要求是“容量大、速度快、价格低”，而

2、这三个要求是相互矛盾的。为解决以上矛盾，除了研制新型存储器之外，还可采用以下技术途径。（1）在组成上引入并行和重叠技术，构成并行主存系统，使主存的频宽得到较大的提高。（2）改进存储器的系统结构，发展多层次存储体系(或称存储系统)。层次结构的存储体系在速度、容量、价格等性能指标方面的综合水平优于任何的单级存储器。第第4 4章章 存储系统存储系统 4存储体系的概念 把两个或两个以上速度、容量、价格不相同的存储器从系统结构的角度，通过软、硬结合有机地联系在一起，使之成为一个统一的整体，其速度接近于速度最快的存储器，容量等于容量大的存储器，每位价格接近价格低的存储器，并且存储器内的信息调动对应用程序设

3、计者是透明的，这样的存储系统就称为存储体系或存储层次。第第4 4章章 存储系统存储系统 5存储体系的形成 在存储容量方面，为弥补主存容量的不足，形成主存 辅存存储层次，并进而发展成为虚拟存储系统。工作中虚实地址变换及程序调动对应用程序员是透明的，但对系统程序员是不透明的。在存取速度方面，为弥补主存速度的不足，形成Cache 主存存储层次。使Cache 和主存构成的存储体系从CPU来看是一个整体，且具有接近Cache的速度，主存的容量，接近主存的每位价格。信息在这一存储层次中的调动全部由硬件实现，故这一存储层次对应用程序员和系统程序员来说都是透明的。第第4 4章章 存储系统存储系统 6存储体系的

4、层次结构如图所示。其中，M1，M2，Mn是用不同技术实现的存储器。它们之间以块或页面为单位传送数据。设ci、TAi、SMi分别表示Mi的每位价格、访问时间和存储容量，则多级存储层次中任意相邻两级之间存在以下关系：cici+1、TAiTA(i+1)、SMiSM(i+1)。层次存储系统设计追求的目标是：从CPU来看，该存储体系是一个整体，且具有接近于M1的速度和Mn的容量和价格。第第4 4章章 存储系统存储系统 7 存储体系的管理总是力图使它能发挥最大的效率，即尽可能使即将被访问的信息在层次最高、速度最快的M1当中。以此为目的进行管理的依据是基于程序的局部性原理。局部性原理指出，绝大多数程序访问的

5、指令和数据是相对簇聚的。它包括时间上的局部性和空间上的局部性。时间局部性是指在最近的未来将要用到的信息很可能是现在正在使用的信息。第第4 4章章 存储系统存储系统 8 空间局部性是指在最近的未来将要用到的信息很可能与现在正在使用的信息在程序空间上是保存在相邻或相近位置的。CPU访存时，由M1开始，首先访问Mi，若在Mi中找不到所需数据，则访问Mi+1，并将包含所需数据的块或页面调入Mi，依此类推。第第4 4章章 存储系统存储系统 94.1.2 存储系统的性能参数存储系统的性能参数 以两级存储层次结构为例进行分析。存储层次由M1和M两个存储器构成，设M1的容量、访问时间和每位价格分别为SM1、T

6、A1和c1，M2的参数为SM2、TA2和c2。第第4 4章章 存储系统存储系统 10 1.每位平均价格cSSScSccMMMM212211 当SM1 t 是未来时刻)，然后选择 tit 最大的页面进行替换。特点 最能反映程序局部性，命中率最高。实现 只有得到实际页面地址流(运行过程序)才能实现该算法。第第4 4章章 存储系统存储系统 635.影响主存命中率的因素 替换算法的影响 地址流的影响 分配给程序主存页数的影响 第第4 4章章 存储系统存储系统 64（1）替换算法对命中率的影响 一般LRU算法的命中率优于FIFO算法。第第4 4章章 存储系统存储系统 65（2）页地址流对命中率的影响 当

7、一个循环程序的虚页数大于分配给它的主存实页数时FIFO和LRU算法的命中率将大大降低。严重时会发生“程序颠簸”。第第4 4章章 存储系统存储系统 66程序颠簸 因将要用到的页依次从主存被替换出去，而连续出现页面失效。这是虚拟存储技术的代价，在执行存取时往往引起可观的I/O操作，要占用相当的时间。这部分对于直接处理问题无用的时间称为“系统开销”。I/O操作是把不在主存的信息从辅存中找到并调入主存，而把主存中已不用的信息送回辅存。这种信息交换在严重时可使系统只忙于交换，而无法对问题进行处理，这种情况被称为系统发生了“颠簸”。第第4 4章章 存储系统存储系统 67（3）程序的主存页数对命中率的影响

8、给程序分配的主存页数越多，虚页装入主存的机会应该越多，但实际上能否提高命中率还与替换算法的类型有关。举例，FIFO算法的实页数增加，命中率反而有可能下降。第第4 4章章 存储系统存储系统 686.堆栈型替换算法及模拟处理技术（1）堆栈型替换算法A 是长度为L的任意一个虚页地址流；t 为已处理过t1个虚页的时间点；n 为分配给该虚页地址流的主存实页数；Bt(n)表示在t时间点、在n个主存实页中的虚页集合；Lt 表示到t时间点已处理过的虚页地址流中虚页号相异的页数。如果替换算法具有下列包含性质：当nLt时，Bt(n)Bt(n1)当nLt时，Bt(n)Bt(n1)则此替换算法为堆栈型替换算法。第第4

9、 4章章 存储系统存储系统 69LRU t 1 2 3 4 5 6 7 8 9 10 11 12 A 1 2 3 4 1 2 5 1 2 3 4 5n=3 1 1 1 4 4 4 5 5 5 3 3 3 2 2 2 1 1 1 1 1 1 4 4命中命中2次次 3 3 3 2 2 2 2 2 2 5n=4 1 1 1 1 1 1 1 1 1 1 1 5 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 5 5 5 5 4 4命中命中4次次 4 4 4 4 4 4 3 3 3 第第4 4章章 存储系统存储系统 70OPT t 1 2 3 4 5 6 7 8 9 10 11 12 A 1

10、 2 3 4 1 2 5 1 2 3 4 5n=3 1 1 1 1 1 1 1 1 1 3 4 4 2 2 2 2 2 2 2 2 2 2 2命中命中5次次 3 4 4 4 5 5 5 5 5 5n=4 1 1 1 1 1 1 1 1 1 1 4 4 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3命中命中6次次 4 4 4 5 5 5 5 5 5 第第4 4章章 存储系统存储系统 71 LRU算法和OPT算法满足包含性质，属于堆栈型替换算法。而LRU算法不满足包含性质，如B7(3)=1，2，5，而B7(4)=2，3，4，5，因此LRU算法不是堆栈型替换算法。

11、采用堆栈型替换算法访问主存的命中率会随分配给程序的主存实页数的增加而单调上升，至少不会下降。可采用堆栈处理技术对访存虚页地址流进行一次模拟处理，即可同时获得对此虚页地址流分配不同主存实页数时的主存命中率。第第4 4章章 存储系统存储系统 72（2）堆栈型替换算法的模拟处理技术 用堆栈St表示主存在 t 时间点的状态，St 是Lt 个页面在堆栈中的有序集合，St(1)是栈顶，St(Lt)为栈底。根据堆栈型替换算法的包含性质，应有：n Lt时 Bt(n)=St(1),St(2)St(Lt)n Lt时 Bt(n)=St(1),St(2)St(n)给地址流分配的主存为 n 页时,其中存放的程序页号应由

12、St的前 n 项决定。而 t 时间点所用程序页At是否命中，则看St-1 的前 n 项中是否有At，若有则命中。此模拟处理进行一次得到St(1)St(Lt)后，可同时知道分配主存页面数 n 不同时的相应命中率。第第4 4章章 存储系统存储系统 73 例4.2对图4.17给出的访存虚页地址流，采用LRU算法进行堆栈模拟处理。分别求出分配给该程序主存实页数为1，2，3，4和5页时的主存命中率。对虚页地址流进行堆栈模拟处理的过程：命中率0.000.170.420.500.58 第第4 4章章 存储系统存储系统 74（3）堆栈型替换算法的发展 根据堆栈型替换算法实页数 n 与命中率的关系，提出可优化系

13、统性能的动态算法。页面失效频率法 根据各道程序运行中主存页面失效率的高低，由操作系统动态调节分配给每道程序的实页数。确定一个主存页面失效率的限值，当主存页面失效率超过限值时就自动增加分配的主存页数来提高其命中率；而当主存页面失效率低于限值时就自动减少分配的主存页数，以便释放出部分主存页面给其他程序使用，从而使整个系统的主存命中率和主存利用率都得到提高。第第4 4章章 存储系统存储系统 754.3.4 虚拟存储器中的相关技术虚拟存储器中的相关技术 1.多级页表技术 在页式和段页式虚拟存储器中，页表的长度取决于某道(段)程序中所划分的页数。若程序较大、页面很多时，页表的大小很可能超过一个页面，此时

14、页表可能分存于主存中不连续的页面中。这时用前述地址变换的方法就可能出错。如虚地址为：12位 8位 页表就需要2 P212行，而页面大小为2D28个存储单元，若每个页表行占用一个存储单元，该页表要分存于16个页面，为此需建立多级页表。虚地址虚页号页内地址 第第4 4章章 存储系统存储系统 76 用页表基址寄存器指明一级页表起点，而一级页表中各表项地址字段指明各二级页表基址，以此类推，直到最后一级页表指明相应的实页号。用树的概念可得出页表级数 i 和P、D的关系为 如果页表中的每一项（行）需要Be个编址单元，而Be是2的幂，则Be需用 个地址位表示。此时 DPiD2log2log22BNe2elo

15、gNDPie 第第4 4章章 存储系统存储系统 77而用内页表中装入位为 0 的行的实页号字段存放该程序的虚页在辅存中的实地址，以方便调页时实现用户虚页号到辅存实地址的变换。Cache一般采用的取算法：这种信息交换在严重时可使系统只忙于交换，而无法对问题进行处理，这种情况被称为系统发生了“颠簸”。对被选择范围内其他的计数器，凡是计数值小于命中块所对应计数器原值的加1，其他计数器不变。当nLt时，Bt(n)Bt(n1)预取算法有两种不同的方法：恒预取和不命中时预取。而共享主存的多处理机系统为保证各处理机经主存交换信息时不出错，多数采用写直达法。用内页表中装入位为 1 的行的实页号字段存放该程序的

16、虚页在主存中的实地址，实现虚地址到主存实地址的变换。当所有占用位全为1，而页面失效时，则替换使用位为0的页。可采用堆栈处理技术对访存虚页地址流进行一次模拟处理，即可同时获得对此虚页地址流分配不同主存实页数时的主存命中率。其单位为传送位数(字节数)/秒。多用户虚地址Ns由用户号U（或程序号）、虚页号P和页内偏移D等三部分组成。若主存空间为N2n字，则访问该存储器的地址为n位。写直达法是利用Cache主存存储层次在CPU和主存之间的直接通路，每当CPU将信息写入Cache的同时，也通过此通路直接写入主存。2 地址映像与地址变换在出现写不命中时，这两种方法都面临着一个在写时是否取的问题。还经常使用不

17、命中率或失效率F这个参数反映不命中的情况：Cache的空间利用率最高。OPT t 1 2 3 4 5 6 7 8 9 10 11 12当任何处理机要写入Cache时，不仅写入自己Cache的目标块和主存中，还把信息播写到其他包含此单元的Cache中，或者让其他Cache包含此单元的块作废。2.加快地址变换的技术 多用户虚存空间比主存空间大得多，而页表的大小取决于虚页的数量。一般将页表放在工作速度较低的主存中。提高地址变换速度的方法有：目录表法 快表慢表技术 内页表和外页表 第第4 4章章 存储系统存储系统 78 （1）目录表法 将页表压缩成只保存已装入主存(即装入位为1)的虚页与实页位置对应关

18、系表项的相联目录表(简称目录表)。该表的容量取决于主存的实页数，且不设装入位，采用按内容访问的相联存储器构成，以实现快速查表。该方法的缺点是目录表较大时，成本较高，且查表速度会降低。第第4 4章章 存储系统存储系统 79采用目录表进行地址变换的过程：第第4 4章章 存储系统存储系统 80 （2）快表慢表技术 由于程序访问的局部性特点，在一段时间内，地址变换对页表的访问会只用到表中很少的几行。故可用高速硬件(相联存储器)构成比页表小得多的部分“目录表”(即快表)，存放当前正在使用的虚、实地址映像关系，而原来的页表则称为慢表。快表的内容是慢表的小小副本,其容量可为816行，故相联查找的速度将会很快

19、。第第4 4章章 存储系统存储系统 81 快表与慢表构成了由两级存储器组成的用于支持地址变换的存储层次。它使地址变换的速度接近快表的访问速度，而慢表的容量不受限制。若快表的命中率高，地址变换所需时间与主存的读写周期相比可忽略不计，则虚拟存储器的访问速度就可接近于主存的工作速度。第第4 4章章 存储系统存储系统 82采用快慢表的虚拟存储器的地址变换：第第4 4章章 存储系统存储系统 83 （3）内页表和外页表 在页式和段页式虚拟存储器中，虚页数一般远多于实页数。故页表中绝大部分装入位为 0 的行中实页号字段及其他字段为无效，这将使页表的空间利用率大大降低。为提高页表的利用率，可对页表进行修改。第

20、第4 4章章 存储系统存储系统 84 页面失效故障：CPU访问某多用户虚地址Ns所在的虚页未装入主存。当发生页面失效故障时，将由操作系统或I/O处理机把要访问的虚页从辅存调入主存，到辅存中调页需要提供该虚地址在辅存中的实际地址Nvd。辅存一般按块编址，可让辅存块与主存页面的大小相等，以提高调页效率。磁盘的辅存实(块)地址Nvd的格式为：Nvd 磁盘机号柱面号磁头号块号 第第4 4章章 存储系统存储系统 85 多用户虚地址Ns到辅存实(块)地址N vd之间的变换与前述页表方式类似，程序(用户)在装入辅存时由操作系统建立一个存放用户虚页号P与辅存实(块)地址Nvd映像关系的表，称为外页表，用于实现

21、外部地址变换。而前述用于实现内部地址变换的存放P与p映像关系的页表称为内页表。外页表也是2P项(行)，每行中用装入位表示该信息块是否已由海量存储器装入磁盘。当装入位为“1”时，辅存实地址字段内容有效，是该信息块(虚页)在辅存中的实际位置。第第4 4章章 存储系统存储系统 86 外页表通常存在辅存中，并采用软件方法查外页表实现地址变换。地址变换过程如下图：第第4 4章章 存储系统存储系统 87 当某道程序初始运行时，从辅存调信息页入主存并建立内页表，同时把未调入主存的其他虚页在外页表的内容转录到内页表中。用内页表中装入位为 1 的行的实页号字段存放该程序的虚页在主存中的实地址，实现虚地址到主存实

22、地址的变换。而用内页表中装入位为 0 的行的实页号字段存放该程序的虚页在辅存中的实地址，以方便调页时实现用户虚页号到辅存实地址的变换。第第4 4章章 存储系统存储系统 88各地址空间与内、外页表的关系：第第4 4章章 存储系统存储系统 894.3.5虚拟存储器的工作过程虚拟存储器的工作过程 第第4 4章章 存储系统存储系统 904.4 高速缓冲存储器（高速缓冲存储器（Cache）在处理机和主存之间设置一个高速、小容量的缓冲存储器（Cache），构成存储体系结构中的“Cache主存”存储层次，使之从CPU观察，具有接近于Cache的速度，又具有主存的容量。高速缓冲存储器用以弥补主存速度的不足。在

23、当代计算机系统中Cache技术已被普遍使用，Cache的容量不断增大，Cache的管理全部硬化，其部件高度集成，这些已成为当代Cache的特征。第第4 4章章 存储系统存储系统 914.4.1 Cache的基本原理的基本原理 1.Cache的基本结构和工作原理 将Cache和主存分成相同大小的块(行)，每块(行)由若干个字(节)组成。主存地址nm由块号B和块内地址W组成，Cache地址nc由块号b和块内地址w组成。且Cache的块内地址w与主存的块内地址W相同。第第4 4章章 存储系统存储系统 92 第第4 4章章 存储系统存储系统 93 Cache工作过程：（1）CPU送出主存地址；（2）地

24、址映像变换机构判定是否命中；（3）如命中则变换地址访Cache，与处理机以单字宽传送信息；（4）如失效则用主存地址访主存，被访问字从单字宽通路送处理机，并将含该字的一块信息经多字宽通路从主存调入Cache；（5）若Cache已满，则采用替换算法将含被访字的块替换进Cache；（6）新块调入Cache时要更新地址映像表中的相关信息 第第4 4章章 存储系统存储系统 942.Cache存储器的特点 （1）在微处理器芯片中集成了一定容量Cache，它一般由高速SRAM芯片组成，且Cache主存之间的地址映像和变换，以及替换、调度算法全部由专门的硬件来实现。Cache对系统程序员和应用程序员都是透明的

25、。（2）访问Cache包括查表进行地址变换和真正访问Cache两部分工作。在设计时可以让前一地址的访问Cache与后一地址的查表变换在时间上采用重叠流水方式，以提高CPU访问Cache的速度。第第4 4章章 存储系统存储系统 95 （3）Cache发生块失效时，从主存调块的时间只是微秒级，故采用在Cache到CPU和主存到CPU之间分别设置通路，一旦出现Cache块失效，就使Cache调块与CPU访主存同时进行，实现CPU对主存的读直达 和写直达。Cache既是“Cache主存”层次中的一级，又是CPU与主存之间的一个旁视存储器。第第4 4章章 存储系统存储系统 96 （4）Cache与主存之

26、间以块为单位进行数据交换。为加快调块，块的容量一般等于CPU在一个主存读/写周期内由主存所能访问到的字数。故具有Cache的存储系统中的主存通常采用多体交叉存储结构。（5）由于主存被计算机系统的多个部件共享，难免发生访存的冲突。应该把Cache访问主存的优先级尽量提高，一般要高于通道访存的级别。第第4 4章章 存储系统存储系统 974.4.2 地址映像与地址变换地址映像与地址变换 在Cache主存层次中，主存容量远大于Cache的容量。地址映像是指主存块按什么规则定位于Cache之中；而地址变换就是主存块装入Cache后，每次访Cache时如何将主存地址变换成对应的Cache地址。地址映像和地

27、址变换紧密相关。常用的地址映像方式有 全相联映像 直接映像 组相联映像 段相联映像 第第4 4章章 存储系统存储系统 98 1.全相联映像及变换 全相联映像方式：主存中的任意一块可以映像到Cache中任意的块位置上。如果Cache的块数为2b，主存的块数为2B。映像关系为：第第4 4章章 存储系统存储系统 99 存放这种映像关系的目录表由高速的相联存储器构成，其行数为2b，宽度为Cache地址中块号b的长度与主存地址中块号B的长度之和再加一个有效位。有效位为1，表示映像关系有效，否则映像关系无效。第第4 4章章 存储系统存储系统 100 全相联地址变换：第第4 4章章 存储系统存储系统 101

28、 全相联映像法的特点 优点：块冲突概率最低；Cache的空间利用率最高。缺点：随着Cache的容量越来越大，存放目录表的相联存储器的容量也越来越大，使其代价相对较大，且会降低地址变换的速度。第第4 4章章 存储系统存储系统 102 2.直接映像及变换 直接映像方式：指主存中的每一块只能映像到Cache中的一个特定块位置上，设主存块的块号为B、Cache块的块号为b，若Cache的块容量（块数）为2b，则它们的映像关系可表示为：bB mod 2b 这相当于把主存空间按Cache的空间分成2E个区，主存各区中区内块号相同的那些块都映像到Cache中相同块号的那个块位置上。第第4 4章章 存储系统存

29、储系统 103直接地址映像：第第4 4章章 存储系统存储系统 104 按照直接映像规则，装入Cache中的某块信息可能来自主存中不同区对应于此位置的块。为了区分是主存中哪个区的块装入Cache中的对应块位置，建立一个称为区号标志表的按地址访问的表存储器来存放Cache中的各块目前是被主存中哪个区的相应块所占用的信息。区号标志表存储器的行数与Cache的块数相同，字长为主存地址中区号E的长度，另加一个有效位。第第4 4章章 存储系统存储系统 105直接映像的地址变换：第第4 4章章 存储系统存储系统 106 为了提高Cache的访问速度，有些系统将区号标志表存储器与Cache合并成一个存储器。用

30、主存地址的块号B直接访问这个Cache存储器，把有效位、区号和这一块的所有数据同时读出来，由区号和有效位确定该块是否命中和有效，若命中且有效，则通过一个多路选择器，在块内地址W的控制下，从读出的多个字中选出指定的那个字送往CPU。第第4 4章章 存储系统存储系统 107快速的直接映像地址变换：第第4 4章章 存储系统存储系统 108 直接映像方式的特点 优点：所需硬件简单，不需要相联存储器，因此成本很低。访问Cache与访问区号表、比较区号是否相符的操作是同时进行的。省去了地址变换所花费的时间。缺点：Cache的块冲突概率比较高，使Cache的命中率下降，而且Cache的利用率很低。第第4 4

31、章章 存储系统存储系统 109 3.组相联映像及变换 组相联映像方式：把主存按Cache的容量分区，主存中的各区和Cache再按同样大小划分成数量相同的组，组内按同样的大小划分成数量相同的块，主存的组到Cache的组之间采用直接映像方式，但组内各块之间则采用全相联映像方式。第第4 4章章 存储系统存储系统 110组相联映像方式：第第4 4章章 存储系统存储系统 111 组相联映像方式中，用于保存地址变换信息的表称为块表。块表存储器可采用按地址访问与按内容访问混合的存储器实现，块表的行数应与Cache块数相等，块表的字长为主存地址的区号E、组内块号B与Cache地址的组内块号b的长度之和，另外加

32、一个有效位及其他控制字段等。组相联映像方式的地址变换过程如图4.34所示。第第4 4章章 存储系统存储系统 112图4.34 组相联映像的地址变换 第第4 4章章 存储系统存储系统 113 组相联映像方式的特点：组相联映像的Cache块冲突概率要比直接映像的低得多。只有当主存块要进入的Cache对应组中所有块位置都被占用时，才出现块冲突，且组的容量越大(组内块数越多)，Cache块冲突的概率就越低。组相联映像进行地址变换时参与相联比较的行数、位数要小得多，这都会使查表速度提高，且在成本上要低得多。第第4 4章章 存储系统存储系统 114 段相联映像方式：把主存和Cache分成具有相同的Z块的若

33、干段，段与段之间采用全相联映像，而段内各块之间则采用直接映像。段相联实质上是组相联的特例，它采用组间全相联、组内直接映像。采用段相联映像的目的与采用组相联映像一样，主要是为减小相联目录表的容量、降低成本、提高地址变换的速度。当然，其Cache块冲突概率将比全相联的高。段相联映像方式如图4.35所示。第第4 4章章 存储系统存储系统 115图4.35 每段有Z个块的段相联映像 第第4 4章章 存储系统存储系统 1164.4.3 Cache的替换算法及实现的替换算法及实现 当访存发生Cache块失效而需要把主存块按所使用的映像规则装入Cache时，如果又出现Cache块位置冲突，就必须按某种替换策

34、略选择将Cache中的某一块替换出去。直接映像方式实际上不需要替换算法。而全相联映像方式中的替换算法实现起来最复杂。在组相联映像方式中，则需要从同一组内的几个Cache块中选择一块替换出去。第第4 4章章 存储系统存储系统 117 Cache主存存储层次的替换算法与虚拟存储器的大致相同，一般采用FIFO算法或LRU算法，其中LRU算法最常用。但由于CPU调Cache块的时间在微秒级，因此其替换算法必须全部用硬件实现。下面介绍两种用硬件实现LRU替换算法的具体方法。第第4 4章章 存储系统存储系统 118 1.计数器法 在块表中为每个Cache块设置一个计数器，计数器的长度与被选择替换范围内的C

35、ache块号字段的长度相同。计数器的使用及管理规则是：（1）块被装入或被替换时，其对应的计数器清零，而被选择范围内其他块对应的计数器都加1。（2）块命中时，其对应的计数器清零。对被选择范围内其他的计数器，凡是计数值小于命中块所对应计数器原值的加1，其他计数器不变。（3）需要块替换时，对被选择范围内的所有计数器进行相联比较，选择计数值最大（一般为全1）的计数器对应的块作为被替换块。第第4 4章章 存储系统存储系统 119 例4.3某Cache系统，采用组相联映像方式，每组4块，用计数器法实现LRU替换算法。若映像到某Cache组的访存块地址流为：1，3，2，8，9，8，请说明该组内 4个Cach

36、e块计数器的工作情况。解：4个Cache块的计数器工作情况如表4.1所示。由表可见，当4个Cache块位置被占满后Cache块0的计数器值为“11”，是4个计数器值中最大的。当主存块9要调入时，发生块冲突，主存块9替换Cache块0位置上的主存块1。第第4 4章章 存储系统存储系统 120表4.1 Cache的LRU替换算法的计数器工作情况主存块地址流132898块号计数器块号计数器块号计数器块号计数器块号计数器块号计数器Cache块0100101110111900901Cache块1300301310311311Cache块2200201210210Cache块3800801800装入装入装

37、入装入替换命中 计数器法需要硬件有相联比较功能，因此其速度较低，也比较贵。第第4 4章章 存储系统存储系统 121 2.比较对法 基本思想是让各块两两构成比较对，用一个触发器的状态表示该比较对的两块被访问过的先后顺序，经门电路组合，可从多个块中找出最久未被访问过的块。假设有A、B、C三个块，互相之间不重复的组合有AB、AC和BC三对。分别用一个触发器的状态表示每个比较对内两块被访问过的顺序，例如，触发器TAB1表示A比B更近被访问过，TAB0表示B比A更近被访问过，TAC和TBC也类似定义。第第4 4章章 存储系统存储系统 122 以最久未被访问过的块作为被替换块的布尔表达式分别为：用触发器、

38、门电路等硬件组合实现比较对法的逻辑电路如图4.36所示。在每次CPU访问到Cache中的某块时，通过改变与该块有关的比较对触发器的状态来记录各块被访问过的顺序。对于块数更多的情况，可采用同样的思路实现。TTCBCACLRUTTBBCABLRUTTAACABLRU 第第4 4章章 存储系统存储系统 123图4.36 实现比较对法的逻辑电路 第第4 4章章 存储系统存储系统 124 若块数为p，触发器的个数为 ，即触发器个数随块数的平方递增，所以比较对法只适用于组内块数较少的组相联映像的Cache存储器。实现替换算法的设计应考虑以下两点：如何对每次访问进行记录，即记录Cache块被访问的先后次序。

39、如何根据所记录的信息来判断哪一块是最近最少使用的块，使之成为发生Cache块冲突时最先被替换的块。2/22ppCp 第第4 4章章 存储系统存储系统 1254.4.4 Cache的性能分析的性能分析 1.Cache的透明性 由于Cache存储器的地址变换、替换算法和调度算法等均由硬件实现，故“Cache主存”层次对系统程序员和用户都是透明的，且Cache对CPU和主存之间的信息交换也是透明的。对于Cache的透明性可能引发的问题及其影响需慎重对待，并予以妥善地解决。第第4 4章章 存储系统存储系统 126 （1）一致性问题与写策略 主存某单元中的内容与Cache对应单元中的内容可能在一段时间内

40、不一致：CPU修改Cache内容时，主存对应部分内容还没变化；I/O处理机（IOP）已将新的内容输入主存某区域，而Cache对应部分内容却可能还是原来的。以上Cache内容与主存内容不一致的情况，在Cache对CPU和主存均是透明的前提下，可能引发错误 第第4 4章章 存储系统存储系统 127 为了解决这个问题，提出了主存修改算法，即写策略。写回法是指在CPU执行写操作命中Cache时，信息只写入Cache，仅当需要被替换时，才将已被改写过的Cache块先送回主存，然后再调入新块。写直达法是利用Cache主存存储层次在CPU和主存之间的直接通路，每当CPU将信息写入Cache的同时，也通过此通

41、路直接写入主存。第第4 4章章 存储系统存储系统 128 写回法和写直达法的特点：1）写回法把开销花费在替换时，而写直达法则是把开销花费在每次写Cache时都要附加一个比写Cache时间长得多的写主存时间。2）写回法和写直达法都需要有少量缓冲器。3）写回法使主存的通信量比写直达法的要小得多，但它增加了Cache的复杂性，并且写回法在块替换前，会存在主存内容与Cache内容不一致的问题。4）写直达法的可靠性比写回法的可靠性要高。5）写直达法需花费大量缓冲器和其他辅助逻辑来减少CPU为等待写主存所耗费的时间，相对而言写回法的实现成本则要低得多。第第4 4章章 存储系统存储系统 129 在出现写不命

42、中时，这两种方法都面临着一个在写时是否取的问题。这有两种解决方法：一种是不按写分配法，即当Cache写不命中时只写入主存，该单元所在块不从主存调入Cache；另一种是按写分配法，即当Cache写不命中时除写入主存外，还把该单元所在块由主存调入Cache。写回法一般采用“按写分配”，写直达法一般采用“不按写分配”。一般单处理机Cache多数采用写回法以节省成本；而共享主存的多处理机系统为保证各处理机经主存交换信息时不出错，多数采用写直达法。第第4 4章章 存储系统存储系统 130 对于Cache的内容跟不上已变化了的主存内容的问题，一种解决方法是当IOP向主存写入新内容时，由操作系统用某个专用指

43、令清除整个Cache。这种方法的缺点是使Cache对操作系统和系统程序员非透明。另一种方法是当IOP向主存写入新内容时，由专用硬件自动地将Cache内对应区域的副本作废，而不必由操作系统干预，从而保持了Cache的透明性。另外，采用CPU、IOP共享一个Cache也是一种办法。第第4 4章章 存储系统存储系统 131 （2）多处理机系统的Cache结构及一致性 多处理机系统的一般形式，是由多个CPU和多个I/O处理机组成共享主存的系统。对于共享主存的多处理机系统，绝大多数还是采用各CPU具有自己私有Cache的方式与共享主存连接。在这样的系统中，由于Cache的透明性，仅靠采用写直达法并不能保

44、证同一主存单元在各个Cache中的对应内容都一致。第第4 4章章 存储系统存储系统 132 在图4.37所示的系统中，处理机A和处理机B通过各自的 Cache a和 Cache b共享主存。在处理机 A写入Cache a的同时，采用写直达法也写入了主存，如果恰好Cache b中也有此单元，则其内容并未变化，此时若处理机B也访问此单元，就会因读到的是原先的内容而出错。图4.37 共享主存的多处理机系统 第第4 4章章 存储系统存储系统 133 对于共享主存的多处理机系统中，多个Cache与主存内容不一致的问题。解决的方法有三种：播写法。当任何处理机要写入Cache时，不仅写入自己Cache的目标

45、块和主存中，还把信息播写到其他包含此单元的Cache中，或者让其他Cache包含此单元的块作废。控制某些共享信息不得进入Cache。目录表法。在CPU读、写Cache不命中时，先得查主存中的目录表，以判定目标块是否已在别的Cache内，以及是否正在被修改等，然后再决定如何读、写此块。第第4 4章章 存储系统存储系统 134 如果一个 I/O处理机修改了共享主存的内容，它会使某些CPU的 Cache中与之相对的内容与主存内容不一致，解决方法有两种：当 I/O处理机未经 Cache而向主存写入新内容时，由操作系统通过专用指令清除整个 Cache，但这样会使 Cache对操作系统和系统程序员不透明。

46、当 I/O处理机向主存的某个区域写入新内容时，由专用硬件自动地将所有 Cache中对应此区域的副本作废，而无需操作系统进行任何干预，从而保持Cache的透明性。第第4 4章章 存储系统存储系统 1352.Cache的取算法 取算法是指将信息从主存调入Cache的规则，取算法的选择会对Cache的命中率有所影响。Cache一般采用的取算法：按需取进法：在Cache不命中时，才将要访问的单元所在的块（行）调入Cache。预取算法：在用到某信息块之前就将其预取进Cache。预取算法有两种不同的方法：恒预取和不命中时预取。采用预取法能否提高命中率和效率，与以下因素有关：（1）块的大小 （2）预取开销

47、第第4 4章章 存储系统存储系统 136 采用预取技术可以明显提高Cache的命中率Hc。若采用恒预取，采用预取算法后的命中率为其中，Hc为原来的命中率，n为Cache的块大小与数据块重复使用次数的乘积。nnHH1cc 第第4 4章章 存储系统存储系统 137 例4.4 如果Cache的块大小为4个字，预取到Cache中的数据的重复利用率为5次，Cache存储系统原来的命中率为Hc0.8，则采用预取技术后，命中率为多少？若tm5tc，则Cache主存存储系统的访问效率 e 为多少？解：采用预取技术后，命中率为Cache主存存储系统的访问效率 e 为99.0541548.0cH96.005.09

48、9.011mccccactttttHHe 第第4 4章章 存储系统存储系统 138 3.Cache的性能分析 评价 Cache 性能的重要指标是命中率的高低。而 Cache 命中率与块的大小、块的总数、采用组相联时组的大小、取算法、替换策略和地址流情况等有关。（1）Cache的容量、组的大小和块的大小与命中率的关系 块的大小、组的大小及Cache容量这三者增大都会提高命中率。见关系图4.38所示。Cache 容量与不命中率（1Hc）的关系为（1Hc）a(容量)b 式中 a、b 为常数，且b 0。随着存储器芯片集成度的提高、价格下降，Cache的容量正在不断增大。第第4 4章章 存储系统存储系统

49、 139图4.38 块、组的大小及Cache容量对命中率的影响 第第4 4章章 存储系统存储系统 140 （2）“Cache主存”存储层次的等效速度与命中率的关系 设tc为Cache的访问时间，tm为主存的访问时间，Hc为访Cache的命中率，则“Cache主存”存储层次的等效访问时间为由此得系统采用Cache后比CPU直接访问主存在速度上提高的倍数为 在给定主存和Cache的速度之比情况下，随Hc的提高而有所增加。tttHHmccca1HHHtttttttcmcmcccmam)1(11)1(第第4 4章章 存储系统存储系统 141 Hc1时，有maxtm/tc。的期望值与Hc的关系如图4.3

50、9所示。由于Cache的Hc比0.9大得多，故采用Cache结构可使接近于所期望的tm/tc。图4.39 的期望值与Hc的关系 第第4 4章章 存储系统存储系统 142 例4.5 设某计算机的 Cache主存存储层次采用组相联映像，已知主存容量为8 MB，Cache容量为8 KB，按4字块分组，每个字块的长度为8个字（32位/字）。（1）设计主存地址格式和 Cache 地址格式，标出各字段的位数。（2）假设 Cache 起始内容为空，CPU从主存单元0，1，2，2063依次读出2064个字，并重复读此数序列共10次。若 Cache 速度为主存速度的10倍，且采用LRU算法，问采用Cache 后