操作系统教程-第3章存储器管理

1、操作系统(co zu x tn)教程主编(zhbin) 何樱 连卫民中国水利水电出版社共一百零八页第 3 章存储器管理(gunl)3.1 存储器管理概述3.2 单用户连续存储管理方式3.3 固定(gdng)分区存储管理方式3.4 可变分区存储管理方式3.5 分页式存储管理方式3.6 分段式存储管理方式3.7 段页式存储管理方式3.8 虚拟存储管理方式共一百零八页3.1 存储器管理(gunl)概述 存储管理的主要任务是尽可能方便用户和提高主存储器的使用效率，使主存储器在成本、速度和规模之间获得较好的权衡(qunhng)。3.1.1 存储器管理的主要功能 1主存空间的分配和回收 2地址转换 3主存

2、空间的共享与保护 4主存空间的扩充共一百零八页3.1.2 存储器的层次 目前，计算机均采用分层结构的存储子系统，以便在容量、速度和价格等因素中获得较好的性价比。 图中，上面的速度快，下面的容量大。寄存器、高速缓存、主存和磁盘缓存属于OS存储管理范围，掉电后数据丢失；固定磁盘和可移动存储介质属于设备管理范围，数据可长期保存；磁盘缓存本身并不是一种实际存在的存储介质，它依托(ytu)于固定磁盘，提供对主存空间的扩充。寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质存储管理设备管理共一百零八页 寄存器访问速度最快且最昂贵，它容量小，以字（word）为单位。一个计算机系统可能包括几十个至上百个寄存

3、器，用于提高存储访问速度。比如，用寄存存放操作数，或用地址寄存器加快地址转换速度。 高速缓存的容量稍大，速度快于主存，利用它存放主存中马上要访问的指令，可大大提高执行速度。主存的速度为1s，高速缓存为0.1s。 要执行的程序必须先装入主存，根据局部性原理，只要(zhyo)将程序的一部分装入主存就可以执行，其余部分放在磁盘缓存。共一百零八页 高速缓存（cache） 高速缓存是现代计算机结构中的一个重要部件。 有些cache由硬件实现(shxin) 如，指令cache，用于暂存下一条欲执行的指令，纯硬件cache不需要os控制。 有些cache由程序员、编译系统和os实现 如，快表。 在采用cac

4、he的系统中，要注意解决数据的一致性问题。因为这时数据可能出现在不同的层次上。在多处理机的环境中，情况会更复杂。共一百零八页3.1.3 地址转换 源程序经过编译后得到的目标程序存在于它所限定的地址范围内，这个范围称为地址空间。它总是从0开始编址，是一个(y )相对于实际起始地址的相对地址，也称为逻辑地址。当将其装入内存后得到的地址才是其真正的内存存储地址，这个地址称为物理地址或绝对地址。 把程序和数据的逻辑地址转换为物理地址的过程称为地址转换或重定位。地址转换有两种方式，一种方式是在作业装入时由作业装入程序实现地址转换，称为静态地址转换；另一种方式是在程序执行时实现地址转换，称为动态地址转换。

5、 共一百零八页1静态重定位 静态重定位是在程序执行之前，由作业装入程序将程序装入内存，同时实现地址转换(zhunhun)。一旦确定下来的地址就不再改变。 LOAD A,12500 36510000110001250015000LOAD A,2500 3655000010002500图3-2 作业装入主存时的情况作业主存共一百零八页特点：静态重定位程序在内存中不能移动，而且必须连续存放。优点：不需要增加硬件地址变换装置，实现简单。缺点： 程序占用连续的存储空间。 如果没有足够大的连续空间，作业只能等待。 不能实现虚拟存储技术。 因为程序只能一次完全装入内存。 无法实现程序的共享。 不能寻址存储(

6、cn ch)区，每个程序的寻址范围只在自己的存储(cn ch)区范围内。 共一百零八页2动态重定位 动态重定位是在程序执行过程中，随着每条指令和数据的访问自动地连续地进行转换，这种重定位的实现需要硬件的帮助，一般是靠硬件地址变换机构实现的。特点：动态重定位程序在内存中可不连续存放，并可在内存中移动。优点： 可以对主存不连续分配，灵活、方便，存储效率高。 可以实现虚拟存储技术。 可以实现程序的共享。缺点： 需要增加硬件（界限寄存器、页表寄存器）。 实现存储管理的软件(run jin)算法比较复杂。共一百零八页3.1.4 存储管理方式(fngsh)全部装入部分装入连续分配单用户连续存储管理方式分区

