第讲(存储系统)

1、计 算 机 组 成 原 理第二十四、二十六讲2022年10月13日存储系统1、 存储器层次概述存储器层次结构及其工作原理，CACHE和虚拟存储器的性能2、CACHE结构设计直接、全相联、组相联，地址映象，地址变换3、CACHE的替换策略RAND、FIFO、LRU4、CACHE的写策略写透，写回5、虚拟存储器及其管理 分段管理，分页管理，段页式管理，多级页表，TLB本讲安排本讲将解决的主要问题 Cache和虚拟存储器的构成原理以及工作原理。1存储容量：（1）存储容量是指一个功能完备的存储器所能容纳的二进制信息总量，即可存储多少位二进制信息代码。（2）存储容量存储字数字长（3）要求：大容量。存储器

2、性能指标2价格： 又称成本，它是衡量经济性能的重要指标。设是存储容量为位的整个存储器以元计算的价格，可定义存储器成本为： c（）元位3速度: （1）存取时间：从读或写存储器开始接到存储器发出完成信号的时间间隔（2）存取周期：连续两次访问存储器之间所必需的最短时间（3）数据传输率：单位时间可写入存储器或从存储器取出的信息的最大数量，称为数据传输率或称为存储器传输带宽BM 。BM =WtM 其中，存储周期的倒数tM 是单位时间（每秒）内能读写存储器的最大次数。W表示存储器一次读取数据的宽度，即位数，也就是存储器传送数据的宽度。衡量存储器性能还有一些其它性能指标，如体积、功耗、重量、使用环境等。4可

3、靠性：存储器的可靠行是指在规定时间内存储器无故障的情况，一般用平均无故障时间MTBF来衡量。为提高存储器的可靠性，必须对存储器中存在的特殊问题，采取适当的方法。实际：速度、容量、价格存在巨大的矛盾希望：高速度、大容量、低价格1、存储器层次概述 存储体系：把各种不同存储容量、不同存取速度、不同价格的存储器，组成层次结构，并通过管理软件和辅助硬件将不同性能的存储器组合成有机的整体，称为计算机的存储层次或存储体系。概念：存储器系统的层次结构存储器系统的层次结构如下图所示：CPU内的寄存器高速缓存主存储器磁盘存储器磁带机层1：M1层2：M2层4：M4容量和存取时间增加每位成本增加较低级：与处理器较远的

4、存储级 -容量较大、速度较慢、使用较廉价的技术工艺存储器系统的层次结构的特点：在任何指定时间，数据只能在相邻的两级之间拷贝：较高级：与处理器较近的存储级 - 容量较小、速度较快、使用较昂贵的技术工艺程序访问的局部性原理CPU访问存储器时，无论是取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。(程序循环、堆栈)空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。(指令顺序执行、数组存放)这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问

5、的局部性原理。 程序地址的分布是连续的，加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问具有相对集中的倾向。 程序访问的局部性主要表现： 数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。其它原因：优先考虑最近经常被访问的代码最近可能被访问的数据放在小的但高速存储器里容量小、离CPU近的高速存储器存放最近要访问的数据。在高速机器中，信号传输是延迟的一个重要原因。而大的存储器因地址译码级数多，信号延迟会更大。相同器件条件下，小容量存储器比大容量存储器快。存储器层次结构特点：1.包含性 M0 M1 M2 Mn 2. 相邻层之间的数据

6、传送单位CPU高速缓存：字高速缓存主存储器：块（每块32个字节（8个字）主存磁盘：页面（比如每页4K字节，包含128块）磁盘磁带：段所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2， 如果在Mi中找到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，Mn中都一定可以找到。M1:高速缓存a,b为高速缓存块，32个字节M2:主存储器M3:磁盘存储器M4:磁带机后援存储器CPU寄存器ba页面Aa页面Bb页面Aa页面Bb段F段G页面Aa页面Bb段F段G字单位块单位页单位段单位命中：在Mi中找到一个信息项时，称之为命中，反之称为失效

7、。命中率：在Mi层的命中率hi则是信息项可在Mi中找到的概率。失效率：在Mi中的失效率定义为1-hi。 相继层的命中率是存储器容量、管理策略和程序行为的函数，它是独立的随机变量，其值在0到1之间。我们假设h0=0和hn=1，这意味着CPU总是先访问M1，并且访问到最外层Mn时总是命中的。对Mi的访问频率为：是指在较低层次有i-1次失效而在Mi有一次命中时访问Mi成功的概率。通常情况下，这说明，访问内存比访问外存要多。存储器层次结构的性能每当发生失效时，就要付出代价去访问较高层次的存储器。这种失效在Cache中称为块失效。在主存储器中称为缺页错（page fault），因为块和页面是这些层次之间

8、传送信息的单位。缺页错付出的时间代价要比块缺失付出的更大。 存储器层次结构的性能是由层次结构的有效存取时间Teff决定的，它依赖于相继层次的命中率和访问频率。有效存取时间层次结构设计的目标： 使Teff接近于M1的t1， 总成本接近于Mn的Cn。Cache基本原理Cache存储器Cache存储器组织 替换策略 写操作策略 80386的Cache奔腾PC机的Cache 根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不必从主存储器取指令和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓

