计算机系统结构第四章学习资料.ppt

《计算机系统结构第四章学习资料.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构第四章学习资料.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机系统结构第四章存贮器的速度可用访问时间存贮器的速度可用访问时间T TA A、存贮周期、存贮周期T TM M、频宽（也称、频宽（也称带宽）带宽）B BM M来描述。来描述。访问时间访问时间T TA A：存贮器从接到访存申请，到信息被读到数据存贮器从接到访存申请，到信息被读到数据总线上所需的时间。总线上所需的时间。存贮周期存贮周期T TM M：连续启动一个存贮体所需要的时间间隔，一连续启动一个存贮体所需要的时间间隔，一般比般比T TA A大。大。速度速度2频宽频宽存储器频宽：存储器可提供的数据传送速率，即每秒钟存储器频宽：存储器可提供的数据传送速率，即每秒钟传送的信息位数传送的信息位数最大频

2、宽最大频宽B BM M：存储器连续访问时能提供的带宽：存储器连续访问时能提供的带宽。单体最大频宽：单体最大频宽：B BM M=W/T=W/TM Mm m个存储体并行工作的最大带宽：个存储体并行工作的最大带宽：B BM M=W m/T=W m/TM M其中其中 W W：存贮体的字长（位或字节）；：存贮体的字长（位或字节）；m m：并行工作的存贮体个数。并行工作的存贮体个数。每位价格每位价格c=C/Sc=C/SM M 其中其中C C：总价格：总价格 ；S SM M：位数。：位数。3这三个指标相互矛盾这三个指标相互矛盾:42.并行主存系统频宽的分析并行主存系统频宽的分析频带宽度：单位时间内所能访问的

3、数据量。频带宽度：单位时间内所能访问的数据量。W位单体单字存贮器单体单字存贮器读出寄存器读出寄存器地址寄存器l l字长为字长为W W位的单体主存，位的单体主存，最大频宽最大频宽B BM M=W/T=W/TM M5W位位W位位W位位W位位W位位地址寄存器单体多字（单体多字（m=4）存贮器）存贮器单字长寄存器单字长寄存器 l l/4最大频宽最大频宽B BM M=4W/T=4W/TM Mm m为一个主存字所包含的为一个主存字所包含的CPUCPU字数。字数。6M0主主 存存 控控 制制 部部 件件多体（多体（m=4）交叉存贮器）交叉存贮器地址寄存器地址寄存器0地址寄存器地址寄存器1地址寄存器地址寄存器

4、2地址寄存器地址寄存器3M1M2M3总总 线线 控控 制制 CPUIOPCPUCPU字在主存中可按模字在主存中可按模m m交叉编址，交叉编址，m m为分体体数。为分体体数。MiMi体的编址模式为：体的编址模式为：m i+j m i+j，其中其中i=0i=0，1 1，2 2，,l-1;j=0,1,2,m-1,l-1;j=0,1,2,m-17并行主存系统并行主存系统：能并行读出多个能并行读出多个CPUCPU字的单体多字和多体单字或多体字的单体多字和多体单字或多体多字的交叉存贮系统。多字的交叉存贮系统。多体单字与单体多字比较：多体单字与单体多字比较：前者花费的器件和总价格并不比后者多多少，但其实际前

5、者花费的器件和总价格并不比后者多多少，但其实际频宽却可以比较高（为单体单字的频宽却可以比较高（为单体单字的m m倍）。倍）。单体多字方式要求可并行读出的单体多字方式要求可并行读出的m m个字必须是地址顺序的个字必须是地址顺序的且处于同一主存单元，而多体单字则可并行读出地址不连且处于同一主存单元，而多体单字则可并行读出地址不连续的主存字。续的主存字。多体单字方式的各存贮体可以同时启动也可以分时启动。多体单字方式的各存贮体可以同时启动也可以分时启动。8采用多种存贮器技术，构成采用多种存贮器技术，构成存贮层次存贮层次:3.存贮体系的形成与分支存贮体系的形成与分支9 一般来说：一般来说：“Cache“

6、Cache主存主存”层次：由层次：由CacheCache和主存贮器构成。和主存贮器构成。主要目的：提高存主要目的：提高存贮贮器速度。器速度。“主存辅存主存辅存”层次：由主存和磁盘存层次：由主存和磁盘存贮贮器构成器构成 主要目的：扩大存主要目的：扩大存贮贮器容量。器容量。10“Cache-“Cache-主存主存”层次的实现：主要借助于辅助硬层次的实现：主要借助于辅助硬件件从从CPUCPU看，速度是看，速度是CACHECACHE的，容量是主存的。的，容量是主存的。11 “主辅存主辅存”层次的实现：主要借助于辅助软硬件层次的实现：主要借助于辅助软硬件从整体上看，速度是主存的，容量是辅存的从整体上看，

