计算机系统结构(ch-3)

1、1 3.1 3.1 存储系统原理存储系统原理 3.2 3.2 交叉访问存储器交叉访问存储器 3.3 3.3 虚拟存储器虚拟存储器 3.4 Cache3.4 Cache存储器存储器 2 3.1.1 3.1.1 存储系统的基本概念存储系统的基本概念 v存储器的主要性能指标：存储器的主要性能指标： 容量容量: :用字节用字节B B、千字节、千字节KBKB、兆字节、兆字节MBMB和千兆字节和千兆字节GBGB 等单位表示。等单位表示。 S Sm m=WLm=WLm 速度速度: :用访问时间用访问时间T Ta a、存储周期、存储周期T Tm m、频带宽度、频带宽度B Bm m等表等表 示。示。 B Bm

2、m=W/T=W/Tm m（单体）（单体） B Bm m=m=mW/TW/Tm m（m m体）体） 价格价格: :用总价格和每位价格表示。用总价格和每位价格表示。c=C/Sc=C/SM M v无能同时满足容量、速度、价格三方面要求的存贮器无能同时满足容量、速度、价格三方面要求的存贮器 件，因此系统中必须使用多种不同工艺的存贮器组成存件，因此系统中必须使用多种不同工艺的存贮器组成存 储器系统。储器系统。 3 v在一台计算机中，通常有多种存储器在一台计算机中，通常有多种存储器 种类：种类：主存储器、主存储器、CacheCache、通用寄存器、先行缓冲存储器、通用寄存器、先行缓冲存储器、 磁盘存储器、

3、磁带存储器、光盘存储器等磁盘存储器、磁带存储器、光盘存储器等 材料工艺：材料工艺：ECLECL、TTLTTL、MOSMOS、磁表面、激光、磁表面、激光、SRAMSRAM、DRAMDRAM 访问方式：访问方式：直接译码、先进先出、随机访问、相联访问直接译码、先进先出、随机访问、相联访问 v提高速度的提高速度的两种方法两种方法： 组成上采用并行和重叠技术，构成组成上采用并行和重叠技术，构成并行主存系统并行主存系统 系统结构上发展系统结构上发展存储体系存储体系，如，如Cache-Cache-主存主存- -辅存辅存 v存储体系（系统、层次）存储体系（系统、层次） 由多种不同的存储器件构成，在由多种不同

4、的存储器件构成，在OSOS和辅助硬件管理下成为完和辅助硬件管理下成为完 整的整体，以满足容量、速度、价格的要求。整的整体，以满足容量、速度、价格的要求。对应用程序员对应用程序员 透明透明。 4 vRISC的先进技术的先进技术 流水线技术流水线技术 延迟加载指令（延迟加载指令（load） 延迟转移技术延迟转移技术 优化编译技术优化编译技术 数据相关数据相关 延迟加载指令（延迟加载指令（load） 重叠寄存器窗口技术重叠寄存器窗口技术 v存储系统的基本概念存储系统的基本概念 由多种不同存储器件构成，在由多种不同存储器件构成，在OSOS和辅助硬件管理下成为完整和辅助硬件管理下成为完整 的整体，以满足

5、容量、速度、价格的要求。的整体，以满足容量、速度、价格的要求。 依据程序访问的局部性原理依据程序访问的局部性原理 5 T Tminmin（T T1 1, T, T2 2 T Tn n）= T= T1 1, , 用存储周期表示用存储周期表示 S Smaxmax（S S1 1, S, S2 2 S Sn n）= S= Sn n, , 用用MBMB或或GBGB表示表示 C Cminmin（C C1 1, C, C2 2 C Cn n）= C= Cn n, , 用每位的价格表示用每位的价格表示 v依据：依据：程序访问的局部性原理程序访问的局部性原理 M Mi i一般只存放一般只存放M Mi+1 i+1

6、中近期使用过的块或页（时间局部性）； 中近期使用过的块或页（时间局部性）； 取取M Mi+1 i+1字到 字到M Mi i时把所在块或页整个取出来（空间局部性）。时把所在块或页整个取出来（空间局部性）。 CPUCPU M1 (T1, S1, C1) M2 (T2, S2, C2) Mn (Tn, Sn, Cn) (T,S,C)(T,S,C) 6 从从应用程序员应用程序员的角的角 度看，速度接近主存储度看，速度接近主存储 器，容量是虚拟空间的器，容量是虚拟空间的 容量，每位价格接近磁容量，每位价格接近磁 盘存储器价格。由盘存储器价格。由OSOS和和 辅助硬件管理，仅对应辅助硬件管理，仅对应 用程

7、序员透明。用程序员透明。 从从系统程序员系统程序员的角的角 度看，速度接近度看，速度接近CacheCache， 容量接近主存容量接近主存, ,每位价每位价 格接近主存。由硬件格接近主存。由硬件 管理，对系统和应用管理，对系统和应用 程序员均透明。程序员均透明。 特点特点 扩大容量扩大容量提高速度提高速度主要目的主要目的 主存储器主存储器- -磁盘存储器磁盘存储器Cache-Cache-主存储器主存储器组成组成 虚拟存储系统虚拟存储系统CacheCache存储系统存储系统存储系统存储系统 7 （1）容量）容量 要求：要求： 存储系统的容量等于存储系统的容量等于M2存储器的容量，存储器的容量， 提

