第五章存储管理

1、第五章 存储管理存储管理的目的： 1、为用户使用存储器提供方便。使用户使用计算机的过程不考虑存储器的申请、分配、保存、回收等问题，体现在以下方面： （1）每个用户均以独立方式编成，而不必关心其 程序在存储空间上的物理位置； （2）为用户提供充分大的内存空间。 2、充分发挥内存的利用率：既要为用户程序分配足够大的内存空间，又不至于浪费。 3、扩充内存容量的方法：物理扩充与逻辑扩充 4、信息保护：市内存中的数据不被非法修改。 5.1 存储管理的功能一、虚拟存储器 基本思想：利用大容量的外存空间来逻辑扩充内存，使得产生一个不受实际内存容量大小限制的逻辑的虚拟存储器，以便充分发挥内存利用率，使系统有效

2、地支持多道程序的并发执行以及解除对用户作业大小的限制。 1、虚拟存储器实现的可能性 （1）现代计算机系统的物理存储器分成内存和外存。 因内存价格昂贵，不可能用大容量的内存来存 储所有被访问的或暂时不被访问的程序和数据，而 外存价格低，适于存储大量的信息。 （2）程序执行的局部性原理 （3）编译、链接 通常由用户编写的源程序，首先要有编译程序 编译成可执行代码，然后，由链接程序把一个进程 的不同程序段连接起来以完成要求的功能。显然， 对于不同的程序段，应具有不同的地址。 a、物理地址：物理存储器中存储单元的编号。 优点：速度快； 缺点：影响并发执行的进程数； 大进程无法运行。 b、编译链接程序将

3、用户进程编译链接到一个以0位始 址的线性或多维地址空间。 静态链接：在程序执行前由链接程序对进程所含目 标代码进行连接； 动态链接：在程序执行过程中根据需要而进行的连 接。 虚拟存储器（P106第一行）：将进程中的目标代码、 数据等的虚拟地址组成的虚拟空间称为虚 拟存储器。 虚拟地址（逻辑地址） 物理地址 （4）地址变换：由逻辑地址向物理地址的转换过程。二、地址变换(P106) 内存空间（物理地址空间）：内存地址的集合。 虚拟空间的划分：使编译链接程序可以把不同的程序 模块连接到一个统一的虚拟空间。 地址重定位：把虚拟空间中已链接和划分好的内容装入 内存，并将虚拟地址映射为内存地址的过程叫 地

4、址重定位或地址映射。 1、静态地址重定位（P107） (1)方法：是在虚拟空间中程序执行之前由OS的重定位 装入程序完成地址映射工作。 (2)特点： 优点：不需要硬件支持 缺点： 使用静态重定位法进行地址变换无法实现虚拟 存贮器，因静态重定位将程序一旦装入内存之后不 能再移动，并且必须在程序执行之前将有关部分全 部装入。 进程必须占用连续的内存空间，难实现数据共 享。 2、动态地址重定位： （1）方法：在程序执行过程中，在CPU访问内存之前， 将要访问的程序或数据地址变成内存地址，动 态重定位依靠硬件地址变换机构完成。 （2）动态地址重定位机构 基地址寄存器BR（始址）、虚地址寄存器 VR偏移

5、） 则：内存地址MA MA=（BR）+（VR） （3）址映射过程： 设置基地址寄存器BR，虚地址寄存器VR 将程序段装入内存，将其占用的区域的首地址送BR； 在程序执行过程中，将要访问的虚地址送入VR中； 地址变换机构把VR和BR的内容相加，得访问的物 理地址 （4）动态重定位优点： 可以对内存进行非连续分配 动态重定位提供了实现虚拟存贮器的基础 有利于程序段共享三、内外存数据传输的控制(P108) （1）把即将执行的程序和数据段调入内存； （2）把处于等待状态的程序、数据段调出内存，为此目 的，有两种方法实现内存与外存间的控制即覆盖与 交换。 1、覆盖（overlay ）：由用户程序自己控制

