计算机系统结构第4章.ppt

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

1、第 4 章 存 贮 体 系 第第 4 4 章章 存存 贮贮 体体 系系 4.1 存储体系的概念存储体系的概念 4.2 虚拟存储器虚拟存储器 4.3 高速缓冲存储器高速缓冲存储器 4.4 Cache主存主存辅存三级层次辅存三级层次 4.5 主存保护主存保护 第 4 章 存 贮 体 系 4.1 存贮体系的形成与性能存贮体系的形成与性能 4.1.14.1.1存储体系及其分支存储体系及其分支所谓存储体系,就是让构成存储系统的n种不同的存储器(M1Mn)之间，配上辅助软、硬件或辅助硬件，使之从应用程序员来看，它们在逻辑上是一个整体。让存储层次的等效访问速度是接近于M1的，容量是Mn的，每位价格是接近于M

2、n的。基本的两级存储体系是虚拟存储器和Cache存储器，这是存储体系的两个不同的分支。第 4 章 存 贮 体 系 图4-1主存-辅存存储层次 第 4 章 存 贮 体 系 虚拟存储器是从主存容量满足不了要求提出来的。在主存和辅存之间，增设辅助的软、硬件设备，让它们构成一个整体，所以也称为主存-辅存存储层次。如图4-1所示。从CPU看，速度是接近于主存的，容量是辅存的，每位价格是接近于辅存的。从CPU看，速度是接近于主存的，容量是辅存的，每位价格是接近于辅存的。从速度上看，主存的访问时间约为磁盘的访问时间的10-5，即快10万倍。从价格上看，主存的每位价格约为磁盘的每位价格的103，即贵1000倍

3、。如果存储层次能以接近辅存的每位价格去构成等于辅存容量的快速主存，就会大大提高存储器系统的性能价格比。第 4 章 存 贮 体 系 应用程序员可用机器指令的地址对整个程序统一编址，称该地址为虚地址(程序地址)，而把实际主存地址称为实地址(实存地址)。当虚存空间(程序空间)远远大于实地址空间(实存空间)时，只需将程序空间分割成较小的段或页，由系统程序按需要调入物理主存，并用辅助映像表建立其虚、实地址空间的对应关系。在用虚地址访主存时，由系统硬件查看，这个虚地址所对应单元的内容是否已装入主存。如果在主存内，就变换成主存实地址去访问主存；如果不在主存内，就经辅助软、硬件将含所要访问的单元在内的那个段(

4、或页)的程序块由辅存调入主存，建立好映像关系，再进行访问。这样，不论是虚、实地址的变换还是程序由辅存调入主存都不必由应用程序员安排，即这些操作和辅助软、硬件对应用程序员来讲是透明的。事实上，只要是存储层次，这些都必须对应用程序员是透明的。第 4 章 存 贮 体 系 因主存速度满足不了要求而引出了Cache存储器。在CPU和主存之间增设高速、小容量、每位价格较高的Cache，用辅助硬件将Cache和主存构成整体，如图4-2所示，称之为Cache存储器(或称为Cache-主存存储层次)。从CPU看，有接近于Cache的速度、主存的容量，接近于主存的每位价格。由于CPU与主存的速度只差一个数量级，信

5、息在Cache与主存之间的传送就只能全部用辅助硬件实现，因此，Cache存储器不仅对应用程序员是透明的，而且对系统程序员也是透明的。第 4 章 存 贮 体 系 图4-2Cache-主存存储层次 第 4 章 存 贮 体 系 由二级存储层次可组合成如图4-3所示的多级存储层次。希望从CPU看是一个整体，有接近于最高层M1的速度、最低层Mn的容量，并有接近于最低层Mn的每位价格。第 4 章 存 贮 体 系 图4-3多级存储层次 第 4 章 存 贮 体 系 4.1.24.1.2存储体系的构成依据存储体系的构成依据为了使存储体系能有效地工作，当CPU要用到某个地址的内容时，总希望它已在速度最快的M1中，

6、这就要求未来被访问信息的地址能预知，这对存储体系的构成是非常关键的。这种预知的可能性是基于计算机程序具有局部性，它包括时间上的局部性和空间上的局部性。前者指的是在最近的未来要用到的信息很可能是现在正在使用的信息，这是因为程序存在循环。后者指的是在最近的未来要用到的信息很可能与现在正在使用的信息在程序空间上是邻近的，这是因为指令通常是顺序存放、顺序执行，数据通常是以向量、阵列、树形、表格等形式簇聚地存放的。所以，程序执行时所用到的指令和数据是相对簇聚成自然的块或页(存储器中较小的连续单元区)。第 4 章 存 贮 体 系 这样，层次的M1级不必存入整个程序，只需将近期用过的块或页(根据时间局部性)