8、供尽可能大、能随机访问的地址空间提供尽可能大、能随机访问的地址空间 （2）每位平均价格）每位平均价格 计算公式：计算公式： S2S1时时, CC2 但但S2与与S1不能相差太大，否则不能相差太大，否则命中率命中率会很低会很低 C C SCS SS 1122 12 M1 (S1, C1 , T1) M2 (S2, C2 , T2) CPUCPU 8 （3 3）速度）速度 表示方法：等效访问时间表示方法：等效访问时间T Ta a（又称访问周期）（又称访问周期） 命中率命中率定义定义：在在M M1 1存储器中访问到的概率存储器中访问到的概率 N N1 1: : 在在M M1 1访问到的次数访问到的次

9、数 N N2 2: : 在在M M2 2访问到的次数访问到的次数 等效访问时间等效访问时间与命中率的关系：与命中率的关系： T Ta aHTHT1 1(1(1H)TH)T2 2 当命中率当命中率H1H1时，时，T Ta aTT1 1 H N NN 1 12 9 （4 4）访问效率访问效率： 2 1 11 12 1 ( , ) (1)(1) T a T TT ef H r TH TH THH 上式表明：上式表明：e e主要与主要与命中率命中率H H和构成存储系统的两级存储和构成存储系统的两级存储 器的器的速度比速度比r r（r=Tr=T2 2/T/T1 1）有关（）有关（P41 P41 图图3.

10、33.3） v注意：注意： e e越高说明存储系统的速度越接近较快的那个存储器的速越高说明存储系统的速度越接近较快的那个存储器的速 度。度。 e1e1 1 图图3.33.3 11 v提高存储系统速度（访问效率）的提高存储系统速度（访问效率）的途径途径： 提高命中率提高命中率H H 减小减小r r（即两级存储器的速度不要相差太大）（即两级存储器的速度不要相差太大） v其中第二条有时做不到其中第二条有时做不到( (如虚拟存储器中如虚拟存储器中r=10r=105 5) )，主主 要依靠提高命中率。要依靠提高命中率。 ),( )1 ( 1 )1 ( 1 2 21 11 rHf HHTHTH T Ta

11、T e T T 12 v复杂的存储系统（一）复杂的存储系统（一） 11122 12n-1n (1) (1)(1)(1) aaa a THTHHT HHHT M1 (T1, S1, C1) M2 (T2, S2, C2) Mn (Tn, Sn, Cn) (T,S,C)(T,S,C) CPUCPU 13 v复杂的存储系统（二）复杂的存储系统（二） CPUCPU I-CacheI-Cache D-CacheD-Cache 主存储器主存储器 vTa= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm) fi：访存取指概率：访存取指概率 Hi ：I-Cache命中率

