第3章存储系统设计fppt课件.ppt

《第3章存储系统设计fppt课件.ppt》由会员分享，可在线阅读，更多相关《第3章存储系统设计fppt课件.ppt（236页珍藏版）》请在三一办公上搜索。

1、第3章 存储系统设计,3.1 存储系统原理 3.2 交叉访问存储器 3.3 页式虚拟存储器 3.4 Cache存储器 习题3,3.1 存储系统原理,3.1.1 基本概念 从用户的角度来看，存储器的三个主要指标是：容量、速度和价格。用户对存储器的要求是“容量大、速度快、价格低”，显然，这三个要求是相互矛盾的，因为很明显存储器的速度越快，价格就越高；存储器的容量越大，速度就越慢。下面我们来具体解释一下这三个概念。,存储器容量SM=Wlm。其中W为单个存储体的字长，l为单个存储体的字数，m为并行工作的存储体的个数。也就是说，存储器的容量与单个存储体的字长、单个存储体的字数和并行工作的存储体的个数成正

2、比。,存储器的速度可以用访问时间TA、存储周期TM或频宽Bm来描述。Bm是存储器被连续访问时，可以提供的数据传送速率，通常用每秒传送信息的位数（或字节数）来衡量。单体的Bm=W/TM。m个存储体并行工作时可达到的最大频宽Bm=Wm/TM。以上指的都是理想情况下，存储器所能达到的最大频宽。由于存储器不一定总能连续满负荷地工作，所以，实际频宽往往要低于最大频宽。,为了提高CPU的访存速度，有以下二种方法： (1)在组成上引入并行和重叠技术，构成并行主存系统。在保持每位价格基本不变的情况下，能使主存的频宽得到较大的提高。如单体多字存储器、多体交叉存储器。 (2)改进存储器的系统结构，发展存储体系（或

3、称存储系统）。如采用Cache-主存-辅存存储层次的存储器。,所谓存储体系，是指计算机系统的存储器部分由多种不同的存储器构成，由操作系统和硬件技术来完成程序的定位，使之成为一个完整的整体。由于它由多级存储器构成，故又称之为存储层次。 存储器价格包含了存储单元本身以及为实现存储器操作所必须的外围电路的价格。,3.1.2 多级存储层次 为实现用户“容量大、速度快、价格低”的要求，仅用单一的一种存储器很难达到这一目标，较为理想的方法就是采用存储层次，用多种存储器构成存储器的层次结构。 图3.1是多级存储层次的示意图。其中，M1，M2，Mn为用不同技术实现的存储器。最靠近CPU的M1速度最快，容量最小

4、，每位价格最高；而离CPU最远的Mn则相反，速度最慢，容量最大，每位价格最低。对于其中任何相邻的两级来说，靠近CPU的存储器总是容量小一些，速度快一些，价格高一些。,图3.1 多级存储层次,若设ci、TAi、Smi分别表示Mi的每位价格、访问时间和存储容量，则多级存储层次中任何相邻二级之间存在以下关系： cici+1 TA iTA i+1 SM iSM i+1 多级存储层次设计追求的目标是：从CPU看，是一个整体，该存储系统具有接近最高层M1的速度、最低层Mn容量，而每位价格却是接近Mn的。,为了使存储体系能有效地工作，当CPU要用到某个地址的内容时，总是希望它尽可能已经在速度较快的M1中准备

5、好，这就要求未来被访问信息的地址在某种程度上可以预知（判）。因此，能否预知（判）出下步所要访问的程序块，对存储体系的构成是非常重要的。而这种预判的可能性是基于计算机程序的一个特性，即程序的局部性。局部性原理指出，绝大多数程序访问的指令和数据都是相对簇聚的，它包括时间上的局部性和空间上的局部性。,时间局部性是指在最近的未来要用到的信息很可能是现在正在使用的信息，这主要是程序循环造成的，即循环中的语句要被重复的执行。 空间局部性是指在最近的未来要用到的信息很可能与现在正在使用的信息，在程序空间上是相邻或相近的，这主要是由于指令通常是顺序执行的，以及数据一般是以向量、阵列、树形、表格等形式簇聚地存储

6、所致。,根据程序的局部性，存储层次的构成和管理主要采用以下两种方法相结合： (1)Mi级一般只需存放Mi+1级中近期使用过的块和页（根据时间局部性）； (2)在从Mi+1级取所要访问的字送到Mi级时，一并把该字所在的块或页整个取出来（根据空间局部性），以增大CPU在访问Mi级时的命中率。,3.1.3 存储系统的性能参数 这里以二级存储层次为例来分析其性能，二级存储层次结构如图3.2所示。存储层次主要采用三个性能参数：平均位价格c、命中率H和等效访问时间TA 。,图3.2 二级存储层次,设ci、TAi、SMi分别表示Mi的平均位价格、访问时间和存储容量。 1. 平均位价格c,显然，当SM1 SM

