第4章__存储体系_第1页
第4章__存储体系_第2页
第4章__存储体系_第3页
第4章__存储体系_第4页
第4章__存储体系_第5页
已阅读5页,还剩113页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第第4 4章章 存储体系存储体系4.1 4.1 存储体系概念与并行主存系统存储体系概念与并行主存系统4.2 4.2 虚拟存储器虚拟存储器4.3 4.3 高速缓冲存储器高速缓冲存储器CacheCache本章重点:本章重点: 段页式和页式虚拟存储器的原理;页式虚拟存段页式和页式虚拟存储器的原理;页式虚拟存储器的地址映像;储器的地址映像;LRU/FIFO/OPTLRU/FIFO/OPT替换算法进行页替换算法进行页面替换的过程模拟;面替换的过程模拟;LRULRU算法对页地址流的堆栈算法对页地址流的堆栈处理模拟及性能分析;处理模拟及性能分析;CacheCache存储器的直接和组存储器的直接和组相联地址映

2、像;相联地址映像;LRULRU替换算法的硬件实现及替换替换算法的硬件实现及替换过程模拟;过程模拟;CacheCache存储器的性能分析等。存储器的性能分析等。本章难点:本章难点: 段页式和页式中虚实地址的计算;各种页面替段页式和页式中虚实地址的计算;各种页面替换算法的模拟和页面命中率的计算;换算法的模拟和页面命中率的计算;CacheCache组相组相联映像和块替换算法的模拟。联映像和块替换算法的模拟。4.1 4.1 存储体系概念与并行主存系统存储体系概念与并行主存系统4.1.1 4.1.1 发展存储体系的必要性发展存储体系的必要性 1.1.存储器的性能要求存储器的性能要求 1)1)大容量大容量

3、 2)2)高速度高速度 3)3)低价格低价格 2.2.容量容量 S SM M=W l m=W l m W W:存储体的字长,单位为:存储体的字长,单位为bitbit或或ByteByte。 l l:每个存储体的字数。:每个存储体的字数。 m m:并行工作的存储体的个数:并行工作的存储体的个数。 3.3.速度速度 从下面三个方面来描述从下面三个方面来描述: 1)1)访问时间访问时间T TA A T TA A是存储器接到访存到信息被读到数据总线上是存储器接到访存到信息被读到数据总线上 所需的时间。是确定所需的时间。是确定CPUCPU与存储器时间关系的重与存储器时间关系的重 要指标。要指标。 2)2)

4、存储周期存储周期T TM M T TM M是连续启动一个存储体所需要的时间间隔。一般来说是连续启动一个存储体所需要的时间间隔。一般来说总比总比T TA A大。大。 3)3)存储器频宽存储器频宽 是指存储器可以提供的数据传送率,一般用每秒钟所传是指存储器可以提供的数据传送率,一般用每秒钟所传送的信息位数来衡量。送的信息位数来衡量。 a)a)最大频宽最大频宽B BM M( (极限频宽极限频宽) ) 是存储器连续访问时能提供的频宽。是存储器连续访问时能提供的频宽。 单体:单体: B BM M =W/T =W/TM M m m体并行工作:体并行工作:B BM M =mW/T =mW/TM M b)b)

5、实际频宽实际频宽 实际频宽小于最大频宽实际频宽小于最大频宽B BM M。 4.4.价格价格 可以用总价格可以用总价格C C或每位价格或每位价格c c来表示。具有来表示。具有S SM M 位的存储器每位价格位的存储器每位价格c=C/Sc=C/SM M。其中包括了存储。其中包括了存储 器本身的价格和为该存储器操作所必须的外围器本身的价格和为该存储器操作所必须的外围 电路的价格。电路的价格。5.5.结论结论 由于存储器的价格、速度和容量的要求是矛盾由于存储器的价格、速度和容量的要求是矛盾的,为了同时满足三方面的要求,在一个完整的的,为了同时满足三方面的要求,在一个完整的存储体系中,必须采用不同工艺的

6、存储器,使得存储体系中,必须采用不同工艺的存储器,使得信息以各种方式分布于不同的存储体。信息以各种方式分布于不同的存储体。 比如:比如: 主存主存 当前活跃的信息,快,少当前活跃的信息,快,少 辅存辅存 暂时不用的信息,慢,多暂时不用的信息,慢,多 虚存虚存 swapswap 从速度来说,主存远远跟不上从速度来说,主存远远跟不上CPUCPU的要求,为的要求,为 了弥补这一差距,特引入并行和重叠技术,构了弥补这一差距,特引入并行和重叠技术,构 成并行主存系统,但这种并行主存的方法提高成并行主存系统,但这种并行主存的方法提高 频宽是有限的,因此还需从系统结构入手,发频宽是有限的,因此还需从系统结构

7、入手,发 展存储体系。展存储体系。4.1.2 4.1.2 并行主存系统频宽的分析并行主存系统频宽的分析 1.1.类型类型 1)1)单体单字单体单字 存储器字长存储器字长W W与与CPUCPU字长字长W W 相同相同, ,一次访问一个存储器一次访问一个存储器 字字, ,主存最大频宽主存最大频宽B BM M =W/T =W/TM MW位读出寄存器读出寄存器地址寄存器单体单字存储器单体单字存储器l 2) 2)单体多字单体多字 存储器字长等于存储器字长等于m m个个 CPUCPU字字, ,B BM M =mW/T =mW/TM M W位W位W位W位地址寄存器单体多字单体多字(m=4)(m=4)存储器存