6、内外存之间 的数据交换，它要求用户清楚了解程序的结构，并指 定各程序段调入内存的先后次序。 2、交换（swapping）：包括换进与换出，它是指由操作 系统把那些在内存中处于等待状态的进程换出内存，以 及把那些等待事件已经发生，处于就绪态的进程换入内 存，以及那些即将执行的程序数据调入内存。 3、请求调入方式： 在程序执行时，如访问的程序段或数据段不在内存 中，则操作系统自动地从外存将有关程序、数据调入 内存。 4、预调入方式：由OS预测在不远的将来会访问到的那 些程序、数据部分，并在他们被访问之前由系统选择 适当的时机将它们调入内存的方法。 5、区分交换与覆盖： （1）交换不需要程序员给出程

7、序、数据段的交换方法、 过程，而覆盖要求明确给出程序段之间的覆盖结构 （2）交换主要是在进程之间进行，而覆盖主要是在一 个进程内或一个作业内进行，同时覆盖程序段与被覆 盖程序段是无关的。 6、 区分请求式调入与预调入 （1）二者一般是在一个进程内的不同程序段、数据 段间进行； （2）请求式调入命中率为100%，但程序执行速度慢， 预调方式命中率100%四、内存分配与回收 1、任务：存贮管理模块为每一个并发执行的进程分配 内存空间，另外，当进程执行结束后，存贮管理模块 又要及时回收该进程所使用的内存资源，以便给其他 进程分配本内存。 2、设计内存分配和回收方法时，要考虑的策略及数据结 构如下：

8、（1）分配结构：空闲区表、空闲区队列（链） （2）放置策略：选择空闲区方法 （3）交换策略 （4）调入策略 （5）回收策略五、内存信息的共享和保护 内存信息共享 内存保护 常用的内存信息保护方式： 1、 上下界保护法： 方法：为每个进程设置一对上下界寄存器，存贮被保护 程序和数据段的起始地址和终止地址。程序执行 过程中，在对内存进行访问操作时进行地址合法 性检查，即检查经过重定位后的内存地址是否在 上下界寄存器所规定范围内。若在规定范围内， 则访问是合法的。否则是非法的，并产生访地越 界中断。 2、保护键法： 方法：为每一个被保护存贮块分配一个单独的保护键。 在程序状态字中设置相应的保护键开关

9、字段，对 不同进程赋予不同的开关代码，与保护的存贮块 中的保护键匹配，保护键可设置成对RW同时进行 保护或只对R、W进行单独保护的。如果开关字与 保护键匹配或存贮块未受到保护，则访问该存贮 块是允许的，否则产生访问出错中断。 3、界限寄存器与CPU的用户态或核态工作方式相结合 的保护方式，在这种方式下，用户态进程只能访问 那些在界限寄存器所规定范围内的内存部分，而核 心态进程则可以访问整个内存区域。 内存空间：由若干存储单元组成的，每个存贮单元 有一编号，这一编号可唯一标识一个存 贮单元，称内存地址。 逻辑空间：源程序经过汇编或编译后，形成目标程序， 每个目标程序均以0为基址顺序进行编址， 原

10、来用符号名访问的单元用数据单元 号取代，这样生成的目标程序占据一定的 地址空间，称为作业的逻辑地址空间。 5.2分区存贮管理 一、分区管理的基本原理： 给内存中的每一个进程划分一块适当大小的存贮区，以连续存放各进程的程序与数据，使各进程得以并发执行。 1、固定分区法：（也称静态分区管理） （1）方法：将内存区域固定地划分为若干大小不等的 区域，分区划分的原则 由系统操作员或OS决定。 （2）数据结构PPT（partition describe table) 分区说明表 （3）特点 每个分区在表中对应一个表目（行），表目内容 包括区号、大小、起始地址，使用状态等。 2、 动态分区法：（可变分区管

11、理） （1）方法：作业执行前不建立分区，分区的建立是 在作业的处理过程中进行的，且其大小可随作业 或进程对内存的要求而改变， （2）数据结构：（分区说明表）(P112) 可用表 自由表 请求表二、分区的分配与回收： 1、 固定分区时的分配与回收、 （1）分配：当用户程序要装入执行时，通过请求表提 出内存分配要求和所要求的内存空间大小，存贮管 理程序根据请求查询分区说明表，从中找出一个满 足要求的空闲分区，并将其分配给申请者。 分配算法如图5.10 2、 动态分区的分配与回收 （1）动态分配与回收要解决以下三个问题： 对于请求表中的要求内存长度，从可用分区表或 自链中寻找出合适的空闲区进行分配。

