高速缓冲存储器和虚拟存储器

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,8,章,高速缓冲存储器和虚拟存储器,本章主要内容,高速缓冲存储器（,Cache,）,高速缓存的基本运行原理,高速缓存的,3,种映像方式,高速缓存使用中的几个问题,虚拟存储器,虚拟存储器概述,段式存储管理,页式存储管理,2,微电子技术发展趋势,CPU,与,DRAM,性能比较,3,程序的局部性原理,程序在一定时间段内通常只访问较小的地址空间,两种局部性：,时间局部性,和,空间局部性,时间局部性：最近被访问的信息很可能还要被访问。,将最近被访问的信息项装入到,Cache,中。,空间局部性：最近被访问的信息临近的信息也可能被访问。,将最近被访问的信息项临近的信息一起装入到,Cache,中。,地址空间,访问概率,4,高速缓冲存储器（,Cache,）,用途：,设置在,CPU,和 主存储器之间，完成高速与,CPU,交换信息，尽量避免,CPU,不必要地多次直接访问慢速的主存储器，从而提高计算机系统的运行效率。,实现：,这是一个存储容量很小，但读写速度更快的，以,关联存储器方式,运行、用静态存储器芯片实现的存储器系统。,要求：,有足够高的命中率，既当,CPU,需用主存中的数据时，多数情况可以直接从,CACHE,中得到，称二者之比为命中率。,5,CACHE,的基本运行原理,Cache,存储单元的组成部分,数据字段,：保存从主存单元复制过来的数据,标志字段,：保存相应主存单元的地址信息,有效位字段,：标识,数据字段,和,标志字段,是否有效,提高,Cache,性能，降低成本,Cache,单元的大小：,cache line size,（几个主存字，减少标志位位数，较少,Cache,总容量）,Cache,与主存交换数据的单位：,cache line size,（充分利用空间局部性）,Cache,单元与主存单元的对应关系，例如：,完全随意对应、一对多硬性对应和多对多有限随意对应,Cache,的容量、分层组织、接入方式等方面,6,CACHE,的基本运行原理,MEMORY,CACHE CONTROL,数据总线,译码选一单元,比较选一行,读过程为例,地址总线,ADDR DATA,CACHE,CPU,7,CACHE,的,3,种映像方式,地址映像,：把一主存单元的数据复制到,CACHE,中时，还要把该主存单元的地址，经过某种函数关系处理后写进,CACHE,的标志字段，这一过程被称为,CACHE,的地址映像。,地址变换,：在程序执行时，还要把主存地址变换为访问,CACHE,的地址，这一过程被叫做,CACHE,的地址变换。,CACHE,存储器通常使用,3,种映像方式，它们是全相联映像方式、直接映像方式、多路组相联映像方式，,3,种映像方式有各自的优缺点。,8,全相联映像方式,全相联映像方式：是指主存的一个字块可以映像到整个,CACHE,的任何一个字块中。,全相联映像方式特点：,主存的字块可以和,Cache,的任何字块对应，利用率高，方式灵活。,标志位较长，比较电路的成本太高。如果主存空间有,2,m,块，则标志位要有,m,位。同时，如果,Cache,有,n,块，则需要有,n,个比较电路。,使用成本太高,9,全相联映像方式,C P U,数据,主存字块标记,有效位,主存储器,CACHE,比较,译码,标志,数据,主存字块标记,块内地址,主存地址,10,全相联硬件实现举例,11,直接映像方式,直接映像方式：是指主存的一个字块只能映像到,CACHE,的一个准确确定的字块中。,直接映像方式特点：,主存的字块只可以和固定的,Cache,字块对应，方式直接，利用率低。,标志位较短，比较电路的成本低。如果主存空间有,2,m,块，,Cache,中字块有,2,c,块，则标志位只要有,m-c(2,m,/2,c,),位。且仅需要比较一次。,利用率低，命中率低，效率较低,12,直接映像方式,C P U,数据,有效位,主存储器,CACHE,比较,译码,译码,cache,字块地址,主存字块标记,标志,数据,主存字块标记,块内地址,主存地址,cache,字块地址,13,直接映像硬件实现举例,14,多路组相联映像方式,多路组相联映像方式：是对全相联映像和直接映想象的一种折衷的处理方案。既不在主存和,CACHE,之间实现字块的完全随意对应，也不在主存和,CACHE,之间实现字块的多对一的硬性对应，而是实现一种有限度的随意对应。,多路组相联映像方式特点：,折衷方案。组间为全相连，组内为直接映像。,集中了两个方式的优点。成本也不太高。,最常用的,CACHE,映像方式,15,组地址,两路组相联映像方式,C P U,数据,有效位,主存储器,CACHE,译码,比较,比较,译码,译码,标志,数据,主存地址,主存字块标记,块内地址,组地址,主存字块标记,16,多路组相联硬件实现举例,17,三种映像方式比较,全相联映射,主存中的一块可以映射到,Cache,中任何一个位置,直接映像,主存中的一块只能映射到,Cache,中唯一的一个位置,定位时，不需要判断，只需替换,多路组相联映射,主存中的一块可以选择映射到,Cache,中多个位置,全相联映射和多路组相联映射的失效处理,从主存中取出新块,为了腾出,Cache,空间，需要替换出一个,Cache,块,不唯一，则需要判断应替出哪块,18,CACHE,使用中的几个问题,CACHE,的重要技术指标：,命中率,影响,CACHE,命中率的因素,CACHE,的容量，大一些好,CACHE,与主存储器每次交换信息的单位量,(Cache Line Size),适中,CACHE,不同的组织方式，多路组相联更好,CACHE,的多级组织可提高命中率,CACHE,装满后的替换算法,19,cache,的容量与命中率的关系,Cache Size in KB,Hit Rate,20,cache line size,与缺失率的关系,cache,容量,21,多级的,cache,结构与命中率的关系,为增加计算机系统中的,cache,容量，通常可以在已有的,cache,存储器系统之外，再增加一个容量更大的,cache,。此时原有,cache,为第一级,cache,（例如奔腾机微处理机芯片内的,cache,），新增加的,cache,则成为第二级的,cache,。,第二级,cache,的容量比第一级,cache,的容量要大得多，在第一级,cache,中保存的信息也一定保存在第二级,cache,中，但保存有比第一级,cache,中更多的信息。当,CPU,访问第一级,cache,出现缺失情况时，就去访问第二级,cache,。,若第一级、第二级,cache,的命中率为,90%,，则它们合起来后的命中率为,-,（,-90,）,（,-90,）,=99,，而不会是,81,。,22,Cache,替换算法,随机替换（,RAND,）,随机找一个,Cache,块进行替换，比较盲目。,先进先出算法（,FIFO,）,将最早调入,Cache,的字块替换出去，采用循环电路容易实现，开销小。,最近最少使用算法（,LRU,）,需要计算字块的使用次数，开销大，但平均命中率比,FIFO,要高。,23,改写主存储器的策略,若,CPU,改写了,Cache,一单元内容（写命中）后且尚未改变主存相应单元内容，则出现数据不一致性。有两种解决办法：,直接改写主存单元内容（,Write Through,）,：,简便易行，数据一致性容易保证，但可能带来系统运行效率不高的问题，,Cache,对写操作没有提高性能。,拖后改写主存单元内容（,Write Back,）,：,一直拖到有另外的设备要读该内容过时的主存单元时，则首先停止这一读操作，接下来改写主存内容，之后再起动已停下来的读操作。矛盾是如何检查是否是读无效内存单元的操作，这是通过监视地址总线完成的，记下无效单元地址用于比较。控制复杂些，但可以提供更高的系统运行效率。,24,CACHE,接入系统的体系结构,侧接法：象入出设备似的连接到总线上，优点是结构简单，成本低，缺点是不利于降低总线占用率。,CPU,MEMORY,CACHE,Bus Master 1,Bus Master 2,总线,25,CACHE,接入系统的体系结构,隔断法：把原来的总线打断为两段，使,CACHE,处在两段之间。优点是有利于提高总线利用率，支持总线并发操作；缺点是结构复杂，成本较高。,CPU,MEMORY,Bus Master 1,Bus Master 2,总线,CACHE,26,本章主要内容,高速缓冲存储器（,Cache,）,高速缓存的基本运行原理,高速缓存的,3,种映像方式,高速缓存使用中的几个问题,虚拟存储器,虚拟存储器概述,段式存储管理,页式存储管理,27,虚拟存储器概述,虚拟存储器是指用磁盘的存储空间来弥补主存空间的不足，使得程序人员能够使用比主存实际空间更大的存储空间来编写和运行程序。,根据,“程序运行的局部性原理”,，只把一小段时间内用到的程序和数据装入主存；其他程序和数据在操作系统的支持下，在磁盘和主存之间按程序运行的需要自动成批量地完成交换。,虚拟存储器经常使用两种基本管理技术，核心问题都在于处理数据的存放与调度。,段式存储管理,页式存储管理,综合起来：段页式存储管理,28,段式存储管理,段,是程序模块化设计的结果，即把程序中逻辑上相对独立的部分设计为不同的段，再经过连接程序连接成更大的程序。此时用段作为信息调入主存的单位是合适的，以段为单位分配与管理主存储器被称为段式存储管理。,段式存储管理的核心问题在于设立和管理,段表,；段表也是主存中的可再定位的一段信息，用于变换程序中的,虚地址（逻辑地址）,为主存单元的,实地址（物理地址）,。,29,段式存储管理,30,段表内容及其管理,段号 段内地址,+,+,逻辑地址,段始地址,段长 装入位,段,表,主存实际地址,段表基地址,31,段式存储管理,提高性能的方法,使用段地址寄存器，保存一段的起始地址，以后使用这一段的数据不必再查段表，直接计算主存地址,段式存储管理的特点,优点：段的分界与程序的自然分界对应,段逻辑上的独立性有利于内存保护,便于实现对段的信息共享,缺点,段长不确定，主存分配和管理不便,容易在段间形成难以利用的碎片,32,页式存储管理,页,式存储管理是把虚拟空间和主存空间都分成大小相同的页（为,2,的整数幂个字），并以页为单位进行虚存与主存间的信息交换。此时虚存逻辑地址和主存物理地址分别被分为“,虚存页号,页内地址”和“,主存页号,页内地址”，,虚、实二页号,会不同，但使用相同的页内地址。,与段式存储管理不一样，页不是程序本身的结构特性，而是从管理的角度人为划分的结果。设置和管理好,页表,是页式存储管理的关键技术。,33,页式存储管理,34,页表内容和页式管理,+,（在内存中）控制位 有效位,页表,虚地址,(,程序中给出,),实地址,(,读写内存用,),按地址读,实页号,虚页号 页内地址,实页号 页内地址,页表基地址,控制位：包括修改位、替换位,有效位：表示该页是否已装入主存,35,页式存储管理,页式存储管理的特点,优点：只要有空白页新页就可以调入内存,只有程序的最后一页可能有零头浪费,缺点：页不是逻辑上的独立程序实体,处理、保护和共享信息不如段式方便,提高性能的方法,为了克服读取一次数据访问两次内存的问题,(,一次查页表,一次读内存,),，引入,快速页表（转换旁路缓冲器,TLB,：,translation,lookaside,buffer,）,TLB,完全由快速硬件实现，但容量较小，采用类似于,Cache,的关联存储器方式进行访问,36,页表内容和页式管理,+,（在内存中）控制位 有效位,虚 页号 实 页号,慢表,虚地址,(,程序中给出,),实地址,(,读写内存用,),快表,(,专设硬件,),比较,(,按内容选,),按地址读,实页号,虚页号 页内地址,实页号 页内地址,页表基地址,37,虚拟存储器与高速缓冲存储器区别,Cache,虚拟存储器,功能,提高了主存储器的速度