8、储器 W位单字长寄存器单字长寄存器 3)3)多体单字交叉多体单字交叉总线控制地址寄存器0 地址寄存器1 地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件) CPUIOP多体多体(m=4)(m=4)交叉存储器交叉存储器 a) a)存储器字长等于存储器字长等于m m个个CPUCPU字,字,B BM M =mW/T =mW/TM M。实际频。实际频宽大于单体多字。宽大于单体多字。 单体多字:并行读出的单体多字:并行读出的m m个字要地址顺序的存在个字要地址顺序的存在于同一主存单元。于同一主存单元。 多体单字:多体单字:m m个个CPUCPU字地址不必顺序存放,只要不字地址不必顺序存放,只要

9、不发生冲突。发生冲突。 b)b)编址模式编址模式 M Mj j体的编制模式为:体的编制模式为:m i+jm i+j; 其中其中I=0I=0,1 1, ,l-1l-1,表示第,表示第i i个字;个字; j=0j=0,1 1, ,m-1m-1,表示第,表示第j j个分体;个分体; m m模模 单体多字:一个主存包含的单体多字:一个主存包含的CPUCPU字数字数 多体单字:分体体数多体单字:分体体数模体模体地址编址序列地址编址序列二进制地址码末二位状态二进制地址码末二位状态M M0 0M M1 1M M2 2M M3 30,4,8, 12, ,4i+0, 1,5,9, 13, ,4i+1, 2,6,

10、10, 14, ,4i+2, 3,7,11, 15, ,4i+3, 00011011地址的模地址的模4 4低位交叉编址低位交叉编址 4) 4)多体多字交叉多体多字交叉 多个存储体,每个存储体有多个存储体,每个存储体有CPUCPU字。字。 上述能并行读出多个上述能并行读出多个CPUCPU字的单体多字和多体字的单体多字和多体单字或多体多字的交叉存储主存系统统称为并行单字或多体多字的交叉存储主存系统统称为并行主存系统。主存系统。2.2.分析分析 提高提高m m值,可以提高主存系统的最大频率,但值,可以提高主存系统的最大频率,但并不能线性提高实际频率。并不能线性提高实际频率。 原因:原因: 1)1)模

11、模m m越高,存储器数据总线越长,导致传输越高,存储器数据总线越长,导致传输 延迟增加;延迟增加; 2)2)系统效率问题,对于顺序取指,效率可以系统效率问题,对于顺序取指,效率可以 提高提高m m倍,但遇到转移指令,效率就会下降。倍,但遇到转移指令,效率就会下降。3.3.模型分析模型分析 对于对于m m个独立分体的主存系统,处理机发出一个独立分体的主存系统,处理机发出一 串地址为串地址为A A1 1,A,A2 2, A Aq q的访存申请队,在每个主的访存申请队,在每个主 存周期到来前,申请队被扫描,截取从队头起存周期到来前,申请队被扫描,截取从队头起 的的A A1 1,A,A2 2, A A

12、k k的申请序列。申请序列是个在要的申请序列。申请序列是个在要 求访存申请的求访存申请的k k个地址中,没有两个或两个以上个地址中,没有两个或两个以上 的地址处于同一分体中的最长序列。显然的地址处于同一分体中的最长序列。显然k k表示表示 可以同时访问的分体个数的随机变量,不大于可以同时访问的分体个数的随机变量,不大于m m, 系统效率取决于系统效率取决于k k的均值的均值B B,其值越大,可访问,其值越大,可访问 的分体个数越多,系统效率越高。的分体个数越多,系统效率越高。 1)1)数学模型数学模型 设设p(k)p(k)表示申请序列长度为表示申请序列长度为k k的概率密度函数,的概率密度函数

13、,其中其中k=1,2,mk=1,2,m。则。则k k的均值的均值B B为为 B=kB=k p(k)p(k) B B实际就是每个主存周期所访问的平均字数。而实际就是每个主存周期所访问的平均字数。而p(k)p(k)与程序的状态密切相关,特别是指令转移概与程序的状态密切相关,特别是指令转移概率率p p,它定义为给定下条指令地址为非顺序地址,它定义为给定下条指令地址为非顺序地址的概率。因此的概率。因此 p(k)=(1-p)p(k)=(1-p)k-1k-1 p p, 1km 1km 几何概率几何概率 p(m)=(1-p)p(m)=(1-p)m-1m-1k=1k=1m m 所以,所以,B=kB=k p(k

14、)=1p(k)=1 p+2p+2 (1-p)(1-p) p p + +m + +m (1-p)(1-p)m-1m-1 =(1-(1-p)=(1-(1-p)m m)/p)/p 2) 2)讨论:讨论: a)a)若每条指令都是转移指令且转移成功,即若每条指令都是转移指令且转移成功,即p=1,p=1,则则B=1B=1,就是并行多体交叉存取的实际频宽,就是并行多体交叉存取的实际频宽降到和单体单字一样;降到和单体单字一样; b)b)若所有指令都不转移,即若所有指令都不转移,即p=0p=0,则,则B=mB=m,此时,此时多体交叉存储的效率最高。多体交叉存储的效率最高。k=1k=1m m 3) )结论结论 由

15、于程序的转移概率不会很低,数据分布的离由于程序的转移概率不会很低,数据分布的离散性较大,所以单纯靠增大散性较大,所以单纯靠增大m m来提高并行主存系来提高并行主存系统的频宽是有限的,而且性价比还会随统的频宽是有限的,而且性价比还会随m m的增大的增大而下降。如果采用并行主存系统仍不能满足速度而下降。如果采用并行主存系统仍不能满足速度上的要求,就必须从系统结构上改进,采用存储上的要求,就必须从系统结构上改进,采用存储体系。体系。4.1.3 4.1.3 存储体系的形成与分支存储体系的形成与分支 1.容量需求容量需求 1)程序覆盖技术程序覆盖技术 方法:方法:将大程序分块,将大程序分块, 确定在辅存