12、 分配空闲区之后，更新可用表或自由链。 进程或作业释放内存资源时，各相邻的空闲区进 行链接合并，更新可用分区表或自由链。 （2）常用的三种分配算法： A、 最先适应算法：（FFA） 可用分区表或自由链的组织：按起始地址递增的 次序将可用分区或自由链排列起来。 分配：从头搜索可用分区表或自由链，一旦找到 大于或等于所要求内存长度的分区，则结束搜索。 然后从所找到的分区中划出所要求的内存长度分 配给用户进程，并把余下的部分（进行合并后） 留在可用表中。 特点：内存利用率低，易产生碎片 算法实现简单，速度快。 B、最佳适应算法： 可用分区组织：按空闲分区的从小到大次序组织 可用分区表或自由链 。 分

13、配：当用户作业或进程申请一个空闲分区时， 存贮管理程序从表头开始查找，当找到第一个满 足要求的时，停止查找，如果该分区长度大于请 求表中的请求长度，则将减去请求长度后的剩余 空闲区部分留在可用表中 特点： 优点：自由分区表或可用链中尾部的空闲区容量 大，便于大服务业运行。 缺点：更容易形成碎片。 C、最坏适应算法：（MF） 空闲分区组织：按空闲分区容量从大到小次序组 织可用表或自由键。 分配：当用户作业或进程请求一个空闲区时，先 检查可用分区表或自由链的第一个空闲区的大小 是否大于或等于所要求内存长度，若第一个的长 度小于分配请求，则分配失败，否则从空闲区可 用分区表或自由链中分配相应的存贮空

14、间给用户， 然后修改和调整空闲区可用表或自由键。 特点：优不易产生碎片 缺大作业往往无法运行。 3、动态分区时的回收与拼接 可用分区拼接(P114) 图5.12(四种情形) 4、几种分配算法的比较： 从查找速度，释放速度、空闲区利用三方面进行比较（1）最先适应算法：搜索速度，回收速度快，同时尽可 能地利用了低地址空闲，保证了高地址端有较大的空 闲区来放置要求内存较多的进程作业。（2）最佳适应算法：找到的空闲区最佳（3）最坏适应算法：克服了碎片问题，但大作业往往无 法运行。三、有关分区管理其他问题的讨论： 1、关于虚存的讨论： 在分区管理中，每个用户进程所需内存容量是受分 区大小限制的 2、关于

15、内存扩充 所谓内存扩充，是指通过覆盖或交换技术来扩 充内存。 3、关于地址变换和内存保护。 地址变换分：静态地址重定位 动态地址重定位 内存保护 4、 分区存贮管理的主要优缺点： （1）优点： 实现了多个服务业或进程对内存的共享，有助于多 道程序设计，从而提高了系统资源的利用率 该方法要求的硬件支持少，管理算法简单 （2）缺点： 内存利用率仍然不高 作业或进程的大小受分区大小控制，除非配合采用 覆盖和交换技术。 难以实现各分区间的信息共享。 5.3 覆盖与交换技术一、覆盖技术 1、 概念： 所谓覆盖，指一内存区可以被不同的程序段重复使用，当某一程序段不再需要时，另一程序段可以占用它的位置，把可

16、以在其上进行覆盖的内存区域称为“覆盖区”，而可以相互覆盖的程序为“覆盖”。 2、基本思想： 程序的执行具有局部性特征 程序在CPU上执行，在一个绝对时刻，CPU只能执 行一条指令，在一个相对较短的时间段内，又只有一 个和谐段被执行。 程序的划分： 由于程序的执行具有局部性特征，因此在程序执 行前没有必要将程序全部加载到内存，而且只装入一 个或若干个程序段。为此，需将程序进行划分，将那 些不会同时执行的程序段共享同一内存区 程序段的执行与覆盖： 当内存中的程序段执行结束，再将外存中它的 后键程序段加载内存，原来的程序段被覆盖。 3、覆盖的实现要求： （1）要求程序员提供一个清楚的覆盖结构，搞清楚