7、2时，cc2。,2. 命中率H 命中率为CPU访问存储系统时，在M1中找到所需信息的概率。,其中，R1为逻辑地址流的信息能在M1中访问到的次数，R2为逻辑地址流的信息当时在M2中还未调到M1的次数。,3. 等效访问时间TA TA =HTA1 +（1-H）TA2 我们总希望TA越接近于TA1为好，也就是说存储层次的访问效率e=TA1/TA，越接近于1越好。 设CPU对存储层次相邻两级的访问时间比r=TA2/TA1，则，,由上式可得，对于不同的访问时间比r、命中率H与访问效率e的关系如图3.3所示。由图可见，要使访问效率e接近于1，在r值越大时，就要求命中率H越高。,图3.3 对于不同的r，命中率

8、H与访问效率e的关系,前面介绍了二级存储体系的性能参数，下面我们再来讨论更为复杂的存储系统。 (1)假设存储体系由n级存储器构成，如图3.1所示。设TAi、Ri、Hi分别表示Mi的访问时间、访问次数和命中率，则有：,那么等效访问时间TAi则为： TAi=H1TA1+(1-H1)H2TA2+(1-H1)(1-H2)H3TA3+ +(1-H1)(1-H2)(1-Hn-1) TAn (2)假设Cache存储器分为指令体（I-Cache）和数据体（D-Cache），如图3.4所示。,图3.4 Cache分为指令体和数据体的二级存储体系,设指令Cache和数据Cache的访问时间均为tc，主存的访问时间

9、为tm，指令Cache的命中率为hi，数据Cache的命中率为hd，CPU访存取指的比例为fi，则存储体系的等效访问时间为： TA= fi(hitc+(1- hi)tm)+(1- fi)( hdtc+(1- hd) tm),例3.1 某机是由高速缓存与主存组成的二级存储系统，高速缓存存取周期tc=50ns，主存存取周期tm=400ns。访问Cache的命中率为0.96。 (1)系统等效的存取周期TA为多少？ (2)如果将高速缓存分为指令体与数据体，使等效存取周期减小了10%。在所有的访问操作中有20%是访问指令体，而访指令体的命中率仍为0.96（假设不考虑写操作一致性的问题），问数据体的访问命

10、中率应是多少？,解：(1)系统等效的存取周期为：TA =htc+(1-h)tm =0.96*50+(1-0.96)*400 =64ns,(2)设改进后的D-Cache的命中率为hd，按公式 TA= fi(hitc+(1- hi)tm)+(1- fi)( hdtc+(1- hd) tm) 64*(1-10%)=0.2(0.96*50+(1-0.96)*400)+(1-0.2)(hd*50+(1-hd)*400) 280hd=275.2 hd0.983,3.2 交叉访问存储器,3.2.1 主存系统的类型 1. 主存系统的类型 根据主存中存储体的个数，以及CPU访问主存一次所能读出的信息的位数，可以

11、将主存系统分为以下四种类型：,(1)单体单字存储器，即存储器只有一个存储体，而且存储体的宽度为一个字。如图3.5所示是一个字长为W位的单体主存，一次可以访问一个存储器字，所以主存最大频宽Bm=W/TM。假设，此存储器字长W与CPU所要访问的字（数据字或指令字，简称CPU字）的字长W相同，则CPU从主存获得信息的速率就为W/ TM。我们称这种主存是单体单字存储器。,(2)单体多字存储器，即存储器只有一个存储体，但存储体的总线宽度较大，可以是多个字，如图3.6所示。若要想提高主存频宽Bm，使之与CPU速度匹配，显然可以想到，在同样的器件条件（即同样的TM）下，只有设法提高存储器的字长W才行。例如，

12、改用图3.6的方式组成，这样，主存在一个存储周期内就可以读出4个CPU字，相当于CPU从主存中获得信息的最大速率提高到原来的4倍，即Bm=4W/TM。我们称这种主存为单体多字存储器。,图3.5 单体单字存储器,图3.6 单体多字（m=4）存储器,(3)多体单字交叉存取的存储器。如：多体交叉存储器，因为每个存储体都是一个CPU字的宽度。 (4)多体多字交叉存储器。它将多分体并行存取与单体多字相结合。 我们将能并行读出多个CPU字的单体多字、多体单字交叉、多体多字交叉存取的主存系统称为并行主存系统。,2. 单体多字方式与多体单字交叉方式的区别 (1)单体多字方式要求可并行读出的m个字必须是地址顺序