7、分配固定分区存储管理方式可变分区存储管理方式分页式存储管理方式分段式存储管理方式段页式存储管理方式非连续分配 请求分页式虚拟存储管理方式请求分段式虚拟存储管理方式图3-3 存储管理方式层次图共一百零八页3.2 单用户连续(linx)存储管理方式 3.2.1 基本原理 单用户连续存储管理方式是一种最简单的存储管理方式，在这种管理方式下，在主存中仅驻留一道程序，整个(zhngg)用户区为一个用户所独占。当用户作业空间大于用户区时，该作业不能装入。这种分配方式仅能用于单用户、单任务的操作系统中，不能用于多用户系统和单用户多任务系统中。共一百零八页3.2.2 主存空间的分配与回收1主存空间的分配 主存

8、空间分为两个区：系统区和用户区。（1）系统区 供操作系统使用(shyng)，操作系统的常驻内存部分存放在这里。比如，DOS的文件（内部命令解释程序）。（2）用户区 存放用户作业。只能存放一道作业，并且这个程序不能大于内存容量。共一百零八页2主存空间的回收 程序执行完毕，系统全部回收所有主存空间，再分配(fnpi)给下一个作业。（只要设置一个状态：“空”或“不空”）共一百零八页3.2.2 管理特点 简单：一次全部分配，一次全部回收。 资源利用率低：每次只运行(ynxng)一个作业。 共一百零八页3.3 固定(gdng)分区存储管理方式 3.3.1 基本原理 将用户区划分为多个固定大小的区域，每个

9、区域称为(chn wi)一个分区，每个分区可装入一个作业，每个作业只能装入一个分区。分区的划分方法： 1分区大小相等 优点：划分方法简单。 缺点：大分区放小程序浪费 小分区放大程序程序无法运行 2分区大小不等 在主存中划分出多个较小的分区、适量的中等分区及少量的大分区。这样就可以满足不同大小程序的要求。共一百零八页3.3.2 主存空间的分配与回收1采用的数据结构 设置了一张分区分配表。分区分配表的内容包括分区号、起始地址(dzh)、大小、状态。分区表如下表所示。共一百零八页2主存空间的分配 在初始状态下，状态栏的初值为0。主存空间的分配步骤为：从作业队列取出一个作业。搜索分区表中状态为“0”的

10、分区。将作业大小与分区大小进行(jnxng)比较，直到找到满足条件的分区。若未找到满足条件的分区，则给出提示信息，返回第步。把作业装入该分区，作业名写入状态栏。返回第步。共一百零八页3主存空间的回收 根据作业名到分区表的状态栏中查找(ch zho)，找到后将状态栏置“0”，表示该分区空闲，可以用来装入新的作业。3.3.3 地址转换与存储保护1地址转换 因为分区的大小和个数是固定的，因此既可以采用静态重定位方式，也可以采用动态重定位方式。 共一百零八页2存储保护 存储保护是使作业只在自己(zj)的分区内进行存储，即：下限寄存器绝对地址上限寄存器，当绝对地址超出此范围时，提示“地址越界”。CPU+

11、主存下限寄存器上限寄存器逻辑地址物理地址否是地址越界低地址高地址共一百零八页例3-1 在某系统中采用固定分区分配管理方式，主存分区情况如图3-9（a）所示。现有大小为1KB、9KB、33KB、121KB的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明主存浪费(lngfi)有多大？3.3.4 管理特点 固定分区解决了单用户连续存储管理中内存只装入一道作业的问题，内存中同时装入多道作业，提高了内存利用率，并实现了并发执行。 但是，主存利用率还是存在浪费现象，因为每个作业不可能与固定分区一样大小。共一百零八页3.4 可变分区(fn q)存储管理方式3.4.1 基本原理 可变分区存储

12、管理方式是在作业要求装入主存时，根据(gnj)作业的大小动态地划分分区，使分区的大小正好适应作业的要求。各分区的大小是不确定的，主存中分区的数目也是不确定的。共一百零八页3.4.2 主存空间的分配与回收1采用(ciyng)的数据结构 共一百零八页2主存空间的分配与回收 首先初始化已分分区表（0个记录）和空闲分区表（1个记录），整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小。主存空间的分配见书中图3-11 。 当作业执行完毕回收存储区时，在已分分区表中，只要按照(nzho)作业的首地址找到相应分区，将分区的状态项置0即可；共一百零八页在空闲分区表中，回收分为(fn wi)以下四种情

