计算机系统结构第4章 存储系统

计算机系统结构教程陈嘉多媒体教学课件福州大学软件学院存储系统的层次结构与性能指标存储系统的设计目标：以较小的成本使存储系统的工作速度与处理机的速度相匹配，同时要求存储系统有尽可能大的容量。程序访问局部性：时间局部性：程序在最近的未来要用到的信息很可能是现在正在使用的信息。（如循环程序）空间局部性：程序在最近的未来要用到的信息很可能同现在正在使用的信息在存储空间位置上相邻近。（如顺序执行程序,数据聚族存储）存储系统的多级层次结构：M1(T1,S1,C1)M2(T2,S2,C2)Mn(Tn,Sn,Cn)…T1<T2<…<Tn存储器访问周期S1<S2<…<Sn存储容量C1>C2>…>Cn单位容量平均价格通过程序访问局部性原理使存储系统的等效访问速度接近于M1的访问速度存储系统的容量为Mn的容量，每位价格接近于Mn的每位价格程序局部性不仅使层次结构的存储系统在速度、容量和价格的综合水平较高，而且可对存储空间采用分块或分页的管理方式来获得对M1较高的命中率由于程序访问的时间和空间局部性，从而保证对M1有较高的命中率存储系统层次结构要解决的问题：定位问题寻址问题替换问题写回问题三级存储系统Cache内存辅存Cache存储器虚拟存储器虚拟存储器(主存-辅存存储系统)是针对主存容量不能满足要求而提出的，对应用程序员透明，对系统程序员不透明。虚拟存储器的等效访问速度接近于主存访问速度，容量却是辅存的容量，每位价格接近辅存的每位价格Cache存储器(Cache-主存存储系统)是针对主存速度不能满足要求而提出的，对应用程序员和系统程序员都透明。虚拟存储器在主存和辅存之间增加辅助的硬、软件，使主存和辅存构成一个整体Cache存储器的等效访问速度接近于物理Cache的访问速度，其容量却是主存的容量，每位价格接近主存的每位价格在物理Cache和主存之间增加辅助硬件，使Cache和主存构成一个整体存储系统的性能指标：存储容量“Cache-主存”存储系统

存储系统的容量就是主存的容量“主存-辅存”存储系统虚拟地址空间的容量虚拟地址空间既不是主存的地址空间，也不是辅存的地址空间，这个虚拟地址空间比主存的实际地址空间大得多，并采用像主存一样的随机访问方式存储系统带宽存储器最大带宽—每秒从存储器进出信息的最大数量（若存储周期200ns，存储字为32位，则存储器带宽为160M位/秒）存储器带宽—存储器被连续访问时能提供的数据传输速率

实际带宽<最大带宽单位容量平均价格C=C1S1+C2S2S1+S2S1<<S2，CC2如果S1与S2相差太大，则会使得对M1的命中率很低要使C接近于C2，还应使增加的辅助软硬件价格只占价格中很小比例，否则性价比将会显著降低命中率命中率—由CPU产生的逻辑地址在存储器M1中访问到指定信息的概率

H=N1N1+N2与命中率相关的因素程序的访存地址流采用的M1和M2之间的地址映像关系采用的块或页面替换算法

M1的容量等效访问周期T=HT1+(1-H)T2H1,TT1访问效率e=T1T1H+(1-H)T2/T1=访问效率与命中率和两级存储器的访问周期比有关存储系统的透明性要求地址变换和替换算法对程序员都应是透明的，这种透明性由对存储系统进行管理的硬件和软件自动实现地址映象虚拟地址与物理地址间对应关系的规则地址变换虚拟存储系统按照某种地址映象方式把虚拟地址转换成物理地址相邻层之间的数据传送单位

CPU与高速缓存之间：字

高速缓存与主存储器之间：块（每块32个字节）主存与磁盘之间：页面（每页4K字节，包括128块）磁盘与磁带之间：段并行存储器并行存储器—通过设置多个存储器或存储体，使它们并行工作，在一个存储器访问周期能并行访问到多个存储字单体多字并行存储器把存储器的存储字字长增加n倍，以存放n个指令字或数据字，从而在一个存储周期内能访问到n个指令字或数据字，最大带宽比单体单字存储器的最大带宽提高n倍优点：实现简单缺点：访问冲突概率大取指令冲突一个存储字中有一个转移指令字时，转移指令后预取的指令字只能作废读操作数冲突单体多字并行存储器一次取出的n个数据字不一定都是要执行的指令所需要的操作数，而当前执行指令需要的全部操作数也可能不包含在一个存储字中而不能被一次取出数据存放的随机性比指令存放的随机性大，所以读操作数冲突的概率较大写数据冲突必须凑齐n个数据字后才能作为一个存储字一次写入存储器。需要先把属于一个存储字的n个数读到数据寄存器中，然后再把整个存储字写回存储器读写冲突在要读出的数据字和要写入的数据字同处于一个存储字时，读和写的操作就无法在同一个存储周期中完成交叉访问存储器由多个存储体组成一个更大容量的主存时，对存储器的多个存储体的存储单元采用交叉编址方式，组成交叉访问存储器高位交叉访问存储器高位(体号k)低位(体内地址j)log2m位log2n位A=k*n+j(0=<j<n,0=<k<m)k=A/nj=Amodn由m个存储体组成，每个存储体的容量均为n个字缺点：由于程序的连续性和局部性，在程序执行过程中被访问的指令序列和数据绝大多数会分布在同一存储体中，引起访问冲突优点：有利于扩大常规主存容量MBRMAR存储体0MBRMAR存储体1MBRMAR存储体n-1000000000000000100ffffff010000000100000101ffffffff000000ff000001ffffffff………………译码器……高位(体号)低位(体内地址)地址寄存器高位(体内地址j)低位(体号k)log2n位log2m位A=j*m+k(0≤j<n,0≤k<m)j=A/mk=Amodm低位交叉访问存储器由m个存储体组成，每个存储体的容量均为n个字优点：避免了顺序执行程序和顺序读取指令时存储体的访问冲突缺点：不便于主存容量的扩充，在执行转移指令或随机访问数据时仍会产生访问冲突按m个连续的存储单元地址访问存储器，将对m