13、排列且处于同一主存单元。 (2)而主存采用多体单字方式组成，即采用m个存储体交叉编址，多个存储体并行进行存取操作，每个存储体的宽度一般是一个字的宽度。其所花费的器件和总价格并不比采用单体多字方式的多多少，但其实际带宽却可以比较高。这是因为多体单字方式只要m个地址不发生分体冲突（即没有发生两个以上地址同属一个分体），即使地址之间不是顺序的，仍可并行读出，使实际带宽提高成单体单字的m倍。 基本的多体交叉方法有两种，即高位交叉访问存储器和低位交叉访问存储器。,3.2.2 高位交叉访问存储器 图3.7是高位交叉的四体交叉存储器结构示意图。如果主存空间为N=2n字，那么访问该存储器的地址为n位。若存储器

14、由M=2m个存储体构成，用高m位地址来选择不同的存储体，低n-m位为体内的地址。当高m位不相同时，便可以访问不同的存储体，即当多个处理机发出的访存地址高位不相同时，可对共享存储器内的不同存储体进行同时存取。当多个处理机发出的访存地址高位相同时，即访存同一存储体时，就不能并行操作了，我们称之为存储器的分体冲突。高位交叉访问存储器一般适合于共享存储器的多机系统。,图3.7 高位交叉的四体交叉存储器结构示意图,3.2.3 低位交叉访问存储器 图3.8是低位交叉的四体交叉存储器结构示意图。 如果模块的字是与数据总线等宽（W位）。若模块存取一个字的存储周期是，由m个子周期（要大于或等于总线传送周期）组成

15、，即=m，并使用m个模块来交叉存取，则成块存取可按间隔流水进行，即每经时间延迟后即启动下一模块。这样，连续读m个字所需时间为+(m-1),而顺序组织方式却要m时间，显然加快了成块存取速度。模四多体交叉存取存储器的流水存取示意图如图3.9所示。,如果主存空间为N=2n字，那么访问该存储器的地址为n 位。若存储器由M=2m个存储体构成，用低m位地址来选择不同的存储体，高n-m位为体内地址。当低m位不相同时，便可以访问不同的存储体，即当处理机发出的访存地址访问不同的存储体时（地址不一定连续），可对存储器内的不同存储体进行并行存取（这里的并行性指的是并发性）。当处理机访存同一存储体时，就不能并行操作了

16、。低位交叉访问存储器一般适合于单处理机内的高速数据存取及带Cache的主存。,图3.8 低位交叉的四体交叉存储器结构示意图,图3.9 模四多体交叉存取存储器的流水存取示意图,在最好的情况下，即一个模m的多体交叉访问存储器在不发生分配冲突时的带宽是单体带宽的m倍。,3.2.4 拓宽存储器带宽的方法 前面讲过，并行主存系统可达到的最大频宽Bm=Wm/TM ,由这个式子可以看出： 提高模m的值，是能提高主存系统的频宽的，但主存频宽并不是随m值增大而线性提高，也就是说其实际效率并不像所希望的那么高。例如，CDC-6600、7600采用模32交叉实际频宽只是理想频宽的三分之一都不到，这是因为：,(1)工

17、程实现上由于模m越高，存储器数据总线越长，总线上并联的负载越重，有时还不得不增加门的级数，这些都会使传输延迟增加； (2)是系统效率问题。对模m交叉，如果都是顺序的取指令，效率是可以提高到m倍的，但实际上程序中指令不总是顺序执行的，一旦出现转移，效率就会下降，转移的频度越高，这种并行主存系统的效率下降就越大，而数据的顺序性比指令差，实际的频宽可能还要低一些。,图3.10 m个分体并行存取B=f()曲线,从图3.10中不难看出，如果转移概率0.3时，m=4、8、16的B的差别不大，即在这种情况下，模m的取值再大，对系统效率也并没有带来多大的好处；而在0.1时，m值的大小对B的改进则会有显著的影响

18、。为了降低转移概率，就要求在程序中尽量少使用转移指令。,如果从最不利的情况考虑，假设让所有的申请（包括指令和数据）都是完全随机性的，Hellerman用单服务、先来先服务排队论模型进行模拟，估算出B=m0.56 ,即得出随m的提高，主存频宽只是以近似平方根的关系得到改善。 因为程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大m来提高并行主存系统的带宽是有限的，而且性能价格比还会随m的增大而下降。,在有些系统中，主存与处理机通过总线相连，主存的宽度受总线宽度的限制不能做的太宽，为提高数据传输的速度，这些系统中广泛采用突发式(burst mode)传送数据，即在一个总线周期中以数据块传

19、送的方式将数据块从主存调入Cache。,3.3 页式虚拟存储器,3.3.1 虚拟存储器的工作原理 在1961年，英国曼彻斯特大学的Kilburn等人提出了虚拟存储器的概念。经过20世纪60年代初到70年代初的发展完善，虚拟存储器已广泛应用于大中型计算机系统。目前几乎所有的计算机都采用了虚拟存储系统。,虚拟存储器是“主存-辅存”层次进一步发展的结果。它由价格较贵、速度较快、容量较小的主存储器M1和一个价格低廉、速度较慢、容量很大的辅助存储器M2（通常是硬盘）组成，在系统软件和辅助硬件的管理下，就像一个单一的、可直接访问的大容量主存储器。由于中央处理机只能执行已装入主存的那一部分程序块，同时，为了

