第6章存储系统

存储系统第

6

章6.1存储系统层次结构6.2高速缓冲存储器6.3.1Cache概述6.3.2Cache的工作原理6.3.3Cache的组织方式6.3.4替换算法和更新策略

6.3虚拟存储器6.4.1虚拟存储器概述6.4.2段式虚拟存储器6.4.3页式虚拟存储器6.4.4段页式虚拟存储器6.4.5快表与慢表掌握cache的基本原理、地址映射、替换策略；掌握虚拟存储器的基本概念以及段式、页式、段页式虚拟存储器的原理；了解只读存储器、闪速存储器的原理及存储保护的原理。了解外存储设备的发展动态。

教学要求第6.1节存储系统的层次结构存储系统的层次结构衡量存储器有三个指标:容量、速度和价格/位.单一的存储器很难同时满足三个指标.

因为存取时间越短,每位的价格就越高;容量越大,每位的价格就越低;容量越大,存取时间就越长.存储系统实现：存储系统不是硬件的简单堆积，是硬软件相结合的方法连接而成的系统。这个系统对应用程序员透明。这个存储器的速度接近速度最快的那个存储器,存储器容量与容量最大的那个存储器相等或接近,单位容量的价格接近最便宜的那个存储器.存储系统的层次结构主板内存储器寄存器Cache主存储器主板外存储器磁盘CD-ROMCD-RWDVD-RWDVD-RAM离线存储器磁带MO(光－磁盘)WORM(一写多读光盘)第6.2节Cache高速缓冲存储器内存主要是DRAM，价格低、容量大，但存取速度难以提高；而CPU速度提高很快。目前CPU的速度比DRAM要快一个数量级以上，导致两者速度不匹配。只有双极型TTLSRAM，存取速度与CPU处于同一量级，但价格较贵，功耗很大，集成度低，所以不能将所有DRAM都采用SRAM。折中的办法是分级处理，在主存和CPU之间加一个容量相对小的双极型SRAM作为高速缓冲存储器Cache。

目前Cache的分为一级Cache、二级Cache等。Cache的命中率可达到90%-98%，这样就大大提高了CPU访问数据的速度。Cache高速缓冲存储器6.2.1Cache概述6.21.使用Cache的必要性Cache高速缓冲存储器6.2.1Cache概述时间局部性:在一小段时间内，最近被访问过的程序和数据很可能再次被访问；空间局部性:这些最近被访问过的程序和数据，往往集中在一小片存储区域中；

指令执行顺序方面：指令顺序执行比转移执行的可能性要大（大约为5:1），因此，合理地把数据和程序放在不同的存储介质中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问的局部性。6.22.程序访问的局部性3.Cache-CPU-主存之间的关系关系CPUCache主存字传送块传送…...…...主存块Cache标记结构6.2.1CACHE概述1.cache基本结构

Cache和主存分同样大小的块；主存中只有一小部分块的内容可放在Cache中.在cache中每一块都有一个标记,

指明它是主存的哪一块的副本，该标记的内容相当于主存中块的编号，设主存地址为n位，且n=m+b，则主存的块数M=2n/2b=2m

，块内字节数B=2b。

cache地址码=（c+b）位。cache的块数为2c。块内字节数与主存相同。6.2.2高速缓存工作原理2.Cache工作原理它由cache存储体、地址映像变换机构、cache替换机构模块组成。6.2.2CACHE的工作原理3.Cache的设计要素Cache容量映射功能直接映射组相联映射全相联映射替换算法最近最少使用（LRU）先进先出（FIFO）最不经常使用（LFU）随机写策略写通过(writethrough)回写(writeback)写一次块大小Cache数目一级或二级统一或分离6.2.2CACHE的工作原理块长：块的大小，块长一般取一个主存周期所能调出的信息长度。Pentium为32个字节。cache的容量和块的大小是影响cache的效率的重要因素。通常用“命中率”来测量cache的效率。命中率：指CPU所要访问的信息在cache中的比率。失效率：将所要访问的信息不在cache中的比率。cache的存储容量比主存的容量小得多；太小会使命中率太低；过大不仅会增加成本，且当容量超过一定位后，命中率随容量的增加将不会有明显地增长。4.cache的容量和块大小6.2.2CACHE的工作原理5.cache的命中率增加cache的目的是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此cache的命中率应接近于1。在一个程序执行期间命中率Hc＝Nc/(Nc+Nm)

Nc表示Cache完成存取的总次数

Nm表示主存完成存取的总次数设Tc为Cache的存取周期，Hc为Cache的命中率，Tm为主存的存取时间，则平均存取时间T为：

T＝Hc*Tc+(1-Hc)Tm

