1、当代计算机系统以存放器为中心当代计算机系统以存放器为中心 3.1 存放系统原理存放系统原理 3.2 虚拟存放器虚拟存放器 3.3 高速缓冲存放器高速缓冲存放器(Cache)3.4 三级存放系统三级存放系统第第3章章 存放系统存放系统10/2/1计算机系统结构 第三章 存放系统计算机系统结构原理第1页 3.1 3.1 存放系统原理存放系统原理3.1.1 存放系统定义存放系统定义3.1.2 存放系统层次结构存放系统层次结构3.1.3 存放系统频带平衡存放系统频带平衡3.1.4 并行访问存放器并行访问存放器 3.1.5 交叉访问存放器交叉访问存放器 3.1.6 无冲突访问存放器无冲突访问存放器海量无
2、偿资料，尽在10/2/2计算机系统结构 第三章 存放系统计算机系统结构原理第2页3.1.1 3.1.1 存放系统定义存放系统定义 在一台计算机中，通常有各种存放器在一台计算机中，通常有各种存放器种类：种类：主存放器、主存放器、Cache、通用存放器、缓冲、通用存放器、缓冲存放器、磁盘存放器、磁带存放器、光盘存存放器、磁盘存放器、磁带存放器、光盘存放器等放器等材料工艺：材料工艺：ECL、TTL、MOS、磁表面、激光，、磁表面、激光，SRAM，DRAM访问方式：访问方式：随机访问、直接译码、先进先出、随机访问、直接译码、先进先出、相联访问、相联访问、块传送、文件组块传送、文件组10/2/3计算机系
3、统结构 第三章 存放系统计算机系统结构原理第3页 存放器主要性能：存放器主要性能：速度、容量、价格速度、容量、价格 速度速度用存放器访问周期、读出时间、频带宽度等表示。容量容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示。价格价格用单位容量价格表示，比如：$C/bit。组成存放系统关键：组成存放系统关键：把速度、容量和价格不把速度、容量和价格不一样多个物理存放器组织成一个存放器，这个一样多个物理存放器组织成一个存放器，这个存放器速度最快，存放容量最大，单位容量价存放器速度最快，存放容量最大，单位容量价格最廉价。格最廉价。10/2/4计算机系统结构 第三章 存放系统计算机系统结构原理
4、第4页1.1.存放系统定义存放系统定义 两个或两个以上速度、容量和价格各不相同存两个或两个以上速度、容量和价格各不相同存放器用硬件、软件、或软件与硬件相结合方法连接放器用硬件、软件、或软件与硬件相结合方法连接起来成为一个存放系统。这个存放系统对应用程序起来成为一个存放系统。这个存放系统对应用程序员是透明，而且，从应用程序员看，它是一个存放员是透明，而且，从应用程序员看，它是一个存放器，这个存放器速度靠近速度最快那个存放器，存器，这个存放器速度靠近速度最快那个存放器，存放容量与容量最大那个存放器相等，单位容量价格放容量与容量最大那个存放器相等，单位容量价格靠近最廉价那个存放器。靠近最廉价那个存放
5、器。虚拟存放器系统：对应用程序员透明虚拟存放器系统：对应用程序员透明Cache存放系统：对系统程序员以上均透明存放系统：对系统程序员以上均透明10/2/5计算机系统结构 第三章 存放系统计算机系统结构原理第5页由多个存放器组成存放系统由多个存放器组成存放系统10/2/6计算机系统结构 第三章 存放系统计算机系统结构原理第6页 在一般计算机系统中，有两种存储系统：Cache存储系统：由Cache和主存储器构成 主要目：提高存储器速度10/2/7计算机系统结构 第三章 存放系统计算机系统结构原理第7页虚拟存储系统：由主存储器和硬盘构成 主要目：扩大存储器容量10/2/8计算机系统结构 第三章 存放
6、系统计算机系统结构原理第8页2.2.存放系统容量存放系统容量要求：要求：提供尽可能大地址空间提供尽可能大地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存放容量最大那个存放器进行编址，其它存放器只在内部编址或不编址 CacheCache存放系统存放系统另外设计一个容量很大逻辑地址空间，把相关存放器都映射这个地址空间中 虚拟存放系统虚拟存放系统10/2/9计算机系统结构 第三章 存放系统计算机系统结构原理第9页3.3.存放系统价格存放系统价格计算公式：当S2S1时，CC2 S2与S1不能相差太大10/2/10计算机系统结构 第三章 存放系统计算机系统结构原理第10页4.4.存放
7、系统速度存放系统速度表示方法：表示方法：访问周期、存取周期、存放周期、存取时间等命中率定义：命中率定义：在在M1存放器中访问到概率存放器中访问到概率 其中：N1是对M1存放器访问次数 N2是对M2存放器访问次数访问周期与命中率关系：访问周期与命中率关系：THT1(1H)T2 当命中率H1时，TT110/2/11计算机系统结构 第三章 存放系统计算机系统结构原理第11页存放系统访问效率：存放系统访问效率：访问效率主要与命中率和两级存放器速度之比访问效率主要与命中率和两级存放器速度之比相关相关例例3.13.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存放系统访问效率。解：解：当
8、当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.9610/2/12计算机系统结构 第三章 存放系统计算机系统结构原理第12页提升存放系统速度两条路径：提升存放系统速度两条路径：一是提升命中率一是提升命中率H H，二是两个存放器速度不要相差太大二是两个存放器速度不要相差太大其中：第二条有时做不到(如虚拟存放器)，这时，只能依靠提升命中率依靠提升命中率例例3.23.2：在虚拟存放系统中，两个存放器速度相差尤其悬殊，比如：T21
9、05 T。假如要使访问效率抵达e0.9，问需要有多高命中率？10/2/13计算机系统结构 第三章 存放系统计算机系统结构原理第13页解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得：H0.999998888877777 0.9999995.采取预取技术提升命中率采取预取技术提升命中率 方法：方法：不命中时，把不命中时，把M2存放器中相邻多个单存放器中相邻多个单元组成一个数据块取出来送入元组成一个数据块取出来送入M1存放器中。存放器中。10/2/14计算机系统结构 第三章 存放系统计算机系统结构原理第14页 计算公式：计算公式：其中：H是采取预取技术之后命中率 H
10、是原来命中率 n为数据块大小与数据重复使用次数乘积例例3.33.3：在一个Cache存放系统中，当Cache块大小为一个字时，命中率H0.8；假设数据重复利用率为5，T25T1。计算块大小为个字时，Cache存放系统命中率？并分别计算访问效率。10/2/15计算机系统结构 第三章 存放系统计算机系统结构原理第15页解：解：n4520，采取预取技术之后，命中率提升到：10/2/16计算机系统结构 第三章 存放系统计算机系统结构原理第16页例例3.43.4：在一个虚拟存放系统中，T2105 T，原来命中率只有0.8，假如访问磁盘存放器数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存放
11、器中重复利用率最少为多少？解：解：假设数据在主存放器中重复利用率为m，依据前面给出关系，有以下方程组：10/2/17计算机系统结构 第三章 存放系统计算机系统结构原理第17页解方程组：解方程组：由方程(1)得到：0.9H+90000-90000H=110/2/18计算机系统结构 第三章 存放系统计算机系统结构原理第18页 证实方法一：证实方法一：采取预取技术之后，不命中率不命中率(1-H)(1-H)降低倍：降低倍：10/2/19计算机系统结构 第三章 存放系统计算机系统结构原理第19页 证实方法二：证实方法二：在原有命中率计算公式中，把访问次数扩大到n倍。因为采取了预取技术，命中次数为：nN1
12、(n-1)N2,不命中次数仍为N2，所以新命中率为：10/2/20计算机系统结构 第三章 存放系统计算机系统结构原理第20页3.1.2 3.1.2 存放系统层次结构存放系统层次结构多个层次存放器多个层次存放器：第第1层：层：Register Files(存放器堆存放器堆)第第2层：层：Buffers(Lookahead)(先行缓冲站先行缓冲站)第第3层：层：Cache(高速缓冲存放器高速缓冲存放器)第第4层：层：Main Memory(主存放器主存放器)第第5层：层：Online Storage(联机存放器联机存放器)第第6层：层：Off-line Storage(脱机存放器脱机存放器)用用i
13、表示层数，表示层数，则有：工作周期工作周期TiTi+1，存放容量：存放容量：SiSi+1，单位价格：单位价格：CiCi+110/2/21计算机系统结构 第三章 存放系统计算机系统结构原理第21页计算机系统结构原理第22页各级存放器主要主要性能特征各级存放器主要主要性能特征 CPU CPU与主存放器速度差距越来越大与主存放器速度差距越来越大 当前相差当前相差两个数量级 今后今后CPUCPU与主存放器速度差距会更大与主存放器速度差距会更大10/2/23计算机系统结构 第三章 存放系统计算机系统结构原理第23页3.1.3 3.1.3 存放系统频带平衡存放系统频带平衡例例3.5：Pentium4指令执
14、行速度为8GIPS，CPU取指令8GW/s，访问数据16GW/s，各种输入输出设备访问存放器1GW/s，三项相加，要求存放器频带宽度不低于25GW/s。假如采取PC133内存，主存与CPU速度差188倍 假如采取PC266内存，主存与CPU速度差94倍处理存放器频带平衡方法处理存放器频带平衡方法 (1)多个存放器并行工作（本节下面介绍）多个存放器并行工作（本节下面介绍）(2)设置各种缓冲存放器（第五章介绍）设置各种缓冲存放器（第五章介绍）(3)采取存放系统（本章第二、第三节介绍）采取存放系统（本章第二、第三节介绍）10/2/24计算机系统结构 第三章 存放系统计算机系统结构原理第24页3.1.
15、4 3.1.4 并行访问存放器并行访问存放器方法：方法：把把m字字w位存放器改变成为位存放器改变成为m/n字字nw位位存放器存放器逻辑实现：逻辑实现：把地址码分成两个部分，一部分作把地址码分成两个部分，一部分作为存放器地址另一部分负责选择数据为存放器地址另一部分负责选择数据主要缺点：访问冲突大主要缺点：访问冲突大 (1)(1)取指令冲突取指令冲突 (2)(2)读操作数冲突读操作数冲突 (3)(3)写数据冲突写数据冲突 (4)(4)读写冲突读写冲突10/2/25计算机系统结构 第三章 存放系统计算机系统结构原理第25页 并行访问存放器结构框图并行访问存放器结构框图10/2/26计算机系统结构 第
16、三章 存放系统计算机系统结构原理第26页1.1.高位交叉访问存放器高位交叉访问存放器主要目标：主要目标：扩大存放器容量扩大存放器容量实现方法：实现方法：用地址码高位部分区分存放体号用地址码高位部分区分存放体号参数计算方法参数计算方法:m：每个存放体容量，n：总共存放体个数，j：存放体体内地址，j0，1，2，.，m-1 k：存放体体号，k0，1，2，.，n-1 存放器地址：Amkj 存放器体内地址：AjA mod m。存放器体号：Ak 3.1.5 3.1.5 交叉访问存放器交叉访问存放器10/2/27计算机系统结构 第三章 存放系统计算机系统结构原理第27页 高位交叉访问存放器结构框图高位交叉访
17、问存放器结构框图10/2/28计算机系统结构 第三章 存放系统计算机系统结构原理第28页例例3.6：用用4M字字4位位存存放放芯芯片片组组成成16M32位位主主存放器。共用存放芯片：存放器。共用存放芯片：用用最最高高2位位地地址址经经译译码码后后产产生生信信号号，控控制制各各组组存存放芯片放芯片CS。每每组组中中32根根数数据据线线分分别别对对应应直直接接相相连连，称称为为“线线或或”方式。方式。10/2/29计算机系统结构 第三章 存放系统计算机系统结构原理第29页10/2/30计算机系统结构 第三章 存放系统计算机系统结构原理第30页2.2.低位交叉访问存放器低位交叉访问存放器 主要目标：
18、主要目标：提升存放器访问速度提升存放器访问速度 实现方法：实现方法：用地址码低位部分区分存放体号用地址码低位部分区分存放体号 参数计算参数计算:m：每个存放体容量，n：总共存放体个数，j：存放体体内地址，j0，1，2，.，m-1 k：存放体体号，k0，1，2，.，n-1 存放器地址A计算公式为：Anjk 存放器体内地址：Aj 存放器体号：AkA mod n10/2/31计算机系统结构 第三章 存放系统计算机系统结构原理第31页 低位交叉访问存放器结构框图低位交叉访问存放器结构框图10/2/32计算机系统结构 第三章 存放系统计算机系统结构原理第32页 地址是编码方法：地址是编码方法：由由8 8
19、个存放体组成低位交叉编址方式个存放体组成低位交叉编址方式10/2/33计算机系统结构 第三章 存放系统计算机系统结构原理第33页 n n个存放体分时开启个存放体分时开启 一个采取流水线方式工作并行存放器 每存放体开启间隔为：t 其中：Tm为每个存放体访问周期,n为存放体个数。10/2/34计算机系统结构 第三章 存放系统计算机系统结构原理第34页访问冲突访问冲突 共有共有n n个存放体，每个存放周期只能取到个存放体，每个存放周期只能取到k k个个有效字有效字,其余其余n-kn-k个存放体有冲突。个存放体有冲突。假设p(k)是k概率密度函数，即p(1)是k1概率，p(2)是k2概率，,p(n)是
20、kn概率。k平均值为：N是每个存放周期能够访问到平都有效字个数。通常把 N N称为并行存放器加速比。称为并行存放器加速比。10/2/35计算机系统结构 第三章 存放系统计算机系统结构原理第35页定义转移概率为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-110/2/36计算机系统结
21、构 第三章 存放系统计算机系统结构原理第36页 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
22、)(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-110/2/37计算机系统结构 第三章 存放系统计算机系统结构原理第37页1-(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-1(1-g)(1-g)n-2n-2g g1 1(1-g)(1-g)(1-g)(1-g)2 2(1-g)(1-g)n-2n-2(1-g)
23、(1-g)n-1n-110/2/38计算机系统结构 第三章 存放系统计算机系统结构原理第38页10/2/39计算机系统结构 第三章 存放系统计算机系统结构原理第39页10/2/40计算机系统结构 第三章 存放系统计算机系统结构原理第40页例例3.7：Star-100巨型机存放系统采取并行和交叉相结合方式工作，有32个存放体低位交叉，每次并行读写512位，存放周期为1280ns，处理机字长32位，计算它频带宽度Bm和峰值速度T。解：解：因为：n32，w512，Tm1280ns，Bmn w/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s T2.5ns与与TmTm相比，
24、峰值速度提升相比，峰值速度提升512512倍倍实际速度提升要远远小于这个数字实际速度提升要远远小于这个数字10/2/41计算机系统结构 第三章 存放系统计算机系统结构原理第41页 3.1.6 3.1.6 无冲突访问存放器无冲突访问存放器1.1.一维数组一维数组(向量向量)无冲突访问存放器无冲突访问存放器 按连续地址访问，没有冲突，位移量为2变址访问，速度降低一倍，10/2/42计算机系统结构 第三章 存放系统计算机系统结构原理第42页 详细方法：详细方法：存放体个数取质数，且存放体个数取质数，且nn向量长度。向量长度。原因：原因：变址位移量必定与存放体个数互质 比如：比如：Burroughs企
25、业巨型科学计算机BSP 存放体个数为17 向量长度16我国研制银河巨型向量机 存放体个数为37 向量长度3210/2/43计算机系统结构 第三章 存放系统计算机系统结构原理第43页2.2.二维数组无冲突访问存放器二维数组无冲突访问存放器要求：要求：一个一个nn二维数组，按行、列、对角线二维数组，按行、列、对角线和反对角线访问，而且在不一样变址位移量和反对角线访问，而且在不一样变址位移量情况下，都能实现无冲突访问。情况下，都能实现无冲突访问。次序存放：次序存放：按行、对角线访问没有冲突，但按列访问每次冲突10/2/44计算机系统结构 第三章 存放系统计算机系统结构原理第44页 错位存放：错位存放
26、：按行、按列访问无冲突，但按对角线访问有冲突10/2/45计算机系统结构 第三章 存放系统计算机系统结构原理第45页nn二维数组无冲突访问存放方案二维数组无冲突访问存放方案 (P Budnik 和和 D J Kuck提出提出)：并行存放体个数并行存放体个数mn，而且取质数，同时还，而且取质数，同时还要在行、列方向上错开一定距离存放数组元要在行、列方向上错开一定距离存放数组元素。素。设同一列相邻元素在并行存放器中错开设同一列相邻元素在并行存放器中错开d1个个存放体存放，同一行相邻元素在并行存放器存放体存放，同一行相邻元素在并行存放器中错开中错开d2个存放体存放。当个存放体存放。当m22p1（p为
27、为任意自然数）时，能够同时实现按行、按列、任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问充要条件按对角线和按反对角线无冲突访问充要条件是：是：d12P，d21。10/2/46计算机系统结构 第三章 存放系统计算机系统结构原理第46页比如：比如：44二维数组，取并行存放体个数二维数组，取并行存放体个数m5，由关系式，由关系式m22P1，解得到，解得到p1，计算，计算得到：得到：d1212 d2110/2/47计算机系统结构 第三章 存放系统计算机系统结构原理第47页 nn数组中任意一个元素数组中任意一个元素aij在无冲突并行存放器在无冲突并行存放器中体号地址和体内地址计算
28、公式：中体号地址和体内地址计算公式：体号地址：体号地址：(2P ijk)MOD m 体内地址：体内地址：i 其中：0in1，0jn1，k是数组第一个元素a00所在体号地址，m是并行存放体个数，要求mn且为质数，p是满足m22P1关系任意自然数。主要缺点：主要缺点：浪费存放单元 对于对于nn数组数组,有有(m-n)m个存放单元浪费个存放单元浪费 主要优点：主要优点：实现简单 列元素次序存放，行元素按地址取模次序存放列元素次序存放，行元素按地址取模次序存放48计算机系统结构原理第48页3.3.二维数组无冲突访问存放器二维数组无冲突访问存放器(之二之二)规则：规则：对于任意一个对于任意一个nn数组，
29、假如能够找到满数组，假如能够找到满足足n22P关系任意自然数关系任意自然数p，则这个二维数组，则这个二维数组就能够使用就能够使用n个并行存放体个并行存放体实现按行、列、对实现按行、列、对角线和反对角线无冲突访问。角线和反对角线无冲突访问。4444数组用数组用4 4个存放体无访问冲突存放方案个存放体无访问冲突存放方案10/2/49计算机系统结构 第三章 存放系统计算机系统结构原理第49页实现方法：实现方法：假设假设aij是是4444数组中任意一个元素，数组中任意一个元素，下标下标i和和j都能够用两位二进制表示。假设都能够用两位二进制表示。假设i和和j高位和低高位和低位分别为位分别为iH、iL、j
30、H和和jL，则则aij在无冲突并行存在无冲突并行存放器中体号地址和体内地址以下：放器中体号地址和体内地址以下：体号地址：体号地址：2(iL jH)(iH iL jL)体内地址：体内地址：j 其中：其中：0i3，0j3主要优点：主要优点：没有浪费存放单元没有浪费存放单元，主要缺点：主要缺点：在执行并行读和写操作时需要借助比在执行并行读和写操作时需要借助比较复杂对准网络较复杂对准网络。10/2/50计算机系统结构 第三章 存放系统计算机系统结构原理第50页3.2.1 虚拟存放器工作原理虚拟存放器工作原理3.2.2 地址映象和变换方法地址映象和变换方法3.2.3 加紧内部地址变换方法加紧内部地址变换
31、方法3.2.4 页面替换算法及其实现页面替换算法及其实现3.2.5 提升主存命中率方法提升主存命中率方法3.2 3.2 虚拟存放器虚拟存放器10/2/51计算机系统结构 第三章 存放系统计算机系统结构原理第51页3.2.1 3.2.1 虚拟存放器工作原理虚拟存放器工作原理也称为虚拟存放系统、虚拟存放体系等也称为虚拟存放系统、虚拟存放体系等其概念由英国曼彻斯特大学其概念由英国曼彻斯特大学Kilbrn等人于等人于1961年提出年提出到到70年代广泛应用于大中型计算机系统年代广泛应用于大中型计算机系统当前，许多微型机也使用虚拟存放器当前，许多微型机也使用虚拟存放器把主存放器、磁盘存放器和虚拟存放器都
32、划分成固定大小页 主存放器页称为实页主存放器页称为实页 虚拟存放器中页称为虚页虚拟存放器中页称为虚页10/2/52计算机系统结构 第三章 存放系统计算机系统结构原理第52页内部地址变换：内部地址变换：多用户虚拟地址多用户虚拟地址Av变换成主存实地址变换成主存实地址A A 多用户虚拟地址中页内偏移多用户虚拟地址中页内偏移D D直接作为主存直接作为主存实地址中页内偏移实地址中页内偏移d d，主存实页号主存实页号p p与它页内偏移与它页内偏移d d直接拼接起来就直接拼接起来就得到主存实地址得到主存实地址A A。10/2/53计算机系统结构 第三章 存放系统计算机系统结构原理第53页计算机系统结构原理
33、第54页3.2.2 3.2.2 地址映象与变换地址映象与变换三种地址空间：三种地址空间：虚拟地址空间 主存放器地址空间 辅存地址空间地址映象：地址映象：把虚拟地址空间映象到主存地址空间把虚拟地址空间映象到主存地址空间地址变换地址变换：在程序运行时，把虚地址变换成主存实地址在程序运行时，把虚地址变换成主存实地址三种虚拟存放器：三种虚拟存放器：页式虚拟存放器页式虚拟存放器 段式虚拟存放器段式虚拟存放器 段页式虚拟存放器段页式虚拟存放器10/2/55计算机系统结构 第三章 存放系统计算机系统结构原理第55页1.1.段式虚拟存放器段式虚拟存放器地址映象方法：地址映象方法：每个程序段都从每个程序段都从0
34、 0地址开始编址，地址开始编址，长度可长可短，能够在程序执行过程中动态长度可长可短，能够在程序执行过程中动态改变程序段长度。改变程序段长度。计算机系统结构原理第56页地址变换方法：地址变换方法：由用户号找到基址存放器，读由用户号找到基址存放器，读出段表起始地址，与虚地址中段号相加得到出段表起始地址，与虚地址中段号相加得到段表地址，把段表中起始地址与段内偏移段表地址，把段表中起始地址与段内偏移D相加就能得到主存实地址。相加就能得到主存实地址。计算机系统结构原理第57页 主要优点：主要优点：(1)(1)程序模块化性能好。程序模块化性能好。(2)(2)便于程序和数据共享。便于程序和数据共享。(3)(
35、3)程序动态链接和调度比较轻易。程序动态链接和调度比较轻易。(4)(4)便于实现信息保护。便于实现信息保护。主要缺点：主要缺点：(1)(1)地址变换所花费时间长，两次加法地址变换所花费时间长，两次加法 (2)(2)主存放器利用率往往比较低。主存放器利用率往往比较低。(3)(3)对辅存（磁盘存放器）管理比较困难。对辅存（磁盘存放器）管理比较困难。10/2/58计算机系统结构 第三章 存放系统计算机系统结构原理第58页2.2.页式虚拟存放器页式虚拟存放器 地址映象方法：地址映象方法：计算机系统结构原理第59页 地址变换方法：地址变换方法：10/2/60计算机系统结构 第三章 存放系统计算机系统结构
36、原理第60页 主要优点：主要优点：(1)主存放器利用率比较高主存放器利用率比较高 (2)页表相对比较简单页表相对比较简单 (3)地址变换速度比较快地址变换速度比较快 (4)对磁盘管理比较轻易对磁盘管理比较轻易 主要缺点：主要缺点：(1)程序模块化性能不好程序模块化性能不好 (2)页表很长，需要占用很大存放空间页表很长，需要占用很大存放空间 比如：比如：虚拟存放空间4GB，页大小1KB，则页表容量为4M字，16MB。10/2/61计算机系统结构 第三章 存放系统计算机系统结构原理第61页3.3.段页式虚拟存放器段页式虚拟存放器 用户按段写程序用户按段写程序,每段分成几个固定大小页每段分成几个固定
37、大小页 地址映象方法：地址映象方法：每个程序段在段表中占一行，在段表中给出页表长度和页表起始地址，页表中给出每一页在主存放器中实页号。计算机系统结构原理第62页 地址变换方法：地址变换方法：先查段表，得到页表起始地址和页表长度，再查页表找到要访问主存实页号，把实页号p与页内偏移d拼接得到主存实地址。计算机系统结构原理第63页4.4.外部地址变换外部地址变换 每个程序有一张外页表，每一页或每个程序段，在外页表中都有对应一个存放字。计算机系统结构原理第64页3.2.3 3.2.3 加紧内部地址变换方法加紧内部地址变换方法造成虚拟存放器速度降低主要原因：造成虚拟存放器速度降低主要原因：(1)要访问主
38、存放器必须先查段表或页表，要访问主存放器必须先查段表或页表，(2)可能需要多级页表。可能需要多级页表。页表级数计算公式：页表级数计算公式：其中：Nv为虚拟存放空间大小，Np为页面大小，Nd为一个页表存放字大小10/2/65计算机系统结构 第三章 存放系统计算机系统结构原理第65页比如：比如：虚拟存放空间大小Nv4GB，页大小Np1KB，每个页表存放字占用4个字节。计算得到页表级数：通常仅把1级页表和2、3级页表中一小部分驻留在主存中10/2/66计算机系统结构 第三章 存放系统计算机系统结构原理第66页1.1.目录表目录表 基本思想：基本思想：用一个小容量高速存放器存放页表用一个小容量高速存放
39、器存放页表计算机系统结构原理第67页地址变换过程：地址变换过程：把多用户虚地址中把多用户虚地址中U与与P拼接，相联访问目录拼接，相联访问目录表。读出主存实页号表。读出主存实页号p，把，把p与多用户虚地址与多用户虚地址中中D拼接得到主存实地址。假如相联访问失败，拼接得到主存实地址。假如相联访问失败，发出页面失效请求。发出页面失效请求。主要优点：主要优点：与页表放在主存中相比，查表速度快。与页表放在主存中相比，查表速度快。主要缺点：主要缺点：可扩展性比较差可扩展性比较差,主存放器容量大时，目录表造价高，速度低。主存放器容量大时，目录表造价高，速度低。10/2/68计算机系统结构 第三章 存放系统计
40、算机系统结构原理第68页2.2.快慢表快慢表计算机系统结构原理第69页 快表：快表：TLB(Translation Lookaside Buffer)：小容量(几几十个字)，高速硬件实现，采取相联方式访问。慢表：慢表：当快表中查不到时，从主存慢表中查找；慢表按地址访问；用软件实现。快表与慢表也组成一个两级存放系统。快表与慢表也组成一个两级存放系统。主要存在问题：主要存在问题：相联访问实现困难，速度低10/2/70计算机系统结构 第三章 存放系统计算机系统结构原理第70页3.散列函数 目：把相联访问变成按地址访问 散列(Hashing)函数：AhH(Pv)计算机系统结构原理第71页 采取散列变换
41、实现快表按地址访问采取散列变换实现快表按地址访问 防止散列冲突：防止散列冲突：采取相等比较器采取相等比较器 地址变换：地址变换：相等比较与访问存放器同时进行计算机系统结构原理第72页4.4.虚拟存放器举例虚拟存放器举例 例例3.83.8：IMB370/168计算机虚拟存放器中快表结构及地址变换过程。虚拟地址长36位，页面大小为4KB，每个用户最多占用4K 个页面，最多允许16G个用户，但同时上机用户数普通不超出6个。采取了两项新办法：采取了两项新办法：(1)(1)采取两个相等比较器，以降低散列冲突。采取两个相等比较器，以降低散列冲突。(2)(2)用一个相联存放器组，把用一个相联存放器组，把24
42、24位用多户号位用多户号U U压缩成压缩成3 3位，以缩短快表长度。位，以缩短快表长度。10/2/73计算机系统结构 第三章 存放系统计算机系统结构原理第73页计算机系统结构原理第74页3.2.4 3.2.4 页面替换算法及其实现页面替换算法及其实现1.1.页面替换发生时间：页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到当发生页面失效时，要从磁盘中调入一页到主存。假如主存放器全部页面都已经被占用，主存。假如主存放器全部页面都已经被占用，必须从主存放器中淘汰掉一个不常使用页面，必须从主存放器中淘汰掉一个不常使用页面，方便腾出主存空间来存放新调入页面。方便腾出主存空间来存放新调入页面。2
43、.2.评价页面替换算法好坏标准：评价页面替换算法好坏标准：一是命中率要高，一是命中率要高，二是算法要轻易实现。二是算法要轻易实现。10/2/75计算机系统结构 第三章 存放系统计算机系统结构原理第75页3.3.页面替换算法使用场所：页面替换算法使用场所：(1)虚拟存放器中，主存页面替换，普通用软件实现。(2)Cache中块替换，普通用硬件实现。(3)虚拟存放器快慢表中，快表存放字替换，用硬件实现。(4)虚拟存放器中，用户基地址存放器替换，用硬件实现。(5)在有些虚拟存放器中，目录表替换。10/2/76计算机系统结构 第三章 存放系统计算机系统结构原理第76页4.4.主要页面替换算法主要页面替换
44、算法(1)随机算法随机算法（RAND random algorithm）算法简单，轻易实现。没有利用历史信息，没有反应程序局部性 命中率低。(2)先进先出算法先进先出算法 (FIFO first-in first-out algorithm)轻易实现，利用了历史信息，没有反应局部性。最先调入页面，很可能也是要使用页面10/2/77计算机系统结构 第三章 存放系统计算机系统结构原理第77页(3)近期最少使用算法近期最少使用算法(LFU least frequently used algorithm)：既充分利用了历史信息，又反应了程序局部性实现起来非常困难。(4)最久没有使用算法最久没有使用算法
45、(LRU least recently used algorithm)：把把LFU算法中算法中“多多”与与“少少”简化成简化成“有有”与与“无无”，实现比较轻易，实现比较轻易(5)最优替换算法最优替换算法（OPT optimal replacement algorithm）：是一个理想算法，仅用作评价其它页面替换算法好坏标准。在虚拟存放器中，实际上可能采取只有在虚拟存放器中，实际上可能采取只有FIFO和和LRU两种算法。两种算法。10/2/78计算机系统结构 第三章 存放系统计算机系统结构原理第78页例例3.93.9：一个程序共有5个页面组成，在程序执行过程中，页面地址流以下：P1P1，P2P
46、2，P1P1，P5P5，P4P4，P1P1，P3P3，P4P4，P2P2，P4P4 假设分配给这个程序主存只有3个页面。(1)给出用FIFO、LRU和OPT三种页面替换算法对这3个主存页面调度情况表，并统计页面命中次数。(2)计算这LRU页面替换算法页面命中率。(3)假设每个数据平均被访问30次，为了使LRU算法失效率小于10-5，计算页面大小最少应该为多少？10/2/79计算机系统结构 第三章 存放系统计算机系统结构原理第79页解：解：(1)FIFO、LRU和OPT页面命中次数分别为2次、4次和5次(2)LRU页面替换算法页面命中率为：Hp4/100.4(3)解得解得 P P 字字 页面大小
47、应该为页面大小应该为2K2K字。字。10/2/80计算机系统结构 第三章 存放系统计算机系统结构原理第80页10/2/81计算机系统结构 第三章 存放系统计算机系统结构原理第81页例例3.10：一个循环程序，依次使用P1，P2，P3，P4页面，分配给它主存页面数只有2个。在 FIFO和LRU算法中，发生“颠簸颠簸”现象。计算机系统结构原理第82页5.5.堆栈型替换算法堆栈型替换算法 定义：定义：对任意一个程序页地址流作两次主存对任意一个程序页地址流作两次主存页面数分配，分别分配页面数分配，分别分配 m 个主存页面和个主存页面和 n 个主个主存页面，而且有存页面，而且有 mn。假如在任何时刻。假
48、如在任何时刻 t，主，主存页面数集合存页面数集合 Bt 都满足关系：都满足关系：Bt（m）Bt（n），），则这类算法称为堆栈型替换算法。则这类算法称为堆栈型替换算法。堆栈型算法基本特点是：堆栈型算法基本特点是：伴随分配给程序主存页面数增加，主存命中伴随分配给程序主存页面数增加，主存命中率也提升，最少不下降。率也提升，最少不下降。10/2/83计算机系统结构 第三章 存放系统计算机系统结构原理第83页10/2/84计算机系统结构 第三章 存放系统计算机系统结构原理第84页3.2.5 3.2.5 提升主存命中率方法提升主存命中率方法影响主存命中率主要原因：影响主存命中率主要原因：(1)程序在执行过
49、程中页地址流分布情况。(2)(2)所采取页面替换算法。所采取页面替换算法。(3)(3)页面大小。页面大小。(4)(4)主存放器容量主存放器容量(5)(5)所采取页面调度算法所采取页面调度算法 以下，对后三个原因进行分析。以下，对后三个原因进行分析。1.1.页面大小与命中率关系页面大小与命中率关系 页面大小为某个值时，命中率到达最大。页面大小为某个值时，命中率到达最大。10/2/85计算机系统结构 第三章 存放系统计算机系统结构原理第85页页面大小与命中率关系解释：页面大小与命中率关系解释：假设At和At+1是相邻两次访问主存逻辑地址，dAtAt+1。假如假如SpSp，伴随，伴随SpSp增大，增
50、大，A At 和和 A At+1在同一页在同一页面可能性增加，即伴随面可能性增加，即伴随SpSp增大而提升。增大而提升。假如假如SpSp，A At和和A At+1一定不在同一个页面内。一定不在同一个页面内。伴随伴随SpSp增大，主存页面数降低，页面替换愈增大，主存页面数降低，页面替换愈加频繁。伴随加频繁。伴随SpSp增大而降低。增大而降低。10/2/86计算机系统结构 第三章 存放系统计算机系统结构原理第86页当Sp比较小时候，前一个情况是主要，伴随Sp增大而提升。当Sp到达某一个最大值之后，后一个情况成为主要，伴随Sp增大而降低。当页面增大时，造 成浪费也要增加当页面减小时，页 表和页面表在