13、况：（1）回收的分区前后没有相邻的空闲分区。（2）回收分区的前面有相邻的空闲区。（3）回收分区的后面有相邻的空闲分区。（4）回收分区的前后都有相邻的空闲分区。回收分区回收分区空闲分区回收分区空闲分区回收分区空闲分区空闲分区（a）（b）（c）（d）图3-6 空闲分区修改图共一百零八页3常用主存分配算法（1）最先适应分配算法（FF） 空闲分区(fn q)按地址递增的顺序排列，从头开始查找，找到第1个满足作业长度要求的空闲区，分割出作业需要的长度分配给它。优点：简单、迅速。缺点：内存区间利用率不均匀，低地址区用的多，容易产生过多的小地址碎片。改进：循环最先适应分配算法。共一百零八页（2）最优适应分配

14、算法（BF） 最优适应分配算法是按作业(zuy)要求从所有的空闲分区中挑选一个能满足作业(zuy)要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业(zuy)时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲分区表中，分配时顺序查找。优点：保留了较大的连续内存空间。缺点：容易产生碎片，每次内存回收时都要重新排序。共一百零八页（3）最坏适应分配算法（WF） 最坏适应分配算法每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用。为实现这种算法，把空闲区按长度递减(djin)次序登记在空闲分区表中，分配时顺序查找。优点：因为

15、总是对大区间分割，因此不容易产生过多的碎片。缺点：大作业的分配受影响。每次内存回收时空闲区都要重新排序。 共一百零八页3.4.3 地址(dzh)转换与存储保护物理地址CPU+主存基址寄存器限长寄存器逻辑地址否是地址越界分区始址分区末址图3-7 可变分区存储管理的地址转换共一百零八页3.4.4 管理(gunl)特点分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业数决定的。分区的大小由作业大小来定，提高了主存的使用效率。在主存分配过程中，会产生许多主存“碎片”。 有可能出现这种情况：内存空闲分区的总容量还有30k，但都是一些不超过5k的分区，这时

16、有一个10k的作业要装入，可是它只能等待。 解决的方法是：采用移动或对换技术。 共一百零八页3.4.5 采用(ciyng)的技术 1移动技术说明： 正在与外设交换信息的作业不能移动。因为外设是根据已确定的绝对地址完成信息传输的。 移动会增加系统开销一般不会轻易使用移动技术。共一百零八页2对换技术（Swapping） 对换是指把主存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据，换入主存的技术。在以下几种(j zhn)情况下需要使用对换技术：（1）必须把一部分进程调出主存，否则系统将因为主存不够而发生死锁。（2）主存中的进程全部处于阻

17、塞状态，CPU空闲，需要把内存中的阻塞进程调出，将外存中就绪进程调入。 系统开销大。 共一百零八页 对换到外存的进程存放在对换区，对换区采用(ciyng)可变分区分配方式。换出进程选择的步骤：（1）选择阻塞状态的进程，如果有多个，则选择优先级低的进程。（2）如果无阻塞进程，则选择优先级低的就绪进程。换入进程的选择： 当有空闲内存时，便执行进程的换入操作。 首先选择“就绪且换出”状态的进程换入，如果存在多个，则选择换出时间最久的进程。共一百零八页3.4.6 可变分区存储管理举例【例3-2】主存有两个空闲区F1、F2如图所示。F1为220KB，F2为120KB，另外依次有J1 、J2、J3三个作业

18、请求加载运行，它们的主存需求量分别是40KB、160KB、100KB，试比较最先适应算法(sun f)、最优适应算法(sun f)和最坏适应算法(sun f)的性能。共一百零八页3.5 分页式存储管理方式(fngsh) 页式存储管理方式与前面介绍的存储管理方式有着根本的不同：不连续存储。3.5.1 基本原理 作业分页，内存分块，页与块大小(dxio)相等，可存放在不连续的内存块中。共一百零八页页面大小： 页面小，可以减小内碎片，但页表过长，占用内存。 页面大，可减小页表长度，但会增加内碎片。地址结构： 图中地址长度为32位，页面大小为4K，最多可以有1M个页面。 因为页与块大小相同，所以，页内