16、中的位置并放入辅存,然后根据要确定在辅存中的位置并放入辅存,然后根据要 求把当前用到的程序和数据调入主存中指定位求把当前用到的程序和数据调入主存中指定位 置以覆盖或替换那些已在主存但现在不用的段。置以覆盖或替换那些已在主存但现在不用的段。 这只构成一个存储系统而非存储体系。主辅存这只构成一个存储系统而非存储体系。主辅存 间的调入调出完全由程序员安排,增大编程难间的调入调出完全由程序员安排,增大编程难 度和负担,拉长程序运行时间,也难以使用更度和负担,拉长程序运行时间,也难以使用更 好的算法。好的算法。主存主存辅存辅存程序员程序员 2)增设辅助软硬件增设辅助软硬件 随着随着I/O处理处理机的出现

17、及多道机的出现及多道程序的发展,一道程序的发展,一道程序的运行可以与程序的运行可以与另一道程序的调入调出同时进行。因此主辅存间另一道程序的调入调出同时进行。因此主辅存间的地址定位可以改由辅助软硬件来完成,如图。的地址定位可以改由辅助软硬件来完成,如图。这样就构成了存储体系,或存储层次。这样就构成了存储体系,或存储层次。主存主存辅存辅存辅助软硬设备辅助软硬设备从整体来看,从整体来看,速度是主存的速度是主存的容量是辅存的容量是辅存的主存主存辅存存储层次辅存存储层次 如果存储层次能以接近于辅存的每位价格构成如果存储层次能以接近于辅存的每位价格构成等于辅存容量的快速主存,存储系统的性价比就等于辅存容量

18、的快速主存,存储系统的性价比就会大大提高。进一步完善发展就形成虚拟存储系会大大提高。进一步完善发展就形成虚拟存储系统。这样程序员就可以用机器指令的地址码对整统。这样程序员就可以用机器指令的地址码对整个程序统一编址,这一空间远大于实际主存空间。个程序统一编址,这一空间远大于实际主存空间。这种指令地址码称为虚地址、逻辑地址、程序地这种指令地址码称为虚地址、逻辑地址、程序地址等,其对应的存储容量称为虚存容量或程序空址等,其对应的存储容量称为虚存容量或程序空间;而实际主存的地址称为物理地址、实间;而实际主存的地址称为物理地址、实( (存存) )地地址,其对应的存储容量称为主存容量、实存容量址,其对应的

19、存储容量称为主存容量、实存容量或实或实( (主主) )存空间存空间。 由于程序空间远大于主存空间,特别多道程序,由于程序空间远大于主存空间,特别多道程序,每个用户只用到主存空间的一部分,不能将程序每个用户只用到主存空间的一部分,不能将程序全部装入主存,只能把程序空间分成较小的块或全部装入主存,只能把程序空间分成较小的块或页,由系统负责把所需块或页按需调入主存。当页,由系统负责把所需块或页按需调入主存。当用虚地址访问主存时,首先检查其对应的内容是用虚地址访问主存时,首先检查其对应的内容是否已在主存。若在,就由硬件自动把虚地址变换否已在主存。若在,就由硬件自动把虚地址变换成实地址去访存;否则需经辅

20、助软硬件将包含所成实地址去访存;否则需经辅助软硬件将包含所要访问的单元在内的那一块程序由虚存调入主存,要访问的单元在内的那一块程序由虚存调入主存,然后进行访问。这样,不论是虚实地址的变换还然后进行访问。这样,不论是虚实地址的变换还是程序的调入都不必程序员安排,而是透明的。是程序的调入都不必程序员安排,而是透明的。也正符合存储层次的要求。也正符合存储层次的要求。2.速度需求速度需求 由于主存和由于主存和CPUCPU的速度差距已达一个数量级,的速度差距已达一个数量级, 为了解决这一问题,提出了多种办法:为了解决这一问题,提出了多种办法: 1)在在CPUCPU中设置通用寄存器中设置通用寄存器(GR)

21、,让运算直接在,让运算直接在CPUCPU的的GRGR中进行,减少与主存的交往。但主存与中进行,减少与主存的交往。但主存与GRGR间间的传送要由程序设计者安排,且的传送要由程序设计者安排,且GRGR的数目不能过的数目不能过多。多。 2)2)采用存储器的多体交叉并行存取来提高主存的速采用存储器的多体交叉并行存取来提高主存的速度。但这种方法对速度的改善有限,且有可能使度。但这种方法对速度的改善有限,且有可能使性价比下降。性价比下降。 3)CacheCache主存存储层次主存存储层次 通过在通过在CPUCPU与主存间加一级速度高、容量小、每与主存间加一级速度高、容量小、每个价格较高的高速缓冲存储器个价

22、格较高的高速缓冲存储器(Cache)(Cache),借助于,借助于硬件是硬件是CacheCache和主存构成一个整体。信息在和主存构成一个整体。信息在CacheCache与主存间的传送全部由硬件完成,所以与主存间的传送全部由硬件完成,所以CacheCache对对应用程序员和系统程序员都是透明的。应用程序员和系统程序员都是透明的。高速缓冲高速缓冲 CacheCache 主主 存存 M M辅助硬件辅助硬件CPUCPU从从CPUCPU来看,来看,速度是速度是Cache的的容量是主存的容量是主存的 4)多级存储层次多级存储层次 从从M M1 1到到M Mn n,速度变慢,容量增大,价格降低。,速度变慢

