第七章 存储系统.ppt

1、第七章 存储系统,7.1 存储系统的层次结构 7.2 高速缓冲存储器（cache） 7.3虚拟存储器 7.4相联存储器 7.5存储保护,学习目的 1. 掌握存储系统的层次结构，分析层次结构的目的和实现方式。 2. 掌握高速缓冲存储器的原理、基本结构和cache的存储器组织。 3. 掌握虚拟存储器信息传送单位和存储管理和虚拟存储器工作的全过程。 4. 了解相联存储器和存储保护。,重点 1.层次结构的目的和实现方式。 2.高速缓冲存储器的原理、基本结构和cache的存储器组织。 3.虚拟存储器信息传送单位和存储管理以及虚拟存储器工作的全过程。难点 1.cache的存储器组织。 2.虚拟存储器工作的

2、全过程。,7.1 存储系统的层次结构,CPU,CACHE,主存（内 存）,辅存（外 存）,存储体系：把各种不同存储容量、不同存取速度、不同价格的存储器，组成层次结构，并通过管理软件和辅助硬件将不同性能的存储器组合成有机的整体，称为计算机的存储层次或存储体系。,cache,1 主存与辅存之间的关系,主存(半导体) 优:速度快 缺:容量受限,单位成本高,断电丢失信息 辅存(光盘,磁盘) 优:容量大,信息长久保存,单位成本低. 缺:存取速度慢 虚拟存储系统速度接近于主存的速度，容量接近于辅存的容量，每位平均价格接近于辅存平均价格（大容量低成本）。 虚地址经辅助软、硬件变换成实地址。,2 主存和高速缓

3、存之间的关系,Cache引入 为解决CPU和主存之间的速度差距,提高整机的运算速度,在CPU和主存之间插入的由高速电子器件组成的容量不大,但速度很高的存储器作为缓冲区。 解决了速度与成本之间的矛盾（速度接近cache，容量与每位价格接近于主存）。 Cache特点 存取速度快，容量小，存储控制和管理由硬件实现,较低级：与处理器较远的存储级-容量较大、速度较慢、使用较廉价的技术工艺,存储器系统的层次结构的特点：,在任何指定时间，数据只能在相邻的两级之间拷贝：,较高级：与处理器较近的存储级- 容量较小、速度较快、使用较昂贵的技术工艺,层次化存储系统,访存局部性 时间局部性 空间局部性 层次化结构 c

4、ache 主存 辅存,容量和存取时间增加,每位价格增加,1.包含性,2. 相邻层之间的数据传送单位 CPU高速缓存：字 高速缓存主存储器：块（每块32个字节（4个字） 主存磁盘：页面（比如每页4K字节，包含128块） 磁盘磁带：段,M0 M1 M2 Mn 所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2，如果在Mi中找到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，Mn中都一定可以找到。,M1:高速缓存,a,b为高速缓存 块，32个字节,M2:主存储器,M3:磁盘存储器,M4:磁带机 后援存储器,7.2 高速缓冲存储器

5、Cache,一、cache存储器工作原理程序访问的局部性在较短时间内由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内。（指令分布的连续性和循环程序及子程序的多次执行）这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问的局部性。 时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。(程序循环、堆栈) 空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。(指令顺序执行、数组存放),根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在

6、程序运行时，不必从主存储器取指令和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓冲存储器Cache。Cache由高速的SRAM组成，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。,cache的基本结构,它由cache存储体、地址映象变换机构、cache替换机构几大模块组成。,Cache概念：（1）CPU与主存储器之间的一种高速缓冲装置；（2）Cache-主存层次结构：由硬件变换地址和控制调度。 Cache具有如下特点： 位于CPU与主存之间，是存储器层次结构中级别最高的一级； 容量比主存小，目前一般有数到数； 速度一般比主存快倍,通常由存储速度高的

7、双极型三极管或SRAM组成； 其内容是主存的部分副本； 其用途可用来存放指令，也可用来存放数据； 快存的功能全部由硬件实现，并对程序员透明。,cache的命中,任何时候都有一些主存块处在Cache中。 当CPU发出读请求时，将主存地址m位（或m位中的一部分）与Cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况： (1)当比较结果相等时，说明需要的数据已在Cache中，那么直接访问Cache就行了，在CPU与Cache之间，通常一次传送一个字；访问Cache命中 (2)当比较结果不相等时，说明需要的数据尚未调入Cache，那么就要把该数据所在的整个字块从主存一次调进来。访 问Ca

