计算机系统结构原理

现代计算机系统以存储器为中心3.1存储系统原理3.2虚拟存储器3.3高速缓冲存储器(Cache)3.4三级存储系统第3章存储系统10/18/20221计算机系统结构第三章存储系统3.1存存储系系统原理理3.1..1存存储系统统的定义义3.1..2存存储系统统的层次次结构3.1..3存存储系统统的频带带平衡3.1..4并并行访问问存储器器3.1..5交交叉访问问存储器器3.1..6无无冲突访访问存储储器2/28/20202计算机系系统结构构第第三章存存储储系统3.1..1存存储系统统的定义义在一台计计算机中中，通常常有多种种存储器器种类：主存储器器、Cache、通用用寄存器器、缓冲冲存储器器、磁盘盘存储器器、磁带带存储器器、光盘盘存储器器等材料工艺艺：ECL、、TTL、MOS、磁磁表面、、激光，，SRAM，DRAM访问方式式：随机访问问、直接接译码、、先进先先出、相相联访访问、块块传送送、文件件组2/28/20203计算机系系统结构构第第三章存存储储系统存储器的的主要性性能：速度、容容量、价价格速度用存储器器的访问问周期、、读出时时间、频频带宽度度等表示示。容量用字节B、千字字节KB、兆字字节MB和千兆兆字节GB等单单位表示示。价格用单位容容量的价价格表示示，例如如：$C/bit。组成存储储系统的的关键：：把速度、、容量和和价格不不同的多多个物理理存储器器组织成成一个存存储器，，这个存存储器的的速度最最快，存存储容量量最大，，单位容容量的价价格最便便宜。2/28/20204计算机系系统结构构第第三章存存储储系统1.存存储系统统的定义义两个或两两个以上上速度、、容量和和价格各各不相同同的存储储器用硬硬件、软软件、或或软件与与硬件相相结合的的方法连连接起来来成为一一个存储储系统。。这个存存储系统统对应用用程序员员是透明明的，并并且，从从应用程程序员看看，它是是一个存存储器，，这个存存储器的的速度接接近速度度最快的的那个存存储器，，存储容容量与容容量最大大的那个个存储器器相等，，单位容容量的价价格接近近最便宜宜的那个个存储器器。虚拟存储储器系统统：对应应用程序序员透明明Cache存储储系统：：对系统统程序员员以上均均透明2/28/20205计算机系系统结构构第第三章存存储储系统由多个存存储器构构成的存存储系统统2/28/20206计算机系系统结构构第第三章存存储储系统在一般计计算机系系统中，，有两种种存储系系统：Cache存储储系统：：由Cache和主存存储器构构成主要目的的：提高高存储器器速度2/28/20207计算机系系统结构构第第三章存存储储系统虚拟存储储系统：：由主存存储器和和硬盘构构成主要目的的：扩大大存储器器容量2/28/20208计算机系系统结构构第第三章存存储储系统2.存储储系统的的容量要求：提供尽可可能大的的地址空空间能够随机机访问方法有两两种：只对系统统中存储储容量最最大的那那个存储储器进行行编址，，其他存存储器只只在内部部编址或或不编址址Cache存储储系统另外设计计一个容容量很大大的逻辑辑地址空空间，把把相关存存储器都都映射这这个地址址空间中中虚拟存储储系统2/28/20209计算机系系统结构构第第三章存存储储系统3.存储储系统的的价格计算公式式：当S2》》S1时时，C≈≈C2S2与S1不能能相差太太大2/28/202010计算机系系统结构构第第三章存存储储系统4.存存储系统统的速度度表示方法法：访问周期期、存取取周期、、存储周周期、存存取时间间等命中率定定义：在M1存存储器中中访问到到的概率率

