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

高速缓冲存储器和虚拟存储器第一页，共四十页，2022年，8月28日本章主要内容高速缓冲存储器（Cache）高速缓存的基本运行原理高速缓存的3种映像方式高速缓存使用中的几个问题虚拟存储器虚拟存储器概述段式存储管理页式存储管理2第二页，共四十页，2022年，8月28日微电子技术发展趋势CPU与DRAM性能比较3第三页，共四十页，2022年，8月28日程序的局部性原理程序在一定时间段内通常只访问较小的地址空间两种局部性：时间局部性和空间局部性时间局部性：最近被访问的信息很可能还要被访问。将最近被访问的信息项装入到Cache中。空间局部性：最近被访问的信息临近的信息也可能被访问。将最近被访问的信息项临近的信息一起装入到Cache中。地址空间访问概率4第四页，共四十页，2022年，8月28日高速缓冲存储器（Cache）用途：设置在CPU和主存储器之间，完成高速与CPU交换信息，尽量避免CPU不必要地多次直接访问慢速的主存储器，从而提高计算机系统的运行效率。实现：这是一个存储容量很小，但读写速度更快的，以关联存储器方式运行、用静态存储器芯片实现的存储器系统。要求：有足够高的命中率，既当CPU需用主存中的数据时，多数情况可以直接从CACHE中得到，称二者之比为命中率。5第五页，共四十页，2022年，8月28日CACHE的基本运行原理Cache存储单元的组成部分数据字段：保存从主存单元复制过来的数据标志字段：保存相应主存单元的地址信息有效位字段：标识数据字段和标志字段是否有效提高Cache性能，降低成本Cache单元的大小：cachelinesize（几个主存字，减少标志位位数，较少Cache总容量）Cache与主存交换数据的单位：cachelinesize（充分利用空间局部性）Cache单元与主存单元的对应关系，例如：完全随意对应、一对多硬性对应和多对多有限随意对应Cache的容量、分层组织、接入方式等方面6第六页，共四十页，2022年，8月28日CACHE的基本运行原理MEMORYCACHECONTROL数据总线译码选一单元比较选一行读过程为例地址总线ADDRDATACACHE

CPU

7第七页，共四十页，2022年，8月28日CACHE的3种映像方式地址映像：把一主存单元的数据复制到CACHE中时，还要把该主存单元的地址，经过某种函数关系处理后写进CACHE的标志字段，这一过程被称为CACHE的地址映像。地址变换：在程序执行时，还要把主存地址变换为访问CACHE的地址，这一过程被叫做CACHE的地址变换。CACHE存储器通常使用3种映像方式，它们是全相联映像方式、直接映像方式、多路组相联映像方式，3种映像方式有各自的优缺点。8第八页，共四十页，2022年，8月28日全相联映像方式全相联映像方式：是指主存的一个字块可以映像到整个CACHE的任何一个字块中。全相联映像方式特点：主存的字块可以和Cache的任何字块对应，利用率高，方式灵活。标志位较长，比较电路的成本太高。如果主存空间有2m块，则标志位要有m位。同时，如果Cache有n块，则需要有n个比较电路。使用成本太高9第九页，共四十页，2022年，8月28日全相联映像方式CPU数据主存字块标记有效位主存储器CACHE比较译码标志数据主存字块标记块内地址主存地址10第十页，共四十页，2022年，8月28日全相联硬件实现举例11第十一页，共四十页，2022年，8月28日直接映像方式直接映像方式：是指主存的一个字块只能映像到CACHE的一个准确确定的字块中。直接映像方式特点：主存的字块只可以和固定的Cache字块对应，方式直接，利用率低。标志位较短，比较电路的成本低。如果主存空间有2m块，Cache中字块有2c块，则标志位只要有m-c(2m/2c)位。且仅需要比较一次。利用率低，命中率低，效率较低12第十二页，共四十页，2022年，8月28日直接映像方式CPU数据有效位主存储器CACHE比较译码译码cache字块地址主存字块标记标志数据主存字块标记块内地址主存地址cache字块地址13第十三页，共四十页，2022年，8月28日直接映像硬件实现举例14第十四页，共四十页，2022年，8月28日多路组相联映像方式多路组相联映像方式：是对全相联映像和直接映想象的一种折衷的处理方案。既不在主存和CACHE之间实现字块的完全随意对应，也不在主存和CACHE之间实现字块的多对一的硬性对应，而是实现一种有限度的随意对应。

