计算机硬件技术及应用 第3章 存储器(2)

1、v掌握掌握cache的基本原理、地址映射、替换策略；的基本原理、地址映射、替换策略；v掌握虚拟存储器的基本概念以及段式、页式、段掌握虚拟存储器的基本概念以及段式、页式、段页式虚拟存储器的原理；页式虚拟存储器的原理；v了解只读存储器、闪速存储器的原理及存储保护了解只读存储器、闪速存储器的原理及存储保护的原理。的原理。v了解外存储设备的发展动态。了解外存储设备的发展动态。 教教 学学 要要 求求 衡量存储器有三个指标衡量存储器有三个指标:容量、速度和价格容量、速度和价格/位位. 单一的存储器很难同时满足三个指标单一的存储器很难同时满足三个指标. 因为存取时间越短因为存取时间越短,每位的价格就越高每

2、位的价格就越高;容量越大容量越大,每位的价格就越低每位的价格就越低;容量越大容量越大,存取时间就越长存取时间就越长. 存储系统实现：存储系统实现：l存储系统不是硬件的简单堆积，是硬软件相结合存储系统不是硬件的简单堆积，是硬软件相结合的方法连接而成的系统。的方法连接而成的系统。l这个系统对应用程序员透明。这个系统对应用程序员透明。l这个存储器的速度接近速度最快的那个存储器这个存储器的速度接近速度最快的那个存储器,l存储器容量与容量最大的那个存储器相等或接近存储器容量与容量最大的那个存储器相等或接近,l单位容量的价格接近最便宜的那个存储器单位容量的价格接近最便宜的那个存储器.u 内存主要是内存主要

3、是DRAM，价格低、容量大，但存取速度难以，价格低、容量大，但存取速度难以提高；而提高；而CPU速度提高很快。目前速度提高很快。目前CPU的速度比的速度比DRAM要要快一个数量级以上，导致两者速度不匹配。快一个数量级以上，导致两者速度不匹配。u只有双极型只有双极型TTL SRAM，存取速度与，存取速度与CPU处于同一量级，处于同一量级，但价格较贵，功耗很大，集成度低，所以不能将所有但价格较贵，功耗很大，集成度低，所以不能将所有DRAM都采用都采用SRAM。u折中的办法是分级处理，在主存和折中的办法是分级处理，在主存和CPU之间加一个容量之间加一个容量相对小的双极型相对小的双极型SRAM作为高速

4、缓冲存储器作为高速缓冲存储器Cache。u 目前目前Cache的分为一级的分为一级Cache、二级、二级Cache等。等。Cache的的命中率可达到命中率可达到90% - 98%，这样就大大提高了，这样就大大提高了CPU访问数据访问数据的速度。的速度。l时间局部性时间局部性:在一小段时间内，最近被访问过的程序和数在一小段时间内，最近被访问过的程序和数据很可能再次被访问；据很可能再次被访问；l空间局部性空间局部性: 这些最近被访问过的程序和数据，往往集这些最近被访问过的程序和数据，往往集中在一小片存储区域中；中在一小片存储区域中；l指令执行顺序方面指令执行顺序方面：指令顺序执行比转移执行的可能性

5、：指令顺序执行比转移执行的可能性要大（大约为要大（大约为5:1），因此，合理地把数据和程序放在不），因此，合理地把数据和程序放在不同的存储介质中。同的存储介质中。 这种对局部范围的存储器地址频繁访问，而对此范围这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为以外的地址则访问甚少的现象就称为关系关系CPUCPUCacheCache主存主存字传送字传送块传送块传送.主存主存块块Cache标记标记结构结构3.3.1 CACHE概述概述lCache和主存分和主存分同样大小的块同样大小的块；l主存中只有一小部分块的内容主存中只有一小部分块的内容 可放在可放在Cache中中.

6、l在在cache中每一块都有一个中每一块都有一个标记标记, 指明它是主存的哪一块的副本，指明它是主存的哪一块的副本， 该标记的内容相当于主存中块该标记的内容相当于主存中块 的编号，的编号，l设主存地址为设主存地址为n位，位， 且且n=m+b，则，则l主存的块数主存的块数M=2n/2b=2m ，l块内字节数块内字节数B=2b。 l cache地址码地址码=（c+b）位）位。lcache的块数为的块数为2c。 块内字节数与主存相同。块内字节数与主存相同。主存块号块内地址地址映象变换机构Cache块号块内地址C Ca ac ch he e主主存存C Ca ac ch he e替替换换策策略略主主存存

7、地地址址C Ca ac ca ah he e地地址址访访问问主主存存替替换换C Ca ac ch he e访访问问主主存存装装入入C Ca ac ch he e已已满满不不命命中中命命中中未未满满块块单单字字到到C CP PU U来来自自C CP PU U它由它由cache存储体、地址映像变换机构、存储体、地址映像变换机构、cache替换机构模块组成。替换机构模块组成。3.3.2 CACHE的工作原理的工作原理uCache容量容量u映射功能映射功能l直接映射直接映射l组相联映射组相联映射l全相联映射全相联映射u替换算法替换算法l最近最少使用（最近最少使用（LRU）l先进先出（先进先出（FIFO