23、,容量增大,价格降低。CPUCPUM M1 1M M2 2M M3 3M Mn n从从CPU来看,来看,速度是速度是M M1 1的,的,容量是容量是M Mn n的,的,价格价格是M Mn n的 程序局部性概念:程序局部性概念: a)a)时间局部性:在最近的未来要用到的信息很时间局部性:在最近的未来要用到的信息很可能是现在正在使用的信息,这是由程序循环造可能是现在正在使用的信息,这是由程序循环造成的,即循环中的语句要被重复执行。成的,即循环中的语句要被重复执行。 b)b)空间局部性:在最近的未来要用到的信息很空间局部性:在最近的未来要用到的信息很可能与现在正在使用的信息在程序空间上相邻或可能与现

24、在正在使用的信息在程序空间上相邻或相近,这是由于指令通常是顺序执行的。相近,这是由于指令通常是顺序执行的。 利用程序局部性,可以预知下一步要访问的利用程序局部性,可以预知下一步要访问的程序块而在程序块而在M M1 1中做好准备。中做好准备。时间局部性:存放近期使用过的块或页。时间局部性:存放近期使用过的块或页。空间局部性:从空间局部性:从M M2 2级把访问字所在页或块一同取级把访问字所在页或块一同取 到到M M1 1中。中。4.1.4 4.1.4 存储体系的性能参数存储体系的性能参数 以以如图如图所示的二级体系所示的二级体系(M(M1 1,M,M2 2) )为例来分析为例来分析 1.存储体系

25、的每位存储体系的每位 平均价格平均价格c c c c1 1 S SM1 M1 +c+c2 2 S SM2M2 S SM1 M1 +S+SM2M2 1)M M2 2容量大且便宜容量大且便宜,所以,所以, S SM1M122n nv v,使得页表,使得页表 中绝大部分行中实页号中绝大部分行中实页号n nv v字段及其它字段都不字段及其它字段都不 再有用了,这就会大大降低页表的空间利用率。再有用了,这就会大大降低页表的空间利用率。 c)解决办法解决办法 将页表中装入位为将页表中装入位为0的行用实页号的行用实页号n nv v字段存放字段存放该程序此虚页在辅存中的实地址,以便调页时该程序此虚页在辅存中的

26、实地址,以便调页时实现用户虚页号到辅存实地址的变换。实现用户虚页号到辅存实地址的变换。 相联目录表法相联目录表法: :把页表压缩成只存放已装入主把页表压缩成只存放已装入主存的那些虚页存的那些虚页( (用基号用基号b b和和N Nv v标识标识) )与实页位置与实页位置(n(nv v) )的对应关系。这样该表最多为的对应关系。这样该表最多为2 2n nv v行,简称行,简称为目录表法,采用按内容访问的相联存储器构为目录表法,采用按内容访问的相联存储器构成。成。如下图:如下图:基号基号用户虚页号用户虚页号页内位移页内位移某用户虚地址某用户虚地址基号用户基号用户 虚页号虚页号实页号实页号其它其它信息

27、信息目录表目录表( (存在相联存储器中存在相联存储器中) )相联比较相联比较查找到查找到目录表法目录表法NvbNrnvnvnr(Nr)npb+Nv2 2n nv v行行 d)相联存储器相联存储器 在一个存储周期内能将给定的在一个存储周期内能将给定的N Nv v同时与目录表同时与目录表 的全部的全部2 2n nv v个单元对应的虚页号字段内容比较进行个单元对应的虚页号字段内容比较进行 相联查找。如有相符的即相联查找到时,表示此相联查找。如有相符的即相联查找到时,表示此 虚页已装入主存,该单元存放的实页号虚页已装入主存,该单元存放的实页号n nv v就是此就是此 虚页所存放的实页位置,将其读出拼接

28、上虚页所存放的实页位置,将其读出拼接上N Nr r就可就可 形成访存实地址形成访存实地址n np p;如无相符的即相联查找不到,;如无相符的即相联查找不到, 表示此虚页未装入主存,发生页面失效,请求从表示此虚页未装入主存,发生页面失效,请求从 辅存中调页。由此可见,采用目录表法不用设置辅存中调页。由此可见,采用目录表法不用设置 装入位了。装入位了。 6)虚页的调入虚页的调入 当发生页面失效时,要想把该道程序的虚页当发生页面失效时,要想把该道程序的虚页 调入主存,必须给出该页在辅存中的实际地址。调入主存,必须给出该页在辅存中的实际地址。 为了提高调页效率,辅存一般是按信息块编址为了提高调页效率,

29、辅存一般是按信息块编址 的,且块的大小等于页面大小。以磁盘为例,的,且块的大小等于页面大小。以磁盘为例, 辅存实辅存实( (块块) )地址格式地址格式NvNvd d为:为: 这样就需要将多用户虚页号这样就需要将多用户虚页号N Nv v变换成辅存实变换成辅存实 地址地址NvNvd d 。磁盘号磁盘号柱面号柱面号磁头号磁头号块块 号号NvNvd d 外页表外页表:存放用户虚页号存放用户虚页号N Nv v与辅存实地址与辅存实地址NvNvd d的的 映像关系,用于外部地址变换。映像关系,用于外部地址变换。 内页表内页表:存放用户虚页号存放用户虚页号N Nv v与主存实页号与主存实页号n nv v的映的

30、映 像关系,用于内部地址变换。像关系,用于内部地址变换。 由于虚拟存储器的页面失效率很低,很少调用由于虚拟存储器的页面失效率很低,很少调用 外页表进行地址变换,因此外页表存放在辅存中,外页表进行地址变换,因此外页表存放在辅存中, 当某道程序初始运行时,才把外页表的内容转录当某道程序初始运行时,才把外页表的内容转录 到已建立内页表的实页号地址字段中,这也是前到已建立内页表的实页号地址字段中,这也是前 述当内页表装入位为述当内页表装入位为0时让实页号地址字段改放时让实页号地址字段改放 该虚页在辅存中的实地址的原因。而且对外页表该虚页在辅存中的实地址的原因。而且对外页表 速度要求低,可以用软件实现。