17、程 序应分为多少段，每段的前起后键各是什么。 （2）要求程序员清楚了解程序所属进程的虚拟空间以 及各程序段所在虚拟空间位置。 （3）要求程序员了解系统和内存的内部结构和地址划 分情况 4、例（备课本）二、交换技术： 1、概念：交换是指先将内存某部分的程序或数据写入 外存交换区，再从外存交换区中调入指定的程序或数 据到内存中来，并让其执行的一种内存扩充技术。 2、引入交换原因：多道程序系统中，同时执行好几个 作业或进程，但是同时存在于内存中的作业或进程， 有的处于执行状态或变绪状态，而有的则于等待状态 ，一般来说，等待较长，如果让处于等待状态的进程 继续驻留内存，将会造成存储空间浪费，因此，应把

18、 处于等待态进程换出内存。 3、交换与覆盖区别： 交换不需要程序员给出程序段之间的覆盖结构，而 覆盖要求明确给是等程序段之间的覆盖结构。 交换是进程之间或作业之间进行，而覆盖主要在同 一作业内来进程内进行内。同时覆盖程度段与被覆 盖程序段之间是无关的。5.4 分页管理 分区管理的缺陷：系统对于每个存储要求，都分配一片连续的内存空间，导致碎片的产生和内存利用率不高。一、实现原理 1、作业（进程）空间的划分： （1）系统将作业（进程）地址空间分成一些大小 相等的块，每一块称为一个页，叫逻辑页。长 度为1KB-4KB. （2）例：如作业被分成L页，编号为1,2,3,L-1，每一 个自然数叫页号或逻辑

19、页号，其逻辑地址由页号和页内偏移地址确定；表示成序偶（p,d）即： 2、内存空间的划分：将内存空间分成大小可与逻辑页相 等的若干块，每块叫内存块（物理页）。设内存总容量 为2S，页长为2r，则内存页数目为2 s-r=m，从低地址开 始编号为0,1,2,m-1，其中每一个整数叫物理页号。 物理地址=块号x页长+偏移 3、作业空间与内存空间的关系 （1）页表:当作业（进程）运行时，先将其各逻辑页加 载道内存的物理页中，作业（进程）的所有逻辑页号 是连续的，而该进程获得的物理页号是不连续的，为 此需要建立一个数据结构页表，反映逻辑页与物 力页间的对应关系。pd逻辑地址=px页长+d逻辑页号 物理页号

20、（2）页表控制寄存器：包括页表基地址和页表长度，有 的系统建立一个总页表。二、地址映射 （1）指令本身得到逻辑地址，分离出逻辑页号L和页内 地址b； （2）将L与长度寄存器值m比较，若0=L=m，则从 始址寄存器取得页表始址，找到与L相应的物理页号L；若L不满足0=L=m，则发出越界访问错误信息； （3）由物理页号L与b进行地址合成，得到逻辑地址所指示的物理单元； （4）进行操作，取指令； （5）转（1）。三、快表进程标志页表始址长度 （1）目的：提高地址映射速度； （2）设快表的方法：设置一组寄存器，用以存储当前 进程的页表的一部分，这样有效地避免地址映射过 程中频繁地访问内存中的页表。 （

21、3）快表的组成： a、一个快表通常含8-16个寄存器。 b、每个寄存器组存储页表的一个表目，包括逻辑 页号、物理页号、访问值和状态四项，前两项由 页表直接取得，状态项表示该表目是否空表目， 访问值表示该页表当前被访问的频率获该表目建 立的次序，的便于置换快表的表目。 四、引入快表之后的地址映射过程： （1）指令产生逻辑地址L,b； （2）由逻辑页号l查页表的物理页页号l； 如找不到，则： a、由逻辑页号l和页表长度寄存器中的内容m比较， 判断是否满足0=l=m，如不满足则产生越界错误； b、如满足0=l=m，由逻辑页号l和页表首址寄存器 内容查页表的物理页号L，将逻辑页号l和物理页号 L一起置