9、冲存储器Cache。 Cache由高速的SRAM组成，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。cache基本原理cache的基本结构它由cache存储体、地址映象变换机构、cache替换机构几大模块组成。Cache概念： （1）CPU与主存储器之间的一种高速缓冲装置 （2）Cache-主存层次结构：由硬件变换地址和控制调度。Cache具有如下特点： 位于CPU与主存之间，是存储器层次结构中级别最高的一级； 容量比主存小，目前一般有数到数； 速度一般比主存快倍,通常由存储速度高的双极型三极管或SRAM组成； 其内容是主存的部分副本； 其用途可用来存放指令，也可用来存放数

10、据； 快存的功能全部由硬件实现，并对程序员透明。(2)当比较结果不相等时，说明需要的数据尚未调入Cache，那 么就要把该数据所在的整个字块从主存一次调进来。 前一种情况称为访问Cache命中，后一种情况称为访问Cache不命中。cache的命中 任何时候都有一些主存块处在Cache中。 当CPU发出读请求时，将主存地址s位（或s位中的一部分）与Cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况： (1)当比较结果相等时，说明需要的数据已在Cache中，那么直接访问Cache就行了，在CPU与Cache之间，通常一次传送一个字；cache的命中率 命中率指CPU所要访问的信息在

11、Cache中的比率； 而将所要访问的信息不在Cache中的比率称为失效率。 增加cache的目的，就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此, cache的命中率应接近于1。 由于程序访问的局部性 ，这是可能的。 在一个程序执行期间： 设Nc表示cache完成存取的总次数， Nm表示主存完成存取的总次数， h定义为命中率，则有：若 tc表示命中时的cache访问时间， tm表示未命中时的主存访问时间， 1-h表示不命中率，则cache/主存系统的平均访问时间ta为：ta=htc+(1-h)tm我们追求的目标是： 以较小的硬件代价使cache/主存系统的平均访问时间ta

12、越接近tc越好。设 r=tm/tc表示主存慢于cache的倍率, e表示访问效率，则有: 为提高访问效率： 命中率h越接近1越好，r值以510为宜，不宜太大。 命中率h与程序的行为、cache的容量、组织方式、块的大小有关。例：CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。解： h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=

13、83.3% ta=tc/e=50ns/0.833=60ns例:已知Cache存储周期为40ns,主存存储周期为200ns, Cache /主存系统平均访问时间为50ns,求Cache的命中率是多少?解: 因为 ta=htc+(1-h)tm 所以 h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16 （1）数据块在Cache中存放在哪个位置？即定位问题（地址映象） 。如果一个块存放在某一Cache中，怎样确定并找到该块，即寻址问题（地址变换）。（2）不命中时将从主存储器中访问，并将该块调入Cache中，但是如果Cache中已无空闲空间，则势必将Cache中的某一块调

14、出，但应调出那一块，即替换问题。（3）在写访问时，写入Cache必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性。写操作失配时是否将访问块取入高层存储器。Cache结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？ 地址映象 把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。 地址变换 信息按这种映象关系装入Cache后，执行程序时，将主存地址变换成 Cache地址的变换过程叫做地址变换。 地址映象和变换密切相关。 使用Cache的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的。这带来

15、的另一好处是Cache的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到Cache的存在。1.地址映象(映射)与地址变换基本的地址映象方式：直接映象； 全相连映象；组相连映象 在高速缓冲存储器中,把Cache和主存机械等分为相同大小的块,每一块是由若干个字(或字节)组成. 块0块1块15Cache标记标记标记块0块1块2047主存m位 块字0字1字511 由于Cache的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的哪一块的副本(拷贝)。例：某机主存容量为1MB,划分为2048块,每块51

16、2B;Cache容量为8KB,划分为16块,每块512B。 因刚加电时所有标记位都为“0”，开始执行程序时，命中率较低。另外Cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。标记的有效位 每个标记设置有一个有效位。机器加电启动时，Reset信号将所有标记的有效位置“0”，即无效。程序执行过程中，Cache不命中时，逐步将指令块或数据块从主存调入Cache中的某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或数据时，可直接从Cache中取指令或数据。字块0字块1字块Lm-1.标记Cache012r-1 标记有效位1）直接映射方式 这是一种多对一的映射关系，但一个