12、命中率 Hd： D-Cache命中率命中率 Tc： Cache访问时间访问时间 Tm： 主存访问时间主存访问时间 14 例：例：假设假设T T2 2=5T=5T1 1，在命中率，在命中率H H为为0.90.9和和0.990.99两种情况下，两种情况下， 分别计算存储系统的访问效率。分别计算存储系统的访问效率。 解：解： 由由T T2 2=5T=5T1 1，可得，可得r=5r=5 当当H=0.9H=0.9时时, e, e1 1=1/(0.9+5(1-0.9)=0.72=1/(0.9+5(1-0.9)=0.72 当当H=0.99H=0.99时时, e, e2 2=1/(0.99+5(1-0.99)

13、=0.96=1/(0.99+5(1-0.99)=0.96 v结论：提高命中率确实可以大幅提高访问效率结论：提高命中率确实可以大幅提高访问效率 15 v某机由某机由Cache与主存组成二级存储系统，与主存组成二级存储系统， Cache的存取周期的存取周期 tc=50ns，主存的存取周期，主存的存取周期tm=400ns。Cache命中率为命中率为0.96。 (1)系统等效访问时间系统等效访问时间Ta为多少？为多少？ (2)如果将如果将Cache分为分为I-Cache和和D-Cache，使等效访问时，使等效访问时 间间Ta减小减小10%。在所有的访问操作中有。在所有的访问操作中有20%是访问是访问I

14、-Cache ， 而访问而访问I-Cache的命中率仍为的命中率仍为0.96，问，问D-Cache的访问命中率的访问命中率 应是多少？应是多少？ 16 v解：解：(1)(1)系统等效的存取周期为：系统等效的存取周期为： T Ta a =HT =HTc c+(1-H)T+(1-H)Tm m = 0.96 = 0.9650 + (1-0.96)50 + (1-0.96)400 = 64ns400 = 64ns v（2 2）设改进后的）设改进后的D-CacheD-Cache的命中率为的命中率为H Hd d，则，则 T Ta a= f= fi i(H(Hi iT Tc c+(1- H+(1- Hi i

15、)T)Tm m)+(1- f)+(1- fi i)( H)( Hd dT Tc c+(1- H+(1- Hd d) T) Tm m) ) 6464(1-10%)=0.2(0.96(1-10%)=0.2(0.9650+(1-0.96)50+(1-0.96)400)+(1-0.2)(H400)+(1-0.2)(Hd d50+(1-H50+(1-Hd d) )400)400) 280H 280Hd d=275.2=275.2 H Hd d0.9830.983 17 v例：在虚拟存储系统中，两级存储器的速度相差特例：在虚拟存储系统中，两级存储器的速度相差特 别悬殊，别悬殊，T T2 2=10=105

16、5T T 。如果要使访问效率 。如果要使访问效率e=0.9e=0.9，问需要，问需要 有多高的命中率？有多高的命中率？ H=0.999998888877777.0.999999H=0.999998888877777.0.999999 5 10)1 ( 1 9 . 0 HH 解：解： v结论：结论：要使存储体系有高的访问效率，两级存储器的速度差要使存储体系有高的访问效率，两级存储器的速度差 不能太大（即减少公式中的不能太大（即减少公式中的r r），否则要使），否则要使H H特别高才行。特别高才行。 18 vRISC的先进技术的先进技术 流水线技术流水线技术 延迟加载指令（延迟加载指令（load）

17、 延迟转移技术延迟转移技术 优化编译技术优化编译技术 数据相关数据相关 延迟加载指令（延迟加载指令（load） 重叠寄存器窗口技术重叠寄存器窗口技术 v存储系统的基本概念存储系统的基本概念 由多种不同存储器件构成，在由多种不同存储器件构成，在OSOS和辅助硬件管理下成为完整和辅助硬件管理下成为完整 的整体，以满足容量、速度、价格的要求。的整体，以满足容量、速度、价格的要求。 依据程序访问的局部性原理依据程序访问的局部性原理 19 v存储系统的性能参数存储系统的性能参数( (两级两级) ) 等效访问时间等效访问时间 T Ta aHTHT1 1(1(1H)TH)T2 2 访问效率访问效率 v复杂的

18、存储系统复杂的存储系统 Ta= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm) ),( )1 ( 1 )1 ( 1 2 21 11 rHf HHTHTH T Ta T e T T CPUCPU I-CacheI-Cache D-CacheD-Cache 主存储器主存储器 20 v预取技术：预取技术：不命中时，把不命中时，把M M2 2存储器中相邻几个单元组成的一个存储器中相邻几个单元组成的一个 数据块都取出来送入数据块都取出来送入M M1 1存储器中。存储器中。( (依据程序访问的局部性原理依据程序访问的局部性原理） v计算公式计算公式： v其中：其中

19、： H H是采用预取技术后的命中率；是采用预取技术后的命中率； H H是原来的命中率是原来的命中率; ; n n为为数据块大小数据块大小与与数据重复使用次数数据重复使用次数的乘积。的乘积。 n nH n H H 11 1 例：例：某某Cache系统中，块大小为系统中，块大小为1个字时，命中率个字时，命中率H=0.8；假设数；假设数 据重复利用率为据重复利用率为5，计算块大小为个字时，计算块大小为个字时，Cache的命中率是多的命中率是多 少？假设少？假设T2=5T1，分别计算普通方式和采用预取方式的访问效率。，分别计算普通方式和采用预取方式的访问效率。 99. 0 20 1208 . 01 n

20、 nH H 0.550.8)-5(1(0.8/ 1e1 0.960.99)5(1(0.99/1e2 解：解： 采用预取技术后采用预取技术后, n=45=20，命中率提高到：，命中率提高到： Cache块为块为1个字大时个字大时, H=0.8, 访问效率为访问效率为: Cache块为块为4个字大时个字大时, H=0.99, 访问效率为访问效率为: 结论结论：预取技术：预取技术 确实能大幅度提确实能大幅度提 高命中率高命中率 22 例：例：某虚拟存储系统中，某虚拟存储系统中，T2105 T ，原来的命中率只有 ，原来的命中率只有0.8， 如果访问磁盘存储器的数据块大小为如果访问磁盘存储器的数据块大

21、小为4K字，并要求访问效率不字，并要求访问效率不 低于低于0.9，计算数据在主存储器中的重复利用率至少为多少？，计算数据在主存储器中的重复利用率至少为多少？ m m H HH 4096 140968 . 0 105 )1 ( 1 9 . 0 ， 解得解得m=44，即数据在主存储器中的重复利用率至少为，即数据在主存储器中的重复利用率至少为44次。次。 H= 0.999995560.99999556 解：解：假设数据在主存储器中的重复利用率为假设数据在主存储器中的重复利用率为m，根据前面的，根据前面的 给出关系：给出关系： 23 v目的目的：解决存储器容量与速度的问题：解决存储器容量与速度的问题

22、vCPU与主存储器的与主存储器的速度差距越来越大速度差距越来越大 1955年，第一台大型机年，第一台大型机IBM 704，CPU和主存储器的工作和主存储器的工作 周期均为周期均为12微秒，目前，微秒，目前，CPU的工作速度提高了的工作速度提高了4个数量级以个数量级以 上，主存储器的工作速度仅提高上，主存储器的工作速度仅提高2个数量级。个数量级。 v今后，今后，CPU与主存储器的速度差距会更大与主存储器的速度差距会更大 v研究研究存储系统的目的存储系统的目的就是要找出解决这一问题的办法。就是要找出解决这一问题的办法。 24 v计算机中各级存储器的频带（带宽）应该达到平衡，计算机中各级存储器的频带

23、（带宽）应该达到平衡， 即即。 v例如例如: : 一台速度为一台速度为500MIPS500MIPS的计算机系统的计算机系统, , 主存储器主存储器 的各种访问源的频带宽度如下：的各种访问源的频带宽度如下： CPUCPU取指令取指令: 500MW/s: 500MW/s CPUCPU取操作数和保存运算结果：取操作数和保存运算结果：1000MW/s1000MW/s 各种输入输出设备访问存储器：各种输入输出设备访问存储器：50MW/s50MW/s v三项相加，要求存储器的频带宽度不低于三项相加，要求存储器的频带宽度不低于1550MW/s, 1550MW/s, 即访问周期不大于即访问周期不大于0.64n

24、s, 0.64ns, 实际上目前主存储器的工作实际上目前主存储器的工作 周期为周期为100ns100ns左右左右, , 两者相差两者相差150150多倍。多倍。 25 v解决存储器频带平衡的方法解决存储器频带平衡的方法 多个存储器并行工作（本节）多个存储器并行工作（本节） 设置各种缓冲存储器（第四章：流水处理）设置各种缓冲存储器（第四章：流水处理） 采用存储系统（本章后两节）采用存储系统（本章后两节） 3.2.2 并行存储器并行存储器 v主要内容：主要内容： 并行主存系统（单体多字、多体单字、多体多字）并行主存系统（单体多字、多体单字、多体多字） 交叉访问存储器（高位交叉、低位交叉）交叉访问存

25、储器（高位交叉、低位交叉） 26 v能并行读出多个能并行读出多个CPU字的单体多字、多体单字、多体字的单体多字、多体单字、多体 多字交叉存取的主存系统称为多字交叉存取的主存系统称为并行主存系统并行主存系统。 v方法：方法：把把m字字w位的存储器改变成为位的存储器改变成为m/n字字nw位的位的 存储器（保持容量不变）（存储器（保持容量不变）（如图所示如图所示） v逻辑实现：逻辑实现：把地址码分成两个部分，一部分作为存储把地址码分成两个部分，一部分作为存储 器的地址，另一部分负责选择数据。器的地址，另一部分负责选择数据。 数据寄存器数据寄存器 MBR 存储体存储体 (m字字w位位) 地址寄存器地址

26、寄存器 MAR 一般存储器（单体单字）一般存储器（单体单字） 多路选择器多路选择器 MBR. 存储体存储体(m/n字字nw位位) MAR . 并行访问存储器（单体多字）并行访问存储器（单体多字） 28 v实现方法：实现方法：用地址码的高位区分存储体号，低位进行体内寻址。用地址码的高位区分存储体号，低位进行体内寻址。 v适用于适用于，当多个处理机发出的访存地址，当多个处理机发出的访存地址 高位不同时，可对各存储体并发存取，理想情况下，带宽可提高高位不同时，可对各存储体并发存取，理想情况下，带宽可提高 m倍。否则，倍。否则，分体冲突分体冲突。在。在单处理机系统单处理机系统中，扩充存储器的容量。中，

27、扩充存储器的容量。 v参数计算方法：参数计算方法： w：每个存储体的容量；：每个存储体的容量； n：总共的存储体个数：总共的存储体个数 j：存储体的体内地址，：存储体的体内地址，j=0, 1, 2 , w-1 k：存储体的体号，：存储体的体号，k=0, 1, 2 , n-1 存储器的地址：存储器的地址：A=wkj 存储器的存储器的体内地址体内地址：Aj=A mod w 存储器的存储器的体号体号：Ak w A Ak 29 30 v实现方法：实现方法：用地址码的低位区分存储体号，高位进行体内寻址。用地址码的低位区分存储体号，高位进行体内寻址。 v适用于单处理机适用于单处理机内的高速数据存取及带内的

28、高速数据存取及带cache的主存，当处理的主存，当处理 机发出的访存地址低位不相同时，可以进行并发存取。机发出的访存地址低位不相同时，可以进行并发存取。 v参数计算方法：参数计算方法： 存储器的地址：存储器的地址：A=nj+k 存储器的体内地址：存储器的体内地址：Aj 存储器的体号：存储器的体号：Ak=A mod n n A A j 31 32 v实际上是一种采用实际上是一种采用流水线方式工作的并行存储器流水线方式工作的并行存储器，理，理 论上，存储器的速度可望提高论上，存储器的速度可望提高n倍。倍。 v每存储体的启动间隔每存储体的启动间隔t为：为： 其中：其中：n为存储体个数为存储体个数 T

29、m为每个存储体的访问周期为每个存储体的访问周期 n T t m . tTm #0 #1 #2 #n-1 P44 图图3.9 存储周存储周 期期 启动间启动间 隔隔 33 v理论带宽可提高理论带宽可提高m倍，倍，Bm=mWTm，实际只是理想的实际只是理想的1/3 v带宽提高受限的带宽提高受限的原因原因 工程实现上的原因，工程实现上的原因，m越大，总线越长，延时增加越大，总线越长，延时增加 访问冲突概率大（访问冲突概率大（P45 图图3. 10） 取指令冲突（转移指令，取出的取指令冲突（转移指令，取出的n条指令不全有用）条指令不全有用） 读操作数冲突（取的读操作数冲突（取的n个数不全有用）个数不全

30、有用） 写数据冲突（要同时写入写数据冲突（要同时写入n个数，或先读后写）个数，或先读后写） 读写冲突（读、写同一个存储字）读写冲突（读、写同一个存储字） v结论：单纯靠增加结论：单纯靠增加m来提高并行主存系统的带宽是有来提高并行主存系统的带宽是有 限的，而且性价比还会随限的，而且性价比还会随m的增大而下降，一般取的增大而下降，一般取 m32。如不行就要发展存储体系（系统、层次）。如不行就要发展存储体系（系统、层次）。 m Bm 图图 3.10 m个分体并行存取的个分体并行存取的Bm=f()曲线曲线 35 v存储系统的性能参数存储系统的性能参数( (两级两级) ) 等效访问时间等效访问时间 T

31、Ta aHTHT1 1(1(1H)TH)T2 2 访问效率访问效率 v复杂的存储系统复杂的存储系统 Ta= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm) ),( )1 ( 1 )1 ( 1 2 21 11 rHf HHTHTH T Ta T e T T CPUCPU I-CacheI-Cache D-CacheD-Cache 主存储器主存储器 36 v提高命中率方法提高命中率方法 预取技术：预取技术：不命中时，把不命中时，把M M2 2存储器中相邻几个单元组成的存储器中相邻几个单元组成的 一个数据块都取出来送入一个数据块都取出来送入M M1 1存储器

32、中。存储器中。P40(2)P40(2) v并行主存系统与交叉访问存储器并行主存系统与交叉访问存储器 单体多字、多体单字、多体多字单体多字、多体单字、多体多字 高位交叉、低位交叉高位交叉、低位交叉 分时（流水）启动方式、对存储器带宽的提高有限分时（流水）启动方式、对存储器带宽的提高有限 n nH n H H 11 1 m Bm 37 v3.3.1 虚拟存储器的工作原理虚拟存储器的工作原理 v3.3.2 虚拟存储器的地址映像与变换虚拟存储器的地址映像与变换 v3.3.3 页面替换算法及其实现页面替换算法及其实现 v3.3.4 提高虚拟存储器等效访问速度的措施提高虚拟存储器等效访问速度的措施 v3.

33、3.5 影响主存命中率的因素影响主存命中率的因素 38 v 1961年英曼彻斯特大学的年英曼彻斯特大学的Kilburn等人提出，目前普遍使用等人提出，目前普遍使用 v 主主-辅存储层次，由辅助软、硬件管理，对应用程序员透明辅存储层次，由辅助软、硬件管理，对应用程序员透明 v 三种地址空间：三种地址空间： 逻辑地址空间（虚拟、程序地址空间，用户编程时使用）逻辑地址空间（虚拟、程序地址空间，用户编程时使用） 物理地址空间（主存地址空间，访问主存时使用）物理地址空间（主存地址空间，访问主存时使用） 辅存地址空间（访问硬盘等辅存时使用）辅存地址空间（访问硬盘等辅存时使用） v 目的：扩大主存容量，同时

34、不能降低太多速度目的：扩大主存容量，同时不能降低太多速度 v 原理：基于程序访问的局部性原理原理：基于程序访问的局部性原理 39 v地址映像：地址映像： 程序运行前程序运行前把虚拟地址空间映象到主存地址空间，即把用把虚拟地址空间映象到主存地址空间，即把用 户程序按某种规则（对应关系）装入主存。户程序按某种规则（对应关系）装入主存。 v地址变换：地址变换： 在程序运行时在程序运行时，把虚地址变换成主存实地址（内部地址变，把虚地址变换成主存实地址（内部地址变 换）、或磁盘存储器地址（外部地址变换）换）、或磁盘存储器地址（外部地址变换） v按地址映象和变换方法的不同，分按地址映象和变换方法的不同，分

35、三种虚拟存储器三种虚拟存储器管理方式：管理方式： 段式虚拟存储器段式虚拟存储器 页式虚拟存储器页式虚拟存储器 段页式虚拟存储器段页式虚拟存储器 40 v 地址映像方法：地址映像方法： 每个程序段都从每个程序段都从0地址开始编址，长度可长可短。在地址开始编址，长度可长可短。在段表段表 的控制下，将程序段映射到主存的不同区域。如图所示。的控制下，将程序段映射到主存的不同区域。如图所示。 v 地址变换方法：地址变换方法： 由用户号查找段表基址寄存器，得到段表的起始地址由用户号查找段表基址寄存器，得到段表的起始地址 把段表起始地址与多用户虚地址中段号相加得到该段在段把段表起始地址与多用户虚地址中段号相

36、加得到该段在段 表中地址（行号）表中地址（行号） 把段表中给出的起始地址与段内偏移把段表中给出的起始地址与段内偏移D相加就能得到主存相加就能得到主存 实地址，实地址， 如图所示。如图所示。 0段段 1k 1段段 2段段 3段段 0 500 0 200 0 200 0 段号段号 段长段长 起址起址 01k8k 150016k 22009k 320030k 0 8k 9k 16k 30k 程序空间程序空间 主存储器主存储器 段表段表 42 1 2 3 安全保安全保 护护 43 v主要优点：主要优点： 程序的模块化性能好。程序的模块化性能好。 便于程序和数据的共享。便于程序和数据的共享。 程序的动态

37、链接和调度比较容易（动态定位）。程序的动态链接和调度比较容易（动态定位）。 便于实现信息保护（段长字段、访问方式字段）。便于实现信息保护（段长字段、访问方式字段）。 v主要缺点：主要缺点： 地址变换速度慢，做地址变换速度慢，做两次加法两次加法运算，运算，两次查表两次查表，且段表，且段表 中的地址字段和段长字段都比较长，中的地址字段和段长字段都比较长，查表速度慢查表速度慢。 要求整段连续要求整段连续，导致主存储器的利用率比较低，易在主，导致主存储器的利用率比较低，易在主 存空间中形成大量的碎片。存空间中形成大量的碎片。 对辅存（磁盘等、要求固定大小的块）的管理比较困难。对辅存（磁盘等、要求固定大

38、小的块）的管理比较困难。 44 v首先分配首先分配 顺序扫描顺序扫描可用区域表可用区域表，当找到第一个不小于要调入，当找到第一个不小于要调入 段长度的可用区时，就立刻进行分配。段长度的可用区时，就立刻进行分配。 v最佳分配最佳分配 先先扫描全部扫描全部可用区域表，然后选择一个与程序段大可用区域表，然后选择一个与程序段大 小最接近的可用区，使分配后段间可用区零头最小。小最接近的可用区，使分配后段间可用区零头最小。 45 46 剩余空间（碎片）剩余空间（碎片） 不连续，无法装不连续，无法装 下程序下程序D D 47 v 把主存空间和程序空间都划分成把主存空间和程序空间都划分成固定大小的页固定大小的

39、页，主存，主存 空间的页称为空间的页称为实页实页，程序空间的页称为，程序空间的页称为虚页虚页。 实页号实页号nv页内位移页内位移nr v 主存实地址主存实地址np： 用户号用户号U用户虚页号用户虚页号Nv页内位移页内位移Nr v 多用户虚地址多用户虚地址Ns： 多用户虚页号多用户虚页号Nv 48 v地址映像：地址映像： 一般采用全相联映像一般采用全相联映像 v内部地址变换：内部地址变换： 多用户虚地址多用户虚地址Ns变换成主存实地址变换成主存实地址np （ Ns np ） 只需将只需将多用户虚页号转换为实页号多用户虚页号转换为实页号（NV nv ） 多用户虚地址中的页内偏移多用户虚地址中的页内

40、偏移Nr直接作为主存实地址直接作为主存实地址 中的页内偏移中的页内偏移nr （ Nr = nr ） 0页页 1页页 2页页 3页页 虚页号虚页号实页号实页号 0 1 2 3 用户程序用户程序 主存储器主存储器 页表页表 页式虚拟存储器的地址映像页式虚拟存储器的地址映像 0 1 2 3 4 5 6 7 2 6 1 4 50 Pa 装入装入 修改修改 主存页号主存页号 标志标志 用户号用户号U 虚页号虚页号P页内偏移页内偏移D 页内偏移页内偏移d 1p Pa 页表基址页表基址 页表页表 实页号实页号p 1 2 3 图图3.123.12 51 v主要优点：主要优点： 主存储器的利用率比较高；主存储器

41、的利用率比较高； 页表相对比较简单；页表相对比较简单； 地址变换的速度比较快（一次加法、两次查表）；地址变换的速度比较快（一次加法、两次查表）； 对磁盘的管理比较容易（块大小可是辅存块大小的整数倍）。对磁盘的管理比较容易（块大小可是辅存块大小的整数倍）。 v主要缺点：主要缺点： 程序的模块化结构不好；程序的模块化结构不好； 页表太长，需要占用很大的存储空间。例如：虚拟存储空间页表太长，需要占用很大的存储空间。例如：虚拟存储空间 4GB，页大小，页大小1KB，则页表的容量为，则页表的容量为4M字，若每个页表项（页字，若每个页表项（页 表的一行）占表的一行）占4B，则页表容量为，则页表容量为16M

42、B，需多级页表。，需多级页表。 52 v提高命中率方法提高命中率方法 预取技术：预取技术：不命中时，把不命中时，把M M2 2存储器中相邻几个单元组成的一存储器中相邻几个单元组成的一 个数据块都取出来送入个数据块都取出来送入M M1 1存储器中。存储器中。P40(2)P40(2) v并行主存系统与交叉访问存储器并行主存系统与交叉访问存储器 单体多字、多体单字、多体多字（对存储器带宽的提高有限）单体多字、多体单字、多体多字（对存储器带宽的提高有限） 高位交叉、低位交叉（分时启动方式）高位交叉、低位交叉（分时启动方式） v虚拟存储器虚拟存储器 逻辑地址、物理地址、辅存地址逻辑地址、物理地址、辅存地

43、址 地址映象、地址变换（段式、页式、段页式）地址映象、地址变换（段式、页式、段页式） n nH n H H 11 1 53 v段式段式 模块化性能好、主存利用率低、速度慢模块化性能好、主存利用率低、速度慢 v页式页式 主存利用率高、速度比段式快、模块化性能差、页表简单但主存利用率高、速度比段式快、模块化性能差、页表简单但 容量太大，有时可能要多级页表容量太大，有时可能要多级页表 54 v用户按照程序段来编写程序，每个程序段再分成固定大小用户按照程序段来编写程序，每个程序段再分成固定大小 的页。的页。 v地址映象地址映象 v地址变换方法：地址变换方法： 查找段表基址寄存器，找到段表位置；查找段表

44、基址寄存器，找到段表位置； 查多用户段表，得该程序段的页表起始地址和页表长度；查多用户段表，得该程序段的页表起始地址和页表长度； 再查页表找到要访问的主存实页号再查页表找到要访问的主存实页号nv； 最后把实页号最后把实页号nv与页内偏移与页内偏移nr拼接得到主存的实地址。拼接得到主存的实地址。 3、段页式虚拟存储器、段页式虚拟存储器 段页式虚拟存储器的地址映像段页式虚拟存储器的地址映像 每页每页4KB4KB 0段0页 0段(12K)0段1页 页表长度页表地址0段2页 3 0段页表 31段0页 1段(10K)21段1页 段表段表1段2页 1段页表 2段(5K)2段0页 2段1页 用户程序用户程序

45、 页表页表 主存储器主存储器 2段页表 56 装入装入修改修改实页号实页号标志标志 用户号用户号U 段号段号S页内偏移页内偏移 页内偏移页内偏移 0/11p A 实页号实页号p 虚页号虚页号P As 装入装入 1 修改修改 0/1 页表页表 地址地址 Ap As Ap 1 2 3 4 57 v页面替换发生时间：页面替换发生时间： 发生页面失效，要调一新页到主存，但此时主存已满。发生页面失效，要调一新页到主存，但此时主存已满。 v评价页面替换算法好坏的标准：评价页面替换算法好坏的标准： 命中率要高命中率要高 容易实现，辅助软、硬件成本低容易实现，辅助软、硬件成本低 v常见页面替换算法：常见页面替

46、换算法： 随机算法（随机算法（RANDRAND） 先进先出算法（先进先出算法（FIFOFIFO） 近期最少使用算法（近期最少使用算法（LRULRU） 近期最久未用过算法近期最久未用过算法（LFULFU） 最优替换算法（最优替换算法（OPTOPT） 58 随机算法随机算法(RAND Random algorithm)(RAND Random algorithm)： 简单，容易实现；没有利用历史信息，没有反映程序的局部简单，容易实现；没有利用历史信息，没有反映程序的局部 性规律，命中率低。性规律，命中率低。 先进先出算法先进先出算法 (FIFO First-In First-Out algorit

47、hm)(FIFO First-In First-Out algorithm)： 简单，容易实现；利用了历史信息，但没有反映程序的局部简单，容易实现；利用了历史信息，但没有反映程序的局部 性。最先调入主存的页面，很可能还是经常要使用的页面。性。最先调入主存的页面，很可能还是经常要使用的页面。 近期最少使用算法近期最少使用算法 (LRU Least Recently Used algorithm)(LRU Least Recently Used algorithm)： 既充分利用了历史信息，又反映了程序的局部性，命中率高。既充分利用了历史信息，又反映了程序的局部性，命中率高。 实现困难，每命中一次

48、，该页计数器（实现困难，每命中一次，该页计数器（主存页面表主存页面表（非页表）（非页表） 中的计数器字段）清中的计数器字段）清0 0，其它计数器加，其它计数器加1 1，替换时选择计数值最，替换时选择计数值最 大的页。大的页。计数器字段要很长计数器字段要很长。P60 P60 图图3.153.15 59 近期最久未用过算法近期最久未用过算法 (LFU Least Frequently Used (LFU Least Frequently Used algorithm)algorithm)： 把把LRULRU算法中的算法中的多、少多、少简化成简化成有、无有、无，实现起来相对容易。，实现起来相对容易。

49、 在主存页面表中增加在主存页面表中增加使用位使用位和和未用过计数器位未用过计数器位HsHs来实现，替来实现，替 换时选择换时选择HsHs最大的。具体最大的。具体实现细节实现细节P61P61。 最优替换算法最优替换算法 (OPT OPTimal replacemant algorithm)(OPT OPTimal replacemant algorithm)： 选择未来近期不用的替换出去。选择未来近期不用的替换出去。 是一种理想化的算法，不现实。用来作为评价其它页面替换是一种理想化的算法，不现实。用来作为评价其它页面替换 算法好坏的标准。算法好坏的标准。 v目前目前多数计算机采用多数计算机采用L

50、FULFU算法算法。 60 某程序共由某程序共由5 5个页面组成，执行个页面组成，执行页地址流页地址流如下：如下： P1, P2, P1, P5, P4, P1, P3, P4, P2, P4P1, P2, P1, P5, P4, P1, P3, P4, P2, P4 假设分配给该程序的主存共假设分配给该程序的主存共3 3个页面。试给出个页面。试给出FIFOFIFO、 LRULRU、OPT OPT 三种页面替换算法对这三种页面替换算法对这3 3页主存的使用和替页主存的使用和替 换过程。换过程。 时间t12345678910实际 页地址流P1P2P1P5P4P1P3P4P2P4 命中次数 111

51、1*444*4*22 先进先出算法2222*1111*4 （FIFO算法）555*3333* 调入调入命中调入 替换替换替换命中 替换替换2次 11111111*22 最久没有使用算法222*444*444 （LRU算法）55*5*333*3* 调入调入命中调入 替换命中替换命中 替换命中4次 111111*3*3*33 最优替换算法2222*22222 （OPT算法）5*444444 调入调入命中调入 替换命中替换命中 命中命中5次 三种页面替换算法对同一个页地址流的调度过程 * * (LFU 62 v替换算法中，有时会出现总是将下次就要使用的页面替换出去替换算法中，有时会出现总是将下次就要

52、使用的页面替换出去 的情况，导致命中率为的情况，导致命中率为0，称，称颠簸现象颠簸现象。 v例：例：一个循环程序，依次使用一个循环程序，依次使用P1，P2，P3，P4四个页面，分四个页面，分 配给该程序的主存页面数为配给该程序的主存页面数为3个。个。FIFO、LRU和和OPT三种页面替三种页面替 换算法对主存页面的调度情况如下图所示。换算法对主存页面的调度情况如下图所示。 63 64 v一般来说，分配给程序的主存页数越多，命中率越高。但非堆一般来说，分配给程序的主存页数越多，命中率越高。但非堆 栈型算法可能出现页面越多，命中率越低的情况，如图所示。栈型算法可能出现页面越多，命中率越低的情况，如

53、图所示。 v定义：定义： 对任意一个程序的页地址流作两次主存页面数分配，对任意一个程序的页地址流作两次主存页面数分配， 分别分配分别分配m个主存页面和个主存页面和n个主存页面，并且有个主存页面，并且有mn。如在任何。如在任何 时刻时刻t，主存页面数集合主存页面数集合Bt都满足如下关系，则为堆栈型算法：都满足如下关系，则为堆栈型算法： v堆栈型算法的基本特点：堆栈型算法的基本特点： 命中率随着页面数增加而提高，至少不下降。命中率随着页面数增加而提高，至少不下降。 v5种替换算法种替换算法哪些属于堆栈型替换算法哪些属于堆栈型替换算法？ )()(nBtmBt非堆栈型：随机、非堆栈型：随机、FIFOF

54、IFO 堆栈型：堆栈型：LRULRU、LFULFU、OPTOPT 65 66 v造成虚拟存储器速度降低的主要原因：造成虚拟存储器速度降低的主要原因： 要访问主存储器须先查段表或要访问主存储器须先查段表或/ /和页表和页表 可能需要多级页表可能需要多级页表 v解决方法（加快内部地址变换的方法）：解决方法（加快内部地址变换的方法）： 目录表法目录表法 快慢表法快慢表法 散列函数法散列函数法 N Ns snnp p 67 1 1、目录表法、目录表法 v基本思想：基本思想：用一个高速小容量存储器存放部分页表（仅存放用一个高速小容量存储器存放部分页表（仅存放 已装入主存的那部分页面的虚页号和实页号的对应

55、关系）。采已装入主存的那部分页面的虚页号和实页号的对应关系）。采 用用相联查找相联查找访问。访问。普通页表是什么样普通页表是什么样? ? v地址变换过程：地址变换过程：按用户号按用户号U U与虚页号与虚页号N Nv v相联访问目录表相联访问目录表。读出。读出 主存实页号主存实页号n nv v，与多用户虚地址中的，与多用户虚地址中的N Nr r拼接得到主存实地址。如拼接得到主存实地址。如 果相联访问失败，则发出页面失效请求。如图果相联访问失败，则发出页面失效请求。如图3.133.13所示。所示。P48P48 v主要优点：主要优点：与页表放在主存中相比，查表速度快。与页表放在主存中相比，查表速度快

56、。 v主要缺点：主要缺点：可扩展性比较差。主存储器容量增加时，目录表可扩展性比较差。主存储器容量增加时，目录表 变大（共变大（共 行）、造价高，速度降低。行）、造价高，速度降低。 2 v n 实页号实页号其它标志其它标志 用户号用户号U页内偏移页内偏移Nr nv 虚页号虚页号NV多用户多用户 虚地址虚地址 目录表（目录表（按内容访问的相联存储器按内容访问的相联存储器） 页内偏移页内偏移nr实页号实页号n nv v 多用户虚页号多用户虚页号 U+NV 修改位修改位 0/1 主存实地址主存实地址 相联比较相联比较 69 2 2、快慢表法、快慢表法 v根据程序访问的根据程序访问的局部性局部性，在一段

57、时间内，对页表的访问只是局，在一段时间内，对页表的访问只是局 限在少数几个存储单元内。限在少数几个存储单元内。 v可以用快表与慢表构成了一个类似于可以用快表与慢表构成了一个类似于CacheCache的两级的两级存储系统。存储系统。 v快表快表TLBTLB(Translation Lookaside Buffer)(Translation Lookaside Buffer)：小容量：小容量( (几几十几几十 个字个字) )，高速硬件实现，采用相联方式访问，高速硬件实现，采用相联方式访问 v慢表（普通页表）：慢表（普通页表）：当快表中查不到时，从存放在主存储器中当快表中查不到时，从存放在主存储器中

58、 的慢表（即普通页表）中按地址进行查找访问，其查找过程可用的慢表（即普通页表）中按地址进行查找访问，其查找过程可用 软件实现。软件实现。 P54P54图图3.173.17 v改进方案改进方案P54P54图图3.183.18 70 v虚拟存储器的三种管理方式虚拟存储器的三种管理方式 段式、页式、段页式段式、页式、段页式 掌握多用户虚地址变换成主存实地址的方法掌握多用户虚地址变换成主存实地址的方法 v页面替换算法页面替换算法 RAND、FIFO、LRU、LFU、OPT 哪些属于哪些属于堆栈型替换算法堆栈型替换算法 v提高等效访问速度（加快地址变换）的方法提高等效访问速度（加快地址变换）的方法 目录

59、表（目录表（可扩展性差，可扩展性差， 行行） 快（目录表局部）慢表法及其优化方案（减少快表比较位快（目录表局部）慢表法及其优化方案（减少快表比较位 数，用户位数，用户位u u不参与比较）不参与比较） 散列函数法及其优化方案（减少散列冲突）散列函数法及其优化方案（减少散列冲突） 2 v n 快表（快表（硬件、按内容相联访问硬件、按内容相联访问） 实页号实页号 用户号用户号U 页内偏移页内偏移Nr n nv v 虚页号虚页号NV多用户多用户 虚地址虚地址 页内偏移页内偏移nr实页号实页号nv 多用户虚页号多用户虚页号 U+ NV 主存实地址主存实地址 实页号实页号 n nv v 装入位装入位 1

60、慢表（慢表（软件、按地址访问软件、按地址访问） 分分2路同时查找路同时查找 72图图3.183.18 用户位用户位u u不不 再参与比较再参与比较 增加增加1 1位用户位位用户位 确保用户切换时确保用户切换时 的正确性的正确性 73 3 3、散列查找、散列查找 hashinghashing（按地址访问的大容量快表）（按地址访问的大容量快表） 快表容量越大，命中率越高，但查找时间越慢，容量越小查快表容量越大，命中率越高，但查找时间越慢，容量越小查 找速度越快，但命中率越低。找速度越快，但命中率越低。速度与命中率矛盾速度与命中率矛盾 为了提高速度，同时也降低成本，可以采用为了提高速度，同时也降低成