个不同的存储体中各自一个存储单元进行访问，即在一个存储器访问周期中访问了m个存储单元MBRMAR存储体0MBRMAR存储体1MBRMAR存储体n-10000000000000100ffffff000000000100000101ffffff01000000ff000001ffffffffff………………译码器……高位(体内地址)低位(体号)地址寄存器无冲突访问存储器一维数组的无冲突访问在低位交叉访问存储器中，由于程序中的转移指令和数据访问的随机性仍可能产生访问存储体的冲突a0a1a2a3a4a5a6a7a8a9a10a11…………0号体1号体2号体3号体0123体内地址变址位移量访问4个元素的冲突情况1无冲突2一半冲突3无冲突4全冲突通常把存储体的个数n选为质数，变址位移量选为同n互质若存储体的个数与变址位移量互质，就不会产生一维数组的访问冲突二维数组的无冲突访问要求对存放在并行存储器中的二维数组按行，按列，按对角线，按反对角线访问均能实现无冲突访问a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a330号体1号体2号体3号体0123体内地址按列访问冲突！0号体1号体2号体3号体0123体内地址按对角线和反对角线访问冲突！a00a01a02a03a11a12a13a10a22a23a20a21a33a30a31a32体内地址=i体号=(j-i)%N0号体1号体2号体3号体0123体内地址a00a11a22a33a03a02a01a12a13a10a21a20a23a30a31a32按行，按列，按对角线及反对角线访问均不产生冲突。但需要对准网络把数组元素的地址变换成并行存储器的实际地址a00a02a03a01a13a11a10a12a21a23a22a20a32a30a31a330号体1号体2号体3号体0123体内地址a00a20a30a10a21a01a11a31a32a12a02a22a13a33a23a030号体1号体2号体3号体0123体内地址体号=2*(iL^jH)+(iH^iL^jL)(^为异或运算)体内地址=jP.Budnik和D.J.Kuck提出了一种能对n*n二维数组实现按行，按列，按对角线，按子对角线，按反对角线，并行访问数组中任意一个n0.5×n0.5子数组中的n个元素无冲突的存储方案：要求并行存储体的个数m≥n，且m取质数。二维数组的任意元素aij在无冲突并行存储器中的体号和体内地址分别为：体号=(2p*i+j+k)modm

体内地址=i其中，p是满足m=22p+1的任意自然数；k是数组第一个元素a00所在存储体的体号，一般取k=0。a00a01a02a03a13a10a11a12a21a22a23a20a30a31a32a330号体1号体2号体3号体4号体0123体内地址n=4,m=5，p=1，k=0存储空间的(m-n)/m被浪费，存储空间利用率不高m个存储体组成的并行存储器的最大带宽为fmax=mW/T，n*n的二维数组错位存储后，可达到的实际带宽为f=(n/m)fmax虚拟存储器虚拟存储器中的三种地址空间主存储器地址空间

由主存单元地址表示的可以随机访问的地址空间虚拟存储器为应用程序员提供一个比主存容量大得多的可以按接近主存的工作速度运行的存储空间虚拟地址空间既不是主存的地址空间，也不是辅存的地址空间，是由虚拟地址表示的，比主存的实际地址空间大得多且可以随机访问的空间辅存地址空间

由数据块的外部地址表示的顺序访问的地址空间虚拟存储器中的三种地址主存地址主存存储单元的地址辅存地址辅存上数据的存放地址虚拟地址程序经编译生成的访存地址地址映象

虚拟地址与主存物理地址间对应关系的规则地址变换

虚拟存储系统按照某种地址映象方式把虚拟地址转换成物理地址的过程

对应用程序员透明，由存储系统自动完成外部地址变换

将虚拟地址转换为磁盘存储器物理地址外部地址变换更多依靠软件实现

替换算法

当有新数据块调入主存，而主存已没有空闲位置时，需要采用某种替换算法确定新数据块调入主存的位置段式虚拟存储器的地址映象与地址变换由程序员将一个大的复杂程序划分为逻辑上相互独立的若干模块或它们的部分集合，这些模块称为段。每个程序段都从0开始编址(段内偏移)，段可长可短。段式管理：把主存空间按段进行分配的存储管理方式段表：存放程序的各段装入主存的相关信息

段长，起始地址，访问方式，装入位装入位表示要访问的程序段是否已经装入主存访问方式可以指出本程序段是否需要保护和保护的级别，例如允许读允许写，允许读禁止写每个程序都用一个段表来存放该程序的各段装入主存的有关信息段号段长起始地址01K8K150016K22009K320030KMainFunc1()Func2()Func3()8k9k16k30k主存储器用户程序段式虚拟存储器的地址映象用户号U段号S段内偏移D多用户虚地址Av6As段表长度段表基地址+012345段名起始地址装入位段长访问方式+主存实地址段表段表基址寄存器检查是否越界主存或磁盘0N-1AsCPU内有一个段表基址寄存器堆，每道程序使用其中的一个段表基址寄存器

如果装入位给出的信息表示要访问的段不在主存中，则称发生了段失效，那么不能将虚地址变换成主存实地址。需要从磁盘存储器中把该段读入主存，并在段表中填入该段的相关信息随着长度不等的段在主存中不断调入调出，主存中出现段间零头(不足以容纳一个段)，使主存空间利用率较低