8、che不命中,cache的命中率,命中率指CPU所要访问的信息在Cache中的比率； 失效率指所要访问的信息不在Cache中的比率。 在一个程序执行期间：设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有：,若 tc表示命中时的cache访问时间，tm表示未命中时的主存访问时间，1-h表示不命中率， 则cache主存系统的平均访问时间ta为：ta=htc+(1-h)(tm +tc),例：CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache-主存系统

9、的效率和平均访问时间。,解： h=Nc/(Nc+Nm)=1900/(1900+100)=0.95ta=htc+(1-h)tm0.95*50+0.05*(250+50)=62.5ns,例:已知Cache存储周期为40ns,主存存储周期为200ns, Cache -主存系统平均访问时间为50ns,求Cache的命中率是多少?,解: 因为 ta=h*tc+(1-h)(tm+tc)所以 h=(tm+tc-ta)/tm=(200+40-50)/200=19/20,课后作业,1 设某流水线计算机有一个指令和数据合一的cache，已知cache的读写时间为10ns，主存的读写时间为100ns，取指的命中率为

10、98%，数据的命中率为95%，在执行程序时，约有1/5指令需要存取一个操作数，为简化起见，假设指令流水线在任何时候都不阻塞。问设置cache后，与无cache比较，计算机的运算速度可提高多少倍? 2 接上题，如果采用哈佛结构(分开的指令cache和数据cache)，运算速度可提高多少倍?,（1）数据块在Cache中存放在哪个位置？即定位问题（地址映象）。如果一个块存放在某一Cache中，怎样确定并找到该块，即寻址问题（地址变换）。 （2）不命中时将从主存储器中访问，并将该块调入Cache中，但是如果Cache中已无空闲空间，则势必将Cache中的某一块调出，但应调出那一块，即替换问题。 （3）

11、在写访问时，写入Cache必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性。,二、Cache结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？, 地址映象 把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。 地址变换信息按这种映象关系装入Cache后，执行程序时，将主存地址变换成 Cache地址的变换过程叫做地址变换。地址映象和变换密切相关。 使用Cache的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的。这带来的另一好处是Cache的透明性，除了程序运行速度提高之外，用户包括系统软件

12、编制人员，丝毫未感觉到Cache的存在。,1.地址映象(映射)与地址变换,基本的地址映象方式：直接映象； 全相连映象；组相连映象,在高速缓冲存储器中,把Cache和主存机械等分为相同大小的块,每一块是由若干个字(或字节)组成.,由于Cache的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的哪一块的副本(拷贝)。,例：某机主存容量为1MB,划分为2048块,每块512B;Cache容量为8KB,划分为16块,每块512B。,图7.2 cache的基本结构,指明是主存的哪一块副本，相当于主存中块的编号,块长一般取一个

13、主存周期所能调出的信息长度,因刚加电时所有标记位都为“0”，开始执行程序时，命中率较低。另外Cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。,标记的有效位,每个标记设置有一个有效位。机器加电启动时，Reset信号将所有标记的有效位置“0”，即无效。程序执行过程中，Cache不命中时，逐步将指令块或数据块从主存调入Cache中的某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或数据时，可直接从Cache中取指令或数据。,（1）直接映像,这是一种多对一的映射关系，但一个主存块只能映象到Cache的一个特定块位置上去。 直接映像函数可定义为：j=i mod 2c其

14、中，j是cache的字块号，i是主存的字块号。在这种映像方式中，主存的第0块，第2c块，第2c+1块，只能映像到cache的第0块，而主存的第1块，第2c+1块，第2c+1+1块，只能映像到cache的第1块。,7位,直接映象的地址变换方法,图7.3 直接映像cache组织,块内地址,组地址,区地址,优点： 实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在cache存储器中。 缺点： 不够灵活。主存中2t个字块只能对应唯一的cache存储器字块，因此，即使cache存储器别的许多地址空着也不能占用。这使得cache存储空间得不到充分利用，并降低了命中率。,例：设有一个ca

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

