c第四章 存储器管理

第四章存储器管理4.0存储器的层次结构4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式内存(MainMemory或PrimaryMemory或RealMemory)也称主存,是指CPU能直接存取指令和数据的存储器。图

内存在计算机系统中的地位4.0存储器的层次结构高速缓存主存储器（简称内存或主存）外存储器（软盘、硬盘、光盘）磁盘内存储器：存储管理外存储器：设备管理寄存器

磁盘缓存可移动存储介质4.0存储器的层次结构功能：储存以二进位形式表示的程序和数据分类：内存储器/外存储器内存储器外存储器(简称外存或辅存)存取速度很快较慢存储容量较小(因单位成本较高)很大(因单位成本较低)性质断电后信息消失断电后信息保持用途存放已经启动运行的程序和需要立即处理的数据长期存放计算机系统中几乎所有的信息与CPU关系CPU所处理的指令及数据直接从内存中取出程序及相关数据必须先送入内存后才能被CPU使用在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步:（1）编译：由编译程序（Compiler）将用户源代码编译成若干个目标模块（ObjectModule）；（2）链接：由链接程序（Linker）将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（LoadModule）；（3）装入：由装入程序（Loader）将装入模块装入内存。4.1程序的装入和链接4.1程序的装入和链接图4-1对用户程序的处理步骤1)静态链接：在装入内存前链接成一个大的装入模块module。但需要解决两个问题，即：

(1)修改相对地址。

(2)变换外部调用符号。2)装入时动态链接：边装入边链接，即装入一个模块时，便去找它的调用模块，如有便再装入，同时修改目标模块中的相对地址。由于分开装入：便于模块更新修改；便于模块的共享。3)运行时动态链接:

将对某些目标模块的链接推迟到执行时才进行。凡在执行过程中未被用到的目标模块，都不会被调入内存或被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.1.2程序的链接图4-3程序链接示意图4.1.1程序的装入绝对装入方式可重定位装入方式（静态重定位）动态运行时装入方式（动态重定位）重要的术语：

逻辑地址，是目标程序中的地址。这种地址一般以0为基地址，顺序编址。一个作业或进程的目标程序（准确地说应是装入模块）的逻辑地址的集合称为该作业或进程的逻辑地址空间，或称地址空间或虚拟空间。逻辑地址也称相对地址或虚拟地址。

物理地址，是物理存贮器的单元地址。物理地址的集合称为物理地址空间，或称存储空间或实地址空间。物理地址也称绝对地址或实地址。

重定位：把装入模块中指令的逻辑地址以及数据的逻辑地址变换成内存中物理地址的过程称为重定位。1.绝对装入：只能将目标模块装入指定的内存位置缺点：（1）在程序中必须由程序员给出绝对地址。或者说此时的相对地址和绝对地址一样；（2）要求程序员对内存使用情况非常熟悉。事先知道自己的程序将要装在什么地方；（3）只适合于单道程序环境。例如：某个程序员想在内存200处编一个程序：Movax,[204]35h200204Movax,[204]35h装入程序逻辑地址相对地址内存中进程绝对地址物理地址….20020402.可重定位的装入：装入时将逻辑地址转换为物理地址(重定位)，逻辑地址从0开始。适合于多道程序环境。地址变换在装入时一次性完成，以后不变，可看作是静态重定位。Movax,[2500]3650100025005000例如:准备将程序装入内存10000处1000015000Movax,[2500]3651100012500Movax,[12500]365注意：这种装入后程序不便在内存中移动。Why?3.动态运行时装入：模块装入内存后没有立即重定位，仍然是相对地址；只有当CPU执行到具有相对地址的代码时才去重定位，因此是动态重定位。Movax,[2500]365010002500500010000150001100012500Movax,[2500]3652500相对地址10000重定位寄存器＋12500这种装入后程序可以内存中移动，但需要重定位寄存器的硬件支持。内存的分配提纲内存分配的总的介绍：连续分配方式--〉离散分配方式连续1.单一连续分配2.固定分区分配3.动态分区分配4.动态重定位分区分配离散1.基本分页存储管理2.基本分段存储管理3.段页式存储管理对换技术1.请求分页存储管理2.请求分段存储管理虚拟存储器4.2连续分配方式4.2.1单一连续分配最简单的一种存储管理方式将内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用只能用于单用户、单任务的操作系统例如：一个容量为256k的内存，OS占用32K。操作系统作业用户区0KB32KB96KB256KB-14.2.2固定分区分配最简单的多道程序的存储管理方式主要思想：在单一连续分配的基础上，将用户区划分成若干个固定大小的区，每个区可以放一个作业进程，多个进程并发。系统一启动后就已经分好了分区；4.2.2固定分区分配分区大小划分方法：（a）分区大小相等：缺乏灵活性，当程序太小时，内存空间浪费；当程序太大时，一个分区又不足以装入该程序。通常适合于控制多个相同对象的场合。（b）分区大小不等：将内存划分成含多个较小的分区、适量的中等分区及少量的大分区。操作系统用户区分区1分区2分区3…操作系统用户区分区5分区4分区1分区2分区34.2.2固定分区分配如何分配