可通过定时运行段间零头回收程序来合并段间零头成为一个连续空间，但将增加系统运行的时间开销段表中的起始地址字段的长度就是主存实地址的长度，段长字段的长度就是主存空间大小的表示长度，这两个字段都很长。这样既增加了段表本身的存储开销，又增加了虚实地址变换的时间开销。段式虚拟存储器的主要优点：(1)程序的模块化性能好。(2)便于程序和数据的共享。(3)程序的动态链接和调度比较容易。(4)便于实现信息保护。

段式虚拟存储器的主要缺点：地址变换所花费的时间比较长（做两次加法运算，访存读写段表的时间长）(2)主存储器的利用率往往比较低，易出现段间零头(3)对辅存（磁盘存储器）的管理比较困难，因为段长度不定，而磁盘是按固定的块来访问(4)段表所占的存储空间大页式虚拟存储器的地址映象与地址变换页式管理：把虚拟地址空间和主存地址空间都划分为同样大小的页面，程序以页为单位调入调出主存。虚拟空间的页称为虚页，主存空间的页称为实页。地址空间的页面划分和页面大小是由虚拟存储器的页式管理软硬件实现的虚页号主存页号0123…………0页1页2页3页……用户程序页表主存储器页式虚拟存储器的地址映象用户号U虚页号P页内偏移D多用户虚地址AvPa+1p装入位修改位主存页号各种标志实页号p页内偏移d页表页表基址寄存器主存实地址APa页表：在页式虚拟存储器中，每个程序都用一个页表来存放程序的各虚页装入主存实页位置的有关信息主存页号，修改位，装入位,…

一个虚页占用页表中的一行修改位表示对应的实页是否被修改。如果没有被修改，则在需要把该实页替换出主存时，不必把它写回到磁盘存储器去更新相应的页，只需用调入的新页来覆盖它即可。如果被修改过，替换时则需要把它先写回磁盘存储器。CPU内有一个基址寄存器堆，每道程序使用其中的一个基址寄存器存放该程序的页表在主存中的基地址

当一个虚地址变换成主存实地址时，需要变换的是把虚地址中的虚页号变换成实地址的实页号，从而大大缩短了要进行变换的地址长度，既节省了硬件和存储开销，又能加快地址变换的速度内部地址变换：一个用户程序要访问虚存时，必须先给出多用户虚拟地址Av，在操作系统和有关硬件共同管理下，首先进行内部地址变换，如果成功，则得到实页号P。如果不成功，则：外部地址变换：需要用软件实现，首先查外页表，得到与虚页号对应的磁盘存储器的实地址，然后查内页表（主存页表），看主存是否有空页。如有，把整页磁盘数据调入主存，修改页表。如果没有，则：页面替换：把主存中暂时不用的一页写回到磁盘存储器中原来的位置上磁盘存储器的地址格式磁盘号柱面号磁头号块号在操作系统中，把页面失效当作一种异常故障来处理。失效几率很低，1%，因此外部地址变换采用软件来实现每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有对应的一个存储字。每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。外部地址变换用户号U虚页号P页内偏移D多用户虚地址Av1装入位磁盘实地址磁盘号柱面号磁头号块号外部地址变换用软件实现外页表页式虚拟存储器的优点：主存空间利用率较高

页内零头远小于段间零头地址变换速度快只做一次地址加法运算页表的一行长度比段表的一行长度要短，读出和写入一行信息费时较少对辅存的管理容易，固定页对应固定块页式虚拟存储器的缺点：程序的链接和调度不方便一个程序代码段或数据块中可能先只有部分代码和数据调入主存，在主存中占用若干个不连续的实存空间模块化性能差，程序和数据的保护不方便对属于同一个程序段的多个页的访问方式标志要同样设置和同样修改由于每一个虚页都要占用页表的一行，导致页表行数很多，需占用很大主存空间段页式虚拟存储器的地址映象与地址变换段页式管理：对用户编写程序的虚拟空间采用分段方式管理，对主存的物理空间采用分页方式管理用户仍然按照逻辑分段来编写程序，但是虚拟空间到主存物理空间的映像是分页进行的段表：页表长度，页表起始地址，装入位，修改位，…

页表：实页号，修改位，装入位，…段号页表长度页表始址031322用户程序主存储器段表段0段1段2页号主存页号031128页号主存页号05113217页号主存页号01011401234567891011121314151617段0的页表段1的页表段2的页表12K10K5K用户号U段号S虚页号P页内偏移D多用户虚地址Av：段表长段表基地址As段号装入位修改位页表长页表始址Ap段表基址寄存器多用户段表++As装入位修改位实页号标志pAp实页号p页内偏移d多用户页表主存地址A段页式虚拟存储器的优点：主存空间利用率较高

每段出现一个页内零头，不会出现段间碎片对辅存的管理容易，固定页对应固定块便于程序的调度和链接程序段和数据段的共享和保护方便段页式虚拟存储器的缺点：地址转换速度慢

需访存3次，进行2次地址加法需设置段表和多个页表，占用存储空间大加快地址变换的方法目录表基本思想：用一个小容量高速存储器存放目录表，目录表存储容量由实页数决定，使目录表占用存储空间少，采用相联存储器的并行相联查找功能访问目录表，加快查表速度如果将容量较大的页表放在主存中，由于主存的工作速度较低，所以地址变换费时较多相联存储器（按内容访问存储器）能实现对存储器中所有存储字的并行查找操作查找速度快，造价高，容量小比较寄存器C

存放待查找的存储字内容屏蔽寄存器M