16、i mod 128个块中。 (5) 存储器的字地址分成三段：区地址、组地址、块内字地址。区地址的长度为18-11=7位，组地址为7位，块内字地址为4位。,（2）全相联映像,全相联映像方式是最灵活但成本最高的一种方式，如图7.4所示 ：,图7.4 全相联映像cache组织,实际上由于它的成本太高而不能采用。（1）标记位数增加；（2）比较的地址数目增多。,11位,允许主存中的每一个字块映象到Cache的任何一个字块位置上。,全相联映象的地址变换方法,这只是一个理想的方案。两个原因使其实际上很少采用： (1) 标记位数从7位增加到11位，使Cache标记容量加大， (2) 访问Cache时，需要和C

17、ache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在Cache中。由于Cache速度要求高，通常由“按内容寻址”的相联存储器完成，所需硬件逻辑电路很多，以至于无法用于cache中。实际的Cache组织则是采取各种措施来减少所需比较的地址数目。优点：灵活，块冲突概率小。只有当Cache中全部装满后,才有可能出现块冲突； 缺点：要作相联搜索，速度慢，代价高。,(3) 组相联映像,组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组内全相联，组间直接映像Cache字块分为2c组，每组包含2r个字块，于是有c c+r。那么，主存字块Mm（i）（0=i=2m-1)可以用下列映像函数映

18、像到cache字块Mc（j）（0=j=2c-1）上：j=(i mod 2c)*2r+k 0=k=2r-1 k为位于上列范围内的可选参数（整数）。,图7.5 组相联映像cache组织,组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r=0时，是直接映像方式；当r=c时，是全相联映像方式。主存中的一块能对应到Cache中一个特定组的任意一行。若组中有n个块，则称其为 n路组相联。 直接映象和全相联映象是组相联的特例：直接映像：1路组相联全相联映像：2c路组相联cache的命中率除了与地址映像的方式有关外，还与cache的容量有关。cache容量大，命中率高，但达到一定容量后，命

19、中率的提高就不明显了。,课后作业,1.设某计算机的cache采用4路组相联映像，已知cache容量为16KB，主存容量为2MB，每个字块有8个字，每个字有32位。请回答： (1) 主存地址多少位(按字节编址)，各字段如何划分(各需多少位)? (2) 设cache起始为空，CPU从主存单元0，1，100。依次读出101个字(主存一次读出一个字)，并重复按此次序数读11次，问命中率为多少?若cache速度是主存的5倍，问采用cache与无cache比较速度提高多少倍?2.设某计算机采用直接映像cache，已知容量为4096B。 (1) 若CPU依次从主存单元0，1，99和4096，4097，419

20、5交替取指令，循环执行10次，问命中率为多少? (2) 如cache存取时间为10ns，主存存取时间为100ns，cache命中率为95%，求平均存取时间。,2.替换算法,当一个新的主存块要调入到cache，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为cache工作原理要求它应尽量保存最新的数据。,(1)对于采用直接映射方式的cache来说：因一个主存块只有一个特定的行位置可存放，所以问题解决很简单，把此特定行位置上的原主存块妥善处理后，换出Cache即可。 (2)对全相联的cache来说，它的全部行都是可被替换的特定行； （3）组相联的cache中同组各路的行都是可被替换的

21、特定行： 这样就要从允许存放新主存块的若干特定行中选取一行换出。, 替换问题与cache的组织方式紧密相关,如何选取就涉及到替换策略或称替换算法的采用。以硬件 实现的常用算法主要有以下三种。,1).先进先出（FIFO）算法FIFO(First In First Out)算法是把一组中最先调入 Cache的字块替换出去，不需要随时记录各个字块的使用情 况，所以实现容易，开销小。,2).近期最少使用（LRU）算法 LRU （Least Recent1y Used）算法是将近期内长久未被访问过的行换出。方法：每行设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访

22、问次数计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。这种算法显然保护了刚拷贝进新数据的行，符合cache工作原理，因而使cache有较高的命中率。LRU算法硬件实现也不难。如果是两路组相联的cache，就更简单了。,例如：两路组相联的cache。因为一个主存块只能在一个特定组的两行中来做替换选择， 二选一完全不需要计数器，一组两行只需要一个二进制位即可。如规定一组中的A行拷贝进新数据将此位置“1”，B行拷贝进新数 据将此位置“0”。那么当需要替换时只需检查此二进制位的状态即可，为“0”换出A行，为“1”换出B行，实现了保护新行的原则。 Pentium片内的数据cache是一