7、速度是主存的，容量是辅存的。12主要由软件实现主要由软件实现,硬件为辅硬件为辅“Cache“Cache主存主存”与与“主存辅存主存辅存”层次的区别层次的区别几百到几千个字节几百到几千个字节存储层次存储层次CPUCPU对第二级的对第二级的访问方式访问方式比较项目比较项目目的目的存储管理实现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小失效时失效时CPUCPU是否切换是否切换“Cache“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为了弥补主存速度的不足为了弥补主存容量的不足为了弥补主存容量的不足主要由

8、专用硬件实现主要由专用硬件实现几比一几比一几百比一几百比一几十个字节几十个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程主要由专用软件实现主要由专用软件实现几百到几千个字节几百到几千个字节134.程序局部性原理程序局部性原理程序的局部性程序的局部性:时间上的局部性和空间上的局部时间上的局部性和空间上的局部性。性。v时间局部性指的是：在最近的未来要用到的信时间局部性指的是：在最近的未来要用到的信息很可能是现在正在使用的信息。息很可能是现在正在使用的信息。v空间局部性指的是：在最近的未来要用到的信空间局部性指的是：在最近的未来要用到的信息很可能是与现在正在

9、使用的信息在程序空间上息很可能是与现在正在使用的信息在程序空间上是相邻或相近的。是相邻或相近的。14155.存贮体系的性能参数存贮体系的性能参数存贮系统的单位容量平均价格。存贮系统的单位容量平均价格。计算公式：计算公式：M1(S1,C1,T1)M2(S2,C2,T2)总希望每位平均价格能接近于总希望每位平均价格能接近于C2(C2(辅存辅存),),为此应使：为此应使：S2S1 S2S1其中：其中：CiCi为为MiMi的每位价格；的每位价格；Si Si为为MiMi的以位计算的存贮容量。的以位计算的存贮容量。v每位价格每位价格C C，命中率，命中率H H，等效访问时间，等效访问时间T TA A16命

10、中率定义：在命中率定义：在M1M1存贮器中访问到的概率。存贮器中访问到的概率。存贮系统的等效访问时间：存贮系统的等效访问时间：vT TA AHTHT1 1(1(1H)TH)T2 2N1:M1N1:M1的访问次数的访问次数 ；N2:M2 N2:M2的访问次数的访问次数当命中率当命中率H1H1时，时，TT1TT117存贮系统的访问效率存贮系统的访问效率e：存贮系统的访问效率主要与命中率和两级存贮器的存贮系统的访问效率主要与命中率和两级存贮器的速度之比有关。速度之比有关。例：假设例：假设T2=5T1T2=5T1，在命中率，在命中率H H为为0.90.9和和0.990.99两种情两种情况下，分别计算存

