第四章第五节虚拟存储器课件

第六节高速缓冲存储器Cache存储系统的层次结构第六节高速缓冲存储器Cache存储系统的层次结构一、高速缓冲存储器与内存CPU的关系一、高速缓冲存储器与内存CPU的关系二、cache存储器工作原理：1、局部性原理：在一个较短的时间间隔内，地址往往集中在存储器逻辑地址空间的很小范围内。程序地址的分布本来就是连续的，再加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问就自然地具有相对集中的倾向。数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序访问的局部性。2、高速缓冲存储器：根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，当程序运行时，不必从主存储器取指令和取数据，而访问这个高速存储器即可，所以提高了程序运行速度，这个存储器称作高速缓冲存储器(cache)。二、cache存储器工作原理：1、局部性原理：2、高速缓冲存3、命中率：命中率：指CPU所要访问的信息在cache中的比率；失效率：所要访问的信息不在cache中的比率。一般来说，cache的存储容量比主存的容量小得多，但不能太小，太小会使命中率太低；也没有必要过大，过大不仅会增加成本，而且当容量超过一定值后，命中率随容量的增加将不会有明显地增长。4、替换算法：在从主存读出新的字块调入cache存储器时，如果遇到cache存储器中相应的位置已被其他字块占有，那么就必须去掉一个旧的字块，让位于一个新的字块。这种替换应该遵循一定的规则，最好能使被替换的字块是下一段时间内估计最少使用的。这些规则称为替换策略或替换算法3、命中率：4、替换算法：5、cache的基本结构：5、cache的基本结构：三、cache存储器组织：

为了把信息放到cache存储器中，必须应用某种函数把主存地址映像到cache，称作地址映像。在信息按照这种映像关系装入cache后，执行程序时，应将主存地址变换成cache地址，这个变换过程叫做地址变换。地址的映像和变换是密切相关的。假设主存储器空间被分为Mm(0)，Mm(1)，…，Mm(i)，…，Mm(2m-1)共2m个块，字块大小为2b个字；cache存储空间被分为Mc(0)，Mc(1)，…，Mc(j)，…，Mc(2c-1)共2c个同样大小的块。三、cache存储器组织：为了把信息放到c(1)直接映像设主存空间被分为：

Mm(0)，Mm(1)，……，Mm(i)，……，Mm(2m-1)共2m个块，字块大小为2b个字节；cache空间被分为：Mc(0)，Mc(1)，……，Mc(j)，……，Mc(2c-1)共2c个同样大小的块。直接映像函数可定义为：