存放屏蔽字内容关键字段屏蔽字用来屏蔽掉寄存器C中不需要查找的某些位用户号U虚页号P页内偏移D多用户虚地址多用户虚页号(U,P)修改位实页号P其他标志U,P0/1p目录表按内容访问的相联存储器实页号p页内偏移d相联访问主存实地址目录表地址变换方法的优点：

由于采用相联存储器，因此查表速度快目录表地址变换方法的缺点：

可扩展性差：随着主存容量的增加，目录表的容量也必须增加，原有的相联存储器的容量就可能不够。如果扩大相联存储器的容量就使造价太高，查表速度也会因此降低快慢表快表(TLB)：是慢表的一个部分副本，在相联存储器中存放一段时间内经常要访问的存储字，容量可为8~16个存储字，访问速度与CPU中的通用寄存器相当。程序在执行过程中具有局部性慢表：存放页表的所有存储字，放在主存中快慢表地址变换的速度接近快表的访问速度，并使主存中的慢表容量不受限制用户号U虚页号P页内偏移D多用户虚地址Av1p装入位实页号U,PpU,P拼接实页号p实页号p页内偏移d快表(按内容相联访问)慢表(按地址访问)主存实地址快表的查找速度很快，只要对快表的命中率较高，地址变换所需时间与主存的一个存储周期相比就几乎可以忽略不计。虚拟存储器的访问速度就可以接近主存的工作速度例：某页式虚拟存储器的虚空间分为8个虚页，虚页号为0~7，页的大小为1024个字，主存容量为4096个字。采用页表进行地址变换时，页表的当前内容如下表所示。实页号装入位3123210011001010（1）列出会发生页面失效的全部虚页号。（2）若程序按以下虚地址访存：0,3728,1023,1024,2055,7800,4096,6800，请计算出变换的主存实地址（用十进制表示）。（1）2，3，5，7虚地址虚页号页内偏移装入位实页号页内偏移实地址0372810231024205578004096680003012746065610230763206561011001130

页面失效3102310

页面失效

页面失效2006563072

无40951024

无无2048656页面替换算法在产生页面失效，需将新页调入主存，主存已被虚页占满的情况下，控制腾出主存中哪个页面以接纳新页的算法评价页面替换算法的优劣准则主存命中率是否便于实现实现成本随机算法（RAND算法）用软件或硬件随机产生被替换的虚页号优点：简单，易于实现缺点：没有利用主存使用的“历史”情况，没有利用程序的局部性，使主存命中率低先进先出算法（FIFO算法）选择最早装入主存的虚页作为被替换页实现方法：为页表或目录表中的每个页增设一个“年龄计数器”字段刚调入的虚页的计数器的计数值为0每调入一个新的虚页时，其他装入页的计数值都加1需要替换时，计数值最大的装入页就是最先进入

主存的虚页优点：较易实现，利用了主存使用的“历史”信息缺点：最先进入的页很可能是现在经常要用到的页，不一定能反映出程序的局部性近期最少使用替换算法（LRU算法）选择过去近期最少访问的虚页作为被替换页实现方法：在页表或目录表中，对每个页增设一个“使用次数计数器”字段某个页被访问一次时，该页的计数器字段加1

使用次数最少的页是被替换页优点：由于一般近期最少使用的页在未来一段时间内也将最少被访问，因此能较好地反映程序的局部性缺点：是按页的过去使用情况来确定被替换页，不是按页的未来使用情况确定被替换页，具有一定的局限性实现困难近期最近未使用替换算法选择过去近期最久未被访问的虚页作为被替换页在页表或目录表中，对每个页增设一个“使用计时器”字段某个页被访问时，该页的计时器字段清0，其他装入页的计时器的值都加1

使用最久的页（即计时器的值最大）是被替换页近期最久未使用替换算法的“使用计时器”字段的位数比近期最少使用替换算法的“使用次数计时器”字段的位数少，使页表增加的容量较少。最优替换算法（OPT算法）选择将来一段时间内最久不被访问的页作为被替换页优点：根据虚页未来使用情况来确定被替换页，命中率最高缺点：只有让程序先运行一遍得到程序访存的虚页地址流，才能在替换时确定未来一段时间内哪一页是最久不被访问的。是一种理想化的算法，不具有实用价值，常用作评价其它页面替换算法优劣的标准例：设有一道程序，有0~4共5个虚页，程序执行时的访存地址流为：

0,1,0,4,3,0,2,3,1,3若分配给该道程序有3个实页，请图示分别采用FIFO，LRU和OPT替换算法对3页主存空间的使用和替换过程，并分别计算主存命中率。时间t12345678910虚页地址流0104302313001010*14调进调进命中调进替换31*4304*替换3*02替换3*02命中10*2替换132*替换先进先出

FIFO命中2次时间t12345678910虚页地址流01043023130010101*4调进调进命中调进替换0*34034*03*2替换0*32命中132*替换132*近期最少使用

LRU命中4次命中命中时间t12345678910虚页地址流010430231300101014*调进调进命中调进替换01*30*132*13替换2*13命中2*132*13最优替换算法

OPT命中5次命中命中命中例：设有一道循环程序，有0~3共4个虚页，分配给该程序的主存实页只有3个。程序执行时的访存地址流为：

0,1,2,3,0,1,2,3,……请图示分别采用FIFO，LRU和OPT替换算法对主存实页的使用和替换过程，并分别计算主存命中率。时间t12345678虚页地址流012301230010*1231*2调进调进替换302*3*01替换20*1替换231*先进先出

FIFO命中0次调进替换替换时间t12345678虚页地址流012301230010*1231*2调进调进替换302*3*01替换20*1替换231*调进替换替换近期最少使用LRU命中0次时间t12345678虚页地址流01230123001012*013*调进调进命中0*1301*302*3替换023*调进替换命中3次最优替换算法