（a）分区使用表：表中包含每个分区的起始地址、大小、状态。

（b）分配方法：在分区使用表中找出一个能满足要求的、尚未分配的分区。将该分区分给程序、并修改分区使用表点击鼠标：对1k、9k、33k、121k作业分配内存，并修改分区状态浪费（阴影部分）：7k23k87k211k总浪费：328k操作系统0K20K28K60K180K512k-1分区1分区2分区3分区4内存分区情况分区号起始地址大小状态1未分配2未分配3未分配4未分配180k20k8k例题：某系统采用固定分区管理方式，内存分区如图。现有大小为1k、9k、33k、121k要求进入内存，画出他们进入内存的空间分配情况，说明主存浪费多大。28k60k32k120k332k分区使用表1k9k33k121k已分配已分配已分配已分配4.2.3动态分区分配含义：根据作业进程的需要，动态的分配内存。系统刚启动时并不分区。数据结构：用来描述空闲分区和已分配分区的情况。常用的数据结构有以下两种形式：空闲分区链：以链表形式记录每个空闲分区的情况。空闲分区表：以表结构形式记录每个空闲分区的情况。例如：操作系统0K20K28K60K180K1k9k33k121k21K37K93K301K空闲分区表分区号起始地址大小状态1234301k21k7k37k93k23k87k211k空闲空闲空闲空闲4.2.3动态分区分配分配算法：（1）首次适应算法：从空闲分区表或分区链（按照地址递增次序排列）头上开始查找，找到第一个满足要求的分区为止，分配内存，余下的部分然仍留在空闲分区表中。优点：倾向于优先利用内存低地址部分的空闲分区；保留了高地址部分的空闲分区。缺点：低地址部分不断被划分，留下很多碎片.

例题：例题：已知主存有256k容量，其中os占地端内存20k，有下列作业序列：分析内存分配情况和空闲分区表情况作业1要求80k；作业2要求16k；作业3要求140k

作业1完成；作业3完成；作业4要求60k；作业5要求120k操作系统0k20k256k-1空闲分区表分区号起始地址大小120k236k作业1来到操作系统0k20k256k-1空闲分区表分区号起始地址大小1100k156k作业1100k刚开始时作业216k作业3140k分别来到后空闲分区表分区号起始地址大小1100k156k操作系统0k20k256k-1作业1100k作业2作业3116k1116k140k0作业1完成作业3完成操作系统0k20k256k-1作业1100k作业2作业3116k空闲分区表分区号起始地址大小120k80k2116k140k作业460k作业5120k（12k?)分别来到180k20k作业4作业51236k20kback4.2.3动态分区分配分配算法：（2）最佳适应算法：每次为作业分配内存时，总是找一个既能满足要求、又是最小的空闲分区分配给作业。特点：为提高程序中查找速度，常常将分配表按照分区容量按照从小到大排列，查找时只需要从表首按顺序查找最合适的。缺点：都在找最合适的分割，常会剩下一些小碎片

