分页存储管理课件

4．3分页管理

4.3.1

分页管理的基本原理

分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。4．3分页管理分页存储管理，在该方式中，用户程序的地址被划分成划分若干个固定大小的区域，称为页（或页面）。页面的典型大小为1k；相应地将内存空间分成若干个物理块(或页框)，页和块的大小相同，这样可将用户程序的任一页放到内存的任一块中，实现离散分配。这时内存中的碎片大小不会超过一页。关键问题是实现逻辑地址到物理地址的二维动态映射，这是通过页表实现的。引入联想存贮器（超高速缓存）构成的快表可加快映射的速度。内存空间的保护是通过地址映射过程中检查页号越界来实现的。分页存储管理，在该方式中，用户程序的地址被划分成划分若干个固（1）基本分页存储管理原理1．分页 分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配内存时，将进程中若干页分别装入多个不相邻接的块中。2.地址结构 分页系统的地址结构如下图所示，它由两部分组成：前一部分为页号P；后一部分为位移量W，即页内地址。图中的地址长度为32位，其中0～11位为页内地址（每页的大小为4K），12～31位为页号，所以允许地址空间的大小最多为1M个页。

3112110

页号P位移量W（1）基本分页存储管理原理页号P页号页内地址

51025＝32（页）210＝1024（每页1024字节）在分配存储空间时,是以页面为单位来分配.例如,一个作业的地址空间有M页,那么只需要分配给他M个页面的存储空间,每一页分别装入一个存储页面即可.并不需要这些页面是连续的.以上这些问题需要一个地址映射.页号页内地址51025＝32（若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址w可按下式求得：P=INT[A/L]W=[A]MODL其中，INT是整除函数，MOD是取余函数。例：系统页面大小为１KB，设A＝2170B，则P=2,W=122若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和3.页表在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。3.页表

页表：由页号和页面号组成，指出逻辑地址中页号与主存中块号（页面号）的对应关系页号作业地址空间的页序号页面号内存空间的页面序号

页号页面号页表页表：由页号和页面号组成，页号页面号页表存储页面表一个系统只有一张存储页面表.它指出内存各页面是否被分配,以及来分配页面的总数.………

19183210

若内存被分配为1024个页面,内存单元长20比特.1024/20=52个单元.描述了1024个页面是否分配.存储页面表………19184.3.2地址变换(映射)机构1.基本的地址变换机构

地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。4.3.2地址变换(映射)机构1.基本的地址变换机构物理地址(绝对地址)

相对地址(有效逻辑地址)页面号页内地址页号页内地址页表长度页表始址控制寄存器物理地址(绝对地址)相对地址(有效逻辑地址)页面号页内地址页表长度页表始址31k2452相对地址页号页面号0213288452OS物理地址86441024*8+452=8644页表长度页表始址31k2452第0页第1页第2页第3页第4页第5页第6页