17、主存块只能映象到Cache的一个特定块位置上去。 Cache的第i块和主存的第j块有如下函数关系： i = j mod m ( m为Cache的总块数） i =0,1,2,m-1 j=0,1,2,n-1在这种映象方式中：主存的第0块，第16块，第32块，只能映象到Cache的第0块；而主存的第1块，第17块，第33块，只能映象到Cache的第1块；直接映象Cache地址4位 9 位主存地址7位 4位 9 位11位 9 位主存地址7位优点:硬件简单,成本低 缺点:块冲突率很高直接映象的地址变换方法优点: 实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在Cache中。 缺点：

18、 不够灵活，主存的多个字块只能对应唯一的Cache字块，因此，即使Cache别的地址空着也不能占用。Cache存储空间得不到充分利用，降低了命中率。例：设有一个cache的容量为2K字，每个块为16字，求(1) 该cache可容纳多少个块？(2) 如果主存的容量是256K字，则有多少个块？(3) 主存的地址有多少位？cache地址有多少位？(4) 在直接映象方式下，主存中的第i块映象到cache中哪一个块中？(5) 进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？解：(1) cache中有2048/16=128个块。(2) 主存有256K/16=16384个块。(3) cache容量

19、为2K=211字，所以cache字地址为11位。(4) 主存中的第i块映象到cache中第 i mod 128个块中。(5) 存储器的字地址分成三段：区号、块号、块内字地址。 区号的长度为18-11=7位，块号为7位。块内字地址为4位。块0块1块15Cache标记标记标记标记标记标记.块0块1块15块16块17块31块2047主存Tag2）全相联映象方式Cache地址4位 9 位11位 9 位主存地址11位允许主存中的每一个字块映象到Cache的任何一个字块位置上 最灵活但成本最高的一种方式。全相联映象的地址变换方法这只是一个理想的方案。两个原因使其实际上很少采用：(1) 标记位数从7位增加到

20、11位，使Cache标记容量加大， (2) 访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在Cache中。由于Cache速度要求高，通常由“按内容寻址”的相联存储器完成，所需硬件逻辑电路很多，以至于无法用于cache中。实际的Cache组织则是采取各种措施来减少所需比较的地址数目。优点：灵活，块冲突概率小。只有当Cache中全部装满后,才有可能出现块冲突；缺点：要作相联搜索，速度慢，代价高。1、组间全相联，组内直接映像8位 3位 9 位8位1位 3位 9 位注意：当只有一个组并且每组16块时，此时为直接映像； 当有16组并且每组一个块时,则为全相联映

21、像。3）组相联映射方式直接映象和全相联映象方式的一种折衷方案。0组 1组 内存组相联的地址变换方法直接映象是：1路组相联全相联是： m路组相联N个直接映射cache并行工作。直接映象和全相联映象是组相联的特例：主存中的一块能对应到Cache中一个特定组中的任意一行上。若组中有n个块，则称其为 n路组关联。另外一种组相联映射方式 Cache与主存均分组,主存中一个组内的块数与Cache 的分组数相同,主存中的各块与Cache的组号有固定的映象关系,但可自由映象到对应的Cache组中任一块.2、组内全相联，组间直接映像注意：当只有一个组并且每组16块时，此时为全相联映像； 当有16组并且每组一个块

22、时,则为直接映像。 把Cache字块分为u组，每组v块，则Cache的总块数为： m=uv 若j为主存块号，i为cache块号，q为组号，q=0,1,2,u-1， 按u为模将其映像到cache，那么，主存字块可以用下列映象函数映象到Cache的第u组内： q = j mod u 凡是符合以上求模公式的主存j块，均会映像到Cache的u组内，一一对应，为直接映像关系。可映像到u组内的任何一块，组内是全相联映像。v值越大越灵活，相联搜索的规模越小。 v比较小，通常取2、4、8。 例:设一个Cache中有8个块,访问主存进行读操作的块地址序列为22、26、22、26、16、4、16、18，求每次访问

23、后Cache中的内容。解：地址命中与否地址转换关系 不命中 22 MOD 8=6 不命中 26 MOD 8=2 22 命中 22 MOD 8=6 命中 26 MOD 8=216 不命中 16 MOD 8=04 不命中 4 MOD 8=4 16 命中 16 MOD 8=0 18 不命中 18 MOD 8=2 直接映象下Cache访问情况 直接映象的块分配情况访问顺序 1 2 3 4 5 6 7 8 地址 22 26 22 26 16 4 16 18块分配情况 22操作状态调进2226调进2226命中2226命中222616调进2241626调进2216264命中2216184替换例：设有一个ca

24、che的容量为2K字，每个块为16字，求(1) 该cache可容纳多少个块？(2) 如果主存的容量是256K字，则有多少个块？(3) 主存的地址有多少位？cache地址有多少位？(4) 在直接映象方式下，主存中的第i块映象到cache中哪一个块中？(5) 进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？解：(1) cache中有2048/16=128个块。(2) 主存有256K/16=16384个块。(3) cache容量为2K=211字，所以cache字地址为11位。(4) 主存中的第i块映象到cache中第 i mod 128个块中。(5) 存储器的字地址分成三段：区号、块号、块

25、内字地址。 区号的长度为18-11=7位，块号为7位。块内字地址为4位。 Cache的容量和块的大小是影响Cache的效率的重要因素。 一般来说，Cache的存储容量比主存的容量小得多; 但不能太小，太小会使命中率太低； 也没有必要过大，过大不仅会增加成本，而且当容量超过一 定值后，命中率随容量的增加将不会有明显地增长。 但随着芯片价格的下降，Cache的容量不断增大，已由几K发展到几十K，甚至到几百K字节。 因此，cache容量是总成本价与命中率的折衷值。 如：80386的主存最大容量为4G，与其配套的cache容量为 16KB或32KB，其命中率为95%。Cache容量与命中率块长与命中率

26、 块长与命中率的关系更为复杂，它取决于程序的局部特性。块长的最优值很难确定，通常： 每块取4至8个可编址单位（字或字节）较好； 也可取一个主存周期所能调出主存的信息长度。 例如，CARY-1的主存是16个交叉体，每个体为单字宽， 其指令cache的块长为16个字； IBM 370/168机主存是4体交叉，每个体宽为64位 （8个字），其cache块长为32个字。2.替换策略 当一个新的主存块要调入到cache，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为cache工作原理要求它应尽量保存最新的数据。(1)对于采用直接映射方式的cache来说： 因一个主存块只有一个特定的行位置

27、可存放，所以问题解决很简单，把此特定行位置上的原主存块妥善处理后，换出Cache即可。(2)对于全相联的cache来说，它的全部行都是可被替换的特定行；而组相联的cache中同组各路的行都是可被替换的特定行： 这样就要从允许存放新主存块的若干特定行中选取一行换出。 替换问题与cache的组织方式紧密相关 如何选取就涉及到替换策略或称替换算法的采用。以硬件实现的常用算法主要有以下三种。 FIFO(First In First Out)算法是把一组中最先调入Cache的字块替换出去，不需要随时记录各个字块的使用情况，所以实现容易，开销小。1).先进先出（FIFO）算法LRU （Least Rece