20、提高主存空间的利用率，应及时释放出主存中现已不用的那部分空间，以便装入别的程序块。,这样，随着程序的运行，程序的各个部分就会在主存和辅存之间调进调出。当辅存中的程序调入主存时，必须进行程序在主存中的定位。为了使应用程序员对其程序不用修改就可以在虚拟存储器上运行，即应用程序员不用考虑如何把程序地址映象和变换成实际主存的物理地址，这种程序的定位应当是由系统提供的定位机构来自动完成，从而使之对应用程序员透明。应用程序员可以用机器指令的地址码对整个程序统一编址，就如同应用程序员具有对应于这个地址码宽度的存储空间（称为程序空间）一样，而不必考虑实际主存空间的大小。,虚拟存储器可以分为两类：页式和段式。本

21、节我们主要学习页式虚拟存储器。在页式虚拟存储器中通过把主存空间和程序空间都机械等分成固定大小的页（页面大小随机器而定，一般为512B到几KB），按页顺序编号，用相应的映象表机构来指明该程序的某页是否已经装入主存。若已经装入主存，则应同时指明其在主存中所处的位置；如果未装入主存，则去辅存中调页，并建立起程序空间和实存空间的地址映象关系。这样，程序执行时通过查映象表将程序（虚拟）地址变换成实际主存（物理）地址再访问主存。,此存储系统具有主存的速度和辅存的容量，提高了存储器系统的性能价格比。CPU直接访问主存，主存与辅存之间的信息交换由操作系统和硬件来完成，这种把辅存看作是主存的一部分，以扩大主存容

22、量的技术，称之为虚拟技术。用虚拟技术设计的存储器，称为虚拟存储器。,这些主存与辅存之间实际存在的操作和辅助软、硬件，对应用程序设计者来讲是透明的。但虚拟存储器对系统程序员来讲基本上是不透明的，只是某些部分（如虚拟地址到主存地址的变换）由于采用硬件实现才是透明的。虚拟地址又称逻辑地址，是指访问虚拟空间的地址。由于指令中给出的地址码是按虚存空间来统一编址的，因此指令的地址码实际上是虚拟地址。而物理地址是指访问主存空间的地址。,3.3.2 虚拟存储器的地址映象与变换 1. 虚拟地址到物理地址之间的映象与变换 地址映象是指按某种规则（算法）建立多用户虚拟地址Ns与物理地址np之间的对应关系。在页式虚拟

23、中，由于多用户虚拟地址中的页内地址与物理地址中的页内地址相同，其地址映象主要是多用户虚页号Nv与实存（物理）页号nv之间的对应关系。 在页式管理方式中，虚拟地址和物理地址的格式如图3.11所示。,每道程序都有自己的内页表，内页表的长度等于程序的页数，在程序装入和运行过程中，页表基址寄存器和页表的内容全部由存储层次来完成置定和修改（即由硬件来完成），对用户完全透明。内页表一般都是按照虚存页号的顺序进行排列，所以内页表中的虚存页号可省略，而主存页号就是实页号。,图3.11 虚拟地址、物理地址和内页表的格式,地址变换是指程序按照某种映象关系装入实存后，在执行程序时，多用户虚拟地址Ns如何变换成对应的

24、实存地址np。对页式虚拟而言，其核心是如何将多用户虚页号Nv变换成实存（物理）页号nv，很显然地址变换就是利用了地址映象关系，地址变换与地址映象之间密切相关。,由于是把大的虚存空间压缩到小的主存空间去，主存中的每一个页面位置必须能与多个虚页相对应，能对应多少个虚页与采用的映象方式有关。这就不可避免地会发生两个以上的虚页想要进入主存中同一个页面位置的现象，这种现象被称为发生了页面争用或实页冲突。一旦发生实页冲突，只能先装入其中的一个虚页，待其退出主存之后方可再装入，这当然会使执行效率下降。因此，映象方式的选择主要应考虑能否尽量减少实页冲突概率，其次也要考虑辅助硬件是否少、成本低，实现是否方便，以

25、及地址变换的速度是否快等。,由于虚存空间远远大于实存空间，页式虚拟存储器一般采用实页冲突概率最低的全相联映象，但全相联映象方式的地址映象需要内页表，辅助硬件较多，成本较高，地址映象与地址变换由存储层次统一来完成。页式管理的全相联定位映象机构及其地址的变换过程如图3.12所示，由于它采用页表作为地址映象表，故又称之为页表法。由用户标志u指明该道程序使用哪个页表基址寄存器，从而可以找到该道程序在主存中的起点x。再根据x+NV找到主存中的一行，从而获得实页号nv，然后由实页号nv和页内位移nr拼接成实地址。,在页表法中，由于每一个虚页都要占用页表中的一行，在N道程序的页表中总共有N2Nv行，装入位为