OPT命中命中在程序按虚页地址流访问主存过程中，每次发生替换时的被替换页就是下次要使用的页，产生“颠簸”。若再多分配一个主存实页，3种算法均能命中4次，达到最大主存命中率。命中率与分配给程序的主存实页数有关。例：设有一道循环程序，有0~4共5个虚页，程序执行时的访存地址流为：

0,1,2,3,0,1,4,0,1,2,3,4请图示采用FIFO算法，在分配给程序的主存实页数分别为3页和4页时的命中率。并不是分配给程序的主存实页数越多，主存访问的命中率就越高。时间t123456789101112虚页地址流0123014012340010*1231*2调进调进替换302*3*01替换40*1替换40*1命中40*1421*替换n=3命中3次调进替换命中4*23替换4*23命中时间t123456789101112虚页地址流0123014012340010120*12调进调进0*120*1241*2替换402*4014*01替换n=4命中2次调进30*1替换341*333333*222调进命中命中替换替换替换堆栈型替换算法堆栈型替换算法的定义：设A是长度为L的任意一个虚页地址流，t为已处理过t-1个虚页的时间点，n为分配给该虚页地址流的主存实页数，Bt(n)表示在t时间点，在n个实页中的虚页集合，Lt表示到t时间点已处理过的虚页地址流中虚页号相异的页数。如果替换算法具有下列包含性质：

n<Lt时，Bt(n)cBt(n+1)n≥Lt时，Bt(n)=Bt(n+1)则称此替换算法属于堆栈型替换算法。

堆栈型替换算法具有性质：随着分配给程序的主存实页数增加，堆栈型替换算法保证访问主存的命中率也随之增加，至少不下降

LRU算法及OPT算法是堆栈型替换算法FIFO算法非堆栈型替换算法对于LRU算法，在主存中保留的是最近使用过的虚页，最近使用过的n+1个虚页中必包含最近使用过的n个虚页对于OPT算法，在主存中保留的是最近的将来要访问的虚页，最近的将来要访问的n+1个虚页中必包含最近的将来要访问的n个虚页可采用堆栈处理技术对访存虚页地址流处理一次，就可同时获得对此虚页地址流分配不同主存实页数时的主存命中率用堆栈处理技术对虚页地址流进行处理时，主存在t时间点的状态用堆栈St表示，St是Lt个不同虚页号在堆栈中的有序集。St(1)是栈顶项，St(2)是次栈顶项……

n<LtBt(n)={St(1),St(2),…,St(n)}n≥LtBt(n)={St(1),St(2),…,St(Lt)}对虚页地址流A在时间点t的At虚页是否命中，只需看St的前n项中是否有At页，若有，则命中LRU算法把刚访问过的虚页号压入栈顶单元后，把栈顶单元中的虚页号与其他堆栈单元的虚页号进行比较，去掉与栈顶单元虚页号相同的其他堆栈单元，保证栈中保留的虚页号都是相异的。例：设有一道程序，有0~4共5个虚页，程序执行时的访存地址流为：

1,2,1,0,4,1,3,4,2,1,4,1若分配给该道程序有3个实页，采用LRU算法对虚页地址流进行堆栈处理。分别求出分配给该程序主存实页数为1，2，3，4和5页时的主存命中率。n=1，H1=0n=2，H2=2/12=0.167n=3,H3=5/12=0.417n=4,H4=6/12=0.5n=5,H5=7/12=0.583时间t123456789101112虚页地址流1210413421411n=1n=2n=3n=4n=5St(1)St(2)St(3)St(4)St(5)2112调入调入调入调入调入替换调入调入调入调入替换命中命中命中命中012替换替换调入调入调入4012替换替换替换调入调入1402替换替换命中命中命中31402替换替换替换替换调入43102替换替换命中命中命中24310替换替换替换替换命中12430替换替换替换命中命中41230替换替换命中命中命中14230替换命中命中命中命中高速缓冲存储器

Cache-主存存储系统与主存-辅存存储系统之间的区别：两级存储器间的信息交换单位不同主存与辅存间的信息交换单位是页(1K~几十K个存储字)，Cache与主存间的信息交换单位是块(几个~几十存储字)两级存储器的速度比不同：主存速度是磁盘速度的105倍，Cache速度是主存速度的3~10倍CPU与Cache及主存均有直接通路CPU对Cache未命中可直接访问主存；辅存与CPU间没有直接通路，CPU访存未命中，需等待虚页调入主存再访存Cache-主存存储系统以提高速度为目标，各项管理功能由硬件实现；主存-辅存存储系统以扩大容量为目标，各项管理功能由软件实现Cache-主存存储系统对应用程序员和系统程序员均透明；

主存-辅存存储系统仅对应用程序员透明存储系统Cache-主存主存-辅存实现目标提高主存速度扩大主存容量实现方法全硬件软件为主,硬件为辅两级速度比3~10倍105倍页（块）大小1~16字1K~16K字等效存储容量主存容量虚拟存储空间容量透明性对应用和系统程序员仅对应用程序员未命中处理直接访存等待调入Cache的工作原理主存和Cache都划分成相同大小的块块号块内地址Cache—主存地址映象变换机构块号块内地址Cache主存主存地址Cache地址Cache替换策略不命中命中已装不进还可装入去CPU来自CPU块数据（多字宽）指令/数据（单字宽）修改块表替换某块单字宽

Cache的地址映象与地址变换Cache的地址映象：把主存地址空间映象到Cache地址空间，建立起主存块与Cache块间位置对应关系的规则。Cache的地址变换：在程序实际运行过程中，把主存地址变换为