7、存入即可。在从M2级取所要访问的字送M1时，一并把该字所在的块或页整个取来(根据空间的局部性)，就能使要用的信息已在M1的概率显著增大。这是存储层次构成的主要依据。预知的准确性是存储层次设计好坏的主要标志，很大程度取决于所用算法和地址映像变换的方式。一旦出现被访问信息不在M1中时，原先申请访存的程序就暂停执行或被挂起，直到所需信息被调到M1为止。然而这是指的虚拟存储器。若M1为Cache，则不将程序挂起，只是暂停执行，等待信息调入M1。同时为缩短CPU空等时间，还让CPU不只与Cache，也和主存有直接通路。就是说，虚拟存储器只能适用于多道程序(多用户)环境，而Cache存储器既可以是单用户环

8、境也可以是多用户环境。第 4 章 存 贮 体 系 4.1.3存储体系的性能参数存储体系的性能参数为简单起见，以图4-4的二级体系(M1,M2)为例来分析。设ci为Mi的每位价格,SMi为Mi的以位计算的存储容量，TAi为CPU访问到Mi中的信息所需的时间。为评价存储层次性能，引入存储层次的每位价格c、命中率H和等效访问时间TA。存储层次的每位价格 第 4 章 存 贮 体 系 图4-4二级存储体系的评价第 4 章 存 贮 体 系 总希望存储层次的每位价格能接近于c2，为此应使。同时，上式中并未把采用存储体系所增加的辅助软、硬件价格计算在内，所以要使c接近于c2，还应限制所增加的这部分辅助软、硬件

9、价格只能是总价格中一个很小的部分，否则将显著降低存储体系的性能价格比。第 4 章 存 贮 体 系 命中率H定义为CPU产生的逻辑地址能在M1中访问到(命中到)的概率。命中率可用实验或模拟方法求得，即执行或模拟一组有代表性的程序，若逻辑地址流的信息能在M1中访问到的次数为R1，当时在M2中还未调到M1的次数为R2，则命中率H=R1/(R1+R2)。显然命中率H与程序的地址流，所采用的地址预判算法及M1的容量都有很大关系。我们总希望H愈大愈好，即H越接近于1越好。相应的，不命中率或失效率是指由CPU产生的逻辑地址在M1中访问不到的概率。对二级存储层次，失效率为1-H。存储层次的等效访问时间TA=H

10、TA1+(1-H)TA2。希望TA越接近于TA1，即存储层次的访问效率e=TA1/TA越接近于1越好。第 4 章 存 贮 体 系 设CPU对存储层次相邻二级的访问时间比r=TA2/TA1，则 据此，可得e=f(r,H)的关系如图4-5所示。第 4 章 存 贮 体 系 由图4-5可知，要使访问效率e趋于1，在r值越大时，就要求命中率H越高。例如，r=100时，为使e0.9，必须使H0.998；而当r=2时，只需H0.889即可。像主-辅层次，速度差达105，要求H极高才能有高的访问效率，但H很难极高。为了降低对H的要求，可以减少相邻二级的访问速度差，减少相邻二级存储器的容量差也能提高H，但与为降

11、低每位平均价格要求容量差要大相矛盾。因此，在主、辅存之间增加一级电子磁盘，使级间r值不会过大，有利于降低对H的要求，以获得同样的e。所以要想使存储层次的访问效率e趋于1，就要在选择具有高命中率的算法、相邻二级的容量差和速度差及增加的辅助软、硬件的代价等因素间综合权衡，进行优化设计。第 4 章 存 贮 体 系 图4-5对于不同的r,命中率与访问效率e的关系第 4 章 存 贮 体 系 4.2虚拟存储器虚拟存储器 4.2.14.2.1虚拟存储器的管理方式虚拟存储器的管理方式1.1.段式管理段式管理程序都有模块性，一个复杂的大程序总可以分解成多个在逻辑上相对独立的模块。这些模块可以是主程序、子程序或过

12、程，也可以是数据块。模块的大小各不相同，有的甚至事先无法确定。每个模块都是一个单独的段，都以该段的起点为0相对编址。当某个段由辅存调入主存时，只要系统赋予该段一个基址(即该段存放在主存中的起始地址)，就可以由此基址和单元在段内的相对位移形成单元在主存中的实际地址。将主存按段分配的存储管理方式称为段式管理。第 4 章 存 贮 体 系 为了进行段式管理，每道程序在系统中都有一个段(映像)表来存放该道程序各段装入主存的状况信息。参看图4-6，段表中的每一项(对应表中的每一行)描述该道程序一个段的基本状况，由若干个字段提供。段名字段用于存放段的名称，段名一般是有其逻辑意义的，也可以转换成用段号指明。由

