第03章存储系统(4cache及虚拟存储器)PPT课件

第三章存储系统,存储器概述,随机读写存储器RAM,半导体只读存储器ROM,高速存储器,虚拟存储器,cache存储器,.,2,何谓程序访问的局部性原则？,程序对存储空间90%的访问局限于存储空间的10%区域中，而另外10%的访问则分布在存储空间其余90%的区域中，这即为访存局部性规律。,3.5Cache存储器,.,3,3.5.1Cache基本原理,解决CPU和主存之间速度不匹配采用的一项重要技术一、Cache的工作机制Cache的工作机制基于程序访问的局部性原则。一个运行程序的代码大都顺序存放在地址连续的存储器中，与程序相关的数据在存储器中也相对集中。所以程序运行时，尤其有循环程序和子程序时，在较短时间区间内，常会对局部范围的存储器频繁访问，而此范围之外的地址访问甚少。这种现象称为程序访问的局部性。把局部范围的主存内容从主存放到一个高速小容量存储器中，使CPU在这一段时间内直接访问它，以减少或不去访问慢速的主存，程序运行速度明显提高。,.,4,二、Cache及特点,位于CPU与主存之间；Cache容量小于主存容量；Cache速度比主存速度快510倍Cache由快速半导体元件构成(高速SRAM芯片)Cache是主存部分内容的复制全部功能由硬件实现,对程序员来说,Cache是透明的.,.,5,三、Cache存储器的构成,了解构成及工作原理必须首先了解“块”的概念。Cache存储器中，把cache和主存各分成若干块。主存与cache中块的数目不同但块的大小相等。块的大小通常以在主存的一个读/写周期中能访问的数据长度为限，常为几十字节。,1、Cache的基本工作原理,CPU,主存,主存地址寄存器MA,主存Cache地址变换机构,Cache存储器,Cache地址寄存器,替换算法控制部件,AB,DB,单字宽,多字宽,不命中,命中,(块),未满,已满,2.Cache的工作过程(1)CPU送出访问单元的地址由AB打入Cache存储器的MA,由主存-Cache地址变换机构判断该单元内容是否已在Cache中存有副本,如果副本已在Cache中,称为命中;否则,称为不命中.(2)当命中时,把访问地址变换为它在Cache的地址,然后驱动Cache存储体,当是读操作时,CPU从Cache中直接读取信息,若为写操作,应注意Cache与主存数据的一致性(3)当不命中时,CPU转去直接访问主存,若为读操作,CPU从主存读取信息的同时,Cache控制部件把该地址所在那块存储内容从主存一次调进Cache存储器.不命中时,若为写操作,许多计算机系统只向主存写信息,不必同时把这个地址所在的整块存储内容再调入Cache中.注意:CPU与Cache之间的数据交换是以字为单位;而Cache与主存之间的数据交换是以块为单位.,3.5.2主存与cache的地址映射（映象）和地址变换,地址映象:将主存块按照某种规则或方法装入或定位在Cache中。地址变换:是将主存地址变换成Cache地址，从而访问Cache。在高速缓冲存储器当中,把Cache和主存机械等分为相同大小的块,每一块是由若干个字(或字节)组成.例：某机主存容量为1MB,划分为2048块,每块512B;Cache容量为8KB,划分为16块,每块512B,块0块1块15,Cache,块0块1块2047,主存,m位,块,字0,字1,字511,1.全相联映射方式允许主存中的每一个字块映象到Cache的任何一个字块位置上,优点:块冲突概率最低,只有当Cache中全部装满后,才有可能出现块冲突,灵活缺点:查找时间长,速度慢,块0块1块15,Cache,块0块1块2047,主存,块0块1块2047,主存,11位,主存块号,块内地址,主存地址,11位,9位,块0块1块15,Cache,0000,0001,1111,相联存储器,主存块号,Cache块号,块内地址,Cache地址,4位,9位,全相联映射,比较,2.直接映象主存第j块和Cache第i块有如下函数关系:i=jmodm(m为Cache中总块数),块0块1块15,Cache,.,.,.,0组,1组,127组,块0,块1,块15,块0,块1,块15,块15,主存,优点:硬件简单,成本低缺点:块冲突率很高,块0块1块15,Cache,.,.,.,0组,1组,127组,块0,块1,块15,块0,块1,块15,块15,主存,块内地址,主存地址,9位,主存组号,7位,块号,7位,存储器,主存组号,4位,块内地址,Cache地址,9位,块号,4位,0000,0001,1111,比较,直接映象,例:设一个Cache中有8个块,访问主存进行读操作的块地址序列为22、26、22、26、16、4、16、18，求每次访问后Cache中的内容,地址,命中与否,地址转换关系,22不命中22MOD8=6,22命中22MOD8=6,26命中26MOD8=2,16不命中16MOD8=0,4不命中4MOD8=4,16命中16MOD8=0,18不命中18MOD8=2,直接映象下Cache访问情况,26不命中26MOD8=2,直接映象的块分配情况,访问顺序12345678地址222622261641618块分配情况,22,操作状态,调进,22,26,调进,22,26,命中,22,26,命中,22,26,16,调进,22,4,16,26,调进,22,16,26,4,命中,22,16,18,4,替换,0,1,2,3,4,5,6,7,块号,.,15,设有一个Cache的容量为2K字,每块16字,求:(1)该Cache可容纳多少个块?(2)如果主存的容量为256K字,则有多少个块?(3)在直接映象方式下,主存的地址格式?Cache的地址格式?(4)在直接映象方式下,主存中的第I块映象到Cache中哪一块?,作业,3、组相联映象Cache与主存均分组，主存再分区，主存中任一区的某一组号与Cache的相应组号有固定的映象关系(组间直接映射)，但主存组内的块可自由映象到对应的Cache组中任一块(组内全相联映射),块0块1块1块0块0块0块1,主存,0组,1组,7组,块0块1块0块1块0块1,Cache,0组,1组,7组,块0,块1,7组,0区,块内地址,7位3位1位9位,组号,组内块号,主存地址,区号,块内地址,3位1位9位,组号,组内块号,Cache地址,8位,0,7,相联存储器,区号,块号,8组之一,块0块1块1块0块0块0块1,主存,0组,1组,7组,块0块1块0块1块0块1,Cache,0组,1组,7组,块0,块1,7组,0区,128区,比较,块0块1,.,18,1、先进先出（FirstInFirstOutFIFO）算法替换出最早进入Cache的信息块2、最不经常使用（LeastFrequentlyUsedLUF）算法替换掉访问次数最少的信息块3、近期最少使用（LeastRecentlyUsedLRU）算法替换掉近期最少使用的信息块4、随机（RandomRAND）算法用随机数发生器来产生需替换的块号,3.5.5Cache替换算法,Cache替换算法例：访问Cache的地址流顺序为：232152453252，假设只有3块Cache,3.5.4Cache的写操作策略,如何保证cache内容与主存中“原本”内容相一致（只有“写”操作才有的问题）常见的写操作策略有：1、全写法、写直达法（WriteThrough）：命中时，不仅写cache，也同时写入主存。2、回写法（WriteBack）：命中时，只改写cache的内容，而并不立即修改主存中相应单元的内容，只有在被改写过的块将被替换出去时才一次写回主存。3、写一次法处理方法和回写法基本相同,只是第一次写命中时要同时写入主存。是全写法和回写法的结合。,Cache的命中率设Nc为Cache完成存取的总次数,Nm为主存完成存取的总次数,h为命中率,则有:h=Nc/(Nc+Nm)若tc表示命中时的Cache访问时间(即Cache存储周期),tm表示未命中时的主存访问时间(即主存存储周期),1-h表示未命中率,则Cache/主存系统的平均访问时间ta为:ta=htc+(1-h)tm设r=tm/tc表示主存慢于Cache的倍率,e表示访问效率,则有:e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h例:已知Cache存储周期为40ns,主存存储周期为200ns,Cache/主存系统平均访问时间为50ns,求Cache的命中率是多少?解:因为ta=htc+(1-h)tm所以h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16,.,22,Cache的容量讨论,增加Cache的容量，显然会提高命中率，但两者之间并非成正比关系。比如：VAX-11/7504KBCache90%命中率VAX-11/7808KBCache95%命中率所以Cache一般为几KB几十KB,.,23,3.6虚拟存储器3.6.1虚拟存储器的基本概念,一、什么叫虚拟存储器（VirtualMemory）为了克服内存空间不足而提出。虚拟存储器是建立在主存辅存物理结构的基础之上，由附加的硬件装置及操作系统存储管理软件组成的一种存储体系。它将主存和辅存的物理空间统一编址，形成一个庞大的存储空间，用户可在其中自由编程，感到的不再是处处受主存容量限制的存储系统。但是，实质上CPU仍只能执行调入主存的程序，所以称这种存储体系为虚拟存储器。,主存页号,主存地址空间,虚存页号,程序地址空间,0,1,3,2,4,0,1,2,7,实际的主存单元地址叫做实地址（物理地址、主存地址），对应的空间叫做实存空间（物理空间、主存空间）。虚地址实地址变换,二、虚地址和实地址（VA：VirtualAddress，PA：PhysicalAddress）引入虚拟存储器后用户编程时使用的指令地址叫做虚地址（逻辑地址），该地址允许涉及的空间范围叫做虚存空间（逻辑空间）。,辅存的物理空间,三、虚拟存储器与cache存储器比较认识是两个不同层次的存储体系。两者在概念上有许多共同之处：1、程序划分为信息块；2、程序运行时，信息块自动从慢速存储器向快速存储器调度；3、块的调出都采用一定的替换策略；4、新块的调入按一定的映射关系确定调入的位置。,两者也有许多不同之处：1、Cache存储器采用与CPU速度相匹配的快速存储元件弥补了主存和CPU之间的速度差距；而虚存的主要功能是用来弥补主存和辅存之间的容量差距。2、两个存储体系均以信息块作为存储层次之间信息传送的单位，但cache与主存每次传送的信息块定长，常为几十个字节；而主存和辅存之间即虚拟信息块的划分却有多种方案：页、段等，块长通常为几百几百K字节。3、CPU访问cache比访问慢速主存快510倍；而虚存中主存速度比辅存快1001000倍；（辅存向主存调块时间为ms级）。4、主存-cache体系中，CPU与二者都有直接的通路；而虚存中辅存与CPU之间无直接通路。5、Cache存储器存取信息、地址变换和替换策略全部用硬件实现;虚存基本由操作系统的存储管理软件辅助一些硬件进行块的划分及主-辅间调度。,3.6.2页式虚拟存储器以页为基本信息传送单位的虚存一、页的划分及页式虚存的虚、实地址形式将主存和虚存空间分成大小相等的页，一页为512几K字节。,例：主存容量64K，地址16位，一页长2K字节，共32页,0000000000000000,0000011111111111,0000100000000000,0000111111111111,0001000000000000,0001011111111111,0001100000000000,1111011111111111,1111100000000000,1111111111111111,主存空间,第0页,第1页,第2页,第31页,2K,2K,2K,2K,实地址,实地址形式：,实页号,页内地址,类似有虚地址形式：,虚页号,页内地址,二、页表（PageTable）：建立一张虚地址页号与实地址页号的对照表,记录程序的虚页面调入主存时被安排在主存的位置,并登记一些有关页面的控制信息,这张表称为页表,.0虚页1虚页2虚页.,虚存空间,.4页面.8页面.19页面.,内存空间,1004111191008,装入位,修改位,替换位,其它,实页号,控制位,页表首地址,页表基地址寄存器,0虚页,1虚页,2虚页,程序A,例：程序A有3个虚页，其页表及虚、实空间定位如下：,三、虚-实地址变换,+,实页号页内地址,变换后的实地址（主存地址）,虚页号页内地址,程序地址(虚地址),来自CPU,收到来自CPU的程序地址后，判断,若该页在主存中，确定其页面号,若该页不在主存中，从辅存调入,控制位,实页号,.,30,四、页式虚存的特点,1、页长固定，可以顺序编号，故页表设置灵活。主存只要有空页即可调度，操作简单。2、页长固定会造成空间的“零头”浪费；机械地划分页也无法顾及程序的内部结构，指令、数据跨页的状况将增加查表的次数。,页表,0001,0011,1100,007H,300H,307H,练习：已知页式虚存中，某程序一条指令的虚地址是000001111111100000，该程序页表起始地址为0011，页面大小为1K，下列内存单元末4位状态如图：指出该指令虚地址变换后的实地址。,解：分为218/210=28页。即虚页号(高八位):00000111页内地址:1111100000查表:001100000000+00000111=307H实地址为：11001111100000,12位（页表起始地址0011后加8个0）,例(P125.11):主存容量为4MB,虚存容量为1GB,则虚拟地址和物理地址各为多少位?如果页面大小为4KB,则页表长度是少?解:因为:1KB=210B1MB=220B1GB=230B所以,虚拟地址为30位,物理地址为22位.如果页面大小为4KB=212B,则虚存分为218页,虚存地址格式为:,虚页号,页内地址,0,11,12,29,物理分为210页,物理地址格式为:,页内地址,实页号,0,11,12,21,页表长度为:218(页表中每页要占用一行的信息描述),.,33,3.7.3段式管理,段式管理：以程序的逻辑结构所形成的段（如过程、子程序等）作为主存的分配单位虚段：程序空间的段实段：主存中的段段表：虚段与实段之间关系的对照表，存放在内存中,程序段空间(外存),长度,1K,2K,3K,1K,2K,段0,段1,段2,段3,段4,段起址,装入位,段长,段号,0,1,2,3,4,1000,6120,9192,2024,1,0,1,1,1,1K,3K,1K,2K,实主存空间,地址,1000,2023,2024,4071,未用,4072,6119,6120,9191,9192,10215,段0,段4,段2,段3,未用,段式虚拟存储器地址变换,段表,实段,虚段,.,35,3.6虚拟存储器,3.6.3段式管理-虚、实地址变换,段表基址,+,+,由段表确定所要访问的虚段是否调入主存，判断,未从辅存调入,调入确定其在主存的位置,段号,0,1,2,.,36,一、段式、页式管理比较段式管理易于编译、修改和保护，页式管理相对困难段式管理可以实现程序和数据共享页式管理主存空间易分配，段式管理困难二、段页式管理程序按逻辑结构分段，每段再分成大小固定的页每个程序有一张段表，各段有一张相应的页表CPU访存时，先查段表找该段页表地址再查页表找对应的主存地址,3.7.4段页式管理,(a),地址映象关系,段基址表,段表,页表,0,0,0,.,N,-,1,L,-,1,M,-,1,段表长度,段表基址,装入位,段长,页表地址,(b),地址映象方法,页内地址,页内地址,虚页号,实页号,段号,基号,1,M,1,L,主存地址空间,程序地址空间,A,段,B,段,虚地址,实地址,段,页,装入位,.,实页号,.,38,3.6.5虚拟存储器管理,调度方法：按需调页，程序的各页仅在需要时才调入主存映象方式：全相联映象、直接映象、组相联映象替换策略：先进先出（FirstInFirstOutFIFO）近期最少使用算法（LeastRecentlyUsedLRU）,例:假设主存只有a,b,c三个页框,组成a进c出的FIFO队列,进程访问页面的序列是0,1,2,4,2,3,0,2,1,3,2号,用列表法求出采用FIFO+LRU和FIFO替换策略时的命中率.解:,页面访问序列,0,1,2,4,2,3,0,2,1,3,2,FIFO算法,FIFO+LRU算法,a,b,c,a,b,c,0,1,0,2,1,0,4,2,1,4,2,1,3,4,2,0,3,4,2,0,3,1,2,0,3,1,2,3,1,2,命中率,2/11=18.2%,命,命,0,1,0,2,1,0,4,2,1,2,4,1,3,2,4,0,3,2,2,0,3,1,2,0,3,1,2,2,3,1,3/11=27.3%,命,命,命,FIFO+LRU算法：未命中时,以“先进先出”进行淘汰,一旦命中,将命中项置