例题：例题：已知内存分配情况如下图。要求填写空闲分区表，并分配如下作业序列作业4大小2k，作业5大小6k，作业6大小2k操作系统作业10k20k256k-110k25k作业23k35k45k作业3156k48k100k分区号起始地址大小空闲分区表125k10k245k3k3100k156k作业4247k1k作业5131k4k作业6133k2k改进：空闲分区表（按大小排列，便于程序）分区号起始地址大小225k10k3100k156k145k3k4.2.3动态分区分配分配算法：（3）最坏适应算法每次分配总是挑选出分配表（链）中最大的分区进行分配（4）循环首次适应算法由首次适应算法演变而来（5）快速适应算法又称为分类搜索算法，将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。

看书自行理解4.2.3动态分区分配分配内存：在系统利用上述的某种分配算法，从空闲分区表（链）中找到所需大小的空闲分区之后，应进行内存的分配操作，即：

1.计算当前空闲分区的大小m.size和实际请求的分区大小u.size之差

2.若m.size-u.size<=size（size是实现规定的不在分割的剩余分区的大小），则将整个空闲分区分配给请求者。

3.若m.size-u.size>size，则从该空闲分区中按请求的大小划分出一块内存空间分配给请求者，并将剩余的部分仍留在空闲分区表（链）中。

4.将分配区的首地址返回给调用者。实际地，内存分配的操作流程亦可描述为：4.2.3动态分区分配回收内存：当进程运行完毕释放内存时，系统根据回收区的首地址，从空闲分区表（链）中找到相应的插入点，将回收区插入到空闲分区表（链）中的适当位置。此时，可能出现以下四种情况之一：

1.回收区前连空闲区

2.回收区后连空闲区

3.回收区前、后连空闲区

4.回收区前、后都不连空闲区例题：操作系统作业10k20k256k-110k25k作业23k35k45k作业3156k48k100k作业5作业6作业458k68k70k分区号起始地址大小125k10k245k3k3100k156k空闲分区表作业3完成、作业1完成、作业2完成、作业5完成作业3完成10k245k13k作业1完成5k120k15k作业2完成10k120k38k作业5完成2k268k2k4.2.4动态重定位分区分配1.动态重定位的引入思想：在动态分区分配的基础上引入“紧凑”技术（整理功能）操作系统作业10k20k256k-110k25k作业23k35k45k作业3156k48k100k操作系统作业10k20k256k-110k25k作业23k作业3156k2.动态重定位的实现动态重定位分区分配算法需与在装入时，采用“动态运行时装入”方式，才能保证程序中相对地址的正确性4.2.4动态重定位分区分配3.动态重定位分区分配算法4.2.4动态重定位分区分配动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：在找不到足够大的空闲分区来满足用户需求时应进行“紧凑”。其流程可描述为：优点:可以消除碎片,能够分配更多的分区,有助于多道程序设计,提高内存的利用率。缺点:紧凑花费了大量CPU时间;4.2.5对换(Swapping)1.对换的引入（新教材P129）所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。对换又分为：（1）整体对换即对换是以整个进程为单位的，又称进程对换。

（2）部分对换

页面对换：对换是以“页”为单位进行的。

分段对换：对换是以“段”为单位进行的。图

对换两个进程4.2.5对换(Swapping)2.对换空间的管理

为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，它们的单位是盘块号和盘块数。3.进程的换出与换入

(1)进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。4.2.5对换(Swapping)

(2)进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。4.3基本分页存储管理方式为什么会引入离散分配管理？连续分配管理（单一连续、固定分区、可变分区、可重定位分区）中的每个进程都是连续的放在内存中、要能运行一定要一段连续的空间。要求严格、浪费空间、产生很多碎片。虽然有“紧凑”、但开销大。如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无需再进行“紧凑”。基于这一思想而产生了离散分配管理方式，包括：