23、个两路组相联结构，采用的就 是这种简捷的LRU替换策略。,3).随机替换法 随机替换（Random Rep1acement）策略实际上是不要什么算 法，从特定的行位置中随机地选取一行换出即可。优点：这种策略以硬件实现最容易，而且速度也比前两种策略快。缺点：是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和cache 的工作效率。但这个缺点可以用增大cache的容量来克服，实验统计表明，随机替换策略的功效只是稍逊于前两种策略。,例：一访Cache的地址流为：2 3 2 1 5 2 4 5 3 2 5 2，假设Cache只有3块(?),时间： 1 2 3 4 5 6 7 8 9

24、10 11 12 块地址流： 2 3 2 1 5 2 4 5 3 2 5 2,FIFO,3,LRU,5,课后作业,某程序对页面要求的序列为P3P4P2P6P4P3P7P4P3P6P3P4P8P4P6。 (1) 设主存容量为3个页面，求FIFO和LRU替换算法时各自的命中率(假设开始时主存为空)。 (2) 当主存容量增加到4个页面时，两替换算法各自的命中率又是多少?,3.写操作策略,因为cache的内容是部分主存内容的副本，应该与主存内容保持一致。而CPU对cache的写入更改了cache内容，如何与主存内容保持一致就有几种写操作工作方式可供选择，统称为写策略。,1).写回法（write-bac

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

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

27、gh-with-Write-Allocate）； 另一种是不取主存块到cache, 称为WTNWA法（Write-Through-with NO-Write-Allocate）。,(3)优缺点： 写直达法是写cache与写主存同步进行， 优点：cache每行无需设置一个修改位以及相应的判测逻辑； 缺点：cache对CPU向主存的写操作无高速缓存功能，降低了cache的功效。80486处理器片内cache采用的就是写直达法。,三、cache存储器举例,以Intel 82385 cache控制器为例： Intel公司的82385Cache控制器，是专为80386设计的高性能32位外围支持芯片。它与

28、静态RAM(简称SRAM)芯片一起构成高速缓冲存储器。与80386微处理器相匹配的主存-cache存储系统是由82385 cache控制器来实现地址映像和变换的。可全部映像80386的32位地址提供的4G(千兆)字节的地址空间，使CPU几乎无任何等待地读出数据，命中率可高达99%。标志存储器和控制逻辑均在芯片内，使用82385可大大简化高速缓冲存储器子系统的设计。82385片内只含有cache控制器， 82385没有把数据存储器集成于一体，cache数据保存在片外的SRAM中。 82385提供了两种地址映像方式： 直接映像（r0）和两路组相联映像（r1）。,直接映像方式,图7.7 80386地