05k6k7k8k9k10k11k12k13k14k15k16k17k31k57915131016...0k1k2k3k4k5k6k0k1k2k3k4k5k6k作业1的地址空间作业1的地址空间页表图页式管理的示意图主存空间页表第0页0.0k0k作业1的地例：作业地址空间共有7个页，每页的相对地址为0~1023，1024~2047，2048~3071，…，6144~6150。其对应的主存块在页表中已列出。分别为5，7，9，15，13，10，16共7块。假定页表在主存始址为500。若该程序从第0页开始运行，且现程序计数器内容为：例：作业地址空间共有7个页，每页的相对地址为0~1023，114.……..109…0硬件动态地址转换机构工作如下：1.把该作业的页表始址（500）和页表长度（7）放入控制寄存器中。2.将程序计数器内容的页号部分（0）与控制寄存器中的页表长度（7）相比较，若页号<页表长度时转3，否则产生地址越界，终止程序运行。010014.……..109…03.将程序计数器中的页号与控制寄存器中的页表始址相加，得到该访问操作所在页号在页表中的入口地址：500+0=5004.用该地址去访页表，获得该页所对应的主存块5。5.把主存块号5与程序计数器中的页内位移相拼接，从而得到该操作所在主存的物理地址：5×1024+100=52206.根据这个地址5220，完成指定操作。3.将程序计数器中的页号与控制寄存器中的页表始址相加，得到该控制寄存器程序计数器50070(页号）

100（页内地址）>+57915131016页表内存地址寄存器5(内存块号）

100（页内地址）12345图页式地址变换过程控制寄存器程序计数器50070(页号）

页表寄存器

逻辑地址2500

页号块号

012

每页1KB(1024)

页号2页内地址452页表始址页表长度

2 4 5写出下图中逻辑地址2500所对应的物理地址

越界中断

页表寄存器

逻辑地址2500

页号块号

012

每页1KB(1024)

物理地址55725*1024+452块号5块内地址452

页号2页内地址452页表始址页表长度﹥

2 4 5逻辑地址2500所对应的物理地址

快表和联想存贮器

从上述地址转换过程可以看出，执行一次访内操作至少要访问主存两次。一次访页表，以确定所取数据或指令的物理地址；另一次是根据地址取数据或指令。这样就把程序的执行速度降低一倍。为了提高存取速度，通常设置一个专用的高速缓冲寄存器组，用来存放页表的一部分。我们把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫联想存贮器。快表和联想存贮器联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，整个系统通常只要用8~16个寄存器即可使程序执行速度大大提高。快表的格式见下图。

页号块号访问位状态位联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所对应的主存块号；访问位指示该页最近是否被访问过。“0”表示没有被访问，“1”表示访问过；“状态”位指示该寄存器是否被占用。通常“0”表示空闲，“1”表示占用。为了保证快表中的内容为现正运行程序的页表内容，在每个程序被选中时，由恢复现场程序把快表的所有状态位清“0”，或恢复已保存的快表内容。其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入快表中，若快表已满，则置换其中访问位为0的一项。另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与CPU给出的页内位移相拼接，得到访问主存的绝对地址。从而结束了快表的查找工作。一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的当利用快表进行变换时，若没有找到要查询的页时，则继续正常的转换过程，直到形成访问主存的绝对地址。而且还要把从主存页表中取出的块号和CPU给出的页号一起写入快表中状态位为0的一行中。若没有这样行存在，则写入访问位为0的某一行中，并同时置状态位和访问位为1。需要说明的是，快表的地址转换是非常快的，因为它是将页号与快表中的各行同时比较，从而大大减少了地址变换时间，基本上克服了两次访问主存的缺点。当利用快表进行变换时，若没有找到要查询的页时，则继续正常的转由于成本的原因，快表不可能做得很大，通常只能存放16~512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%～90%。例如，假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为85%，则CPU存取一个数据的平均时间T=0.85*120+0.15*220=135ns，所以访问时间只增加35%。如果不引入联想存储器，其访问将延长一倍（达200ns）。由于成本的原因，快表不可能做得很大，通常只能存放16~512具有快表的地址变换机构

越界中断

页表寄存器

逻辑地址

页号块号

页号块号020141252

快表页表物理地址

页号页内地址页表始址页表长度﹥

245块号块内地址

输入寄存器具有快表的地址变换机构4.3.3两级页表机制80386的逻辑地址有232B，如页面大小为4KB（212B），则页表项达1M个，每个页表项占用4B，故每个进程的页表占用4MB内存空间，还要求是连续的，显然这是不现实的。在80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。4.3.3两级页表机制80386的逻辑地址有232B，如两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1）和页号（外层页内地址p2）两项各占10位，偏移量（页内地址d）占12位。每页的大小为4KB。由于物理块号和页表的物理地址都占4个字节，使每页中包含1024个页表项，所以页表目录和页表的大小也都是4KB，即一页。在80386中设置了一个外层页表寄存器（CR3），用于存放页表目录的基址。两级页表的逻辑地址结构和两级页表的地址变换机构图如下：31222112110

外层页表页表物理地址

外层页号p1外层页内地址p2页内地址d外层页表寄存器++

bd两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目两级页表机制图

第0页页表（物理块号10）内存010┇110232第1页页表（物理块号25）01┇1023第N页页表（物理块号120）01

外层页表┇102310251201214323515115201……121314……32333435……151152……两级页表机制图第0页页表（物理块号4.5虚拟存储器4.6请求分页存储管理（动态页式）4.5虚拟存储器4.5虚拟存储器的基本概念（1）虚拟存储器的引入常规存储管理方式的特征是：一次性、驻留性。

1．局部性原理早在1968年P．Denning就指出过，程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间——数组的访问，往往局限于很小的范围内。4.5虚拟存储器的基本概念（1）虚拟存储器的引入所以局限性表现为：

时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。2.虚拟存储器的定义根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。所以局限性表现为：程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。程序在运行时如果它所要访问的页（段）已调入内存，便可继续虚拟存储器是具有请求调入功能和置换功能，能仅把作业的一部分装入内存便可运行作业的存储器系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储器系统。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。虚拟存储器是具有请求调入功能和置换功能，能仅把作业的一部分装（2）虚拟存储器实现方式1.请求分页系统：它是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。2.请求分段系统：它是在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。3.请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。（2）虚拟存储器实现方式1.请求分页系统：（3）虚拟存储器的特征离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。（3）虚拟存储器的特征4.6请求分页存储管理方式（动态页式）动态页式管理是在分页存储管理基础上发展起来的，指导思想：在作业运行之前，不必把作业的整个地址空间全部装入主存，而只要求当前需要的一部分装入主存即可。这样，对作业地址空间，当其作业的大小超过主存可用空间时，用户无需考虑覆盖结构，用页式存储管理实现虚拟存储器管理。这个方案可以为每个用户提供一个虚拟存储器，其虚拟空间比主存的空间大。这对编制大型程序来说，带来了很多方便。4.6请求分页存储管理方式（动态页式）

动态页式管理分为请求页式管理和预调入式管理。由于请求也是只让进程或作业的部分程序和数据驻留在内存中，因此，在执行过程中，不可避免地会在内存中虚页以及怎样处理这种情况，是请求页式管理必须解决的基本问题。取页--将哪部分装入内存置页--将调入的页放在什么地方淘汰--内存不足时，将哪些页换出内存。动态页式管理分为请求页式管理和预调入式管理。请求页式管理中的置换算法（页式淘汰算法）

为了衡量一个调度算法的优劣，先介绍几个概念。为了简单起见，假定一个作业分配的主存块数固定不变，且采用局部淘汰(淘汰一页时，只考虑本作业内部实施淘汰)。假定作业Ji共有m页，系统分配给它的主存块为n块，这里m>n。开始时，主存没有装入任何一页的信息。如果作业Ji在运行中成功访问的次数为S，不成功的访问次数为F(产生缺页中断的次数)，则作业执行过程中总的访问次数为A.这里，A=S（成功访问的次数）+F（不成功的访问次数）作业Ji执行过程中的缺页率f=F/A。

请求页式管理中的置换算法（1）请求分页中的硬件支持

它是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。1．请求分页的页表机制它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。

页号物理块号状态位P访问字段A修改位M外存地址（1）请求分页中的硬件支持页号物理块号状态位P其中各字段说明如下：状态位（存在位P）：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。其中各字段说明如下：

2．缺页中断机构 在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。3．地址变换机构 请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等，下图给出了请求分页系统的地址变换过程。2．缺页中断机构

缺页中断处理是否否 是是否产生缺页中否是断请求调页是开始（程序请求访问一页)越界中断CPU检索快表页表项是否在快表中？访问页表页是否在内存中？修改快表修改访问位和修改位形成物理地址

地址变换结束保留CPU现场

从外存中找到缺页

页号>页表长度？

内存满否？选择一页换出

该页是否被修改？

将该页写回外存

将一页从外存换入内存

修改页表

CPU从外存读缺页

启动I/O硬件

（2）页面分配1.最少物理块数在为进程分配物理块时，首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数（称为最小物理块数）。若系统为某进程所分配的物理块数少于此值时，进程将无法运行，这取决于指令的格式、功能和寻址方式。2.页面的分配和置换策略在请求分页系统中，可采取两种分配策略——固定和可变分配策略。在进行置换时，也可采取两种策略——全局置换和局部置换。于是可组合成以下三种策略：固定分配局部置换策略：它基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。如果进程在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入另一页，保证分配给该进程的内存空间不变。（2）页面分配1.最少物理块数可变分配全局置换策略：系统为每个进程分配一定数目的物理块，而OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。可变分配局部置换：根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，而不影响其它进程的运行。可变分配全局置换策略：系统为每个进程分配一定数目的物理块，而3．页面分配算法在采用固定分配策略时，可采用以下几种物理块分配方法：平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法：这是根据进程的大小按比例分配物理块。考虑优先权的分配算法：该方法是把内存中可供分配的所有物理块分成两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。3．页面分配算法(3)页面调入策略

为能使进程运行，必须事先将一部分要执行的程序和数据调入内存。1.调入页面的时机为了将进程运行时所缺的页面调入内存，可采取策略有：预调页策略是一种主动的缺页调入策略，即将那些预计在不久的将来会被访问的程序或数据所在的页面，预先调入内存。由于预测的准确率不高（50%），所以这种策略主要用于进程的首次调入。有的系统将预调页策略用于请求调页，例如在VAX/VMS操作系统中，采用了一种称为群页式的调页策略，当系统将进程所请求的页面调入内存时，也同时将其相邻的几个页面调入内存。请求调页策略是指当进程在运行中发生缺页时，就立即提出请求，由系统将缺页调入内存。目前的虚拟存储器中，大多采用此策略。但这种策略在调页时须花费较大的系统开销，如需频繁启动磁盘I/O。(3)页面调入策略为能使进程运行，必须事先将一部分要执行2.从何处调入页面在虚拟存储系统中，外存（硬盘）常常被分成两部分；文件区（用于存放文件）和对换区（用于存放对换页面）。通常，对换区的磁盘I/O速度比文件区要高。每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？在UNIX系统中，对于从未运行过的页面，都应从硬盘文件区调入；对于曾经运行过而又被换出的页面，可以从对换区调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。2.从何处调入页面（三）页面置换算法

（PageReplacementAlgorithms）在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生“抖动”（Thrashing)。即刚被换出的页很快又被访问，需重新调入，导致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称该进程发生了“抖动”（颠簸）。从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。

（三）页面置换算法

（PageReplacementAl（1）最佳（Optimal）置换算法 它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下图所示，进程运行时先将7，0，1三个页面装入内存。当进程访问页面2时，产生缺页中断，此时OS根据最佳置换算法，页面7将在第18次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面0时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了6次页面置换。4.7页面置换算法（1）最佳（Optimal）置换算法4.7页面置换算法最佳（Optimal）置换算法发生了6次面置换，9次缺页中断。最佳（Optimal）置换算法发生了6次面置换，9次缺页中断4.7页面置换算法

2.先进先出（FIFO）算法FIFO：总是淘汰最先进入主存储器的那一页。FIFO算法容易实现，但是它所依据的理由不是普遍成立的。哪些在内存中驻留很久的页，往往是被经常访问的页，结果这些常用的页都被淘汰调出，而可能又需要立即调回内存。采用FIFO算法还会产生一种奇怪现象，直观上，分配给的作业的实页越多，进程执行时发生的缺页中断率就越小，但对FIFO算法这个结论并不是绝对的。在某些情况下，当分配的页面多反而导致更多的缺页中断，这种现象称为FIFO异常现象或称Belady现象。

4.7页面置换算法所谓异常现象，即在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。所谓异常现象，即在未给进程或作业分配足它所要求的页面数时，有(2)先进先出（FIFO）置换算法

(2)先进先出（FIFO）置换算法

练习：物理块从3块增加到4块

练习：物理块从3块增加到4块Belady现象示例Belady现象示例Belady现象示例Belady现象示例（3）最近最久未使用置换算法

LRU（LeastRecentlyUsed）该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。但在实现时需要硬件的支持（寄存器或栈）。利用LRU算法对上例进行页面置换的结果如下：

（3）最近最久未使用置换算法

LRU（Least

当需要淘汰某一页时，算法选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。其理由是，如果某页被访问了，则它可能马上还要被访问，反之如果该页很长时间未被访问，则它在最近一段时间内也不会被访问。要实现LFU算法，需要付出很大的系统开销。在实际系统中，经常采用LRU的近似算法LFU和NUR。

实现：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，再将它压入栈顶。因此，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未使用页面的页面号。

2.最近最久未使用页面置换算法（LRU）当需要淘汰某一页时，算法选择离当前时间最近的一段时间A.近似算法(LFU)：当需要淘汰时，应淘汰被访问次数最少的页。一种简单的方法式为每一页设置一个计数器，每当访问一页时，就把该页对应的计数器加1，隔一个周期T，把左右计数器清0，当发生缺页中断时，选择技术值最小的页，把它淘汰，同时把所有计数器清0。A.近似算法(LFU)：当需要淘汰时，应淘汰被访问次数最少的B.最近没有使用页面淘汰算法NUR,NRU,CLOCK：当需要淘汰某一页时，从那些最近一个时期内来被访问的页中任选一页淘汰。虽然LRU算法是一种比较好的置换算法，但由于它要求有较多的硬件支持，使实现起来成本较高，在实际应用中，这是一种用得较多的算法。实现方法：在页内增设一个访问位，当这一页被访问时，硬件把它置成“1”，而没有被访问过的页，访问位为“0”。因此产生缺页中断时，可从那些访问位为0的页中选一页进行淘汰。B.最近没有使用页面淘汰算法NUR,NRU,CLOCK：当需(4)Clock置换算法

（最近未用算法NUR（NotUsedRecently））将最近一段时间未引用过的页面换出(4)Clock置换算法

（最近未用算法NUR（NotUClock置换算法Clock置换算法C.改进型的CLOCK算法：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换言之，对于修改过的页面在换出时所付出的开销将比未修改过的页面开销大。因而，新算法中还须考虑置换代价问题。由访问位A和修改位M可组成：1类（A=0,M=0）,表示该页最近既未被访问、又未被修改，是最佳淘汰页。2类（A=0,M=1）,表示该页最近未被访问、但已被修改，并不是很好的淘汰页。3类（A=1,M=0）,该页最近已被访问、又未被修改，有可能再被访问。4类（A=1,M=1）,该页最近已被访问且被修改，有可能再被访问。C.改进型的CLOCK算法：在将一个页面换出时，如果该页已被改进型CLOCK算法的执行过程：1从指针所指示的当前位置开始，扫描循环队列，寻找1类页面，将所遇到的第一个页面作为所选中的淘汰页，在第一次扫描期间不改变访问位A；2如果第一步失败，即查找一周后未遇到的1类页面，则开始第2类页面，将所遇到的第一个页面作为所选中的淘汰页。第二轮扫描期间，将所有经过的页面的访问位置0；3如果第二步也失败，则将指针返回到开始的位置（此时所有页面的访问位为0），然后重复第一步，仍不行再重复第二步，一定能找到要淘汰的页。改进型CLOCK算法的执行过程：④随机淘汰(RG)算法，在系统设计人员认为无法确定哪些页被访问的概率较低时，随机地选择某个用户页面并将其淘汰的算法。*⑤轮转法，循回换出内存可用区内一个可以被换出的页面，无论该页是刚换进或已换进内存很长时间的算法。n抖动（或称颠簸）：如果分配给进程的存储块数小于进程所需要的最小值，进程的运行将很频繁地产生缺页中断的现象。④随机淘汰(RG)算法，在系统设计人员认为无法确定哪些页被访(5)性能分析1.缺页率对有效访问时间的影响在请求分页系统中，假设存储器的访问时间ma为100ns（一般为10ns～几百ns），缺页率为p，缺页中断时间为25ms，则有效访问时间就可以表示为：有效访问时间=（1一p）×ma十p×缺页中断时间=（1一p）×0.1十p×25000=0.1十24999.9p 由上式可以看出，有效访问时间与缺页率成正比。如果缺页率为0.1%，则有效访问时间约为25μs，与直接访问存储器的有效访问时间（0.1μs）相比的时间，程序执行的性能将受到严重的影响。如果希望在缺页时，仅使有效访问时间延长不超过10%，则可计算出缺页率p=0.0000004，由此得出，要求在2500000次的访问中才发生一页缺页，即请求分页方式应保持非常低的缺页率；否则，将使程序执行速度受到严重影响。此外，提高磁盘I/O的速度，对改善请求分页系统的性能至关重要。为此，应选用高速磁盘和高速磁盘接口。(5)性能分析1.缺页率对有效访问时间的影响2.工作集程序在运行中所产生的缺页情况，会影响程序的运行速度及系统性能，而缺页率的高低又将是与每个进程所占用的物理块数目有关。这里我们简单地分析一下应为每个进程分配多少个物理块，才能把缺页率保持在一个合理的水平上。缺页率与进程所分得的物理块数目有密切关系。下图说明了的缺页率与进程分得的物理块数目N之间的关系曲线。从图中可以看出，缺页率随着所分得的物理块数目的减少而递增，并在所分到的物理块数目较少处，出现一个拐点。在拐点上限以左时，随着分到的物理块数目的增加，缺页率明显地减少；而过了拐点，在下限以右时，随着分到的物理块数目的增加，却对缺页率的改善并不明显。所以，为进程分配的物理块数，应取在该曲线的拐点左右。2.工作集缺页率拐点

所分得的物理块数工作集的理论是在1968年由Denning提出来的。他认为，程序在运行时对页面的访问是不均匀的，即往往在某段时间内的访问仅局限于较少的若干个页面，如果能够预知程序在某段时间间隔内要访问哪些页面，并能将它们提前调入内存，将会大大地降低缺页率，从而减少置换工作，提高CPU的利用率。缺页率

所谓工作集是指，在某段时间间隔（Δ）里，进程实际要访问的页面的集合。Denning认为，虽然程序只需有少量的几页在内存就可以运行，但为了使程序能够有效地运行，较少地产生缺页、就必须使程序的工作集全部在内存中。把某进程在时间t的工作集记为w（t，Δ），把变量Δ称为工作集“窗口尺寸”（WindowsSize）。正确选择工作集窗口（Δ）的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。在WindowsNT中，虚拟存储管理程序（VirtualMemoryManager)为每一个进程分配固定数量的页面，并且这个数目可以进行动态的调整。那么这个数量如何确定？又如何进行动态的调整呢？这个数目就是由每个进程的工作集来确定，并且根据主存的负荷和进程的缺页情况动态地调整其工作集。所谓工作集是指，在某段时间间隔（Δ）里，进程实际要访问