26、1的最多只有2nv行。由于N2Nv2nv ，使得页表中绝大部分行中实页号字段及其它字段都成无用的了，这会大大降低页表的利用率。,为了提高页表的空间利用率，有如下方法： (1)采用修改后的内页表法：它将页表中装入位为0的行用实页号字段存放该程序此虚页在辅存中的实地址，以便调页时实现用户虚页号到辅存实地址的变换。,图3.12 页式管理的全相联定位映象机构及其地址的变换过程,(2)采用相联目录表法，又称目录表法。把页表压缩成只存放已装入主存的那些虚页与实页位置的对应关系，并采用相联存储器存放两者对应关系的表。具体如图3.13所示。相联存储器在一个存储周期中将给定的Nv同时与目录表全部2nv个单元对应

27、的虚页号字段内容进行比较，进行相联查找。如有相符的，即相联查找到时，表示此虚页已被装入主存，该单元中存放的实页号nv就是此虚页所存放的实页位置，将其读出，拼接上Nr就可形成访存实地址np，该单元其它字段内容可供访问方式保护或其它工作用。,如无相符的，即相联查找不到时，就表示此虚页未装入主存，发页面失效故障（异常）信息，请求从辅存中调页。 采用修改后的内页表存放在主存中，其行数可能大到要求采用多级表，使查表速度变慢；而采用相联目录表法，由于目录表存放在专门可按内容访问的相联存储器中，尽管目录表的行数为2nv，但这个值也是很大的，采用2nv行的相联存储器，不仅造价高，而且查表速度又难以做得很快。所

28、以虚拟存储器一般不直接采用内页表法和相联目录表法，而是内页表法与快表（按地址访问的高速RAM）的结合。,2. 虚拟地址到辅存实地址之间的映象与变换 对页面失效如何处理是设计好页式虚拟存储器的关键之一。页面失效是指当CPU访问主存中N道程序的某道程序的虚页不在主存时的情况。当发生页面失效时，必须由地址映象和变换机构将虚拟地址变换成辅存实地址（一般由软件实现），再由操作系统或I/O处理机将要访问的虚页从辅存调入主存，必要时可能会进行页面的替换。,图3.13 目录表法,要想把该道程序的虚页调入主存，必须给出该页在辅存中的实际地址。以磁盘为例，辅存的实地址格式为： Nvd,为了提高调页效率，辅存一般是

29、按信息块编址的，而且让块的大小与页面的大小相等。 虚拟地址到辅存地址之间的映象一般采用外页表，外页表的内容是把程序装入辅存时由操作系统建立的。每个用户的外页表也是2Nv项（行），每行中用装入位表示该信息块是否已由海量存储器（如磁带）装入磁盘。当装入位为“1”时，辅存实地址字段内容有效，就是该信息块（页面）在辅存（磁盘）中的实际位置。其地址变换过程如图3.14所示。,由于虚拟存储器的页面失效率一般低于1%，调用外页表进行虚地址到辅存地址变换的机会很少，加上访问辅存调页需机械动作，速度本来就慢，因此外页表通常存在辅存中。若采用修改后的内页表，当某道程序初始运行时，才把外页表的内容转录到已建立内页表

30、的实页号地址字段中，这就是前述当内页表装入位为0时，可以让实页号地址字段改放该虚页在辅存中的实地址的原因。 一旦发生页面失效，不是让处理机空等着调页，而是切换到其它已准备就绪的任务（进程）继续运行，与此同时由操作系统或I/O处理机去完成调页。,3.3.3 页面替换算法及其实现 1. 页面替换算法 通常虚存空间比主存空间大的多，必然会出现主存页面位置已被全部占用后，又发生页面失效的情况，这时将辅存的一页调入主存就会发生实页冲突。选择主存中哪一个页作为被替换页，就是替换算法要解决的问题。,图3.14 虚地址到辅存地址的变换,替换算法的确定主要考虑以下两个方面： (1)有高的主存命中率； (2)算法

31、便于实现，辅助软硬件成本较低。 常见的替换算法有：随机算法（RAND）、先进先出算法（FIFO）、近期最少使用算法（LRU）、最久未用过算法（或称最不经常使用算法LFU）等等。 RAND算法用软的或硬的随机数产生器来形成主存中要被替换页的页号。这种算法简单，易于实现，但没有利用主存使用情况的“历史”信息，反映不了程序的局部性，使主存命中率很低，因此很少采用。,FIFO算法选择最早装入主存的页作为被替换的页。为了实现这种算法，只需在操作系统为实现主存管理而设置的主存页面表中给每个实页配置一个计数器字段（参见图3.15，需将其中的使用位字段改成计数器字段）即可。每当一页装入主存时，让该页的计数器清