11、贮系统的访问效率。况下，分别计算存贮系统的访问效率。解：当解：当H=0.9H=0.9时时,e1=1/(0.9+5(1,e1=1/(0.9+5(1 0.9)=0.720.9)=0.72当当H=0.99H=0.99时时,e2=1/(0.99+5(1,e2=1/(0.99+5(1 0.99)=0.960.99)=0.96184.2 4.2 虚拟存贮器（虚拟存贮器（Virtual Memory）19611961年英国曼彻斯特大学年英国曼彻斯特大学KilburnKilburn等人提出。等人提出。7070年代广泛地应用于大中型计算机系统中。年代广泛地应用于大中型计算机系统中。KilburnKilburn特

12、点：特点：v虚拟存贮器指的是虚拟存贮器指的是“主主辅存辅存”层层次；次；v它能使计算机具有辅存的容量它能使计算机具有辅存的容量,接近接近于主存的速度和辅存的每位成本；于主存的速度和辅存的每位成本；v使得程序员可以按比主存大得多的使得程序员可以按比主存大得多的空间来编制程序空间来编制程序,即按虚存空间编址即按虚存空间编址.19虚拟存贮器虚拟存贮器管理方式管理方式地址的映象和变换方法地址的映象和变换方法页面替换算法及其实现方法页面替换算法及其实现方法提高主存命中率的方法提高主存命中率的方法本节概述本节概述201.虚拟存贮器管理方式虚拟存贮器管理方式v地址变换：地址变换：在程序运行时，把虚地址变换成

13、主存实地址。在程序运行时，把虚地址变换成主存实地址。v根据根据地址映象和变换地址映象和变换地址映象和变换地址映象和变换方法方法不同，有三种虚拟存贮器：不同，有三种虚拟存贮器：段式虚拟存贮器、页式虚拟存贮器、段页式虚拟存贮器。段式虚拟存贮器、页式虚拟存贮器、段页式虚拟存贮器。虚存通过增设虚存通过增设地址映像表地址映像表地址映像表地址映像表机构来实现程序在贮存中的定位。机构来实现程序在贮存中的定位。这种定位技术是把程序分割成较小的段或页，用相应的映这种定位技术是把程序分割成较小的段或页，用相应的映像表机构来指明该程序的某段或某页是否装入主存。像表机构来指明该程序的某段或某页是否装入主存。21段式虚

14、拟存储贮器段式虚拟存储贮器地址映象方法：每个程序段都从地址映象方法：每个程序段都从0 0地址开始编址，长度可地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。长可短，可以在程序执行过程中动态改变程序段的长度。主程序(0段)1k1段2段3段0500020002000段号 段长 起址01k8k150016k22009k320030k08k9k16k30k程序空间主存储器段式虚拟存储器的地址映象段式虚拟存储器的地址映象220段表段表长度长度段表段表基址基址6As段名段名起始起始地址地址装入装入位位段长段长访问访问方式方式程序号程序号U段号段号S段内偏移段内偏移D多用户多用户虚地址

15、虚地址主存实地址主存实地址432101n-1As段表基址寄存器段表基址寄存器一个用户（一道作业）的段表一个用户（一道作业）的段表段式虚实地址转换段式虚实地址转换由用户程序号找到由用户程序号找到基址寄存器基址寄存器。从基址寄存器中读出从基址寄存器中读出段表的起始地址段表的起始地址。把起始地址与多用户虚地址中段号相加得到把起始地址与多用户虚地址中段号相加得到段表地址段表地址。把段表中给出的起始地址与段内偏移把段表中给出的起始地址与段内偏移D D相加就能得到相加就能得到主存主存实地址实地址。地地址址变变换换方方法法23n段式虚拟存贮器的主要优点：段式虚拟存贮器的主要优点：(1)(1)程序的模块化性能

16、好。程序的模块化性能好。(2)(2)便于程序和数据的共享。便于程序和数据的共享。(3)(3)便于实现信息保护。便于实现信息保护。n段式虚拟存贮器的主要缺点：段式虚拟存贮器的主要缺点：(1)(1)地址变换所花费的时间比较长，做两次加法运算。地址变换所花费的时间比较长，做两次加法运算。(2)(2)主存贮器的利用率往往比较低。主存贮器的利用率往往比较低。(3)(3)对辅存（磁盘存储器）的管理比较困难。对辅存（磁盘存储器）的管理比较困难。段式虚拟存贮器的主要优缺点段式虚拟存贮器的主要优缺点240 0.5K3K主存空间主存空间AB7K8K10KDC1K程序程序E2K2.5KF（a）依次调入）依次调入D、

17、E、F段段6.5K主存空间主存空间D0 0.5K3KE4K7K8KF10KABC（b）首先分配法）首先分配法主存空间主存空间AE5.5K0 0.5K3K7K8KD9K10KCB（c）最佳分配法）最佳分配法段式存贮分配算法段式存贮分配算法:首先分配法、最佳分配法首先分配法、最佳分配法25页式虚拟存贮器把虚拟地址空间划分成一个个固定大小页式虚拟存贮器把虚拟地址空间划分成一个个固定大小的块的块,每块称为一页每块称为一页,把主存贮器的地址空间也按虚拟地把主存贮器的地址空间也按虚拟地址空间同样的大小划分为页。址空间同样的大小划分为页。页是一种逻辑上的划分，它可以由系统软件任意指定。页是一种逻辑上的划分，

18、它可以由系统软件任意指定。n 虚拟地址空间中的页称为虚页虚拟地址空间中的页称为虚页n 主存地址空间中的页称为实页主存地址空间中的页称为实页页式虚拟存贮器页式虚拟存贮器26一个主存地址一个主存地址A A由两部分组成，由两部分组成，实页号实页号p p和和页内偏移页内偏移d d。一个虚地址一个虚地址AvAv由三部分组成，由三部分组成，程序号程序号U U、虚页号虚页号P P和和页内页内偏移偏移D D。用户号U虚页号P页内偏移D多用户虚拟地址Av的组成实页号p页内偏移d主存地址A的组成270页页1页页2页页3页页页号页号主存页号主存页号0123用户程序用户程序主存贮器主存贮器页式虚拟存贮器的地址映象页式

19、虚拟存贮器的地址映象虚页号虚页号实页号实页号页表页表28Pa装入装入修改修改主存页号主存页号标志标志程序号程序号U虚页号虚页号P页内偏移页内偏移D页内偏移页内偏移d2pPa页表基址页表基址页表页表实页号实页号p页式虚拟存贮器的地址变换页式虚拟存贮器的地址变换1)1)每个程序使用一个基址寄存器每个程序使用一个基址寄存器,通过程序号通过程序号U U可找到与这可找到与这个程序对应的基址寄存器，从中读出个程序对应的基址寄存器，从中读出页表起始地址。页表起始地址。2)2)访问这个页表地址，把得到的主存页号访问这个页表地址，把得到的主存页号p p与虚地址中的页与虚地址中的页内偏移内偏移直接拼接直接拼接直接