19、地址与块内地址相同，所以从逻辑地址转换(zhunhun)到物理地址只是将页号置换为块号即可。共一百零八页3.5.2 主存空间的分配与回收(hushu)1采用的数据结构（1）页表页表给出了逻辑地址中的页号与主存中的块号的对应关系共一百零八页（2）主存分配(fnpi)表（作业表） 作业表记录了各作业的作业名、页表始址和页表长度，页表长度为页表中的最大序号。共一百零八页（3）位示图 位示图用于内存块的分配。对于以上例子，内存共8块，就用8位二进制数表示每一块的状态，如果一个(y )块已分配，则为1，未分配则为0，因此，上面例子的位示图可表示为： 00101011 8位正好1个字节，再用一个字节表示剩

20、余空闲块数，则位示图共需要2字节。 假如内存容量512k，块的大小为2k，共256块，那么用256个二进制位来表示这256块，共32字节，用2字节表示剩余空闲块数，共需要34字节来表示位示图。共一百零八页2主存空间的分配 首先，系统(xtng)要初始化位示图，即把位示图中的标志位全部置为“0”，空闲块数置为主存的最大块数。其分配过程见下图所示。 共一百零八页结束作业队列空？开始空闲块数=页数？初始化位示图计算该作业的页数为该作业建立页表否是否是显示主存不足，删除该作业或入队尾图3-8 页式存储管理的主存分配流程图根据位示图装入作业的每一页，修改位示图中的标记，在页表中填入页号及对应的块号从作业

21、队列中取出队首作业修改位示图中的空闲块数，并在主存分配表中填入该作业的相关记录共一百零八页3主存空间的回收（1）根据作业名在作业表中查找到页表地址。（2）取出页表。（3）逐项归还每一块。位示图中相应块的状态置0。（4）剩余块数加页数。（5）删除(shnch)页表。（6）作业表中删除该作业记录。 共一百零八页3.5.3 地址转换与存储保护1地址转换 因为页与块大小相同，所以页内地址等于块内地址，因此，地址转换的任务实际上是将逻辑地址中的页号，转换为内存中的块号即可。例如：页表如下(rxi)图所示，页长1k，用户基址为2000，将逻辑地址3000（101110111000）转换为物理地址。 共一百

22、零八页图3-9 页式系统的地址转换图14057页号=页长页表始址 页表长度 2 769页号 页内地址页表寄存器 + 0 2 1 4 2 6 3 8 页号 块号 6 769块号 越界CPU主存4865物理地址逻辑地址页长共一百零八页2页的共享与保护（1）页的共享 前面所讲的连续存储(cn ch)方式无法做到程序的共享，而页式方式因为不再是连续存储(cn ch)，因此可以实现页的共享。 共一百零八页（2）页的保护 页式存储管理方式下的保护有3情况(qngkung)：共享页的保护、不同作业所占空间的保护、逻辑地址转换成物理地址的保护。共享页的保护。其方法是在页表中设置一个权限位，指出该信息可读/写、

23、只读、只执行等权限。 不同作业所占空间的保护。通过位示图中的每个存储块的标志位，来保护已经分配到主存中的作业空间，不被新作业覆盖。 逻辑地址转换成物理地址的保护。共一百零八页3.5.4 对页式存储管理的改进1具有快表的地址变换 CPU在存取数据时，每次要访问主存两次。分页存储解决了碎片问题，提高了内存利用率，实际上是以时间做为代价的，即以时间换空间。 为了解决多次访问内存的问题，可以把页表放在一个可并行操作的存储器中，称为“联想存储器” ，又称为快表。关于联想存储器（Associative Memory） ： 不按地址而按给定内容的特征进行存取的存储器。如要对两个存储单元中的内容作某种运算，并