多路组相联映像方式特点：折衷方案。组间为全相连，组内为直接映像。集中了两个方式的优点。成本也不太高。最常用的CACHE映像方式15第十五页，共四十页，2022年，8月28日组地址两路组相联映像方式CPU数据有效位主存储器CACHE译码比较比较译码译码标志数据主存地址主存字块标记块内地址组地址主存字块标记16第十六页，共四十页，2022年，8月28日多路组相联硬件实现举例17第十七页，共四十页，2022年，8月28日三种映像方式比较全相联映射主存中的一块可以映射到Cache中任何一个位置直接映像主存中的一块只能映射到Cache中唯一的一个位置定位时，不需要判断，只需替换多路组相联映射主存中的一块可以选择映射到Cache中多个位置全相联映射和多路组相联映射的失效处理从主存中取出新块为了腾出Cache空间，需要替换出一个Cache块不唯一，则需要判断应替出哪块18第十八页，共四十页，2022年，8月28日CACHE使用中的几个问题CACHE的重要技术指标：命中率影响CACHE命中率的因素CACHE的容量，大一些好CACHE与主存储器每次交换信息的单位量(CacheLineSize)适中CACHE不同的组织方式，多路组相联更好CACHE的多级组织可提高命中率CACHE装满后的替换算法19第十九页，共四十页，2022年，8月28日cache的容量与命中率的关系CacheSizeinKBHitRate20第二十页，共四十页，2022年，8月28日

cachelinesize与缺失率的关系

cache容量