28、nt1y Used）算法是将近期内长久未被访问过的行换出。方法： 每行设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访问次数计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。这种算法显然保护了刚拷贝进新数据的行，符合cache工作原理，因而使cache有较高的命中率。2).近期最少使用（LRU）算法 LRU算法硬件实现也不难。如果是两路组相联的cache，就更简单了。例如：两路组相联的cache。 因为一个主存块只能在一个特定组的两行中来做替换选择， 二选一完全不需要计数器，一组两行只需要一个二进制位即可。 如规定一组中的A行拷贝进新数据

29、将此位置“1”，B行拷贝进新数 据将此位置“0”。那么当需要替换时只需检查此乒乓位的状态即 可，为“0”换出A行，为“1”换出B行，实现了保护新行的原则。 Pentium片内的数据cache是一个两路组相联结构，采用的就 是这种简捷的LRU替换策略。 随机替换（Random Rep1acement）策略实际上是不要什么算法，从特定的行位置中随机地选取一行换出即可。 这种策略以硬件实现最容易，而且速度也比前两种策略快。 缺点是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和cache 的工作效率。但这个缺点可以用增大cache的容量来克服，实验统计表明，随机替换策略的功效只是稍

30、逊于前两种策略。3).随机替换例：一访Cache的地址流为：2 3 2 1 5 2 4 5 3 2 5 2，假设Cache只有3块(?)时间： 1 2 3 4 5 6 7 8 9 10 11 12块地址流： 2 3 2 1 5 2 4 5 3 2 5 2FIFO2 调23 调23 命231调531替521替524替524命324替324命354替352替3LRU2 调23 调23命231调251替251命254替254命354替352替352命352命5先进先出替换策略访问顺序 1 2 3 4 5 6 7 8地址块号 2 11 2 9 7 6 4 3块分配情况操作状态 调进 调进 命中 调进

31、调进 替换 替换 替换先进先出替换方式下的cache内容变化情况2-211-211-2119-211976119764976437近期最久未使用替换策略访问顺序 1 2 3 4 5 6 7 8地址块号 2 11 2 9 7 6 4 3块分配情况操作状态 调进 调进 命中 调进 调进 替换 替换 替换最久未使用替换方式下的cache内容变化情况2*-2*11-211*-211*9-211*972*697469*746373.写操作策略 因为cache的内容是部分主存内容的副本，应该与主存内容保持一致。而CPU对cache的写入更改了cache内容，如何与主存内容保持一致就有几种写操作工作方式可供

32、选择，统称为写策略。1).写回法（write-back） 当CPU对cache写命中时，只修改cache的内容不立即写入主存，只当此行被换出时才写回主存。 对一cache行的多次写命中都在cache中快速完成修改，只是需被替换时才写回速度较慢的主存，减少了访问主存的次数从而提高了效率。(1) CPU对cache写命中时方法：每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。当某行被换出时，根据此行修改位为1还是为0，决定是将该行内容写回主存还是简单地弃之而不顾。(2) CPU对cache写未命中时 对于cache写未命中，写回法的处理是为包含欲写字的主存块在cache分配一行，