24、将结果存入其中一个单元，则选用按地址存取的存储器比较适宜。如果根据(gnj)某些内容特征来查找存储单元，则使用联想存储器能更快地得到结果。共一百零八页特点： 除有存储功能外，还具有信息处理功能。它能根据送来内容的特征查找存储单元。 对各个存储单元并行进行查找，因而能显著提高查找速度。组成： 联想(linxing)存储器由多个寄存器和存储体组成，要查找的变量放在寄存器中，存储体中的每个存储单元都含有存储、比较、读写、控制等电路。 因为其价格昂贵，不能做得很大，因此一个大作业的页表只能有一部分放入联想存储器。486的联想存储器是32个。从中能找到所需页的概率为90%。共一百零八页优点：查找速度(s

25、d)快，功能强。缺点：所含的电路较多，造价很高。 设访问主存时间为100ns（纳秒），访问联想存储器的时间为20ns，联想存储器的命中率为90%，则按逻辑地址访问主存的平均时间为：（100+20)*90%+(100+100+20)*10%=130ns共一百零八页2两级页表的地址转换 大作业的逻辑地址空间可能会非常大（232264） ，它的页表就会很长，有时会占据很大的存储空间。 比如(br)，逻辑地址空间232，若每页4KB，则需要1M个页表项，若每个页表项占4B，则页表需要占主存4MB。 要在主存中找到这么大的一个连续存储空间是很困难的。我们可以把页表也分页存储，页的大小与主存物理块大小相同

26、。原来页表只有一个，现在有多个页表，所以必须再为这些分散的页表再建立一个页表，称为外层页表。 外层页号、外层页内地址、页内地址 共一百零八页3.5.5 管理特点1可以使程序和数据存放在不连续的主存空间，也不必象可变分区管理那样通过增加系统开销来解决“碎片”问题，它有效地解决了“碎片”多的问题。 2通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间。另外，它要求有相应的硬件(yn jin)支持，从而增加了系统成本，也增加了系统开销。3.5.6 页式存储管理举例 共一百零八页【例3-3】设一页式存储管理系统，向用户提供逻辑

27、地址空间最大为16页，每页2048字节，主存总共有8个存储块，试问逻辑地址应为多少(dusho)位？主存空间有多大？【解】页式存储管理系统中的逻辑地址结构为：页号+页内地址。本题中，每页2048字节，所以页内地址部分地址需要占据11个二进制位；逻辑地址空间最大为16页，所以页号部分地址需要占据4个二进制位。故逻辑地址至少为15位。 由于主存共有8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等。因此，主存空间为16K。共一百零八页【例3-4】在一个页式存储管理系统中，某作业的页表如下表所示。已知页面大小(dxio)为1024字节，用户区的基址为1000，试将逻辑地址1011、2148

28、、3000、4000、5012转换为相应的物理地址。共一百零八页【例3-5】假设主存用户区大小为200MB，作业的大小为100KB，页面大小为4KB，页表项长度为4字节，采用页式存储管理(gunl)方式管理(gunl)主存，请计算位示图和页表的大小。解：200M/4K=50K=51200（块） 51200/8=6400（字节） 剩余空闲块数需要2字节。 位示图需要占用6402字节。 100K/4K*4字节=100字节 所以页表占100字节。共一百零八页3.6 分段(fn dun)式存储管理方式 3.6.1 基本原理 段式存储是将作业分段，按段存储。段是按照作业的逻辑关系划分，比如(br)：主程

29、序段、子程序段、数据段、栈段等，每个段有一个段号，每段都从0开始编址，因此段的逻辑地址是二维的，由段号和段内地址组成。 在内存中，每个段占用一段连续的存储空间，而段与段之间可不连续。如果没有足够大的连续空间，则采用移动技术，拼接出大的空间。 共一百零八页段地址结构： 在该地址结构中，一个作业(zuy)最多可有256（28）个段，每段最长为16MB（224） 。3.6.2 主存空间的分配与回收1采用的数据结构（1）段表 共一百零八页 与页表一样，CPU在存取数据时也要访问(fngwn)主存两次，一次是访问(fngwn)段表，得到段的首地址，合成物理地址后，再按物理地址访问(fngwn)主存得到数

30、据。不同的是，页表较大，不能把它们全部放入联想存储器以制成“快表”，而段表较小，通常可以将它们全部放入联想存储器中，因此，分段方式不会在速度上有太大损失。 共一百零八页（2）主存分配(fnpi)表（作业表）共一百零八页（3）空闲分区表 段式存储的内存空间分配(fnpi)类似于可变分区，需要建立一个表来记录内存中的空闲分区 。2主存空间的分配过程 其主存分配流程如图3-10所示。共一百零八页图3-10 段式存储管理主存分配开始空闲区之和段长越界段始址+段内地址段表CPU主存 段长 段始址逻辑地址物理地址8292地址越界图3-11 段式存储管理主存分配流程图段号段号页长页表页号 块号否是共一百零八