31、速度要求低,可以用软件实现。如下图:如下图:磁盘号磁盘号柱面号柱面号 磁头号磁头号 块号块号NvNvd d多用户虚地址多用户虚地址辅存地址辅存地址NrNSuNvNvNvd d1 1装入位装入位辅存实地址辅存实地址 地址变换地址变换( (软件实现软件实现) )已装入已装入外页表外页表虚地址到辅存实地址的变换虚地址到辅存实地址的变换2Nv2.替换算法替换算法 1)解决问题解决问题 当处理机要用到的指令或数据不在主存中时,当处理机要用到的指令或数据不在主存中时, 就会产生页面失效,应去辅存中将包含该指令就会产生页面失效,应去辅存中将包含该指令 或数据的一页调入主存。由于虚存空间比主存或数据的一页调入

32、主存。由于虚存空间比主存 空间大得多,必然会出现主存页面位置已全被空间大得多,必然会出现主存页面位置已全被 占用后又发生页面失效,这时再将辅存中的一占用后又发生页面失效,这时再将辅存中的一 页调入主存时就发生页面争用。只用强制腾出页调入主存时就发生页面争用。只用强制腾出 主存中某页后才能接纳从辅存调来的新页。具主存中某页后才能接纳从辅存调来的新页。具 体选择主存中哪一页作为被替换的页,就是替体选择主存中哪一页作为被替换的页,就是替 换算法要解决的问题。换算法要解决的问题。 2)原则原则 a)有高的主存命中率有高的主存命中率 b)算法便于实现算法便于实现 c)辅助软、硬件成本尽量低辅助软、硬件成

33、本尽量低 3)常用算法常用算法 a)随机算法随机算法( (Random,RAND) ) 用软的或硬的随机数产生器来形成主存中要被用软的或硬的随机数产生器来形成主存中要被替换页的页号。这种算法简单,易于实现,但没替换页的页号。这种算法简单,易于实现,但没有利用主存使用情况的历史信息,反映不了程序有利用主存使用情况的历史信息,反映不了程序的局部性,使主存命中率低,很少采用。的局部性,使主存命中率低,很少采用。 b)先进先出算法先进先出算法(First In First Out,FIFO) 选择最早装入的页作为被替换的页。这种算法选择最早装入的页作为被替换的页。这种算法 实现方便,虽然利用了主存使用

34、情况的历史信息,实现方便,虽然利用了主存使用情况的历史信息, 但是不一定能正确反映出程序的局部性,因为最但是不一定能正确反映出程序的局部性,因为最 先进入的页很可能是现在经常要用到的页先进入的页很可能是现在经常要用到的页。 实页号实页号 占用位占用位 程序号程序号 段页号段页号 计数器计数器(使用位使用位) 程序优先位程序优先位 HS其它信息其它信息012nv-1主存页面表主存页面表 c)近期最少使用算法近期最少使用算法(Least Recently Used, ,LRU) ) 选择近期最少访问的页作为被替换的页。这种选择近期最少访问的页作为被替换的页。这种 算法能比较正确的反映程序的局部性,

35、因为当前算法能比较正确的反映程序的局部性,因为当前 最少使用的页一般来说未来也将很少访问,但完最少使用的页一般来说未来也将很少访问,但完 全按此算法实现比较困难,需要为每个实页都配全按此算法实现比较困难,需要为每个实页都配 置一个字长很长的计数器字段才行。所以一般采置一个字长很长的计数器字段才行。所以一般采 用它的变形,即近期最久没被访问过的页作为被用它的变形,即近期最久没被访问过的页作为被 替换的页。这样把替换的页。这样把“多多”和和“少少”简化成简化成“有有”和和“无无” 之后,实现起来比较方便。之后,实现起来比较方便。 主存页面表主存页面表 OS为实现主存管理而设置的,是对主存而言为实现

36、主存管理而设置的,是对主存而言 的,整个主存只有一个。每一行用来记录主存中的,整个主存只有一个。每一行用来记录主存中 各页的使用状况。而页表是对程序空间而言的,各页的使用状况。而页表是对程序空间而言的, 每道程序都有一个,是用来存储地址映像关系和每道程序都有一个,是用来存储地址映像关系和 实现地址变换的。实现地址变换的。 实页号实页号:主存页号是顺序的,可以省略主存页号是顺序的,可以省略 占用位占用位:表示该主存页面是否被占用表示该主存页面是否被占用 程序号程序号/段页号段页号:该主存页被哪道程序的哪段该主存页被哪道程序的哪段 哪页占用哪页占用 使用位使用位:表示该主存页近期是否被使用过表示该

37、主存页近期是否被使用过 开始时所有页的使用位全为开始时所有页的使用位全为“0”0”,只要某个页,只要某个页的的 任何单元被访问过,硬件就自动将该页使用位置任何单元被访问过,硬件就自动将该页使用位置 “ “1”1”。由于采用全相联映像,调入页可进入对。由于采用全相联映像,调入页可进入对应应 于主存页面表中任何占用位为于主存页面表中任何占用位为“0”0”的实页位置,的实页位置, 一旦装入主存某实页上,就置该实页的占用位为一旦装入主存某实页上,就置该实页的占用位为 “ “1”1”。只有当所有占用位都是。只有当所有占用位都是1 1且又发生页面失且又发生页面失效效 时才有页面替换问题,这时就要用到使用位