33、将此块整个拷贝到Cache后在cache中对其进行修改；拷贝主存块时虽已读访问到主存，但此时并不对主存块修改，统一地将主存写修改操作留待换出时进行。(3)优缺点： 写cache与写主存分开进行方式可显著减少写主存次数，但写回法存在cache/主存不一致性的隐患。2).写直达法（write-through） 也称全写法。(1)当cache写命中时：cache与主存同时发生写修改。这种策略显然较好地维护了cache与主存的内容一致性；(2)当cache写未命中时：直接向主存写。 但此时是否将修改过的主存块取到cache，写直达法有两种选择： 一种是取主存块到cache并为它分配一个行位置， 称为W

34、TWA法(Write-Through-with-Write-Allocate）； 另一种是不取主存块到cache, 称为WTNWA法 （Write-Through-withNO-Write-Allocate）。写直达法是写cache与写主存同步进行，优点是： cache每行无需设置一个修改位以及相应的判测逻辑；缺点是： cache对CPU向主存的写操作无高速缓存功能，降 低了cache的功效。 80486处理器片内cache采用的就是写直达法。(3)优缺点：3)写一次法（write-once）策略：写一次法是一种基于写回法又结合了写直达法的写策略，即写命中和写未命中的处理与写回法基本相同，只是

35、第一次写命中时要同时写入主存。应用： 这种策略主要用于某些处理器的片内cache，例如Pentium处理器的片内数据cache就采用的是写一次法。因为片内cache写命中时，写操作就在CPU内部高速完成，若没有内存地址及其它指示信号送出，就不便于系统中的其它cache监听（snoop）。 在第一次片内cache写命中时， CPU要在总线上启动一个存储器写周期。其它cache监听到此主存块地址及写信号后，即可把它们各自保存可能有的该块拷贝及时作废（无效处理）。尔后若有对片内cache此行的再次或多次写命中，则按回写法处理，无需再送出信号了。这样虽然第一次写命中时花费了一个存储周期，但对维护系统全

36、部cache的一致性有利。而大多的cache写操作不涉及到片外，对指令流水执行有利。 Intel公司的82385Cache控制器，是专为80386设计的高性能32位外围支持芯片。它与静态RAM(简称SRAM)芯片一起构成高速缓冲存储器。 标志存储器和控制逻辑均在芯片内，使用82385可大大简化高速缓冲存储器子系统的设计。 82385没有把数据存储器集成与一体。 Intel 82385 cache控制器支持直接映象和两路组相联映象两种地址映象方式。1.Intel 82385 Cache简介结构框图(Snoop bus) 支持容量为16K字节或32K字节的cache，它以16MHz和20MHz的操