Cache地址的过程。选择地址映象方式考虑的因素：用硬件实现地址变换的难易地址变换速度主存或Cache空间利用率块调入时发生块位置冲突的概率全相联映象及其地址变换全相联映象：主存中的任意一块可以映象到Cache中的任意块位置上若Cache块数为Cb，主存块数为Mb，则主存与Cache间的对应关系有Cb×Mb种块0块Cb-1块1…块0块1块i块Mb-1……Cache主存块号B块内地址W主存块号BCache块号b有效位………………Bb1相联比较块号b块内地址w主存地址Cache地址命中目录表（由相联存储器存储，共Cb个字）log2CB位log2WB位log2Cb位CB：主存总块数Cb：Cache总块数WB：每块存储字数全相联映象方式的优点：Cache块位置冲突概率低，Cache空间利用率高。全相联映象方式的缺点：

随着Cache容量的增大，而Cache块受主存频宽的限制容量较小，因此Cache块数增多，目录表行数增多，要求相联存储器的容量越来越大。过大的相联存储器不仅价格昂贵，而且也会降低地址变换的速度直接相联映象及其地址变换主存中的一块只能映象到Cache的一个特定块位置上。

b=BmodCb设主存的块数为Mb，将主存按Cache的大小分为Me=Mb/Cb

个区(主存块块号为B，Cache块块号为b,Cache的块数为Cb)块0块1块Cb-1…块Cb块Cb+1块2Cb-1…块Mb-Cb块Mb-Cb+1块Mb-1……区0区1区Me-1Cache主存…块0块1块Cb-1直接映像方式中，Cache的地址与主存地址除区号外的低位部分完全相同用于保存地址变换信息的表称为区表块号B区号E块内地址W区号E(按地址访问)有效位…………E1块号b块内地址w主存地址Cache地址相等比较若比较结果相等且有效位为1，用Cache地址访问Cache,读出数据送往CPU相等区表（按地址访问的物理Cache）访问主存CE：主存区数CB:区内块数WB:块内存储字数CECBWB为了提高Cache的访问速度，有些系统将区表存储器与Cache合并成一个存储器块号B区号E块内地址W主存地址有效位区号E数据D0数据D1数据Dw-1……1ED0D1Dw-1……相等比较1/w相等…送CPU访问主存按地址访问的Cache多路选择器直接相联映象方式的优点：区表的空间占用量比目录表小地址变换仅需处理区号部分，变换速度更快区表可存放在按地址访问的Cache中，不需相联存储器，降低了地址变换的成本直接相联映象方式的缺点：块冲突率高，使Cache空间利用率低，块替换频繁组相联映象及其地址变换主存的组与Cache的组之间采用直接映象方式，两个对应组的块间采用全相联映象方式把主存按Cache的容量分区，主存中的各区和

Cache再按同样大小划分成数量相同的组，组内按同样大小划分成数量相同的块Gb:组内块数Cg:组数Me:区数Cb=GbCg:区内块数Mb=GbCgMe=CbMe:内存总块数块表存储器采用按地址访问和相联访问两种方式工作主存区号E+主存组内块号B+Cache组内块号b+有效位保存地址变换信息的表称为块表块表的行数与Cache的块数相等区号E区内组号G组内块号B块内地址W组号g组内块号b块内地址w相联比较Gb个块b区号E,组内块号B组内块号b相等不等块失效,访问主存主存地址Cache地址块表有效位e在块内字数不多时将块表存储器与Cache合并为一个存储器：将原块表中相联比较的一个组按块方向展开存放使块表的行数是Cache的组数Cg，一行由Cb个存储字组成（Cb是组内块数）用多个相等比较器代替相联访问，加快查表速度将Cache的地址变换与访问Cache并行进行区号E区内组号G组内块号B块内地址W组号g组内块号b块内地址wE,BbeE,BbeE,Bbe……E,BbeE,BbeE,Bbe……相等比较相等比较相等比较……≠≠≠＝＝＝或与块失效主存地址Cache地址块表（按地址访问的单体多字存储器）组相联映象方式的优点：块冲突概率较低，Cache空间利用率较高，块表占用空间较少，地址变换速度较快组相联映象方式的缺点：实现难度高

Cache的替换算法及其实现各种地址映象方式的替换范围：直接映象方式：只能换出与主存地址的区内块号同号的Cache块全相联映象方式：由替换算法换出主存中的某Cache块组相联映象方式：由替换算法换出与主存地址的区内组号同号的Cache组中某块Cache系统要求访问速度很高，替换算法必须全部用硬件实现

随机替换算法实现硬件：随机数发生器优点：实现简单缺点：未利用程序的局部性特点，也未利用历史的块地址流分布情况，因此命中率低

FIFO替换算法实现硬件：每块设置一个计数器在块表内增设一个计数器字段，其长度与Cache地址中的组内块号字段长度相同新装入块时，将所属的计数器清零，同组的其他块所属的计数器都加1

需要替换时，在同组中选择计数器的值最大的块作为被替换块每组设置一个计数器为每组设置一个模为Cb的计数器，最先指向该组最先进来的块，该块被替换后计数值加1，指向下一个要替换的块优点：利用了Cache块地址流的历史信息缺点：最先装入的块有可能是经常要用的块，命中率仍不高

LRU替换算法

实现硬件：计数器法为每块设置一个计数器，其长度与组内块号字段的长度相同。被装入或被替换的块，其对应的计数器清0，同组中其他所有块所属的计数器均加1命中的块所对应计数器清0，同组中计数值小于命中块原计数值的均加1需替换时，以计数值最大的计数器所对应块作为被替换块例：某Cache系统，采用组相联映象方式，每组4块，用计数器实现LRU替换算法。若访存块地址流为：1，2，3，4，5，4，且设所有块均被映象到同一Cache组中。请说明该Cache相应组内4个Cache块计数器的工作情况。装入装入装入装入替换