8、）l最不经常使用（最不经常使用（LFU）l随机随机u写策略写策略l写通过写通过(write through)l回写回写(write back)u块大小块大小uCache数目数目l一级或二级一级或二级l统一或分离统一或分离3.3.2 CACHE的工作原理的工作原理。3.3.2 CACHE的工作原理的工作原理u增加增加cache的目的是在性能上使主存的平均读出时间尽可能的目的是在性能上使主存的平均读出时间尽可能接近接近cache的读出时间。因此的读出时间。因此cache的命中率应接近于的命中率应接近于1。u在一个程序执行期间命中率在一个程序执行期间命中率HcNc /(Nc+Nm) Nc表示表示Ca

9、che完成存取的总次数完成存取的总次数 Nm表示主存完成存取的总次数表示主存完成存取的总次数u设设Tc为为Cache的存取周期，的存取周期，Hc为为Cache的命中率，的命中率，Tm为主为主存的存取时间，则平均存取时间存的存取时间，则平均存取时间T为：为： THc *Tc + ( 1- Hc ) Tm u 追求的目标是：以较小的硬件代价使追求的目标是：以较小的硬件代价使cache/主存系统的平主存系统的平均均 访问时间访问时间T越接近越接近Tc越好。越好。ucache的命中率还与程序有关，不同程序命中率可能不同。的命中率还与程序有关，不同程序命中率可能不同。3.3.2 CACHE的工作原理的工

10、作原理3.3.3 cache存储器组织存储器组织u 主存的地址和主存的地址和cache地址间建立一种确定的逻辑关系，地址间建立一种确定的逻辑关系，必须应用某种函数把主存地址映像到必须应用某种函数把主存地址映像到cache，这样的逻辑，这样的逻辑关系称作关系称作。u在信息按照这种映像关系装入在信息按照这种映像关系装入cache后，执行程序时，后，执行程序时，将主存地址变换成将主存地址变换成cache地址，这个变换过程叫做地址，这个变换过程叫做。地址的映像和变换是密切相关的。地址的映像和变换是密切相关的。u地址映像方式：地址映像方式：u设主存储器空间被分为设主存储器空间被分为Mm(0), Mm(1

11、), , Mm (i), , Mm(2m1)，共，共2m块块,字块大小为字块大小为2b个字个字; u设设Cache存储空间被分为存储空间被分为Mc(0), Mc(1), , Mc(j), , Mc(2c1)，共，共2c个同样大小的块个同样大小的块. 3.3.3 cache存储器组织存储器组织 直接映像直接映像：一个主存块只能映像到：一个主存块只能映像到cache中的中的唯一唯一一一个指定块的地址映像方式。若这个位置已有内容，则产个指定块的地址映像方式。若这个位置已有内容，则产生块冲突，原来的块将无条件到被替换出去。生块冲突，原来的块将无条件到被替换出去。 直接相联是一种直接相联是一种最强的约束

12、关系最强的约束关系，它规定每个虚页，它规定每个虚页只对应唯一的实页。地址映像方法一般是将主存块地址只对应唯一的实页。地址映像方法一般是将主存块地址对对cache的块数取模得到的块数取模得到cache中的块地址，这相当于将中的块地址，这相当于将主存的空间按主存的空间按cache的尺寸分区，每区内相同的块号映像的尺寸分区，每区内相同的块号映像到到cache中相同的位置。中相同的位置。 在这种映像方式中，主存的第在这种映像方式中，主存的第0块，第块，第2c块，第块，第2c+1块，块，只能映像到，只能映像到cache的第的第0块，而主存的第块，而主存的第1块，第块，第2c+1块，第块，第2c+1+1块

13、，块，只能映像到，只能映像到cache的第的第1块。以块。以此类推。此类推。 3.3.3 cache存储器组织存储器组织字块字块0字块字块1字块字块2c-1字块字块0字块字块1字块字块2c-1标记标记标记标记标记标记字块字块2c+1-1字块字块2c字块字块2c+1主存字块主存字块标记标记cache字块地址字块地址块内地址块内地址t位位 c位位 b位位m位位主存地址主存地址比较器（比较器（t位）位） 有效位有效位=1主存储器主存储器命中命中 不命中不命中cache存储器存储器字块字块2c+1字块字块2c+1+1字块字块2m-11主存分为主存分为M个区，每个区有个区，每个区有2c个块，总共有个块，

14、总共有M 2c块，块，编号从编号从0到到M 2c -1。Cache有有2c个块。个块。第第0区区第第1区区第第M-1区区3.3.3 cache存储器组织存储器组织块块0 0块块1 1块块1515CacheCache标记标记标记标记标记标记块块0 0块块1 1块块20472047主存主存m m位位 块块字字0 0字字1 1字字511511 由于由于Cache的块数远小于主存的块数，因此一个的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的中，每一块外加有一个标记，指明它是主存的哪