13、于段号从0开始顺序编号，正好与段表中的行号对应，如2段必是段表中的第3行，这样，段表中就可不设段号(名)字段。装入位字段用来指示该段是否已经调入主存，“1”表示已装入，“0”表示未装入。在程序的执行过程中，各段的装入位随该段是否活跃而动态变化。第 4 章 存 贮 体 系 当装入位为“1”时，地址字段用于表示该段装入主存中的起始(绝对)地址，当装入位为“0”时，则无效(有的机器用它表示该段在辅存中的起始地址)。段长字段指明该段的大小，一般以字数或字节数为单位，取决于所用的编址方式。段长字段是用来判断所访问的地址是否越出段界的界限保护检查用的。访问方式字段用来标记该段允许的访问方式，如只读、可写、

14、只能执行等，以提供段的访问方式保护。除此之外，段表中还可以根据需要设置其他的字段。段表本身也是一个段，一般常驻在主存中，也可以存在辅存中，需要时再调入主存。第 4 章 存 贮 体 系 假设系统在主存中最多可同时有N道程序，可设N个段表基址寄存器。对应于每道程序，由基号(程序号)指明使用哪个段表基址寄存器。段表基址寄存器中的段表基地址字段指向该道程序的段表在主存中的起始地址。段表长度字段指明该道程序所用段表的行数，即程序的段数。由系统赋予某道程序(用户、进程)一个基号，并在调入/调出过程中对有关段表基址寄存器和段表的内容进行记录和修改，所有这些都不用用户程序员来管。某道活跃的程序在执行过程中产生

15、的指令或操作数地址只要与基号组合成系统的程序地址，即可通过查表自动转换成主存的物理地址。图4-6示意性地表示了这一地址变换的过程。第 4 章 存 贮 体 系 图4-6段式管理的定位映像机构及地址的变换过程 第 4 章 存 贮 体 系 分段方法能使大程序分模块编制，从而可以多个程序员并行编程，缩短编程时间，在执行或编译过程中对不断变化的可变长段也便于处理。各个段的修改、增添并不影响其他各段的编制，各用户以段的连接形成的程序空间可以与主存的实际容量无关。分段还便于几道程序共用已在主存内的程序和数据，如编译程序、各种子程序、各种数据和装入程序等。不必在主存中重复存储，只需把它们按段存储，并在几道程序

16、的段表中有公用段的名称及同样的基址值即可。第 4 章 存 贮 体 系 由于各段是按其逻辑特点组合的，容易以段为单位实现存储保护。例如，可以安排成常数段只能读不能写；操作数段只能读或写，不能作为指令执行；子程序段只能执行，不能修改；有的过程段只能执行，不能读也不能写，如此等等。一旦违反规定就中断，这对发现程序设计错误和非法使用是很有用的。第 4 章 存 贮 体 系 段式管理的虚拟存储器由于各个段的长度完全取决于段自身，当然不会恰好如图4-6所示的那样是1K的整数倍，段在主存中的起点也会是随意的，这就给高效地为调入段分配主存区域带来困难。为了进行段式管理，除了系统需要为每道程序分别设置段映像表外，

17、还得由操作系统为整个主存系统建立一个实主存管理表，它包括占用区域表和可用区域表两部分。占用区域表的每一项(行)用来指明主存中哪些区域已被占用，被哪道程序的哪个段占用以及该段在主存的起点和长度。第 4 章 存 贮 体 系 此外，还可以设置诸如该段是否进入主存后被改写过的字段，以便该段由主存中释放时，决定是否还要将其写回到辅存中原先的位置来减少辅助操作。可用区域表的每一项(行)则指明每一个未被占用区的基地址和区域大小。当一个段从辅存装入主存时，操作系统就在占用区域表中增加一项，并修改可用区域表。而当一个段从主存中退出时，就将其在占用区域表的项(行)移入可用区域表中，并进行有关它是否可与其他可用区归

18、并的处理，修改可用区域表。当某道程序全部执行结束或者是被优先级更高的程序所取代时，也应将该道程序的全部段的项从占用区域表移入可用区域表并作相应的处理。第 4 章 存 贮 体 系 2.2.页式管理页式管理段式存储中各段装入主存的起点是随意的，段表中的地址字段很长，必须能表示出主存中任意一个绝对地址，加上各段长度也是随意的，段长字段也很长。这既增加了辅助硬件开销，降低了查表速度，也使主存管理麻烦。段式管理和存储还会带来大的段间零头浪费。例如，主存中已有A、B、C三个程序，其大小和位置如图4-7所示，现有一长度为12KB的D道程序想要调入。段式管理时尽管D道程序长度小于主存所有可用区零头总和16KB