命中块号计数器块号计数器块号计数器块号计数器块号计数器块号计数器块地址流主存块1主存块2主存块3主存块4主存块5主存块4Cache块0Cache块1Cache块2Cache块3100010101200011010301100011410110100511001001112312432543211011000

比较对法让2个块组成一个比较对，用一个触发器的状态表示该比较对的两块被访问过的先后次序，经门电路组合，可从多个块中找出最久未被访问的块若块数为p，则触发器的个数为Cp2=p(p-1)/2，门电路个数为p个。由于触发器个数随块数的平方递增，故比较对法只适用于组内块数较少的情况TABTAC0TBC01&&&011ALRUBLRUCLRU访问B访问A访问CCLRU=TAC·TBC=1ALRU=TAB·TAC=1BLRU=TAB·TBC=1

Cache的性能分析

Cache系统的加速比T=H×Tc+(1-H)×TmSp=TmTTmH×Tc+(1-H)×Tm=(1-H)+H×TcTm1=提高加速比Sp的最好途径是提高命中率HTc与Tm的比值受到器件的限制影响对Cache的命中率H的主要因素：访存的块地址流

Cache的容量大小

Cache存储器采用的地址映象

Cache存储器采用的块替换算法

Cache的一致性问题导致主存某单元内容与Cache对应单元内容不一致的原因：CPUX’XI/OCache主存储器CPU写Cache，并不同时写回主存，造成主存内容的过时，I/O或其它处理机从主存得到错误输出信息CPUXX’I/OCache主存储器

I/O或其它处理机写主存，并不同时更新Cache，造成Cache中内容过时，CPU从Cache中读出错误信息

解决主存内容跟不上Cache对应内容变化的方法：

写回法CPU执行写操作时，被写数据只写入Cache，

不写入主存。仅当需要替换时，才将修改过的Cache块写回主存。在采用写回法的Cache块表中，一般有一个“修改位”优点：使主存与Cache的通信量较小，成本较低缺点：会出现主存与Cache的不一致；增加了Cache的复杂性（需设置修改位以确定是否需要写回及控制先写回后才调入的执行顺序）为保证可靠性，需在Cache中采用纠错码，导致

冗余信息位更多。写直达法CPU执行写操作时，必须把数据同时写入Cache和主存。优点：可始终保持Cache和主存的一致性；Cache块表中不需设置修改位，降低了Cache的复杂性；Cache块的错误可由主存纠正，Cache中只需设置