其具体的作法是：一个进程在创建时就指定了一个最小工作集，该工作集的大小是保证进程运行在主存中应有的最小页面数。但在主存负荷不太大（页面不太满）时，虚存管理程序还允许进程拥有尽可能多的页面作为其最大工作集。当主存负荷发生变化时，如空闲页架（块）不多了，虚存管理程序就使用“自动调整工作集”的技术来增加主存中可用的自由页架。方法是检查主存中的每个进程，将它当前工作集大小与其最小工作集进行比较。如果大于最小值，则从它们的工作集中移去一些页面作为主存自由页面，可为其它进程所使用。若主存自由页面仍然太小，则不断进行检查，直到每个进程的工作集都达到最小值为止。当每个工作集都已达到最小值时，虚存管理程序跟踪进程的缺页数量，根据内存中自由页面数量可以适当增加其工作集的大小。其具体的作法是：一个进程在创建时就指定了一个最小工作集，

存储保护一种是地址越界保护，另一种是通过页表控制对内存信息的操作方式提供保护。地址越界保护可由地址变换机构中的控制寄存器的值——页表长度和所要访问的虚地址相比较完成。

存取控制保护的实现则是在页表增加相应的保护位即可。

存储保护

4．3分页管理

4.3.1

分页管理的基本原理