19、，但没有哪一个零头能装得下它，所以无法装入。于是提出了页式存储。第 4 章 存 贮 体 系 图4-7采用页式存储后D道程序仍可装入 第 4 章 存 贮 体 系 页式存储是把主存空间和程序空间都机械等分成固定大小的页(页面大小随机器而异，一般在512B到几，按页顺序编号。这样，任一主存单元的地址np就由实页号nv和页内位移nr两个字段组成。每个独立的程序也有自己的虚页号顺序。如此例中，若页面大小取4KB，则独立编址的D程序就有三页长，页号02。如果让虚存中的每一页均可装入主存中任意的实页位置，如图4-7那样,D程序中各页仍可分别装入主存的第2、6、7三个实页位置上，只要系统设置相应的页(映像)表

20、，保存好虚页装入实页时的页面对应关系，就可由给定的程序(虚)地址查页表变换成相应的实(主)存地址访存。第 4 章 存 贮 体 系 由于页式存储中程序的起点必处于一个页面的起点，用户程序中每一个虚地址就由虚页号字段Nv和页内位移字段Nr组成。而虚存和实(主)存的页面大小又一样，所以页表中只需记录出虚页号Nv和实(主)存页号nv的对应关系，不用保存页内位移。而虚页号与页表的行号是对应的，如虚页号2必对应于页表中第3行，所以不用专设虚页号字段。页面大小固定，页长字段也省了。所有这些都简化了映像表硬件，也利于加快查表。当然与段表类似，页表也必须设置装入位字段以表示该页是否已装入主存。第 4 章 存 贮

21、 体 系 当装入位为“1”时，实页号字段中的内容才是有效的，否则无效。为便于存储保护，页表中也可相应设置访问方式字段等。可以看出，由虚地址查表变换成实地址过程，段式管理需要较长的加法器进行将段起始地址加上段内位移的操作，而页式管理只需将主存实页号与页内位移拼装在一起，可大大加快地址变换的速度，也利于提高形成实地址的可靠性。第 4 章 存 贮 体 系 与段式一样，机器是采用多道程序方式工作的。若系统内最多可在主存中容纳N道程序，对每道程序都将有一个页表。由用户号u指明该道程序使用哪个页表基址寄存器，从而可以找到该道程序的页表在主存中的起点。就整个多用户虚拟存储器的虚存空间来说，其虚地址应有用户(

22、进程、程序)标识号u、虚页号Nv和页内位移Nr三个字段。如同段式管理一样，在程序装入和运行过程中，页表基址寄存器和页表的内容全部由存储层次来完成置定和修改，对用户完全是透明的。图4-8示意出页式管理的定位映像机构及其虚、实地址的变换过程。第 4 章 存 贮 体 系 图4-8页式管理的定位映像机构及其地址的变换过程 第 4 章 存 贮 体 系 3.3.段页式管理段页式管理页式对应用程序员完全透明，所需映像表硬件较少，地址变换的速度快，调入操作简单等方面都优于段式。页式不能完全消除主存可用区的零头浪费，因为程序的大小不可能恰好就是页面大小的整数倍。产生的页内零头虽然无法利用，但其浪费比段式的要小得

23、多，所以在主存空间利用率上，页式的也优于段式的。因此，单纯用段式管理的虚拟存储器已很少见到。第 4 章 存 贮 体 系 然而，相比而言段式也具有页式所没有的若干优点，如：段式中每个段独立，有利于程序员灵活实现段的链接、段的扩大缩小和修改，而不影响到其他的段；每段只包含一种类型的对象，如过程或是数组、堆栈、标量等集合，易于针对其特定类型实现保护；把共享的程序或数据单独构成一个段，从而易于实现多个用户、进程对共用段的管理，等等。如果采用页式，做到这些就比较困难。因此，为取长补短，提出了将段式和页式相结合的段页式存储和管理。第 4 章 存 贮 体 系 段页式存储是把实存机械等分成固定大小的页，程序按

24、模块分段，每个段又分成与主存页面大小相同的页。每道程序通过一个段表和相应的一组页表进行定位。段表中的每一行对应一个段。其中，“装入位”表示该段的页表是否已装入主存。若未装入主存，则访问该段时将引起段失效故障，请求从辅存中调入页表。若已装入主存，则地址字段指出该段的页表在主存中的起始地址。“访问方式”字段指定对该段的控制保护信息。“段长”字段指定该段页表的行数。每一个段都有一个页表。页表中每一行用装入位指明此段该页是否已装入主存。若未装入主存，则访问该页时将引起页面失效故障，需从辅存调页。如果已装入主存，则用地址字段来指明该页在主存中的页号。此外，页表中还可以包含一些其他信息。段页式与纯段式的主

25、要差别是段的起点不再是任意的，必须是位于主存中页面的起点。第 4 章 存 贮 体 系 图4-9段页式管理的定位映像机构及其地址的变换过程 第 4 章 存 贮 体 系 对于多道程序来说，每道程序(用户或进程)都需要有一个用户标志号u(转换成基号b)以指明该道程序的段表起点存放在哪个基址寄存器中。这样，多用户虚地址就由用户号u、段号s、页号p、页内位移d四个字段组成。设系统中主存最多可容纳N道程序，图49表示采用段页式管理的定位映像机构及由多用户虚地址变换成主存实地址的过程。不少大、中型机都采用这种段页式存储。在虚拟存储器中每访问一次主存都要进行一次程序地址向实(主)存地址的转换。段页式的主要问题

26、是地址变换过程至少需要查表两次，即查段表和页表。因此，要想使虚拟存储器的速度接近于主存的，必须在结构上采取措施加快地址转换中查表的速度。第 4 章 存 贮 体 系 4.2.2页式虚拟存储器的构成页式虚拟存储器的构成1.地址的映像和变换地址的映像和变换它将主存空间和程序空间都按相同大小机械等分成页，并让程序的起点总是处在页的起点上。程序员用指令地址码Ni来编写每道程序，Ni由用户虚页号Nv和页内地址Nr组成。主存地址则分成实页号nv与页内位移nr两部分，其中nr总是与Nr一样。大多数虚拟存储器中每个用户的程序空间可比实际主存空间大得多，即一般有Nv nv。这样，虚拟存储器系统总的多用户虚地址Ns

27、就由用户标志u、用户的虚页号Nv及页内地址Nr三部分构成，总的虚存空间是2u+Nv 个页。可将u和Nv合并成多用户虚页号Nv，则2Nv2nv。它们各部分的地址对应关系如图4-10所示。第 4 章 存 贮 体 系 图4-10虚、实地址对应关系及空间的压缩 第 4 章 存 贮 体 系 地址的映像是将每个虚存单元按什么规则(算法)装入(定位于)实存，建立起多用户虚地址Ns与实(主)存地址np之间的对应关系。对页式而言，就是将多用户虚页号Nv的页可以装入主存中的哪些页面位置，建立起Nv与nv的对应关系。地址的变换是指程序按照这种映像关系装入实存后，在执行中，如何将多用户虚地址Ns变换成对应的实地址np

28、。对页式而言，就是如何将多用户虚页号Nv变换成实页号nv。地址的变换与所采用的地址映像规则密切相关，因此结合在一起来讲述。第 4 章 存 贮 体 系 由于是把大的虚存空间压缩到小的主存空间，主存中的每一个页面位置应可对应多个虚页，能对应多少个虚页，与采用的映像方式有关。这就可能发生两个以上的虚页想进入主存同一个页面位置的页面争用(或实页冲突)的情形。一旦发生实页冲突，只能让主存中该页面位置先装入其中的一个虚页，待其退出主存后方可再装入，执行效率自然会下降。因此，映像方式的选择应考虑能否尽量减少实页冲突概率，同时应考虑辅助硬件是否少,成本是否低,实现是否方便以及地址变换的速度是否快等。由于虚存空

29、间远大于实存空间，页式虚拟存储器一般都采用让每道程序的任何虚页可以映像装入到任何实页位置的全相联映像，如图4-11所示。仅当一个任务要求同时调入主存的页数超出2nv时，两个虚页才会争用同一个实页位置，这种情况是很少见的。因此，全相联映像的实页冲突概率最低。第 4 章 存 贮 体 系 图4-11全相联映像 第 4 章 存 贮 体 系 全相联映像的定位机构及其地址的变换过程已在4.2.1节中介绍过，它用页表作为地址映像表，故称之为页表法。整个多用户虚存空间可对应2u个用户(程序)，但主存最多同时只对其中N个用户(N道程序)开放。由基号b标识的N道程序中的每一道都有一个最大为行的页表，而主存总共只有

30、个实页位置，因此N道程序页表的全部行中，装入位为“1”的最多只有行。由于，使得页表中绝大部分行中的实页号nv字段及其他字段都成了无用的了，这会大大降低页表的空间利用率。第 4 章 存 贮 体 系 一种解决办法是将页表中装入位为“0”的行用实页号nv字段存放该程序此虚页在辅存中的实地址，以便调页时实现用户虚页号到辅存实地址的变换。不过当辅存实地址的位数与用户虚页号字段的位数差别大时，就很难利用。另一种方法是把页表压缩成只存放已装入主存的那些虚页(用基号b和Nv标识)与实页位置(nv)的对应关系，如图4-12所示，该表最多为2nv行。我们称它为相联目录表法，简称目录表法。该表采用按内容访问的相联存

31、储器构成。第 4 章 存 贮 体 系 图4-12目录表法 第 4 章 存 贮 体 系 按内容访问的相联存储器不同于按地址访问的随机存储器。按地址访问的随机存储器是在一个存储周期里只能按给出的一个地址访问其存储单元。相联存储器是在一个存储周期中能将给定的Nv同时与目录表全部2nv个单元对应的虚页号字段内容比较，进行相联查找。如有相符的，即相联查到时，表示此虚页已被装入生存，该单元中存放的实页号nv就是此虚页所存放的实页位置，将其读出拼接上Nr就可形成访存实地址np,该单元其他字段内容可供访问方式保护或其他工作用。如无相符的，即相联查找不到时，就表示此虚页未装入主存，发出页面失效故障，请求从辅存中

32、调页。可见，目录表法不用设置装入位。第 4 章 存 贮 体 系 尽管目录表的行数为2nv，比起页表法的行少得多，但主存的页数2nv还是很大的，这样用有2nv行的相联存储器，不仅造价很高，而且查表速度也较慢。所以，虚拟存储器一般不直接用目录表来存储全部虚页号与实页号的对应关系，但它可以被用来提高地址变换速度。第 4 章 存 贮 体 系 当给出的多用户虚地址Ns所在的虚页未装入主存时都将发生故障。其中，可能是出现了一个从未运行过的新程序，此时将进行程序换道。也可能是已在主存中的某程序的虚页未装入主存而发生页面失效，到辅存中去调页。现以后者为例来讨论。要想把该道程序的虚页调入主存，必须给出该页在辅存

33、中的实际地址。为了提高调页效率,辅存一般是按信息块编址，而且让块的大小通常等于页面的大小。以磁盘为例，辅存实(块)地址Nvd的格式为：表第 4 章 存 贮 体 系 图4-13虚地址到辅存实地址的变换 第 4 章 存 贮 体 系 2.2.页面替换算法页面替换算法当处理机要用到的指令或数据不在主存中时，会产生页面失效，须去辅存中将含该指令或数据的一页调入主存。通常虚存空间比主存空间大得多，必然会出现主存已满又发生页面失效的情况，这时将辅存的一页调入主存会发生实页冲突。只有强制腾出主存中某个页才能接纳由辅存中调来的新页。选择主存中哪个页作为被替换的页，就是替换算法要解决的问题。替换算法的确定主要看主

34、存是否有高的命中率，也要看算法是否便于实现，辅助软、硬件成本是否低。目前已研究过多种替换算法，如随机算法、先进先出算法、近期最少使用(近期最久未用过)算法等。第 4 章 存 贮 体 系 随机算法(Random,RAND)是用软的或硬的随机数产生器产生主存中要被替换页的页号。这种算法简单，易于实现，但没有利用主存使用的“历史”信息，反映不了程序的局部性，使主存命中率很低，因此已不采用。先进先出算法(FirstInFirstOut,FIFO)是选择最早装入主存的页作为被替换的页。这种算法实现方便，只要在操作系统为主存管理所设的主存页面表中给每个实页配一个计数器字段。每当一页装入主存时，让该页的计数

35、器清零，其他已装入主存的那些页的计数器都加“1”。需要替换时，计数器值最大的页的页号就是最先进入主存而现在准备替换掉的页号。它虽利用了主存使用的“历史”信息，但不一定能正确地反映出程序的局部性。因为最先进入的页很可能正是现在经常在用的页。第 4 章 存 贮 体 系 图4-14主存页面表 第 4 章 存 贮 体 系 近期最少使用算法(LeastRecentlyUsed,LRU)是选择近期最少访问的页作为被替换页。这种算法能比较正确地反映程序的局部性。一般来说，当前最少使用的页，未来也将很少被访问。但完全按此算法实现比较困难，需要为每个实页都配一个字长很长的计数器。所以一般用其变形。把近期最久未访

36、问过的页作为被替换页，将“多”和“少”变成“有”和“无”实现就方便多了。第 4 章 存 贮 体 系 图4-14是操作系统为实现主存管理设置的主存页面表，其中每一行用来记录主存中各页的使用状况。主存页面表不是前述的页表。页表用于存储地址映像关系和实现地址变换的，是对用户程序空间而言，每道程序都有一个。主存页面表存于主存。主存页号是顺序的，该字段可以省去，用相对于主存页面表起点的行数表示。占用位表示主存该页是否已占用，“0”表示未被占用，“1”表示已被占用。至于被哪个程序的哪个段或哪个页占用，由程序号、段页号字段指明。为实现近期最久未用过算法，给表中每个主存页配一位“使用位”标志。开始时，所有页的

37、使用位全为“0”。只要某个实页的任何单元被访问过，就由硬件自动将该页使用位置为“1”。由于是全相联映像，调入页可进入主存页面表中任何占用位为“0”的实页位置，一旦装入就将该实页之占用位置为“1”。只有当占用位都是“1”，又发生页面失效时，才有页面替换，只需替换使用位为“0”的页即可。第 4 章 存 贮 体 系 显然，使用位不能出现全为“1”，否则无法确定哪页被替换。一种办法是一旦使用位要进入全“1”时立即由硬件强制全部使用位都为“0”。从概念上看，近期最少使用的“期”是从上次使用位全“0”到这次使用位为全“0”的这段时期。此“期”的长短是随机的，故称为随机期法。另一种办法是定期置全部使用位为“

38、0”。给每个实页再配一个“未使用过计数器”Hs(或称历史位)，定期地每隔t时间扫视所有使用位，凡使用位为“0”的将其Hs加“1”，并让使用位仍为“0”；而对使用位为“1”的将其Hs和使用位均“清0”。这样,Hs值最大的页表明是最久未用的将作为被替换的页。可见，使用位反映一个t期内的页面使用情况，Hs则反映了多个t期内的页面使用状况。第 4 章 存 贮 体 系 这种方法比近期最少使用法所耗费的计数器硬件要少得多。由于页面失效后调页时间长，加上程序换道，因此主存页面表的修改可软、硬件结合地实现。在主存页面表中还可增设修改位以记录该页进入主存后是否被修改过，如未改写过，替换时就可不必写回辅存。否则，

39、需先将其写回辅存原先的位置，然后才能替换。第 4 章 存 贮 体 系 近期最少使用和近期最久未用过两种算法都是LRU法，与FIFO法一样，都是根据页面使用的“历史”情况来预估未来的页面使用状况。如果能根据未来实际使用情况将未来的近期里不用的页替换出去，一定会有最高的主存命中率，这种算法称为优化替换算法(Optimal,OPT)。它是在时刻t找出主存中每个页将要用到的时刻ti，然后选择其中ti+t最大的那一页作为替换页。显然，这只有让程序运行过一遍，才能得到各页未来的使用情况信息，所以实现是不现实的。优化替换算法是一种理想算法，可以被用来作为评价其他替换算法好坏的标准，看哪种替换算法的主存命中率

40、最接近于优化替换算法的主存命中率。第 4 章 存 贮 体 系 替换算法一般是通过用典型的页地址流模拟其替换过程，再根据所得到的命中率的高低来评价其好坏的。影响命中率的因素除替换算法外，还有地址流、页面大小、主存容量等。设有一道程序，有15页，执行时的页地址流(即依次用到的程序页页号)为：2,3,2,1,5,2,4,5,3,2,5,2 第 4 章 存 贮 体 系 若分配给该道程序的主存有3页，图4-15表示了分别用FIFO、LRU、OPT3种替换算法对这3页的使用和替换过程。其中用*号标记出按所用算法选作下次应被替换的页号。由图4-15可知，FIFO算法的页命中率最低，LRU算法的页命中率却非常

41、接近于OPT算法的页命中率。说明命中率与所选用替换算法有关。LRU算法要优于FIFO算法。第 4 章 存 贮 体 系 图4-153种替换算法对同一页地址流的替换过程 第 4 章 存 贮 体 系 命中率也与页地址有关。例如一个循环程序当所需页数大于分配给它的主存页数时，无论是FIFO算法还是LRU算法的命中率都明显低于OPT算法的命中率。图4-16就表明了这种情况。但只要将实页数增加1页，就使命中次数都增大到4次。所以，命中率又与分配给程序的主存页数有关。第 4 章 存 贮 体 系 图4-16命中率与页地址流有关 第 4 章 存 贮 体 系 一般来说，分配给程序的主存页数越多，虚页装入主存的机会

42、越多，命中率也就可能越高，但能否提高还和替换算法有关。FIFO算法就不一定。由图4-17可知，主存页数由3页增至4页时，命中率反而由3/12降低到2/12。而LPU算法则不会发生这种情况，随着分配给程序的主存页数增加，命中率一般都能提高，至少不会下降。因此，从衡量替换算法好坏的命中率高低来考虑，如果对影响命中率的主存页数n取不同值都模拟一次，工作量是非常大的。于是提出了使用堆栈处理技术处理的分析模型，它适用于采用堆栈型替换算法的系统，可以大大减少模拟的工作量。第 4 章 存 贮 体 系 图4-17FIFO算法的实页数增加，命中率反而有可能下降 第 4 章 存 贮 体 系 什么是堆栈型替换算法呢

43、?设A是长度为L的任意一个页地址流,t为已处理过t-1个页面的时间点,n为分配给该地址流的主存页数，Bt(n)表示在t时间点、在n页的主存中的页面集合，Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法满足：nLt时，Bt(n)Bt(n+1)nLt时，Bt(n)=Bt(n+1)则属堆栈型的替换算法。第 4 章 存 贮 体 系 LRU算法在主存中保留的是n个最近使用的页，它们又总是被包含在n+1个最近使用的页中，所以LRU算法是堆栈型算法。显然，OPT算法也是堆栈型算法，而FIFO算法则不是。因为从图4-17可以看出，FIFO算法不具有任何时刻都能满足上述包含性质的特征。例如，B7(

44、3)=1,2,5,而B7(4)=2,3,4,5，所以，B7(3)B7(4)。由于堆栈型替换算法具有上述包含性质，因此命中率随主存页数的增加只有可能提高，至少不会下降。只要是堆栈型替换算法，只需采用堆栈处理技术对地址流模拟一次，即可同时求得对此地址流在不同主存页数时的命中率。第 4 章 存 贮 体 系 用堆栈模拟时，主存在t时间点的状况用堆栈St表示,St是Lt个不同页面号在堆栈中的有序集,St(1)是t时间点的St的栈顶项，St(2)是t时间点的St的次栈顶项，依次类推。由于堆栈型算法的包含性，必有 nLt时，Bt(n)=St(1),St(2),St(n)nLt时,Bt(n)=St(1),St

45、(2),St(Lt)这样，容量为n页的主存中，页地址流A在t时间点的At页是否命中，只需看St-1的前n项中是否有At，若有则命中。所以，经过一次模拟处理获得St(1),St(2),St(Lt)之后，就能同时知道不同n值时的命中率，从而为该道程序确定所分配的主存页数提供了依据。第 4 章 存 贮 体 系 不同的堆栈型替换算法，St各项的改变过程不同。对于LRU算法是把主存中刚访问过的页号置于栈顶，而把最久未被访问过的页号置于栈底。设t时间点访问的页为At，若At St-1，则把At压入栈顶使之成为St(1),St-1各项都下推一个位置；若AtSt-1，则将它由St-1中取出压入栈顶成为St(1

46、)，在At之下的各项位置不动，而At之上的各项都下推一个位置。图4-18是对应于图4-15页地址流的St变化过程。第 4 章 存 贮 体 系 图4-18使用LRU算法对页地址流进行堆栈处理 第 4 章 存 贮 体 系 由图4-18的St可确定对应这个页地址流，主存页数n取不同值时的命中率。只要取栈中顶n项，若AtSt-1为命中，若ASt-1为 不 命 中。例 如，对 n=4,其 S5=5,1,2,3，因 为A6=2S5，所以命中；但对n=2，其S5=5,1，因为A6=2S5，所以不命中。这样就可算出各个n值的命中率H*，如表4-1所示。可见，LRU算法的命中率随分配给该道程序的主存页数n的增加

47、而单调上升，至少不会下降，这是堆栈型算法所共有的特点。而FIFO这种非堆栈型算法由图4-17可知，它不具备这一特点。虽然虚页在主存的机会多了，命中率总趋势应随n增加而增大，但从某个局部看，n的增加有时会使命中率降低。第 4 章 存 贮 体 系 表4-1不同实页数n的命中率H*第 4 章 存 贮 体 系 由于堆栈型替换算法有随分配给该道程序的实页数n增加，命中率H会单调上升这一特点，因此可对LRU算法加以改进，提出使系统性能更优的动态算法。即根据各道程序运行中的主存页面失效率，由操作系统动态调节分配给各道程序的实页数。当主存页面失效率超过某个值时就自动增加给该道程序的主存页数以提高其命中率；而当

48、主存页面失效率低于某个值时就自动减少分配给该道程序的主存页数，以便释放出这部分主存页面位置供给其他程序用，从而使整个系统总的主存命中率和主存利用率得到提高。我们称此算法为页面失效频率(PFF)算法。显然它是立足于主存页数增加一定会使命中率单调上升，至少不下降这一基本点上的。第 4 章 存 贮 体 系 3.虚拟存储器工作的全过程虚拟存储器工作的全过程参看图4-19，在页式虚拟存储器中每当用户用虚地址访问主存时，都必须查内页表，将多用户虚地址变换成主存的实地址、。在查内页表时，如果对应该虚页的装入位为“1”，就取出其主存页号nv，拼接上页内位移Nr，形成主存实地址np后访主存。如果对应该虚页的装入

49、位为“0”，表示该虚页未在主存中，就产生页面失效，程序换道经异常处理从辅存中调页。这时需查外页表，完成外部地址变换。在查外页表时，若该虚页的装入位为“0”，表示该虚页尚未装入辅存，产生辅存缺页故障(异常)，由海量存储器调入；若查外页表时，该虚页的装入位为“1”，就将多用户虚地址变换成辅存中的实块号Nvd，告诉I/O处理机到辅存中去调页，而后经I/O处理机送入主存。在多道程序机器中，CPU的运行与I/O处理机的调页是并行进行的。第 4 章 存 贮 体 系 图4-19页式虚拟存储器工作的全过程 第 4 章 存 贮 体 系 4.2.34.2.3页式虚拟存储器实现中的问题页式虚拟存储器实现中的问题1.

50、1.页面失效的处理页面失效的处理对于按字节编址的存储器完全可能出现指令或操作数横跨在两页上存储的情况。特别是字符串数据、操作数多重间接寻址，这种跨页现象更为严重。如果当前页在主存中，而跨页存放的那一页不在主存中，就会在取指令、取操作数或间接寻址等访存过程中发生页面失效。就是说，页面失效会在一条指令的分析或执行的过程中产生。一般，中断都是在每条指令执行的末尾安排有访中断微操作，检验系统中有无未屏蔽的中断请求，以便对其响应和处理。页面失效如果也用这种办法就会造成死机，因为不调页，指令就无法执行到访中断微操作，从而就不可能对页面失效给予响应和处理。所以，页面失效不能按一般的中断对待，应看做是一种故障