20、拼接直接拼接起来得到起来得到主存实地址主存实地址。29n页式虚拟存贮器的页式虚拟存贮器的主要优点：主要优点：(1)(1)主存贮器的利用率比较高。主存贮器的利用率比较高。(2)(2)页表相对比较简单。页表相对比较简单。(3)(3)地址变换的速度比较快。地址变换的速度比较快。(4)(4)对磁盘的管理比较容易。对磁盘的管理比较容易。n页式虚拟存贮器的主要缺点：页式虚拟存贮器的主要缺点：(1)(1)程序的模块化性能不好。程序的模块化性能不好。(2)(2)页表很长，需要占用很大的存储空间。例如：虚拟页表很长，需要占用很大的存储空间。例如：虚拟存储空间存储空间4GB4GB，页大小，页大小1KB1KB，则页

21、表的容量为，则页表的容量为4M4M字。字。30段页式虚拟存贮器段页式虚拟存贮器用户程序按段编写，每个程序段分成几个固定大小的页。用户程序按段编写，每个程序段分成几个固定大小的页。31n段页式虚拟存贮器的地址变换方法：段页式虚拟存贮器的地址变换方法：(1)(1)先查段表，得到该程序段的页表起始地址和页表长度；先查段表，得到该程序段的页表起始地址和页表长度；(2)(2)再查页表找到要访问的主存实页号；再查页表找到要访问的主存实页号；(3)(3)最后把实页号最后把实页号p p与页内偏移与页内偏移d d拼接得到主存的实地址。拼接得到主存的实地址。装入修改实页号标志用户号U段号S页内偏移页内偏移0/11

22、pA实页号p虚页号PAs装入1修改0/1页表地址AAs段页式虚拟存贮器的地址变换段页式虚拟存贮器的地址变换322.2.地址映像和变换地址映像和变换v地址映象地址映象:是指某一数据在主存中的地址与在虚存是指某一数据在主存中的地址与在虚存中的地址两者之间的对应关系。中的地址两者之间的对应关系。页面争用（实页冲突）页面争用（实页冲突）页面争用（实页冲突）页面争用（实页冲突）：两个以上的虚页想要进入主存中：两个以上的虚页想要进入主存中同一页面位置的现象。同一页面位置的现象。v映象映象方式的选择应考虑能否尽量减少实页冲突概率。方式的选择应考虑能否尽量减少实页冲突概率。33页面位置页面位置0ny-1ny-

23、1全相联映像全相联映像每道程序任何每道程序任何虚页可映像到虚页可映像到任何实页位置任何实页位置全相联映像：全相联映像：每道程序的任何虚页可以映像装入到任何实页位置每道程序的任何虚页可以映像装入到任何实页位置主存主存虚存虚存34实页号实页号其它标志其它标志程序号U页内偏移Dp虚页号P某用户某用户虚地址虚地址目录表（按内容访问的相联存储器）目录表（按内容访问的相联存储器）页内偏移d实页号p程序号程序号+用户虚页号用户虚页号U,P修改修改0/1主存实地址相联访问n地址变换过程：把某用户虚地址中地址变换过程：把某用户虚地址中U U与与P P拼接起来，相联拼接起来，相联访问目录表。读出主存实页号访问目录

24、表。读出主存实页号p p，把，把p p与多用户虚地址中的与多用户虚地址中的D D拼接得到主存实地址。如果相联访问失败，发出页面失拼接得到主存实地址。如果相联访问失败，发出页面失效请求。效请求。目录表目录表:用一个小容量高速存贮器存放页表用一个小容量高速存贮器存放页表35n目录表的主要优点：目录表的主要优点：与页表放在主存中相比，查表速度快。与页表放在主存中相比，查表速度快。不用设置装入位。不用设置装入位。n目录表的主要缺点：目录表的主要缺点：可扩展性比较差。可扩展性比较差。主存储器容量增加时，目录表的造价高，速度降低。主存储器容量增加时，目录表的造价高，速度降低。36对虚拟存储器来说对虚拟存储

