计算机系统结构计算机系统结构第五章第五章 存储系统存储系统5.1 存储系统介绍存储系统 指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统。 计算机系统中，一般使用具有层次结构的存储系统，主要可分为三个存储层面：高速缓冲存储器、主存储器和辅助存储器。 高速缓冲存储器主要用于改善主存储器与中央处理器（CPU）的速度匹配问题，而辅助存储器则主要用于扩大计算机系统的存储空间。5.1.1 存储系统的层次结构层次存储系统是指把各种不同存储容量、存取速度、访问方式和单位存储价格的存储器，按照一定的层次结构组成多层存储器，并通过管理软件和辅助硬件有机组合成统一的存储体系，使计算机系统中使用到的各种程序和数据层次的分布到各个存储器中。辅助软硬件辅助软硬件主存主存辅存辅存图5-1主/辅存结构5.1.1 5.1.1 存储系统的定义存储系统的定义 在一台计算机中，通常有多种存储器在一台计算机中，通常有多种存储器种类：种类：主存储器、主存储器、Cache、通用寄存器、缓冲存储器、通用寄存器、缓冲存储器、磁盘存储器、磁带存储器、光盘存储器等磁盘存储器、磁带存储器、光盘存储器等材料工艺：材料工艺：ECL、TTL、MOS、磁表面、激光，、磁表面、激光，SRAM，DRAM访问方式：访问方式：随机访问、直接译码、先进先出、随机访问、直接译码、先进先出、 相联访问、相联访问、 块传送、文件组块传送、文件组 存储器的主要性能：存储器的主要性能：速度、容量、价格速度、容量、价格 速度速度用存储器的访问周期、读出时间、频带宽度等表示。 容量容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示。 价格价格用单位容量的价格表示，例如：$C/bit。 组成存储系统的关键：组成存储系统的关键：把速度、容量和价格不同的多个物理把速度、容量和价格不同的多个物理存储器组织成一个存储器，这个存储器的速度最快，存储容量存储器组织成一个存储器，这个存储器的速度最快，存储容量最大，单位容量的价格最便宜。最大，单位容量的价格最便宜。1. 1. 存储系统的定义存储系统的定义 两个或两个以上速度、容量和价格各不相同的存储器用硬件、两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。那个存储器。虚拟存储器系统：对应用程序员透明（通过操作系统的存储管虚拟存储器系统：对应用程序员透明（通过操作系统的存储管理系统调度）理系统调度）Cache存储系统：对系统程序员及以上均透明（全部用硬件调存储系统：对系统程序员及以上均透明（全部用硬件调度）度）由多个存储器构成的存储系统由多个存储器构成的存储系统n 在一般计算机系统中，有两种存储系统：在一般计算机系统中，有两种存储系统：CacheCache存储系统：由存储系统：由CacheCache和主存储器构成和主存储器构成 主要目的：提高存储器速度主要目的：提高存储器速度虚拟存储系统：由主存储器和硬盘构成虚拟存储系统：由主存储器和硬盘构成 主要目的：扩大存储器容量主要目的：扩大存储器容量2.2.存储系统的容量存储系统的容量对存储系统进行编址的要求：对存储系统进行编址的要求：提供尽可能大的地址空间提供尽可能大的地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址 CacheCache存储系统存储系统另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中 虚拟存储系统虚拟存储系统3.3.存储系统的价格存储系统的价格计算公式：当S2S1时，CC2 S2与S1不能相差太大4. 4. 存储系统的速度存储系统的速度表示方法：表示方法：访问周期、存取周期、存储周期、存取时间等命中率定义：命中率定义：在在M1存储器中访问到的概率存储器中访问到的概率其中：N1是对M1存储器的访问次数N2是对M2存储器的访问次数访问周期与命中率的关系：访问周期与命中率的关系：THT1(1H)T2 当命中率H1时，TT1存储系统的访问效率：存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之比有关访问效率主要与命中率和两级存储器的速度之比有关例例3.13.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：解：当当H H0.90.9时，时，e e1 11 1(0.9(0.95(15(10.9)0.9)0.720.72当当H H0.990.99时，时，e e2 21 1(0.99(0.995(15(10.99)0.99)0.960.96提高存储系统速度的两条途径：提高存储系统速度的两条途径：一是提高命中率一是提高命中率H H，二是两个存储器的速度不要相差太大二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提依靠提高命中率高命中率例例5.25.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2105 T。如果要使访问效率到达e0.9，问需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得： H0.999998888877777 0.9999995. 采用预取技术提高命中率采用预取技术提高命中率 方法：方法：不命中时，把不命中时，把M2存储器中相邻多个单存储器中相邻多个单元组成的一个数据块取出来送入元组成的一个数据块取出来送入M1存储器中。存储器中。 计算公式：计算公式： 其中：H是采用预取技术之后的命中率 H是原来的命中率 n为数据块大小与数据重复使用次数的乘积例例5.35.3：在一个Cache存储系统中， T25T1。当Cache的块大小为一个字时，命中率H0.8。假设数据的重复利用率为5，Cache块大小为个字，Cache存储系统的命中率？并分别计算访问效率。解：解：n4520， 采用预取技术之后，命中率提高到：例例5.45.4：在一个虚拟存储系统中，T2105 T，原来的命中率只有0.8，如果访问磁盘存储器的数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：解：假设数据在主存储器中的重复利用率为m，根据前面给出的关系，有如下方程组：解方程组：解方程组：由方程(1)得到：0.9H+90000-90000H=15.1.2 5.1.2 存储系统的层次结构存储系统的层次结构多个层次的存储器多个层次的存储器： 第第1层：层：Register Files(寄存器堆寄存器堆) 第第2层：层： Buffers(Lookahead)(先行缓冲站先行缓冲站) 第第3层：层： Cache(高速缓冲存储器高速缓冲存储器) 第第4层：层： Main Memory(主存储器主存储器) 第第5层：层： Online Storage(联机存储器联机存储器) 第第6层：层： Off-line Storage(脱机存储器脱机存储器)用用i表示层数，表示层数，则有：工作周期工作周期TiTi+1，存储容量：存储容量：SiSi+1，单位单位价格：价格：CiCi+1各级存储器的主要主要性能特性各级存储器的主要主要性能特性 CPUCPU与主存储器的速度差距越来越大与主存储器的速度差距越来越大 目前相差目前相差两个数量级 今后今后CPUCPU与主存储器的速度差距会更大与主存储器的速度差距会更大5.1.3 5.1.3 存储系统的频带平衡存储系统的频带平衡例例5.5：Pentium4的指令执行速度为8GIPS，CPU取指令8GW/s，访问数据16GW/s，各种输入输出设备访问存储器1GW/s，三项相加，要求存储器的频带宽度不低于25GW/s。如果采用PC133内存，主存与CPU速度差188倍如果采用PC266内存，主存与CPU速度差94倍解决存储器频带平衡方法解决存储器频带平衡方法(1)多个存储器并行工作多个存储器并行工作(2)设置各种缓冲存储器设置各种缓冲存储器(3)采用存储系统采用存储系统5.1.4 5.1.4 并行访问存储器并行访问存储器方法：方法：把把m字字w位的存储器改变成为位的存储器改变成为m/n字字nw位的存储器位的存储器逻辑实现：逻辑实现：把地址码分成两个部分，一部分作为存储器的地址把地址码分成两个部分，一部分作为存储器的地址另一部分负责选择数据另一部分负责选择数据主要缺点：访问冲突大主要缺点：访问冲突大 (1)(1)取指令冲突取指令冲突 (2)(2)读操作数冲突读操作数冲突 (3)(3)写数据冲突写数据冲突 (4)(4)读写冲突读写冲突 并行访问存储器结构框图并行访问存储器结构框图1. 1. 高位交叉访问存储器高位交叉访问存储器主要目的：主要目的：扩大存储器容量扩大存储器容量实现方法：实现方法：用地址码的高位部分区分存储体号用地址码的高位部分区分存储体号参数计算方法参数计算方法: m：每个存储体的容量，n：总共的存储体个数，j：存储体的体内地址，j0，1，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器的地址：Amkj 存储器的体内地址：AjA mod m。存储器的体号：Ak 5.1.5 5.1.5 交叉访问存储器交叉访问存储器 高位交叉访问存储器结构框图高位交叉访问存储器结构框图2. 2. 低位交叉访问存储器低位交叉访问存储器 主要目的：主要目的：提高存储器访问速度提高存储器访问速度 实现方法：实现方法：用地址码的低位部分区分存储体号用地址码的低位部分区分存储体号 参数计算参数计算: m：每个存储体的容量，n：总共的存储体个数，j：存储体的体内地址，j0，1，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器地址A的计算公式为：Anjk 存储器的体内地址：Aj存储器的体号：AkA mod n 低位交叉访问存储器结构框图低位交叉访问存储器结构框图 地址是编码方法：地址是编码方法： 由由8 8个存储体构成的低位交叉编址方式个存储体构成的低位交叉编址方式 n n个存储体分时启动个存储体分时启动 一种采用流水线方式工作的并行存储器 每存储体的启动间隔为：t 其中：Tm为每个存储体的访问周期, n为存储体个数。访问冲突访问冲突 共有共有n n个存储体，每个存储周期只能取到个存储体，每个存储周期只能取到k k个有效字个有效字, ,其余其余n-kn-k个存储体有冲突。个存储体有冲突。假设p(k)是k的概率密度函数，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值为：N是每个存储周期能够访问到的平均有效字的个数。通常把 N N称为并行存储器的加速比。称为并行存储器的加速比。定义转移概率为g，即读出的是转移指令，且转移成功的概率。这时有： p(1)p(1)g g p(2) p(2)(1-p(1)g(1-p(1)g(1-g)g(1-g)g p(3) p(3)(1-p(1)-p(2)g(1-p(1)-p(2)g(1-g)(1-g)2 2g g p(k) p(k)(1-g)(1-g)k-1k-1g (g (k1,2,n1) p(n) p(n)(1-g)(1-g)n-1n-1 g g(1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)n-2n-2g g n(1-g)n(1-g)n-1n-1以上共以上共n n行，前行，前n-2n-2行分别为等比级数行分别为等比级数把把n-1n-1行拆分成行拆分成2 2项项则：则：1g1g2(1-g)g2(1-g)g3(1-g)3(1-g)2 2g g (n-1)(1-g)(n-1)(1-g)n-2n-2g gn(1-g)n(1-g)n-1n-11-(1-g)1-(1-g)n-1n-11-(1-g)1-(1-g)n-1n-1 (1-g)-(1-g)(1-g)-(1-g)n-1n-1 (1-g)(1-g)2 2-(1-g)-(1-g)n-1n-1 (1-g)(1-g)n-2n-2-(1-g)-(1-g)n-1n-1 n(1-g)n(1-g)n-1n-11 1(1-g)(1-g)(1-g)(1-g)2 2(1-g)(1-g)n-2n-2(1-g)(1-g)n-1n-1例例5.7：Star-100巨型机存储系统采用并行和交叉相结合的方式工作，有32个存储体低位交叉，每次并行读写512位，存储周期为1280ns，处理机字长32位，计算它的速度提高多少倍？和频带宽度Bm。解：解：因为：n32，w512，Tm1280ns， Bmnw/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s提高提高512512倍倍实际速度的提高要远远小于这个数字实际速度的提高要远远小于这个数字 5.1.6 5.1.6 无冲突访问存储器无冲突访问存储器1. 1. 一维数组一维数组( (向量向量) )的无冲突访问存储器的无冲突访问存储器 按连续地址访问，没有冲突， 位移量为2的变址访问，速度降低一倍， 具体方法：具体方法： 存储体的个数取质数，且存储体的个数取质数，且nn向量长度。向量长度。 原因：原因：变址位移量必然与存储体个数互质 例如：例如：Burroughs公司巨型科学计算机BSP 存储体个数为17 向量长度16我国研制的银河巨型向量机 存储体的个数为37 向量长度322. 2. 二维数组的无冲突访问存储器二维数组的无冲突访问存储器要求：要求：一个一个nn的二维数组，按行、列、对角线和反对角线访的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。问，并且在不同的变址位移量情况下，都能实现无冲突访问。顺序存储：顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突 错位存储：错位存储： 按行、按列访问无冲突， 但按对角线访问有冲突nn二维数组无冲突访问存储方案二维数组无冲突访问存储方案( P Budnik 和和 D J Kuck提出提出 ) ：并行存储体的个数并行存储体的个数mn，并且取质数，同时还要在行、列，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。方向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开设同一列相邻元素在并行存储器中错开d1个存储体存放，个存储体存放，同一行相邻元素在并行存储器中错开同一行相邻元素在并行存储器中错开d2个存储体存放。当个存储体存放。当m22p1（p为任意自然数）时，能够同时实现按行、按列、为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：按对角线和按反对角线无冲突访问的充要条件是：d12P，d21。例如：例如：44的二维数组，取并行存储体的个数的二维数组，取并行存储体的个数m5，由关系式，由关系式m22P1，解得到，解得到p1，计算得到：，计算得到：d1212 d21 nn数组中的任意一个元素数组中的任意一个元素aij在无冲突并行存储器中的体号地址在无冲突并行存储器中的体号地址和体内地址的计算公式：和体内地址的计算公式：体号地址：体号地址：(2P ijk) MOD m 体内地址：体内地址：i 其中：0in1，0jn1，k是数组的第一个元素a00所在体号地址，m是并行存储体的个数，要求mn且为质数，p是满足m22P1关系的任意自然数。主要缺点：主要缺点：浪费存储单元对于对于nn数组数组, ,有有(m-n) m个存储单元浪费个存储单元浪费 主要优点：主要优点：实现简单 列元素顺序存储，行元素按地址取模顺序存储列元素顺序存储，行元素按地址取模顺序存储45453. 3. 二维数组的无冲突访问存储器二维数组的无冲突访问存储器( (之二之二) )规则：规则：对于任意一个对于任意一个nn的的数组，如果能够找到满足数组，如果能够找到满足n22P关关系的任意自然数系的任意自然数p，则这个二维数组就能够使用，则这个二维数组就能够使用n个并行存储个并行存储体体实现按行、列、对角线和反对角线的无冲突访问。实现按行、列、对角线和反对角线的无冲突访问。4444数组用数组用4 4个存储体的无访问冲突存储方案个存储体的无访问冲突存储方案实现方法：实现方法： 假设假设aij是是4444数组中的任意一个元素，数组中的任意一个元素，下标下标i和和j都可以用两位都可以用两位二进制表示。假设二进制表示。假设i和和j的高位和低位分别为的高位和低位分别为iH、iL、jH和和jL，则则aij在无冲突并行存储器中的体号地址和体内地址如下：在无冲突并行存储器中的体号地址和体内地址如下：体号地址：体号地址：2(iL jH)(iH iL jL) 体内地址：体内地址：j 其中：其中：0i3，0j3主要优点：主要优点：没有浪费的存储单元没有浪费的存储单元，主要缺点：主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网在执行并行读和写操作时需要借助比较复杂的对准网络络。5.2 高速缓冲存储器Cache计算机系统为改善CPU与主存储器之间的速度匹配问题，在CPU和主存储器之间加入一个高速、小容量的缓冲存储器Cache，构成Cache主存储器的存储系统，使得存储系统对CPU而言，速度接近于高速缓冲存储器Cache，存储容量接近于主存储器。Cache存储器主要由三个部分组成：(1)Cache存储器，用于存放由主存储器调入的指令与数据块；(2)地址转换部件，用于实现主存储器地址到Cache存储器地址的转换；(3)替换部件，当缓存满时根据指定策略进行数据块替换，并对地址转换部件做对应修改。Cache工作原理Cache工作原理(续1)系统工作时，地址转换部件维护一个映射表，用于确定Cache存储器中是否有所要访问的块，以及确定其位置。该映射表中的每一项对应于Cache存储器的一个分块，用于指出当前该块中存放的信息对应于主存储器的哪个分块。为提高CPU对Cache存储器的访问命中率，Cache存储器的工作原理是基于程序访问局部性原理程序访问局部性原理的，它不断地将与当前指令集相关联的一部分后继指令集从主存储器读取到Cache存储器，以供CPU访问，从而达到存储系统与CPU速度匹配的目的。5.2.2 地址映象与变换方法地址映象是将主存储器中的数据分块按某种规则装入Cache存储器中，并建立主存储器地址与Cache存储器地址之间的对应关系。地址变换是指当主存储器中的分块按照地址映象方法装入Cache存储器后，在实际运行过程中，主存储器地址如何转换成为相应的Cache存储器地址。地址的映象和变换是紧密相关的，采用什么样的地址映象方法，就有与这种映象方法相对应的地址变换方法。5.2.2 地址映象与变换方法u在选取地址映象方法要考虑的主要因素：在选取地址映象方法要考虑的主要因素：1.地址变换的硬件容易实现，地址变换的速度要快， 2.Cache空间利用率要高， 3.3.发生块冲突的概率要小。发生块冲突的概率要小。一般可分为以下几种类型：(1)全相联映象及其变换方法(2)直接映象及其变换方法(3)组相联映象及其变换方法(1)全相联映象及其变换方法全相联映象是指主存储器中的任意分块可以被放置到Cache存储器中的任意一个位置。其中，主存储器与Cache存储器的分块大小相同。映像规则(1)全相联映象及其变换方法 主存储器块号与Cache存储器块号的映象关系存放在一个用高速缓存实现的目录表中，目录表中的存储单元由三部分组成：主存储器块号、Cache存储器块号，以及有效位。(2)直接映象及其变换方法直接映象是指将主存储器中的某一分块在Cache存储器中都有唯一对应的位置。主存储器按Cache大小分成若干区，在区内进行分块，分块大小与Cache存储器中分块大小相等，主存储器中每个区包含分块的个数与Cache存储器中分块的个数相等。uCache地址的计算公式： bB mod Cb 其中：b为Cache块号，B是主存块号， Cb是Cache块数。u实际上，Cache地址与主存储器地址的低位完全部分相同(2)直接映象及其变换方法地址映像规则(2)直接映象及其变换方法u地址变换过程：地址变换过程： 用主存地址中的块号用主存地址中的块号B去访问区号存去访问区号存储器，把读出来的区号与主存地址中的区号储器，把读出来的区号与主存地址中的区号E进行比较进行比较 比较结果相等，有效位为比较结果相等，有效位为1，则，则Cache命中，否则该块已经作废。命中，否则该块已经作废。 比较结果不相等，有效位为比较结果不相等，有效位为1，Cache中的该块被其他块占用，否则该块是空的。中的该块被其他块占用，否则该块是空的。9/24/2024(2)直接映象及其变换方法直接映像地址变换规则(2)直接映象及其变换方法u提高提高Cache速度的一种方法：速度的一种方法： 把区号存储器与把区号存储器与Cache合并成一个存储器合并成一个存储器(2)直接映象及其变换方法直接映象及其变换的优缺点：直接映象及其变换的优缺点： 主要优点：主要优点： 硬件实现很简单，不需要相联访问存储器硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不需要进行地址访问速度也比较快，实际上不需要进行地址 变换。变换。 主要缺点：主要缺点： 块的冲突率比较高。块的冲突率比较高。9/24/2024(3)组相联映象及其变换方法组相联映象把主存储器和Cache按同样大小划分成块，再将主存储器和Cache按同样大小划分成组，每一组由相同的块数组成，然后将主存储器按Cache大小分成区，主存储器每个区的组数与Cache的组数相同。组相联映象在各组之间是直接映象，但组内各块之间是全相联映象。(3)组相联映象及其变换方法映像规则(3)组相联映象及其变换方法u地址变换过程：地址变换过程： 用主存地址中的组号用主存地址中的组号G按地址访问块表存储按地址访问块表存储器。把读出来的一组区号和块号与主存地址中的器。把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。区号和块号进行相联比较。 如果有相等的，表示如果有相等的，表示Cache命中；否则表示命中；否则表示Cache没有命中。没有命中。9/24/2024(3)组相联映象及其变换方法(续1)地址变换规则(3)组相联映象及其变换方法 组相联映象方式的优点：组相联映象方式的优点： 块的冲突概率比较低，块的冲突概率比较低， 块的利用率大幅度提高，块的利用率大幅度提高， 块失效率明显降低。块失效率明显降低。 组相联映象方式的缺点：组相联映象方式的缺点： 实现难度和造价要比直接映象方式高。实现难度和造价要比直接映象方式高。(3)组相联映象及其变换方法u提高提高Cache访问速度的一种方法：访问速度的一种方法： 把块表存储器中一个相联比较的组按把块表存储器中一个相联比较的组按块方向展开存放。块方向展开存放。 用多个相等比较器来代替相联访问，用多个相等比较器来代替相联访问，加块查表的速度。加块查表的速度。9/24/2024(3)组相联映象及其变换方法9/24/20245.2.3 Cache替换算法及实现当CPU读Cache时，有两种可能： (一) 需要的数据已在Cache中，那么只需直接访问Cache； (二)是需要的数据尚未装入Cache，则CPU从主存储器中读取信息的同时，需按所需的映象规则将该地址所在的那块存储内容从主存储器拷贝到Cache中。对于第二种情况，若该块所映象的Cache块位置已全部被占满，则必须选择将Cache中的某一块替换出去，需要Cache替换算法解决如何选择被换出块的问题。Cache替换算法随机替换算法随机替换算法随机法是Cache替换算法中最简单的一种。这种方法是随机地选择可以被替换的一块进行替换。有些系统设置一个随机数产生器，依据所产生的随机数选择替换块，进行替换。先进先出替换算法先进先出替换算法(FIFO)这种策略总是把最先调入的Cache块作为被替换的块替换出去。最近最少使用替换算法最近最少使用替换算法(LRU) LRU法是依据各块的使用情况，总是选择最近最久没被使用的块作为被替换的块进行替换。因为目前为止最久没有被访问的块，很可能也是将来最少访问的块。Cache替换算法堆栈替换算法堆栈替换算法堆栈替换算法使用栈顶到栈底各项的先后次序来记录Cache中或Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最近被访问过的块的块号，栈底恒存放近期最久没有被访问过的块的块号，即准备被替换掉的块的块号（LRU堆栈实现）。比较对替换算法比较对替换算法LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时间和次数， 然后按照各个块被访问过的时间顺序排序，从中找出最久没有被访问过的块。用一个两态的触发器的状态来表示两个块之间的先后顺序，再经过门电路就可以找到LRU块。Cache替换算法比较对法比较对法 以三个块为例，三个块分别称为块以三个块为例，三个块分别称为块A、B、Cu 表示方法：表示方法： 用用TAB1表示表示 B块比块比 A 块更久没有被访问过。块更久没有被访问过。 如果要表示块如果要表示块 C 最久没有被访问过：最久没有被访问过： 从最近到最远分别是：从最近到最远分别是：A、B、C 或或 B、A、CCache替换算法即：即：u每次访问之后要改变触发器的状态。每次访问之后要改变触发器的状态。 在访问块在访问块A之后：之后：TAB1，TAC1 在访问块在访问块B之后：之后：TAB0，TBC1 在访问块在访问块C之后：之后：TAC0，TBC09/24/2024Cache替换算法每组个块的比较对法每组个块的比较对法9/24/2024Cache替换算法u硬件需求量计算：硬件需求量计算： 需要的触发器个数为：需要的触发器个数为： 与门的个数为与门的个数为Gb个，每个与门的输入个，每个与门的输入端个数为端个数为Gb-1个个, 其中：其中：Gb为每组的块数。为每组的块数。u 当每组的块数比较多时当每组的块数比较多时 采用分级的办法实现。采用分级的办法实现。 实质上是用降低速度来换取节省器件。实质上是用降低速度来换取节省器件。9/24/2024Cache替换算法比较对法中每组数与所需硬件的关系比较对法中每组数与所需硬件的关系9/24/2024Cache替换算法例如例如：IBM 3033机的机的Cache，每组的块数为每组的块数为16，分，分3级。从第级。从第1级到第级到第3级分别为级分别为4、2、2。共需要触发器个数为：共需要触发器个数为：64818。 如果不分级则需要触发器如果不分级则需要触发器120个。个。9/24/2024Cache替换算法 堆栈法的管理规则：堆栈法的管理规则： 把本次访问的块号与堆栈中保存的所有块号把本次访问的块号与堆栈中保存的所有块号进行相联比较。进行相联比较。 如果有相等的，则如果有相等的，则Cache命中。把本次访问命中。把本次访问的块号从栈顶压入，堆栈内各单元中的块号依的块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。单元为止，再往下的单元直止栈底都不变。 9/24/2024Cache替换算法 如果没有相等的，则如果没有相等的，则Cache块失效。本次块失效。本次访问的块号从栈顶压入，堆栈内各单元的块号访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底，栈底单元中的块号被依次往下移，直至栈底，栈底单元中的块号被移出堆栈，它就是要被替换的块号。移出堆栈，它就是要被替换的块号。9/24/2024Cache替换算法u堆栈法的主要优点：堆栈法的主要优点： 块失效率比较低，因为它采用了块失效率比较低，因为它采用了LRU算算法。法。 硬件实现相对比较简单。硬件实现相对比较简单。u 堆栈法的主要缺点：堆栈法的主要缺点： 速度比较低，因为它需要进行相联比较。速度比较低，因为它需要进行相联比较。9/24/2024Cache替换算法各种各种Cache替换算法的优缺点替换算法的优缺点(1)随机替换算法： 优点是简单，容易实现；缺点是没有考虑到Cache块的使用历史情况，没有利用程序的局部性特点，从而命中率较低，失效率较高。(2)FIFO替换算法： 优点是由于它不需记录各个块的使用情况，实现起来也较容易；缺点是虽然考虑到了各块进入Cache的先后顺序这一使用“历史”，但还不能正确地反映程序的局部性特点。(3) LRU替换算法： LRU算法较好地反映了程序的局部性特点，失效率较低，但LRU算法比较复杂，硬件实现较困难，特别是当组的大小增加时，LRU的实现代价将越来越高。5.2.4 cache一致性问题由于Cache中保存的是主存储器的一部分副本，则有可能在一段时间内，主存储器中某单元的内容与Cache中对应单元的内容出现不一致。 例如： （1）CPU在写入Cache时，修改了Cache中某单元的内容，而主存储器中对于单元的内容却可能没有改变，还是原来的。此时，如果I/O处理器或其他处理器要用到主存储器中的数据，则可能会出现主存储器内容跟不上Cache对应内容的变化而造成的数据不一致性错误。 （2）I/O处理机或其他处理机已修改了主存储器某个单元的内容，而Cache中对于单元的副本内容却可能没有改变。这时，如果CPU访问Cache并读取数据，也可能会出现Cache内容跟不上主存储器对于内容的变化而产生的不一致性错误。5.2.4 cache一致性问题对于Cache中的副本与主存储器中的内容能否保持一致，是Cache能否可靠工作的一个关键问题。要解决这个问题，首先要选择合适的Cache更新算法。对Cache不一致性问题的解决，主要是需要更新主存储器内容，一般有两种常用更新算法： (1) 写直达法写直达法:又称写通过法，又称写通过法，WT（Write-through） CPU在执行写操作时，把数据同时写入在执行写操作时，把数据同时写入Cache和主存。和主存。 (2) 写回法写回法:又称为抵触修改法，又称为抵触修改法，WB（Write-Back） CPU的数据只写入的数据只写入Cache，不写入主存。不写入主存。 仅当替换时，才把修改过的仅当替换时，才把修改过的Cache块写回到主存。块写回到主存。5.2.4 cache一致性问题8383写回法与写直达法的优缺点比较：写回法与写直达法的优缺点比较：(1)写回法较写直达法速度要快；(2)在可靠性方面，写回法不如写直达法；(3)写直达法的控制较比写回法简单；(4)写直达法易于实现，但硬件实现代价相对较大。5.2.4 cache一致性问题84845.2.4 cache一致性问题例如：例如：写操作占总访存次数的操作占总访存次数的20，Cache的命中率的命中率为为99，每块为，每块为4个字。当个字。当Cache发生块替换时，有发生块替换时，有30块需要写回到主存，其余的块因为没有被修改过而块需要写回到主存，其余的块因为没有被修改过而不必写回主存。试比较写回法与写直达法的访存通信不必写回主存。试比较写回法与写直达法的访存通信量。则对于写直达法，写主存次数占总访存次数的量。则对于写直达法，写主存次数占总访存次数的20,而对于写回法，而对于写回法，(199)3041.2。 因此，与主存的通信量，写回法要比写直达法少因此，与主存的通信量，写回法要比写直达法少10多倍。多倍。85855.2.4 cache一致性问题进行“写”操作时，也可能出现写不命中。由于“写”操作并不需要访问该单元中的所有的数据，在出现Cache写不命中时，无论写回法还是写直达法，都需要考虑在写操作的同时是否将其调入Cache，一般有两种选择： (1)按写分配法：写失效时，除了完成写入主存储器外，还把该写地址单元所在的块由主存储器调入Cache。 (2)不按写分配法：写失效时，只完成写入主存储器，而不把该写地址单元所在的块从主存储器调入Cache。5.2.5 Cache性能分析评价Cache存储器，主要是看Cache命中率的高低，命中率主要与下面几个因素有关：(1)程序在执行过程中的地址流分布情况，其中地址流的分布情况是由程序本身决定的；可通过编写适应Cache的代码；(2)当发生Cache块失效时，所采用的替换算法；(3)Cache的容量，块的大小、块的总数；(4)采用组相联时组的大小等。 5.2.5 Cache性能分析(续1)Cache命中率与容量的关系Cache的容量越大，则Cache的命中率将越高。5.2.5 Cache性能分析(续2)Cache命中率与块大小的关系在采用组相联映象方式的Cache中，当Cache的容量一定时，块的大小也会影响命中率。5.2.5 Cache性能分析(续3)Cache命中率与组数的关系当Cache的容量一定时，分组的数目对于Cache命中率的影响也是很明显的：组数分得越多，命中率会下降，命中率会随着组数的增加而下降；当组数不太大时，命中率降低得相当少；当组数超过一定数量时，命中率下降非常快。Cache系统加速定义： 5.2.5 Cache性能分析(续4)从Cache系统加速比定义可以看出，Cache系统的加速比与Cache的命中率H和主存储器访问周期Tm及Cache访问周期Tc有关，而Cache系统中，主存储器的访问周期和Cache的访问周期一般是一定的，所以只要提高Cache的命中率，就可以获得较高的Cache系统加速比，提高存储系统的速度。5.3 Cache性能的优化除加速比定义衡量Cache存储系统性能外，Cache存储器的平均访问时间是测评存储系统性能的一种更好的指标： 平均访问时间 = 命中时间 + 失效率*失效开销从平均访问时间这一指标来看，还可以从3个方面对Cache的性能进行优化： （1）降低Cache失效率 （2）减少失效开销 （3）减少命中时间5.3.1降低Cache失效率的方法Cache失效的原因分析：(1)强制性失效：对块第一次访问，该块不在Cache中，需从主存储器中将该块调入Cache中。(2)容量失效：如果程序执行时，Cache容纳不了所需的所有块，则会发生容量失效。当某些块被替换后，可能随后重新访问又被调入。(3)冲突失效：在组相联映象或直接相联映象中，如果太多的冲突块映象到同一组中，产生冲突，则可能会出现某个块刚被替换出去，随后又重新访问而被再次调入。5.3.1降低Cache失效率的方法(续1)增加Cache块大小 Cache命中率和块大小的关系：在Cache容量一定时，当块大小开始增加时，命中率也开始增加，但当增加到一定程度后，命中率反而开始下降。 失效率和命中率是两个相关的概念，命中率增加时，失效率下降；命中率下降时，失效率反而增加。另外，Cache容量越大，则使失效率达到最低的块大小就越大。5.3.1降低Cache失效率的方法(续2)增加Cache容量 Cache容量越大，命中率越高，相关，失效率则越低。但增加Cache容量不仅会增加成本，而且也可能会因为复杂的电路结构等而增加Cache的访问时间。指令和数据硬件预取 指令和数据硬件预取是指在处理器访问指令和数据之前，就把它们预取到Cache中或预取到可以比存储器访问速度更快的外部缓冲区中。指令预取一般有恒预取和不命中预取两种方法。5.3.1降低Cache失效率的方法(续3)编译器控制预取 硬件预取的一种替代方法是在编译时加入预取指令，在数据被使用之前发出预取请求。有以下两种方式：(1)寄存器预取：将数据预取到寄存器中。(2)Cache预取：只将数据预取到Cache中，并不放入寄存器。编译器优化以降低Cache失效率这种方法是采用软件方法来优化Cache性能，试图通过优化编译时间来改善Cache性能：(1)程序代码和数据重组(2)循环交换(3)分块5.3.2 减少Cache失效开销与降低失效率一样，减少Cache失效开销同样可以缩短Cache存储器的平均访问时间并提高Cache的性能。 (1)采用两级Cache：在原Cache和存储器之间增加一级Cache，构成两级Cache。其中第一级Cache可以让它小到足以与快速的处理器运行时钟周期相匹配，而第二级Cache则让它大到足以捕获到对内存进行的大多数访问，从而有效地降低了失效开销。 (2)让读失效优先于写：提高写直达Cache性能最重要的方法是设置一个容量适中的写缓存。然而写缓存中可能包含读失效时所需单元的最新值，这个值尚未写入存储器，导致了存储器访问的复杂化。解决方法是让读失效等待，直至写缓存为空。5.3.2 减少Cache失效开销(续1)合并写缓冲区 采用写直达法的Cache要有一个写缓冲区，如果写缓冲区为空，就把被替换的数据和相应地址写入缓冲区。请求字处理技术 处理器在同一时刻只需要调入块中的一个字(即请求字)，不必等到全部的块调入Cache，就可以将该字送往处理器并重新启动处理器进行访问，一般有以下两种策略：(1)请求字优先：调块时，先向存储器请求处理器所要的请求字。一旦该请求字到达即送往处理器，让处理器继续执行，同时可以从存储器中调入该块的其他字。(2)提前重启动：在请求字没到达处理器时，处理器处于等待状态。5.3.3 减少命中时间除了通过降低失效率和减少失效开销来优化Cache性能的方法以外，还可通过减少命中时间来优化Cache的性能。命中时间也是平均访问时间的一个组成部分，它的重要性在于它会影响处理器的时钟频率。(1)小而简单的Cache减少命中时间 采用容量小、结构简单的Cache，这样快表较小，查表的速度较快，从而有效地提高了Cache的访问速度。(2)路预测减少命中时间 路预测要求Cache中预留特殊的比较位，用来预测下一次访问Cache时可能会用到的路或块。5.3.3 减少命中时间(续1)(3)踪迹Cache(Trace Cache)减少命中时间 踪迹Cache中存储的是处理器所执行的动态指令序列，而不是用于存储主存储器中给出的静态指令序列。例如，在Pentium4处理器的踪迹Cache中由于使用了译码微操作，从而节省了译码时间。(4)流水线Cache访问 流水线Cache访问方法是将流水线、Cache访问以及使一级Cache命中时的有效时延分散到几个时钟周期。它实际上并不能真正减少Cache命中时间，但可以提供较短的周期时间和高宽带。5.4 主存储器及性能优化主存储器也即主存，是存储层次中紧接着Cache下面的一个层次。它是计算机硬件的一个重要部件，其作用是存放指令和数据，并能由中央处理器直接随机存取。它既被用来满足Cache的请求，也被用作I/O接口。主存的性能指标主要是存储容量、存取时间、存储周期和存储器带宽。存储容量是指在一个存储器中可以容纳的存储单元总数；存取时间是指从启动到完成一次存储器操作所经历的时间；存储周期是指连续启动两次操作所需间隔的最小时间；存储器带宽是指单位时间里存储器所存取的信息量。5.4.1 主存储器目前，就主存的速度来看，仍不能满足CPU的要求，这是因为主存速度的改进跟不上CPU速度的提高。Cache的引入，在很大程度上弥补了主存和CPU速度上的巨大差距。主存的延迟因影响Cache的失效开销而成为Cache主要关心的问题，另外，随着第二级Cache的广泛应用，主存带宽对于Cache来说也越来越重要了。在有Cache的存储层次中，主存的性能主要是用主存的延迟和带宽来衡量的。5.4.2主存储器性能优化增加存储器的宽度增加存储器的宽度 增加数据带宽可以增加同时访问的数据量，提高数据的吞吐量，最简单的方法是增加存储器的宽度。 第一级Cache的宽度通常为一个字，因为CPU大部分的访存都是一个字的宽度的。在不具有第二级Cache的计算机系统中，主存的宽度一般与Cache的宽度相同。因此，可以将Cache和主存的宽度同时增加为原来宽度的两倍或以上，从而增加了主存的宽度。5.4.2 主存储器性能优化(续1)多体交叉存储器采用模m多体交叉编址，利用多体潜在的并行性进行并行存取。其中每个存储体的宽度一般为一个字的宽度，通过同时向多个个体发送地址对它们同时进行访问，从而一次可以读或者写多个字。有两种基本的多体交叉方法：高位多体交叉方法和低位多体交叉方法。5.4.2 主存储器性能优化(续2)高位多体交叉方法高位交叉存储器的地址高位部分用于区分不同的存储体，低位部分用于选择一个存储体体内不同的存储单元。5.4.2 主存储器性能优化(续3)低位多体交叉方法低位交叉存储器的地址位使用方法与高位交叉存储器刚好相反：低位部分用于区分不同的存储体，高位部分用于选择一个存储体体内不同的存储单元。5.5 虚拟存储器虚拟存储器是由主存和联机的外存共同组成的，在主存的容量不能满足要求时，数据可存放在外存中，但在程序中仍按地址进行访问外存空间。在虚拟存储器中，应用程序员是直接用机器指令的地址码对整个程序统一编址的，虚拟存储器的空间大小取决于它能产生的地址位数。从程序员的角度看，存储空间扩大了，并可以放得下整个程序，程序不必作任何修改就可以以接近于实际主存的速度在这个虚拟存储器上运行。5.5 虚拟存储器$1 虚拟存储器工作原理虚拟存储器工作原理把主存储器、磁盘存储器和虚拟存储器都划分把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页，成固定大小的页，主存储器的页称为实页，虚拟存储器中的页称主存储器的页称为实页，虚拟存储器中的页称为虚页。为虚页。1081085.5 虚拟存储器u内部地址变换：多用户虚拟地址内部地址变换：多用户虚拟地址Av变换成主变换成主存实地址存实地址A 多用户虚拟地址中的页内偏移多用户虚拟地址中的页内偏移D D直接作为主存直接作为主存实地址中的页内偏移实地址中的页内偏移d d，主存实页号主存实页号p p与它的页与它的页内偏移内偏移d d直接拼接起来就得到主存实地址直接拼接起来就得到主存实地址A A。u外部地址变换：外部地址变换： 首先查外页表得到磁盘存储器的实地址，把首先查外页表得到磁盘存储器的实地址，把磁盘存储器的实地址和主存储器的实页号送入磁盘存储器的实地址和主存储器的实页号送入输入输出处理机，把要访问数据所在的一整页输入输出处理机，把要访问数据所在的一整页都从磁盘存储器调入到主存储器。都从磁盘存储器调入到主存储器。1091095.5 虚拟存储器1101105.5 虚拟存储器$2 地址的映象和变换方法地址的映象和变换方法 三种地址空间：三种地址空间：虚拟地址空间虚拟地址空间 主存储器地址空间主存储器地址空间 辅存地址空间辅存地址空间 地址映象：地址映象：把虚拟地址空间映象到主存地址把虚拟地址空间映象到主存地址空间空间 地址变换：地址变换：在程序运行时，把虚地址变换成在程序运行时，把虚地址变换成主存实地址主存实地址1111115.5 虚拟存储器因地址映象和变换方法不同，有三种虚拟存储因地址映象和变换方法不同，有三种虚拟存储器：器： 页式虚拟存储器页式虚拟存储器 段式虚拟存储器段式虚拟存储器 段页式虚拟存储器段页式虚拟存储器1121125.5 虚拟存储器1 1、段式虚拟存储器段式虚拟存储器u 地址映象方法地址映象方法：每个程序段都从：每个程序段都从0 0地址开始地址开始编址，长度可长可短，可以在程序执行过程中编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。动态改变程序段的长度。1131135.5 虚拟存储器1141145.5 虚拟存储器u地址变换方法：地址变换方法： 由用户号找到基址寄存器，从基址寄存器中由用户号找到基址寄存器，从基址寄存器中读出段表起始地址，读出段表起始地址， 把起始地址与多用户虚地址中段号相加得到把起始地址与多用户虚地址中段号相加得到段表地址，段表地址， 把段表中的起始地址与段内偏移把段表中的起始地址与段内偏移D D相加就能得相加就能得到主存实地址。到主存实地址。115115第三节虚拟存储器1161165.5 虚拟存储器u主要优点：主要优点： (1) (1) 程序的模块化性能好。程序的模块化性能好。 (2) (2) 便于程序和数据的共享。便于程序和数据的共享。 (3) (3) 程序的动态链接和调度比较容易。程序的动态链接和调度比较容易。 (4) (4) 便于实现信息保护。便于实现信息保护。1171175.5 虚拟存储器u主要缺点：主要缺点： (1) (1) 地址变换所花费的时间比较长，做两次地址变换所花费的时间比较长，做两次加法运算。加法运算。 (2) (2) 主存储器的利用率往往比较低。主存储器的利用率往往比较低。 (3) (3) 对辅存（磁盘存储器）的管理比较困难。对辅存（磁盘存储器）的管理比较困难。1181185.5 虚拟存储器2 2、页式虚拟存储器页式虚拟存储器u 地址映象方法地址映象方法1191195.5 虚拟存储器u地址变换方法地址变换方法1201205.5 虚拟存储器u主要优点：主要优点： (1)(1)主存储器的利用率比较高主存储器的利用率比较高 (2) (2)页表相对比较简单页表相对比较简单 (3) (3)地址变换的速度比较快地址变换的速度比较快 (4) (4)对磁盘的管理比较容易对磁盘的管理比较容易1211215.5 虚拟存储器u主要缺点主要缺点： (1)(1)程序的模块化性能不好程序的模块化性能不好 (2) (2)页表很长，需要占用很大的存储空间页表很长，需要占用很大的存储空间 例如：虚拟存储空间例如：虚拟存储空间4 4GBGB，页大小页大小1 1KBKB，则页表则页表的容量为的容量为4 4M M字，字，1616MBMB。1221225.5 虚拟存储器3、段页式虚拟存储器、段页式虚拟存储器 用户按照段来编写程序，每个段分成几个用户按照段来编写程序，每个段分成几个固定大小的页。固定大小的页。u 地址映象方法：地址映象方法： 每个程序段在段表中占一行，每个程序段在段表中占一行， 在段表中给出该程序段的页表长度和页表的在段表中给出该程序段的页表长度和页表的起始地址，起始地址， 页表中给出这个程序段的每一页在主存储器页表中给出这个程序段的每一页在主存储器中的实页号。中的实页号。1231235.5 虚拟存储器1241245.5 虚拟存储器u地址变换方法：地址变换方法： 先查段表，得到该程序段的页表起始地址和页表先查段表，得到该程序段的页表起始地址和页表长度，长度， 再查页表找到要访问的主存实页号，再查页表找到要访问的主存实页号， 最后把实页号最后把实页号p p与页内偏移与页内偏移d d拼接得到主存的实地拼接得到主存的实地址。址。1251255.5 虚拟存储器1261265.5 虚拟存储器u地址变换方法：地址变换方法： 先查段表，得到该程序段的页表起始地址和先查段表，得到该程序段的页表起始地址和页表长度，页表长度， 再查页表找到要访问的主存实页号，再查页表找到要访问的主存实页号， 最后把实页号最后把实页号p p与页内偏移与页内偏移d d拼接得到主存的拼接得到主存的实地址。实地址。1271275.5 虚拟存储器4、外部地址变换、外部地址变换 在操作系统中，把页面失效当作一种异常故在操作系统中，把页面失效当作一种异常故障来处理。障来处理。 每个用户程序都有一张外页表，虚拟地址空每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有间中的每一页或每个程序段，在外页表中都有对应的一个存储字。对应的一个存储字。1281285.5 虚拟存储器1291295.5 虚拟存储器$3 加快内部地址变换速度的方法加快内部地址变换速度的方法u造成虚拟存储器速度降低的主要原因：造成虚拟存储器速度降低的主要原因： (1) 要访问主存储器必须先查段表或页表，要访问主存储器必须先查段表或页表， (2) 可能需要多级页表。可能需要多级页表。页表级数的计算公式：页表级数的计算公式：其中： Nv为虚拟存储空间大小， Np为页面的大小， Nd为一个页表存储字的大小1301305.5 虚拟存储器例如：例如：虚拟存储空间大小Nv4GB，页的大小Np1KB，每个页表存储字占用4个字节。计算得到页表的级数：通常仅把1级页表和2、3级页表中的一小部分驻留在主存中1311315.5 虚拟存储器1、目录表、目录表 基本思想：用一个小容量高速存储器存放页表。基本思想：用一个小容量高速存储器存放页表。1321325.5 虚拟存储器 基本思想：基本思想： 用一个小容量高速存储器存放页表。用一个小容量高速存储器存放页表。 地址变换过程：地址变换过程： 把多用户虚地址中把多用户虚地址中U U与与P P拼接，相联访问目拼接，相联访问目录表。读出主存实页号录表。读出主存实页号p p，把把p p与多用户虚地址与多用户虚地址中的中的D D拼接得到主存实地址。如果相联访问失败，拼接得到主存实地址。如果相联访问失败，发出页面失效请求。发出页面失效请求。 133133 主要优点：主要优点： 与页表放在主存中相比，查表速度快。与页表放在主存中相比，查表速度快。 主要缺点：主要缺点： 可扩展性比较差可扩展性比较差, , 主存储器容量大时，目录表造价高，速度主存储器容量大时，目录表造价高，速度低。低。5.5 虚拟存储器1341342、快慢表、快慢表5.5 虚拟存储器135135u快表：快表： TLB(Translation Lookaside Buffer)： 小容量小容量(几几十个字)， 高速硬件实现高速硬件实现， 采用相联方式访问采用相联方式访问。5.5 虚拟存储器1361365.5 虚拟存储器u慢表：慢表： 当快表中查不到时，从存放在主存中的慢表中查找； 慢表按地址访问； 用软件实现。137137u 快表与慢表实际上也构成了一个两级存储系快表与慢表实际上也构成了一个两级存储系统。统。u 主要存在问题：相联访问实现困难，速度主要存在问题：相联访问实现困难，速度比较低。比较低。5.5 虚拟存储器1381383 3、散列函数散列函数 目的：目的：把相联访问变成按地址访问，从而加把相联访问变成按地址访问，从而加大快表容量大快表容量 散列（散列（HashingHashing）函数：函数：AhH（Pv），20位左右68位5.5 虚拟存储器1391395.5 虚拟存储器140140 采用散列变换实现快表按地址访问采用散列变换实现快表按地址访问 避免散列冲突：避免散列冲突：采用相等比较器采用相等比较器 地址变换过程：相等比较与访问存储器同时地址变换过程：相等比较与访问存储器同时进行进行5.5 虚拟存储器1411415.5 虚拟存储器1421424、虚拟存储器举例、虚拟存储器举例 例例5.8：IMB370/168计算机的虚拟存储器中的快表结构及地址变换过程。 虚拟地址长48位，页面大小为4KB，每个用户最多占用4K 个页面，最多允许16G个用户，但同时上机的用户数一般不超过6个。 5.5 虚拟存储器143143采用了两项新的措施：采用了两项新的措施： (1) 采用两个相等比较器，以减少散列冲突。采用两个相等比较器，以减少散列冲突。 (2) 用一个相联寄存器组，把用一个相联寄存器组，把24位用户号位用户号 U 压缩成压缩成 3 位，以缩短快表的长度。位，以缩短快表的长度。5.5 虚拟存储器1441445.5 虚拟存储器145145$4 页面替换算法及其实现方法页面替换算法及其实现方法u页面替换发生时间：页面替换发生时间： 当发生页面失效时，要从磁盘中调入一当发生页面失效时，要从磁盘中调入一页到主存。页到主存。 如果主存储器的所有页面都已经被占用，如果主存储器的所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。面，以便腾出主存空间来存放新调入的页面。u 评价页面替换算法好坏的标准：评价页面替换算法好坏的标准： 一是命中率要高，二是算法要容易实现。一是命中率要高，二是算法要容易实现。5.5 虚拟存储器146146u 页面替换算法的使用场合：页面替换算法的使用场合： (1) 虚拟存储器中，主存页面的替换，一般用软件实现。 (2) Cache中的块替换，一般用硬件实现。 (3) 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。 (4) 虚拟存储器中，用户基地址寄存器的替换，用硬件实现。 (5) 在有些虚拟存储器中，目录表的替换。5.5 虚拟存储器1471475.5 虚拟存储器1、页面替换算法、页面替换算法(1)随机算法随机算法（RAND random algorithmRAND random algorithm） 算法简单，容易实现。没有利用历史信息，算法简单，容易实现。没有利用历史信息，没有反映程序的局部性，命中率低。没有反映程序的局部性，命中率低。(2)先进先出算法先进先出算法（FIFO first-in first-FIFO first-in first-out algorithmout algorithm） 比较容易实现，利用了历史信息，没有反比较容易实现，利用了历史信息，没有反映程序的局部性。映程序的局部性。 最先调入主存的页面，很可能也是经常要最先调入主存的页面，很可能也是经常要使用的页面。使用的页面。148148(3)近期最少使用算法近期最少使用算法( (LFU least LFU least frequently used algorithm)frequently used algorithm) 既充分利用了历史信息，又反映了既充分利用了历史信息，又反映了程序的局部性程序的局部性 实现起来非常困难。实现起来非常困难。(4)(4)最久没有使用算法最久没有使用算法（LRU least LRU least recently used algorithmrecently used algorithm） 把把LFULFU算法中的算法中的“多多”与与“少少”简化成简化成“有有”与与“无无”，实现比较容易，实现比较容易5.5 虚拟存储器149149(5)最优替换算法最优替换算法（OPT optimal replacement OPT optimal replacement algorithmalgorithm）：）： 是一种理想算法是一种理想算法, ,仅用作评价其它页面替换仅用作评价其它页面替换算法好坏的标准算法好坏的标准 在虚拟存储器中在虚拟存储器中, ,实际上可能采用的只有实际上可能采用的只有FIFOFIFO和和LRULRU两种算法两种算法5.5 虚拟存储器150150例例5.9：一个程序共有一个程序共有5 5个页面组成，在程序个页面组成，在程序执行过程中，页面地址流如下：执行过程中，页面地址流如下：P1P1，P2P2，P1P1，P5P5，P5P5，P1P1，P3P3，P4P4，P3P3，P4P4 假设在程序执行过程中分配给这个程序假设在程序执行过程中分配给这个程序的主存储器只有的主存储器只有3 3个页面。个页面。5.5 虚拟存储器151151(1)(1)给出用给出用 FIFOFIFO、LRULRU和和OPT OPT 三种页面替换三种页面替换算法对这算法对这3 3个主存的调度情况表，并统计页个主存的调度情况表，并统计页面命中次数。面命中次数。(2)(2)计算这计算这LRULRU页面替换算法的页面命中率。页面替换算法的页面命中率。(3)(3)假设每个数据平均被访问假设每个数据平均被访问2020次，为了使次，为了使LRULRU算法的页面失效率小于算法的页面失效率小于1010-5-5，计算页面，计算页面大小至少应该为多少？大小至少应该为多少？5.5 虚拟存储器152152解：解：(1)(1)FIFOFIFO、LRULRU和和OPTOPT的页面命中次数分的页面命中次数分别为别为2 2次、次、4 4次和次和5 5次次 (2)(2)LRULRU页面替换算法的页面命中率为：页面替换算法的页面命中率为：H Hp p4/104/100.40.4(3) (3) 解得解得 P P 30003000字字5.5 虚拟存储器1531535.5 虚拟存储器154154例例5.10：一个循环程序，依次使用一个循环程序，依次使用P1P1，P2P2，P3P3，P4P4四个页面，分配给这个程序的主四个页面，分配给这个程序的主存页面数为存页面数为3 3个。个。 在在FIFOFIFO和和LRULRU算法中，总是发生下次将算法中，总是发生下次将要使用的页面在本次被替换出去的情况，要使用的页面在本次被替换出去的情况，这就是这就是“颠簸颠簸”现象。现象。5.5 虚拟存储器1551555.5 虚拟存储器1561565.5 虚拟存储器2、堆栈型替换算法、堆栈型替换算法 定义：定义：对任意一个程序的页地址流作对任意一个程序的页地址流作两次主存页面数分配，分别分配两次主存页面数分配，分别分配 m 个主存个主存页面和页面和 n 个主存页面，并且有个主存页面，并且有 mn。如果如果在任何时刻在任何时刻 t，主存页面数集合主存页面数集合 Bt 都满足都满足关系：关系：Bt（m） Bt（n），），则这类算法则这类算法称为堆栈型替换算法。称为堆栈型替换算法。 1571575.5 虚拟存储器 堆栈型算法的基本特点是：堆栈型算法的基本特点是： 随着分配给程序的主存页面数增加，主随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降存的命中率也提高，至少不下降1581585.5 虚拟存储器159159$5提高主存命中率的方法提高主存命中率的方法u影响主存命中率的主要因素：影响主存命中率的主要因素： (1)(1)程序在执行过程中的页地址流分布程序在执行过程中的页地址流分布情况。情况。 (2) (2)所采用的页面替换算法。所采用的页面替换算法。 (3) (3)页面大小。页面大小。 (4) (4)主存储器的容量主存储器的容量 (5) (5)所采用的页面调度算法所采用的页面调度算法5.5 虚拟存储器160160以下，对后三个因素进行分析。以下，对后三个因素进行分析。1、页面大小与命中率的关系、页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。页面大小为某个值时，命中率达到最大。u页面大小与命中率关系的解释：页面大小与命中率关系的解释： 假设假设AtAt和和At+1At+1是相邻两次访问主存的逻是相邻两次访问主存的逻辑地址，辑地址，d dAtAtAt+1At+1。 如果如果Sp，随着随着Sp增大，增大，At和和At+1在同一页面的可能性增加，即随着在同一页面的可能性增加，即随着Sp的的增大而提高。增大而提高。5.5 虚拟存储器161161如果如果Sp，At和和At+1一定不在同一个页一定不在同一个页面内。随着面内。随着Sp增大，主存页面数减少，页面增大，主存页面数减少，页面替换更加频繁。随着替换更加频繁。随着Sp的增大而降低。的增大而降低。当当SpSp比较小的时候，前一种情况是主要的，比较小的时候，前一种情况是主要的，随着随着SpSp的增大而提高。当的增大而提高。当SpSp达到某一个最达到某一个最大值之后，后一种情况成为主要的，随着大值之后，后一种情况成为主要的，随着SpSp的增大而降低。的增大而降低。5.5 虚拟存储器162162当页面大小当页面大小增大时，造增大时，造成的浪费也成的浪费也要增加。要增加。当页面大小当页面大小减小时，页减小时，页表和页面表表和页面表在主存储器在主存储器中所占的比例将增加中所占的比例将增加5.5 虚拟存储器1631632、主存容量与命中率的关系、主存容量与命中率的关系 主存命中率主存命中率H随着分配给该程序的主存随着分配给该程序的主存容量容量S的增加而单调上升。的增加而单调上升。 在在S S比较小的时候，比较小的时候，H H提高得非常快。提高得非常快。随着随着S S的逐渐增加，的逐渐增加，H H提高的速度逐渐降低。提高的速度逐渐降低。当当S S增加到某一个值之后，增加到某一个值之后，H H几乎不再提高。几乎不再提高。5.5 虚拟存储器1641645.5 虚拟存储器1651653、页面调度方式与命中率的关系、页面调度方式与命中率的关系u 请求式请求式：当使用到的时候，再调入主：当使用到的时候，再调入主存存u 预取式预取式：在程序重新开始运行之前，：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。先调入到主存储器，然后才开始运行程序。5.5 虚拟存储器166166u预取式的主要优点预取式的主要优点： 可以避免在程序开始运行时，频繁发生页可以避免在程序开始运行时，频繁发生页面失效的情况。面失效的情况。u预取式的主要缺点：预取式的主要缺点： 如果调入的页面用不上，浪费了调入的时如果调入的页面用不上，浪费了调入的时间，占用了主存的资源。间，占用了主存的资源。5.5 虚拟存储器1671675.6 进程保护和虚拟存储器实例在多道程序中，计算机资源可以被多道同时运行的用户程序所共享。为使系统能够正常工作，应防止由于一个用户程序出错而破坏主存中其他用户的程序和数据，还要防止一个用户不合法地访问主存中不是分配给它的存储区域而造成对系统的破坏，即使这种访问不会引起破坏也是不允许的。操作系统和系统结构需要为存储系统的安全提供保护手段。5.6.1 进程保护保证进程的正确和安全运行既是系统设计者也是操作系统设计者的责任。保护的手段主要是：将主存区域分为几个区域，使得主存中可以同时存放多个不同进程的状态；并对每个存储区域进行保护，使一个进程的信息不被另一个进程所修改。存储系统的保护分为： (1)存储区域的保护，可用一对寄存器(即界限寄存器)来检查每一个地址，以确保地址在两个界限之间。 (2)访问保护，由系统软件设置用户进程访存的地址上下界，禁止了访问越界。5.6.1 进程保护(续1)在虚拟存储系统中，由于用户程序的访问空间映射到主存后将不是一个连续的地址空间，而将分布在主存中的各个页面，因此不适用以上述保护方式。在虚拟存储系统中，将采用更细微的方法： (1)映射表保护法，利用映射表的映射关系来限制用户程序的访问地址空间，用户程序不能访问映射表上找不到的主存页面，从而起到保护作用。 (2)键保护，由操作系统根据主存使用分配的情况，给主存中的每一页分配一个存储键，相当于保护锁。所有页的存储键是在主存相应的快速寄存器内，当用户访问这些页面时，需要一个访问键，相当于钥匙，来打开这把锁。5.6.1 进程保护(续2)(3)环保护，把系统程序和用户程序按其重要性及其访问权限进行分层。最内的几层是系统程序的分层，之外的几层是同一用户程序的分层，保护级别由里向外逐层降低。5.6.2 Alpha 21064存储管理Alpha处理机的系统结构采用段页相结合的方式，既提供了存储保护，又将页表减少到最小。Alpha根据64位地址的最高两位将地址空间分为3个段：seg0(最高位63位为0)，seg1(最高两位63和62位都为1)和kseg(最高位63位为1，次高位62位为0)。其中，seg0用于存储用户代码和堆，seg1用作用户栈，kseg是操作系统内核段。kseg是留给操作系统内核使用的，并且整个空间具有相同的保护权限，不需要存储管理。seg0和seg1是用户进程使用的，它们所映射到的各个页面具有不同的保护权限。5.6.2 Alpha 21064存储管理(续1)seg0段和seg1段的布局结构5.6.2Alpha21064存储管理(续2)为使页表大小更合理，Alpha采用三级分层页表结构，64位地址除了高位用于段选择的两位，其余的位则用于表示虚地址。虚地址中有3个域：V1、V2、V3，分别是：一级页表项偏移，二级页表项偏移、三级页表项偏移，这三个域分别用于查找这三级页表。另外，还有一个页内偏移量字段。5.6.2 Alpha 21064存储管理(续3)Alpha虚地址向物理地址的变化过程5.7Alpha21264存储层次结构(续1)Alpha 21264片上和片外高速缓存提供了特别低的数据延迟访问能力，允许很高的数据访问带宽。Alpha21264中设有两级cache：一级cache和二级cache。由于带宽的原因，三级cache在Alpha 21264中没有被采用。一级cache被分割成独立的caches来存储指令和数据，分别为I-cache(指令缓存) 和D-cache(数据缓存)，这两个caches都有64KB的容量；二级cache是一个外部cache，有1到16MB容量。5.7 Alpha 21264存储层次结构(续2)21264是乱序执行的，它允许执行指令的顺序和取指令的顺序不同，实际上做到了指令只要有可能就执行。每个周期最多可以取四个指令和执行6条指令，通过对这些指令进行处理来加速执行速度。Alpha 21264还采用推理执行方法，即使在不能立即知道哪一条指令将处于最后的执行路径的情况下，Alpha 21264仍然可以用推理的方法取指令和执行指令。例如，当21264 动态预测出分支方向并且沿着这条预测路径进行推理执行时，这种方法将特别有用。21264可以使用48位虚地址和44位物理地址，或者使用43位虚地址和41位物理地址。其中，物理地址空间被分为相等的两个部分，低地址部分用于内存地址，高地址部分用于I/O地址。5.7 Alpha 21264存储层次结构(续3)当Alpha启动时，芯片上的硬件从一个外部PROM加载指令cache，同时串行接口也会加载其他一些配置信息，这样初始化可以使指令cache省去有效位，因为这时cache中的指令都是有效的。预装载的指令在优先级结构库(PAL)模式下运行。PLA代码执行时，禁止异常发生，因此回避了TLB，所以由于不受存储管理的限制，取指令时不进行对存储访问的权限检查。一旦操作系统准备好执行一个用户程序，它将PC置为指向seg0段的相应地址。