现代计算机系统以存储器为中心3.1存储系统原理3.2虚拟存

现代计算机系统以存储器为中心3.1存储系统原理3.2虚拟存储器3.3高速缓冲存储器(Cache)3.4三级存储系统第3章存储系统3.1存储系统原理3.1.1存储系统的定义3.1.2存储系统的层次结构3.1.3存储系统的频带平衡3.1.4并行访问存储器3.1.5交叉访问存储器3.1.6无冲突访问存储器3.1.1存储系统的定义在一台计算机中，通常有多种存储器种类：主存储器、Cache、通用寄存器、缓冲存储器、磁盘存储器、磁带存储器、光盘存储器等材料工艺：ECL、TTL、MOS、磁表面、激光，SRAM，DRAM访问方式：随机访问、直接译码、先进先出、相联访问、块传送、文件组存储器的主要性能：速度、容量、价格速度用存储器的访问周期、读出时间、频带宽度等表示。容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示。价格用单位容量的价格表示，例如：$C/bit。组成存储系统的关键：把速度、容量和价格不同的多个物理存储器组织成一个存储器，这个存储器的速度最快，存储容量最大，单位容量的价格最便宜。1.存储系统的定义两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。虚拟存储器系统：对应用程序员透明Cache存储系统：对系统程序员以上均透明1.存储系统的定义两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。虚拟存储器系统：对应用程序员透明Cache存储系统：对系统程序员以上均透明由多个存储器构成的存储系统在一般计算机系统中，有两种存储系统：Cache存储系统：由Cache和主存储器构成主要目的：提高存储器速度虚拟存储系统：由主存储器和硬盘构成主要目的：扩大存储器容量2.存储系统的容量要求：提供尽可能大的地址空间能够随机访问方法有两种：只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址Cache存储系统另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中虚拟存储系统3.存储系统的价格计算公式：当S2》S1时，C≈C2S2与S1不能相差太大3.存储系统的价格计算公式：当S2》S1时，C≈C2S2与S1不能相差太大4.存储系统的速度表示方法：访问周期、存取周期、存储周期、存取时间等命中率定义：在M1存储器中访问到的概率其中：N1是对M1存储器的访问次数N2是对M2存储器的访问次数访问周期与命中率的关系：T＝HT1＋(1－H)T2当命中率H→1时，T→T1存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之比有关例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.96提高存储系统速度的两条途径：一是提高命中率H，二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率例3.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2＝105T１。如果要使访问效率到达e＝0.9，问需要有多高的命中率？解：0.9H＋90000(1-H)＝189999.1H＝89999计算得：H＝0.999998888877777…≈0.9999995.采用预取技术提高命中率方法：不命中时，把M2存储器中相邻多个单元组成的一个数据块取出来送入M1存储器中。计算公式：其中：H’是采用预取技术之后的命中率H是原来的命中率n为数据块大小与数据重复使用次数的乘积例3.3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率H＝0.8；假设数据的重复利用率为5，T2＝5T1。计算块大小为４个字时，Cache存储系统的命中率？并分别计算访问效率。计算公式：其中：H’是采用预取技术之后的命中率H是原来的命中率n为数据块大小与数据重复使用次数的乘积例3.3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率H＝0.8；假设数据的重复利用率为5，T2＝5T1。计算块大小为４个字时，Cache存储系统的命中率？并分别计算访问效率。解：n＝4×5＝20，采用预取技术之后，命中率提高到：例3.4：在一个虚拟存储系统中，T2＝105T１，原来的命中率只有0.8，如果访问磁盘存储器的数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：假设数据在主存储器中的重复利用率为m，根据前面给出的关系，有如下方程组：解方程组：由方程(1)得到：0.9H+90000-90000H=1证明方法一：采用预取技术之后，不命中率(1-H)降低ｎ倍：证明方法二：在原有命中率的计算公式中，把访问次数扩大到n倍。由于采用了预取技术，命中次数为：nN1＋(n-1)N2,不命中次数仍为N2，因此新的命中率为：证明方法二：在原有命中率的计算公式中，把访问次数扩大到n倍。由于采用了预取技术，命中次数为：nN1＋(n-1)N2,不命中次数仍为N2，因此新的命中率为：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+1各级存储器的主要主要性能特性CPU与主存储器的速度差距越来越大目前相差两个数量级今后CPU与主存储器的速度差距会更大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)采用存储系统（本章第二、第三节介绍）3.1.4并行访问存储器方法：把m字w位的存储器改变成为m/n字n×w位的存储器逻辑实现：把地址码分成两个部分，一部分作为存储器的地址另一部分负责选择数据主要缺点：访问冲突大(1)取指令冲突(2)读操作数冲突(3)写数据冲突(4)读写冲突3.1.4并行访问存储器方法：把m字w位的存储器改变成为m/n字n×w位的存储器逻辑实现：把地址码分成两个部分，一部分作为存储器的地址另一部分负责选择数据主要缺点：访问冲突大(1)取指令冲突(2)读操作数冲突(3)写数据冲突(4)读写冲突并行访问存储器结构框图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交叉访问存储器高位交叉访问存储器结构框图例3.6：用4M字×4位的存储芯片组成16M×32位的主存储器。共用存储芯片：用最高2位地址经译码后产生的信号，控制各组存储芯片CS。每组中的32根数据线分别对应直接相连，称为“线或”方式。2.低位交叉访问存储器主要目的：提高存储器访问速度实现方法：用地址码的低位部分区分存储体号参数计算:m：每个存储体的容量，n：总共的存储体个数，j：存储体的体内地址，j＝0，1，2，...，m-1k：存储体的体号，k＝0，1，2，...，n-1存储器地址A的计算公式为：A＝n×j＋k存储器的体内地址：Aj＝存储器的体号：Ak＝Amodn低位交叉访问存储器结构框图地址是编码方法：由8个存储体构成的低位交叉编址方式n个存储体分时启动一种采用流水线方式工作的并行存储器每存储体的启动间隔为：t＝其中：Tm为每个存储体的访问周期,n为存储体个数。访问冲突共有n个存储体，每个存储周期只能取到k个有效字,其余n-k个存储体有冲突。假设p(k)是k的概率密度函数，即p(1)是k＝1的概率，p(2)是k＝2的概率，…,p(n)是k＝n的概率。k的平均值为：N是每个存储周期能够访问到的平均有效字的个数。通常把N称为并行存储器的加速比。访问冲突共有n个存储体，每个存储周期只能取到k个有效字,其余n-k个存储体有冲突。假设p(k)是k的概率密度函数，即p(1)是k＝1的概率，p(2)是k＝2的概率，…,p(n)是k＝n的概率。k的平均值为：N是每个存储周期能够访问到的平均有效字的个数。通常把N称为并行存储器的加速比。定义转移概率为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-1Ｎ＝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-1Ｎ＝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-1例3.7：Star-100巨型机存储系统采用并行和交叉相结合的方式工作，有32个存储体低位交叉，每次并行读写512位，存储周期为1280ns，处理机字长32位，计算它的频带宽度Bm和峰值速度T。解：因为：n＝32，w＝512，Tm＝1280ns，Bm＝nw/tm＝32512b/1280ns＝12.8Gb/s＝1.6GB/s＝400MW/sT＝2.5ns与Tm相比，峰值速度提高512倍实际速度的提高要远远小于这个数字3.1.6无冲突访问存储器1.一维数组(向量)的无冲突访问存储器按连续地址访问，没有冲突，位移量为2的变址访问，速度降低一倍，…具体方法：存储体的个数取质数，且n≥向量长度。原因：变址位移量必然与存储体个数互质例如：Burroughs公司巨型科学计算机BSP存储体个数为17向量长度≤16我国研制的银河巨型向量机存储体的个数为37向量长度≤322.二维数组的无冲突访问存储器要求：一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突错位存储：按行、按列访问无冲突，但按对角线访问有冲突错位存储：按行、按列访问无冲突，但按对角线访问有冲突n×n二维数组无冲突访问存储 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 (P·Budnik和D·J·Kuck提出)：并行存储体的个数m≥n，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。当m＝22p＋1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1＝2P，d2＝1。例如：4×4的二维数组，取并行存储体的个数m＝5，由关系式m＝22P＋1，解得到p＝1，计算得到：d1＝21＝2d2＝1n×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个存储单元浪费主要优点：实现简单列元素顺序存储，行元素按地址取模顺序存储3.二维数组的无冲突访问存储器(之二) 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ：对于任意一个n×n的数组，如果能够找到满足n＝22P关系的任意自然数p，则这个二维数组就能够使用n个并行存储体实现按行、列、对角线和反对角线的无冲突访问。4×4数组用4个存储体的无访问冲突存储方案实现方法：假设aij是4×4数组中的任意一个元素，下标i和j都可以用两位二进制表示。假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址如下：体号地址：2(iLjH)＋(iHiLjL)体内地址：j其中：0≤i≤3，0≤j≤3主要优点：没有浪费的存储单元，主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。实现方法：假设aij是4×4数组中的任意一个元素，下标i和j都可以用两位二进制表示。假设i和j的高位和低位分别为iH、iL、jH和jL，则aij在无冲突并行存储器中的体号地址和体内地址如下：体号地址：2(iLjH)＋(iHiLjL)体内地址：j其中：0≤i≤3，0≤j≤3主要优点：没有浪费的存储单元，主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网络。3.2.1虚拟存储器工作原理3.2.2地址的映象和变换方法3.2.3加快内部地址变换的方法3.2.4页面替换算法及其实现3.2.5提高主存命中率的方法3.2虚拟存储器3.2.1虚拟存储器工作原理也称为虚拟存储系统、虚拟存储体系等其概念由英国曼彻斯特大学的Kilbrn等人于1961年提出到70年代广泛应用于大中型计算机系统目前，许多微型机也使用虚拟存储器把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页主存储器的页称为实页虚拟存储器中的页称为虚页内部地址变换：多用户虚拟地址Av变换成主存实地址A多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d，主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A。3.2.2地址的映象与变换三种地址空间：虚拟地址空间主存储器地址空间辅存地址空间地址映象：把虚拟地址空间映象到主存地址空间地址变换：在程序运行时，把虚地址变换成主存实地址三种虚拟存储器：页式虚拟存储器段式虚拟存储器段页式虚拟存储器3.2.2地址的映象与变换三种地址空间：虚拟地址空间主存储器地址空间辅存地址空间地址映象：把虚拟地址空间映象到主存地址空间地址变换：在程序运行时，把虚地址变换成主存实地址三种虚拟存储器：页式虚拟存储器段式虚拟存储器段页式虚拟存储器1.段式虚拟存储器地址映象方法：每个程序段都从0地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。地址变换方法：由用户号找到基址寄存器，读出段表起始地址，与虚地址中段号相加得到段表地址，把段表中的起始地址与段内偏移D相加就能得到主存实地址。主要优点：(1)程序的模块化性能好。(2)便于程序和数据的共享。(3)程序的动态链接和调度比较容易。(4)便于实现信息保护。主要缺点：(1)地址变换所花费的时间长，两次加法(2)主存储器的利用率往往比较低。(3)对辅存（磁盘存储器）的管理比较困难。2.页式虚拟存储器地址映象方法：地址变换方法：地址变换方法：主要优点：(1)主存储器的利用率比较高(2)页表相对比较简单(3)地址变换的速度比较快(4)对磁盘的管理比较容易主要缺点：(1)程序的模块化性能不好(2)页表很长，需要占用很大的存储空间例如：虚拟存储空间4GB，页大小1KB，则页表的容量为4M字，16MB。3.段页式虚拟存储器用户按段写程序,每段分成几个固定大小的页地址映象方法：每个程序段在段表中占一行，在段表中给出页表长度和页表的起始地址，页表中给出每一页在主存储器中的实页号。地址变换方法：先查段表，得到页表起始地址和页表长度，再查页表找到要访问的主存实页号，把实页号p与页内偏移d拼接得到主存实地址。4.外部地址变换每个程序有一张外页表，每一页或每个程序段，在外页表中都有对应的一个存储字。3.2.3加快内部地址变换的方法造成虚拟存储器速度降低的主要原因：(1)要访问主存储器必须先查段表或页表，(2)可能需要多级页表。页表级数的计算公式：其中：Nv为虚拟存储空间大小，Np为页面的大小，Nd为一个页表存储字的大小3.2.3加快内部地址变换的方法造成虚拟存储器速度降低的主要原因：(1)要访问主存储器必须先查段表或页表，(2)可能需要多级页表。页表级数的计算公式：其中：Nv为虚拟存储空间大小，Np为页面的大小，Nd为一个页表存储字的大小例如：虚拟存储空间大小Nv＝4GB，页的大小Np＝1KB，每个页表存储字占用4个字节。计算得到页表的级数：通常仅把1级页表和2、3级页表中的一小部分驻留在主存中1.目录表基本思想：用一个小容量高速存储器存放页表地址变换过程：把多用户虚地址中U与P拼接，相联访问目录表。读出主存实页号p，把p与多用户虚地址中的D拼接得到主存实地址。如果相联访问失败，发出页面失效请求。主要优点：与页表放在主存中相比，查表速度快。主要缺点：可扩展性比较差,主存储器容量大时，目录表造价高，速度低。2.快慢表快表：TLB(TranslationLookasideBuffer)：小容量(几～几十个字)，高速硬件实现，采用相联方式访问。慢表：当快表中查不到时，从主存的慢表中查找；慢表按地址访问；用软件实现。快表与慢表也构成一个两级存储系统。主要存在问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：相联访问实现困难，速度低快表：TLB(TranslationLookasideBuffer)：小容量(几～几十个字)，高速硬件实现，采用相联方式访问。慢表：当快表中查不到时，从主存的慢表中查找；慢表按地址访问；用软件实现。快表与慢表也构成一个两级存储系统。主要存在问题：相联访问实现困难，速度低3.散列函数目的：把相联访问变成按地址访问散列(Hashing)函数：Ah＝H(Pv)采用散列变换实现快表按地址访问避免散列冲突：采用相等比较器地址变换：相等比较与访问存储器同时进行4.虚拟存储器举例例3.8：IMB370/168计算机的虚拟存储器中的快表结构及地址变换过程。虚拟地址长36位，页面大小为4KB，每个用户最多占用4K个页面，最多允许16G个用户，但同时上机的用户数一般不超过6个。采用了两项新的措施：(1)采用两个相等比较器，以减少散列冲突。(2)用一个相联寄存器组，把24位用的多户号U压缩成3位，以缩短快表的长度。3.2.4页面替换算法及其实现1.页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存储器的所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。2.评价页面替换算法好坏的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ：一是命中率要高，二是算法要容易实现。3.2.4页面替换算法及其实现1.页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存储器的所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。2.评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。3.页面替换算法的使用场合：(1)虚拟存储器中，主存页面的替换，一般用软件实现。(2)Cache中的块替换，一般用硬件实现。(3)虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。(4)虚拟存储器中，用户基地址寄存器的替换，用硬件实现。(5)在有些虚拟存储器中，目录表的替换。4.主要页面替换算法(1)随机算法（RANDrandomalgorithm）算法简单，容易实现。没有利用历史信息，没有反映程序的局部性命中率低。(2)先进先出算法(FIFOfirst-infirst-outalgorithm)容易实现，利用了历史信息，没有反映局部性。最先调入的页面，很可能也是要使用的页面(3)近期最少使用算法(LFUleastfrequentlyusedalgorithm)：既充分利用了历史信息，又反映了程序的局部性实现起来非常困难。(4)最久没有使用算法(LRUleastrecentlyusedalgorithm)：把LFU算法中的“多”与“少”简化成“有”与“无”，实现比较容易(5)最优替换算法（OPToptimalreplacementalgorithm）：是一种理想算法，仅用作评价其它页面替换算法好坏的标准。在虚拟存储器中，实际上可能采用的只有FIFO和LRU两种算法。例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，计算页面大小至少应该为多少？解：(1)FIFO、LRU和OPT的页面命中次数分别为2次、4次和5次(2)LRU页面替换算法的页面命中率为：Hp＝4/10＝0.4(3)解得P>2000字页面大小应该为2K字。解：(1)FIFO、LRU和OPT的页面命中次数分别为2次、4次和5次(2)LRU页面替换算法的页面命中率为：Hp＝4/10＝0.4(3)解得P>2000字页面大小应该为2K字。例3.10：一个循环程序，依次使用P1，P2，P3，P4页面，分配给它的主存页面数只有2个。在FIFO和LRU算法中，发生“颠簸”现象。5.堆栈型替换算法定义：对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt（m）Bt（n），则这类算法称为堆栈型替换算法。堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。3.2.5提高主存命中率的方法影响主存命中率的主要因素：(1)程序在执行过程中的页地址流分布情况。(2)所采用的页面替换算法。(3)页面大小。(4)主存储器的容量(5)所采用的页面调度算法以下，对后三个因素进行 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 。1.页面大小与命中率的关系页面大小为某个值时，命中率达到最大。3.2.5提高主存命中率的方法影响主存命中率的主要因素：(1)程序在执行过程中的页地址流分布情况。(2)所采用的页面替换算法。(3)页面大小。(4)主存储器的容量(5)所采用的页面调度算法以下，对后三个因素进行分析。1.页面大小与命中率的关系页面大小为某个值时，命中率达到最大。页面大小与命中率关系的解释：假设At和At+1是相邻两次访问主存的逻辑地址，d＝｜At－At+1｜。如果ｄ＜Sp，随着Sp增大，At和At+1在同一页面的可能性增加，即Ｈ随着Sp的增大而提高。如果ｄ＞Sp，At和At+1一定不在同一个页面内。随着Sp增大，主存页面数减少，页面替换更加频繁。Ｈ随着Sp的增大而降低。当Sp比较小的时候，前一种情况是主要的，Ｈ随着Sp的增大而提高。当Sp达到某一个最大值之后，后一种情况成为主要的，Ｈ随着Sp的增大而降低。当页面增大时，造成的浪费也要增加当页面减小时，页表和页面表在主存储器中所占的比例将增加2.主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。3.页面调度方式与命中率的关系请求式：当使用到的时候，再调入主存预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。预取式的主要优点：可以避免在程序开始运行时，频繁发生页面失效的情况。预取式的主要缺点：如果调入的页面用不上，浪费了调入的时间，占用了主存的资源。3.3高速缓冲存储器3.3.1基本工作原理3.3.2地址映象与变换方法3.3.3Cache替换算法及其实现3.3.4Cache存储系统的加速比3.3.5Cache的一致性问题3.3.6Cache的预取算法3.3高速缓冲存储器3.3.1基本工作原理3.3.2地址映象与变换方法3.3.3Cache替换算法及其实现3.3.4Cache存储系统的加速比3.3.5Cache的一致性问题3.3.6Cache的预取算法3.3.1基本工作原理3.3.2地址映象与变换方法地址映象：把主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系。地址变换：当程序已经装入到Cache之后，在程序运行过程中，把主存地址变换成Cache地址。在选取地址映象方法要考虑的主要因素：地址变换的硬件实现容易、速度要快，主存空间利用率要高，发生块冲突的概率要小。1.全相联映象及其变换映象规则：主存的任意一块可以映象到Cache中的任意一块。（映象关系有Cb×Mb种）地址变换规则用硬件实现非常复杂地址变换规则用硬件实现非常复杂2.直接映象及其变换映象规则：主存储器中一块只能映象到Cache的一个特定的块中。Cache地址的计算公式：b＝BmodCb其中：b为Cache块号，B是主存块号，Cb是Cache块数。实际上，Cache地址与主存储器地址的低位部分完全相同。直接映象方式的地址映象规则直接映象方式的地址变换过程：用主存地址中的块号B去访问区号存储器，把读出来的区号与主存地址中的区号E进行比较：比较结果相等，有效位为1，则Cache命中，否则该块已经作废。比较结果不相等，有效位为1，Cache中的该块是有用的，否则该块是空的。直接映象方式的地址变换规则提高Cache速度的一种方法：把区号存储器与Cache合并成一个存储器提高Cache速度的一种方法：把区号存储器与Cache合并成一个存储器2.直接映象及其变换的优缺点主要优点：硬件实现很简单，不需要相联访问存储器访问速度也比较快，实际上不需要进行地址变换主要缺点：块的冲突率比较高。3.组相联映象及其变换映象规则：主存和Cache按同样大小划分成块和组。主存和Cache的组之间采用直接映象方式。在两个对应的组内部采用全相联映象方式。组相联映象方式的优点：块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。组相联映象方式的缺点：实现难度和造价要比直接映象方式高。组相联映象的地址变换过程：用主存地址中的组号G按地址访问块表存储器。把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。如果有相等的，表示Cache命中；如果全部不相等，表示Cache没有命中。组相联映象的地址变换组相联映象的地址变换提高Cache访问速度的一种方法：用多个相等比较器来代替相联访问4.位选择组相联映象及其变换地址映象规则：主存和Cache都按同样大小分块，Cache在分块的基础上再分组，主存按照Cache的组容量分区。主存的块与Cache的组之间采用直接映象方式，主存中的块与Cache中组内部的各个块之间采用全相联映象方式。与组相联映象方式比较：映象关系明显简单，实现起来容易。在块表中存放和参与相联比较的只有区号E位选择组相联的地址映象规则位选择组相联的地址变换规则位选择组相联的地址变换规则5.段相联映象及其变换映象规则：主存和Cache都按同样大小分块和段段之间采用全相联映象方式段内部的块之间采用直接映象方式地址变换过程：用主存地址中的段号与段表中的主存段号进行相联比较如果有相等的，用主存地址的段内块号按地址访问Cache的段号部分。把读出的段号s与主存地址的段内块号b及块内地址w拼接起来得到Cache地址；段相联映象地址映象规则段相联映象地址变换过程段相联映象方式的优缺点主要优点：段表比较简单，实现的成本低。例如：一个容量为256KB的Cache，分成8个段，每段2048块，每块16B。在段表存储器中只需要存8个主存地址的段号,而在块表中要存储8×2048＝16384个区号，两者相差2000多倍。主要缺点：当发生段失效时，要把本段内已经建立起来的所有映象关系全部撤消。3.3.3Cache替换算法及其实现使用的场合：直接映象方式实际上不需要替换算法全相联映象方式的替换算法最复杂主要用于组相联、段相联等映象方式中要解决的问题：记录每次访问Cache的块号在访问过程中，对记录的块号进行管理根据记录和管理结果，找出替换的块号主要特点：全部用硬件实现3.3.3Cache替换算法及其实现使用的场合：直接映象方式实际上不需要替换算法全相联映象方式的替换算法最复杂主要用于组相联、段相联等映象方式中要解决的问题：记录每次访问Cache的块号在访问过程中，对记录的块号进行管理根据记录和管理结果，找出替换的块号主要特点：全部用硬件实现1.轮换法及其实现用于组相联映象方式中，有两种实现方法。方法一：每块一个计数器在块表内增加一个替换计数器字段，计数器的长度与Cache地址中的组内块号字段的长度相同。替换方法及计数器的管理规则：新装入或替换的块，它的计数器清0，同组其它块的计数器都加“1”。在同组中选择计数器的值最大的块作为被替换的块。例3.11：Solar-16/65小型机的Cache采用位选择组相联映象方式。Cache每组的块数为4，因此，每块用一个2位的计数器。方法二：每组一个计数器替换规则和计数器的管理：本组有替换时，计数器加“1”，计数器的值就是要被替换出去的块号。例3.12：NOVA3机的Cache采用组相联映象方式，Cache每组的块数为8，每组设置一个3位计数器。在需要替换时，计数器的值加“1”，用计数器的值直接作为被替换块的块号。轮换法的优点：实现比较简单，能够利用历史上的块地址流情况轮换法的缺点：没有利用程序的局部性特点2.LRU算法及其实现为每一块设置一个计数器计数器的长度与块号字段的长度相同计数器的使用及管理规则：新装入或替换的块，计数器清0，同组中其它块的计数器加1。命中块的计数器清0，同组的其它计数器中，凡计数器的值小于命中块计数器原来值的加1，其余计数器不变。需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块被替换。LRU算法的优缺点主要优点：(1)命中率比较高，(2)能够比较正确地利用程序的局部性特点，(3)充分地利用历史上块地址流的分布情况，(4)是一种堆栈型算法，随着组内块数增加，命中率单调上升。主要缺点：控制逻辑复杂，因为增加了判断和处理是否命中的情况。LRU算法的优缺点主要优点：(1)命中率比较高，(2)能够比较正确地利用程序的局部性特点，(3)充分地利用历史上块地址流的分布情况，(4)是一种堆栈型算法，随着组内块数增加，命中率单调上升。主要缺点：控制逻辑复杂，因为增加了判断和处理是否命中的情况。例3.13：IBM370/165机的Cache采用组相联映象方式。每组有4块，为了实现LRU替换算法，在块表中为每一块设置一个2位的计数器。在访问Cache的过程中，块的装入、替换及命中时，计数器的工作情况如表：3.比较对法以三个块为例，分别称为块A、块B、块C表示方法：用TAB＝1表示B块比A块更久没有被访问过。如果表示块C最久没有被访问过：每次访问之后要改变触发器的状态在访问块A之后：TAB＝1，TAC＝1在访问块B之后：TAB＝0，TBC＝1在访问块C之后：TAC＝0，TBC＝0每组３个块的比较对法比较对法硬件需求量计算：需要的触发器个数为：与门个数为Gb，每个门的输入端个数为Gb-1当每组的块数比较多时,采用分级办法实现实质上是用降低速度来换取节省器件。例3.14：IBM3033机的Cache，每组的块数为16，分3级。从第1级到第3级分别为4、2、2。共需要触发器个数为：6＋4＋8＝18。如果不分级则需要触发器120个。比较对法中每组块数与所需硬件的关系比较对法中每组块数与所需硬件的关系4.堆栈法堆栈法的管理规则：把本次访问的块号与堆栈中保存的所有块号进行相联比较。如果有相等的，则Cache命中。把本次访问块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。如果没有相等的，则Cache块失效。本次访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底，栈底单元中的块号被移出堆栈，它就是要被替换的块号。例如：每组为4块，则堆栈有4个存储单元，每个单元2位。每组4块的堆栈法逻辑图堆栈法的主要优点：块失效率比较低，因为它采用了LRU算法。硬件实现相对比较简单。堆栈法的主要缺点：速度比较低，因为它需要进行相联比较。堆栈法与比较对法所用触发器的比例：其中，Gb是Cache每一组的块数。当Gb大于8时，堆栈法所用的器件明显少于比较对法。3.3.4Cache存储系统的加速比1.加速比与命中率的关系Cache存储系统的加速比SP为：其中：Tm为主存储器的访问周期，Tc为Cache的访问周期，T为Cache存储系统的等效访问周期，H为命中率。提高加速比的最好途径是提高命中率3.3.4Cache存储系统的加速比1.加速比与命中率的关系Cache存储系统的加速比SP为：其中：Tm为主存储器的访问周期，Tc为Cache的访问周期，T为Cache存储系统的等效访问周期，H为命中率。提高加速比的最好途径是提高命中率加速比SP能够接近于期望值是：加速比SP与命中率H的关系2.Cache命中率与容量的关系Cache的命中率随它的容量的增加而提高。关系曲线可以近似地表示为：3.Cache命中率与块大小的关系在组相联方式中,块大小对命中率非常敏感块很小时，命中率很低。随着块大小增加命中率也增加,有一个极大值当块非常大时,进入Cache中的数据可能无用当块大小等于Cache容量时,命中率将趋近零4.Cache命中率与组数的关系在组相联方式中,组数对命中率的影响很明显随着组数的增加，Cache的命中率要降低。当组数不太大时(小于512),命中率的降低很少当组数超过一定数量时,命中率的下降非常快Cache命中率与块大小的关系3.3.5Cache的一致性造成Cache与主存的不一致的原因：(1)由于CPU写Cache，没有立即写主存(2)由于IO处理机或IO设备写主存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)与主存的通信量，写回法少于写直达法。对于写回法：大多数操作只需要写Cache，不需要写主存；当发生块失效时，可能要写一个块到主存；即使是读操作，也可能要写一个块到主存。对于写直达法：每次写操作，必须写、且只写一个字到主存。实际上：写直达法的写次数很多、每次只写一个字；写回法是的写次数很少、每次要写一个块。举例说明：例3.15：写操作占总访存次数的20％,Cache的命中率为99％，每块为4个字。当Cache发生块替换时，有30％块需要写回到主存，其余的块因为没有被修改过而不必写回主存。试比较写回法与写直达法的访存通信量。解：对于写直达法：写主存次数占总访存次数的20％，对于写回法：(1－99％)×30％×4＝1.2％。因此，与主存的通信量，写回法要比写直达法少10多倍。(3)控制的复杂性,写直达法比写回法简单。对于写回法：要为每块设置一个修改位，而且要对修改位进行管理；为了保证Cache的正确性，通常要采用比较复杂的校验方式或校正方式。对于写直达法：不需要设置修改位；只需要采用简单的奇偶校验即可。由于Cache始终是主存的副本，Cache一旦有错误可以从主存得到纠正。(4)硬件实现的代价,写回法要比写直达法好。对于写直达法：为了缩短写Cache流水段的时间，通常要设置一个小容量的高速寄存器堆（后行写数缓冲站），每个存储单元要有数据、地址和控制状态等3部分组成。每次写主存时，首先把写主存的数据和地址写到高速寄存器堆中。每次读主存时，要首先判断所读数据是否在这个高速寄存器堆中。写回法不需要设置高速缓冲寄存器堆。(4)硬件实现的代价,写回法要比写直达法好。对于写直达法：为了缩短写Cache流水段的时间，通常要设置一个小容量的高速寄存器堆（后行写数缓冲站），每个存储单元要有数据、地址和控制状态等3部分组成。每次写主存时，首先把写主存的数据和地址写到高速寄存器堆中。每次读主存时，要首先判断所读数据是否在这个高速寄存器堆中。写回法不需要设置高速缓冲寄存器堆。写Cache的两种方法：(1)不按写分配法：在写Cache不命中时，只把所要写的字写入主存。(2)按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。解决Cache与主存不一致的主要方法：(1)共享Cache法。能根本解决Cache不一致，共享Cache可能成为访问的瓶颈，硬件复杂(2)作废法。当某一处理机写局部Cache时，同时作废其他处理机的局部Cache。(3)播写法。把写Cache的内容和地址放到公共总线上，各局部Cache随时监听公共总线(4)目录表法。在目录表中存放Cache一致性的全部信息。(5)禁止共享信息放在局部Cache中。Cache对系统程序员不透明。3.3.6Cache的预取算法预取算法有如下几种：(1)按需取。当出现Cache不命中时，才把需要的一个块取到Cache中。(2)恒预取。无论Cache是否命中，都把下一块取到Cache中。(3)不命中预取。当出现Cache不命中，把本块和下一块都取到Cache中。主要考虑因素：命中率是否提高，Cache与主存间通信量。恒预取能使Cache不命中率降低75～85％不命中预取能使Cache不命中率降低30～40％3.4三级存储系统虚拟存储系统和Cache存储系统可同时存在存储系统可以有多种构成方法不同的构成只是实现技术不同3.4.1存储系统的组织方式两个存储系统的组织方式：又称为：物理地址Cache存储系统目前的大部分处理机采用这种两级存储系统一个存储系统组织方式：又称为：虚拟地址Cache存储系统如Intel公司的i860等处理机采用这种组织方式全Cache系统：没有主存储器，由Cache和磁盘组成存储系统。3.4.1存储系统的组织方式两个存储系统的组织方式：又称为：物理地址Cache存储系统目前的大部分处理机采用这种两级存储系统一个存储系统组织方式：又称为：虚拟地址Cache存储系统如Intel公司的i860等处理机采用这种组织方式全Cache系统：没有主存储器，由Cache和磁盘组成存储系统。1.两个存储系统的组织方式2.一个存储系统组织方式3.全Cache系统3.4.2虚拟地址Cache虚拟存储器采用位选择组相联方式虚拟存储器中的一页等于主存储器的一个区用虚拟地址中的虚页号访问快表如果快表命中，把块表中的主存区号E与快表中的主存实页号P进行比较。若比较结果相等，则Cache命中。读出Cache的块号b，并与B、b、W拼接得到Cache地址。若Cache不命中，则用主存实页号P、及B和W拼接，得到主存实地址。若快表没有命中，通过软件查主存中的慢表3.4.3全Cache存储系统建立存储系统的目的：获得一个速度接近Cache，容量等于虚拟地址空间的存储器。这个存储器如何构成，具体分成几级来实现，只是具体的实现技术而已。随着计算机硬件和软件技术的发展，存储系统的实现技术也在不断改变。最直接最简单的方法：用一个速度很高，存储容量很大的存储器来实现。全Cache(all-Cache)是一种理想的存储系统。一种多处理机系统中的全Cache存储系统一种多处理机系统中的全Cache存储系统本章重点：1.存储系统的定义及主要性能计算。2.并行存储器的工作原理。3.虚拟存储系统的工作原理。4.虚拟存储器中加快地址变换的方法。5.虚拟存储系统的页面替换算法。6.Cache存储系统的地址映象及变换方法。7.Cache存储系统的替换算法。8.Cache存储系统的加速比。