32、零，其它已装入主存的那些页的计数器都加“1”。需要替换时，找出计数器值最大的页，它就是最先进入主存而现在准备替换掉的页。这种算法虽然利用了主存使用情况的“历史”信息，但不一定能正确反映出程序的局部性。因为最先进入的页很可能正是现在经常要用到的页。,LRU算法选择近期最少访问的页作为被替换的页。这种算法能比较正确地反映程序的局部性。因为当前最少使用的页，一般来说，未来也将很少被访问。但是完全按此算法来实现比较困难，需要为每个实页都配置一个字长很长的计数器字段才行。所以，一般采用它的变形LFU算法，即把近期最久没被访问过的页作为被替换的页。这样，实现起来比较方便。,对于先进先出算法（FIFO）和近

33、期最少使用算法（LRU），操作系统为实现主存管理设置有专门的主存页面表，主存页面表对主存而言，整个主存只有一个，主存页面存于主存，其结构图如图3.15所示，其中每一行用来记录主存中各页的使用情况。由于主存页号（实页号）是顺序的，所以该字段可以略去，用相对于主存页面表起点的相对行数来表示。占用位表示该主存页面是否已被占用。占用位为“0”，表示该页是空的，未被占用。占用位为“1”，表示该页已被占用。至于被哪个程序的哪个段、哪个页占用，则由程序号和段页号字段表示。,为实现近期最久未使用的替换算法，只需简单地给表中每个主存页面配一个“使用位”标志即可。开始时，所有页的使用位全为“0”。只要某个实页的任

34、何单元被访问过，就由硬件自动地置该页使用位为“1”。由于采用全相联映象，调入页可进入对应于主存页面表中任何占用位为“0”的实页位置，一旦装到主存某页位置上时，就置该实页的占用位为“1”。只有当所有占用位都是“1”，且又发生页面失效时才有页面替换问题，这时就要用到使用位，只需替换使用位为“0”的页即可。,图3.15 主存页面表,显然，任何时候使用位都不能出现全为“1”，否则，再发生页面失效时就无法确定究竟哪页该被替换。一种办法是一旦使用位进入全“1”，就立即由硬件强制全部使用位都为“0”。另一种办法是让它定期地置全部使用位为“0”。为此，可给每个实页配一个“未用过计数器”Hs（或称为历史位），定

35、期地每隔t（例如每隔几毫秒、几秒或几分钟）扫视所有使用位，对使用位为“0”的页，则加“1”Hs，并让使用位继续保持为“0”；而对使用位为“1”的页，则置“0”Hs，同时置“0”使用位。这样，扫视结束时，所有的使用位都成了“0”，又开始一个新的t期，但原有使用位的状态都已被记录到各自的Hs中。,因此，Hs值最大，说明该页最久未被用过，应成为被替换的页。可以看出，使用位只反映一个t期内的页面使用情况，Hs则反映了多个t期内的页面使用情况，而且这种方法比近期最少使用法的那种计数器所耗费的辅助硬件要少得多。由于页面失效后调页时间较长，加上程序换道，所以主存页面表的修改置定可用软硬结合的方法去实现。在主

36、存页面表中还可增设某些其它信息，例如可增设修改位以记录该页进入主存后是否被修改过。由于辅存中原来有其副本，如果是未修改（写入）过的页，在替换时就可不必先写回辅存，以减少辅助操作时间，否则必须先将它写回辅存原来的地方，然后才能替换。,LRU算法尽管比FIFO算法更能反映程序的局部性，但它们都是根据过去页面的使用情况确定被替换页。若能将未来的近期内不用的页替换出去，一定会有最高的命中率，这种算法成为优化替换算法(Optimal Replacement Algorithm、OPT)，它是理想化的算法，不太现实。 替换算法一般是通过用典型的页地址流模拟其替换过程，再根据所得到的命中率的高低来评价其好坏

37、。下面举例说明替换算法、页地址流、页面大小、主存容量（分配给程序的主存页数）对命中率的影响。,例3.2 设有一道程序，执行时的页地址流为：2，3，2，1，5，2，4，5，3，2，5，2。若分配给该道程序的主存有3页，表3.1表示了分别采用FIFO、LRU、OPT 3种替换算法对这3页的使用和替换过程。其中用*号标记出按所用算法选作下次应该被替换的页号。,表3.1 3种替换算法对同一页地址流的替换过程,由表3.1可见，FIFO算法的页命中率最低，而LRU算法的命中率却非常接近于OPT。这不仅表明命中率与所用的替换算法有关，而且也表明LRU算法要优于FIFO算法，因此实际中用的更多。 命中率也与页

