1、 43 分页管理 4.3.1分页管理的基本原理 分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。q分页存储管理，在该方式中，用户程序的地址分页存储管理，在该方式中，用户程序的地址被划分成划分若干个固定大小的区域，称为页被划分成划分若干个固定大小的区域，称为页（或页面）。页面的典型大小为（或页面）。页面的典型大小为1k；相应地将；相应地将内存空间分成若干个物理块内存空间分成若干个物理块(或页框或页框)，页和块，页和块的大
2、小相同，这样可将用户程序的任一页放到的大小相同，这样可将用户程序的任一页放到内存的任一块中，实现离散分配。这时内存中内存的任一块中，实现离散分配。这时内存中的碎片大小不会超过一页。的碎片大小不会超过一页。q关键问题是实现逻辑地址到物理地址的二维动关键问题是实现逻辑地址到物理地址的二维动态映射，这是通过页表实现的。引入联想存贮态映射，这是通过页表实现的。引入联想存贮器（超高速缓存）构成的快表可加快映射的速器（超高速缓存）构成的快表可加快映射的速度。内存空间的保护是通过地址映射过程中检度。内存空间的保护是通过地址映射过程中检查页号越界来实现的。查页号越界来实现的。（1 1）基本分页存储管理原理）基
3、本分页存储管理原理1分页分页 分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配内存时，将进程中若干页分别装入多个不相邻接的块中。2.2.地址结构地址结构分页系统的地址结构如下图所示，它由两部分组成：前一部分为页号P；后一部分为位移量W，即页内地址。图中的地址长度为32位，其中011位为页内地址（每页的大小为4K），1231位为页号，所以允许地址空间的大小最多为1M个页。31 12 11 0 页号 P 位移量W 页页 号号 页内地址页内地址 5 5 10 102 25 53232（页）（页）2 2
4、101010241024（每页每页10241024字节字节）在分配存储空间时,是以页面为单位来分配.例如,一个作业的地址空间有M页,那么只需要分配给他M个页面的存储空间,每一页分别装入一个存储页面即可.并不需要这些页面是连续的.以上这些问题需要一个地址映射.若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址w可按下式求得：P=INTA/LW=AMODL其中，INT是整除函数，MOD是取余函数。例：系统页面大小为KB，设A2170B，则P=2,W=1223.3.页表页表 在将进程的每一页离散地分配到内存的多个在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存
5、中找到每个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建页面所对应的物理块。为此，系统为每个进程建立了一张立了一张页面映射表页面映射表，简称，简称页表页表（如下图（如下图所示所示）。）。每个页在页表中占一个表项，记录该页在内存中每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，就可以找到每页所对应的物理块号。可见，页表页表的作用的作用是实现从页号到物理块号的地址映射。是实现从页号到物理块号的地址映射。页表：由页号和页面号组成，指出逻辑地址中
6、页号与主存中块号（页面号）的对应关系 页号-作业地址空间的页序号 页面号-内存空间的页面序号 页页 号号页面号页面号页页 表表存储页面表 一个系统只有一张存储页面表.它指出内存各页面是否被分配,以及来分配页面的总数.19 18 3 2 1 0 若内存被分配为1024个页面,内存单元长20比特.1024/20=52个单元.描述了1024个页面是否分配.4.3.2地址变换(映射)机构1.基本的地址变换机构基本的地址变换机构地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。为了实现地址变换功能，在系统中设置页表寄存器，用
7、来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。物理地址(绝对地址)相对地址(有效逻辑地址)页面号页面号页内地址页内地址页号页号页内地址页内
8、地址页表长度页表长度页表始址页表始址控制寄存器页表长度页表长度 页表始址页表始址 3 1k2452相对地址页号页号 页面号页面号 0 2 1 3 2 88452OS物理地址 86441024*8+452=8644第0页第1页第2页第3页第4页第5页第6页05k6k7k8k9k10k11k12k13k14k15k16k17k31k57915131016.0k1k2k3k4k5k6k0k1k2k3k4k5k6k作业1的地址空间作业1的地址空间 页表 图图 页式管理的示意图页式管理的示意图主存空间页表 例：作业地址空间共有例：作业地址空间共有7 7个页，个页，每页的相对地址为每页的相对地址为0102
9、301023，1024204710242047，2048307120483071，6144615061446150。其对应的主存块在。其对应的主存块在页表中已列出。分别为页表中已列出。分别为5 5，7 7，9 9，1515，1313，1010，1616共共7 7块。假定页块。假定页表在主存始址为表在主存始址为500500。若该程序。若该程序从第从第0 0页开始运行，且现程序计页开始运行，且现程序计数器内容为：数器内容为：14.10 9 014.10 9 0 硬件动态地址转换机构工作如下：硬件动态地址转换机构工作如下：1.1.把该作业的页表始址（把该作业的页表始址（500500）和页）和页表长度
10、（表长度（7 7）放入控制寄存器中。）放入控制寄存器中。2.2.将程序计数器内容的页号部分（将程序计数器内容的页号部分（0 0）与控制寄存器中的页表长度（与控制寄存器中的页表长度（7 7）相比较，）相比较，若页号若页号+57915131016页表内存地址寄存器5(内存块号）100（页内地址）12345图图 页式地址变换过程页式地址变换过程 页表寄存器 逻辑地址2500 页号 块 号 0 1 2 每页1KB(1024)页 号2 页内地址452页表始址页表长度 2 45写出下图中逻辑地址2500所对应的物理地址 越界中断 页表寄存器 逻辑地址2500 页号 块 号 0 1 2 每页1KB(1024
11、)物理地址5572 5*1024+452块号5 块内地址452 页 号2 页内地址452页表始址页表长度 2 45逻辑地址2500所对应的物理地址快表和联想存贮器快表和联想存贮器 从上述地址转换过程可以看出，执从上述地址转换过程可以看出，执行一次访内操作至少要访问主存两次。行一次访内操作至少要访问主存两次。一次访页表，以确定所取数据或指令的一次访页表，以确定所取数据或指令的物理地址；另一次是根据地址取数据或物理地址；另一次是根据地址取数据或指令。这样就把程序的执行速度降低一指令。这样就把程序的执行速度降低一倍。为了提高存取速度，通常设置一个倍。为了提高存取速度，通常设置一个专用的高速缓冲寄存器
12、组，用来存放页专用的高速缓冲寄存器组，用来存放页表的一部分。我们把存放在高速缓冲寄表的一部分。我们把存放在高速缓冲寄存器中的页表叫快表，存器中的页表叫快表，这个高速缓冲寄这个高速缓冲寄存器又叫联想存贮器。存器又叫联想存贮器。联想存贮器的存取速度比主存高联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，但造价也高。因此只能采用少量，整个系统通常只要用整个系统通常只要用816816个寄存器个寄存器即可使程序执行速度大大提高。快即可使程序执行速度大大提高。快表的格式见下图。表的格式见下图。页号块号访问位状态位 其中，其中，“页号页号”是程序访问过的地址空是程序访问过的地址空间的页号，间的页
13、号，“块号块号”是该页所对应的主是该页所对应的主存块号；访问位指示该页最近是否被访存块号；访问位指示该页最近是否被访问过。问过。“0”0”表示没有被访问，表示没有被访问，“1”1”表表示访问过示访问过 ；“状态状态”位指示该寄存器是位指示该寄存器是否被占用。通常否被占用。通常“0”0”表示空闲，表示空闲，“1”1”表示占用。表示占用。为了保证快表中的内容为现正运行程为了保证快表中的内容为现正运行程序的页表内容，在每个程序被选中时，序的页表内容，在每个程序被选中时，由恢复现场程序把快表的所有状态位清由恢复现场程序把快表的所有状态位清“0”0”，或恢复已保存的快表内容。，或恢复已保存的快表内容。当
14、进程访问一页时，系统将页号与快表当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。在快表中，即可立即进行地址转换。当被访问的页不在快表中时，就要当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入将由慢表找到的内存块号与虚页号填入快表中，若快表已满，则置换其中访问快表中，若快表已满，则置换其中访问位为位为0 0的一项。的一项。另外，在设置快表的情况下，硬件地另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开址转换机构在进行地址变换时，同时开始两个变换过程。始两个变换过程。一个是利用主
15、存页表进行的正常变一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中常的访主存页表过程。并将快表中的块号与的块号与CPUCPU给出的页内位移相拼接，给出的页内位移相拼接，得到访问主存的绝对地址。从而结得到访问主存的绝对地址。从而结束了快表的查找工作。束了快表的查找工作。当利用快表进行变换时，若没有找到要查询的当利用快表进行变换时，若没有找到要查询的页时，则继续正常的转换过程，直到形成访问页时，则继续正常的转
16、换过程，直到形成访问主存的绝对地址。而且还要把从主存页表中取主存的绝对地址。而且还要把从主存页表中取出的块号和出的块号和CPUCPU给出的页号一起写入快表中状给出的页号一起写入快表中状态位为态位为0 0的一行中。若没有这样行存在，则写的一行中。若没有这样行存在，则写入访问位为入访问位为0 0的某一行中，并同时置状态位和的某一行中，并同时置状态位和访问位为访问位为1 1。需要说明的是，快表的地址转换需要说明的是，快表的地址转换是非常快的，因为它是将页号与快表中的各行是非常快的，因为它是将页号与快表中的各行同时比较，从而大大减少了地址变换时间，基同时比较，从而大大减少了地址变换时间，基本上克服了两
17、次访问主存的缺点。本上克服了两次访问主存的缺点。由于成本的原因，快表不可能做得很大，通常只能由于成本的原因，快表不可能做得很大，通常只能存放存放16512个页表项。例如，在个页表项。例如，在Intel80486中有中有32个。这对中、小型作业来说，已可能把全部页表项个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。分页表放入快表中。由于对程序和数据的访问往往带有局限性，所以快由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到表的命中率可以达到80%90%。例如，假设检索。例如，假设检
18、索联想存储器的时间为联想存储器的时间为20ns，访问内存的时间为，访问内存的时间为100ns，访问联想存储器的的命中率为，访问联想存储器的的命中率为85%，则，则CPU存取一个数据的平均时间存取一个数据的平均时间T=0.85*120+0.15*220=135ns，所以访问时间只增，所以访问时间只增加加35%。如果不引入联想存储器，其访问将延长一。如果不引入联想存储器，其访问将延长一倍（达倍（达200ns）。）。具有快表的地址变换机构 越界中断 页表寄存器 逻辑地址 页号 块号 页 号 块 号 0 2 0 1 4 1 2 5 2 快 表 页 表 物理地址 页 号 页内地址页表始址 页表长度 2
19、4 5块号 块内地址 输入寄存器4.3.3两级页表机制 80386 80386的逻辑地址有的逻辑地址有232B，如，如页面大小为页面大小为4KB4KB（2 21212B B），），则页表项达则页表项达1M1M个，每个页表项占用个，每个页表项占用4B4B，故每个进程，故每个进程的页表占用的页表占用4MB4MB内存空间，还要求是连续的，显然这内存空间，还要求是连续的，显然这是不现实的。是不现实的。在在8038680386中，为了减少页表所占用的连续的内存空间，中，为了减少页表所占用的连续的内存空间，采用了采用了两级页表机制两级页表机制：基本方法是将页表进行分页，：基本方法是将页表进行分页，每个页面
20、的大小与内存物理块的大小相同，并为它每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为同的物理块中，为此再建立一张页表，称为外层页外层页表表（页表目录），即第一级页表，其中的每个表目（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。中的每个表目所存放的才是页的物理块号。两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1）和页号（外层
21、页内地址p2）两项各占10位，偏移量（页内地址d）占12位。每页的大小为4KB。由于物理块号和页表的物理地址都占4个字节，使每页中包含1024个页表项，所以页表目录和页表的大小也都是4KB，即一页。在80386中设置了一个外层页表寄存器（CR3），用于存放页表目录的基址。两级页表的逻辑地址结构和两级页表的地址变换机构图如下：31 22 21 12 11 0 外层页表 页表 物理地址 外层页号p1 外层页内地址p2 页内地址d外层页表寄存器+b d两级页表机制图 第第0 0页页表（物理块号页页表（物理块号1010）内内 存存 0 0 1 1 0 0 1 1023 1 1023 2 2 第第1 1
22、页页表（物理块号页页表（物理块号2525）0 0 1 1 1023 1023 第第N N页页表（物理块号页页表（物理块号120120）0 0 1 1 外层页外层页表表 1023 102310251201214323515115201121314323334351511524.5 虚拟存储器4.6 请求分页存储管理 （动态页式）4.5 虚拟存储器的基本概念的基本概念（1 1）虚拟存储器的引入虚拟存储器的引入v 常规存储管理方式的特征是：一次性、驻留性。常规存储管理方式的特征是：一次性、驻留性。1 1局部性原理局部性原理 早在1968年PDenning就指出过，程序在执行时将呈现出程序在执行时将呈
23、现出局部局部性规律性规律，即在一段时间内，程序的执行仅局限于某个部分；，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。所以局限性表现为：时间
24、局限性时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。空间局限性空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。2.虚拟存储器的定义虚拟存储器的定义 根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时如果它所要访问的
25、页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。虚拟存储器是具有请求调入功能和置换功能，
26、能仅把作业的虚拟存储器是具有请求调入功能和置换功能，能仅把作业的一部分装入内存便可运行作业的存储器系统，它能从逻辑上一部分装入内存便可运行作业的存储器系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储器系统对内存容量进行扩充的一种虚拟的存储器系统。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。（2）虚拟存储）虚拟存储器器实现方式实现方式1.请求分页系统请求分页系统：它是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允
27、许只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。2.请求分段系统请求分段系统：它是在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。3.请求段页式系统请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。（3）虚拟存储器的特征虚拟存储器的特征 离散
28、性离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。多次性多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。对换性对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。虚拟性虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。4.64.6请求分页存储管理方式请求分页存储管理方式（动态页式）（动态页式）动态页式管理是在分页存储管理基础上动态页式管理是在分页存储管理基础上发展起来的，指导思想：在作业运行之前，发展起来的，指导思想：
29、在作业运行之前，不必把作业的整个地址空间全部装入主存，不必把作业的整个地址空间全部装入主存，而只要求而只要求当前需要的一部分装入主存当前需要的一部分装入主存即可。即可。这样，对作业地址空间，当其作业的大小超这样，对作业地址空间，当其作业的大小超过主存可用空间时，用户无需考虑覆盖结构，过主存可用空间时，用户无需考虑覆盖结构，用页式存储管理实现虚拟存储器管理。这个用页式存储管理实现虚拟存储器管理。这个方案可以为每个用户提供一个虚拟存储器，方案可以为每个用户提供一个虚拟存储器，其虚拟空间比主存的空间大。这对编制大型其虚拟空间比主存的空间大。这对编制大型程序来说，带来了很多方便。程序来说，带来了很多方
30、便。动态页式管理分为动态页式管理分为请求页式管理和预调入式管请求页式管理和预调入式管理。理。由于请求也是只让进程或作业的由于请求也是只让进程或作业的部分程序和数部分程序和数据驻留在内存中据驻留在内存中，因此，在执行过程中，不可避免，因此，在执行过程中，不可避免地会在内存中虚页以及怎样处理这种情况，是请求地会在内存中虚页以及怎样处理这种情况，是请求页式管理必须解决的基本问题。页式管理必须解决的基本问题。l取页取页-将哪部分装入内存将哪部分装入内存l置页置页-将调入的页放在什么地方将调入的页放在什么地方l淘汰淘汰-内存不足时，将哪些页换出内存。内存不足时，将哪些页换出内存。请求页式管理中的置换算法
31、请求页式管理中的置换算法 （页式淘汰算法）（页式淘汰算法）为了衡量一个调度算法的优劣，先介绍几个概念。为了衡量一个调度算法的优劣，先介绍几个概念。l为了简单起见，假定一个作业分配的主存块数固定不变，为了简单起见，假定一个作业分配的主存块数固定不变，且采用局部淘汰且采用局部淘汰(淘汰一页时，只考虑本作业内部实施淘淘汰一页时，只考虑本作业内部实施淘汰汰)。假定作业。假定作业JiJi共有共有m m页，系统分配给它的主存块为页，系统分配给它的主存块为n n块，块，这里这里mnmn。开始时，主存没有装入任何一页的信息。如果。开始时，主存没有装入任何一页的信息。如果作业作业JiJi在运行中在运行中成功访问
32、的次数成功访问的次数为为S S，不成功的访问次数不成功的访问次数为为F F(产生缺页中断的次数产生缺页中断的次数)，则作业执行过程中，则作业执行过程中总的访问总的访问次数次数为为A.A.l这里，这里，A=SA=S（成功访问的次数）成功访问的次数）+F+F（不成功的访问次数）不成功的访问次数）作业作业JiJi执行过程中的执行过程中的缺页率缺页率f=F/Af=F/A。（1 1）请求分页中的硬件支持）请求分页中的硬件支持 它是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。1请求分页的页表机制 它是在纯分页的页表机制上形成的，由于只
33、将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。页号 物理块号 状态位P 访问字段A 修改位M 外存地址其中各字段说明如下：状态位状态位（存在位P）：用于指示该页是否已调入内存，供程序访问时参考。访问字段访问字段A A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。修改位修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数
34、；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存地址外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。2 2缺页中断机构缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。3 3地址变换机构地址变换机构 请求分页系统中的地址变换机构，是在分页系统的地址
35、变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。缺页中断处理缺页中断处理 是 否 否 是 是 否 产生缺页中产生缺页中 否 是 断请求调页断请求调页 是开始（程序请求访问一页开始（程序请求访问一页)越界中断越界中断CPU检索快表检索快表页表项是否在快表中？页表项是否在快表中？访问页表访问页表页是否在内存中？页是否在内存中？修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址 地址变换结束地址变换结束保留保留CPU现场现场 从外存中找到缺页从外存中找到缺页 页号页号页
36、表长度？页表长度？内存满否？内存满否？选择一页换出选择一页换出 该页是否被修改？该页是否被修改？将该页写回外存将该页写回外存 将一页从外存换入内存将一页从外存换入内存 修改页表修改页表 CPU从外存读缺页从外存读缺页 启动启动I/O硬件硬件（2 2）页面分配）页面分配1.1.最少物理块数最少物理块数 在为进程分配物理块时，首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数（称为最小物理块数）。若系统为某进程所分配的物理块数少于此值时，进程将无法运行，这取决于指令的格式、功能和寻址方式。2.2.页面的分配和置换策略页面的分配和置换策略 在请求分页系统中，可采取两种分配策略固定和可变分配
37、策略。在进行置换时，也可采取两种策略全局置换和局部置换。于是可组合成以下三种策略：固定分配局部置换策略固定分配局部置换策略：它基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。如果进程在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入另一页，保证分配给该进程的内存空间不变。可变分配全局置换策略可变分配全局置换策略：系统为每个进程分配一定数目的物理块，而OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物
38、理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。可变分配局部置换可变分配局部置换：根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，而不影响其它进程的运行。3 3页面分配算法页面分配算法在采用固定分配策略时，可采用以下几种物理块分配方法：平均分配算法平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法按比例分配算法：这是根据进程的大小按比例分配物理块。考虑优先权的分配算法考虑优先权的分配算法：该方法是把内存中可供分配的所有物理块分成两部分：一部分按比例分
39、配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。(3)(3)页面调入策略页面调入策略 为能使进程运行，必须事先将一部分要执行的程序和数据调入内存。1.1.调入页面的时机调入页面的时机 为了将进程运行时所缺的页面调入内存，可采取策略有：预调页策略预调页策略是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于进程的首次调入。有的系统将预调页策略用于请求调页，例如在VAX/VMS操作系统中，采用了一种称为群页式的调页策略，当系统将进程所请求的页面调入内存时，也同时将其相邻的
40、几个页面调入内存。请求调页策略是指当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。2.2.从何处调入页面从何处调入页面 在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区的磁盘I/O速度比文件区要高。每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？在UNIX系统中，对于从未运行过的页面，都应从硬盘文件区文件区调入；对于曾经运行过而又被换出的页面，可以从对换区对换区调入；对于共享页面，该页面可能已由其它进程调入内存
41、，此时就无须再从对换区调入。（三）页面置换算法（三）页面置换算法（Page Replacement AlgorithmsPage Replacement Algorithms）在进程运行过程中，如果发生缺页，此时内存中又无空闲在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定。置换算法的好坏将直接影响系一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不
42、适当的算法可能会导致进程发生统的性能，不适当的算法可能会导致进程发生“抖动抖动”（Thrashing)Thrashing)。即刚被换出的页很快又被访问，需重新调入，即刚被换出的页很快又被访问，需重新调入，导致系统频繁地更换页面，以致一个进程在运行中把大部分导致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称该进程发生了时间花费在完成页面置换的工作上，我们称该进程发生了“抖动抖动”（颠簸）。（颠簸）。从理论上讲，应将那些以后不再被访问的页面换出，或把那从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。些在较长时间内不会
43、再被访问的页面换出。（1 1）最佳（）最佳（OptimalOptimal）置换算法）置换算法 它是一种理想化的算法，性能最好，但在实际上难于实它是一种理想化的算法，性能最好，但在实际上难于实现。现。即选择那些永不使用的，或者是在最长时间内不再被访即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去问的页面置换出去。但是要确定哪一个页面是未来最长时间。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常内不再被访问的，目前来说是很难估计的，所以该算法通常用来用来评价评价其它算法。其它算法。例：假定系统为某进程分配了三个物理块，并考虑有以下的例：假定系
44、统为某进程分配了三个物理块，并考虑有以下的页面号引用串：页面号引用串：7 7，0 0，l l，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，l l，2 2，0 0，l l，7 7，0 0，1 1。如下图。如下图所示，所示，进程运行时先将进程运行时先将7 7，0 0，1 1三个页面装入内存。当进程访问页面三个页面装入内存。当进程访问页面2 2时，产生缺页中断，时，产生缺页中断，此时此时OSOS根据最佳置换算法，页面根据最佳置换算法，页面7 7将在第将在第1818次才被访问，是三次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面页中将最久不被访问的
45、页面，所以被淘汰。接着访问页面0 0时，时，发现已在内存中，而不会产生缺页中断，以此类推。发现已在内存中，而不会产生缺页中断，以此类推。从从图可图可以看出，采用最佳置换算法，只发生了以看出，采用最佳置换算法，只发生了6 6次页面置换。次页面置换。4.7 4.7 页面置换算法页面置换算法最佳（最佳（OptimalOptimal）置换算法）置换算法发生了6次面置换，9次缺页中断。页面引用70120304230321201701777222222222222227770000004440000000000物理块111333333331111111缺页 xxxxxxxxx4.7 4.7 页面置换算法页
46、面置换算法 2.2.先进先出（先进先出（FIFOFIFO）算法）算法 FIFOFIFO：总是淘汰最先进入主存储器的那一页。：总是淘汰最先进入主存储器的那一页。FIFOFIFO算法容易实现，但是它所依据的理由不是普算法容易实现，但是它所依据的理由不是普遍成立的。哪些在内存中驻留很久的页，往往是被经遍成立的。哪些在内存中驻留很久的页，往往是被经常访问的页，结果这些常用的页都被淘汰调出，而可常访问的页，结果这些常用的页都被淘汰调出，而可能又需要立即调回内存。能又需要立即调回内存。采用采用FIFOFIFO算法还会产生一种奇怪现象，直观上，算法还会产生一种奇怪现象，直观上，分配给的作业的实页越多，进程执
47、行时发生的缺页中分配给的作业的实页越多，进程执行时发生的缺页中断率就越小，但对断率就越小，但对FIFOFIFO算法这个结论并不是绝对的。算法这个结论并不是绝对的。在某些情况下，当分配的页面多反而导致更多的缺页在某些情况下，当分配的页面多反而导致更多的缺页中断，这种现象称为中断，这种现象称为FIFOFIFO异常现象或称异常现象或称BeladyBelady现象现象。所谓异常现象，即在未给进程或作业分配所谓异常现象，即在未给进程或作业分配足它所要求的页面数时，有时会出现分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪的页面数增多，缺页次数反而增加的奇怪现象。现象。(2)(
48、2)先进先出（先进先出（FIFOFIFO）置换算法）置换算法 页面引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1 7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0 物理块 7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7 缺页 x x x x x x x x x x x x x x x 发生了12次页面置换，缺页次数15次。练习：物理块从3块增加到4块物理块从3 块增加到4 块。页面引用 7 0 1 2 0 3 0 4 2 3 0
49、 3 2 1 2 0 1 7 0 1 7 0 1 2 2 3 3 4 4 4 0 0 0 1 2 2 2 7 7 7 7 0 1 1 2 2 3 3 3 4 4 4 0 1 1 1 2 2 2 7 0 0 1 1 2 2 2 3 3 3 4 0 0 0 1 1 1 物理块 7 7 0 0 1 1 1 2 2 2 3 4 4 4 0 0 0 缺页 x x x x x x x x x x 发生了6 次页面置换，缺页次数10 次。Belady现象示例物理块3块。页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 5 5 5 3 4 4 1 2 3 4 1 2 2 2 5
50、 3 3 物理块 1 2 3 4 1 1 1 2 5 5 缺页 x x x x x x x x x 发生了6次页面置换，缺页次数9次。缺页率为：9/12=75%Belady现象示例物理块从3块增加到4块。页面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 4 4 5 1 2 3 4 5 1 2 3 3 3 4 5 1 2 3 4 1 2 2 2 3 4 5 1 2 3 物理块 1 1 1 2 3 4 5 1 2 缺页 x x x x x x x x x x 发生了6次页面置换，缺页次数10次。缺页率为：10/12=83.3%（3 3）最近最久未使用置换算法）最近最久未使用
