第七章 存储系统

计算机组成原理课程组,计算机组成与结构本科生课程教学,计算机组成与结构,本课程主要讲授计算机系统的硬件和软件构成方法，包括硬件系统中运算器、控制器、存储器、输入设备和输出设备和总线系统的构成原理等；并与当代先进的计算机技术相结合。是计算机科学与技术本科专业核心课程。本课程着重计算机系统组成与结构方面的教学和研究。计算机结构定义为系统程序员所能见到的计算机硬件特性；计算机组成是指计算机硬件的具体实现。,第七章存储系统,存储系统的层次结构高速缓冲存储器虚拟存储器相联存储器存储保护,7.1存储系统的层次结构,一、存储系统的分类从不同的角度和观点，可将存储系统分为不同的类型。1、按存储介质分磁表面存储器：用磁性材料做成的存储器半导体存储器：用半导体器件组成的存储器光存储器：用感光材料做成的存储器2、按存储方式分随机存储器：任何存储单元的内容都能被随机存取，且存取时间和存储单元的物理位置无关顺序存储器：只能按某种顺序来存取，存取时间和存储单元的物理位置有关,7.1存储系统的层次结构,3、按存储器的读写功能分：ROM，RAM4、按信息的可保存性分：非永久记忆，永久记忆5、按在计算机系统中的作用分：主存、辅存、高速缓存、控制存储器,7.1存储系统的层次结构,二、存储系统层次结构计算机系统对存储器的要求是：容量大、速度快、成本低，但由于各类存储器各具其特点，即半导体存储器速度快、成本较高；磁表面存储器容量大、成本低但速度慢，无法与CPU高速处理信息的能力相匹配。因此，在计算机系统中，通常采用三级存储器结构，即使用高速缓冲存储器、主存储器和外存储器组成的结构。CPU能直接访问的存储器称为内存储器，它包括高速缓冲存储器和主存储器；CPU不能直接访问外存储器，外存储器的信息必须调入内存储器后才能为CPU进行处理。,7.1存储系统的层次结构,Cache主存辅存三级存储层次如图所示。其中Cache容量最小，辅存容量最大，各层次中存放的内容都可以在下一层次中找到。这种多层次结构已成为现代计算机的典型存储结构。,7.1存储系统的层次结构,主辅存层次满足了存储器的大容量和低成本需求。在速度方面，计算机的主存和CPU一直保持了大约一个数量级的差距。显然这个差距限制了CPU速度潜力的发挥。为了弥合这个差距，必须进一步从计算机系统结构上去研究。设置高速缓冲存储器(cache)是解决存取速度的重要方法。在CPU和主存中间设置高速缓冲存储器，构成高速缓存(cache)主存层次。要求cache在速度上能跟得上CPU的要求。,7.1存储系统的层次结构,从CPU的角度看，cache主存层次的速度接近于cache，容量与每位价格则接近于主存。因此，解决了速度与成本之间的矛盾。上述主存辅存和cache主存这两种存储层次。现代大多数计算机同时采用这两种存储层次，构成cache主存辅存三级存储层次，与CPU之间的关系如下图所示。,7.1存储系统的层次结构,7.1存储系统的层次结构,寄存器微处理器内部的存储单元高速缓存（Cache）完全用硬件实现主存储器的速度提高主存储器存放当前运行程序和数据，采用半导体存储器构成辅助存储器磁记录或光记录方式磁盘或光盘形式存放可读可写或只读内容以外设方式连接和访问,虚拟存储器,7.1存储系统的层次结构,其中cache容量最小，辅存容量最大，各层次中存放的内容都可以在下一层次中找到。这种多层次结构已成为现代计算机的典型存储结构。,7.2高速缓冲存储器(Cache),一、Cache存储器工作原理对大量的典型程序的运行情况的分析结果表明，在一个较短的时间间隔内，地址往往集中在存储器逻辑地址空间的很小范围内。程序地址的分布本来就是连续的，再加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问就自然地具有相对集中的倾向。数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问的局部性。,7.2高速缓冲存储器(Cache),根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，当程序运行时，不必从主存储器取指令和取数据，而访问这个高速存储器即可，所以提高了程序运行速度，这个存储器称作高速缓冲存储器(cache)。cache存储器介于CPU和主存之间，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。,7.2高速缓冲存储器(Cache),CPU与cache之间的数据交换以字(字节)为单位Cache与主存间的数据传送以数据块为单位一个块(Block)由若干字组成Cache的基本结构如图7.2所示。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),Cache的数据块称为行（线Line，槽Slot）用Li表示，其中i=0,1,m-1，共有m=2r行主存的数据块称为块（Block）用Bj表示，其中j=0,1,n-1，共有n=2s块行与块是等长的，包含k=2w个主存字字是CPU每次访问存储器时可存取的最小单位Cache由数据存储器和标签存储器组成数据存储器：高速缓存主存数据标签存储器：保存数据所在主存的地址信息,7.2高速缓冲存储器(Cache),设主存有2n个单元，地址码为n位，将主存分块(block)，每块有B个字节，则共分成M2nB块。cache也由同样大小的块组成，由于其容量小，所以块的数目小得多，主存中只有一小部分块的内容可存放在cache中。在cache中，每一块外加有一个标记，指明它是主存的哪一块的副本，所以该标记的内容相当于主存中块的编号，设主存地址为n位，且n=m+b，则可得出：主存的块数M2m，块内字节数B=2b。cache地址码为(c+b)位。cache的块数为2c。块内字节数与主存相同。,7.2高速缓冲存储器(Cache),主存与Cache之间地址关系如下：,7.2高速缓冲存储器(Cache),当CPU发出读请求时，将主存地址m位(或m位中的一部分)与cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况：当比较结果相等时，说明需要的数已在cache中，那么直接访问cache就行了，在CPU与cache之间，通常一次传送一个字；当比较结果不相等时，说明需要的数据尚未调入cache，那么就要把该数据所在的整个字块从主存一次调进来。前一种情况称为访问cache命中，后一种情况称为访问cache不命中。,7.2高速缓冲存储器(Cache),高速命中(Hit)：微处理器读取主存的内容已包含在Cache中，可以直接读取Cache，不用访问主存。高速失效(Miss)、缺失、未命中：微处理器读取主存的内容不在Cache中，需要访问主存读取一个数据块。,Cache的读操作,7.2高速缓冲存储器(Cache),Cache的容量和块的大小是影响Cache的效率的重要因素。通常用“命中率”来测量Cache的效率。命中率（HitRate）：高速命中的概率,Cache/主存系统的平均访问时间ta：ta=htc+(1-h)tmtc命中时的cache访问时间tm未命中时的主存访问时间,h命中率Nccache完成存取的总次数Nm主存完成存取的总次数,7.2高速缓冲存储器(Cache),Cache的访问效率e,设r=tm/tc表示主存慢于Cache的倍率,7.2高速缓冲存储器(Cache),【例】CPU执行一段程序时，Cache完成存取的次数为1900次，主存完成存取的次数为100次，已知Cache存取周期为50ns，主存存取周期为250ns，求Cache/主存系统的效率和平均访问时间。【解】h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3%ta=tc/e=50ns/0.833=60ns或者，ta=htc+(1-h)tm=60ns,7.2高速缓冲存储器(Cache),二、Cache存储器的组织1、地址映像为了把信息放到Cache存储器中，必须应用某种函数把主存地址映像到Cache，称作地址映像。在信息按照这种映像关系装入Cache后，执行程序时，应将主存地址变换成Cache地址，这个变换过程叫做地址变换。,7.2高速缓冲存储器(Cache),Cache通过地址映射(mapping)的方法确定主存块与Cache行之间的对应关系，确定一个主存块应该存放到哪个Cache行中，几种基本地址映像方式如下：全相联映射(fullyassociativemapping)可以将一个主存块存储到任意一个Cache行直接映射(directmapping)将一个主存块存储到唯一的一个Cache行组相联映射(setassociativemapping)可以将一个主存块存储到唯一的一个Cache组中任意一个行,7.2高速缓冲存储器(Cache),1)直接映像在直接映像方式中，映像函数可定为：jimod2c其中，j是Cache的字块号，i是主存的字块号。在这种映像方式中，主存的第0块，第2c块，第2c1块，只能映像到Cache的第0块，而主存的第l块，第2c1块，第2c+11块，只能映像到Cache的第l块。在直接映像方式中，主存和Cache中字块的对应关系如图7.3所示。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),【例】设主存容量1MB，高缓容量16KB，块的大小为512字节。(1)分析Cache地址格式(2)写出主存地址格式(3)计算块表的容量为多大？(4)画出直接方式地址映像及变换示意图(5)主存地址为CDE8FH的单元在cache中的什么位置？【解答】(1)Cache容量16KB，16KB=214，所以Cache地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位。,7.2高速缓冲存储器(Cache),Cache地址格式为：13980块地址块内地址(2)主存容量1MB，1MB=220，所以主存地址为20位；块的大小为512字节，所以块内地址为9位，块地址为5位，块标记为6位。主存地址格式为：191413980块标记块地址块内地址(3)Cache的每一块在块表中有一项，Cache的块地址为5位，所以块表的单元数为25；块表中存放的是块标记，由于块标记为6位，所以块表的字长为6位。故块表的容量为：25字6位。,7.2高速缓冲存储器(Cache),(4)直接方式地址映像及变换示意图如图所示：,7.2高速缓冲存储器(Cache),(5)因为cache容量为16KB=214B，块长为512B，所以cache有161024/512=32个块。因为CDE8FH=1100，1101，1110，1000，1111所以块号=1100，1101，111块内地址=0，1000，1111在直接映射方式下，主存中的第i块映射到cache中第imod25个块中；1100，1101，111mod32=01111；所以，地址CDE8F的单元在cache中的地址为01111，010001111。,7.2高速缓冲存储器(Cache),直接映像的优点是实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在cache存储器中。直接映像方式的缺点是不够灵活，即主存的2t个字块只能对应惟一的cache存储器字块，因此，即使cache存储器别的许多地址空着也不能占用。这使得cache存储空间得不到充分利用，并降低了命中率。,7.2高速缓冲存储器(Cache),2)全相联映像全相联映像方式是最灵活但成本最高的一种方式，如图7.4所示。它允许主存中的每一个字块映像到Cache存储器的任何一个字块位置上，也允许从确实已被占满的Cache存储器中替换出任何一个旧字块。这是一个理想的方案，但实际上由于它的成本太高而不能采用。不只是它的标记位数从mc位增加到m位(与直接映像相比)，使Cache标记容量加大，主要问题是在访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在Cache中。由于Cache速度要求高，所以全部“比较”操作都要用硬件实现，通常由“按内容寻址的”相联存储器完成。所需逻辑电路甚多，以致无法用于Cache中。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),【例】设主存容量1MB，高缓容量16KB，块的大小为512字节。(1)分析Cache地址格式(2)写出主存地址格式(3)计算块表的容量为多大？(4)画出全相联方式地址映像及变换示意图【解】(1)Cache容量16KB，16KB=214，所以Cache地址为14位；块的大小为512字节，所以块内地址为9位，块地址为5位，共32个块。Cache地址格式为：13980块地址块内地址,7.2高速缓冲存储器(Cache),(2)主存容量1MB，1MB=220，所以主存地址为20位；块的大小为512字节，所以块内地址为9位，块地址为11位，共211=2048个块。主存地址格式为：19980块标记块内地址(3)Cache的每一块在块表中有一项，Cache的块地址为5位，所以块表的单元数为25；块表中存放的是块标记，由于块标记为11位，所以块表的字长为11位。故块表的容量为：25字11位。,7.2高速缓冲存储器(Cache),(4)全相联映像方式地址映像及变换示意图如图所示：,7.2高速缓冲存储器(Cache),显然可见：采用全相联映像方式地址映像方法的特点：优点：命中率较高，Cache的存储空间利用率高缺点：线路复杂，成本高，速度低3)组相联映像组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组相联映像cache组织如图75所示。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),它把Cache字块分为2c组，每组包含2r个字块，于是有ccr。那么，主存字块Mm(i)(0i2m1)可以用下列映像函数映像到Cache字块Mc(j)(0j2c1)上。j(imod2c)2rk0k2r1k是为位于上列范围内的可选参数(整数)。按这种映像方式，组间为直接映像，而组内的字块为全相联映像方式。组相联映像把地址划分成3段，低b位为块内地址，中间c位为cache组地址，高t位和r位形成标记字段。,7.2高速缓冲存储器(Cache),【例】一个组相联映象Cache由64个存储块构成，每组包含4个存储块。主存包含4096个存储块，每块由8字组成，每字为32位。存储器按字节编址，访存地址为字地址。(1)Cache地址位数和地址格式。(2)写出主存地址位数和地址格式。(3)画出组相联映像方式的示意图。(4)主存地址18AB9H映射到Cache的哪个字块？【解】(1)Cache由64个存储块构成，每块由8字组成，每字为32位，存储器按字节编址，所以Cache容量=648字4B=211B，所以Cache的地址总数为11位。每组包含4个存储块，所以组内块号为2位；Cache有64/4=16个组，所以组号为4位。,7.2高速缓冲存储器(Cache),Cache地址格式为：109854210组内块号组号块内字地址块内字节地址(2)主存包含4096个存储块，主存容量=40968字4字节=217字节主存字块标记为17-11=6位。主存地址格式为：1611109854210主存字块标记组内块号组号块内字地址块内字节地址,7.2高速缓冲存储器(Cache),(3)组相联映像方式的示意图如图所示。由于访存地址为字地址，所以块内字节地址无用，图中由主存高位地址和组内块号组成标记，分别与由组号选中的组中的四个标记进行比较，比较符合即可访问相应的字块。,7.2高速缓冲存储器(Cache),第,0,块,第,1,块,1,区,组,cache(r=2),0,标记,字块0,标记,字块1,标记,字块2,标记,字块3,第,15,块,1,标记,字块4,标记,字块5,标记,字块,6,标记,字块7,第,16,块,第,17,块,14,标记,字块56,标记,字块57,标记,字块58,标记,字块59,第,31,块,15,标记,字块60,标记,字块61,标记,字块62,标记,字块63,第,4079,块,比,较,第,4080,块,64,区,主存高位地址,组内块号,组号,块内地址,第,4095,块,1611109,854,0,组相联映像方式的示意图,7.2高速缓冲存储器(Cache),(4)主存地址18AB9H=11000101010111001方法1：组号为0101，所以主存地址18AB9H可以映射到Cache的第5组中的字块21、字块22、字块23或字块24。方法2：块内地址位11001；块号位i=110001010101；设Cache的块号为j，因为j=(imod24)22k0k221所以j=(110001010101mod24)22k=010122k=54k所以主存地址18AB9H可以映射到Cache的第5组中的字块21、字块22、字块23或字块24。,7.2高速缓冲存储器(Cache),在实际Cache中用得最多的是直接映像(r0)，两路组相联映像(r1)和4路组相联映像(r2)。如r2，则0k3，所以主存某一字块可映像到Cache某组4个字块的任一字块中，这大大地增加了映像的灵活性，提高了命中率。组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r0时，它就成为直接映像方式；当rc时，就是全相联映像方式。Cache的命中率除了与地址映像的方式有关外，还与Cache的容量有关。Cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。,7.2高速缓冲存储器(Cache),2、替换算法当新的主存字块需要调入Cache存储器而它的可用位置又已被占满；辅存的页需要调入主存而主存的页已被占满时，就产生替换问题。替换问题新主存块要进入Cache，决定替换哪个原主存块直接映射，只能替换唯一的一个Cache行全相联和组相联，需要选择替换策略（算法）,7.2高速缓冲存储器(Cache),常用的替换算法有：先进先出(FIFO)算法和近期最少使用(LRU)算法。FIFO算法总是把一组中最先调入的块或页替换出去，它不需要随时记录各个字块或页的使用情况，所以实现容易、开销小。LRU算法是把一组中近期最少使用的字块或页替换出去。这种替换算法需随时记录Cache存储器中各个字块或主存中的各页的使用情况，以便确定那个字块是近期最少使用的字块。LRU替换算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。,7.2高速缓冲存储器(Cache),随机替换法(RAND)，这种算法不考虑使用情况，在组内随机选择一块来替换。其性能比根据使用情况的替换算法要差些。最不常用(LFU:least-frequentlyused)替换使用次数最少的块。,7.2高速缓冲存储器(Cache),LRU是最常使用的一种算法。其设计思想是把组中各块的使用情况记录在一张表上(如图76所示)。,7.2高速缓冲存储器(Cache),Cache写入策略处理器对Cache读占大多数，也容易提高速度写入Cache有些问题：确认命中，才可以对Cache块写入写入的数据字数不定写入后可能导致与主存内容不一致写入策略解决主存内容的更新问题，保持正确直写法(writethrough)全写法写入Cache的同时也写入主存（下一级存储器）回写法(writeback)写回法只写入Cache，在被替换时才写回主存,7.2高速缓冲存储器(Cache),直写和回写的比较直写策略优点：简单可靠缺点：总线操作频繁、影响工作速度解决方法：在Cache与主存间设置一级/多级缓冲器，形成实用的“缓冲直写”方式，提高速度回写策略优点：可以减少写入主存次数、提高速度缺点：硬件结构比较复杂实现方法：为了表明Cache是否被修改，需要设置一个更新位（update，污染位dirtybit）。替换时只需将被修改的Cache块内容写入主存,7.2高速缓冲存储器(Cache),写未命中的处理方法写访问并不需要Cache块中所有数据。写未命中时，写入的数据是否还要将其读回Cache呢？写分配法(writeallocate，WTWA)先把数据所在的块调入Cache，然后再进行写入。类似读失效的方式，也称fetchonwrite不写分配法(no-writeallocate，WTNWA)直接把数据写入下一级存储器，不将相应的块调入Cache，也称writearound直写策略通常配合不写分配法，回写策略一般采用写分配法,7.2高速缓冲存储器(Cache),三、Cache存储器举例【例1】以Intel82385cache控制器为例来作进一步说明。与80386微处理器相匹配的主存一cache存储系统是由82385cache控制器来实现地址映像和变换的。可全部映像80386的32位地址提供的4G(千兆)字节的地址空间，使CPU几乎无任何等待地读出数据，命中率可高达99。,7.2高速缓冲存储器(Cache),82385片内只含有cache控制器，cache数据保存在片外的SRAM中。82385提供了两种地址映像方式：直接映像和两路组相联映像。当采用直接映像方式时，80386的地址总线分配如图7.7所示。它分成三部分：17位标记字段A31A15(相当于图7.3中的t)，10位组地址字段A14A5(相当于图73中的c)和3位行选择位A4A2(相当于图7.3中的b位，但80386一次访存只能取出一个字)。A1，A0为字节地址，在这里以字作为最小存储单元，所以A1A0无用，在图上未标出。,7.2高速缓冲存储器(Cache),直接映像cache组织如图7.8所示。Intel80386的4GB地址空间被分成217页，页的大小为8K字(每字32位)，正好和cache的容量相同。cache被分成1024组，每组8个字(8X32位)。每个字被称作一“行”，行是主存和cache之间的信息传输单位。在82385cache目录表中，对应cache的每一组有一个条目。每一条目有26位，分成三部分：17位标记，1位标记有效位，8位行有效位。17位标记指出主存的页号，它是217页中的某一页。所谓直接映像，是指主存各页中的第0组只能驻留在cache的第0组，第1组只能驻留在cache的第1组，第1023组驻留在cache的第1023组中。由于每组包含着8行，在目录表中有8个行有效位与其对应，如果某一行被调入cache中，则此行有效位被置“1”，同时置标记有效位。例如，若主存第二页中的第9行正驻留在cache中，则第一组的对应表目中的标记位将记作2。由于第0组包含第07行，第一组包含第815行，。所以，第一组对应表目中第2个行有效位被置“1”，以此指出第9行驻留，在cache中。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),在80386启动读周期时，82385用10位地址选择目录表中1024个表目中的一条，用3位选择表目中8个行有效位的一位。这13位cache地址选择cache中的一行(4字节)。82385将地址总线的标记字段(A31A5)与目录表表目中的标记相比较，若相等，并且目录中的标记有效位和行有效位皆为“1”状态，说明读命中。82385指示cache将选中的字送入80386数据总线。读命中不改变cache和目录中的内容。,7.2高速缓冲存储器(Cache),读失效分为两种情况。一种情况叫做行失效。这时，目录表目中标记和地址总线的标记字段相等，且标记有效位为“1”，但是行有效位为“0”。另一种情况叫做标记失效。这时，目录表目中标记和地址总线标记宇段不相等，或是标记有效位为“0”。在失效发生时，80386将直接访问主存取得数据，并同时写入cache。若为行失效，则只将该行对应的行有效位置“1”；若为标记失效，则用上述地址页号修改标记，并将标记有效位和相应的行有效位置“1”，清除其他7个行有效位。,7.2高速缓冲存储器(Cache),在两路组相联映像方式下，80386地址总线分配和cache组织分别如图79和图710所示。地址A31A14相当于图75中的t+r位。在这种方式中，cache被分成两个体(A和B)，每体为4K字。主存页面大小和cache的一个体的大小相同，而页数比直接映像方式增加一倍，为218页。对应着cache的两个体，目录表也分为两部分(A和B)，每个部分有27位，18位标记为主存页号，1位标记有效位，8位行有效位。此外，在目录表中还有一个附加位，称为LRU位。由于在组相联映像方式下，其置换算法为最近最少使用法，LRU位指定cache两个体中同一组的那一行为最近最少使用行，也就是置换的对象。在两路组相联映像方式中，主存储器各页的同一组可以任意映射到cache的两个体的同一组中，同时可有两个页的同一组存于cache中。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),Intel82385还有监听功能，其作用解释如下：现代计算机以存储器为中心，除了CPU访存以外，输入输出(IO)设备也可直接访问存储器，而cache中的数据又要与主存储器相应单元的内容保持一致(相同)，因此需要对地址进行监听。假如某一IO设备直接向存储器传送数据(写入存储器)，而且其提供的地址中的数据在cache中有副本(即该地址与cache中相应单元的标记相符，且标记的有效位为“1”)，此时如不进行处理，会造成cache数据与存储器数据的不一致性。为简化操作，通常采取将cache相应单元的标记有效位清“0”的办法，这样当CPU再访问(读)该单元时，将产生不命中信号，而到存储器去取数，这样可保证CPU所取数据的正确性。图711是引入cache后的计算机框图，CPU与cache之间通过内部高速总线传送地址、数据和控制信号，CPU通过cache与系统总线联系。当系统中存在多个CPU时，监听功能更显得必要。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),【例2】80486的片上Cache指令和数据共用的4路组相联Cache结构8KB容量分成128组，每组有4路，每组每路为一行，每行16个字节（128位）每行对应21位标签，一个有效位每组中4路对应3位LRU位，用于实现伪LRU替换算法采用4级缓冲直写策略，允许6个连续的写操作而无等待写命未中时，采用不写分配法，只将数据写入主存，不进行Cache的回填,7.2高速缓冲存储器(Cache),80486片上Cache的结构,7.2高速缓冲存储器(Cache),80486片上Cache的伪LRU算法,7.2高速缓冲存储器(Cache),【例3】Pentium的片上Cache指令和数据分离的2路组相联Cache结构指令Cache和数据Cache都是8KB，共16KB8KB容量分成128组，每组2路，每行32个字节LRU算法，回写策略(可动态改变为直写策略),7.2高速缓冲存储器(Cache),四、多层次Cache和Cache的一致性1）指令cache和数据cache计算机开始实现cache时，是将指令和数据存放在同一cache中的。后来随着计算机技术的发展和处理速度的加快，存取数据的操作经常会与取指令的操作发生冲突，从而延迟了指令的读取。发展的趋势是将指令cache和数据cache分开而成为两个相互独立的cache。,7.2高速缓冲存储器(Cache),在给定cache总容量的情况下，单一cache可以有较高的利用率。因为在执行不同程序时，cache中指令和数据所占的比例是不同的，在单一cache中，指令和数据的空间可以自动调剂，而分开的指令cache和数据cache则不具有这一优点。但在超标量等新型计算机结构中，为了照顾速度，还是采用将指令cache和数据cache分开的方案。2）多层次cache结构当芯片集成度提高后，可以将更多的电路集成在一个微处理器芯片中，于是近年来新设计的快速微处理芯片都将cache集成在片内，片内cache的读取速度要比片外cache快得多。,7.2高速缓冲存储器(Cache),Pentium微处理器的逻辑结构如图649所示，片内包含有8KB数据cache和8KB指令cache。cache行的长度为32B，采取两路组相联组织。数据cache有两个端口，分别与两个ALU交换数据，每个端口传送32位数据，也可组合成64位数据，与浮点部件接口相连，传送浮点数。数据cache采取“写回”策略，即仅当cache中的数据要调出，且被修改过，才需要写回主存。,7.2高速缓冲存储器(Cache),7.2高速缓冲存储器(Cache),指令cache只读不写，其控制比数据cache简单。片内cache的容量受芯片集成度的限制，一般在几十KB以内，因此命中率比大容量cache低。于是推出了二级cache方案：其中第一级cache(L1)在处理器芯片内部；第二级cache(L2)在片外，其容量可从几十KB到几百KB，采用SRAM存储器，两级cache之间一般有专用总线相连。Pentium微处理器支持片外的第二级cache，其容量为256KB或512KB。也是采用两路组相连方案。,7.2高速缓冲存储器(Cache),3）cache的一致性问题由于数据cache有写入操作，且有多种写入方案，为了提高计算机处理速度，在每次写入时，并不同时修改L1，L2和主存储器的内容，造成了数据的不一致，这就是要解决的cache一致性问题。程序是不允许修改的，因此使用指令cache不存在cache一致性问题。,7.2高速缓冲存储器(Cache),实现Cache一致性的基本方案软件方法：由编译程序和操作系统在编译时分析代码，避免共享变量进入Cache硬件方法：程序运行时动态处理，对程序员和编译员透明，称为Cache一致性协议(Cachecoherenceprotocol)目录(directory)：物理主存中共享数据的状态及相关信息保存在目录中，通常由中央控制器集中维护监听(snoopy)：各个Cache除保存数据拷贝外，也保存数据的共享状态信息，通过监听总线操作判断,7.2高速缓冲存储器(Cache),MESI协议商业化多处理器系统中，Cache块常利用标签中额外的2位记录其数据共享的4种状态：修改(modified)、唯一(exclusive)、共享(shared)和无效(invalid)；所以也称为MESI协议修改M：该Cache块已经被修改（与主存不同），而且只在这个Cache中可用唯一E：该Cache块与对应主存块相同，而且不存在于其它Cache中共享S：该Cache块与对应主存块相同，但可能存在于其它Cache中无效I：该Cache块包含的数据无效,7.2高速缓冲存储器(Cache),Pentium的L1和L2级Cache数据一致性Pentium采用MESI协议，配合第一次直写(writethrough)，以后回写(writeback)，实现L1和L2Cache的数据一致，也称为一次写(writeonce),7.2高速缓冲存储器(Cache),Pentium处理器支持“修改唯一共享无效”(modifiedexclusivesharedinvalid，简称MESI)协议。它原是为多处理器系统的cache一致性设计的，但也适用于单处理机的二级cache系统。数据cache的每一行包含两个状态位，每一cache行处于4种状态之一，各状态的意义如下：(1)修改(Modified，简称M)本cache行中的数据已被修改(与主存的内容不同)，仅在本cache中的数据是正确的。(2)唯一(Exclusive，简称E)本cache行中的数据与主存中的数据相同，但不存在于其他cache中。(3)共享(Shared，简称S)本cache行中的数据与主存中的数据相同，且可存在于其他cache中。(4)无效(Invalid，简称I)本cache行中的数据无效。,7.2高速缓冲存储器(Cache),当处理器加电或总清(reset)时，所有cache行都处于无效状态。当新数据写入无效行时，数据从主存取出，并同时存人L1和L2，此时cache行处于共享状态。写入操作的一般过程描述如下：当处理器发出写入数据到存储器的命令时，首先查询cache是否命中，如命中，则根据cache行的状态进行相应的写入数据操作，并修改(或保留)原状态位。L1和L2都设置有4种状态位，但处理方法不完全相同，情况比较复杂。,7.3虚拟存储器,一、虚拟存储的基本概念虚拟存储技术是为了扩大主存的寻址空间而采用的。虚拟存储器是建立在主存与辅存物理结构基础之上，由附加硬件装置以及操作系统存储管理软件组成的一种存储体系。它把主存和辅存的地址空间统一编址，形成一个庞大的存储空间，在这个大空间里，用户可自由编程，完全不必考虑程序在主存中是否装得下，或者放在辅存的程序将来在主存中的实际位置，编好的程序由计算机操作系统装入辅助存储器中，程序运行时，附加的辅助硬件机构和存储管理软件会把辅存的程序一块块自动调入主存由CPU执行或从主存调出，用户感觉到的不再是处处受主存容量限制的存储系统，而是一个容量充分大的存储器。因为实质上CPU仍只能执行调入主存的程序，所以这样的存储体系称为“虚拟存储器”。,7.3虚拟存储器,虚地址和实地址虚拟存储器的辅存部分也能让用户像内存一样使用，用户编程时指令地址允许涉及到辅存的空间范围，这种指令地址称为“虚地址”(即虚拟地址)，或叫“逻辑地址”，虚地址对应的存储空间称为“虚拟空间”，或叫“逻辑空间”。实际的主存储器单元的地址则称为“实地址”(即主存地址)，或叫“物理地址”，实地址对应的是“主存空间”，也称物理空间。显然，虚地址范围要比实地址大得多。,7.3虚拟存储器,主存辅存层次与主存Cache层次的比较虚拟存储器和主存Cache存储器是两个不同存储层次的存储体系。但在概念上有不少相同之处：它们都把程序划分为一个个信息块，运行时都能自动地把信息块从慢速存储器向快速存储器调度，信息块的调度都采用一定的替换策略，新的信息块将淘汰最不活跃的旧的信息块，以提高继续运行时的命中率，新调入的信息块需遵守一定的映射关系变换地址后来确定其在存储器的位置。,7.3虚拟存储器,两个存储体系均以信息块作为存储层次之间基本信息的传递单位，主存Cache存储器每次传递是定长的的信息块，长度只有几十字节，而虚拟存储器信息块划分方案很多，有页、段等等，长度均在几百字节至几百千字节左右。由主存与辅存组成的虚拟存储器和主存Cache存储器也有很多不同之处。主存Cache存储器采用与CPU速度匹配的快速存储元件来弥补主存和CPU之间的速度差距，而虚拟存储器虽然最大限度地减少了慢速辅存对CPU的影响，但它却弥补了主存的容量不足，具有容量大和程序编址方便的优点。,7.3虚拟存储器,CPU访问快速Cache存储器的速度比访问慢速主存快510倍。虚拟存储器中主存的速度要比辅存快1001000倍以上。主存Cache存储体系中CPU与Cache和主存都建立了直接访问的通路，一旦在Cache中命中，CPU就直接访问Cache，并同时向Cache调度信息块，从而减少了CPU等待的时间，辅助存储器与CPU之间没有直接通路，一旦在主存中不命中，则只能从辅存调度信息块到主存，因为辅存的速度与CPU的速度差距太大，调度需要毫秒级时间，因此，CPU一般将改换执行另一个程序，等到调度完成后再返回原程序继续工作。,7.3虚拟存储器,主存Cache存储器存取信息的过程、地址变换和替换策略全部用硬件实现，所以对各类程序员均是透明的。主辅层次的虚拟存储器基本上由操作系统的存储管理软件辅助一些硬件进行信息块的划分和主辅存之间的调度，所以对设计存储管理软件的系统程序员来说，它是不透明的，而对于广大用户，因为虚拟存储器提供了庞大的逻辑空间可以任意使用，对应用程序员来说是透明的。,7.3虚拟存储器,主存-外存层次的基本信息传送单位段：按程序逻辑划分为可变长的块，称为段页：机械地划分为大小相同的块，称为页面段页：程序按模块分段，段内分页虚拟存储器的管理段式管理：把主存按段分配的存储管理方式优点：段的界线分明，段易于编译、管理、修改和保护，便于多道程序共享缺点：段的长度各不相同，主存空间分配麻烦,7.3虚拟存储器,页式管理：以定长页面进行存储管理的方式优点：页的起点和终点地址固定,方便造页表,新页调入主存也很容易掌握，比段式空间浪费小缺点：处理、保护和共享都不及段式来得方便段页式管理：分段和分页相结合的存储管理方式优点：综合段式和页式管理方式的特点缺点：需要多次查表过程,7.3虚拟存储器,二、段式虚拟存储器段是利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立的部分。例如，过程、子程序、数据表、阵列等。段作为独立的逻辑单位可以被其他程序段调用，这样就形成段间连接，产生规模较大的程序。段式虚拟存储器一般用段表来指明各段在主存中的位置，如下图所示。,7.3虚拟存储器,7.3虚拟存储器,段式管理的地址变换：用段表,7.3虚拟存储器,把主存按段分配的存储管理方式称为段式管理。段式管理系统的优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。,7.3虚拟存储器,三、页式虚拟存储器页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，称为页面。新页调入主存也很容易掌握，只要有空白页面就可。可能造成浪费的是程序最后一页的零头，是不能利用的页内空间，它比段式管理系统的空间浪费要小得多。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。,7.3虚拟存储器,在页式虚拟存储系统中，把虚拟空间分成页，主存空间也分成同样大小的页，称为实页或物理页，而把前者称为虚页或逻辑页。假设虚页号为0，1，2，m，实页号为0，l，l，显然有ml。可把虚拟地址分为两个字段，高位字段为虚页号，低位字段为页内字地址。虚拟地址到主存实地址的变换是由页表来实现的。在页表中，对应每一个虚存页号有一个表目，表目内容至少要包含该虚页所在的主存页面号，用它作为主存地址的高字段；与虚拟地址的页内地址字段相拼接，就产生完整的实主存地址，据此访问主存。,7.3虚拟存储器,逻辑页：页式虚拟存储系统中，虚拟空间分成页；物理页：主存空间也分成同样大小的页。虚存地址分为两个字段：高字段为逻辑页号，低字段为页内行地址。实存地址也分两个字段：高字段为物理页号，低字段为页内行地址。,7.3虚拟存储器,页式管理的地址变换如图所示。,7.3虚拟存储器,通常，在页表的表项中还包括装入位(有效位)、修改位、替换控制位及其他保护位等组成的控制字。如装入位为“1”，表示该虚页已从辅存调入主存；如装入位为“0”，则表示对应的虚页尚未调入主存，如访问该页就要产生页面失效中断，启动输入输出子系统，根据外页表项目中查得的辅存地址，由磁盘等辅存中读出新的页到主存中来。修改位指出主存页面中的内容是否被修改过，替换时是否要写回辅存。替换控制位指出需替换的页等。假设页表是保存在(或已调入)主存储器中，那么，在访问存储器时，首先要查页表，即使页面命中，也得先访问一次主存去查页表，再访问主存才能取得数据，这就相当于主存速度降低了一倍。如果页面失效，要进行页面替换，页面修改，访问主存次数就更多了。,7.3虚拟存储器,因此，把页表的最活动部分存放在快速存储器中组成快表，这是减少时间开销的一种方法。此外，在一些影响工作速度的关键部分引入了硬件支持。例如，采用按内容查找的相联存储器并行查找，也是可供选择的技术途径。一种经快表与慢表实现内部地址变换的方式如图715所示。,7.3虚拟存储器,7.3虚拟存储器,快表由硬件组成，通常称为转换旁路缓冲器(translationlookasidebuffer，简称TLB)。它比页表小得多，一般在16行64行之间，快表只是慢表(指主存中的页表)的小小的副本。查表时，由虚页号同时去查快表和慢表，当在快表中有此虚页号时，就能很快地找到对应的实页号送入实主存地址寄存器。并使慢表的查找作废，从而就能做到虽采用虚拟存储器但访主存速度几乎没有下降。如果在快表中查不到时，那就要费一个访主存时间查慢表，从中查到实页号送人实主存地址寄存器，并将此虚页号和对应的实页号送入快表，替换快表中某一行内容，这也要用到替换算法。,7.3虚拟存储器,快表与慢表,7.3虚拟存储器,【例3】设主存容量64KB，虚存容量1MB，页面大小为512B。(1)写出主存地址格式(2)写出虚拟地址格式(3)页表的长度为多少？(4)画出虚实地址转换示意图【相关知识】虚拟存储器的地址格式和虚实地址转换过程。,7.3虚拟存储器,【例题解答】(1)主存容量64KB，64KB=216，所以主存地址为16位。主存地址格式为：15980物理页号(7位)页内地址(9位)(2)虚存容量1MB，1MB=220，所以虚存地址为20位。虚拟地址格式为：19980虚页面号(11位)页内地址(9位),7.3虚拟存储器,(3)每一个虚页面号在页表中有一项，所以页表的长度为211=2048(4)虚实地址转换示意图如图所示：,7.3虚拟存储器,7.3虚拟存储器,四、段页式虚拟存储器在段页式虚拟存储器中，把程序按逻辑结构分段以后，再把每段分成固定大小的页。程序对主存的调入调出是按页面进行的，但它又可以按段实现共享和保护。因此，它可以兼取页式和段式系统的优点。它的缺点是在地址映像过程中需要多次查表，在这种系统中，虚拟地址转换成物理地址是通过一个段表和一组页表来进行定位的。段表中的每个表目对应一个段，每个表目有一个指向该段的页表的起始地址(页号)及该段的控制保护信息。由页表指明该段各页在主存中的位置以及是否已装入、已修改等标志。,7.3虚拟存储器,如果有多个用户在机器上运行，称为多道程序，多道程序的每一道(每个用户)需要一个基号(用户标志号)，可由它指明该道程序的段表起点(存放在基址寄存器中)。这样，虚拟地址应包括基号D、段号S、页号P、页内地址d。格式如下：,7.3虚拟存储器,现举例说明段页式地址变换过程。假设实主存分成32个页面，有A，B，C三道程序已经占用主存，如图716(a)中阴影(斜线)部分所示。现在又有D道程序要进入，它有三段(图716(b)，段内页号分别为0，1；0，1；0，1，2。如采用纯段式管理，虽然主存空间总计空余相当于8个页面，比D道程序所需空间(相当于7个页面)要大，但因第二段所需空间相当于3个页面，比任何空隙都大而无法进入。