15、一块的副本哪一块的副本(拷贝拷贝)。【例】【例】某机某机主存容量主存容量为为1MB1MB, ,划分为划分为20482048块块, ,每块每块512B;512B;CacheCache容量容量为为8KB8KB, ,划分为划分为1616块块, ,每块每块512B512B。3.3.3 cache存储器组织存储器组织 这是一种多对一的映射关系，但一个这是一种多对一的映射关系，但一个主存块只能映象主存块只能映象到到Cache的一个特定块位置上去。的一个特定块位置上去。 Cache的第的第i块块和和主存的第主存的第j块块有如下函数关系：有如下函数关系： i = j mod m ( m为为Cache的总块数）

16、的总块数） i =0,1,2,m-1 j=0,1,2,n-1在这种映象方式中：在这种映象方式中：主存的第主存的第0 0块，第块，第1616块，第块，第3232块，块，只能映象到，只能映象到CacheCache的的第第0 0块；块；而主存的第而主存的第1 1块，第块，第1717块，第块，第3333块，块，只能映象到，只能映象到CacheCache的第的第1 1块；块；3.3.3 cache存储器组织存储器组织直接映像方式直接映像方式 Cache Cache地址地址C Ca ac ch he e块块号号块块内内地地址址4位位 9 位位主存地址主存地址块块内内地地址址C Ca ac ch he e块

17、块号号主主存存标标记记（组组号号）7位位 4位位 9 位位主主存存块块号号块块内内地地址址11位位 9 位位主存地址主存地址块块 0块块 1块块 15CacheCache标记标记标记标记标记标记标记标记标记标记标记标记.0 0 组组块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存TagTag1 1 组组127127组组7位位3.3.3 cache存储器组织存储器组织 主存地址分成三段主存地址分成三段：区号、块号和块内地址。：区号、块号和块内地址。 区号区号( (组号组号) )作为标志存放在地址映象表中，用于判作为标志存放在地址映象表中，用于判断命中与否。断命中与否。

18、块号块号直接用于查地址映象表直接用于查地址映象表; ; 块内地址块内地址用于块内寻址。用于块内寻址。 在访存操作时，根据主存地址中的块号读出块在访存操作时，根据主存地址中的块号读出块表中的区号，并与当前地址的区号进行比较，结果表中的区号，并与当前地址的区号进行比较，结果相同表相同表cachecache命中，访问可对命中，访问可对cache cache 进行；不相同则进行；不相同则表示不命中，访问需对主存进行。表示不命中，访问需对主存进行。3.3.3cache存储器组织存储器组织.0 0 组组块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存1 1 组组127127组组块

19、内地址块内地址Cache块号Cache块号主存标记（组号）主存标记（组号）标记标记标记标记标记标记标记标记标记标记标记标记块块 0块块 1块块 15有效位有效位有效位有效位: :有效位有效位7位 4位 9位7位 4位 9位比较比较命中命中数据数据主存地址主存地址不命中不命中比较相等且有效位相等比较相等且有效位相等3.3.3 cache存储器组织存储器组织 有效位有效位: 为了说明标记是否有效为了说明标记是否有效. 当机器刚加电时当机器刚加电时, Reset信号将所有标记的有效位置信号将所有标记的有效位置“0”,使标记无效。使标记无效。在程序执行的过程中在程序执行的过程中,当当Cache不命中时

20、逐步将指令块不命中时逐步将指令块或数据块从主存调入或数据块从主存调入Cache中的某一块中的某一块,并将这一块标记并将这一块标记中的有效位置中的有效位置“1”.刚加电后所有标记位都为刚加电后所有标记位都为“0”，因此开始执行程序时，因此开始执行程序时，命中率较低。命中率较低。3.3.4 替换算法和更新策略替换算法和更新策略CPU送来的主存地址和读写命令后，只需根据中送来的主存地址和读写命令后，只需根据中间间c位字段位字段找到找到cache存储器字块，然后存储器字块，然后,看其标记是否看其标记是否与与主存地址高主存地址高t位位符合符合: 如果如果符合且有效位为符合且有效位为“1”，则可根据，则可

21、根据b位块内地址，位块内地址，从从cache中取得所需指令或数据；中取得所需指令或数据； 如果如果不符合或有效位为不符合或有效位为“0”，就从主存读入新的字，就从主存读入新的字块来替换旧的字块，并将块来替换旧的字块，并将CPU所需数据送往所需数据送往CPU，同，同时修改时修改cache标记。假如原来有效位为标记。假如原来有效位为“0”，还要将有，还要将有效位改置成效位改置成“1”。 直接映像方式的缺点是不够灵活，即主存的直接映像方式的缺点是不够灵活，即主存的2t个字块个字块只能对应惟一的只能对应惟一的cache存储器字块，因此，即使存储器字块，因此，即使cache存存储器别的许多地址空着也不能

22、占用。这使得储器别的许多地址空着也不能占用。这使得cache存储存储空间得不到充分利用，并降低了命中率。空间得不到充分利用，并降低了命中率。3.3.3 cache存储器组织存储器组织优点优点: :硬件硬件实现简单，只需利用主存地址按某些字段直接判实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在断，即可确定所需字块是否已在Cache中。中。成本低成本低 缺点：缺点： 不够灵活，主存的多个字块只能对应唯一的不够灵活，主存的多个字块只能对应唯一的Cache字块，字块，块冲突率很高，块冲突率很高，降低了命中率。降低了命中率。3.3.3 cache存储器组织存储器组织【例【例1】设

23、一个】设一个cache的容量为的容量为2KB，每个块为，每个块为16B，求：，求： 该该cache可容纳多少个块？可容纳多少个块？ 如果主存容量是如果主存容量是256KB，则主存有多少个块？，则主存有多少个块？ 主存的地址有多少位？主存的地址有多少位？ cache地址有多少位？地址有多少位？ 进行地址映象时，存储器的地址分成哪几段？各段分进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？别有多少位？【解】【解】 cache中有中有2048/16=128个块个块 主存有主存有256K/16=16384个块个块 主存容量为主存容量为256KB=218字节，字节， 主存字节地址有主存字节地址

24、有18位。位。 cache容量为容量为2KB=211字节，字节，cache的字节地址为的字节地址为11位。位。存储器的字地址分三段：区号、块号、块内字地址。存储器的字地址分三段：区号、块号、块内字地址。 区号的长度为区号的长度为18-11=7位，位，块号为块号为7位。块内字地址为位。块内字地址为4位。位。 全相联映像全相联映像是指主存中的任何一个字（字块）均是指主存中的任何一个字（字块）均可以映像到可以映像到CACHECACHE中的任何一个字（字块）的位置上，中的任何一个字（字块）的位置上，也允许从确实已被占满的也允许从确实已被占满的cachecache存储器中替换出任何一存储器中替换出任何一

25、个旧字块。个旧字块。 反过来说，反过来说，CACHECACHE的一个字（字块）中，在不同时的一个字（字块）中，在不同时刻可能存放的是整个主存中的任何一个字（字块）中刻可能存放的是整个主存中的任何一个字（字块）中的内容，即二者的对应关系是完全随意的，没有任何的内容，即二者的对应关系是完全随意的，没有任何强制性的限制条件。强制性的限制条件。 全相联映像方式是全相联映像方式是最灵活但成本最高最灵活但成本最高的一种方式。的一种方式。3.3.3 cache存储器组织存储器组织块块 0块块 1块块 15CacheCache标记标记标记标记标记标记标记标记标记标记标记标记.块块0块块1块块 15块块 16块

26、块 17块块 31块块 2047主存主存TagTagC Ca ac ch he e块块号号块块内内地地址址Cache地址地址4 4位位 9 9 位位主主存存块块号号块块内内地地址址1111位位 9 9 位位主存地址主存地址11位位 允许主存中的每一个字块映象到允许主存中的每一个字块映象到CacheCache的任何一个字块位置上的任何一个字块位置上 最灵活但成本最高的一种方式。最灵活但成本最高的一种方式。3.3.3 cache存储器组织存储器组织字块字块0字块字块1字块字块i字块字块0字块字块1字块字块2c-1标记标记标记标记标记标记字块字块2m-1主存字块主存字块标记标记块内地址块内地址m=t

27、+c位位 b位位主存地址主存地址比较器（比较器（m位）位） 有效位有效位=1主存储器主存储器命中命中 不命中不命中cache存储器存储器m=t+c所有标记所有标记3.3.3 cache存储器组织存储器组织.块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存标记标记标记标记标记标记标记标记标记标记标记标记块块 0块块 1块块 15有效位有效位有效位有效位: :有效位有效位11位 9位11位 9位比较所有的标记比较所有的标记命中命中数据数据主存地址主存地址不命中不命中主存块号主存块号块内地址块内地址3.3.3 cache存储器组织存储器组织1.1.对对CACHECACHE的

28、使用可以有最大的灵活性。的使用可以有最大的灵活性。l 只要只要CACHECACHE中有空闲的单元，可确保进行写操作。中有空闲的单元，可确保进行写操作。l 当当CACHECACHE已满，要写入时可以方便地选择一个已满，要写入时可以方便地选择一个CACHECACHE单元单元进行腾空。进行腾空。2.Cache2.Cache的块冲突概率最低，空间利用率最高，地址变换速的块冲突概率最低，空间利用率最高，地址变换速度慢度慢. .3.3.比较操作的电路过多、过于复杂，实现成本高难以实现。比较操作的电路过多、过于复杂，实现成本高难以实现。 CACHECACHE读写操作时，用原本读主存的整个（或部分）地址读写操

29、作时，用原本读主存的整个（或部分）地址去与去与CACHECACHE的标志字段的内容实现比较时，必须与整个的标志字段的内容实现比较时，必须与整个CACHECACHE中每一个单元的标志字段都比较，才能知道要读的信息是否中每一个单元的标志字段都比较，才能知道要读的信息是否已在已在CACHECACHE中。中。4.4.使用条件：由于仅在使用条件：由于仅在CACHECACHE容量很小时方可选用。容量很小时方可选用。3.3.3 cache存储器组织存储器组织 组相联映像将主存空间按组相联映像将主存空间按cache大小等分成区后，再大小等分成区后，再将将cache空间和主存空间中的每一区都等分成大小相等的空间

30、和主存空间中的每一区都等分成大小相等的组。让主存各区中某组中的任何一块，均可直接映像装入组。让主存各区中某组中的任何一块，均可直接映像装入cache中对应的任何一块位置上。中对应的任何一块位置上。 组相联映像方式是直接映像和全相联映像方式的一种组相联映像方式是直接映像和全相联映像方式的一种折衷方案。折衷方案。 特点：特点： 1. 组相联映像方式的性能与复杂性介于直接映像与全相组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。联映像两种方式之间。 2.组相联映像方式的优缺点介于直接映像与全相联映像两组相联映像方式的优缺点介于直接映像与全相联映像两种方式之间。种方式之间。 3. c

31、ache的命中率除了与地址映像的方式有关外，还与的命中率除了与地址映像的方式有关外，还与cache的容量有关。的容量有关。cache容量大，命中率高，但达到一容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。定容量后，命中率的提高就不明显了。3.3.3 cache存储器组织存储器组织块块 0块块 1块块CacheCache标记标记标记标记标记标记标记标记标记标记标记标记.块块0块块1块块 7块块 8块块 9块块 2032块块 2039主存主存TagTag254组块块 0块块 1块块7标记标记标记标记标记标记标记标记标记标记标记标记标记标记70组1组块块 2033块块 15.块块 20

32、47块块 2046.块块 2040255组0组1组8位位 3位位 9 位位主存组号块号块内地址8位位1位位 3位位 9 位位Cache组号块号块内地址注意：当只有一个组并且每组注意：当只有一个组并且每组1616块时，此时为直接映像；块时，此时为直接映像； 当有当有1616组并且每组一个块时组并且每组一个块时, ,则为全相联映像。则为全相联映像。3.3.3 cache存储器组织存储器组织 设主存为设主存为1MB=220 Cache 为为8KB=213 块长为块长为0.5KB=29 块数块数=8KB/0.5KB=16 Cache为二路组相联为二路组相联 组数组数=块数块数/路数路数=16/2=8注

33、注: 块号是组内块号的缩称块号是组内块号的缩称 组号是组号是Cache内组号的缩称内组号的缩称组组组组第第0区区第第1区区第第127区区块块块块 Cache Cache与主存均分组与主存均分组, ,主存中一个组内的块数与主存中一个组内的块数与Cache Cache 的分组数相同的分组数相同, ,主存中的各块与主存中的各块与CacheCache的组号有固定的映象像关系的组号有固定的映象像关系, ,但可自由映像到对应的但可自由映像到对应的CacheCache组中任一块组中任一块. .注意：注意：当只有一个组并且每组当只有一个组并且每组1616块时，此时为全相联映像；块时，此时为全相联映像； 当有当

34、有1616组并且每组一个块时组并且每组一个块时, ,则为直接映像。则为直接映像。 1位位 1位位 9 位位Cache组号组号块号块号块内地址块内地址区号区号6位位 1位位 1位位 9 位位 组号组号块号块号块内地址块内地址主存主存块块 0块块 1块块CacheCache标记标记标记标记标记标记标记标记标记标记标记标记0 0组组块块0块块1块块 3块块 4块块 127TagTag标记标记块块230 0组组1 1组组块块 21 1组组块块 5块块 6块块 7.0 0组组1 1组组块块 124块块 125块块 1261 1组组0 0组组0 0区区1 1区区6363区区.3.3.3 cache存储器组

35、织存储器组织 目前微机中目前微机中CacheCache一般装在主板上，在一般装在主板上，在Intel 486 CPUIntel 486 CPU中集成中集成了了8KB8KB的数据和指令共用的的数据和指令共用的CacheCache；在；在Pentium CPUPentium CPU中集成了中集成了8KB8KB的的数据数据CacheCache和和8KB8KB的指令的指令CacheCache，与主板上的，与主板上的CacheCache形成两级形成两级CacheCache结构。结构。 当当CPU发出读请求时，将主存地址发出读请求时，将主存地址m位（或位（或m位中的一部分）位中的一部分）与与cache某块

36、的标记相比较，根据其比较结果是否相等而区分出某块的标记相比较，根据其比较结果是否相等而区分出两种情况：两种情况： 当比较结果相等时，说明需要的数已在当比较结果相等时，说明需要的数已在cache中，那么直接中，那么直接访问访问cache就行了，在就行了，在CPU与与cache之间，通常一次传送一个字；之间，通常一次传送一个字；这种情况称为这种情况称为访问访问cache命中命中。 当比较结果不相等时，说明需要的数据尚未调入当比较结果不相等时，说明需要的数据尚未调入cache，那，那么就要把该数据所在的整个字块从主存一次调进来。这种情况称么就要把该数据所在的整个字块从主存一次调进来。这种情况称为为访

37、问访问cache不命中不命中。 3.3.4 替换算法和更新策略替换算法和更新策略开始开始结束结束N NY Y3.3.4 替换算法和更新策略替换算法和更新策略 3.3.4 替换算法和更新策略替换算法和更新策略3.3.4 替换算法和更新策略替换算法和更新策略 当一个新的主存块要调入到当一个新的主存块要调入到cache，而允许存放此块，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为的行位置都被其它主存块占满时，就要产生替换，因为cache工作原理要求它应尽量保存最新的数据。工作原理要求它应尽量保存最新的数据。 替换问题与替换问题与cache的组织方式紧密相关的组织方式紧密相关(1)对

38、于采用对于采用直接映射方式直接映射方式的的cache来说：来说： 因一个主存块只有一个特定的行位置可存放，所以问因一个主存块只有一个特定的行位置可存放，所以问题解决很简单，把此特定行位置上的原主存块妥善处理题解决很简单，把此特定行位置上的原主存块妥善处理后，换出后，换出Cache即可。即可。(2)对于对于全相联全相联的的cache来说，它的全部行都是可被替换来说，它的全部行都是可被替换的特定行；而的特定行；而组相联组相联的的cache中同组各路的行都是可被中同组各路的行都是可被替换的特定行：替换的特定行： 这样就要从允许存放新主存块的若干这样就要从允许存放新主存块的若干特定行中选取一行换出。特

39、定行中选取一行换出。3.3.4 替换算法和更新策略替换算法和更新策略（1）先进先出（）先进先出（FIFO）算法）算法 FIFO算法总是把一组中最先调入算法总是把一组中最先调入cache存储器的字块存储器的字块替换出去，它不需要随时记录替换出去，它不需要随时记录各各个字块的使用情况，个字块的使用情况， FIFO算法实现容易，开销小；可能会把一些需要经算法实现容易，开销小；可能会把一些需要经常使用的程序块替换掉。常使用的程序块替换掉。（2）近期最少使用（）近期最少使用（LRU）算法。）算法。 LRU算法是把一组中近期最少使用的字块替换出去。算法是把一组中近期最少使用的字块替换出去。需要纪录需要纪录

40、cache中每个字块的情况，来确定哪个字块是中每个字块的情况，来确定哪个字块是近期最少使用的。近期最少使用的。 LRU算法的命中率要比算法的命中率要比FIFO算法高，但实现比较复算法高，但实现比较复杂，系统开销大。杂，系统开销大。3.3.4 替换算法和更新策略替换算法和更新策略（3）随机替换）随机替换 随机替换（随机替换（Random Replacement）从特定的行位）从特定的行位置中随机地选取一行换出即可。置中随机地选取一行换出即可。 这种策略以硬件实现最容易，而且速度也比前两种策这种策略以硬件实现最容易，而且速度也比前两种策略快。略快。 缺点缺点:是随意换出的数据很可能马上又要用，从而

41、增是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和加了映射次数，降低了命中率和cache 的工作效率。但的工作效率。但这个缺点可以用增大这个缺点可以用增大cache的容量来克服，实验统计表明，的容量来克服，实验统计表明，随机替换策略的功效只是稍逊于前两种策略。随机替换策略的功效只是稍逊于前两种策略。3.3 高速缓冲存储器高速缓冲存储器3 3.4 .4 虚拟存储器虚拟存储器 3 3.4.1 .4.1 虚拟存储器概述虚拟存储器概述 虚拟存储器是指用磁盘一片存储空间来弥补主存空虚拟存储器是指用磁盘一片存储空间来弥补主存空间的不足，使得程序人员能够使用比主存实际容量更大间的不足，使

42、得程序人员能够使用比主存实际容量更大的存储空间来编写和运行程序。的存储空间来编写和运行程序。 虚拟存储器指的是虚拟存储器指的是“主存一辅存主存一辅存”层次层次， 它能使计算机具有：它能使计算机具有：辅存的容量；辅存的容量；接近于主存的速度；接近于主存的速度；辅存的每位成本。辅存的每位成本。使得程序员可以按比主存大得多的空间来编制程序，使得程序员可以按比主存大得多的空间来编制程序，即按虚存空间编址。即按虚存空间编址。在操作系统和相应硬件的支持下，数据在磁盘和主存在操作系统和相应硬件的支持下，数据在磁盘和主存之间按程序运行的需要自动成批量地完成交换。之间按程序运行的需要自动成批量地完成交换。 实现

43、原理相似。实现原理相似。 它们采用的地址变换及映像方法和替换策略，从它们采用的地址变换及映像方法和替换策略，从原理上看是相同的。实际上，这些替换算法和地址映原理上看是相同的。实际上，这些替换算法和地址映像方式最早应用于虚拟存储系统中，后来才发展到像方式最早应用于虚拟存储系统中，后来才发展到cachecache系统中。系统中。主存主存/cache/cache存储器的存储器的访问访问“时间比时间比”较小，典型的较小，典型的为为10:110:1；每次传送的基本信息单元（字块）也比较小，；每次传送的基本信息单元（字块）也比较小，只是几个至几十个字节。只是几个至几十个字节。而辅存而辅存/ /主存的主存的

44、访问访问“时间比时间比”就要大得多，达就要大得多，达100:1100:1至至1000:11000:1，每次传送的基本信息单元（段或页面），每次传送的基本信息单元（段或页面）也很大，达几十至几千字节也很大，达几十至几千字节。 3.4 虚拟存储器虚拟存储器3.4 虚拟存储器虚拟存储器 希望能得到辅存的价格，而得到主存储器的速度。希望能得到辅存的价格，而得到主存储器的速度。 将用户的地址空间设计的可以比主存实际空间大得多，以致将用户的地址空间设计的可以比主存实际空间大得多，以致可以存得下整个程序。可以存得下整个程序。指令地址码称为指令地址码称为虚地址（虚存地址、虚拟地址）或逻辑地址虚地址（虚存地址、

45、虚拟地址）或逻辑地址，其对应的存储容量称为其对应的存储容量称为虚存容量或虚存空间虚存容量或虚存空间；实际主存的地址称为实际主存的地址称为物理地址或实（存）地址物理地址或实（存）地址，其对应的存储，其对应的存储容量称为容量称为主存容量、实存容量或实（主）存空间。主存容量、实存容量或实（主）存空间。当当CPUCPU用虚地址访问主存时用虚地址访问主存时, ,机器自动地把它经辅助软件机器自动地把它经辅助软件, ,硬件硬件变换成主存实地址变换成主存实地址. .查查看这个地址所对应的单元内容是否已经装看这个地址所对应的单元内容是否已经装入主存入主存, ,如果在主存就进行访问如果在主存就进行访问, ,如果不

46、在主存内就经辅助软件硬件把如果不在主存内就经辅助软件硬件把它所在的那块程序和数据由辅存调入主存它所在的那块程序和数据由辅存调入主存, ,而后进行访问而后进行访问. .这些这些操作不必由程序员安排操作不必由程序员安排, ,也就是说也就是说, ,对应用程序员是透明的对应用程序员是透明的. .这就形成了主这就形成了主-辅层次满足了存储器大容量和低成本需求。辅层次满足了存储器大容量和低成本需求。 虚存通过增设虚存通过增设地址映象表地址映象表机构来实现程序在主存中的机构来实现程序在主存中的定位定位。这种定位技术是把程序分割成若干个较小的段或页，用相应这种定位技术是把程序分割成若干个较小的段或页，用相应的

47、映象表机构，来指明该程序的某段或某页是否已装入主存，的映象表机构，来指明该程序的某段或某页是否已装入主存，若已装入主存，则应同时指明其在主存中所处的开始位置；若已装入主存，则应同时指明其在主存中所处的开始位置；若未装入主存，则应到辅存中去调段或页，并建立起程序空若未装入主存，则应到辅存中去调段或页，并建立起程序空间和实存空间的地址映象关系。间和实存空间的地址映象关系。程序执行时通过查映象表，将程序程序执行时通过查映象表，将程序(虚虚)地址变成主存地址再地址变成主存地址再访问主存。访问主存。 由于采用的存储映象算法不同，形成了多种不同的存储器管由于采用的存储映象算法不同，形成了多种不同的存储器管

48、理方式的虚拟存储器，其中主要有理方式的虚拟存储器，其中主要有段式段式、页式页式、段页式段页式三种。三种。3.4 虚拟存储器虚拟存储器主存主存辅存层次的信息传送单位可采用：段、页或段页。辅存层次的信息传送单位可采用：段、页或段页。 段：段：是利用程序的模块化性质，按照程序的逻辑结构划分成的是利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立部分。多个相对独立部分。 段间连接：段间连接：段作为独立的逻辑单位可以被其他程序段调用，这段作为独立的逻辑单位可以被其他程序段调用，这样就形成段间连接，产生规模较大的程序。样就形成段间连接，产生规模较大的程序。 段表：段表：来指明各段在主存中的位置。

49、段都有它的名称、段起点、来指明各段在主存中的位置。段都有它的名称、段起点、段长等。段长等。 段式管理：段式管理：把主存按段分配的存储管理方式。把主存按段分配的存储管理方式。 段式管理系统的特点段式管理系统的特点：段的分界与段的分界与程程序的自然分界相对应；序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护段的逻辑独立性使它易于编译、管理、修改和保护；也便于多道也便于多道程序共享程序共享. .容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。3.4 虚拟存储器虚拟存储器主存和辅存的管理按程序段为单位进行管理。主存和辅存的

50、管理按程序段为单位进行管理。3.4 虚拟存储器虚拟存储器段表长度段表长度段表起始地址段表起始地址位移量位移量100段号段号2 越界越界920020038000500240006001600010000基址基址段长段长段号段号+8100主存主存段表段表虚地址虚地址物理地址物理地址3.4 虚拟存储器虚拟存储器定长的页定长的页: :页式管理系统的信息传送单位页式管理系统的信息传送单位。页面：页面：主存的物理空间被划分为等长的固定域。它主存的物理空间被划分为等长的固定域。它比段式管理系统的空间浪费要小得多。比段式管理系统的空间浪费要小得多。页式管理系统的缺点：页式管理系统的缺点：由于页不是逻辑上独立的

51、实由于页不是逻辑上独立的实体，处理、保护共享都不及段式方便。体，处理、保护共享都不及段式方便。存储管理方式存储管理方式：采用段和页结合的段页式存储管理系统；采用段和页结合的段页式存储管理系统；程序间按模块分段，段内再分页；程序间按模块分段，段内再分页；出入主存仍以页为信息传送单位；出入主存仍以页为信息传送单位；用段表和页表（每段一个页表）进行两级管理。用段表和页表（每段一个页表）进行两级管理。3.4 虚拟存储器虚拟存储器程序逻辑空间程序逻辑空间位位入入装装存存主号主号实页实页辑号辑号逻页逻页页表页表逻辑逻辑页号页号01234实主存空间实主存空间物理物理页号页号01234某个程序有某个程序有5

52、5页页( (逻辑页号逻辑页号0-4),0-4),各页分别在主存不连续的页面位置；各页分别在主存不连续的页面位置；用页表记录逻辑页号及其所对应的实主存页号用页表记录逻辑页号及其所对应的实主存页号, ,页表是由操作系统建立的；页表是由操作系统建立的；图中页号图中页号0, 1, 30, 1, 3已分配实主存空间已分配实主存空间, ,所以装入位为所以装入位为“1”.1”.3.4 虚拟存储器虚拟存储器3 3.4.2.4.2 页式虚拟存储器页式虚拟存储器在页式虚拟存储系统中，把虚拟空间分成页，在页式虚拟存储系统中，把虚拟空间分成页，虚页或虚页或逻辑页逻辑页。主存空间也分成同样大小的页，称为主存空间也分成同

53、样大小的页，称为实页或物理页实页或物理页。页式虚拟存储器页式虚拟存储器：以页为基本单位的虚拟存储器：以页为基本单位的虚拟存储器页的起点都落在低位字段为零的地址上。页的起点都落在低位字段为零的地址上。虚拟地址分为两个字段虚拟地址分为两个字段，高位字段为虚页号，低位字，高位字段为虚页号，低位字段为页内字地址。段为页内字地址。虚拟地址到主存实地址的变换是由虚拟地址到主存实地址的变换是由页表页表来实现的来实现的. .页表页表：是一张存放在主存中的虚存页号和号相对照的：是一张存放在主存中的虚存页号和号相对照的表。记录着从程序的虚页调入主存时被安排在主存中的表。记录着从程序的虚页调入主存时被安排在主存中的

54、位置。位置。 页式虚拟存储器页式虚拟存储器的主存和虚拟空间划的主存和虚拟空间划分成分成大小相等大小相等的页，的页，虚拟空间的页数要比虚拟空间的页数要比主存空间的页数多很主存空间的页数多很多。多。(1) 页页00000 0000000000 1111100000 0000000001 1111100000 0000000010 1111111111 0000011111 11111高位高位(5位位) 低位低位(11位位)实地址实地址主存空间主存空间实页号实页号 页内地址页内地址2K2K2K2K2页页31页页0页页1页页3.4 虚拟存储器虚拟存储器 CPU访问主存时送出的是程序的虚地址，计算机访问

55、主存时送出的是程序的虚地址，计算机必须判断出该地址的存储地址是否已在主存中：如果必须判断出该地址的存储地址是否已在主存中：如果在的话，找出在主存哪一页；如果不在的话，需要将在的话，找出在主存哪一页；如果不在的话，需要将所在页的内容调入指定的主存页后才能被所在页的内容调入指定的主存页后才能被CPU执行。执行。 为此，需要建立一张虚地址页号与实地址页号对照为此，需要建立一张虚地址页号与实地址页号对照表，用以记录程序的虚页面调入主存时被安排在主存表，用以记录程序的虚页面调入主存时被安排在主存的位置。这张表叫的位置。这张表叫页表页表。 页表是存储管理软件根据主存运行情况自动建立的，页表是存储管理软件根

56、据主存运行情况自动建立的，内存中有固定区域存放页表。每个程序都有一张页表。内存中有固定区域存放页表。每个程序都有一张页表。 页表的长度等于该程序虚页数。页表的长度等于该程序虚页数。6.4 虚拟存储器虚拟存储器页表信息字页表信息字3.4 虚拟存储器虚拟存储器页内地址页内地址页内地址页内地址实页号实页号虚页号虚页号 2 1 3 1(b) 地址变换方法地址变换方法主存页号主存页号 装入位装入位 - 0 7 1 - 0 页表基址页表基址虚地址虚地址实地址实地址页表页表页基址寄存器页基址寄存器6.4 虚拟存储器虚拟存储器虚实地址变换是由存储管理软件自动完成的。虚实地址变换是由存储管理软件自动完成的。(来

57、自来自CPU)页表基地址页表基地址页表基址寄存器页表基址寄存器虚地址虚地址控制字控制字 主存页面号主存页面号实存地址实存地址页表页表（在主存中）（在主存中）3.4 虚拟存储器虚拟存储器 假设页表也是保存在（或已调入）主存储器中，在访问存储器时，假设页表也是保存在（或已调入）主存储器中，在访问存储器时，首先要访问页表，即使命中，页是在访问页表之后，首先要访问页表，即使命中，页是在访问页表之后，再再次访问存储次访问存储器才能取得数据，所以至少要访问器才能取得数据，所以至少要访问2次存储器。如果不命中，还需次存储器。如果不命中，还需要页面替换和修改，访问存储器次数更多。要页面替换和修改，访问存储器次

58、数更多。 快表：快表：为了减少多次访问主存带来的开销，可采用为了减少多次访问主存带来的开销，可采用cache技术将技术将页表中最活动部分存放在快速存储器页表中最活动部分存放在快速存储器cache中。中。 快表由硬件组成，通常称为转换旁路缓冲器（快表由硬件组成，通常称为转换旁路缓冲器（TLB），快表是慢），快表是慢表（主存中的页标）的一部分的副本。表（主存中的页标）的一部分的副本。 查表时，同时查快表和慢表。查表时，同时查快表和慢表。v如果如果TLB命中，慢表查询结果作废。命中，慢表查询结果作废。v如果如果TLB不命中，就要访问主存查慢表，取出不命中，就要访问主存查慢表，取出送实主存地送实主存地

59、址寄存器，并送快表，用替换算法替换快表中的一项。址寄存器，并送快表，用替换算法替换快表中的一项。 页式虚拟存储器页式虚拟存储器3.4 虚拟存储器虚拟存储器虚地址虚地址快表（快表（TLB表）表）16行行64行行（硬件构成）（硬件构成）实存地址实存地址相连比较相连比较（按内容访问）（按内容访问）（按地址访问）（按地址访问）（快表中查不到）（快表中查不到）（快表中查到）（快表中查到）慢表慢表（在主存中）（在主存中）3.4 虚拟存储器虚拟存储器3.4.3 段页式虚拟存储器 把程序按逻辑结构分段，再将每段分成固定大小的页。程序对把程序按逻辑结构分段，再将每段分成固定大小的页。程序对主存的调入调出是按页面进行的。而段又可以实现共享和保护。主存的调入调出是按页面进行的。而段又可以实现共享和保护。 多道程序中，每道程序有一张段表和若干页表。多道程序中，每道程序有一张段表和若干页表。 纪录程序的分段信息（分几段就有几个段表项），段表中纪录程序的分段信息（分几段就有几个段表