38、地址流有关。例如一个循环程序，当所需页数大于分配给它的主存页数时，无论是FIFO还是LRU算法的命中率都明显低于OPT算法。表3.2说明了OPT算法能命中3次，而LRU和FIFO算法却一次都没有命中，因为它恰好总是将马上要用到的页面替换出去了，从而连续不断地出现页面失效，产生所谓的颠簸现象。,但是，就表3.2为例来说，只要分配给该道程序的实页数增加一页，就会使命中次数都增加到4次。所以，命中率又与分配给程序的主存页数有关。一般来说，分配给程序的主存页数越多，虚页装入主存的机会越多，命中率也就可能越高，但是否能提高呢，这和所采用的替换算法有很大关系。FIFO算法就不一定。从表3.3中可以看出，分

39、配给程序的主存页数由3页增加到4页时，命中率反而由3/12降低到2/12。,而LRU算法却不会发生这种情况，随着分配给该道程序的主存页数的增加，命中率一般都能得到提高，至少不会下降。因此，从衡量替换算法好坏的命中率高低来考虑，如果对影响命中率的主存页数n取各种不同值时都进行一次模拟，其工作量是非常大的。于是提出了若干能优化存贮体系设计，减少模拟工作量的分析模型。使用堆栈处理技术处理的分析模型就适合于采用堆栈型替换算法的系统。,表3.2 命中率与页地址流的关系,表3.3 FIFO法的页数增加，命中率反而有可能下降,什么是堆栈型替换算法呢？设A是长度为L的任意一个页面地址流，t为已处理过t-1个页

40、面的时间点，n为分配给该地址流的主存页面数，Bt(n)表示在t时间点、在n页的主存中的页面集合，Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法具有下列包含性质： 当nLt时，Bt(n) Bt(n+1)； 当nLt时，Bt(n)= Bt(n+1) 则此替换算法属堆栈型的替换算法。,LRU算法在主存中保留的是n个最近使用的页面，它们又总是被包含在n+1个最近使用的页面之中，所以LRU算法是堆栈型算法。显然，OPT算法也是堆栈型算法，而FIFO算法则不是。,2页式虚拟存储器的工作过程 图3.16描述的是页式虚拟存储器工作的全过程，它主要包括内部地址变换、外部地址变换、页面的替换和页面

41、的调入与调出四个方面。,图3.16 页式虚拟存储器工作的全过程,具体来讲，在页式虚拟存储器中每当用户以虚拟地址访问主存时，都必须查内页表，将多用户虚地址变换成主存的实地址。当查内页表时，如果对应该虚页的装入位为“1”，就取出其主存页号nv，拼接上页内位移Nr，形成主存实地址np后访主存。如果对应该虚页的装入位为“0”，表示该虚页未在主存中，就产生页面失效故障（异常），程序换道经异常处理，并从辅存中调页。这时需经过查外页表，完成外部地址变换。,如查外页表时，该虚页的装入位为“0”，表示尚未装入辅存，还需要产生辅存缺页故障（异常），由海量存储器调入；若查外页表时，该虚页的装入位为“1”，就将多用户

42、虚地址变换成辅存中的实地址Nvd，告诉I/O处理机，到辅存中去调页，而后经I/O处理机送入主存。在多道程序机中，CPU的运行与I/O处理机的调页过程是并行进行的。,一旦发生页面失效，还需要确定调入页应该进入主存中的哪一个页面位置，这就需要操作系统查主存页面表。若占用位为“0”，表示主存未装满。因为采用的是全相联映象，只需找到任何占用位为“0”的一个页面位置即可。若占用位为“1”，表示主存已装满，就需要通过替换算法寻找替换页 。不管哪种情况均将确定了的主存页号送入I/O处理机 ，由I/O处理机完成页的调入。,在进行页面替换时，如果被替换的页调入主存后一直未经修改，则不需送回辅存；如果已经修改，则

43、需将它先送回辅存的原来位置 ，而后才把调入页装入主存。装入主存的页是否修改过是可以由主存页面表中的修改位来指明的。每次调入主存一个虚页或访问过主存中的一页时应记录或修改有关页表与主存页面表的内容。,3.3.4 提高虚拟存储器等效访问速度的措施 从存储层次的等效访问速度公式TA=HTA1+（1-H）TA2，可以看出，提高虚拟存储器等效访问速度的措施有两种： (1)由于TA2远大于TA1，所以要想办法提高主存命中率； (2)缩短访问时间；,1. 如何提高主存的命中率 影响主存命中率的因素很多，如页地址流、页面调度策略、替换算法、页面大小、分配给程序的页数（主存容量）等，将集中在下一部分介绍。 2.

44、 如何缩短访存时间 缩短访问时间主要有两个方面： (1)提高存储器件本身的速度 (2)优化存储器结构设计,下面主要从第二个方面来讨论。 页式虚拟存储器工作的全过程包括四个方面： (1)内部地址变换。每次访问主存时，都必须进行内部地址变换，由多用户虚地址通过查内页表变换成主存地址后，才能访存，这种内部地址变换的概率是100%。 (2)外部地址变换。只有当发生页面失效时才需要进行外部地址变换，由多用户虚地址通过查外页表变换成辅存实地址后，才能去辅存将需要的虚页调入主存，这种外部地址变换的概率一般不到1%。,(3)页面的替换。而只有当发生页面失效又发生页面争用时，才需要调用替换算法来选择将主存中的哪