一位奇偶校验位，可靠性较好；缺点：需设置大量缓冲寄存器以减少CPU为等待写主存完成所耗费的时间，成本较高；Cache与主存的通信量过大；解决Cache内容跟不上主存内容变化的方法：不按写分配法发生写Cache不命中时，只把所写字写入主存，不把包括所写字在内的一个块从主存读入Cache。优点：Cache与主存的信息流量小；缺点：会出现Cache与主存内容的不一致；当出现写Cache不命中时，是否要把包括所写字在内的一个块从主存读入Cache的问题按写分配法发生写Cache不命中时，先把所要写的字写入主存，再把包括所写字在内的一个块从主存读入Cache。优点：能保证Cache的更新跟上主存的更新缺点：Cache与主存的通信量过大当I/O处理机未经Cache往主存写入新内容时，由操作系统经专用指令清除整个Cache缺点：使Cache存储器对系统程序员不透明当I/O处理机往主存某个区域写入新内容时，由专用硬件自动将Cache内对应此区域的副本作废（通过将有效位置0）使CPU，I/O处理机共享同一Cache写回法+按写分配法写直达法+不按写分配法三级存储系统两个存储系统的组织方式组织为“Cache-主存”和“主存-磁盘”两个独立的存储系统物理地址Cache存储系统CPUMMU高速缓存Cache主存储器虚拟地址物理地址物理地址数据/指令数据/指令数据/指令物理地址Cache存储系统结构框图一个存储系统的组织方式由Cache、主存和磁盘组织成一个“Cache-主存-磁盘”存储系统虚拟地址Cache存储系统CPUMMU高速缓存Cache主存储器虚拟地址物理地址数据/指令数据/指令数据/指令虚拟地址Cache存储系统结构框图全Cache存储系统的组织方式没有主存储器，只用Cache和磁盘两种存储器构成“Cache-磁盘”存储系统接近Cache的访问周期,容量等价虚拟地址空间P1P2PnIOP1IOPm……C1C2CnCio1CiomCg……处理机局部Cache共享Cache多处理机系统中的全Cache存储系统结构作业1某页式虚拟存储器的虚拟空间分为8个虚页，虚页号为0~7，页的大小为1024个字，主存容量为4096个字。采用页表进行地址变换时，页表内容如表所示。（1）列出会发生页面失效的全部虚页号。（2）若程序按以下虚地址访存：128,1024,2048,4055，请计算出变换的主存实地址（用十进制表示）。实页号装入位31232100010110100,2,5,7128(0,128)失效1024(1,0)10242048(2,0)失效(3,983）3*1024+983=4055作业2一个程序由920条指令组成，每条指令都是单字长。假设这个程序访问虚拟存储器的字地址流为（地址用十进制数表示）：

20,22,208,214,146,618,370,490,492,868,916,728

采用FIFO替换算法，分别计算下列情况的主存命中率：（1）页面大小为200字，分配的主存容量为

400字。（2）页面大小为100字，分配的主存容量为

400字。（3）页面大小为400字，分配的主存容量为400字。（4）由题（1）、（2）、（3）的结果，可得出什么结论？（5）页面大小为200字，分配的主存容量为

800字。由题（1）和题（5）的结果，可得出什么结论？（1）(0,20)(0,22)(1,8)(1,14)(0,146)(3,18)(1,170)(2,90)(2,92)(4,68)(4,116)(3,128)000*10*131*3*2442*4*3001103122443调入命中调入命中0*1命中31*替换命中替换命中3*2替换2*命中替换命中6次（2）(0,20)(0,22)(2,8)(2,14)(1,46)(6,18)(3,70)(4,90)(4,92)(8,68)(9,16)(7,28)002216344897调入00命中20调入20命中201调入20*16调入2*316替换431*6替换431*6命中4386*替换43*89替换4*789替换命中3次（3）(0,20)(0,22)(0,208)(0,214)(0,146)(1,218)(0,370)(1,90)(1,92)(2,68)(2,116)(1,328)0调入0命中0命中0命中0命中1替换0替换1替换1命中2替换2命中1替换命中6次（5）(0,20)(0,22)(1,8)(1,14)(0,146)(3,18)(1,170)(2,90)(2,92)(4,68)(4,116)(3,128)001103122443调入00命中0调入0命中0命中103调入103命中10*32调入10*32命中1*432替换1*432命中1*432命中11命中7次作业3在页式虚拟存储器中，一个程序由0~4共5个虚页组成，在程序执行过程中，访存虚页地址流为：

0,1,0,4,3,0,2,3,1,3

假设分配给这个程序的主存空间有3个实页，分别采用FIFO、LRU和OPT替换算法进行替换调度。（1）分别画出3种替换算法对主存3个实页位置的使用过程。（2）分别计算3种替换算法的主存命中率。01043023130调入01调入01命中0*14调入31*4替换304*替换3*02替换3*02命中10*2替换132*替换使用FIFO替换算法命中2次01043023130调入01调入01命中0*14调入31*4替换304*替换3*02替换30*2命中312*替换312*命中使用LRU替换算法命中3次01043023130调入01调入01命中014*调入01*3替换0*13命中2*13替换2*13命中2*13命中2*13命中使用OPT替换算法命中5次作业4有一个Cache存储器，主存有8块（0~7），Cache有4块（0~3），采用组相联映像，组内块数为2块。采用LRU替换算法。（1）写出主存地址和Cache地址的格式，并指出各字段的长度。（2）指出主存各块与Cache各块之间的映像关系（3）某程序运行过程中，访存的主存块地址流为

1,2,4,1,3,7,0,1,2,5,4,6,4,7,2

说明该程序访存对Cache的块位置的使用情况，指出发生块失效且块争用的时刻，计算

Cache命中率。124137012546472112调入调入1*24调入124*命中12*4*3调入174*3*替换替换170*3*命中17*0*2替换1*7*52替换47*5*2替换465*2*替换465*2*命中46*5*7替换5*247*替换1*703*作业5在一个采用组相联映像的Cache存储器中，Cache容量为16K字，主存采用8个低位交叉编址的存储体组成，主存容量为8M字。要求Cache的每一块能在一个主存访问周期从主存取得。采用按地址访问存储器存放块表实现地址变换，并采用8个相等比较电路。（1）设计主存地址和Cache地址的格式，并说明地址各字段的长度。（2）设计地址变换的块表，求出该表的行数、宽度和容量，说明每个比较电路进行相等比较的位数。（1）主存地址格式为(E,G,B,W)，各有9、8、3、3位

Cache地址格式为(g,b,w)，各有8、3、3位（2）块表的行数为28行，宽度为8*16位，容量为28*8*16，每个比较电路进行相等比较的位数为12位。强化节能减排实现绿色发展内容览要节能减排，世界正在行动为什么要节能减排什么是节能减排节能减排，我们正在行动0502010403目录CONTENTS一、什么是节能减排

在《中华人民共和国节约能源法》中定义的节能减排，是指加强用能管理，采取技术上可行、经济上合理以及环境和社会可以承受的措施，从能源生产到消费的各个环节，降低消耗、减少损失和污染物排放、制止浪费，有效、合理地利用能源。从具体意义上说，节能，就是降低各种类型的能源品消耗；减排，就是减少各种污染物和温室气体的排放，以最大限度地避免污染我们赖以生存的环境。二、为什么要节能减排1、节能减排是缓解能源危机的有效手段

当下，能源危机迫在眉睫，国外有关机构的统计结果显示：2010年中国的能源消耗超过美国，成为全球第一。2011年2月底，中国能源研究会公布最新统计数据显示，2010年我国一次能源消费量为32.5亿吨标准煤，同比增长6%，超过美国成为全球第一能源消费大国。统计数据称，2010年中国一次能源消费量为24.32亿吨油当量，同比增长11.2%，占世界能源消费总量的20.3%。美国一次能源消费量为22.86亿吨油当量，同比增长3.7%，占世界能源消费总量的19.0%。

根据全球已探明传统能源储量测算，按照当前能源消耗增长速度，传统的石化燃料（煤、石油、天然气）已经不够人类再使用一百年。目前新能源的开发利用方兴未艾，2010年全球有23%的能源需求来自再生能源，其中13%为传统的生物能，多半用于热能（例如烧柴），5.2%是来自水力，来自新的可再生能源（小于20MW的水力，现代的生物质能，风能，太阳，地热等）则只有4.7%。在再生能源发电方面，全球来自水力的占16%，来自新的再生能源者占5%。如果我们不对现有能源和资源节约使用，按照目前情况持续下去，有可能百年之后，人类将会部分进入一个“新石器时代”。2节能减排是保护自然生态环境的强力武器