25、器来说这个虚地址也仅是辅存的逻辑地址这个虚地址也仅是辅存的逻辑地址,辅存的实地址如下辅存的实地址如下外部地址变换外部地址变换虚地址虚 页 号 Nv页内地址NrNvdNd:磁盘机号 磁头号 柱面号 块 号块内地址虚拟存储器中还有虚拟地址到辅存实地址的转换虚拟存储器中还有虚拟地址到辅存实地址的转换.外页表外页表内页表内页表37 外部地址变换过程：外部地址变换过程：1.1.在操作系统中，把页面失效当作一种异常故障来处理。在操作系统中，把页面失效当作一种异常故障来处理。2.2.每个用户程序有一张外页表，虚拟地址空间中的每一页，每个用户程序有一张外页表，虚拟地址空间中的每一页，在外页表中都有对应的一个存

26、储字。在外页表中都有对应的一个存储字。3.3.每一个存储字除了磁盘存储器的地址之外，至少还包括每一个存储字除了磁盘存储器的地址之外，至少还包括一个装入位。一个装入位。装入磁盘实地址程序号页内偏移1虚页号外部地址变换（软件实现）磁盘号柱面号磁头号块号多用户虚地址外页表383.页面替换算法页面替换算法随机法随机法(Random,RAND(Random,RAND法法)先进先出法先进先出法(First-In First-Out,FIFO(First-In First-Out,FIFO法法)近期最少使用法近期最少使用法(Least Recently Used,LRU(Least Recently Use

27、d,LRU法法)最优替换算法最优替换算法(OPT OPTimal replacemant algorithm)(OPT OPTimal replacemant algorithm)39n页面替换发生时间：页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。使用的页面，以便腾出主存空间来存放新调入的页面。n评价页面替换算法好坏的标准：评价页面替换算法好坏的标准：一是命中率要高。

28、一是命中率要高。二是算法要容易实现。二是算法要容易实现。40随机算法随机算法(RAND Random algorithm)(RAND Random algorithm)：用随机数确定要替换的块。用随机数确定要替换的块。特点特点:算法简单，容易实现；算法简单，容易实现；未利用历史信息，未反映程序的局部性，命中率低。未利用历史信息，未反映程序的局部性，命中率低。先进先出算法先进先出算法(FIFO First-In First-Out)(FIFO First-In First-Out)：替换最早装入主存的页。替换最早装入主存的页。特点：特点：比较容易实现，利用了历史信息，没有反映程序的局部性。比较容

29、易实现，利用了历史信息，没有反映程序的局部性。最先调入主存的页面，很可能也是经常要使用的页面。最先调入主存的页面，很可能也是经常要使用的页面。41近期最少使用算法近期最少使用算法(LFU Least (LFU Least RecentlyRecently Used)Used)依据各块使用的情况，选择最近最少使用的块替换。依据各块使用的情况，选择最近最少使用的块替换。特点：既充分利用了历史信息，又反映了程序的局部性，实特点：既充分利用了历史信息，又反映了程序的局部性，实现起来非常困难。现起来非常困难。最优替换算法最优替换算法(OPT Optimal replacemant)(OPT Optima

30、l replacemant)：是一种理想化的算法。用来作为评价其它页面替换算法是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。好坏的标准。在虚拟存储器中，一般采用在虚拟存储器中，一般采用在虚拟存储器中，一般采用在虚拟存储器中，一般采用FIFOFIFOFIFOFIFO和和和和LRULRULRULRU两种算法两种算法两种算法两种算法42举例说明：举例说明：设有一道程序，有设有一道程序，有1 1至至5 5共五页，执行时的页地址流（即共五页，执行时的页地址流（即执行时依次用到的程序页页号）为：执行时依次用到的程序页页号）为：2 2，3 3，2 2，1 1，5 5，2 2，4 4，5 5，3

31、 3，2 2，5 5，2 2若分配给该道程序的主存有若分配给该道程序的主存有3 3页，分别采用页，分别采用FIFOFIFO和和LRULRU替换替换算法表示这算法表示这3 3页的使用和替换过程。页的使用和替换过程。43时间时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流页地址流 2 3 2 1 5 2 4 5 3 2 5 2先进先出先进先出 FIFO调调进进调调进进调调进进命命中中替替换换替替换换替替换换替替换换命命中中命命中中替替换换替替换换2232322*313*1551*25*24245*2*43342*34*53*52命命中中命命中中命命中中命中命中3次次近期最少近期

32、最少使用使用LRU2调调进进23调调进进232命命中中23*1调调进进2*15替替换换51*2命命中中25*4替替换换2*45命命中中54*3替替换换35*2替替换换3*25命命中中523*命命中中命命中中命命中中命命中中命命中中命命中中命中命中5次次244v存储单元替换时应注意防止出现颠簸现象，即调入一块存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。而将该块调入时又将上一块调出，即颠簸。例例2 2：一个循环程序，依次使用一个循环程序，依次使用P1P1，P

33、2P2，P3P3，P4P4四个页面，分四个页面，分配给这个程序的主存页面数为配给这个程序的主存页面数为3 3个。个。FIFOFIFO、LRULRU和和OPTOPT三种三种页面替换算法对主存页面的调度情况如下图所示。页面替换算法对主存页面的调度情况如下图所示。颠簸颠簸45在在FIFOFIFO和和LRULRU算法中，总是发生下次就要使用的页面本次被算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是替换出去的情况，这就是“颠簸颠簸”现象现象,说明命中率与页地说明命中率与页地说明命中率与页地说明命中率与页地址流有关。址流有关。址流有关。址流有关。46 例例3 3：对对于于一一个个全全相相联

34、联CacheCache，假假定定访访问问的的地地址址块块号号序序列列为为 1 1，2 2，3 3，4 4，1 1，2 2，5 5，1 1，2 2，3 3，4 4，5 5，在在FIFOFIFO替替换换方方式式下下，分分别别写写出出分分配配给给程程序序的的主主存存页页面面是是3 3页页和和4 4页的情况下，其队列的变化情况，并得出结论。页的情况下，其队列的变化情况，并得出结论。47时间时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流页地址流 1 2 3 4 1 2 5 1 2 3 4 53N=31121*242*313*44*2151*21*251*2552*35*435*34

35、命命中中命命中中命中命中3次次N=4131214412121*231*32231*52*353*14*55*21*252*命中命中2次次命命中中44444333命命中中命命中中结论：结论：FIFOFIFO算法不是堆栈型算法，主存页数增加，命中率反而下降。算法不是堆栈型算法，主存页数增加，命中率反而下降。484.堆栈型替换算法堆栈型替换算法n定义：定义：对任意一个程序的页地址流作两次主存页面数分配，分对任意一个程序的页地址流作两次主存页面数分配，分别分配别分配m m个主存页面和个主存页面和n n个主存页面，并且有个主存页面，并且有mnmn。如果。如果在任何时刻在任何时刻t t，主存页面数集合，主

36、存页面数集合BtBt都满足关系：都满足关系：Bt(m)Bt(m)Bt(n)Bt(n)，则这类算法称为堆栈型替换算法。，则这类算法称为堆栈型替换算法。n堆栈型算法的基本特点：堆栈型算法的基本特点：随着分配给程序的主存页面数增加，主存的命中率也提随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。高，至少不下降。495.虚拟存储器工作的全过程虚拟存储器工作的全过程506.提高虚拟存贮器等效访问速度的措施提高虚拟存贮器等效访问速度的措施n造成虚拟存储器速度降低的主要原因：造成虚拟存储器速度降低的主要原因：(1)(1)要访问主存储器须先查段表或页表。要访问主存储器须先查段表或页表。(2)(

37、2)可能需要多级页表。可能需要多级页表。快慢表快慢表快慢表快慢表n快表快表TLB(Translation Lookaside Buffer)TLB(Translation Lookaside Buffer)：采用一个小容量的高速的相关存储部件，用来存放当前最采用一个小容量的高速的相关存储部件，用来存放当前最经常用到的那一部分页表，采取按内容相联方式进行访问。经常用到的那一部分页表，采取按内容相联方式进行访问。n慢表：当快表中查不到时，从存放在主存储器中的慢慢表：当快表中查不到时，从存放在主存储器中的慢表中查找；表中查找；按地址访问，用软件实现。按地址访问，用软件实现。n快表与慢表也构成了一个两

38、级存储系统。快表与慢表也构成了一个两级存储系统。51经快表与慢表实现内部地址变换经快表与慢表实现内部地址变换快表的内容包括两部分即虚地址与实地址的对应关系。快表的内容包括两部分即虚地址与实地址的对应关系。52散列函数散列函数n目的：把相联访问变成按地址访问，从而加大快表容量。目的：把相联访问变成按地址访问，从而加大快表容量。n采用散列变换实现快表按地址访问采用散列变换实现快表按地址访问避免散列冲突：采用相等比较器。避免散列冲突：采用相等比较器。地址变换过程：相等比较与访问存储器同时进行。地址变换过程：相等比较与访问存储器同时进行。53经散列实现快表经散列实现快表实页号用户号U页内偏移Dp虚页号

39、P多用户虚地址按地址访问的快表页内偏移d实页号p多用户虚页号Pv主存实地址散列变换（硬件实现）相等比较多用户虚页号查慢表快表地址Ah快表命中n散列（散列（HashingHashing）函数：）函数：AhAhH(Pv)H(Pv)54(1)(1)程序执行过程中的页地址流分布情况。程序执行过程中的页地址流分布情况。(2)(2)所采用的页面替换算法。所采用的页面替换算法。(3)(3)页面大小。页面大小。(4)(4)主存储器的容量。主存储器的容量。(5)(5)所采用的页面调度算法。所采用的页面调度算法。以下，对后三个因素进行分析。以下，对后三个因素进行分析。7.7.影响主存命中率的主要因素：影响主存命中

40、率的主要因素：影响主存命中率的主要因素：影响主存命中率的主要因素：55n页面大小为某个值时，命中率达到最大。页面大小为某个值时，命中率达到最大。页面大小与命中率的关系页面大小与命中率的关系n当页面大小增大时，造成的浪费也要增加。当页面大小增大时，造成的浪费也要增加。n当页面大小减小时，页表和页面表在主存储器当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。中所占的比例将增加。页面大小 SP命中率 H1S2SS:S:分配给某道程序的贮存容量分配给某道程序的贮存容量分配给某道程序的贮存容量分配给某道程序的贮存容量56主存容量与命中率的关系主存容量与命中率的关系n主存命中率主存命中率H H

41、随着分配给该程序的主存容量随着分配给该程序的主存容量S S的增的增加而单调上升。加而单调上升。n在在S S比较小的时候，比较小的时候，H H提高得非常快。随提高得非常快。随着着S S的逐渐增加，的逐渐增加，H H提高的速度逐渐降提高的速度逐渐降低。当低。当S S增加到某一增加到某一个值之后，个值之后，H H几乎不几乎不再提高。再提高。命中率 H主存容量S1.057页面调度方式与命中率的关系页面调度方式与命中率的关系n请求式：请求式：当使用到的时候，再调入主存当使用到的时候，再调入主存。n预取式：预取式：在程序重新开始运行之前，把上次停止运在程序重新开始运行之前，把上次停止运行前一段时间内用到的

42、页面先调入到主存储器，行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。然后才开始运行程序。可以避免在程序开始运行时，频繁发生页可以避免在程序开始运行时，频繁发生页可以避免在程序开始运行时，频繁发生页可以避免在程序开始运行时，频繁发生页面失效的情况。面失效的情况。面失效的情况。面失效的情况。如果调入的页面用不上，浪费了调入的时如果调入的页面用不上，浪费了调入的时间，占用了主存资源。间，占用了主存资源。584.3 4.3 高速缓冲存贮器（高速缓冲存贮器（CacheCache）基本工作原理基本工作原理地址映象与变换方法地址映象与变换方法59n n1 1 基本工作原理基本工作原理CPUC

43、PU速度与主存速度差异速度与主存速度差异。CacheCache全部用硬件调度全部用硬件调度,对所有程序员都是透明的。对所有程序员都是透明的。从从CPUCPU看，速度是看，速度是CACHECACHE的，容量是主存的。的，容量是主存的。60CacheCache存贮器基本结构存贮器基本结构 CacheCache存储存储存储存储体体体体 地址转换部地址转换部地址转换部地址转换部件件件件 替换部替换部替换部替换部件件件件 缓存地址缓存地址主主存存Cache 块号块号块内地址块内地址 MS-Cache地址变换地址变换 块号块号块内地址块内地址 Cache替换替换部件部件 ：主存地址主存地址替换块替换块装入

44、块装入块不命中不命中数据或指令数据或指令命中命中612 Cache-主存地址映象与变换方法主存地址映象与变换方法n地址映象：地址映象：把存放在主存中的程序按照某种规则装入到把存放在主存中的程序按照某种规则装入到CacheCache中，并中，并建立主存地址与建立主存地址与CacheCache地址之间的对应关系。地址之间的对应关系。n地址变换：地址变换：当程序已经装入到当程序已经装入到CacheCache之后，在实际运行过程中，把主之后，在实际运行过程中，把主存地址变换成存地址变换成CacheCache地址。地址。n在选取地址映象方法要考虑的主要因素：在选取地址映象方法要考虑的主要因素：地址变换的

45、硬件容易实现；地址变换的硬件容易实现；地址变换的速度要快；地址变换的速度要快；Cache空间利用率要高；空间利用率要高；发生块冲突的概率要小。发生块冲突的概率要小。62全相联映象全相联映象全相联：主存中的全相联：主存中的任一块可以被映像任一块可以被映像到到Cache中的任意中的任意一个位置。一个位置。CacheCache常包含几百个块，主存常包含几百万个块。常包含几百个块，主存常包含几百万个块。优点：命中率较高，优点：命中率较高，CacheCache的存储空间利用率高；的存储空间利用率高；缺点：线路复杂，成本高，速度低。缺点：线路复杂，成本高，速度低。63直接映象：直接映象：1.1.主存与缓存

46、分成同样大小的块；主存与缓存分成同样大小的块；2.2.主主存存容容量量应应是是缓缓存存容容量量的的整整数数倍倍，将将主主存存空空间间按按缓缓存存的的容量分成区，主存中每一区的块数与缓存的总块数相等；容量分成区，主存中每一区的块数与缓存的总块数相等；3.3.主存中某区的一块存入缓存时只能存入缓存中块号相同主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。的位置。直接相联的地址映象规则直接相联的地址映象规则直接相联的地址映象规则直接相联的地址映象规则 直接映象公式直接映象公式直接映象公式直接映象公式：b=A mod C/Bb=A mod C/Bb b：Cache Cache的块号的块号A A

47、：主存的块号：主存的块号C/BC/B：CacheCache的块数的块数64(循环分配循环分配)直接映象：主存中直接映象：主存中的每一块只能被放的每一块只能被放置到置到Cache中唯一中唯一的一个位置。的一个位置。优点：优点：线路线路简单；简单；缺点：命中缺点：命中率低。率低。65组相联映象方式组相联映象方式 组相联的映象规则组相联的映象规则组相联的映象规则组相联的映象规则 1.1.主存与缓存分成相同大小的块主存与缓存分成相同大小的块;2.2.主主存存容容量量是是缓缓存存容容量量的的整整数数倍倍，将将主主存存空空间间按按缓缓存存的的大大小分成区，主存中每一区的组数与缓存的组数相同。小分成区，主存

48、中每一区的组数与缓存的组数相同。3.3.组间直接相联；组内全相联。组间直接相联；组内全相联。66组相联：主存中的组相联：主存中的每一块可以被放置每一块可以被放置到到Cache中唯一的中唯一的一个组中的任何一一个组中的任何一个位置。个位置。67组相联是直接映象和全相联的一种折衷组相联是直接映象和全相联的一种折衷组组间间直直接接相相联联；组内全相联。组内全相联。68n 组相联映象方式的优点：组相联映象方式的优点：块的冲突概率比较低。块的冲突概率比较低。块的利用率大幅度提高。块的利用率大幅度提高。块失效率明显降低。块失效率明显降低。n 组相联映象方式的缺点：组相联映象方式的缺点：实现难度和造价要比直

49、接映象方式高。实现难度和造价要比直接映象方式高。69段相联段相联映象方式映象方式 段相联映象方式也是全相联与直接相联的一个折段相联映象方式也是全相联与直接相联的一个折中方案。中方案。70由于多个用户对主存的共享由于多个用户对主存的共享,就有多个用户程序和系统软就有多个用户程序和系统软件存于主存中件存于主存中.要防止由于一个用户程序出错而破坏其他用户的程序和系要防止由于一个用户程序出错而破坏其他用户的程序和系统软件统软件,还要防止一个用户程序不合法地访问不是分配给它还要防止一个用户程序不合法地访问不是分配给它的主存区域的主存区域.为此为此,系统应提供存贮保护系统应提供存贮保护.4.5 主存保护主

50、存保护存贮保护主要包括两个方面存贮保护主要包括两个方面:存贮区域保护存贮区域保护存贮区域保护存贮区域保护 非虚拟存储区域保护非虚拟存储区域保护 虚拟存储区域保护虚拟存储区域保护 访问方式保护访问方式保护访问方式保护访问方式保护71非虚拟存储区域保护非虚拟存储区域保护对于不是虚拟存储器的主存系统可采用界限寄存器方式。对于不是虚拟存储器的主存系统可采用界限寄存器方式。由系统软件经特权指令设置上由系统软件经特权指令设置上,下界寄存器为每个程下界寄存器为每个程序划定存储区域序划定存储区域,禁止越界访问禁止越界访问.由于用户程序不能改变上由于用户程序不能改变上,下界的值下界的值,所以它如果出现所以它如果