分页存储管理是解决存储零头的一种方法。动态重定位是解决存储器零头问题的一种途径，但要移动大量信息花去不少处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。4．3分页管理分页存储管理，在该方式中，用户程序的地址被划分成划分若干个固定大小的区域，称为页（或页面）。页面的典型大小为1k；相应地将内存空间分成若干个物理块(或页框)，页和块的大小相同，这样可将用户程序的任一页放到内存的任一块中，实现离散分配。这时内存中的碎片大小不会超过一页。关键问题是实现逻辑地址到物理地址的二维动态映射，这是通过页表实现的。引入联想存贮器（超高速缓存）构成的快表可加快映射的速度。内存空间的保护是通过地址映射过程中检查页号越界来实现的。分页存储管理，在该方式中，用户程序的地址被划分成划分若干个固（1）基本分页存储管理原理1．分页 分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页框。在为进程分配内存时，将进程中若干页分别装入多个不相邻接的块中。2.地址结构 分页系统的地址结构如下图所示，它由两部分组成：前一部分为页号P；后一部分为位移量W，即页内地址。图中的地址长度为32位，其中0～11位为页内地址（每页的大小为4K），12～31位为页号，所以允许地址空间的大小最多为1M个页。

3112110

页号P位移量W（1）基本分页存储管理原理页号P页号页内地址