j=imod2c其中，j是cache的字块号，i是主存的字块号，2c是cache中块的个数。在这种映像方式中，主存的第0块，第2c块，第2c+1块，…，只能映像到cache的第0块；而主存的第1块，第2c+1块，第2c+1+1块，…，只能映像到cache的第1块。直接映像的优点是实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在cache存储器中。在直接映像方式中，主存和cache中字块的对应关系如下图所示。(1)直接映像主存与cache中块的对应关系Cache存储器t位标记字块0字块1字块2……字块2c-1主存块0(2b字节)块1(2b字节)块2(2b字节)……字块2c-1字块2c字块2c+1字块2c+2……字块2c+1-1字块2c+1字块2c+1+1字块2c+1+2……字块2m-1主存地址主存页号Cache字块地址字块内地址t位C位(由cache中字块数确定)b位(由字块大小确定)m位主存与cache中块的对应关系Cache存储器t位标记字块0直接映像cache组织直接映像cache组织例：假设主存空间被分为32个块(2m=32)，cache空间被分为4个块(2c=4)，每个字块4个字节。主存地址位数为7位。标记32位数据块字块号主存空间主存地址第0块0000000第1块0000100第2块0001000第3块0001100第4块0010000第5块0010100第6块0011000第7块0011100第8块0100000第9块0100100第10块0101000第11块0101100第12块0110000第13块0110100第14.块0111000第15块0111100第16块1000000第17块1000100第18块1001000第19块1001100第20块1010000第21块1010100第22块1011000第23块1011100第24块1100000第25块1100100第26块1101000第27块1101100第28块1110000第29块1110100第30块1111000第31块1111100映射关系：根据j=imod2c有：0mod4=0、4mod4=0、8mod4=0、12mod4=0、16mod4=0、20mod4=0、24mod4=0、28mod4=0，所以：主存的第0，4，8，12，16，20，24，28块只能映射到cache的第0块中；1mod4=1、5mod4=1、9mod4=1、13mod4=1、17mod4=1、21mod4=1、25mod4=1、29mod4=1，所以：主存的第1，5，9，13，17，21，25，29块只能映射到cache的第1块中；主存的第2，6，10，14，18，22，26，30块只能映射到cache的第2块中；主存的第3，7，11，15，19，23，27，31块只能映射到cache的第3块中；例：假设主存空间被分为32个块(2m=32)，cache空间例：假设主存空间被分为32个块(2m=32)，cache空间被分为4个块(2c=4)，每个字块4个字节。主存地址位数为7位。页号3位32位数据块第0块第1块第2块第3块字块号主存空间主存地址第0块0000000第1块0000100第2块0001000第3块0001100第4块0010000第5块0010100第6块0011000第7块0011100第8块0100000第9块0100100第10块0101000第11块0101100第12块0110000第13块0110100第14块0111000第15块0111100第16块1000000第17块1000100第18块1001000第19块1001100第20块1010000第21块1010100第22块1011000第23块1011100第24块1100000第25块1100100第26块1101000第27块1101100第28块1110000第29块1110100第30块1111000第31块1111100主存地址主存页号Cache字块地址字块内地址65432105位例：假设主存空间被分为32个块(2m=32)，cache空间基本思想：把主存分为若干页，每页大小与cache存储器容量相同，每页的第一块对应cache中的第一块，每页的第二块对应cache中的第二块，每页的第三块对应cache中的第三块，依次类推。在存储系统中，cache的每一块都可以有多个主存页的块与之对应，cache中的标记存储体用于存放主存的页号，数据存储体用于存储主存的数据块。判断是否命中：基本思想：判断是否命中：例、有一主存容量为16MB，cache容量为64KB的直接映像高速缓存系统，其高速缓存结构如下图所示：Cache字块地址主存页号32位数据111111111111110112345678H11111111111110FF34567890H………………000000000000010033334444H000000000000000111112222H97924322H1111111111111100页55412586H11111111111110…………33334444H00000000000001860AD235H0000000000000012345678H111111111111110154265721H11111111111110…………44565684H0000000000000111112222H0000000000000058621565H11111111111111FF34567890H11111111111110…………68453866H0000000000000155865762H00000000000000主存地址8位主存页号14位块在页中的地址2位字块内地址231615210页内字块地址例、有一主存容量为16MB，cache容量为64KB的直接映把16MB主存分为256页，每一页64KB，64KBcache分为16K个4字节数据块，设CPU要取地址为12FFE8H的数据，cache系统进行如下操作：(1)、cache控制器取主存地址12FFE8H(000100101111111111101000)中的14位cache字块地址(11111111111010),以此值选中cache中的一个字块；(2)、cache控制器将主存地址的高8位12H(00010010)与cache中块地址为11111111111010的块的标记值相比较，若相等，且有效位为1，则命中，否则没有命中。把16MB主存分为256页，每一页64KB，64KBcach(2)全相联映像全相联映像方式是最灵活但成本最高的一种方式，如下图所示。全相联映像cache组织(2)全相联映像全相联映像cache组织cachem位标记数据存储体块0(2b字节)块1(2b字节)块2(2b字节)…………块j(2b字节)…………块n(2b字节)主存块0(2b字节)块1(2b字节)块2(2b字节)块3(2b字节)块4(2b字节)……块i(2b字节)……块2m-1(2b字节)位主存地址0主存字块地址字块内地址cachem位标记数据存储体块0(2b字节)块1(2b字节1MB主存地址……1211111111111100000111001111111111110000011000111111111111000001010011111111111100000100……1100001000000000010011110000100000000001001011000010000000000100011100001000000000010000……F000000000000000000111000000000000000000011000000000000000000001010000000000000000000100……cache18位块地址32位数据块11111111111100000112000000H000000000000000001F0000000H…………00001000000000010011111111H例：设一个大小规模为64KB的全相联告诉缓存系统，每个数据块4字节，内存有1M字节。20位主存地址1921018位块地址字块内地址主存地址为00000000000000000100的数据块，其内容为F0000000H，放在cache数据存储体的第二个位置。查找过程：主存地址被分成两部分，底位为块内地址，高位为标记，为了判断被访问字所在的快是否在cache中，必须把CPU提供的主存地址码中标记与cache中每一块的标记进行比较。1MB主存地址……121111111111110000011(3)组相联映像组相联映像方式是直接映像和全相联映像方式的一种折衷方案。组相联映像cache组织如下图所示。组间采用直接映像，组内的字块为全相联映像：设把cache字块分为2c’组，每组包含2r个字块，主存字块Mm(i)(0≤i≤2m-1,主存有2m个字块)到cache字块Mc(j)(0≤j≤2c-1，cache有2c个字块)的映像函数为：

j=(imod2c’)*2r+k(0≤k≤2r-1)

组号组相联映像方式的性能与复杂性介于直接映像与全相联映像两种方式之间。当r=0时，它就成为直接映像方式；当r=c时，就是全相联映像方式。cache的命中率除了与地址映像的方式有关外，还与cache的容量有关。cache容量大，命中率高，但达到一定容量后，命中率的提高就不明显了。(3)组相联映像组相联映像cache组织组数：Cache字块数2c，每组块数为2r，则组数：2c/2r=2c-r组相联映像cache组织组数：例：设把cache分为4(c’=2)个组，每组4(r=2)字块，每块32位，主存有32块:第0组：由0、1、2、3字块组成；第1组：由4、5、6、7字块组成；第2组：由8、9、10、11字块组成；第3组：由12、13、14、15字块组成；主存块:i=0时：j=(0mod4)*4+k(0≤k≤4-1)=0+（0，1，2，3）=0，1，2，3i=1时：j=(1mod4)*4+k(0≤k≤4-1)=4+（0，1，2，3）=4，5，6，7i=2时：j=(2mod4)*4+k(0≤k≤4-1)=2+（0，1，2，3）=8，9，10，11i=3时：j=(3mod4)*4+k(0≤k≤4-1)=12+（0，1，2，3）=12，13，14，15i=4时：j=(0mod4)*4+k(0≤k≤4-1)=0+（0，1，2，3）=0，1，2，3i=5时：j=(1mod4)*4+k(0≤k≤4-1)=4+（0，1，2，3）=4，5，6，7i=6时：j=(2mod4)*4+k(0≤k≤4-1)=2+（0，1，2，3）=8，9，10，11i=7时：j=(3mod4)*4+k(0≤k≤4-1)=12+（0，1，2，3）=12，13，14，15……例：设把cache分为4(c’=2)个组，每组4(r=2)字块号主存空间主存地址页号第0块00000000页第1块0000100第2块0001000第3块0001100第4块00100001页第5块0010100第6块0011000第7块0011100第8块0100000第9块0100100第10块0101000第11块0101100第12块0110000第13块0110100第14块0111000第15块0111100第16块1000000第17块1000100第18块1001000第19块1001100第20块1010000第21块1010100第22块1011000第23块1011100第24块1100000第25块1100100第26块1101000第27块1101100第28块1110000第29块1110100第30块1111000第31块1111100Cache(4组，每组4块)0组标记字块0标记字块1标记字块2标记字块31组标记字块4标记字块5标记字块6标记字块72组标记字块8标记字块9标记字块10标记字块113组标记字块12标记字块13标记字块14标记字块15访问：根据主存地址的“cache组地址”字段访问cache，并将主存字块标记(t+r位)与cache同一组的2r个字块标记比较。字块号主存空间主存地址页号第0块00000000页第1块00例、有一主存容量为16MB，cache容量为64KB的二路组相联映像高速缓存系统(r=1,2r=2)每组为两块，每个数据块4个字节，其高速缓存结构如下图所示：13位组地址9位字块标记32位数据9位字块标记32位数据111111111111111111111111113333H00000000112345678H111111111111011111111123459A11H………………000000000000100000000033334444H000000000000000000000022222222H00000000111112222H97924322H111111111111100000000055412586H1111111111110…………33334444H000000000000122222222H000000000000012345678H111111111111100000000154265721H1111111111110…………44565684H000000000000111112222H000000000000011113333H111111111111111111111123459A11H1111111111110…………68453866H000000000000155865762H0000000000000主存地址(24位)9位主存字块标记13位组地址2位字块内地址寻找地址为：00FFFDH的数据例、有一主存容量为16MB，cache容量为64KB的二路组四、替换算法当新的主存字块需要调入cache存储器而它的可用位置又已被占满时，就产生替换算法问题。先介绍两种替换算法：先进先出(FIFO)算法和近期最少使用(LRU)算法。2、LRU算法是把一组中近期最少使用的字块替换出去。这种替换算法需随时记录cache存储器中各个字块的使用情况，以便确定那个字块是近期最少使用的字块。LRU替换算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。LRU是最常使用的一种算法。其设计思想是把组中各块的使用情况记录在一张表上。1、FIFO算法总是把一组中最先调入cache存储器的字块替换出去，它不需要随时记录各个字块的使用情况。四、替换算法2、LRU算法是把一组中近期最少使用的字块替换LRU算法替换登记表LRU算法替换登记表

解决方法： ①

通写式(writethrough)

②

缓冲通写式(bufferedwritethrough)

③

回写式(writeback)

五、Cache的数据更新方法：两类一致性问题、数据丢失问题 解决方法：五、Cache的数据更新方法：两类一致性问题、虚拟存储系统虚拟存储系统一、虚拟存储器Cache与虚拟存储器的主要区别存储系统Cache虚拟存储器要达到的目标提高(主存)速度扩大(主存)容量实现方法全部硬件软件为主,硬件为辅两级存储器速度比3倍~10倍105倍页(块)大小1字~16字1KB~16KB等效存储容量主存储器虚拟存储器透明性对系统和应用程序员仅对应用程序员不命中时的处理方法等待主存储器任务切换虚拟存储器：为了给用户提供更大的随机存取空间而采用的一种存储技术。它将内存与外存结合使用，好像有一个容量极大的内存储器，工作速度接近于主存，每位成本又与辅存相近，在整机形成多层次存储系统。

虚拟存储器源出于英国ATLAS计算机的一级存储器概念。这种系统的主存为16千字的磁芯存储器，但中央处理器可用20位逻辑地址对主存寻址。到1970年，美国RCA公司研究成功虚拟存储器系统。IBM公司于1972年在IBM370系统上全面采用了虚拟存储技术。虚拟存储器已成为计算机系统中非常重要的部分。一、虚拟存储器Cache与虚拟存储器的主要区别存储系统Cac根据程序运行的局部性原理，一个程序运行时，在一小段时间内，只会用到程序和数据的很小一部分，仅把这部分程序和数据装入主存储器即可。更多的部分可以在用到时随时从磁盘调入主存。在操作系统和相应硬件的支持下，数据在磁盘和主存之间按程序运行的需要自动成批量地完成交换。

1、虚拟存储器的核心思路

CPU主存储器辅助存储器辅助软硬件2、虚拟存储器的构成根据程序运行的局部性原理，一个程序运行时，在一小段时间内，只二、虚拟存储器中经常使用的基本管理技术：

◎段式存储管理，

◎页式存储管理。

◎段页式存储管理核心问题都在于处理数据的存放与调度。

(一)、段式存储管理1、段：利用程序的模块化性质,按照程序的逻辑结构划分成的多个相对独立部分，通常一个大的程序是由在逻辑上、处理功能上有一定的独立性的程序段组成的，可用段名或段号来标明程序段，每个段的长度是随意的，由指令的条数确定。

程序空间大小

段11K

段22K

段33K

段41K

段52K二、虚拟存储器中经常使用的基本管理技术：

◎段式存储管理，

2、段式存储管理：当运行有若干段组成的程序时，把主存按段进行分配与管理，以段作为信息单位，实现在主存-辅存之间的传送。这种管理方式称为段式存储管理。

主存空间地址01K3K5K8K-1段1段5段3程序空间大小

段11K

段22K

段33K

段41K

段52K3、逻辑地址的组成：而在使用虚拟存储器的情况下，虚地址不是被直接送到内存总线上，而是送到内存管理单元(MMU)，它由一个或一组芯片组成，其功能是把虚地址映射为物理地址段式存储管理的核心问题是：变逻辑地址中的逻辑段号为主存中的一个存储区的起始地址，这是通过在系统中（一般在主存中）设置一个段表来完成。段表由多个表项组成：段起始地址，段长，段的装入位

段号段内地址2、段式存储管理：当运行有若干段组成的程序时，把主存按段进行4、段表：一般用来指明各段在主存中的位置,每段都有它的名称(用户名称或数据结构名或段号),段起点,段长等

段表段号段长段起点装入位……12KB30100H1……25KB42000H1……主存空间地址01K3K5K8K-1段1段5段3程序空间大小

段11K

段22K

段33K

段41K

段52K例如：4、段表：一般用来指明各段在主存中的位置,每段都有它的名称(段号段内地址++逻辑地址段始地址段长装入位段表主存实际地址段表基地址5、逻辑地址到实地址的转换：段号段内地址++逻辑地址段始地址段长段式虚实地址转换段表长度段表起始地址位移量100段号29200H200H38000H500H24000H600H16000H1000H0基址段长段号+8100H主存段表虚地址物理地址段式虚实地址转换段表长度段表起始地址位移量100段号2920把主存按段分配的存储管理方式称为段式管理.段式管理系统的优点是段的分界与程序的自然分界相对应;段的逻辑独立性使它易于编译,管理,修改和保护,也便于多道程序共享.其缺点是容易在段间留下许多空余的零碎存储空间不好利用,造成浪费.把主存按段分配的存储管理方式称为段式管理.(二)、页式存储管理1、页：把虚拟逻辑地址空间和主存实际物理地址空间都划分容量相等（为2的幂）的大小区域，称为页(把前者称为实页或物理页,而把前者称为虚页或逻辑页)。所有的地址都可以用页号拼接页内地址来表示。

假设虚页号为0,1,2,…,m,实页号为0,1,2,…,l,显然有m>l.由于页的大小都取2的整数幂个字,所以,页的起点都落在低位字段为零的地址上.可把虚拟地址分为两个字段,高位字段为虚页号,低位地址为页内字地址。2、页式存储管理：在一个计算机系统中页的长度是人为划分的，并通过分页方式进行存储器管理，实现以页为单位来完成在虚存和主存之间信息交换，称为页式存储管理。

(二)、页式存储管理2、页式存储管理：在一个计算机系统中页的3、虚拟地址的组成：虚拟地址到主存实地址的变换是由页表来实现的.在页表中,对应每一个虚存页号有一个表目,表目内容至少要包含该虚页所在的主存页面地址(页面号),用它作为实(主)存地址的高字段;与虚拟地址的字地址字段相拼接,就产生完整的实主存地址,据此访问主存虚页号页内地址4、页表：虚页号实页号装入位……11401……20421……例如：某个程序有5页(逻辑页号0~4),个页分别主存不连续的页面位置,用页表记录逻辑页号及其所对应的实主存页号,页表是由操作系统建立的.图中页号0,1,3已分配实主存空间,所以装入位为“1”3、虚拟地址的组成：虚拟地址到主存实地址的变换是由页表来实现5、虚拟地址到主存实地址的变换：虚页号页内地址实页号页内地址+（在内存中）控制位有效位慢表虚地址实地址(读写内存用)按地址读实页号虚页号页内地址实页号页内地址页表基地址5、虚拟地址到主存实地址的变换：虚页号页内地址实页号页内地址虚拟地址到物理地址的转换页表(慢表)在主存中的地址由页表寄存器指出110000000000100虚拟地址0000511004100031110210011101001100010000000000100存在位12位偏移实存(主存)地址程序页表例：见课本P142。虚拟地址到物理地址的转换页表(慢表)在主存中的地址由页表寄存主要优点：

(1)主存储器的利用率比较高

(2)页表相对比较简单

(3)地址变换的速度比较快

(4)对磁盘的管理比较容易主要缺点：

(1)程序的模块化性能不好

(2)页表很长，需要占用很大的存储空间。例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB主要优点：

(1)主存储器的利用率比较高

(2)页表相对(三)、段页式管理系统段式和页式存储管理各有其优缺点,可以采用段和页结合的段页式存储管理系统.程序按模块分段,段内再分页,出入主存仍以页为信息传送单位,用段表和页表(每段一个页表)进行两级管理.1、基本原理：在段页式虚拟存储器中,把程序按逻辑结构分段以后，再把每段分成固定大小的页.程序对主存的调入调出是按页面进行的,但它又可按段实现共享和保护.它兼取页式和段式系统的优点,它的缺点是在地址映像过程中需要多次查表,在这种系统中,虚拟地址转换成物理地址是通过一个段表和一组页表来进行定位的段表中的每个表目对应一个段,每个表目有一个指向该段的页表的起始地址(页号)及该段的控制保护信息由页表指明该段各页在主存中的位置以及是否已装入,已修改等标志。如果有多个用户在机器上运行,称为多道程序,多道程序的每一道(每个用户)需要一个基号(用户标志号),可由它指明该道程序的段起点(存放在基址寄存器中)(三)、段页式管理系统段式和页式存储管理各有其优缺点,可以采2、段表、页表和段表地址寄存器：为了实现从逻辑地址到物理地址的转换，系统要为每个进程或作业建立一个段表，并且还要为该作业段表中的每一段建立一个页表。这样，作业段表的内容有所改变：不再是段长和段在内存的起始地址，而是页表长度和页表地址。为指出运行作业的段表地址，系统有一个段表地址寄存器，它指出作业的段表长度和段表起始地址。

2、段表、页表和段表地址寄存器：为了实现从逻辑地址到物理地址3、虚拟地址格式:用户号D段号S页号P页内地址d（1）地址转换硬件将段表地址寄存器的内容B与逻辑地址（即有效地址）中的段号s相加，得到访问该作业段表的人口地址（第s段）。

（2）将段s表项中的页表长度与逻辑地址中的页号

p进行比较。如果页号

p小于页表长度，则表示未越界，向下正常进行；否则，发生中断。

（3）将该段的页表基址与页号p相加，得到访问段s的页表中第p页的人口地址。

（4）从该页表的对应页表项中读出该页所在的物理块号f，再用块号f和页内地址d拼接成访问内存地址。

（5）如果对应的页未在内存，则发生缺页中断，系统进行缺页中断处理。如果