22、于快表中，若此时快表已满，则淘汰一个； c、转步骤(2)。 （3）由物理页号L和页内地址b合成的物理地址。 五、数据结构、存储分配： 1、内存分块（页）表MBT 整个系统一个，用于记录所有内存快的使用情 况，表目数等于内存块总数，各内存块按序对应一 个表目，表目号即块号。 2、页表PMT 每个用户进程一个， 用以记录进程实体的地址 空间与内存空间之间的对应关系， 地址空间中的各 内存块号 状态 占用者名 页按序对应表目中的一个表目，表目号等于逻辑页 号，表长等于逻辑页总数。 3、计数变量freeblocks：记录当前空闲块数目。 4、存储块分页算法（略）六、关于碎片 一个作业占有的各块除最后一

23、块外均不存在碎 片，最后一块存在碎片，小于块长。 5.5分段管理与段页式管理 一、分段管理 （一）分段的引入 1、分页管理的优点：实现了内存分配的非连续性， 解决了碎片问题，从而大大提高了内存利用率。 缺点：对作业或进城实体的分页不是按其内部 的逻辑结构和关系；一页中的内容通常不是完 整的程序和数据逻辑段，导致一个逻辑段可能 被分成若干页，不通逻辑段也可能在同一个页 内，这使程序段或数据段的共享、保护变得困 难。 2、引入：为了解决页式存储管理中共享数据和程序段 的困难，引入一种以作业（进程）逻辑段为单位分 配内存的方法，这就是分段管理。（二）实现原理： 1、思想：把作业（进程）按内容或过程（

24、函数）关系 分成段，每段叫做逻辑段，每段有其段名，在分配内 存时，以逻辑段为单位分配。 2、实现： （1）内存空间的划分：内存空间被动态地分成若干长 度不等的区域，每个区域等于相应程序段长度，叫 物理段。 物理地址：每个物理段中存储单元地址由两个值决 定，即段首址和段内偏移。 物理地址=段首址+段内偏移 = （2）进程空间的划分： 进程空间被静态地划分成长度不等的区域，每个 区域为一个逻辑段，它是具有一定功能和结构的相对 独立的程序单位。 逻辑地址：源程序经过编译后的地址，由段号和段内 偏移量组成。 段名：每个逻辑段有一个符号名称，用以标志该段。段首址段内偏移 段号：将一个作业（进程）的所有逻

25、辑段从0开始编 号，这个自然数叫段号。 （3）进程空间与内存空间的对应关系： 进程的一个逻辑段与内存中的一个物理段相 对应，一个进程的多个逻辑段可存于内存中若干 部相连的物理段中。 （4）所需表目 A、段表：用于记录一个进程各段在内存的起始地址 和长度，从而反映逻辑空间与物理空间的关系。 逻辑段号 内存始址 长度 B、段表控制寄存器（一个系统一个该表） 物理段始址寄存器 段长度寄存器 C、进程表：用于记录个进程段表始址及长度，位于 OS空间。 D、空闲表：用于记录内存中空闲的物理区域，便于进 行内存分配。 进程标识 段表始址 表长度 始址 长度 E、一组联想寄存器快表 用于保存正在运行的进程段

26、表的一部分（投影）。 （5） 地址映射： 指令产生逻辑地址（段号S、段内偏移量lad）； 由段号查快表得到段首址、段长； 若找不到，则： a、由段号S与段表长度寄存器内容l进行比较，是否 满足0=S=l，如不满足则越界； b、由段号及段表首址寄存器内容查内存中的段表， 得到段号S对应的物理段始址和长度，将首址和 长度写入快表（可能存在淘汰） c、转 由段内地址lad和长度leng比较，是否满足 0=lad=leng，如不满足则越界。 由段首址与段内地址相加得物理地址。 （三） 分段与分页的共享： 1、分段的共享： 为了实现不同进程对内存中同一物理段的共享， 方法是通过它的段表来实现，一两个进程

27、共享一段为 例：设甲进程的段号Si，乙进程的段号为Sj，若Si、 Sj对应同一个物理段的始址和长度，则甲乙两进程实 现对该物理段的共享。 2、分页的共享： 与分段的共享相同，即让一个进程的一个逻辑页 号Pi与另一个进程的逻辑页号Pj对应同一个物理页号 PP，则实现了两个进程对PP的共享。二、段页式管理 （一）基本原理： 1、思想：用分段向用户提供二维的编程空间，以方 便用户编程，利用分页来管理内存空间，以提高 内存的利用率。 2、实现： （1）内存空间的划分： 内存空间被静态地划分成若干长度相等的区域，内存空间被静态地划分成若干长度相等的区域， 每个区域长为每个区域长为 2i，称为一个物理页面