其中：N1是对对M1存存储器的的访问次次数N2是对对M2存存储器的的访问次次数访问周期期与命中中率的关关系：T＝HT1＋((1－H)T2当命中率率H→1时，T→T12/28/202011计算机系系统结构构第第三章存存储储系统存储系统统的访问问效率：：访问效率率主要与与命中率率和两级级存储器器的速度度之比有有关例3.1：假设T2＝５T１，在命中中率H为为0.9和0..99两两种情况况下，分分别计算算存储系系统的访访问效率率。解：当H＝0.9时时，e1＝1／((0.9＋5((1－0.9)))＝0.72当H＝0.99时，e2＝1／((0.99＋5(1－－0.99)))＝0..962/28/202012计算机系系统结构构第第三章存存储储系统提高存储储系统速速度的两两条途径径：一是提高高命中率率H，二是两个个存储器器的速度度不要相相差太大大其中：第第二条有有时做不不到(如如虚拟存存储器))，这时时，只能能依靠提高高命中率率例3.2：在虚拟存存储系统统中，两两个存储储器的速速度相差差特别悬悬殊，例例如：T2＝105T１。如果要要使访问问效率到到达e＝＝0.9，问需需要有多多高的命命中率？？2/28/202013计算机系系统结构构第第三章存存储储系统解：0.9H＋90000(1--H)＝＝189999.1H＝＝89999计算得：：H＝0..999998888877777…≈0.9999995.采采用预取取技术提提高命中中率方法：不命中时时，把M2存储储器中相相邻多个个单元组组成的一一个数据据块取出出来送入入M1存存储器中中。2/28/202014计算机系系统结构构第第三章存存储储系统计算公式式：其中：H’是采采用预取取技术之之后的命命中率H是原来来的命中中率n为数据据块大小小与数据据重复使使用次数数的乘积积例3.3：在一个Cache存储储系统中中，当Cache的块块大小为为一个字字时，命命中率H＝0..8；假假设数据据的重复复利用率率为5，，T2＝＝5T1。计算块块大小为为４个字字时，Cache存储储系统的的命中率率？并分分别计算算访问效效率。2/28/202015计算机系系统结构构第第三章存存储储系统解：n＝4××5＝20，采用预取取技术之之后，命命中率提提高到：：2/28/202016计算机系系统结构构第第三章存存储储系统例3.4：在一个虚虚拟存储储系统中中，T2＝105T１，原原来的命命中率只只有0..8，如如果访问问磁盘存存储器的的数据块块大小为为4K字字，并要要求访问问效率不不低于0.9，，计算数数据在主主存储器器中的重重复利用用率至少少为多少少？解：假设数据据在主存存储器中中的重复复利用率率为m，根据前前面给出出的关系系，有如如下方程程组：2/28/202017计算机系系统结构构第第三章存存储储系统解方程组组：由方程((1)得得到：0.9H+90000-90000H=12/28/202018计算机系系统结构构第第三章存存储储系统证明方法法一：采用预取取技术之之后，不命中率率(1--H)降降低ｎ倍倍：2/28/202019计算机系系统结构构第第三章存存储储系统证明方法法二：在原有命命中率的的计算公公式中，，把访问问次数扩扩大到n倍。由由于采用用了预取取技术，，命中次次数为：：nN1＋(n--1)N2,不命中中次数仍仍为N2，因此新新的命中中率为：：2/28/202020计算机系系统结构构第第三章存存储储系统3.1..2存存储系统统的层次次结构多个层次次的存储储器：第1层：：RegisterFiles((寄存器堆堆)第2层：：Buffers((Lookahead)(先先行缓冲冲站)第3层：：Cache(高速速缓冲存存储器))第4层：：MainMemory(主存存储器))第5层：：OnlineStorage(联机机存储器器)第6层：：Off-lineStorage((脱机存存储器))用i表示层数数，则有：工作周期期Ti＜Ti+1，存储容量量：Si＜Si+1，单位价格格：Ci＞Ci+12/28/202021计算机系系统结构构第第三章存存储储系统各级存储储器的主主要主要要性能特特性CPU与与主存储储器的速速度差距距越来越越大目前相差差两个数量量级今后CPU与主主存储器器的速度度差距会会更大2/28/202023计算机系系统结构构第第三章存存储储系统3.1..3存存储系统统的频带带平衡例3.5：Pentium4的指指令执行行速度为为8GIPS，，CPU取指令令8GW/s，，访问数数据16GW//s，各各种输入入输出设设备访问问存储器器1GW/s，，三项相相加，要要求存储储器的频频带宽度度不低于于25GW/s。如果采用用PC133内内存，主主存与CPU速速度差188倍倍如果采用用PC266内内存，主主存与CPU速速度差94倍解决存储储器频带带平衡方方法(1)多多个存储储器并行行工作（（本节下下面介绍绍）(2)设设置各种种缓冲存存储器（（第五章章介绍））(3)采采用存储储系统（（本章第第二、第第三节介介绍）2/28/202024计算机系系统结构构第第三章存存储储系统3.1..4并并行访问问存储器器方法：把m字w位的存存储器改改变成为为m/n字n××w位的的存储器器逻辑实现现：把地址码码分成两两个部分分，一部部分作为为存储器器的地址址另一部部分负责责选择数数据主要缺点点：访问问冲突大大(1)取取指令冲冲突(2)读读操作数数冲突(3)写写数据冲冲突(4)读读写冲突突2/28/202025计算机系系统结构构第第三章存存储储系统并行访问问存储器器结构框框图2/28/202026计算机系系统结构构第第三章存存储储系统1.高高位交叉叉访问存存储器主要目的的：扩大存储储器容量量实现方法法：用地址码码的高位位部分区区分存储储体号参数计算算方法::m：每个个存储体体的容量量，n：总共共的存储储体个数数，j：存储储体的体体内地址址，j＝＝0，1，2，，....，m--1k：存储储体的体体号，k＝0，，1，2，....，n-1存储器的的地址：：A＝m×k＋＋j存储器的的体内地地址：Aj＝Amodm。存储器的的体号：：Ak＝3.1..5交交叉访问问存储器器2/28/202027计算机系系统结构构第第三章存存储储系统高位交叉叉访问存存储器结结构框图图2/28/202028计算机系系统结构构第第三章存存储储系统例3.6：用4M字××4位的的存储芯芯片组成成16M×32位的主主存储器器。共用用存储芯芯片：用最高2位地址址经译码码后产生生的信号号，控制制各组存存储芯片片CS。。每组中的的32根根数据线线分别对对应直接接相连，，称为““线或””方式。。2/28/202029计算机系系统结构构第第三章存存储储系统2/28/202030计算机系系统结构构第第三章存存储储系统2.低低位交叉叉访问存存储器主要目的的：提高存储储器访问问速度实现方法法：用地址码码的低位位部分区区分存储储体号参数计算算:m：每个个存储体体的容量量，n：总共共的存储储体个数数，j：存储储体的体体内地址址，j＝＝0，1，2，，....，m--1k：存储储体的体体号，k＝0，，1，2，....，n-1存储器地地址A的的计算公公式为：：A＝n×j＋＋k存储器的的体内地地址：Aj＝存储器的的体号：：Ak＝Amodn2/28/202031计算机系系统结构构第第三章存存储储系统低位交叉叉访问存存储器结结构框图图2/28/202032计算机系系统结构构第第三章存存储储系统地址是编编码方法法：由8个存存储体构构成的低低位交叉叉编址方方式2/28/202033计算机系系统结构构第第三章存存储储系统n个存储储体分时时启动一种采用用流水线线方式工工作的并并行存储储器每存储体体的启动动间隔为为：t＝＝其中：Tm为每个存存储体的的访问周周期,n为存储储体个数数。2/28/202034计算机系系统结构构第第三章存存储储系统访问冲突突共有n个个存储体体，每个个存储周周期只能能取到k个有效效字,其其余n--k个存存储体有有冲突。。假设p((k)是是k的概概率密度度函数，，即p((1)是是k＝1的概率率，p((2)是是k＝2的概率率，…,,p(n)是k＝n的的概率。。k的平平均值为为：N是每个个存储周周期能够够访问到到的平均均有效字字的个数数。通常把N称为并并行存储储器的加加速比。。2/28/202035计算机系系统结构构第第三章存存储储系统定义转移移概率为为g，即即读出的的是转移移指令，，且转移移成功的的概率。。这时有有：p(1))＝gp(2))＝(1-p((1)))g＝((1-g)gp(3))＝(1-p((1)--p(2))g＝(1-g))2g……p(k))＝(1-g))k-1g(k＝1,,2,……,n－－1)……p(n))＝(1-g))n-12/28/202036计算机系系统结构构第第三章存存储储系统Ｎ＝g＋(1-g))g＋((1-g)2g＋…＋＋(1--g)n-2g＋(1--g)g＋(1-g))2g＋…＋＋(1--g)n-2g＋(1--g)2g＋…＋＋(1--g)n-2g…＋(1--g)n-2g＋n(1-g))n-1以上共n行，前前n-2行分别别为等比比级数把n-1行拆分分成2项项则：Ｎ＝＝1g＋＋2(1-g))g＋3(1--g)2g＋…＋(n--1)((1-g)n-2g＋n((1-g)n-11-(1-g)n-12/28/202037计算机系系统结构构第第三章存存储储系统Ｎ＝1-(1-g))n-1＋(1-g)-((1-g)n-1＋(1-g)2-(1--g)n-1…＋(1-g)n-2-(1--g)n-1＋n(1-g))n-1(1-g)n-2gＮ＝1＋＋(1--g)＋＋(1--g)2＋…(1-g))n-2＋(1--g)n-12/28/202038计算机系系统结构构第第三章存存储储系统2/28/202039计算机系系统结构构第第三章存存储储系统2/28/202040计算机系系统结构构第第三章存存储储系统例3.7：Star-100巨型型机存储储系统采采用并行行和交叉叉相结合合的方式式工作，，有32个存储储体低位位交叉，，每次并并行读写写512位，存存储周期期为1280ns，处处理机字字长32位，计计算它的的频带宽宽度Bm和峰值值速度T。解：因为：n＝32，w＝＝512，Tm＝1280ns，Bm＝nw//tm＝＝32512b/1280ns＝12..8Gb/s＝＝1.6GB//s＝400MW/sT＝2..5ns与Tm相相比，峰峰值速度度提高512倍倍实际速度度的提高高要远远远小于这这个数字字2/28/202041计算机系系统结构构第第三章存存储储系统3.1..6无无冲突访访问存储储器1.一一维数组组(向量量)的无无冲突访访问存储储器按连续地地址访问问，没有有冲突，，位移量为为2的变变址访问问，速度度降低一一倍，……2/28/202042计算机系系统结构构第第三章存存储储系统具体方法法：存储体的的个数取取质数，，且n≥≥向量长长度。原因：变址位移移量必然然与存储储体个数数互质例如：Burroughs公公司巨型型科学计计算机BSP存储体个个数为17向量长度度≤16我国研制制的银河河巨型向向量机存储体的的个数为为37向量长度度≤322/28/202043计算机系系统结构构第第三章存存储储系统2.二二维数组组的无冲冲突访问问存储器器要求：一个n×n的二维数数组，按按行、列列、对角角线和反反对角线线访问，，并且在在不同的的变址位位移量情情况下，，都能实实现无冲冲突访问问。顺序存储储：按行、对对角线访访问没有有冲突，，但按列列访问每每次冲突突2/28/202044计算机系系统结构构第第三章存存储储系统错位存储储：按行、按按列访问问无冲突突，但按对角角线访问问有冲突突2/28/202045计算机系系统结构构第第三章存存储储系统n×n二二维数组组无冲突突访问存存储方案案(P··Budnik和和D··J··Kuck提提出))：并行存储储体的个个数m≥n，并且取取质数，，同时还还要在行行、列方方向上错错开一定定的距离离存储数数组元素素。设同一列列相邻元元素在并并行存储储器中错错开d1个存储储体存放放，同一一行相邻邻元素在在并行存存储器中中错开d2个存存储体存存放。当当m＝22p＋1（p为任意意自然数数）时，，能够同同时实现现按行、、按列、、按对角角线和按按反对角角线无冲冲突访问问的充要要条件是是：d1＝2P，d2＝＝1。2/28/202046计算机系系统结构构第第三章存存储储系统例如：4×4的的二维数数组，取取并行存存储体的的个数m＝5，由由关系式式m＝22P＋1，解解得到p＝1，，计算得得到：d1＝21＝2d2＝12/28/202047计算机系系统结构构第第三章存存储储系统n×n数组中的的任意一一个元素素aij在无冲突突并行存存储器中中的体号号地址和和体内地地址的计计算公式式：体号地址址：(2Pi＋j＋＋k)MODm体内地址址：i其中：0≤i≤≤n－1，0≤j≤n－1，k是数组组的第一一个元素素a00所在体号号地址，，m是并行存存储体的的个数，，要求m≥n且为质数数，p是满足足m＝22P＋1关系系的任意意自然数数。主要缺点点：浪费存储储单元对于n×n数组,有有(m-n)×m个存储单单元浪费费主要优点点：实现简单单列元素顺顺序存储储，行元元素按地地址取模模顺序存存储483.二二维数组组的无冲冲突访问问存储器器(之二二)规则：对于任意意一个n×n的数组，如如果能够够找到满满足n＝22P关系的任任意自然然数p，，则这个个二维数数组就能能够使用用n个并行存存储体实现按行行、列、、对角线线和反对对角线的的无冲突突访问。。4×4数数组用4个存储储体的无无访问冲冲突存储储方案2/28/202049计算机系系统结构构第第三章存存储储系统实现方法法：假设aij是4×4数数组中的的任意一一个元素素，下标i和和j都可可以用两两位二进进制表示示。假设设i和j的高位位和低位位分别为为iH、iL、jH和jL，则aij在无冲突突并行存存储器中中的体号号地址和和体内地地址如下下：体号地址址：2((iLjH)＋(iHiLjL)体内地址址：j其中：0≤i≤≤3，0≤j≤≤3主要优点点：没有浪费费的存储储单元，主要缺点点：在执行并并行读和和写操作作时需要要借助比比较复杂杂的对准准网络。2/28/202050计算机系系统结构构第第三章存存储储系统3.2..1虚虚拟存储储器工作作原理3.2..2地地址的映映象和变变换方法法3.2..3加加快内部部地址变变换的方方法3.2..4页页面替换换算法及及其实现现3.2..5提提高主存存命中率率的方法法3.2虚虚拟存存储器2/28/202051计算机系系统结构构第第三章存存储储系统3.2..1虚虚拟存储储器工作作原理也称为虚虚拟存储储系统、、虚拟存存储体系系等其概念由由英国曼曼彻斯特特大学的的Kilbrn等人于于1961年提提出到70年年代广泛泛应用于于大中型型计算机机系统目前，许许多微型型机也使使用虚拟拟存储器器把主存储储器、磁磁盘存储储器和虚虚拟存储储器都划划分成固固定大小小的页主存储器器的页称称为实页页虚拟存储储器中的的页称为为虚页2/28/202052计算机系系统结构构第第三章存存储储系统内部地址址变换：：多用户虚虚拟地址址Av变换成主主存实地地址A多用户虚虚拟地址址中的页页内偏移移D直接接作为主主存实地地址中的的页内偏偏移d，，主存实页页号p与与它的页页内偏移移d直接接拼接起起来就得得到主存存实地址址A。2/28/202053计算机系系统结构构第第三章存存储储系统3.2..2地地址的映映象与变变换三种地址址空间：：虚拟地址址空间主存储器器地址空空间辅存地址址空间地址映象象：把虚拟地地址空间间映象到到主存地地址空间间地址变换换：在程序运运行时，，把虚地地址变换换成主存存实地址址三种虚拟拟存储器器：页式虚拟拟存储器器段式虚拟拟存储器器段页式虚虚拟存储储器2/28/202055计算机系系统结构构第第三章存存储储系统1.段段式虚拟拟存储器器地址映象象方法：：每个程序序段都从从0地址址开始编编址，长长度可长长可短，，可以在在程序执执行过程程中动态态改变程程序段的的长度。。地址变换换方法：：由用户号号找到基基址寄存存器，读读出段表表起始地地址，与与虚地址址中段号号相加得得到段表表地址，，把段表表中的起起始地址址与段内内偏移D相加就就能得到到主存实实地址。。主要优点点：(1)程程序的模模块化性性能好。。(2)便便于程序序和数据据的共享享。(3)程程序的动动态链接接和调度度比较容容易。(4)便便于实现现信息保保护。主要缺点点：(1)地地址变换换所花费费的时间间长，两两次加法法(2)主主存储器器的利用用率往往往比较低低。(3)对对辅存（（磁盘存存储器））的管理理比较困困难。2/28/202058计算机系系统结构构第第三章存存储储系统2.页页式虚拟拟存储器器地址映象象方法：：地址变换换方法：：2/28/202060计算机系系统结构构第第三章存存储储系统主要优点点：(1)主主存储器器的利用用率比较较高(2)页页表相对对比较简简单(3)地地址变换换的速度度比较快快(4)对对磁盘的的管理比比较容易易主要缺点点：(1)程程序的模模块化性性能不好好(2)页页表很长长，需要要占用很很大的存存储空间间例如：虚拟存储储空间4GB，，页大小小1KB，则页页表的容容量为4M字，，16MB。2/28/202061计算机系系统结构构第第三章存存储储系统3.段段页式虚虚拟存储储器用户按段段写程序序,每每段分成成几个固固定大小小的页地址映象象方法：：每个程序序段在段段表中占占一行，，在段表中中给出页页表长度度和页表表的起始始地址，，页表中给给出每一一页在主主存储器器中的实实页号。。地址变换换方法：：先查段表表，得到到页表起起始地址址和页表表长度，，再查页表表找到要要访问的的主存实实页号，，把实页号号p与页页内偏移移d拼接接得到主主存实地地址。4.外外部地址址变换每个程序序有一张张外页表表，每一一页或每每个程序序段，在在外页表表中都有有对应的的一个存存储字。。3.2..3加加快内部部地址变变换的方方法造成虚拟拟存储器器速度降降低的主主要原因因：(1)要要访问问主存储储器必须须先查段段表或页页表，(2)可可能需需要多级级页表。。页表级数数的计算算公式：：其中：Nv为为虚拟存存储空间间大小，，Np为页页面的大大小，Nd为一一个页表表存储字字的大小小2/28/202065计算机系系统结构构第第三章存存储储系统例如：虚拟存储储空间大大小Nv＝4GB，页页的大小小Np＝＝1KB，每个个页表存存储字占占用4个个字节。。计算得得到页表表的级数数：通常仅把把1级页页表和2、3级级页表中中的一小小部分驻驻留在主主存中2/28/202066计算机系系统结构构第第三章存存储储系统1.目录录表基本思想想：用一个小小容量高高速存储储器存放放页表地址变换换过程：：把多用户户虚地址址中U与与P拼接接，相联联访问目目录表。。读出主主存实页页号p，，把p与与多用户户虚地址址中的D拼接得得到主存存实地址址。如果果相联访访问失败败，发出出页面失失效请求求。主要优点点：与页表放放在主存存中相比比，查表表速度快快。主要缺点点：可扩展性性比较差差,主存储器器容量大大时，目目录表造造价高，，速度低低。2/28/202068计算机系系统结构构第第三章存存储储系统2.快快慢表快表：TLB((TranslationLookasideBuffer)：小容量((几～几几十个字字)，高速硬件件实现，，采用相联联方式访访问。慢表：当快表中中查不到到时，从从主存的的慢表中中查找；；慢表按地地址访问问；用软软件实现现。快表与慢慢表也构构成一个个两级存存储系统统。主要存在在问题：：相联访问问实现困困难，速速度低2/28/202070计算机系系统结构构第第三章存存储储系统3.散散列函数数目的：把相联访访问变成成按地址址访问散列(Hashing)函数数：Ah＝H(Pv)采用散列列变换实实现快表表按地址址访问避免散列列冲突：：采用相等等比较器器地址变换换：相等比较较与访问问存储器器同时进进行4.虚拟拟存储器器举例例3.8：IMB370//168计算机机的虚拟拟存储器器中的快快表结构构及地址址变换过过程。虚拟地址址长36位，页页面大小小为4KB，每每个用户户最多占占用4K个页页面，最最多允许许16G个用户户，但同同时上机机的用户户数一般般不超过过6个。。采用了两两项新的的措施：：(1)采采用两个个相等比比较器，，以减少少散列冲冲突。(2)用用一个相相联寄存存器组，，把24位用的的多户号号U压缩缩成3位位，以缩缩短快表表的长度度。2/28/202073计算机系系统结构构第第三章存存储储系统3.2..4页页面替换换算法及及其实现现1.页页面替换换发生时时间：当发生页页面失效效时，要要从磁盘盘中调入入一页到到主存。。如果主主存储器器的所有有页面都都已经被被占用，，必须从从主存储储器中淘淘汰掉一一个不常常使用的的页面，，以便腾腾出主存存空间来来存放新新调入的的页面。。2.评评价页面面替换算算法好坏坏的标准准：一是命中中率要高高，二是算法法要容易易实现。。2/28/202075计算机系系统结构构第第三章存存储储系统3.页页面替换换算法的的使用场场合：(1)虚虚拟存储储器中，，主存页页面的替替换，一一般用软软件实现现。(2)Cache中的的块替换换，一般般用硬件件实现。。(3)虚虚拟存储储器的快快慢表中中，快表表存储字字的替换换，用硬硬件实现现。(4)虚虚拟存储储器中，，用户基基地址寄寄存器的的替换，，用硬件件实现。。(5)在在有些虚虚拟存储储器中，，目录表表的替换换。2/28/202076计算机系系统结构构第第三章存存储储系统4.主主要页面面替换算算法(1)随机算法法（RANDrandomalgorithm）算法简单单，容易易实现。。没有利用用历史信信息，没没有反映映程序的的局部性性命中率低低。(2)先进先出出算法(FIFOfirst-infirst-outalgorithm)容易实现现，利用用了历史史信息，，没有反映映局部性性。最先调入入的页面面，很可可能也是是要使用用的页面面2/28/202077计算机系系统结构构第第三章存存储储系统(3)近近期最少少使用算算法(LFUleastfrequentlyusedalgorithm))：既充充分利用用了历史史信息，，又反映映了程序序的局部部性实现现起来非非常困难难。(4)最最久没有有使用算算法(LRUleastrecentlyusedalgorithm))：把LFU算法中中的“多多”与““少”简简化成““有”与与“无””，实现现比较容容易(5)最最优替换换算法（OPToptimalreplacementalgorithm）：是是一种理理想算法法，仅用用作评价价其它页页面替换换算法好好坏的标标准。在虚拟存存储器中中，实际际上可能能采用的的只有FIFO和LRU两种种算法。。2/28/202078计算机系系统结构构第第三章存存储储系统例3.9：一个程序序共有5个页面面组成，，在程序序执行过过程中，，页面地地址流如如下：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4假设分配配给这个个程序的的主存只只有3个个页面。。(1)给给出用FIFO、LRU和OPT三三种页面面替换算算法对这这3个主主存页面面的调度度情况表表，并统统计页面面命中次次数。(2)计计算这LRU页页面替换换算法的的页面命命中率。。(3)假假设每个个数据平平均被访访问30次，为为了使LRU算算法的失失效率小小于10-5，计算页页面大小小至少应应该为多多少？2/28/202079计算机系系统结构构第第三章存存储储系统解：(1)FIFO、LRU和OPT的的页面命命中次数数分别为为2次、、4次和和5次(2)LRU页页面替换换算法的的页面命命中率为为：Hp＝4/10＝0.4(3)解得P>2000字页面大小小应该为为2K字字。2/28/202080计算机系系统结构构第第三章存存储储系统2/28/202081计算机系系统结构构第第三章存存储储系统例3.10：一个循环环程序，，依次使使用P1，P2，P3，P4页面面，分配配给它的的主存页页面数只只有2个个。在FIFO和LRU算法法中，发发生“颠簸”现象。。5.堆堆栈型替替换算法法定义：对任意一一个程序序的页地地址流作作两次主主存页面面数分配配，分别别分配m个个主存页页面和n个个主存页页面，并并且有m≤n。如果果在任何何时刻t，主主存页面面数集合合Bt都满满足关系系：Bt（m）Bt（n），则这类算算法称为为堆栈型型替换算算法。堆栈型算算法的基基本特点点是：随着分配配给程序序的主存存页面数数增加，，主存的的命中率率也提高高，至少少不下降降。2/28/202083计算机系系统结构构第第三章存存储储系统2/28/202084计算机系系统结构构第第三章存存储储系统3.2..5提提高主存存命中率率的方法法影响主存存命中率率的主要要因素：：(1)程程序在执执行过程程中的页页地址流流分布情情况。(2)所所采用的的页面替替换算法法。(3)页页面大小小。(4)主主存储器器的容量量(5)所所采用的的页面调调度算法法以下，对对后三个个因素进进行分析析。1.页面面大小与与命中率率的关系系页面大小小为某个个值时，，命中率率达到最最大。2/28/202085计算机系系统结构构第第三章存存储储系统页面大小小与命中中率关系系的解释释：假设At和At+1是相邻两两次访问问主存的的逻辑地地址，d＝｜At－At+1｜。如果ｄ＜＜Sp，，随着Sp增大大，At和At+1在同一页页面的可可能性增增加，即即Ｈ随着着Sp的的增大而而提高。。如果ｄ＞＞Sp，，At和At+1一定不在在同一个个页面内内。随着着Sp增增大，主主存页面面数减少少，页面面替换更更加频繁繁。Ｈ随随着Sp的增大大而降低低。2/28/202086计算机系系统结构构第第三章存存储储系统当Sp比比较小的的时候，，前一种种情况是是主要的的，Ｈ随随着Sp的增大大而提高高。当Sp达到到某一个个最大值值之后，，后一种种情况成成为主要要的，ＨＨ随着Sp的增增大而降降低。当页面增增大时，，造成的浪费费也要增增加当页面减减小时，，页表和页面面表在主主存储器中所所占的比比例将增加2/28/202087计算机系系统结构构第第三章存存储储系统2.主主存容量量与命中中率的关关系主存命中中率H随随着分配配给该程程序的主主存容量量S的增增加而单单调上升升。在S比较较小的时时候，H提高得得非常快快。随着着S的逐逐渐增加加，H提提高的速速度逐渐渐降低。。当S增增加到某某一个值值之后，，H几乎乎不再提提高。2/28/202088计算机系系统结构构第第三章存存储储系统3.页页面调度度方式与与命中率率的关系系请求式：：当使用到到的时候候，再调调入主存存预取式：：在程序重重新开始始运行之之前，把把上次停止运行行前一段段时间内内用到的的页面先先调入到到主存储器器，然后后才开始始运行程程序。预取式的的主要优优点：可以避免免在程序序开始运运行时，，频繁发发生页面面失效的情情况。预取式的的主要缺缺点：如果调入入的页面面用不上上，浪费费了调入入的时间间，占用了主主存的资资源。2/28/202089计算机系系统结构构第第三章存存储储系统3.3高高速缓缓冲存储储器3.3..1基基本工工作原理理3.3..2地地址映映象与变变换方法法3.3..3Cache替替换算法法及其实实现3.3..4Cache存存储系统统的加速速比3.3..5Cache的的一致性性问题3.3..6Cache的的预取算算法2/28/202090计算机系系统结构构第第三章存存储储系统2/28/202091计算机系系统结构构第第三章存存储储系统3.3..1基基本工工作原理理3.3..2地地址映象象与变换换方法地址映象象：把主存中中的程序序按照某某种规则则装入到到Cache中中，并建建立主存存地址与与Cache地地址之间间的对应应关系。。地址变换换：当程序已已经装入入到Cache之后，，在程序序运行过过程中，，把主存存地址变变换成Cache地址址。在选取地地址映象象方法要要考虑的的主要因因素：地址变换换的硬件件实现容容易、速速度要快快，主存空间间利用率率要高，，发生块冲冲突的概概率要小小。2/28/202093计算机系系统结构构第第三章存存储储系统1.全全相联映映象及其其变换映象规则则：主存的任任意一一块可以以映象到到Cache中的任意意一块。。（映象关系系有Cb×Mb种）地址变换换规则用硬件实实现非常常复杂2/28/202095计算机系系统结构构第第三章存存储储系统2.直直接映象象及其变变换映象规则则：主存储器器中一块块只能映映象到Cache的一一个特定定的块中中。Cache地址址的计算算公式：：b＝BmodCb其中：b为Cache块号，，B是主存存块号，，Cb是Cache块块数。实际上，，Cache地址址与主存存储器地地址的低低位部分分完全相相同。2/28/202096计算机系系统结构构第第三章存存储储系统直接映象象方式的的地址映映象规则则直接映象象方式的的地址变变换过程程：用主存地地址中的的块号B去访问问区号存存储器，，把读出出来的区区号与主主存地址址中的区区号E进进行比较较：比较结果果相等，，有效位位为1，，则Cache命中，，否则该该块已经经作废。。比较结果果不相等等，有效效位为1，Cache中的该该块是有有用的，，否则该该块是空空的。2/28/202098计算机系系统结构构第第三章存存储储系统直接映象象方式的的地址变变换规则则2/28/202099计算机系系统结构构第第三章存存储储系统提高Cache速度的的一种方方法：把区号存存储器与与Cache合合并成一一个存储储器2.直直接映象象及其变变换的优优缺点主要优点点：硬件实现现很简单单，不需需要相联联访问存存储器访问速度度也比较较快，实实际上不不需要进进行地址址变换主要缺点点：块的冲突突率比较较高。2/28/2020101计算机系系统结构构第第三章存存储储系统3.组组相联映映象及其其变换映象规则则：主存和Cache按同同样大小小划分成成块和组组。主存和Cache的组组之间采采用直接接映象方方式。在两个对对应的组组内部采采用全相相联映象象方式。。组相联映映象方式式的优点点：块的冲突突概率比比较低，，块的利用用率大幅幅度提高高，块失效率率明显降降低。组相联映映象方式式的缺点点：实现难度度和造价价要比直直接映象象方式高高。2/28/2020102计算机系系统结构构第第三章存存储储系统组相联映映象的地地址变换换过程：：用主存地地址中的的组号G按地址址访问块块表存储储器。把读出来来的一组组区号和和块号与与主存地地址中的的区号和和块号进进行相联比较较。如果有相相等的，，表示Cache命中中；如果全部部不相等等，表示示Cache没没有命中中。2/28/2020104计算机系系统结构构第第三章存存储储系统组相联映映象的地地址变换换提高Cache访问速速度的一一种方法法：用多个相相等比较较器来代代替相联联访问2/28/2020107计算机系系统结构构第第三章存存储储系统4.位位选择组组相联映映象及其其变换地址映象象规则：：主存和Cache都按按同样大大小分块块，Cache在分分块的基基础上再再分组，，主存按照照Cache的的组容量量分区。。主存的块块与Cache的组之之间采用用直接映映象方式式，主存中的的块与Cache中组组内部的的各个块块之间采采用全相相联映象象方式。。与组相联联映象方方式比较较：映象关系系明显简简单，实实现起来来容易。。在块表中中存放和和参与相相联比较较的只有有区号E2/28/2020108计算机系系统结构构第第三章存存储储系统位选择组组相联的的地址映映象规则则位选择组组相联的的地址变变换规则则5.段段相联映映象及其其变换映象规则则：主存和Cache都按按同样大大小分块块和段段之间采采用全相相联映象象方式段内部的的块之间间采用直直接映象象方式地址变换换过程：：用主存地地址中的的段号与与段表中中的主存存段号进进行相联联比较如果有相相等的，，用主存存地址的的段内块块号按地地址访问问Cache的的段号部部分。把读出的的段号s与主存存地址的的段内块块号b及及块内地地址w拼拼接起来来得到Cache地址址；2/28/2020111计算机系系统结构构第第三章存存储储系统段相联映映象地址址映象规规则段相联映映象地址址变换过过程段相联映映象方式式的优缺缺点主要优点点：段表比较较简单，，实现的的成本低低。例如：一个容量量为256KB的Cache，分成成8个段段，每段段2048块，，每块16B。。在段表存存储器中中只需要要存8个个主存地地址的段段号,而在块表表中要存存储8××2048＝16384个区区号，两者相差差2000多倍倍。主要缺点点：当发生段段失效时时，要把把本段内内已经建建立起来来的所有有映象关关系全部部撤消。。2/28/2020114计算机系系统结构构第第三章存存储储系统3.3..3Cache替换换算法及及其实现现使用的场场合：直接映象象方式实实际上不不需要替替换算法法全相联映映象方式式的替换换算法最最复杂主要用于于组相联、段相联联等映象象方式中中要解决的的问题：：记录每次次访问Cache的块块号在访问过过程中，，对记录录的块号号进行管管理根据记录录和管理理结果，，找出替替换的块块号主要特点点：全部用硬硬件实现现2/28/2020115计算机系系统结构构第第三章存存储储系统1.轮轮换法及及其实现现用于组相相联映象象方式中中，有两两种实现现方法。。方法一：：每块一一个计数数器在块表内内增加一一个替换换计数器器字段，，计数器的的长度与与Cache地地址中的的组内块块号字段段的长度度相同。。替换方法法及计数数器的管管理规则则：新装入或或替换的的块，它它的计数数器清0，同组组其它块块的计数数器都加加“1””。在同组中中选择计计数器的的值最大大的块作作为被替替换的块块。2/28/2020116计算机系系统结构构第第三章存存储储系统例3.11：Solar-16/65小型型机的Cache采用用位选择择组相联联映象方方式。Cache每组组的块数数为4，，因此，，每块用用一个2位的计计数器。。2/28/2020117计算机系系统结构构第第三章存存储储系统方法二：：每组一一个计数数器替换规则则和计数数器的管管理：本组有替替换时，，计数器器加“1”，计数器的的值就是是要被替替换出去去的块号号。例3.12：NOVA3机的的Cache采采用组相相联映象象方式，，Cache每每组的块块数为8，每组组设置一一个3位位计数器器。在需需要替换换时，计计数器的的值加““1”，，用计数数器的值值直接作作为被替替换块的的块号。。轮换法的的优点：：实现比较较简单，，能够利利用历史史上的块块地址流流情况轮换法的的缺点：：没有利用用程序的的局部性性特点2/28/2020118计算机系系统结构构第第三章存存储储系统2.LRU算算法及其其实现为每一块块设置一一个计数数器计数器的的长度与与块号字字段的长长度相同同计数器的的使用及及管理规规则：新装入或或替换的的块，计计数器清清0，同同组中其其它块的的计数器器加1。。命中块的的计数器器清0，，同组的的其它计计数器中中，凡计计数器的的值小于于命中块块计数器器原来值值的加1，其余余计数器器不变。。需要替换换时，在在同组的的所有计计数器中中选择计计数值最最大的计计数器，，它所对对应的块块被替换换。2/28/2020119计算机系系统结构构第第三章存存储储系统LRU算算法的优优缺点主要优点点：(1)命命中率比比较高，，(2)能能够比较较正确地地利用程程序的局局部性特特点，(3)充充分地利利用历史史上块地地址流的的分布情情况，(4)是是一种堆堆栈型算算法，随随着组内内块数增增加，命命中率单单调上升升。主要缺点点：控制逻辑辑复杂，，因为增加加了判断断和处理理是否命命中的情情况。2/28/2020120计算机系系统结构构第第三章存存储储系统例3.13：IBM370/165机的的Cache采采用组相相联映象象方式。。每组有有4块，，为了实实现LRU替换换算法，，在块表表中为每每一块设设置一个个2位位的计计数器。。在访问问Cache的的过程中中，块的的装入、、替换及及命中时时，计数数器的工工作情况况如表：2/28/2020121计算机系系统结构构第第三章存存储储系统3.比比较对法法以三个块块为例，，分别称称为块A、块B、块C表示方法法：用TAB＝1表示示B块块比A块更更久没有有被访问问过。如如果表示示块C最久久没有被被访问过过：

每次访问问之后要要改变触触发器的的状态在访问块块A之后后：TAB＝1，TAC＝1在访问块块B之后后：TAB＝0，TBC＝1在访问块块C之后后：TAC＝0，TBC＝02/28/2020122计算机系系统结构构第第三章存存储储系统每组３个个块的比比较对法法2/28/2020123计算机系系统结构构第第三章存存储储系统比较对法法硬件需需求量计计算：需要的触触发器个个数为：：与门个数数为Gb，每个门的的输入端端个数为为Gb-1当每组的的块数比比较多时时,采用分级级办法实实现实质上是是用降低低速度来来换取节节省器件件。例3.14：IBM3033机的的Cache，，每组的的块数为为16，，分3级级。从第第1级到到第3级级分别为为4、2、2。。共需要要触发器器个数为为：6＋＋4＋8＝18。如果果不分级级则需要要触发器器120个。2/28/2020124计算机系系统结构构第第三章存存储储系统比较对法法中每组组块数与与所需硬硬件的关关系2/28/2020125计算机系系统结构构第第三章存存储储系统4.堆堆栈法堆栈法的的管理规规则：把本次访访问的块块号与堆堆栈中保保存的所所有块号号进行相相联比较较。如果有相相等的，，则Cache命中。。把本次次访问块块号从栈栈顶压入入，堆栈栈内各单单元中的的块号依依次往下下移，直直至与本本次访问问的块号号相等的的那个单单元为止止，再往往下的单单元直止止栈底都都不变。。如果没有有相等的的，则Cache块失失效。本本次访问问的块号号从栈顶顶压入，，堆栈内内各单元元的块号号依次往往下移，，直至栈栈底，栈栈底单元元中的块块号被移移出堆栈栈，它就就是要被被替换的的块号。。2/28/2020126计算机系系统结构构第第三章存存储储系统例如：每组为4块，则则堆栈有有4个存存储单元元，每个单元元2位。。2/28/2020127计算机系系统结构构第第三章存存储储系统每组4块块的堆栈栈法逻辑辑图堆栈法的的主要优优点：块失效率率比较低低，因为为它采用用了LRU算法法。硬件实现现相对比比较简单单。堆栈法的的主要缺缺点：速度比较较低，因因为它需需要进行行相联比比较。堆栈法与与比较对对法所用用触发器器的比例例：其中，Gb是Cache每每一组的的块数。。当Gb大于8时时，堆栈栈法所用用的器件件明显少少于比较较对法。。2/28/2020129计算机系系统结构构第第三章存存储储系统3.3..4Cache存储储系统的的加速比比1.加加速比与与命中率率的关系系Cache存储储系统的的加速比比SP为：其中：Tm为主存储储器的访访问周期期，Tc为Cache的的访问周周期，T为Cache存储系系统的等等效访问问周期，，H为命中中率。提高加速速比的最最好途径径是提高高命中率率2/28/2020130计算机系系统结构构第第三章存存储储系统加速比SP能够接近近于期望望值是：加速比SP与命中率率H的关关系2/28/2020131计算机系系统结构构第第三章存存储储系统2.Cache命中中率与容容量的关关系Cache的命命中率随随它的容容量的增增加而提提高。关系曲线线可以近近似地表表示为：：2/28/2020132计算机系系统结构构第第三章存存储储系统3.Cache命中中率与块块大小的的关系在组相联联方式中中,块块大小对对命中率率非常敏敏感块很小时时，命中中率很低低。随着块大大小增加加命中率率也增加加,有一个极极大值当块非常常大时,,进入入Cache中中的数据据可能无无用当块大小小等于Cache容量量时,命命中率率将趋近近零4.Cache命中中率与组组数的关关系在组相联联方式中中,组组数对命命中率的的影响很很明显随着组数数的增加加，Cache的命中中率要降降低。当组数不不太大时时(小于于512),命命中率率的降低低很少当组数超超过一定定数量时时,命命中率的的下降非非常快2/28/2020133计算机系系统结构构第第三章存存储储系统Cache命中中率与块块大小的的关系2/28/2020134计算机系系统结构构第第三章存存储储系统3.3..5Cache的一一致性造成Cache与主存存的不一一致的原原因：(1)由由于CPU写写Cache，，没有立立即写主主存(2)由由于IO处理理机或IO设备备写主存存Cache的更更新算法法(1)写写直达法法，写通过法法，WT(Write--through)CPU的的数据写写入Cache时，同同时也写写入主存存(2)写写回法法，抵触修改改法，WB(Write-Back)CPU的的数据只只写入Cache，不不写入主主存，仅仅当替换换时，才才把修改改过的Cache块写写回主存存写回法与写直达法法的优缺点点比较：：(1)可可靠性，，写直达达法优于于写回法法。写直达法法能够始始终保证证Cache是是主存的的副本。。如果Cache发生错错误，可可以从主主存得到到纠正。。2/28/2020136计算机系系统结构构第第三章存存储储系统(2)与与主存的的通信量量，写回回法少于于写直达达法。对于写回回法：大多数操操作只需需要写Cache，不不需要写写主存；；当发生块块失效时时，可能能要写一一个块到到主存；；即使是读读操作，，也可能能要写一一个块到到主存。。对于写直直达法：：每次写操操作，必