31、页3.7.4 管理特点（1）根据作业模块把作业分成若干段，再根据页面大小把每一段分成若干页，主存仍然分成与页大小相等的块。分配主存时，把作业的每一段的页分配到主存块中。（2）这种分配方式既照顾到了用户共享和使用方便的需求，又考虑到了主存的利用率，提高了系统的性能。（3）这种分配方式的空间浪费要比页式管理的多。作业各段的最后一页都有可能浪费一部分空间。另外(ln wi)段表和页表占用空间，都比页式和段式的多，增加了系统开销。共一百零八页3.8 虚拟存储管理(gunl)方式 3.8.1 基本概念1问题(wnt)的提出 人们发现，作业执行时实际上不会同时使用全部信息，有些程序段根本就不会执行，比如错

32、误处理程序。因此将作业全部装入主存降低了主存的利用率。 在作业运行时，能否不把作业的全部信息同时装入主存，而只是把当前使用的部分先装入，其余部分先放在辅存中。这样当主存空间小于作业需要量时，这个作业也能执行，同时可以装入更多的作业，使并发度得到提高。共一百零八页通过对程序执行的分析，发现了以下一些情况： 程序中只有少量分支和过程调用，大部分是顺序结构，执行的下一条指令总是紧跟在当前指令之后； 程序往往包含若干个循环(xnhun)，在循环(xnhun)过程中，在一段时间内总是在执行同一段程序； 出错处理程序仅当程序出现错误时才会用到。 程序的局部性原理 ： 程序在执行时将呈现出局部性的规律，在一

33、个时间段内，程序仅在某个部分执行，而不是对程序的所有部分具有平均的访问概率，或仅访问存储空间的某个区域。 共一百零八页2虚拟存储器的定义 虚拟存储器是指允许用户作业的逻辑地址空间大于主存储器的绝对地址空间，只把作业的一部分装入即可运行的存储器系统。 虚拟存储器的容量与主存大小无直接关系，它受限于系统的地址结构及可用的辅存容量大小 。 如果地址线是32位，则虚拟存储器的逻辑容量也称为最大容量是2324G。虚拟存储器的实际容量为主存与硬盘容量之和。如果其总和不超过地址线的范围，则是内存+外存，否则就是(jish)由地址线决定。 windows/XP就提供了4G的逻辑主存。 共一百零八页虚拟存储器的

34、好处：（1）小内存运行大作业，用户在编写程序时不必(bb)考虑内存的大小。（2）内存中可以装入更多的作业，提高了系统的并发性，从而提高了系统效率。共一百零八页3虚拟存储器存储的特点（1）离散性 作业在内存中的不连续存放，这是虚拟存储的基础。（2）多次性 先装入一部分(b fen)就开始运行，以后用到哪部分(b fen)，装入哪部分(b fen)，分多次装入。（3）对换性 需要的装入，不需要的换出。（4）虚拟性 内存的扩充是逻辑上的，借助于外存实现的，实际上并没有从物理上扩充内存。共一百零八页虚拟存储管理主要通过以下几种(j zhn)技术实现： 请求分页式、请求分段式、请求段页式。共一百零八页3

35、.8.2 分页式虚拟存储管理1基本原理 分页式虚拟存储是建立在纯分页基础上的。 将作业分页，内存分块，页和块大小相等，只将一部分页放入内存，作业就可以开始运行，当发现要运行的页不在内存时，再将外存的页装入内存，如果(rgu)内存没有空闲块，必须把一些页置换到外存，再把新页装入，作业继续运行。 共一百零八页2采用的数据结构（1）页表 页表的作用： 地址转换，它记录(jl)了页与块的对应关系。 设置访问权限。 设置各种标志位来实现相应控制功能。 表3-1 请求分页存储管理的页表结构共一百零八页 状态位 用于表示该页是否已调入主存。1在，0不在。 访问字段 用于记录本页在一段时间内被访问的次数，或最

36、近已有多长时间未被访问，提供给置换算法选择换出页面(y min)时参考。 修改位 表示该页在调入主存后是否被修改过。 外存地址 用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。 共一百零八页（2）主存分配表（作业表） 主存分配表记录主存中每个作业的作业名、页表始址、页表长度和分配的主存块数 。（3）位示图 与页式存储管理相同。（4）缺页中断机构 在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求操作系统将所缺的页调入主存。缺页中断作为中断，它同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复(huf)CPU环境等几个步骤。共一