1.分页存储管理方式，此时离散分配的基本单位是页。在分页存储管理方式中，又根据是否具备页面对换功能，将分页存储管理方式分为：（1）基本的分页存储管理方式：要求每个作业全部装入内存后方能运行。

（2）请求分页存储管理方式

2.分段存储管理方式，此时离散分配的基本单位是段。在分段存储管理方式中，又根据是否具备分段对换功能，将分段存储管理方式分为：（1）基本的分段存储管理方式

（2）请求分段存储管理方式4.3基本分页存储管理方式分页的思想：把逻辑地址空间（程序）分成若干个大小相等的片－－页面或页，并加以编号0页、1页、2页…….把内存也分成和页面大小相等的若干个物理存储块－－物理块，并加以编号0块、1块、2块……为进程分配内存时，将进程的若干个页装入多个不相邻的块中。当一个用户程序装入内存时,以页面为单位进行分配。页面的大小是为2n,通常为1KB,2KB,nKB等。由于进程的最后一页经常装不满一页，因而形成不可以利用的碎片，称为“页内碎片”。要注意什么问题？4.3基本分页存储管理方式4.3.1页面与页表

1.页面

1)页面和物理块分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0＃块、1＃块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。

2)页面大小在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512B~8KB。4.3.1页面与页表2.地址结构分页地址中的地址结构如下：页号P位移量（或页内地址）d31121104.3.1页面与页表（a）若页内偏移d占12位，表示页面大小为4kB（b）若页号P占20位、表示页面的数目为1M页2.地址结构4.3.1页面与页表例:某系统页面大小为1k，已知地址为A=2170Byte（十进制）、问页号p是多少？页内地址d是多少？A=2170=第0页（1024）＋第1页(1024）+第2页(页内122)页号：P=2页内地址:d=122对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：2170除以1024＝2….122 例:某系统页面大小为1k，已知地址为A=4EA5h（16进制），问页号p是多少？页内地址d是多少？方法一：将A=4EA5h转化为十进制，利用上例中的方法求解：

A=4EA5h=2013320133/1024=19…….677方法二：由于地址系统是：

本题中页面大小为1k=1024是需要10位页内偏移位数0页号位数P910位将A=4EA5h转变为二进制是:0100111010100101页号：P=010011=19页内偏移地址：d=1010100101=6773.页表页表的作用是实现从页号到物理块号的地址映射。4.3.1页面与页表用户程序0页1页2页4k4k4k0块1块2块….3块19块20块….物理内存3页4k页表页号块号0113219304.3.2地址变换机构00页1页…Movax,3…102047204820492170前面的例子：某系统页面大小为1k，共有3页、分别放于内存的1、19、3物理块中。已知逻辑地址为A=2170Byte，问物理块中的地址是多少？1220块1块2块….3块19块20块….Movax,33x1k+122=3194实际的物理地址变换机构，见下一页4.3.2地址变换机构页号块号0111923a页表始址页表长度页表寄存器页号页内偏址逻辑地址A=21702122a3>+越界Na+23122物理地址＝31941.基本的地址变换机构例：在一个分页存储管理系统中、某个作业的页表如下。已知页面大小为1024字节。试将逻辑地址1011、2148、3000、4000、5012转化为相应的物理地址页号块号02132136答：1011－>30592148－>11243000－>19764000－>70725012－>越界非法2.具有快表的地址变换机构4.3.2地址变换机构在基本的地址变换机构中，页表是放在内存中的。此时，CPU存取一个数据，需要访问内存2次。

第1次，访问内存中的页表，找出逻辑地址对应的物理地址；第2次，访问内存物理地址处的数据。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，又称“快表”，用以存放当前访问的那些页表项。此时的变换过程可描述为：页号块号0111923a页表始址页表长度页表寄存器页号页内偏址逻辑地址A=21702122a3>+越界Na+23122物理地址＝3194页号块号页表快表2.具有快表的地址变换机构4.3.2地址变换机构2.具有快表的地址变换机构4.3.2地址变换机构例：某页式系统，页表存在内存中（1）如果对主存一次存取要1.5微秒、存取一个数据需要多少时间（2）如果系统有快表，平均命中率为85%，对快表的查找时间忽略为0，问此时存取一个数据要多少时间？答（1）2次访问内存2x1.5=3微秒（2）85%命中，只要访问一次内存，直接取得数据0.85x1.515％不能命中，要先访问内存快表得物理地址、在访问内存数据，共访问2次3微秒。0.15x3

需要时间：0.85x1.5+0.15x3=1.725微秒4.3.3两级和多级页表现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。在某些情况下，是不现实的。可以采用这样两个方法来解决这一问题：①采用离散分配方式来解决难以找到一块连续的大内存空间的问题；②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。1.两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：图4-14两级页表结构图4-15具有两级页表的地址变换机构

2.多级页表对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4KB即212B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。对于64位的计算机，如果要求它能支持2６４(=1844744TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。4.4基本分段存储管理方式4.4.1分段存储管理方式的引入引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要（新教材P135）：

1)方便编程

2)信息共享