追求的目标是：以较小的硬件代价使cache/主存系统的平均访问时间T越接近Tc越好。cache的命中率还与程序有关，不同程序命中率可能不同。6.2.2CACHE的工作原理6.2.3cache存储器组织主存的地址和cache地址间建立一种确定的逻辑关系，必须应用某种函数把主存地址映像到cache，这样的逻辑关系称作地址映像。在信息按照这种映像关系装入cache后，执行程序时，将主存地址变换成cache地址，这个变换过程叫做地址变换。地址的映像和变换是密切相关的。地址映像方式：直接映像、全相联映像、组相联映像设主存储器空间被分为Mm(0),Mm(1),…,Mmi),…,Mm(2m－1)，共2m块,字块大小为2b个字;设Cache存储空间被分为Mc(0),Mc(1),…,Mc(j),…,Mc(2c－1，共2c个同样大小的块.6.2.3cache存储器组织

直接映像：一个主存块只能映像到cache中的唯一一个指定块的地址映像方式。若这个位置已有内容，则产生块冲突，原来的块将无条件到被替换出去。

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

1.直接映像6.2.3cache存储器组织（1）直接映像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个块，总共有M2c块，编号从0到M2c-1。Cache有2c个块。第0区第1区第M-1区6.2.3cache存储器组织这是一种多对一的映射关系，但一个主存块只能映象到Cache的一个特定块位置上去。

Cache的第i块和主存的第j块有如下函数关系：i=jmodm

(m为Cache的总块数）

i=0,1,2,…,m-1

j=0,1,2,…,n-1在这种映象方式中：主存的第0块，第16块，第32块，…，只能映象到Cache的第0块；而主存的第1块，第17块，第33块，…，只能映象到Cache的第1块；……6.2.3cache存储器组织直接映像方式Cache地址4位9位主存地址7位4位9位11位9位主存地址7位6.2.3cache存储器组织主存地址分成三段：区号、块号和块内地址。区号(组号)作为标志存放在地址映象表中，用于判断命中与否。块号直接用于查地址映象表;块内地址用于块内寻址。在访存操作时，根据主存地址中的块号读出块表中的区号，并与当前地址的区号进行比较，结果相同表cache命中，访问可对cache进行；不相同则表示不命中，访问需对主存进行。6.2.3cache存储器组织（2）直接映像的地址变换方法比较相等且有效位相等6.2.3cache存储器组织CPU送来的主存地址和读／写命令后，只需根据中间c位字段找到cache存储器字块，然后,看其标记是否与主存地址高t位符合:

如果符合且有效位为“1”，则可根据b位块内地址，从cache中取得所需指令或数据；如果不符合或有效位为“0”，就从主存读入新的字块来替换旧的字块，并将CPU所需数据送往CPU，同时修改cache标记。假如原来有效位为“0”，还要将有效位改置成“1”。直接映像方式的缺点是不够灵活，即主存的2t个字块只能对应惟一的cache存储器字块，因此，即使cache存储器别的许多地址空着也不能占用。这使得cache存储空间得不到充分利用，并降低了命中率。（2）直接映像地址变换方法（续）6.2.3cache存储器组织优点:硬件实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在Cache中。成本低

缺点：不够灵活，主存的多个字块只能对应唯一的Cache字块，块冲突率很高，降低了命中率。（3）直接映像的特点6.2.3cache存储器组织【例1】设一个cache的容量为2KB，每个块为16B，求：①该cache可容纳多少个块？②如果主存容量是256KB，则主存有多少个块？③主存的地址有多少位？cache地址有多少位？④进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？【解】①cache中有2048/16=128个块②主存有256K/16=16384个块③主存容量为256KB=218字节，主存字节地址有18位。

cache容量为2KB=211字节，cache的字节地址为11位。④存储器的字地址分三段：区号、块号、块内字地址。区号的长度为18-11=7位，块号为7位。块内字地址为4位。

全相联映像是指主存中的任何一个字（字块）均可以映像到CACHE中的任何一个字（字块）的位置上，也允许从确实已被占满的cache存储器中替换出任何一个旧字块。反过来说，CACHE的一个字（字块）中，在不同时刻可能存放的是整个主存中的任何一个字（字块）中的内容，即二者的对应关系是完全随意的，没有任何强制性的限制条件。

全相联映像方式是最灵活但成本最高的一种方式。2.全相联映像6.2.3cache存储器组织块0块1块15Cache标记标记标记标记标记标记.........块0块1块15块16块17块31块2047主存Tag(1）全相联映像方式Cache地址4位9位11位9位主存地址11位允许主存中的每一个字块映象到Cache的任何一个字块位置上最灵活但成本最高的一种方式。6.2.3cache存储器组织（2）全相联映像cache组织

字块0字块1﹕字块i字块0字块1﹕字块2c-1标记标记标记﹕字块2m-1﹕﹕主存字块标记块内地址m=t+c位b位主存地址比较器（m位）＝≠有效位=1主存储器命中不命中cache存储器m=t+c所有标记6.2.3cache存储器组织（3）全相联映像的地址变换方法6.2.3cache存储器组织1.对CACHE的使用可以有最大的灵活性。只要CACHE中有空闲的单元，可确保进行写操作。当CACHE已满，要写入时可以方便地选择一个CACHE单元进行腾空。2.Cache的块冲突概率最低，空间利用率最高，地址变换速度慢.3.比较操作的电路过多、过于复杂，实现成本高难以实现。

CACHE读写操作时，用原本读主存的整个（或部分）地址去与CACHE的标志字段的内容实现比较时，必须与整个CACHE中每一个单元的标志字段都比较，才能知道要读的信息是否已在CACHE中。4.使用条件：由于仅在CACHE容量很小时方可选用。（4）全相联映像方式的特点6.2.3cache存储器组织组相联映像将主存空间按cache大小等分成区后，再将cache空间和主存空间中的每一区都等分成大小相等的组。让主存各区中某组中的任何一块，均可直接映像装入cache中对应的任何一块位置上。

组相联映像方式是直接映像和全相联映像方式的一种折衷方案。特点：

1.组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。2.组相联映像方式的优缺点介于直接映像与全相联映像两种方式之间。3.cache的命中率除了与地址映像的方式有关外，还与cache的容量有关。cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。3.组相联映像6.2.3cache存储器组织（1）组间全相联，组内直接映像8位3位9位8位1位3位9位注意：当只有一个组并且每组16块时，此时为直接映像；当有16组并且每组一个块时,则为全相联映像。6.2.3cache存储器组织组相联映像Cache组织001213……147151681718919……301531…………203210162033203410172035……204610232047001213……14715设主存为1MB=220Cache为8KB=213块长为0.5KB=29块数=8KB/0.5KB=16Cache为二路组相联组数=块数/路数=16/2=8主存地址格式19131210980主存高位组号块号块内地址Cache地址格式1210980组号块号块内地址注:块号是组内块号的缩称组号是Cache内组号的缩称组组第0区第1区第127区块块

Cache与主存均分组,主存中一个组内的块数与Cache的分组数相同,主存中的各块与Cache的组号有固定的映象像关系,但可自由映像到对应的Cache组中任一块.（2）组间直接映像，组内全相联注意：当只有一个组并且每组16块时，此时为全相联映像；当有16组并且每组一个块时,则为直接映像。1位1位9位Cache组号块号块内地址区号6位1位1位9位组号块号块内地址主存块0块1块Cache标记标记标记标记标记标记0组块0块1块3块4块127Tag标记块230组1组块21组块5块6块7..0组1组块124块125块1261组0组0区1区63区..6.2.3cache存储器组织目前微机中Cache一般装在主板上，在Intel486CPU中集成了8KB的数据和指令共用的Cache；在PentiumCPU中集成了8KB的数据Cache和8KB的指令Cache，与主板上的Cache形成两级Cache结构。当CPU发出读请求时，将主存地址m位（或m位中的一部分）与cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况：①当比较结果相等时，说明需要的数已在cache中，那么直接访问cache就行了，在CPU与cache之间，通常一次传送一个字；这种情况称为访问cache命中。②当比较结果不相等时，说明需要的数据尚未调入cache，那么就要把该数据所在的整个字块从主存一次调进来。这种情况称为访问cache不命中。1.cache的读工作原理6.2.4替换算法和更新策略

cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行写操作，就会遇到如何保持cache与主存的一致性问题。写入方式通常有两种：暂时只向cache存储器写入，并用标志加以注明，直到经过修改的字块被从cache中替换出来时才一次写入主存；这种方式称为标志交换（flag-swap）方式。每次写入cache同时写入主存，使cache和主存保持一致。称为通过式写（write-through），又称写直达法。

当被修改的单元根本就不在cache时，写操作直接对主存进行，而不写入cache存储器。2.cache的写策略6.2.4替换算法和更新策略

有效位:为了说明标记是否有效.当机器刚加电时,Reset信号将所有标记的有效位置“0”,使标记无效。在程序执行的过程中,当Cache不命中时逐步将指令块或数据块从主存调入Cache中的某一块,并将这一块标记中的有效位置“1”.刚加电后所有标记位都为“0”，因此开始执行程序时，命中率较低。6.2.4替换算法和更新策略cache的标记

在从主存读出新的字块调入cache存储器时，如果遇到cache存储器中相应的位置已被其他字块占有，那么就必须去掉一个旧的字块，让位于一个新的字块。这种替换应该遵循一定的规则，最好能使被替换的字块是下一段时间内估计最少使用的。这些规则称为替换策略或替换算法，由替换部件加以实现。6.2.4替换算法和更新策略3.替换策略当一个新的主存块要调入到cache，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为cache工作原理要求它应尽量保存最新的