51025＝32（页）210＝1024（每页1024字节）在分配存储空间时,是以页面为单位来分配.例如,一个作业的地址空间有M页,那么只需要分配给他M个页面的存储空间,每一页分别装入一个存储页面即可.并不需要这些页面是连续的.以上这些问题需要一个地址映射.页号页内地址51025＝32（若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址w可按下式求得：P=INT[A/L]W=[A]MODL其中，INT是整除函数，MOD是取余函数。例：系统页面大小为１KB，设A＝2170B，则P=2,W=122若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和3.页表在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。3.页表

页表：由页号和页面号组成，指出逻辑地址中页号与主存中块号（页面号）的对应关系页号作业地址空间的页序号页面号内存空间的页面序号

页号页面号页表页表：由页号和页面号组成，页号页面号页表存储页面表一个系统只有一张存储页面表.它指出内存各页面是否被分配,以及来分配页面的总数.………

19183210

若内存被分配为1024个页面,内存单元长20比特.1024/20=52个单元.描述了1024个页面是否分配.存储页面表………19184.3.2地址变换(映射)机构1.基本的地址变换机构

地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将页号与页表长度进行比较，如果页号大于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将有效地址（逻辑地址）寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。4.3.2地址变换(映射)机构1.基本的地址变换机构物理地址(绝对地址)