3)信息保护

4)动态增长

5)动态链接4.4.2分段系统的基本原理1.分段分段地址中的地址具有如下结构：段号段内地址3116150图4-16利用段表实现地址映射2.段表图4-17分段系统的地址变换过程3.地址变换机构4.分页和分段的主要区别

(1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

(2)页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

(3)分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。4.4.3信息共享(新教材P139)图4-18分页系统中共享editor的示意图图4-19分段系统中共享editor的示意图4.4.4段页式存储管理方式1.基本原理图4-20作业地址空间和地址结构图4-21利用段表和页表实现地址映射2.地址变换过程图4-22段页式系统中的地址变换机构4.5虚拟存储器的基本概念4.5.1虚拟存储器的引入1.常规存储器管理方式的特征（新教材P142）一次性，即作业在运行前需一次性全部装入内存。(2)驻留性，即作业装入内存后，便一直驻留在内存中，直至作业运行结束。思考这样两种情形：(1)有的作业很大甚至超过了内存总容量；(2)有大量的作业要求运行，但内存容量不足以容纳所有这些作业。2.局部性原理早在1968年，

Denning.P就曾指出：

(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。

(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。

(3)程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。

(4)程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。局限性又表现在下述两个方面：

(1)时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。

(2)空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。3.虚拟存储器定义正是由于程序在执行时具有局部性规律，因此应用程序在执行之前，没有必要全部一次性装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分留在磁盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；如果尚未调入内存(缺页或缺段)，此时程序应利用OS提供的请求调页(段)功能，将它们调入内存，以使程序能继续执行下去；如果此时内存已满，无法再装入新的页(段)，则还需利用页(段)的置换功能，将内存中暂时不用的页(段)调至磁盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。3.虚拟存储器定义所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

4.5.2虚拟存储器的实现方法1.分页请求系统硬件支持。①请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；②缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存；③地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。(2)实现请求分页的软件。包括用于实现请求调页的软件和实现页面置换的软件。4.5.2虚拟存储器的实现方法2.分段请求系统硬件支持。①请求分段的段表机制；②缺段中断机构；③地址变换机构。(2)实现请求分段的软件。4.5.3虚拟存储器管理方式的特征(新教材P144)多次性即一个作业被分成多次调入内存运行。对换性即允许在作业的运行过程中进行换进换出。虚拟性即能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要的目标。4.6请求分页存储管理方式4.6.1请求分页中的硬件支持1.页表机制页号物理块号状态位P访问字段A修改位M外存地址用于指示该页是否已经调入内存用于记录该页在一段时间内被访问的次数，或者记录该页最近已有多长时间未被访问表示该页在调入内存后是否被修改过，若已被修改，则在置换该页是，必须将该页重写到外存上。用于指出该页在外存上的地址2.缺页中断机构图4-23涉及6次缺页中断的指令与一般中断相比，缺页中断有着明显的不同，主要表现在以下两个方面：(1)通常，CPU是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应；否则，继续执行下一条指令。然而，缺页中断则是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。(2)一条指令在执行期间，可能产生多次缺页中断。如右图所示。3.地址变换机构图4-24请求分页中的地址变换过程4.6.2内存分配策略和分配算法在为进程分配内存时，将涉及到三个问题：最小物理块数问题物理块的分配策略物理块分配算法4.6.2内存分配策略和分配算法1.最小物理块数的确定这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。2.物理块的分配策略在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。

先为每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从物理空闲块中取出一个物理块分配给该进程，并将欲调入的页装入其中。仅当空闲物理块队列中的物理块用完时，OS才从内存中选择一页调出，该页可能是系统中任意进程的某一页。为每个进程分配一定数目的物理块，且在整个运行期间都不再改变。若进程在运行中发现缺页，则只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页，从而保证该进程在所占内存空间不变。为每个进程分配一定数目的物理块，但当发现某进程缺页时，只允许从该进程在内存的n个页面中选出一页换出。但如果该进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若某进程在运行过程中的缺页率特别低，则可适当就减少分配给它的物理块数。1)固定分配局部置换：2)可变分配全局置换：3)可变分配局部置换：3.物理块分配算法在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用以下几种算法：