21第二十一页，共四十页，2022年，8月28日多级的cache结构与命中率的关系为增加计算机系统中的cache容量，通常可以在已有的cache存储器系统之外，再增加一个容量更大的cache。此时原有cache为第一级cache（例如奔腾机微处理机芯片内的cache），新增加的cache则成为第二级的cache。第二级cache的容量比第一级cache的容量要大得多，在第一级cache中保存的信息也一定保存在第二级cache中，但保存有比第一级cache中更多的信息。当CPU访问第一级cache出现缺失情况时，就去访问第二级cache。若第一级、第二级cache的命中率为90%，则它们合起来后的命中率为１-（１-90％）×（１-90％）=99％，而不会是81％。22第二十二页，共四十页，2022年，8月28日Cache替换算法随机替换（RAND）随机找一个Cache块进行替换，比较盲目。先进先出算法（FIFO）将最早调入Cache的字块替换出去，采用循环电路容易实现，开销小。最近最少使用算法（LRU）需要计算字块的使用次数，开销大，但平均命中率比FIFO要高。23第二十三页，共四十页，2022年，8月28日改写主存储器的策略若CPU改写了Cache一单元内容（写命中）后且尚未改变主存相应单元内容，则出现数据不一致性。有两种解决办法：直接改写主存单元内容（WriteThrough）：简便易行，数据一致性容易保证，但可能带来系统运行效率不高的问题，Cache对写操作没有提高性能。拖后改写主存单元内容（WriteBack）：一直拖到有另外的设备要读该内容过时的主存单元时，则首先停止这一读操作，接下来改写主存内容，之后再起动已停下来的读操作。矛盾是如何检查是否是读无效内存单元的操作，这是通过监视地址总线完成的，记下无效单元地址用于比较。控制复杂些，但可以提供更高的系统运行效率。24第二十四页，共四十页，2022年，8月28日CACHE接入系统的体系结构侧接法：象入出设备似的连接到总线上，优点是结构简单，成本低，缺点是不利于降低总线占用率。CPUMEMORYCACHEBusMaster1BusMaster2总线25第二十五页，共四十页，2022年，8月28日CACHE接入系统的体系结构隔断法：把原来的总线打断为两段，使CACHE处在两段之间。优点是有利于提高总线利用率，支持总线并发操作；缺点是结构复杂，成本较高。CPUMEMORYBusMaster1BusMaster2总线CACHE26第二十六页，共四十页，2022年，8月28日本章主要内容高速缓冲存储器（Cache）高速缓存的基本运行原理高速缓存的3种映像方式高速缓存使用中的几个问题虚拟存储器虚拟存储器概述段式存储管理页式存储管理27第二十七页，共四十页，2022年，8月28日虚拟存储器概述虚拟存储器是指用磁盘的存储空间来弥补主存空间的不足，使得程序人员能够使用比主存实际空间更大的存储空间来编写和运行程序。根据“程序运行的局部性原理”，只把一小段时间内用到的程序和数据装入主存；其他程序和数据在操作系统的支持下，在磁盘和主存之间按程序运行的需要自动成批量地完成交换。虚拟存储器经常使用两种基本管理技术，核心问题都在于处理数据的存放与调度。段式存储管理页式存储管理综合起来：段页式存储管理28第二十八页，共四十页，2022年，8月28日段式存储管理段是程序模块化设计的结果，即把程序中逻辑上相对独立的部分设计为不同的段，再经过连接程序连接成更大的程序。此时用段作为信息调入主存的单位是合适的，以段为单位分配与管理主存储器被称为段式存储管理。段式存储管理的核心问题在于设立和管理段表；段表也是主存中的可再定位的一段信息，用于变换程序中的虚地址（逻辑地址）为主存单元的实地址（物理地址）。29第二十九页，共四十页，2022年，8月28日段式存储管理30第三十页，共四十页，2022年，8月28日段表内容及其管理段号段内地址++逻辑地址段始地址段长装入位段表主存实际地址段表基地址31第三十一页，共四十页，2022年，8月28日段式存储管理提高性能的方法使用段地址寄存器，保存一段的起始地址，以后使用这一段的数据不必再查段表，直接计算主存地址段式存储管理的特点优点：段的分界与程序的自然分界对应段逻辑上的独立性有利于内存保护便于实现对段的信息共享缺点段长不确定，主存分配和管理不便容易在段间形成难以利用的碎片32第三十二页，共四十页，2022年，8月28日页式存储管理页式存储管理是把虚拟空间和主存空间都分成大小相同的页（为2的整数幂个字），并以页为单位进行虚存与主存间的信息交换。此时虚存逻辑地址和主存物理地址分别被分为“虚存页号＋页内地址”和“主存页号＋页内地址”，虚、实二页号会不同，但使用相同的页内地址。与段式存储管理不一样，页不是程序本身的结构特性，而是从管理的角度人为划分的结果。设置和管理好页表是页式存储管理的关键技术。33第三十三页，共四十页，2022年，8月28日页式存储管理34第三十四页，共四十页，2022年，8月28日页表内容和页式管理+（在内存中）控制位有效位页表虚地址(程序中给出)实地址(读写内存用)按地址读实页号虚页号页内地址实页号页内地址页表基地址控制位：包括修改位、替换位有效位：表示该页是否已装入主存35第三十五页，共四十页，2022年，8月28日页式存储管理页式存储管理的特点优点：只要有空白页新页就可以调入内存只有程序的最后一页可能有零头浪费缺点：页不是逻辑上的独立程序实体处理、保护和共享信息不如段式方便提高性能的方法为了克服读取一次数据访问两次内存的问题(一次查页表,一次读内存)，引入快速页表（转换旁路缓冲器TLB：translationlookasidebuffer）TLB完全由快速硬件实现，但容量较小，采用类似于Cache