37、百零八页 缺页中断又是一种特殊的中断，它与一般(ybn)的中断相比，有着明显的区别，主要表现如下： （1）产生中断的时间不一样。一般中断是在执行完一条指令后，检查中断请求，产生中断。缺页中断是在指令（地址转换程序）执行期间，发现所要访问的指令或数据不在主存时产生和处理的。 （2）产生中断的次数不一样。一般中断在执行一个指令后只产生一次中断，而缺页中断在一条指令执行期间就可以产生多次中断（一条指令占多个字节，可能正好分在不同页中）。 缺页中断处理过程见书中图3-37。 共一百零八页3地址转换主存管理单元MMU（完成逻辑地址到物理地址的转换）将CPU传过来的逻辑地址分解为页号和页内地址。以页号为索

38、引搜索快表（TLB），如果命中，送出块号，与页内地址合成物理地址，然后进行权限(qunxin)检查，如获通过就可以访问物理地址了。如果不命中TLB，搜索内存中的页表，如果该页在内存中，则送出块号，合成物理地址，通过权限检查后访问物理地址。如果该页不在内存中，则发出缺页中断。 到此MMU的工作已经结束，下面由存储管理软件按替换策略进行换页。共一百零八页4页面装入和清除策略 页面装入策略决定何时把一个页面装入主存。（1）请页式调入 仅当发生缺页中断时，由缺页中断处理程序装入页面。优点：只有被访问的页才调入主存，节省主存空间。缺点：开始时缺页中断次数过多，调页系统开销较大；由于每次只调入一页，增加(

39、zngji)了磁盘I/O次数。（2）预调式调入 操作系统动态预测进程可能要访问的页，预先调入主存，而且每次调入若干页面，而不是一个页面。优点：由于进程的页面大多数连续存放，一次调入多个页面减少了磁盘I/O启动次数，节省了寻道时间。缺点：调入的页不一定被使用。共一百零八页 页面清除策略是考虑何时把一个修改过的页面写回辅存。（1）请页式清除 仅当一页被替换时才将其写回辅存。由于回写和替换成对出现，进程必须等待两次I/O操作，会降低CPU效率。（2）预约式清除 操作系统(co zu x tn)定时成批对修改过的页面回写。如果一个页面在替换前又被更改，则预约式清除将毫无意义。（3）页缓冲技术 淘汰了的

40、页面进入两个队列，修改页面队列和非修改页面队列。在修改页面队列中的页定时成批回写，并加入到非修改队列；非修改页面队列中的页可再次被引用或淘汰。共一百零八页5页面分配和置换策略（1）页面分配分为固定分配和可变分配。 固定分配是指分配给作业的内存块数在作业运行期间始终保持不变。当发生缺页时，必须有一页被换出。它的缺点是缺乏灵活性。 可变分配是指分配给作业的内存块数可变，当操作系统发现进程运行的某一阶段缺页率较高，则多为其分配内存块，反之，则减少分配。 可变分配比固定分配性能好，但它必须时刻(shk)监视进程的缺页中断率，系统开销较大。 共一百零八页（2）页面置换分为局部置换和全局置换。 如果页面置

41、换算法的作用范围是整个系统，称为全局置换，如果页面置换算法局限于本进程，则称为局部页面置换算法。 全局置换策略的内存利用率较高，如果使用局部置换，即使其它进程有大量的空闲块存在，也不能使用。但全局转换对其它进程的影响较大。（3）固定分配往往和局部置换配合使用 难点： 应为每个作业分配多少个页面的主存难以确定。若太少，会频繁地出现缺页中断，降低(jingd)了系统的吞吐量；若太多，又必然使主存中驻留的作业数目减少，进而可能造成CPU空闲或其它资源空闲的情况。 共一百零八页（4）可变分配往往和全局置换配合使用 先为系统中的每个作业分配一定数目的物理块，而操作系统自身也保持一个空闲物理块队列。当某作

42、业发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该作业，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时，操作系统才从主存中选择一页调出，该页可能是系统中任一作业的页。 （5）可变分配局部置换 这种方法对其它进程影响小，而且也可以灵活(ln hu)设置分配的物理块数。 难点：选择哪个页面进行置换。如果选择的页面不合适，有可能出现“抖动”现象。 共一百零八页6. 抖动（1）抖动： “抖动”是指刚被换出的页很快又被访问，需重新调入的现象。（2）抖动危害：抖动可使系统的页面置换非常频繁，以致大部分机器时间都浪费在页面置换上，只有一小部分时间用于程序的运行，从而影响到整个系统的效率