1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。

2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：bi应该取整，它必须大于最小物理块数。

3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。页面调入策略涉及到三个问题：调入页面的时机从何处调入页面页面调入的过程4.6.3调页策略4.6.3调页策略1.何时调入页面预调页策略即将那些预计在不久之后便会访问的页面预先调入内存。但遗憾的是，目前预调页的成功率较低，仅约50%。2)请求调页策略根据请求调入页面，此时调入的页面肯定是会被访问的，但这种策略每次仅调入一页，故系统开销相对较大。2.从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)若系统拥有足够的对换区空间，能使得在进程运行前，保证与该进程有关的文件，都已从文件区拷贝到对换区。这时，若发生缺页中断，则可全部从对换区调入所需页面。(2)系统缺少足够的对换区空间，即运行中的进程仅是部分页面拷贝到了对换区。这时，若发生缺页中断，则分以下两种情形：凡是不会被修改的页面，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出（直接覆盖就行），以后再调入时，仍从文件区直接调入。对于那些可能被修改的页面，若已经拷贝到对换区，则从对换区调入，否则从文件区调入。但在将它们换出时，便须调出到对换区，以后需要时，再从对换区调入。(3)UNIX方式。此时，与进程有关的页面都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。3.页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断：(1)中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。(2)该程序通过查找页表，得到该页在外存的物理块后，

(a)如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。

(b)如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出。如果该页未被修改过，可不必将该页写回磁盘；如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。(3)在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。4.8页面置换算法4.8.1最佳置换算法和先进先出置换算法

1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用顺序：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。图4-25利用最佳页面置换算法时的置换图引用顺序70770170122010320304243230321201201770101页框(物理块）2032.先进先出(FIFO)页面置换算法图4-26利用FIFO置换算法时的置换图引用顺序70770170122010323104430230321013201770201页框23042042302301271270114.8.2最近最久未使用(LRU)置换算法1.LRU(LeastRecentlyUsed)置换算法的描述图4-27LRU页面置换算法引用顺序70770170122010320304403230321132201710701页框4024320321022.LRU置换算法的硬件支持

LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。2.LRU置换算法的硬件支持

1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R0

当某页面首次进入内存时，相应寄存器的各位置为1。此时，定时信号将每隔一定时间将寄存器右移一位。注意，当进程访问该页面时，则将相应寄存器的Rn-1位置为1。那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。图4-28某进程具有8个页面时的LRU访问情况2)栈也可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的页面号，而栈底则是最近最久未是页面的页面号。图4-29用栈保存当前使用页面时栈的变化情况44747074070471704101740107