28、。，称为一个物理页面。 （2 2）进程空间的划分：）进程空间的划分： 与段页式存储管理相同，进程空间被静态地划分与段页式存储管理相同，进程空间被静态地划分 为长度不等的区域为长度不等的区域逻辑段，与页式存储相同，在逻辑段，与页式存储相同，在 进行进程存储管理时，每段空间被静态地分成若干长进行进程存储管理时，每段空间被静态地分成若干长 度若干长度为度若干长度为2i的区域，每个区域称为一个逻辑页面。的区域，每个区域称为一个逻辑页面。 逻辑地址：逻辑地址： （3 3）内存空间与进程空间之间的对应关系：）内存空间与进程空间之间的对应关系： 段号 逻辑页号 页内地址 进程空间的一个逻辑页面对应内存空间的

29、一个物进程空间的一个逻辑页面对应内存空间的一个物 理页面，同一段的逻辑页面是连续的，而对应的物理理页面，同一段的逻辑页面是连续的，而对应的物理 页面是不连续的。（如图所示：备课本）页面是不连续的。（如图所示：备课本） （4 4）所需表目：）所需表目： A、段表：每个进程一个，用于记录进程各段的页表、段表：每个进程一个，用于记录进程各段的页表 始址和页表长度；始址和页表长度； B、页表：此表每个段一个，用于记录段中各逻辑页、页表：此表每个段一个，用于记录段中各逻辑页 与物理页号之间的对应关系；与物理页号之间的对应关系； C、进程表：用于记录各进程段表的首址及长度，、进程表：用于记录各进程段表的首

30、址及长度， 一一 个系统。个系统。 D、空闲表：用于记录内存页中空闲页情况。、空闲表：用于记录内存页中空闲页情况。 （5 5）所需寄存器：）所需寄存器： A、段表首址寄存器、段表首址寄存器 B、段表长度寄存器、段表长度寄存器 C、快表、快表 （6 6）地址映射）地址映射 A、由指令产生逻辑地址，包括段号、由指令产生逻辑地址，包括段号s、逻辑页号、逻辑页号lp、 页内偏移页内偏移lad； B、由段号、由段号s和逻辑页号查快表得物理页号，如果找不和逻辑页号查快表得物理页号，如果找不 到：到： a、由段号和页表长度寄存器中的内容、由段号和页表长度寄存器中的内容l进行比较，进行比较， 判断是否满足判断

31、是否满足0=s=l，如果不满足则越界，产生，如果不满足则越界，产生 中断；中断； b、由段号和段表始址寄存器内容查段表得页表首、由段号和段表始址寄存器内容查段表得页表首 址和页表长度；址和页表长度； c、由逻辑页号、由逻辑页号lp与页表长度与页表长度l相比较，判断相比较，判断 0=lp=l,如不满足则越界，产生中断；如不满足则越界，产生中断； d、由逻辑页号与页表首址查对应的物理页号；、由逻辑页号与页表首址查对应的物理页号； e、将段号、逻辑页号和物理页号合在一起送入快、将段号、逻辑页号和物理页号合在一起送入快 表；表； f、转、转b； C、由物理页号和页内地址合成为物理地址。、由物理页号和页

32、内地址合成为物理地址。 （二）特点（二）特点 1、优点：、优点： （1）方便用户、使用户对进程在内存中的映射可见；）方便用户、使用户对进程在内存中的映射可见； （2）内存利用率高，克服了碎片问题。）内存利用率高，克服了碎片问题。 2、缺点：方法复杂，软件、硬件开销大。、缺点：方法复杂，软件、硬件开销大。 动态页式存储管理（动态页式存储管理（P122） (虚拟页式存储管理虚拟页式存储管理)一、类型：一、类型： 1、请求页式存储管理：、请求页式存储管理： 进程执行前只让程序、数据的一部分内容进入内进程执行前只让程序、数据的一部分内容进入内 存，其他部分则在执行过程中动态调入，当访问某条存，其他部分