38、,只时才有页面替换问题,这时就要用到使用位,只 需替换使用位为需替换使用位为“0”0”的页即可。的页即可。 使用位全使用位全“1 ”处理处理 一种办法是由硬件强制全部使用位都为一种办法是由硬件强制全部使用位都为“0”。 从概念上看,近期最少使用的从概念上看,近期最少使用的“期期”是从上次使用是从上次使用 位全位全0到这次使用位全到这次使用位全0的这段时间。由于这个期的这段时间。由于这个期 的长短是随机的,所以称为随机期法。的长短是随机的,所以称为随机期法。 另一种办法是它定期的置全部使用位为另一种办法是它定期的置全部使用位为“0”。 由由“未用过计数器未用过计数器”HS(或称为历史位或称为历史

39、位),定期地每,定期地每 隔隔t扫视使用位扫视使用位,对使用位为对使用位为0的页,则加的页,则加1Hs, 并让使用位继续为并让使用位继续为0;对使用位为;对使用位为1的页,则置的页,则置 0Hs,同时置,同时置0使用位。扫描结束所有使用位为使用位。扫描结束所有使用位为0, Hs大的就是最久未访问过的,作为替换页。大的就是最久未访问过的,作为替换页。 d)优化替换算法优化替换算法(OPT) 定义定义 无论是无论是“近期最少使用近期最少使用”还是还是“近期最久未用近期最久未用过过” 都属于都属于LRU,与,与FIFO类似,都是根据页面使用类似,都是根据页面使用 的历史情况来预估未来的页面使用状况,

40、只是的历史情况来预估未来的页面使用状况,只是 比比FIFO更好反映局部性而已。然而,这种更好反映局部性而已。然而,这种“近近期期”毕竟是过去了的近期,如果能根据未来实毕竟是过去了的近期,如果能根据未来实际使用情况,替换出近期不用的页,主存命中际使用情况,替换出近期不用的页,主存命中率会更高,这就是优化替换算法率会更高,这就是优化替换算法(Optimal Replacement Algorithm,OPT) 方法方法 在时刻在时刻t找出主存中每个页面将要用到的时刻找出主存中每个页面将要用到的时刻ti, 然后选择然后选择tit最大的那一页作为被替换的页。显最大的那一页作为被替换的页。显 然,这只有

41、让程序运行一遍得到实际的页地址流,然,这只有让程序运行一遍得到实际的页地址流, 才能找到为实现这种替换算法所需要的各页使用才能找到为实现这种替换算法所需要的各页使用 信息,这是不现实的。所以,优化替换算法只是信息,这是不现实的。所以,优化替换算法只是 一种理想化的算法,它可以被用作评价其它替换一种理想化的算法,它可以被用作评价其它替换 算法好坏的标准,看看哪种替换算法能使主存的算法好坏的标准,看看哪种替换算法能使主存的 命中率接近于优化替换算法。命中率接近于优化替换算法。 4)影响命命中率的因素影响命命中率的因素 a)与替换算法有关与替换算法有关 例:例:设有一道程序,有设有一道程序,有1 1

42、至至5 5共共5 5页,执行时的页,执行时的 页地址流页地址流( (即执行时依次使用到的程序页页号即执行时依次使用到的程序页页号) )为:为: 2 2,3 3,2 2,1 1,5 5,2 2,4 4,5 5,3 3,2 2,5 5,2 2 若分配给该道程序的主存有若分配给该道程序的主存有3 3页,如下图表示分页,如下图表示分别用别用FIFO,LRU,OPT3FIFO,LRU,OPT3种替换算法对这种替换算法对这3 3页的使用页的使用和替换过程。和替换过程。FIFOFIFO的命中率最低,而的命中率最低,而LRULRU的接近的接近于于OPTOPT的。的。2* *312323命中命中2调进调进 调进

43、调进调进调进53* *1替换替换521* *替换替换5* *24替换替换5* *24命中命中32* *4替换替换32* *4命中命中354* *替换替换3* *52替换替换 FIFO命中命中3次次2323命中命中2调进调进 调进调进2323命中命中2调进调进 调进调进 LRU命中命中5次次 OPT命中命中6次次页地址流页地址流 2 3 2 1 5 2 4 5 3 2 5 2时间时间t 1 2 3 4 5 6 7 8 9 10 11 1223* *1调进调进2* *51替换替换251* *命中命中25* *4替换替换2* *54命中命中354* *替换替换35* *2替换替换3* *52命中命中

44、3* *52命中命中231* *调进调进23* *5替换替换2* *35命中命中4* *35替换替换4* *35命中命中4* *35命中命中23* *5替换替换235命中命中235命中命中3 3种替换算法对同一页地址流的替换过程种替换算法对同一页地址流的替换过程 b)命中率与页地址流有关命中率与页地址流有关 例如例如一个循环程序,当所需页数大于分配给一个循环程序,当所需页数大于分配给 它的主存页数时,无论是它的主存页数时,无论是FIFO还是还是LRU算法的算法的 命中率都明显低于命中率都明显低于OPT的。的。如下图如下图所示,所示,LRU 和和FIFO一次都没有命中,因为它恰好总是将马一次都没

45、有命中,因为它恰好总是将马 上要用到的页面给替换出去了,从而连续不断上要用到的页面给替换出去了,从而连续不断 的出现页面失效,产生所谓的的出现页面失效,产生所谓的颠簸现象颠簸现象。 1* *2312142* *3413* *4* *1231* *2342* * FIFO无命中无命中121121 LRU无命中无命中 OPT命中命中3次次页地址流页地址流 1 2 3 4 1 2 3 4时间时间t 1 2 3 4 5 6 7 812* *4134* *123* *1* *24命中命中命中命中13* *4命中命中 命中率与页地址流有关命中率与页地址流有关124* *1* *2342* *3413* *