45、个页替换出去，其概率显然比1%还要低的多。 (4)页面的调入与调出。当要访问的虚页未装入到主存中时，就会发生调入。另外，在发生页面替换时，也会发生页面的调入和调出。,因此，从缩短访问主存的时间来看，关键就是如何加快多用户虚地址NS到主存实地址np的变换速度。而系统结构设计的主要任务是从逻辑结构上来提高内部地址变换的速度。 提高内部地址变换速度的方法有两种： (1)采用单独的小容量快速随机存储器或寄存器组来存放内页表。一般适用于规模较小的机器，即虚拟存储空间较小的机器，如虚拟存储器的存储容量小于1M机器字。,(2)采用增设“快表”的途径来解决。由于程序的局部性特点，对页表内各行的使用不是随机的。

46、在一段时间内实际只用到表中很少的几行。这样，用快速硬件构成比全表小得多的部分“目录表”（例如，图3.17中所示的816行），存放当前正在使用的虚、实地址映象关系，那么其相联查找的速度将会很快。我们把这个部分目录表称为快表。将原先存放全部虚、实地址映象关系的表称为慢表。快表只是慢表中很小的一部分副本。,由按内容访问的相联存储器构成的快表 图3.17所示是经快表与慢表实现内部地址变换的原理图。查表时，由虚页号Nv同时去查快表和慢表。当在快表中有此虚页号时，就能很快地找到对应的实页号nv，将其送入主存实地址寄存器，并立即使慢表的查找作废，这时访主存的速度几乎没有什么降低。如果在快表中查不到时，则经一

47、个访主存时间后，从慢表中查到的实页号nv就会送入主存实地址寄存器。同时将此虚页号和对应的实页号送入快表。这里，也会用替换算法去替换快表中应该移掉的内容。,图3.17 经快表与慢表实现内部地址变换,当然，快表的命中率如果不高，系统效率就会大大降低。如果快表采用的替换算法是堆栈型的，则快表容量愈大，其命中率必然愈高。但容量愈大，其相联查找的速度也愈慢，所以快表的命中率和查表速度是有矛盾的。若快表取816行，每页容量为14K字，则快表容量可反映主存中的864K单元。一般来说，这样的快表其命中率是不会低的。,为了使快表的查找尽可能快，还可以在结构上采取某些技巧，因为对一般器件，在同样容量情况下，相联比

48、较的位数越少，则相联查找所花费的时间和设备量就越少。因为快表内容在一段时间内总是对应于同一个任务，同一个用户，就是说它们的u值是相同的，所以参与相联比较的位数中就可把 u去掉，如图3.18所示。,对图3.18，由于去掉了u部分，若不采取另外的措施，在任务切换时就会出错。因此早期的快表为此专门设置一位用户位，用户位为0的行，其内容无效。在任务切换时，通过硬件将所有用户位全部置为“0”，让快表中的内容全部作废。这时只能在新任务执行过程中通过慢表逐次取得nv 值，并将其装入快表，同时让该装入行的用户位置成“1” 。,图3.18 减少快表的相联比较位数,但这种方法却会使快表命中率下降，从而降低虚、实地

49、址的变换速度。例如：当某个A任务要使用I/O设备时，它是通过“访管”指令调用操作系统的，这时就要进行任务切换，使快表中的所有用户位都置成“0”。可是，I/O管理程序一般很简单，可能只用到快表中的一行（对应主存中的一页），CPU很快又将任务切换回来运行A任务。为了解决这个问题，有的机器就设置专用指令，只清除快表中指定行的使用位，从而可使其它行的内容在任务切换回来后仍然有效。然而，这使得快表对系统程序员成了不透明的了，增大了操作系统的负担，当然是不理想的。,看来还是采用图3.17所示的大容量的快表，快表容量越大，命中率就越高，但相联比较却越费时，使快表快不起来。 既要增加快表的容量，又要提高查表的

50、速度，采用的方法是：用速度快、容量大的按地址访问的存储器芯片代替相联存储器。,由按地址访问的高速存储芯片构成的快表 对在按地址访问的存储器中的信息实现按内容查找，可以有顺序查找、对分查找和散列查找等多种方法，其中以散列（hashing）方法的速度为最快。散列方法的基本思想是让内容Nv与存放该内容的地址A之间有某种散列函数的关系，即让快表的地址A=H（NV）。为了提高用户虚页Nv转换成散列地址（对应nv在快表中存放地址）的速度，对于较复杂的散列函数，一般用ROM和PLA查表实现。 经散列实现快表按地址访问的原理图如图3.19所示。,图3.19 经散列实现快表,为了解决多个不同的用户虚页Nv散列到