相对地址(有效逻辑地址)页面号页内地址页号页内地址页表长度页表始址控制寄存器物理地址(绝对地址)相对地址(有效逻辑地址)页面号页内地址页表长度页表始址31k2452相对地址页号页面号0213288452OS物理地址86441024*8+452=8644页表长度页表始址31k2452第0页第1页第2页第3页第4页第5页第6页

05k6k7k8k9k10k11k12k13k14k15k16k17k31k57915131016...0k1k2k3k4k5k6k0k1k2k3k4k5k6k作业1的地址空间作业1的地址空间页表图页式管理的示意图主存空间页表第0页0.0k0k作业1的地例：作业地址空间共有7个页，每页的相对地址为0~1023，1024~2047，2048~3071，…，6144~6150。其对应的主存块在页表中已列出。分别为5，7，9，15，13，10，16共7块。假定页表在主存始址为500。若该程序从第0页开始运行，且现程序计数器内容为：例：作业地址空间共有7个页，每页的相对地址为0~1023，114.……..109…0硬件动态地址转换机构工作如下：1.把该作业的页表始址（500）和页表长度（7）放入控制寄存器中。2.将程序计数器内容的页号部分（0）与控制寄存器中的页表长度（7）相比较，若页号<页表长度时转3，否则产生地址越界，终止程序运行。010014.……..109…03.将程序计数器中的页号与控制寄存器中的页表始址相加，得到该访问操作所在页号在页表中的入口地址：500+0=5004.用该地址去访页表，获得该页所对应的主存块5。5.把主存块号5与程序计数器中的页内位移相拼接，从而得到该操作所在主存的物理地址：5×1024+100=52206.根据这个地址5220，完成指定操作。3.将程序计数器中的页号与控制寄存器中的页表始址相加，得到该控制寄存器程序计数器50070(页号）

100（页内地址）>+57915131016页表内存地址寄存器5(内存块号）

100（页内地址）12345图页式地址变换过程控制寄存器程序计数器50070(页号）

页表寄存器

逻辑地址2500

页号块号

012

每页1KB(1024)

页号2页内地址452页表始址页表长度

2 4 5写出下图中逻辑地址2500所对应的物理地址

越界中断

页表寄存器

逻辑地址2500

页号块号

012

每页1KB(1024)

物理地址55725*1024+452块号5块内地址452

页号2页内地址452页表始址页表长度﹥

2 4 5逻辑地址2500所对应的物理地址

快表和联想存贮器

从上述地址转换过程可以看出，执行一次访内操作至少要访问主存两次。一次访页表，以确定所取数据或指令的物理地址；另一次是根据地址取数据或指令。这样就把程序的执行速度降低一倍。为了提高存取速度，通常设置一个专用的高速缓冲寄存器组，用来存放页表的一部分。我们把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫联想存贮器。快表和联想存贮器联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，整个系统通常只要用8~16个寄存器即可使程序执行速度大大提高。快表的格式见下图。

页号块号访问位状态位联想存贮器的存取速度比主存高，但造价也高。因此只能采用少量，其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所对应的主存块号；访问位指示该页最近是否被访问过。“0”表示没有被访问，“1”表示访问过；“状态”位指示该寄存器是否被占用。通常“0”表示空闲，“1”表示占用。为了保证快表中的内容为现正运行程序的页表内容，在每个程序被选中时，由恢复现场程序把快表的所有状态位清“0”，或恢复已保存的快表内容。其中，“页号”是程序访问过的地址空间的页号，“块号”是该页所当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。当被访问的页不在快表中时，就要将由慢表找到的内存块号与虚页号填入快表中，若快表已满，则置换其中访问位为0的一项。另外，在设置快表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与CPU给出的页内位移相拼接，得到访问主存的绝对地址。从而结束了快表的查找工作。一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的当利用快表进行变换时，若没有找到要查询的页时，则继续正常的转换过程，直到形成访问主存的绝对地址。而且还要把从主存页表中取出的块号和CPU给出的页号一起写入快表中状态位为0的一行中。若没有这样行存在，则写入访问位为0的某一行中，并同时置状态位和访问位为1。需要说明的是，快表的地址转换是非常快的，因为它是将页号与快表中的各行同时比较，从而大大减少了地址变换时间，基本上克服了两次访问主存的缺点。当利用快表进行变换时，若没有找到要查询的页时，则继续正常的转由于成本的原因，快表不可能做得很大，通常只能存放16~512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%～90%。例如，假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为85%，则CPU存取一个数据的平均时间T=0.85*120+0.15*220=135ns，所以访问时间只增加35%。如果不引入联想存储器，其访问将延长一倍（达200ns）。由于成本的原因，快表不可能做得很大，通常只能存放16~512具有快表的地址变换机构

越界中断

页表寄存器

逻辑地址

页号块号

页号块号020141252

快表页表物理地址

页号页内地址页表始址页表长度﹥

245块号块内地址

输入寄存器具有快表的地址变换机构4.3.3两级页表机制80386的逻辑地址有232B，如页面大小为4KB（212B），则页表项达1M个，每个页表项占用4B，故每个进程的页表占用4MB内存空间，还要求是连续的，显然这是不现实的。在80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。4.3.3两级页表机制80386的逻辑地址有232B，如两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1）和页号（外层页内地址p2）两项各占10位，偏移量（页内地址d）占12位。每页的大小为4KB。由于物理块号和页表的物理地址都占4个字节，使每页中包含1024个页表项，所以页表目录和页表的大小也都是4KB，即一页。在80386中设置了一个外层页表寄存器（CR3），用于存放页表目录的基址。两级页表的逻辑地址结构和两级页表的地址变换机构图如下：31222112110

外层页表页表物理地址

外层页号p1外层页内地址p2页内地址d外层页表寄存器++

bd两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目两级页表机制图

第0页页表（物理块号10）内存010┇110232第1页页表（物理块号25）