33、则在执行过程中动态调入，当访问某条 指令时发现它在外存而不在内存，则发生缺页中断，指令时发现它在外存而不在内存，则发生缺页中断， 系统将外存中相应的页面调入内存。系统将外存中相应的页面调入内存。 2、预调入方式：、预调入方式： 在缺页中断发生之前，事先调入处于外存中的还在缺页中断发生之前，事先调入处于外存中的还 未被访问的页面。未被访问的页面。二、问题：二、问题： 为了实现虚拟存储管理，需要解决以下问题：为了实现虚拟存储管理，需要解决以下问题： 1、页表的改进、页表的改进 2、置换算法的选择：当内存中无空闲页面时，把调入的、置换算法的选择：当内存中无空闲页面时，把调入的 页放在什么地方。页放在

34、什么地方。三、请求页式管理中的置换算法三、请求页式管理中的置换算法 1、随机淘汰算法、随机淘汰算法 2、轮转法和、轮转法和FIFO 特点：内存利用率不高；特点：内存利用率不高； 缺页中断率高，有时甚至产生缺页中断率高，有时甚至产生Belady现象。现象。 页号 页面号 中段位外存地址改变位 （1）Belady现象：现象： 是一种异常现象，由于缺页中断发生时，置是一种异常现象，由于缺页中断发生时，置 换算法的不合理及程序执行顺序的随机性，呆滞给换算法的不合理及程序执行顺序的随机性，呆滞给 进程分配的内存页面越多，而缺页中断不但不降低进程分配的内存页面越多，而缺页中断不但不降低 反而升高的现象。反

35、而升高的现象。 例例1、 例例2、 （见备课本）（见备课本） 3、最近最久未使用页面淘汰算法（、最近最久未使用页面淘汰算法（P126） LRU （1）基本思想：当需要淘汰一页时，选择离当前时间最）基本思想：当需要淘汰一页时，选择离当前时间最 近的一段时间内最久没有使用过的页面先淘汰。近的一段时间内最久没有使用过的页面先淘汰。 （2）特点：因要记录每个内存页面的访问情况，系统开）特点：因要记录每个内存页面的访问情况，系统开 销较大。销较大。 （3）比较常用的近似算法：）比较常用的近似算法： A、最不经常使用的页面淘汰算法、最不经常使用的页面淘汰算法-LFU a、思想：当需要淘汰一页时，首先淘汰到

36、当前为、思想：当需要淘汰一页时，首先淘汰到当前为 止，被访问次数最少的一页；止，被访问次数最少的一页； b、实现方法：为每个内存页增设一个访问计数器。、实现方法：为每个内存页增设一个访问计数器。 B、最近没有使用页面淘汰算法、最近没有使用页面淘汰算法-NUR a、思想：选择最近一个时期内未被访问的页面进、思想：选择最近一个时期内未被访问的页面进 行淘汰。行淘汰。 b、实现：为每个内存页增设一个访问位即可实现。、实现：为每个内存页增设一个访问位即可实现。 当某页被访问时，访问位置为当某页被访问时，访问位置为1，否则置为，否则置为0。 且系统周期性地对所有访问位清且系统周期性地对所有访问位清0。

37、4、理想型淘汰算法（、理想型淘汰算法（OPT） 淘汰在访问串中将来再也不会出现的或离当前最远淘汰在访问串中将来再也不会出现的或离当前最远 的位置上出现的页。的位置上出现的页。四、存储保护（四、存储保护（P127） 法法1：地址越界保护，通过地址变换机构中的控制寄存器：地址越界保护，通过地址变换机构中的控制寄存器 的值的值页表长度和要访问的虚地址相比较来完成。页表长度和要访问的虚地址相比较来完成。 法法2：存取控制保护，通过在页表中增加相应的保护位实：存取控制保护，通过在页表中增加相应的保护位实 现。现。五、页式存储管理的优缺点五、页式存储管理的优缺点(P127) 1、优点、优点 （1）由于他不要求作业或进程的程序段、数据段在内）由于他不要求作业或进程的程序段、数据段在内 存中连续存放，从而有效地解决了碎片问题。存中连续存放，从而有效地解决了碎片问题。 （2）动态页式存储管理提供了内存和外存统一管理的虚）动态页式存储管理提供了内存和外存统一管理的虚 存实现方法，使用户可以利用的存储空间大大增加，存实现方法，使用户可以利用的存储空间大大增加，