46、4* *1231* *2342* * c)与主存容量与主存容量(即分配给程序的主存页数即分配给程序的主存页数)有关有关 一般来说,分配给程序的主存页数越多,虚一般来说,分配给程序的主存页数越多,虚页装入主存的机会就越多,命中率也可能就越页装入主存的机会就越多,命中率也可能就越高。但具体还与所采用的替换算法有很大关系。高。但具体还与所采用的替换算法有很大关系。如下图所示,当分配给程序的主存页数如下图所示,当分配给程序的主存页数n由由3增增加到加到4时,时,FIFO的命中率反而由的命中率反而由3/12降到降到2/12;而而LRU的命中率却不会发生这种情况,随着分的命中率却不会发生这种情况,随着分配

47、给该道程序的主存页数的增加,命中率一般配给该道程序的主存页数的增加,命中率一般都会得到提高,至少不会降低。都会得到提高,至少不会降低。121* *21413* *4* *1251* *251* *2命中命中51* *2命中命中532* *5* *345* *34命中命中 n=3命中命中3次次12121 n=4命中命中2次次页地址流页地址流 1 2 3 4 1 2 5 1 2 3 4 5时间时间t 1 2 3 4 5 6 7 8 9 10 11 121* *23命中命中342* *3341* *234命中命中1* *23452* *34513* *45124* *5* *12341* *2345

48、2* *3FIFO法的实页数增加,命中率反而有可能下降法的实页数增加,命中率反而有可能下降 5)堆栈型替换算法堆栈型替换算法 a)定义定义 A A:长度为:长度为L的任意一个页面地址流的任意一个页面地址流 t: 已处理过已处理过t1个页面的时间点个页面的时间点 n:分配给该地址流的主存页面数:分配给该地址流的主存页面数 Bt(n):在:在t时间点、在时间点、在n页的主存中的页面集合页的主存中的页面集合 Lt:到:到t时刻已遇到的地址流中相异页的页数时刻已遇到的地址流中相异页的页数 若若 n= Lt时,时, Bt(n1) = Bt(n) 成立,则此替成立,则此替换算法属于堆栈型的替换算法。换算法

49、属于堆栈型的替换算法。 b)优点优点 命中率随主存页数的增加只可能提高,至少不命中率随主存页数的增加只可能提高,至少不会下降。会下降。 只需采用堆栈处理技术对地址流模拟处理一次,只需采用堆栈处理技术对地址流模拟处理一次,即可同时获得对此地址流在不同主存页数时的即可同时获得对此地址流在不同主存页数时的命中率,大大节省存储体系设计的工作量。命中率,大大节省存储体系设计的工作量。 对页地址流对页地址流A A在在t t时刻的时刻的A At t页是否命中,只需看页是否命中,只需看S St-1t-1( (主存在主存在t-1t-1时刻的堆栈时刻的堆栈) )的前的前n n项是否有项是否有A At t,若有则命

50、中。若有则命中。 c)LRU算法算法 属于堆栈型算法,把刚访问过的页面至属于堆栈型算法,把刚访问过的页面至于栈顶,而把最久未被访问过的页面置于于栈顶,而把最久未被访问过的页面置于栈底。命中率随着分配给该道程序的主存栈底。命中率随着分配给该道程序的主存页数页数n n的增加而单调上升,至少不会下降,的增加而单调上升,至少不会下降,这是堆栈型算法具有的共同特点。这是堆栈型算法具有的共同特点。 d)FIFO算法算法 非堆栈型算法,命中率总趋势是会随着非堆栈型算法,命中率总趋势是会随着主存页数主存页数n的增加而提高,但从某个局部的增加而提高,但从某个局部来看,主存页数来看,主存页数n的增加有时反倒可能降

51、的增加有时反倒可能降低其命中率。低其命中率。 5)页面失效频率法页面失效频率法(PFF) 由于堆栈型替换算法具有随分配给该道程序的实由于堆栈型替换算法具有随分配给该道程序的实页数页数n n的增加,命中率的增加,命中率H H会单调上升的特点,所以可会单调上升的特点,所以可对对LRULRU算法加以改进和发展:根据各道程序运行中算法加以改进和发展:根据各道程序运行中的主存页面失效率的高低,由的主存页面失效率的高低,由OSOS来动态调节分配给来动态调节分配给每道程序的实页数。当主存页面失效率超过某个限每道程序的实页数。当主存页面失效率超过某个限值时就自动增加给该道程序的主存页数来提高其命值时就自动增加

52、给该道程序的主存页数来提高其命中率;而当主存页面失效率低于某个限值时就自动中率;而当主存页面失效率低于某个限值时就自动减少分配给该道程序的主存页数,以便释放出这部减少分配给该道程序的主存页数,以便释放出这部分主存页面位置给其它程序用,从而使整个系统总分主存页面位置给其它程序用,从而使整个系统总的主存命中率和主存利用率得到提高。的主存命中率和主存利用率得到提高。3.虚拟存储器工作的全过程虚拟存储器工作的全过程 具体过程见下页图:具体过程见下页图:NvNvd d辅存实地址辅存实地址 外部地址变换外部地址变换虚地址虚地址=辅存实地址辅存实地址用户标志用户标志u虚页号虚页号NvNr 6 多用户多用户虚

53、地址虚地址N NS S 内部地址变换内部地址变换虚页号虚页号=主存实页号主存实页号nvnrnp 5 2 1 2页面页面02 2n nv v-1 2 2n nr r个字个字2 2n nv v个页个页 3 3 2是否在是否在 主存?主存? “是是”( (访主存访主存) ) “否否”( (主存页主存页 面失效面失效) ) 4 5主存主存(页式页式) 2 2n np p个字个字是否在是否在 辅存?辅存? 8 6 “否否”(辅存页辅存页面失效面失效) “是是”(访辅存访辅存)主存页面表主存页面表 9 6页面替页面替换算法换算法1112已满已满未满未满10I/O处理机处理机13主存主存页号页号页面页面0页