37、作速度与80386CPU相配合，组成与80386相匹配的主存-Cache存储系统，并可全部映象80386的32位地址，提供4GB（千兆字节）的地址空间，能使CPU几乎无等待地读出数据，命中率可高达99。2.82385 Cache的直接映象 Intel 80386的4GB地址空间被分成217页； 页的大小和Cache的容量相同，均为8K字 (32位) 或32K字节. Cache又分成1024组，每组8个字 (832位)。 每个字叫做一“行”，行是主存和Cache之间的信息传输单位（ 块）。 在82385 Cache目录表中，对应Cache的每一组有一个条目(目 录项），它有26位。高17位为标记

38、，中间一位为标记有效位 ，低8位为行有效位。17位标记指出主存的页号，标记217页 中的某一页。 Cache由两部分组成： 一部分存放由主存储器来的数据，称数据存储器。 另一部分存放该数据所在的主存储器的地址，故称地址标记 存储器，或目录存储器。 这两个存储器都为静态存储器。直接映象方式： 主存各页中的第0组只能驻留在Cache的第0组，其余各组依次 类推。 目录表中的8位行有效位分别对应每组中的8行，如某一行被 调入Cache中，则该行有效位置“1”，同时将标记有效位置 “1” 。 图中所示为主存第二页的第九行正驻留在Cache中，则第一组的对应表目中的标记位将记作1。由于第0组包含第07行

39、，第1组包含第815行，所以，第1组对应表目中第2个行有效位被置“1”，说明第9行已驻留在Cache中。 A31A15为17位标记字段， A14A5为10位组地址字段 A4A2 为行选择字段。 总线低13位地址A14A2又作为Cache地址，它可以直接选择Cache中8K字中的一行。82385Cache控制器把80386地址线A2A31分成3个字段: 17 10 3标记 组 行A31A15 A14A5 A4A2 82385用A14A510位地址选择目录表中1024个表目中的一条， 用A4A2选择表目中8个行有效位中的一位。这13位Cache 地址选择Cache中的一行 (4字节)。 82385

40、将地址总线的标记字段（A31A15）与目录表表目中的 标记进行比较，若二者相等，并且目录中的标记有效位和行 有效位皆为“1”状态时，则读命中。 82385指示Cache将选中的字送入80386的数据总线。 读命中不改变Cache和目录中的内容。当80386启动读周期时：(1) 行失效. 这时,目录表目中的标记和地址总线的标记字段相等, 且标记有效位为“1”，但行有效位为“0”。(2) 标记失效. 这时，目录表目中的标记和地址总线标记字段不 相等，或是标记有效位为“0”。 当失效发生时，80386则直接访问主存取得数据，并同时将该内容写入Cache，并修改目录表。 若为行失效，则只将该行对应的行

41、有效位置“1”； 若为标记失效，则用上述地址页号用来修改标记，并将标记 有效位置“1”，并置“1”相应的行有效位，清 除其它七个行有效位。读失效可分为两种情况直接映象的cache系统 它把每页分成含有相同数量行（块）的组，这是为了减小地址目录表的项数，以减小Cache目录表的容量。82385 Cache采用的是一种改进的直接映象方式:3.82385 Cache的组相联映象在两路组相联映象方式下： Cache被分成A和B两个体，每体为4K字。 主存页面的大小和Cache的一个体的容量相同，其页数则比直 接映象时增加一倍，共218页。 对应两个体的目录表也为A和B两部分，每个部分有27位, 高 1

42、8位标记主存页号, 中间1位作标记有效位，低8位作行有效位. 目录表中的LRU位是附加位，用以指定A和B两个体中同一组 的哪一行是近期最少使用行，即是被置换的对象。 在两路组相联映象方式中，主存各页的同一组可以任意映象到 Cache的两个体的同一组中。同时可有两个页的同一组存于 Cache。82385把地址总线划分为三段： 18 9 3 标记 组 行A31A14 A13A5 A4A2 当82385选中9位组字段中的某一个特定组时，就要对18位的标记进行比较，如果地址匹配，对特定的一路命中，则把标记的有效位置位，并且被选中的行也置位，82385允许对被选中的cache存储体进行数据的读出或写入。

43、两路组相联cache系统奔腾PC机的CacheL2 安装在主板上，其容量是256 KB或512KB，采用的两路组相联映射方式，每行可以是32，64或128字节。L1 集成在CPU内，其容量是16KB，采用的也是两路组相联映射方式，每行是32字节。 L2的内容是432MB容量主存的子集，L1又是L2的子集，从而使L1未命中处理时间大为缩短，为L1的高速使用提供了支持。L2L11.Pentium PC采用两级cache结构 CPU中的L1分立为各8KB的指令cache和数据cache。 (有学者曾对某些程序进行跟踪研究，得到的统计结果是：取指令占63，取数占25，写数占12。这一结果表明将指令ca

44、che与数据cache分开是有好处的。) 指令cache是只读的，单端口256位（32字节）向指令预取缓冲器提供 指令代码。 数据cache是读写的，双端口，每端口32位（4字节），向两条流水线 的整数运算单元和寄存器提供数据或接收数据，两个端口还可组合成 一个64位端口与浮点运算单元相接。 两个cache与64位数据、32位地址的CPU内部总线相连。CPU中的L1预取缓冲存储器指令译码256控制ROM控制部件地址生成(U流水线)地址生成(V流水线)整数寄存器组ALU(U流水线)ALU(V流水线)筒型移位器8KB数据Cache浮点部件控制寄存器组加法器除法器乘法器80808KB代码Cache分

45、支目标缓冲器预取地址指令指针转移校验和目标地址分页部件323232323232总线部件6464位读总线64位数据总线32位地址总线控制TLBTLB32位地址总线PentiumCPU框图2.Pentium1级cache的组织结构(数据cache) 8KB的数据cache采用两路组相联的组织方式，每一 路为4KB字节，分成128组，每组2行，每行32字节 （8个双字，1个双字32位）； 每行有一个20位的标记和2位的M/E/S/I的状态位， 这22位构成该行的目录项； 采用LRU替换策略，一组两行共用一个LRU位； （L1指令cache的组织类同于此，只是不再是2位状 态位而是1位有效位。） ME

46、SI协议 一种采用写-无效方式的监听协议，它要求每个cache有两个状态位，用以描述该行当前是处于修改态(M)、专有态(E)、共享态(S)、或者无效态(I)中的哪一个状态，从而决定对它的读/写操作行为。用于维护cache的一致性。 L2级cache采用写回法，L1级cache采用写一次法。为维护 cache的一致性， L1、L2均采用MESI协议。 L2负责整个系统的cache/主存一致性，L1负责响应L2，与L2一起维护 L1/L2两个cache的一致性，从而保证了L1-L1-主存三级存储系统的一致性。 CPU与外部数据交换时，存储器读写总线周期主要有两类:一类是256位猝发式传送，用于L1

47、的行填入和行写出,一次完成整行的填入或写出。 另一类是不经L1的64位传送 ，称为非超高速缓存式传送。3.两级cache和主存之间的工作环境方框图虚拟存储器的基本概念页式虚拟存储器段式虚拟存储器替换策略段页式虚拟存储器奔腾PC的虚地址模式虚拟存储器的基本概念1. 虚拟存储器 虚拟存储器是建立在主存-辅存（外存）物理结构基础上的，由负责信息划分及主存-辅存之间信息调度的辅助硬件及操作系统的存储管理软件所组成的一种存储体系。它将主存和辅存的地址空间统一编址，形成一个庞大的存储空间，在这个大空间里，用户自由编程，完全不必考虑程序在主存中是否装得下，或者放在辅存中的程序将来在主存中的位置，编好的程序由

48、计算机操作系统装入辅助存储器，程序运行时附加的辅助硬件机构和存储管理软件会把辅存的程序一块块自动调入内存由CPU执行或调出内存，用户感觉到的不再是处处受到主存容量限制的存储系统，而是好像具有一个容量充分大的存储器，这样的存储体系称为“虚拟存储器”。 虚拟存储器只是一个容量非常大的存储器的逻辑模型，不是任何实际的物理存储器。它借助于磁盘等辅助存储器来扩大主存容量，使之为更大或更多的程序所使用。 虚拟存储器指的是主存-辅存层次。以透明的方式给用户提供了一个比实际主存空间大得多的程序地址空间。它能使计算机具有辅存的容量，而接近于主存的速度。 对应用程序员来说，好象有一个比实际主存大得多的、可使编程空

49、间不受限制的虚(主)存空间存在。2.虚地址和实地址 虚拟存储器的辅存部分也能让用户象内存一样使用，用户编程时的指令地址允许涉及辅存大小的空间范围，这种指令地址称为“虚拟地址”（虚地址）或“逻辑地址”。对应的存储空间称为“虚拟地址空间”或“逻辑空间”。 实际的主存储器地址则称为 “物理地址”（ 实地址）。它由CPU引脚送出，是用于访问主存的地址。对应的存储空间称为“物理地址空间”。 虚拟存储器的用户程序以虚拟地址编址并存放在辅存中，程序运行时CPU以虚地址访问主存，由辅助硬件找出虚地址和物理地址的对应关系，判断这个虚地址指示的存储单元是否已装入主存，如果在主存，CPU就直接执行已在主存的程序；如

50、果不在，要进行辅存向主存的调度，这种调度以块为单位进行， 存储管理软件和相应的硬件把访问单位所在的程序块从辅存调入主存，且把程序虚地址变换成实地址，然后由CPU访问主存。 虚拟存储器程序执行中各程序块在主存和辅存之间进行自动调度和地址变换，主存-辅存形成一个统一的有机体，对于用户是透明的。3.几种虚拟存储器 虚存通过增设地址映象表机构来实现程序在主存中的定位。这种定位技术是把程序分割成若干个较小的段或页，用相应的映象表机构，来指明该程序的某段或某页是否已装入主存，若已装入主存，则应同时指明其在主存中所处的开始位置；若未装入主存，则应到辅存中去调段或页，并建立起程序空间和实存空间的地址映象关系。

51、这样，程序执行时通过查映象表，将程序(虚)地址变成主存地址再访问主存。 由于采用的存储映象算法不同，形成了多种不同的存储器管理方式的虚拟存储器，其中主要有段式、页式、段页式三种。页式虚拟存储器1.页、页表 页式虚拟存储器的主存和虚拟空间划分成大小相等的页，虚拟空间的页数要比主存空间的页数多很多。(1) 页00000 0000000000 1111100000 0000000001 1111100000 0000000010 1111111111 0000011111 11111高位(5位) 低位(11位)实地址主存空间实页号 页内地址2K2K2K2K2页31页0页1页 CPU访问主存时送出的是

52、程序的虚地址，计算机必须判断出该地址的存储地址是否已在主存中：如果在的话，找出在主存哪一页；如果不在的话，需要将所在页的内容调入指定的主存页后才能被CPU执行。 为此，需要建立一张虚地址页号与实地址页号对照表，用以记录程序的虚页面调入主存时被安排在主存的位置。这张表叫页表。 页表是存储管理软件根据主存运行情况自动建立的，内存中有固定区域存放页表。每个程序都有一张页表。 页表的长度等于该程序虚页数。(2) 页表页表信息字主存页号 主存地址空间 虚存页号 程序地址空间0132401272.地址映象(a) 地址映象关系页内地址页内地址实页号虚页号 2 1 6 1(b) 地址变换方法主存页号 装入位

53、- 0 7 1 - 0 页表基址虚地址实地址页表页基址寄存器虚实地址变换是由存储管理软件自动完成的。(来自CPU) 虚页内容若没有调入主存，则计算机启动输入输出系统，把虚地址指示的一页内容从辅存调入主存，再提供CPU访问。注意： 虚地址和辅存地址不是一回事，程序员按虚存空间编址，虚地址由虚页号和页内地址组成，辅存实际地址以磁盘为例，地址由磁盘机号、磁头号、柱面号、块号、块内地址组成，因此从辅存调页时还需要虚存地址空间到辅存地址的变换。这个变换也可以采用类似前述页表的方式。此表称为外页表。 CPU访问主存页面失效时，调用外页表把程序的虚地址变换成辅存的实际地址，从辅存调出该虚页，而后根据页表指出

54、实页号再把虚页内容调入主存。 调入由地址变换机构实现。3.加速地址变换的方法(1) 把表的最活跃部分放在高速存储器组成快表；(2) 一些影响速度的关键部位引入硬件支持，如采用按内容 查询的相联存储器。 使用快表方法 快表由硬件组成，比页表小得多，查表时，由逻辑页号同时去查快表和慢表，当在快表中有此逻辑页号时，就能很快地找到对应的物理页号送入实主存地址寄存器，从而做到虽采用虚拟存储器但访主存速度几乎没有下降。页式管理方案 页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，称为页面。新页调人主存也很容易掌握，只要有空白页面就可。它比段式管理系统的空间浪费要小得多。页式管

55、理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理保护和共享都不及段式来得方便。例：一个有32位程序地址空间，页面容量为1KB，主存的容量为8MB的存储系统，问：(1) 虚页号字段有多少位？页表将有多少行？(2) 页表的每一行有多少位？页表的容量有多少字节？解：(1) 页表的长度为222 =4M行。(2) 主存的容量为8MB=223B， 主存中页框架的数量有223 / 210 = 213个。页表中主存页号字段是13位长，加上其它信息将超过16位。设页表的每一项为16位，页表的容量为4M2 = 8MB。例：一个虚拟存储器有8个页面，页面大小为1024字，内存有4个页面框架。

56、页表的内容为：虚页号实页号03112-3-425-607-对应于虚拟地址4098的主存地址是什么？解：40981024 = 42，所以虚页号为4，页内地址为2。从表中查得实页号为2，实际地址为21024 + 2 = 2050。段式虚拟存储器 段式虚拟存储器，是以程序的逻辑结构所形成的段(如主程序、子程序、过程、表格等)作为主存分配单位的虚拟存储器管理方式的存储器。 段表一般驻留在主存中。 每个段的大小可以不相等，有的甚至事先无法知道。每个程序都有一个段表(映象表)，用于存放该道程序各程序段从辅存装入主存的状况信息。段式虚拟存储器地址映象变换方法主存地址空间程序地址空间 1000 3000(a)

57、 地址映象关系0 段基址 装入位 段长 访问方式(b) 地址变换方法0段1段2段段内地址段号 - 0 1K3000 1 2K1000 1 1K虚地址实地址（相加形成）段表段基址寄存器12段号段表基址 段表中的每一项(对应表中每一行)用于描述该道程序的一个自然段的基本情况： 段号用以存放程序段的段号，它与虚地址中的段号相一致。 装入位表明该段是否已装入主存。 段基址字段用以指明当装入位为“1”时，该程序段装入主存 中的起始(绝对)地址。 段长指明该程序段的大小， 访问方式用以标记该段能允许访问的方式，如只读、可写、 只能执行等。 程序执行时，要先根据段表确定所访问的虚段是否已调入主存。若没有调入

58、，则先调入；若已调入，就要确定其在主存中的位置，也就是要进行虚实地址变换，然后方可执行。表表把主存按段分配的存储管理方式称为段式管理。段式管理系统的优点是段的分界与程序的自然分界相对应段的逻辑独立性，使它易于编译、管理、修改和保护,也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间，造成浪费和段的起点和终点不定。 将段式管理和页式管理相结合，就构成了虚存的段页式管理。 它把程序按逻辑单位分段以后，再把每段分成固定大小的页。 程序对主存的调入调出是按页面进行的，但它又可以按段实 现共享和保护，兼备页式和段式的优点。所以目前大中型机 都采用这种虚拟存储器。段页式虚拟存储器将段式和页式

59、管理方式结合起来.段页式将实际存储器机械等分成固定大小的页,程序则按模块分段,每段又分成与主存页面大小相同的页.段页式管理兼有段式和页式的优点.(a) 地址映象关系 段基址寄存器 段表 页表 0 0 0 . N-1 L-1 M-1 段表长度 段表基址 装入位 段长 页表地址(b) 地址变换方法页内地址页内地址页号页号段号基号 1 M 1 L主存地址空间程序地址空间A段B段虚地址实地址 在段页式虚拟存储系统中,每道程序通过一个段表和相应的一组页表来定位。 段表中每一行对应一个段，其中“装入位”表示该段的页表是否已装入主存。若未装入，则应请求从辅存中调入页表；若已装入，则地址字段表示该段的页表在主

60、存中的起始位置。 “段长”字段表示该段页表的行数。 每个段有一个页表，页表中用“装入位”指明此段该页是否已装入主存。若未装入，就需从辅存调页；若已装入，则用地址字段指明该页在主存中的页号。 段页式虚存在程序地址向实际主存地址变换时，首先要查段表，然后查页表。 如果有多个用户在机器上运行，多道程序的每一道需要一个基号, 由它指明该道程序的段表起始地址。虚拟地址格式如下：基号 段号页号页内地址某道程序地址程序标志 当CPU要用到的数据或指令不在主存时，产生页面失效(缺页)，此时要从辅存调进包含这条指令或数据的页面。替换规则和cache中的行替换策略有很多相似之处，但有三点显著不同：(1) 缺页至少