43、。（3）如何避免抖动 减少内存中作业个数。 根据(gnj)工作集（某段时间间隔内，进程实际访问的页面集合），计算出作业所需最大内存块数，并由此确定所分内存块数。好的页面置换算法也能降低抖动的发生。共一百零八页6页面置换算法（1）最佳置换算法 （Optimal，OPT） 一个理想的置换算法是：当要调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。 例：给定(i dn)一个访问串为（6,1,3,2,1,6,1,4,5,3,1,3,5,0,2,0,1,6,1,0），可用空闲页面数为3，计算缺页中断率。 缺页次数10 缺页中断率10/20=50% 共一百零八页

44、（2）先进先出算法（First In First Out，FIFO） 它是选择最早进入主存的一页将其淘汰。它依据的是，最早进入的页面，其不再使用的可能性比最近(zujn)调入的页面要大。算法实现：把各调入主存的页按其进入主存的先后顺序连成一个循环队列，设置一个替换指针p总是指向最早进入的页面。淘汰页面时，将新页面调入p所指的位置，替换掉先前的页面，然后p向前移一步，指向下个最老的页面。p共一百零八页例：给定(i dn)一个访问串为（6,1,3,2,1,6,1,4,5,3,1,3,5,0,2,0,1,6,1,0），可用空闲页面数为3，计算缺页中断率。 缺页次数15 缺页中断率15/20=75%

45、例：给定一个访问串为（1,2,3,4,1,2,5,1,2,3,4,5），可用空闲页面数分别为3、4，计算缺页中断率。 可用空闲页面数为3： 缺页次数9 缺页中断率9/12=75% 可用空闲页面数为4： 缺页次数10 缺页中断率10/12=83%共一百零八页（3）最近最久未使用算法（Least Recently Used，LRU） 当需要淘汰某一页时，选择在最近一段时间内最久没有使用过的页，把它淘汰。这依据的是程序局部性原理，即如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可会被访问。这种算法实现的方法有两种： 第一，在页表中设置访问字段，记录该页自上次被访问

46、以来所经历的时间t，当需要淘汰一个页面时，选择时间最久的那个页面。将新页的 t 置 0，其它页t+1。缺点(qudin)：需要不断对前面访问过的页面进行记录和更新，如果由软件完成修改，则系统开销大；如果由硬件完成，则成本将加大。共一百零八页第二，利用一个特殊的栈来保存当前使用的各个页的页号。当访问某页时，则将该页的页号从栈中抽出，再将它压入栈顶。因此，栈顶始终是最新被访问的页面的编号，而栈底则是最久未使用的页号。淘汰一页时，从栈底抽出一个页号。缺点：每次产生中断，都要对栈表进行修改，整个(zhngg)系统性能将成倍降低，硬件开销大。例：给定一个访问串为（6,1,3,2,1,6,1,4,5,3,

47、1,3,5,0,2,0,1,6,1,0），可用空闲页面数为3，计算缺页中断率。 缺页次数13 缺页中断率13/20=65%共一百零八页（4）最不经常(jngchng)使用算法（Least Frequently Used，LFU） 选择到当前时间为止被访问次数最少的页置换。其实现方法是每页设置一个访问计数器，每当页面被访问时，该页面的访问计数器加“1”；发生缺页时，淘汰计数器值最小的页，同时将所有计数器清零。共一百零八页（5）时钟算法（Clock ）（NUR） 该算法采用循环队列机制构造页面队列，形成一个类似于钟表面的环形(hun xn)表，指针指向可能要淘汰的页面。淘汰那些引用位（R）为0的页。任何一个页被访问时，其引用位置1。当发生缺页时：指针扫描循环队列，把所遇到的R=1的页，置R=0，淘汰R=0的页，插入新页，置R=1。指针推进一步。如果所有页面的R=1，则指针会循环一周，停在起始位置，并淘汰这一页，插入新页，置R=1。指针推进一步。 共一百零八页 该算法存在一个问题，淘汰(toti)一个页面时，如果该页面已被修改过，必须进行回写。所以最好淘汰(toti)那些没被修