54、面页面0112Nv-1(选页选页) 714调入页调入页 714替换页替换页 被替换页退回被替换页退回若未被修改则不必退回若未被修改则不必退回 辅存辅存2 2N NS S个字个字4.2.34.2.3页式虚拟存储器实现中的问题页式虚拟存储器实现中的问题 1.页面失效处理页面失效处理 1)原因原因 页面的划分只是机械的对程序空间和主存空间页面的划分只是机械的对程序空间和主存空间进行等分,与程序的逻辑结构毫无关系。这样,进行等分,与程序的逻辑结构毫无关系。这样,对于按字节编址的存储器就有可能出现一条指令对于按字节编址的存储器就有可能出现一条指令横跨在两页上存储的情况。同理,也会出现一个横跨在两页上存储

55、的情况。同理,也会出现一个操作数跨在两页上存储。另外,采用间接寻址,操作数跨在两页上存储。另外,采用间接寻址,特别是多重间接寻址时,在寻址的过程中,可能特别是多重间接寻址时,在寻址的过程中,可能出现跨页、甚至连续跨多个页访问的情况。每当出现跨页、甚至连续跨多个页访问的情况。每当当前一页已在主存而跨页存放的另一页不在主存当前一页已在主存而跨页存放的另一页不在主存时,就会发生页面失效。时,就会发生页面失效。 2)解决方法解决方法 由于页面失效可能出现于取指、取操作数、间接由于页面失效可能出现于取指、取操作数、间接寻址等过程中,即会在一条指令的分析或执行中发寻址等过程中,即会在一条指令的分析或执行中

56、发生。通常的中断都是依靠在每条指令执行的末尾去生。通常的中断都是依靠在每条指令执行的末尾去设置一个访中断微操作,来检查系统中有无未屏蔽设置一个访中断微操作,来检查系统中有无未屏蔽的中断请求,以便对其进行响应和处理。而页面失的中断请求,以便对其进行响应和处理。而页面失效不能采用这种办法,否则由于未能对页面失效进效不能采用这种办法,否则由于未能对页面失效进行处理,就不可能调页,也就无法执行到访中断微行处理,就不可能调页,也就无法执行到访中断微操作,从而就不可能对页面失效进行响应和处理,操作,从而就不可能对页面失效进行响应和处理,机器的工作就被停顿下来。所以,页面失效不能按机器的工作就被停顿下来。所

57、以,页面失效不能按一般的中断对待,应看作一种故障,一旦出现,处一般的中断对待,应看作一种故障,一旦出现,处理机必须立即予以响应和处理。理机必须立即予以响应和处理。 a)后援寄存器技术后援寄存器技术 把发生页面失效故障时指令的全部现场都保把发生页面失效故障时指令的全部现场都保 存下来。在处理完故障并把所需要的页调入主存下来。在处理完故障并把所需要的页调入主 存后,取出后援寄存器的内容恢复故障点现场,存后,取出后援寄存器的内容恢复故障点现场, 然后从故障点处继续执行完该条指令。然后从故障点处继续执行完该条指令。 b)预判技术预判技术 执行指令前先预判操作数的首尾字符是否都执行指令前先预判操作数的首

58、尾字符是否都 已在主存中。如果是,才执行这条指令;否则已在主存中。如果是,才执行这条指令;否则 就发生页面失效,直到调入该页后才开始执行就发生页面失效,直到调入该页后才开始执行 这条指令。这条指令。 c)替换算法替换算法 不允许出现指令或操作数跨页存储的那些页不允许出现指令或操作数跨页存储的那些页 被轮流从主存中替换出去的被轮流从主存中替换出去的“颠簸颠簸”现象。因此,现象。因此, 给某道程序分配的主存页数应该有个下限。给某道程序分配的主存页数应该有个下限。 d)页面大小不能过大页面大小不能过大 以便多道程序的道数、每道程序所分配到的以便多道程序的道数、每道程序所分配到的 主存页数都能在一个适

59、当的范围内。如果页面主存页数都能在一个适当的范围内。如果页面 过大,就会使主存中页数过少,从而出现大量过大,就会使主存中页数过少,从而出现大量 的页面失效,严重降低虚拟存储器的访问速率的页面失效,严重降低虚拟存储器的访问速率 和等效速度。和等效速度。2.2.提高虚拟存储器等效访问速度的措施提高虚拟存储器等效访问速度的措施 根据根据虚拟存储器等效访问速度公式虚拟存储器等效访问速度公式 TA=HTA1+(1-H)TA2 希望希望H H提高,提高, TA1 ,TA2缩短缩短 关于高的主存命中率问题,其影响因素很多,关于高的主存命中率问题,其影响因素很多,如地址流、页面调度策略、替换算法、页面大小如地

60、址流、页面调度策略、替换算法、页面大小及分配给程序的页数及分配给程序的页数( (主存容量主存容量) )等。这里主要讨等。这里主要讨论怎样缩短访主存的时间。论怎样缩短访主存的时间。 从虚拟存储器工作的全过程可以看到,每次访从虚拟存储器工作的全过程可以看到,每次访问主存时,都必须进行内部地址变换问主存时,都必须进行内部地址变换(因为页表都因为页表都存在主存中,每次查页表就要增加一次访存。若存在主存中,每次查页表就要增加一次访存。若采用段页式虚拟存储器,查表要增加两次访存采用段页式虚拟存储器,查表要增加两次访存),其概率是其概率是100%。从缩短访主存的时间来看,关。从缩短访主存的时间来看,关键就是

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论