29、址总线字段分配(直接映像方式),图7.8 82385直接映像cache组织,Intel 80386的4GB地址空间被分成217页； 页的大小和Cache的容量相同，均为8K字 (32位) 或32K字节. Cache又分成1024组，每组8个字 (832位)。 每个字叫做一“行”，行是主存和Cache之间的信息传输单位（块）。 在82385 Cache目录表中，对应Cache的每一组有一个条目(目录项），它有26位。高17位为标记，中间一位为标记有效位，低8位为行有效位。17位标记指出主存的页号，标记217页中的某一页。, Cache由两部分组成：一部分存放由主存储器来的数据，称数据存储器。另一

30、部分存放该数据所在的主存储器的地址，故称地址标记存储器，或目录存储器。这两个存储器都为静态存储器。,直接映象方式： 主存各页中的第0组只能驻留在Cache的第0组，其余各组依次 类推。 目录表中的8位行有效位分别对应每组中的8行，如某一行被调入Cache中，则该行有效位置“1”，同时将标记有效位置“1” 。图中所示为主存第二页的第九行正驻留在Cache中，则第一组的对应表目中的标记位将记作1。由于第0组包含第07行，第1组包含第815行，所以，第1组对应表目中第2个行有效位被置“1”，说明第9行已驻留在Cache中。, 82385用A14A510位地址选择目录表中1024个表目中的一条，用A4

31、A2选择表目中8个行有效位中的一位。这13位Cache地址选择Cache中的一行 (4字节)。 82385将地址总线的标记字段（A31A15）与目录表表目中的标记进行比较，若二者相等，并且目录中的标记有效位和行有效位皆为“1”状态时，则读命中。 82385指示Cache将选中的字送入80386的数据总线。读命中不改变Cache和目录中的内容。,当80386启动读周期时：,(1) 行失效. 这时,目录表目中的标记和地址总线的标记字段相等,且标记有效位为“1”，但行有效位为“0”。 (2) 标记失效. 这时，目录表目中的标记和地址总线标记字段不相等，或是标记有效位为“0”。当失效发生时，80386

32、则直接访问主存取得数据，并同时将该内容写入Cache，并修改目录表。 若为行失效，则只将该行对应的行有效位置“1”； 若为标记失效，则用上述地址页号用来修改标记，并将标记有效位置“1”，并置“1”相应的行有效位，清除其它七个行有效位。,读失效可分为两种情况,两路组相联映像,图7.9 80386地址总线字段分配(两路组相联方式),图7.10 两路组相联cache组织,t+r (r=1),在两路组相联映象方式下：Cache被分成A和B两个体，每体为4K字。主存页面的大小和Cache的一个体的容量相同，其页数则比直接映象时增加一倍，共218页。 对应两个体的目录表也为A和B两部分，每个部分有27位,

33、 高18位标记主存页号, 中间1位作标记有效位，低8位作行有效位.目录表中的LRU位是附加位，用以指定A和B两个体中同一组的哪一行是近期最少使用行，即是被置换的对象。在两路组相联映象方式中，主存各页的同一组可以任意映象到Cache的两个体的同一组中。同时可有两个页的同一组存于Cache。当82385选中9位组字段中的某一个特定组时，就要对18位的标记进行比较，如果地址匹配，对特定的一路命中，则把标记的有效位置位，并且被选中的行也置位，82385允许对被选中的cache存储体进行数据的读出或写入。,Intel 82385还有监听功能： 现代计算机以存储器为中心，除了CPU访存以外，输入输出(I/

34、O)设备也可直接访问存储器，而cache中的数据又要与主存储器相应单元的内容保持一致(相同)，因此需要对地址进行监听。假如某一I/O设备直接向存储器传送数据(写入存储器)，而且其提供的地址中的数据在cache中有副本(即该地址与cache中相应单元的标记相符，且标记的有效位为“1”)，此时如不进行处理，会造成cache数据与存储器数据的不一致性。 为简化操作，通常采取将cache相应单元的标记有效位清“0”的办法，这样当CPU再访问(读)该单元时，将产生不命中信号，而到存储器去取数，这样可保证CPU所取数据的正确性。,图7.11 具有cache的计算机框图,图7.11是引入cache后的计算机

35、框图，CPU与cache之间通过内部高速总线传送地址、数据和控制信号，CPU通过cache与系统总线联系。当系统中存在多个CPU时，监听功能更显得必要。,四、多层次cache存储器,指令cache和数据cache指令和数据存放在同一cache中将指令cache和数据cache分开成为两个相互独立的cache。在给定cache总容量的情况下， 单一cache可以有较高的利用率。因为在执行不同程序时，cache中指令和数据所占的比例是不同的，在单一cache中，指令和数据的空间可以自动调剂。 采用将指令cache和数据cache分开的方案可以提高速度。,2. 多层次cache结构 （1）可将cac

36、he集成在快速微处理芯片内，片内cache的读取速度要比片外cache快得多，但容量低，命中率低。 （2）数据cache有两个端口，分别与两个ALU交换数据，每个端口传送32位数据，也可组合成64位数据，与浮点部件接口相连，传送浮点数。数据cache采取“写回”策略，即仅当cache中的数据要调出，且被修改过，才需要写回主存。 （3）指令cache只读不写，其控制比数据cache简单。 （4）二级cache方案：第一级cache(L1)在片内；第二级cache(L2)在片外，采用SRAM存储器，两级cache之间一般有专用总线相连。,3. cache的一致性问题 （1）数据cache存在cac

37、he一致性问题。（数据cache有写入操作，且有多种写入方案，为了提高计算机处理速度，在每次写入时，并不同时修改L1，L2和主存储器的内容，造成了数据的不一致 。 （2）指令cache不存在cache一致性问题（程序是不允许修改的）。,Pentium处理器支持“修改排它共享无效”协议(modified/exclusive/shared/invalid，简称MESI) 。它原是为多处理器系统的cache一致性设计的，但也适用于单处理机的二级cache系统。数据cache的每一行包含两个状态位，每一cache行处于4种状态之一 ： (1) 修改(Modified，简称M) 本cache行中的数据已

38、被修改(与主存的内容不同)，仅在本cache中的数据是正确的。 (2) 排它(Exclusive，简称E) 本cache行中的数据与主存中的数据相同，但不存在于其他cache中。 (3) 共享(Shared，简称S) 本cache行中的数据与主存中的数据相同，且可存在于其他cache中。 (4) 无效(Invalid，简称I) 本cache行中的数据无效。,当处理器加电或总清(reset)时，所有cache行都处于无效状态。当新数据写入无效行时，数据从主存取出，并同时存入L1和L2，此时cache行处于共享状态。 写入操作的一般过程： 当处理器发出写入数据到存储器的命令时，首先查询cache是

39、否命中，如命中，则根据cache行的状态进行相应的写入数据操作，并修改(或保留)原状态位。 L1和L2都设置有4种状态位，但处理方法不完全相同，情况比较复杂。,7.3 虚拟存储器,一、虚拟存储器概述 虚拟存储器指的是“主存辅存”层次，它能使计算机具有辅存的容量，接近于主存的速度和辅存的每位成本。使得程序员可以按比主存大得多的空间来编制程序，即按虚存空间编址。当然，主存实际容量的大小是会影响到系统的工作效率，如果程序过大而主存容量过小，则程序运行速度会明显下降。,1. 主存辅存层次与cache主存层次的比较,区别： 主存cache存储器的访问“时间比”较小；每次传送的基本信息单元(字块)也比较小

40、。 而辅存主存的访问“时间比”就要大得多，每次传送的基本信息单元(段或页面)也很大。 相似处（从原理角度看）： 地址变换及映像方法和替换策略从原理上看是相同的。虚拟存储系统所采取的映像方式同样有全相联映像、组相联映像和直接映像等，替换算法也多采用LRU算法。实际上，这些替换算法和地址映像方式最早应用于虚拟存储系统中，后来才发展到cache系统中。,2. 主存辅存层次信息传送单位和存储管理,主存辅存层次的信息传送单位可采用几种不同的方案： 段、页或段页。 段是利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立部分。段作为独立的逻辑单位可以被其他程序段调用，这样就形成段间连接，产生规模较

41、大的程序。一般用段表来指明各段在主存中的位置，如图7.12所示。每段都有它的名称(用户名称或数据结构名或段号)、段起点、段长等。段表本身也是主存储器的一个可再定位段。,主存按段分配的存储管理方式称为段式管理。其优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。,图7.12 段式管理,页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，称为页面。新页调入主存也很容易掌握，只要有空白页面就可。可能造成浪费的是程序最后一页的零头，它比段式管理系统的空间浪费要

42、小得多。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。,图7.13表示某个程序有5页(逻辑页号04)，各页分别装入主存不连续的页面位置，用页表记录逻辑页号及其所对应的实主存页号，页表是由操作系统建立的。图7.13中逻辑页号0，1，3已分配实主存空间，所以装入位为1。,图7.13 页式管理,段式和页式存储管理各有其优缺点，可以采用段和页结合的段页式存储管理系统。程序按模块分段，段内再分页，出入主存仍以页为信息传送单位，用段表和页表(每段一个页表)进行两级管理。,二、页式虚拟存储器,虚页（逻辑页）:虚拟空间分成的页。 实页（物理页）:

43、主存空间分成的页(同样大小)。 假设虚页号为0，1，2，m，实页号为0，1，l，显然有ml。虚地址 虚页号 页内地址,虚拟地址到主存实地址的变换是由页表来实现的。在页表中，对应每一个虚存页号有一个表目，表目内容至少要包含该虚页所在的主存页面地址(页面号)，用它作为实(主)存地址的高字段；与虚拟地址的字地址字段相拼接，就产生完整的实主存地址，据此访问主存。,图7.14 页式虚拟存储器结构,通常，在页表的表项中还包括装入位(有效位)、修改位、替换控制位及其他保护位等组成的控制字。如装入位为“1”，表示该虚页已从辅存调入主存；如装入位为“0”，则表示对应的虚页尚未调入主存，如访问该页就要产生页面失效

44、中断，启动输入输出子系统，根据外页表项目中查得的辅存地址，由磁盘等辅存中读出新的页到主存中来。修改位指出主存页面中的内容是否被修改过，替换时是否要写回辅存。替换控制位指出需替换的页等。,图7.15 使用快表和慢表实现虚实地址变换,快速存储器（存放页表的最活动部分）,另外，在一些影响工作速度的关键部分引入硬件支持（如采用按内容查找的相联存储器并行查找）,转换旁路缓冲器,注意：,虚页内容若没有调入主存，则计算机启动输入输出系统，把虚地址指示的一页内容从辅存调入主存，再提供CPU访问。虚地址和辅存地址不是一回事，程序员按虚存空间编址，虚地址由虚页号和页内地址组成，辅存实际地址以磁盘为例，地址由磁盘机

45、号、磁头号、柱面号、块号、块内地址组成，因此从辅存调页时还需要虚存地址空间到辅存地址的变换。这个变换也可以采用类似前述页表的方式。此表称为外页表。CPU访问主存页面失效时，调用外页表把程序的虚地址变换成辅存的实际地址，从辅存调出该虚页，而后根据页表指出实页号再把虚页内容调入主存。调入由地址变换机构实现。,3.加速地址变换的方法,(1) 把表的最活跃部分放在高速存储器组成快表； (2) 一些影响速度的关键部位引入硬件支持，如采用按内容查询的相联存储器。,使用快表方法 快表由硬件组成，比页表小得多，查表时，由逻辑页号同时去查快表和慢表，当在快表中有此逻辑页号时，就能很快地找到对应的物理页号送入实主

46、存地址寄存器，从而做到虽采用虚拟存储器但访主存速度几乎没有下降。,页式管理方案页式管理系统的信息传送单位是定长的页，主存的物理空间也被划分为等长的固定区域，称为页面。新页调人主存也很容易掌握，只要有空白页面就可。它比段式管理系统的空间浪费要小得多。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理保护和共享都不及段式来得方便。,例：一个有32位程序地址空间，页面容量为1KB，主存的容量为8MB的存储系统，问： (1) 虚页号字段有多少位？页表将有多少行？ (2) 页表的每一行有多少位？页表的容量有多少字节？,解： (1) 页表的长度为222 =4M行。 (2) 主存

47、的容量为8MB=223B，主存中页框架的数量有223 / 210 = 213个。页表中主存页号字段是13位长，加上其它信息将超过16位。设页表的每一项为16位，页表的容量为4M2 = 8MB。,例：一个虚拟存储器有8个页面，页面大小为1024字，内存有4个页面框架。页表的内容为： 虚页号 实页号 0 3 1 1 2 - 3 - 4 2 5 - 6 0 7 - 对应于虚拟地址4098的主存地址是什么？ 解：40981024 = 42，所以虚页号为4，页内地址为2。从表中查得实页号为2，实际地址为21024 + 2 = 2050。,三、段页式虚拟存储器,思想：程序按逻辑结构分段以后，再把每段分成固

48、定大小的页。 优点： (1)按段实现共享和保护，有段式系统的优点（段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享）。 (2) 程序对主存的调入调出是按页面进行的，有页式系统的优点(存储空间浪费小)。 缺点: 在地址映像过程中需要多次查表。 在这种系统中，虚拟地址转换成物理地址是通过一个段表和一组页表来进行定位的。段表中的每个表目对应一个段，每个表目有一个指向该段的页表的起始地址(页号)及该段的控制保护信息。由页表指明该段各页在主存中的位置以及是否已装入、已修改等标志。,如果有多个用户在机器上运行，称为多道程序，多道程序的每一道(每个用户)需要一

49、个基号(用户标志号)，可由它指明该道程序的段表起点(存放在基址寄存器中)。这样，虚拟地址应包括基号D、段号S、页号P、页内地址d。格式如下：基号D 段号S 页号P 页内地址d,举例说明段页式地址变换过程。如图7.16所示。,图7.16 段页式存储举例,当要访问的程序地址为D道1段0页4单元时，其地址变换过程如图7.17所示 。,图7.17 段页式虚拟存储器地址变换, 将段式管理和页式管理相结合，就构成了虚存的段页式管理。 它把程序按逻辑单位分段以后，再把每段分成固定大小的页。 程序对主存的调入调出是按页面进行的，但它又可以按段实 现共享和保护，兼备页式和段式的优点。所以目前大中型 机都采用这种虚拟存储器。,