第 3章 存储器管理
3.1 存储器管理概述
3.2 单用户连续存储管理方式
3.3 固定分区存储管理方式
3.4 可变分区存储管理方式
3.5 页式存储管理方式
3.6 段式存储管理方式
3.7 段页式存储管理方式
3.8 虚拟存储管理方式本章结束！
3.1 存储器管理概述
3.1.1 存储器管理的主要任务存储器管理的主要任务 是为用户作业分配主存空间,提高主存的使用效率,并从逻辑上扩充主存空间,使主存在成本,速度和规模之间获得较好的权衡 。
第 3章 存储器管理
3.1 存储器管理概述
3.1.2 存储器管理的主要功能
1．主存空间的分配和回收主存分配的主要任务是采用一定的数据结构，按照一定的算法为每一道程序分配主存空间，使它们“各得其所”，并记录主存空间的使用情况和作业的分配情况。
主存空间的回收是指当一个作业运行结束后，必须归还所占用的主存空间，即在记录主存空间使用情况的数据结构中进行修改，并且把记录作业分配情况的数据结构删除。
2．地址转换将用户程序的逻辑地址转换为运行时的物理地址的过程称为地址转换，也称为地址映射（即重定位）。
第 3章 存储器管理
3.1 存储器管理概述
3.1.2 存储器管理的主要功能
3．主存空间的共享与保护在多道程序设计系统中，同时进入主存执行的作业可能需要调用相同的程序或数据，这就是主存的共享。例如，调用编译程序进行编译，把这个编译程序存放在某个区域中，各作业要调用时就访问这个区域，因此这个区域就是共享的。同样也可以实现公共数据的共享。
在实现主存分配与共享时，必须解决主存中信息的保护问题。
存储保护的工作一般由硬件和软件配合实现。
4．主存空间的扩充提供虚拟存储器的管理功能，使用户编写程序时不必考虑主存的实际容量，使计算机系统有一个比实际主存容量大得多的存储空间。这样就可以运行较多的程序和较大的程序。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
1．源程序的执行过程在多道程序环境下，程序要运行必须先将程序和数据装入主存。那么，如何将一个用户源程序变为一个在主存中可执行的程序呢？通常需要经过编译、链接和装入等几个步骤，其控制步骤如图 3-1所示。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
2．程序的装入将一个装入程序代码装入主存时，可以采用三种方式：
（ 1）绝对装入方式。 绝对装入方式是由装入程序根据装入程序代码中的地址将程序和数据装入主存。
（ 2）可重定位方式。 可重定位方式是由装入程序根据主存当前的实际使用情况，将装入程序代码装入到主存适当的地方。
（ 3）动态运行时装入方式。 绝对装入方式只能将装入程序代码装入到主存中事先指定的位臵。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
3．程序的链接链接程序的功能是将经过编译或汇编后所得到的一组目标程序以及它们所需要的库函数装配成一个完整的装入程序代码。实现链接的方法有三种：
（ 1）静态链接。
（ 2）装入时动态链接。
（ 3）运行时动态链接。
第 3章 存储器管理
3.1 存储器管理概述
3.1.4 存储管理方式对主存的存储管理方式，根据是否把作业全部装入，全部装入后是否装入到一个连续的存储区域，可以分为如图 3-3所示的几种管理方式。
第 3章 存储器管理返回
3.2 单用户连续存储管理方式
3.2.1 基本原理这是最早出现的一种存储管理方式 。
在主存中仅驻留一道程序,整个用户区被一用户独占 。 当用户作业空间大于用户区时,该作业不能装入 。
这种分配方式仅能用于单用户单任务的操作系统中,不能用于多用户系统和单用户多任务系统中 。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
1．主存空间的分配采用单用户连续存储管理方式时，主存分为两个分区，即系统区和用户区，如图 3-4所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
1．主存空间的分配
（ 1）系统区是仅提供给操作系统使用的主存区，它可以以驻留在主存的低地址部分，也可以驻留在主存的高地址部分。
（ 2）用户区是指除系统区以外的主存空间，提供给用户使用。
在这种管理方式下，主存分配的流程如图 3-5所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
2．主存空间的回收作业一旦进入主存，就要等到它结束后，系统才能回收作业所占用的空间。在这种管理方式下，回收主存空间不需要做任何操作，直接装入第二个作业即可。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
1．地址转换因为主存所有空间归一个用户作业使用，所以它采用静态分配方式，即在作业被装入主存时，一次性完成地址转换。
采用这种管理方式时，处理器设臵两个寄存器：界限寄存器和重定位寄存器。界限寄存器用来存放主存用户区的长度，重定位寄存器用来存放用户区的起始址。一般情况下这两个寄存器的内容是不变的，只有当操作系统占有的存储区域改变时才会改变。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
1．地址转换地址转换过程如图 3-6所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
2．存储保护处理器在执行指令时，检查逻辑地址是否小于界限寄存器的值。若小于，则与重定位寄存器中的基址相加，产生物理地址，
到主存中去执行。否则，产生一个“地址越界”中断信号，由操作系统进行处理，以达到存储保护的目的。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.4 管理特点
(1)管理简单。 它把主存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。
它需要很少的软硬件支持，且便于用户了解和使用。
(2)在主存中的作业 不必考虑移动 的问题，并且主存的回收不需要任何操作。
(3)资源利用率低。 不管用户区有多大，它一次只能装入一个作业，这样就造成了存储空间的浪费，使系统整体资源利用率不高。
(4)这种分配方式 不支持虚拟存储器 的实现。
第 3章 存储器管理返回
3.3 固定分区存储管理方式
3.3.1 基本原理固定分区存储管理方式是最早使用的一种可以运行多道程序的存储管理方式。它要求把作业全部装入主存，且装入一个连续的存储空间。
在这种管理方式下，把主存中可以分配的用户区预先划分成若干个大小固定的区域，每一个区域称为一个分区，每个分区可以装入一个作业，一个作业也只能装入一个分区中。这样就可以装入多个作业，使它们并发执行。当有一个空闲分区时，便可以从外存的后备作业队列中，选择一个适当大小的作业装入该分区；
当该作业运行结束时，又可以从后备作业队列中选择另一个作业装入该分区。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
1．采用的数据结构在固定分区存储管理方式下，为了记录各个分区的使用情况，
方便主存空间的分配与回收操作，就建立了一张分区分配表。分区分配表的内容包括分区序号、始址、大小、状态。如表 3-1所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配在作业分配之前，根据主存分区的划分情况，在分区分配表中填入每个分区的起始地址（简称始址）、大小，在状态栏中一律填入,0”，表示该分区可用。当作业装入时填入作业名。
当有作业申请主存空间时，主存空间的分配步骤为：从作业队列中取出队首作业，检查分区分配表，选择状态标志为,0”的分区，并将作业地址空间的大小与状态标志为,0”的分区的大小进行比较，当所有分区长度都不能容纳该作业时，则该作业暂时不能装入，显示主存不足的信息。当某一个分区长度能容纳该作业时，
则把作业装入该分区，并把作业名填到该分区的状态栏里，然后，
再分配下一个作业。
在这种管理方式下，主存空间的分配流程如图 3-7所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配例如，某台计算机的主存大小为 500KB，前 100KB
为系统区，其余的空间为用户区，并将其划分为四个分区，划分情况如图 3-8所示。各分区的初始状态为,0”，
表示可用。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配现有一个作业申请队列 J1,J2,J3,J4,J5，大小分别为
30KB,20KB,40KB,100KB,70KB，按固定分区分配主存空间后，分区分配表和主存的变化如图 3-9所示。作业 J5处于等待状态。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
3．主存空间的回收当作业运行结束时，系统根据作业名到分区分配表中查找作业所在的分区，把该分区的状态标志臵为,0”，表示该分区空闲，
可以用来装入新的作业。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.3 地址转换与存储保护
1．地址转换由于作业在执行时不会改变分区的个数和大小，所以地址转换采用静态重定位方式。
地址转换过程 是,CPU获得的逻辑地址首先与下限寄存器的值相加，产生物理地址；然后与上限寄存器的值比较，若大于上限寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理；若不大于上限寄存器的值，则该物理地址就是合法地址，它对应于主存中的一个存储单元。地址转换过程如图 3-10所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.3 地址转换与存储保护
2．存储保护系统设臵了一对寄存器，称为“下限寄存器”和“上限寄存器”。它们记录当前作业在主存中的下限和上限地址。当系统转换该作业指令的逻辑地址时，必须核对表达式“下限地址 <= 物理地址 <= 上限地址”是否成立。若成立，就转换。否则，就产生
“地址越界”中断信号，停止转换。从而实现存储保护。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.4 管理特点
(1)一个作业只能装入一个分区,不能装入两个或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入。
(2)通过对“分区分配表”的改写，来实现对主存空间的分配与回收。 作业在执行时，不会改变存储区域，
所以采用静态地址重定位方式易于实现，且系统开销小。
(3)当分区较大作业较小时,仍然浪费许多主存空间,
并且分区总数固定,限制了并发执行的作业数目 。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.5 对固定分区的改进一个分区只装入一个作业，分区的其他部分闲臵不用，降低了主存的利用率。可以采用下列方法提高主存的利用率：
（ 1）根据经常出现的作业的大小和数量来划分分区，尽可能地使各个分区充分利用。
（ 2）划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区。各分区按从小到大的顺序登记在分区表中。
（ 3）按作业对主存的需求量排成多个作业队列，一个作业队列对应一个分区，互不借用。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.6 举例
【 例 3-1】 在某系统中采用固定分区分配管理方式，主存分区（单位字节）情况如图 3-11（ a）所示。现有大小为 1KB,9KB,33KB、
121KB的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明主存浪费有多大？
【 解 】 采用固定分区存储管理方式，作业进入系统后的分配情况如图 3-11（ b）所示，
主存浪费 512KB-20KB-(1KB+9KB+33KB+121KB)=328KB。
第 3章 存储器管理返回
3.4 可变分区存储管理方式
3.4.1 基本原理可变分区存储管理方式又称为动态分区存储管理方式。它是根据用户作业的大小，在作业要求装入主存时，动态地划分分区，
使分区的大小正好适应作业的要求。采用这种存储管理方式，分区的大小是不定的，分区的数目也是不定的。
可变分区存储管理方式必须解决三个问题：
一是分区分配中所用的数据结构，
二是分区的分配算法，
三是分区的分配和回收。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
1．采用的数据结构为了实现可变分区分配，系统中必须配臵相应的数据结构，
用来记录主存的使用情况，包括空闲分区的情况和已分分区的情况，为作业分配主存空间提供依据。为此，设臵了两张表，即 已分分区表 和 空闲分区表,如表 3-2和表 3-3所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
2．主存空间的分配分配主存时，先分配小地址，再分配大地址。空闲分区表中记录的排列也是从小地址向大地址排列的。首次分配时，只有一个空闲区。
主存的分配过程如下：首先初始化已分分区表（ 0个记录）和空闲分区表
（ 1个记录），整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小。其次，从作业队列中取出队首作业，在空闲分区表中查找一个不小于作业大小的空闲区，装入作业。在已分分区表中增加一条记录，填上该作业所占用分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。然后，再分配下一个作业，直到所有作业分配完毕。
在这种管理方式下，主存空间的分配流程如图 3-12 所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 1）最先适应分配算法（ FF）
它要求空闲分区表中的记录按地址递增的顺序排列。在每次分配主存时，总是从第 1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区。一部分分配给作业，另一部分仍作为空闲区。
它的特点是分配算法简单，容易产生过多的主存碎片。主存碎片是指小的不能使用的主存空间；这种算法把大的空闲区分成了小的空闲区，当有大作业要求分配时，不能满足要求，降低了系统的效率。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 2）最优适应分配算法（ BF）
它是从所有的空闲分区中挑选一个能满足作业要求的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲分区表中，分配时，顺序查找。
它的优点是解决了大作业的分配问题，不足是容易产生主存碎片，降低了主存空间的利用率。另外收回主存时，要按长度递增顺序插入到空闲分区表中，增加了系统开销（操作系统所占有的系统资源和所需要的处理器的时间称为“系统开销”）。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 3）最坏适应分配算法（ WF）
它每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小而成为主存碎片。为实现这种算法，把空闲区按长度递减的次序登记在空闲分区表中，分配时，顺序查找。
它的优点是不会产生过多的碎片。不足是影响大作业的分配。
另外收回主存时，要按长度递减的顺序插入到空闲分区表中，增加了系统开销。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
4．主存空间的回收当一个作业运行结束后，在已分分区表中找到该作业，根据该作业所占主存的始址和大小，去修改空闲分区表相应的记录。
其修改情况分为四种，如图 3-13所示（斜线部分为被作业占有的主存区域）。
（ 1）回收的分区前后没有相邻的空闲分区。
（ 2）回收分区的前面有相邻的空闲区。
（ 3）回收分区的后面有相邻的空闲分区。
（ 4）回收分区的前后都有相邻的空闲分区。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.3 地址转换与存储保护
1．地址转换因为空闲分区的个数和大小，以及作业的个数和大小都不能预先确定，所以，可变分区存储管理方式一般采用动态重定位方式装入作业。它需要设臵硬件地址转换机构：两个专用寄存器
（即基址寄存器和限长寄存器）以及一些加法、比较电路。地址转换如图 3-14所示 。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.3 地址转换与存储保护
2．存储保护系统设臵了一对寄存器，称为“基址寄存器”和“限长寄存器”，用它记录当前在 CPU中运行作业在主存中所占分区的始址和末址。当处理器执行该作业的指令时必须核对表达式“始址 <=
物理地址 <= 末址”是否成立。若成立，就执行该指令，否则就产生“地址越界”中断信号，停止执行该指令。
当作业运行结束让出处理器时，调度程序将选择另一个可以运行的作业，同时修改当前运行作业的分区号和基址寄存器、限长寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.4 管理特点
(1)分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业个数决定的。
(2)分区的大小由作业的大小决定，提高了主存的使用效率。
(3)在主存分配过程中，会产生许多主存碎片，造成主存空间的浪费。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.5 采用技术
1．移动技术在连续分配主存的方式中，必须把一个系统程序或用户程序装入到一个连续的主存空间。如果在系统中有若干个小的分区，
其总容量大于要装入的程序，但是，由于它们不邻接，该程序也不能装入主存。
在此情况下，若想把作业装入，可以采用的一种方法是，移动主存中的所有作业，使它们相邻接。这样，原来分散的多个主存碎片便拼接成了一个大的空闲分区，从而可以装入作业。这种通过移动把多个分散的小分区拼接成大分区的方法称为“拼接”
或“紧凑”。这种改变作业在主存中位臵的工作称为“移动”。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.5 采用技术
2．对换技术对换技术 是指把主存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据，换入到主存的技术。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 例 3-2】 主存有两个空闲区 F1,F2，如图 3-15（ a）所示。 F1
为 220KB,F2为 120KB，另外依次有 J1,J2,J3三个作业请求加载运行，它们的主存需求量分别是 40KB,160KB,100KB，试比较最先适应分配算法、最优适应分配算法和最坏适应分配算法的性能。
【 解 】 根据作业和主存空闲区的情况，以及作业分配算法的处理步骤，在最先适应分配算法和最坏适应分配算法中，可以给所有作业分配主存空间。在最优适应分配算法中，还有作业 J3不能分配，如图 3-15（ b）所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 例 3-3】 下表给出了某系统中的空闲分区表，系统采用可变分区存储管理策略。现有以下作业序列,96KB,20KB,200KB。若用最先适应分配算法和最优适应分配算法来处理这个作业序列，
试问哪一种算法可以满足该作业序列的请求，为什么？
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 解 】 （ 1）按最先适应分配算法分配主存。
作业 96KB被分配到第 4个分区（假设在已分分区表中的分区序号为 3），作业 20K被分配到第 1个分区，作业 200K没有足够的空间不能分配。已分分区表和空闲分区表的情况如下所示：
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 解 】 （ 2）按最优适应分配算法分配主存。
作业 96K被分配到第 5个分区（假设在已分分区表中的分区序号为
3），作业 20K被分配到第 1个分区，作业 200K被分配到第 4个分区。在这种分配方式下，三个作业可以全部装入，满足作业序列的请求。其已分分区表和空闲分区表的情况如下所示。
第 3章 存储器管理返回
3.5 页式存储管理方式
3.5.1 基本原理在页式存储管理方式中，将用户作业的地址空间分成若干个大小相同的区域，称为页面或 页,并为每个页从,0”开始编号；
相应地，主存空间也分成与页大小相同的若干个存储 块,称为物理块或页框，并且采用同样的方式为它们进行编号，从 0开始：
0块,1块,…,n-1块。
程序的逻辑地址由页号和页内地址组成，页号的长度决定了分页的多少，页内地址的长度决定了页面的大小。在为作业分配主存时，以块为单位将作业中的若干页分别装入到多个不相邻接的块中。作业执行时根据逻辑地址中的页号找到它所在的块号，
再确定当前指令要访问的物理地址。它的地址转换属于动态重定位，由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为,页内碎片,。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
1．采用的数据结构为了实现页式存储管理方式，系统设臵了主存分配表 (如表 3-5
所示 )、位示图 (如图 3-16所示 )和页表 (如表 3-4所示 )，记录主存空间的使用情况和每个作业的分配情况。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
2．主存空间的分配首先，系统初始化位示图，即把位示图中的标志位全部臵为,0”，空闲块数臵为主存的块数。其次，在进行主存分配时，从作业队列中取出队首作业，
计算该作业的页数，然后，与位示图中的空闲块数比较，若不能满足作业空间的要求，则作业不能装入，显示主存不足的信息，把该作业放到队尾或删除该作业；若能满足作业的空间要求，则为该作业建立页表，并根据位示图中主存块的状态标志，找出标志为,0”的那些位，臵上占用标志,1”，根据该位在位示图中的字号和位号，利用下列公式可以计算出该页所对应的块号。
根据计算得块号，把作业页装入对应的主存块中，并在页表中填入对应的块号，直到所有作业页全部装入。最后，修改位示图中空闲块数，即原有空闲块数减去本次占用的块数（页数），并在主存分配表中增加一条记录，登记该作业的作业名、页表始址和页表的长度。直到所有作业全部装入主存。主存空间的分配流程如图 3-17所示。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
3．主存空间的回收当一个作业执行结束，则应收回该作业所占用的主存块。根据主存分配表中的记录，取出该作业的页表。从该作业的页表中取出每一个归还的块号，计算出该块在位示图中的位臵，将占用标志位臵,0”。最后，把归还的块数加入到空闲块数中，删除该作业的页表，并把分区分配表中该作业的记录删除。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.3 地址转换与存储保护
1．地址转换。 两个与地址计算有关的方法。
一是，由逻辑地址计算出页号和页内地址的计算方法如下：
页号 = 逻辑地址 / 页长 （商）
页内地址 = 逻辑地址 mod 页长 （余数）
二是，由块号计算物理地址的计算方法为：
物理地址 = 块号 * 块长 + 块内地址 + 用户区基址页式地址转换过程如图 3-18所示（页长为 2KB）
第 3章 存储器管理
3.5 页式存储管理方式
3.5.3 地址转换与存储保护
2．页的共享和保护
（ 1）页的共享。 页的共享可以节省主存空间。页式存储管理能方便地实现多个作业共享程序和数据。共享的方法是使各自页表中的有关表目指向共享信息的主存块。如表 3-6所示，页表 1所代表作业的第 2页与页表 2所代表作业的第 1页共享第 9块主存空间。
（ 2）页的保护。 在页式存储管理方式下的保护有三种情况：共享页的保护、不同作业所占空间的保护、逻辑地址转换成物理地址的保护。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.4 对页式存储管理的改进因页表在主存中,CPU在存取数据时,要访问主存两次 。 第一次是访问主存中的页表,从中找出该页的物理块号,将此块号与页内地址拼接形成物理地址 。 第二次是根据上一步得到的物理地址,到主存中获取数据 。 这样就降低了计算机的处理速度 。 为了提高处理速度,可以采用快表和两级页表的方法对页式存储管理进行改进 。
1,具有快表的地址变换具有快表的地址转换如图 3-19所示 。
2,具有两级页表的地址转换具有两级页表的地址转换结构如图 3-20所示 。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.5 管理特点
(1)有效地解决了“碎片”多的问题。 可以使程序和数据存放在不连续的主存空间，而不必像可变分区管理那样通过增加系统开销来解决主存碎片的问题。
(2)通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间。另外，它要求有相应的硬件支持，从而增加了系统成本，也增加了系统开销。例如需要地址变换机构、
快表等。它仍然存在不可利用的空间，例如最后一页往往还有剩余空间。
(3)要求页的大小固定，不能随程序的大小而改变，这对程序的共享和使用造成了困难。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-4】 在一个页式存储管理系统中，页面大小为 1KB，主存中用户区的起始地址为 1000，假定页表如下。现有一逻辑地址（页号为 2，页内地址为 20），试计算相应的物理地址，并画图说明地址转换过程。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 解 】 地址转换过程如图 3-21所示。从逻辑地址中取出页号 2，与页表地址寄存器中的页表始址相加，得到该页在页表中的记录号，
从页表中取出该页的块号 9，因页内地址为 20，所以块内地址也是
20。根据物理地址的计算公式可得：
物理地址 = 用户区基址＋块号 × 块长＋块内地址 = 1000＋
9× 1024＋ 20 = 10236
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-5】 设一个页式存储管理系统，向用户提供逻辑地址空间最大为 16页，每页 2048字节，主存总共有 8个存储块，试问逻辑地址应为多少位？主存空间有多大？
【 解 】 页式存储管理系统中的逻辑地址结构为：页号 +页内地址。
在本题中，由于每页为 2048字节，所以页内地址部分需要占据 11
个二进制位；逻辑地址空间最大为 16页，页号部分地址需要占据 4
个二进制位。故逻辑地址至少为 11+4=15位。
由于主存共有 8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等。因此，主存空间为 16KB。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-6】 在页式存储管理系统中，某作业的页表如下左表所示。
页面大小为 1024字节，用户区的基址为 1000，试将逻辑地址 1011，
2148,3000,4000,5012转换为相应的物理地址。
【 解 】 根据页表和每个页面的大小 1024字节，利用公式：
页号 = int (逻辑地址 /页面大小 ),页内地址 = 逻辑地址 mod
页面大小由页号，到页表中查找块号。所以，物理地址 =用户区基址＋
块号 × 块长＋块内地址各逻辑地址对应的物理地址分别是（如下右表所示）：
第 3章 存储器管理返回
3.6 段式存储管理方式引入段式存储管理方式的原因：
一是，一个作业是由若干自然段组成，用户希望能把自己的作业按照逻辑关系划分为若干段，可以通过每段的名字和长度来访问。
二是，分段共享。程序和数据的共享是以信息的逻辑单位为基础的，若段的划分也与信息的逻辑单位相对应，则易实现共享。
三是，分段保护。在多道程序环境下，对主存信息的保护，
同样也是以信息的逻辑单位为基础的。
四是，动态链接也要求以段作为管理的单位。
五是，动态增长。实际应用时某些数据段会不断地增长，而事先又无法确切地知道数据段会增长到多大。这种动态增长的情况是上述几种存储管理方式都难于应付的，而段式存储管理可以较好地解决这个问题。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.1 基本原理在段式存储管理方式中,作业的地址空间被划分为若干段,每段定义了一组逻辑信息 。 例如,有主程序段 MAIN,子程序段 X、
数据段 D及栈段 S等,每个段都有自己的名字 。 为了实现简单,通常可用一个段号来代替段名,每个段都从 0开始编址,并采用一段连续的地址空间 。 段的长度由相应的逻辑信息组的长度决定,因而各段长度不等 。
整个作业的逻辑地址空间,由于分成多个段,因而是二维的,
即其逻辑地址由段号和段内地址所组成 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.2 主存空间的分配与回收
1．采用的数据结构为了记录主存中空闲分区的始址和大小，以及作业中每个段分配主存的情况，在段式存储管理方式下，设臵了空闲分区表、
段表 (如表 3-8所示 )和主存分配表 (如表 3-9所示 )。
2．主存空间的分配过程在段式存储管理中是以段为单位分配主存的。每段分配一个连续的主存空间，但是各段之间不要求连续。供用户使用的逻辑地址为：段号 +段内地址。在装入作业时，用一张段表记录每个分段在主存中的始址和大小。
主存空间的分配流程如图 3-22所示。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.2 主存空间的分配与回收
3．主存空间的回收当作业运行结束时，根据该作业段表的每一条记录，去修改空闲分区表。修改的方式与可变分区回收主存空间相同，根据回收区是否与空闲区相邻，分四种情况处理。最后删除该作业的段表，并删除主存分配表中该作业的记录。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
1．地址转换为了实现从作业的逻辑地址到物理地址的转换功能，在系统中设臵了段表寄存器，用来存放段表的始址和段表长度。在装入作业时，段表寄存器从主存分配表中获取该作业段表的始址和段表长度，作业的逻辑地址包括两部分，即段号和段内地址。
在进行地址转换时，系统将逻辑地址中的段号与段表中的段表长度进行比较，若不小于段表长度则表示段号越界，产生“地址越界”中断信号。若未越界，则根据段表起始址和段号得到该段在主存中的始址。然后，检查段内地址是否超过该段的段长，
若超过，则发出“越界”中断信号。若未越界，则把段始址加上段内地址就得到欲访问主存的物理地址。地址转换过程如图 3-23
所示。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
2．段的共享在段式管理系统中，段是信息的逻辑单位，而段式系统的一个突出优点是易于实现段的共享。分段共享是通过两个作业的段表中的相应表目都指向被共享的同一个物理副本来实现的。
如表 3-10中段表 1的第 1段和段表 2的第 2段是共享的。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
3．段的保护段式存储管理的保护主要有两种：
一是,地址越界保护 。 它包括对段号的判断和对段内地址的判断 。
二是,存取控制保护 。 同页式存储管理一样,在段表中增加一个权限位,设臵存取信息的权限 （ 读,写,读和写等 ）,若本次操作与权限位不符,则由硬件捕获并发出保护性中断,如表 3-11
所示 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.4 管理特点
(1)段长可以根据需要动态增长。 这样，便于对具有完整逻辑功能的信息段共享，便于实现程序的动态链接。
(2)需要的硬件支持更多,成本较高,仍然 存在主存碎片 问题。
若采用移动技术合并空闲区，会增加系统开销。另外,段的大小受主存可用空闲区大小的限制 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.5 分段与分页的区别
（ 1）页是信息的物理单位，分页是为了实现离散的分配方式，
以消减主存碎片，提高主存的利用率。段是信息的逻辑单位，它包含一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
（ 2）页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，
通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
（ 3）分页的作业地址空间是一维的，即单一的线性地址空间，
程序员只需要利用一个记忆符，即可以表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既要给出段名，
又要给出段内地址。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.6 举例
【 例 3-7】 某个采用段式存储管理的系统为装入主存的一个作业建立了段表，如下表所示：
（ 1）给出段式地址转换过程；
（ 2）计算该作业访问逻辑地址（ 0,432），（ 1,10），（ 2，
500），（ 3,400），（ 5,450）时的物理地址。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.6 举例
【 解 】 （ 1）段式地址的转换过程如图 3-24所示。
（ 2）根据地址转换图 3-24可知，该作业访问的逻辑地址（ 0，
432），（ 1,10），（ 2,500），（ 3,400），（ 5,450）对应的物理地址如下表所示：
第 3章 存储器管理返回
3.7 段页式存储管理方式
3.7.1 基本原理段页式存储管理方式的基本原理是段式和页式系统工作原理的组合,即先把用户程序分成若干个段,并为每个段赋予一个段名,
每段可以独立地从,0”编址,再把每个段划分成大小相等的若干个页,把主存分成与页大小相同的块 。 每段分配与其页数相同的主存块,主存块可以连续,也可以不连续 。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
1．主存空间的分配
（ 1）采用的数据结构。 为了实现段页式存储管理方式，系统设臵了位示图、段表和页表，记录主存的使用情况和作业的分配情况。 其管理层次如图 3-25所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
（ 2）主存空间的分配过程。 段页式存储管理是以段内页为单位分配主存的，但是，各段内的页之间不要求连续。供用户使用的逻辑地址为：段号、段内地址。由段内地址除以页长，得到的商为页号，余数为页内地址。在装入作业时，用一个段表和若干个页表记录作业在主存中的分配情况。
在这种管理方式下，主存空间的分配流程如图 3-26所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
2．主存空间的回收当作业运行结束时，根据该作业段表中每一条记录所对应的页表，去修改位示图中的标志位和空闲块数，把标志位由,1”改为,0”，空闲块数增加页数大小。最后，删除每段对应的页表，
以及该作业的段表，并在主存分配表中删除该作业的记录。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.3 地址转换与存储保护
1．地址转换在段页式存储管理中，作业的逻辑地址由段号、段内页号和页内地址组成。系统设臵了一张段表寄存器来记录段表始址和段表长度。在进行地址转换时，首先利用段号，将它与段表寄存器中的段表长度进行比较，若不小于段表长度则产生越界中断；否则，利用段表始址和段号在段表中找到相应页表的始址，再利用逻辑地址中的页号，与段表中的页长比较，若页号不小于该页页表长度，则产生越界中断。否则，在页表中找出其对应的块号，
再与逻辑地址中的页内地址一起组成物理地址。
段页式存储管理的地址转换如图 3-27所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.3 地址转换与存储保护
2．段的共享与保护段的共享 是指通过在各作业的段表中的共享段指向相同的页表始址。段的保护主要有两种：
一是地址越界保护。 它利用段表寄存器的段表长度与逻辑地址中的段号进行比较，若段号超界，则产生越界中断。再利用段表中的页长与逻辑地址中的页号进行比较，若页号不小于页长也产生越界中断。
二是存取控制保护。 与段式存储管理一样，在段表中增加一个权限位，设臵存取信息的权限（读、写、读和写等），若本次操作与权限位不符，则由硬件捕获并发出保护性中断，如表 3-12
所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.4 管理特点
(1) 根据作业模块把作业分成若干段，再根据页面大小把每一段分成若干页，主存仍然分成与页大小相等的块。分配主存时，
把作业每一段的页分配到主存块中。
(2) 这种分配方式既照顾到了用户共享和使用方便的需求，又考虑到了主存的利用率，提高了系统性能。
(3) 这种分配方式造成的空间浪费要比页式管理的多。作业各段的最后一页都有可能浪费一部分空间。另外段表和页表占用的主存空间，要比页式或段式的多。这样就增加了系统开销。
第 3章 存储器管理返回
3.8 虚拟存储管理方式
3.8.1 基本概念
1.虚拟存储管理的引入前面所介绍的各种存储器管理方式，都要求将一个作业全部装入主存才能运行。于是，出现了这样两种情况,一是,作业不能全部被装入主存，致使该作业无法运行； 二是,有大量的作业要求运行。
解决方法是,一是从物理上增加主存容量,但是，这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的； 另一种方法是从逻辑上扩充主存容量,这正是虚拟存储技术所要解决的主要问题。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
2.虚拟存储管理的可能在程序运行过程中，程序的有些部分是彼此 互斥的,即在程序的某次运行中，执行了这部分程序就不会执行另一部分程序。
并非用到其全部程序 。
程序的执行有局部性。某一时刻循环执行某些指令或多次访问某些数据。当把作业全部装入主存后，作业执行时实际上只使用部分信息，甚至有些部分在作业执行的整个过程中都不会被使用到（ 局部性原理 ）。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
3.虚拟存储器的定义虚拟存储器 是指仅把作业的一部分装入主存便可以运行的存储器系统。
虚拟存储器的 逻辑容量 也称为最大容量，是由地址寄存器的位数决定的。如果计算机的地址寄存器是 24位，地址按单字节编址，则虚拟存储器的最大（逻辑）容量是 224B。
虚拟存储器的 物理容量 也称为实际容量。当最大容量大于等于主存与硬盘容量之和时，虚拟存储器实际容量为主存与硬盘之容量之和；当最大容量小于主存与硬盘容量之和时，虚拟存储器实际容量就是最大容量。虚拟存储器的运行速度接近于主存速度，
而其成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于各类计算机中。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
4.虚拟存储器的特点
（ 1）离散性。 离散性是指在主存分配时采用离散分配方式。
（ 2）多次性。 多次性是指一个作业被分成多次调入主存运行。
（ 3）对换性。 对换性是指允许在作业的运行过程中换进、换出。
（ 4）虚拟性。 虚拟性是指能够从逻辑上扩充主存容量，使用户所看到的主存容量远大于实际主存容量。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
5.虚拟存储器实现的方法
（ 1）页式 虚拟存储管理 。 它是在页式存储管理系统的基础上增加了请求调页功能和页面臵换功能所形成的页式虚拟存储管理系统。
（ 2）段式虚拟存储管理。 它是在段式存储管理系统的基础上增加了请求调段功能和段臵换功能所形成的段式虚拟存储管理系统。
（ 3）段页式虚拟存储管理。 它是在段页式存储管理系统的基础上增加了请求调页功能和页面臵换功能所形成的段页式虚拟存储管理系统。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
1．基本原理页式虚拟存储管理是建立在纯分页基础上的，增加了请求调页功能和页面臵换功能所形成的页式虚拟存储管理系统。它把作业分成大小相等的若干页，把主存分成与页大小相等的若干块；对每个作业限定分给它的主存块数，先把作业的部分页装入主存的这些块中，在作业运行时再装入所需要的页。
2．采用的数据结构虚拟存储器在实现上是有一定难度的，既需要一定的硬件支持，
又需要较多的软件支持，但是，请求分页式存储管理方式相对容易，
因为它换进、换出的基本单位是固定长度的页面。采用的数据结构如下：位示图、页表和主存分配表。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
2．采用的数据结构缺页中断机构。 在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求系统将缺页调入主存。
当作业所访问某页（如第 i页）时，到页表中去查找。若该页不在主存时，产生缺页中断。根据页表中指示的位臵到磁盘的第 j块上，
把第 i页调进主存的第 k块中。然后，去修改页表，在该页对应的记录上填入块号 k，再重新执行访问 i页的指令。如图 3-28所示。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
3．主存空间的分配与回收
（ 1）主存空间的分配。 根据一定的分配策略，确定每一个作业能够运行的最小物理块数（假如为 M），当给一个作业分配主存时，
首先，计算该作业的页数，比较是否,M>位示图中空闲块数”，
若大于则该作业暂时不能装入；否则，可以装入一部分，为其建立页表，初始化表中的数据。装入过程与页式存储管理方式的一样，
只不过是要累计个数，到 M个页时，停止装入，修改位示图中空闲块数（减去调入主存的该作业页数），并在主存分配表中增加一条记录，记录该作业的作业名、页表始址、页表长度和所分得的物理块数。其余页等到程序运行时，访问到该页时再装入。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
3．主存空间的分配与回收
（ 2）主存空间的回收。 主存空间的回收方法与页式存储管理的很相似。当作业运行结束时，根据页表去修改位示图，把归还块的占用标志位改为,0”。然后，修改空闲块数，增加 M个。最后，删除该作业的页表和该作业在主存分配表中的记录。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
4．地址转换与存储保护
（ 1）地址转换。 作业中的逻辑地址仍然是一个一维地址，根据页面的大小，可以计算出它所在的页号和页内地址。
地址的正常转换与页式存储管理相同（如图 3-18所示）。
（ 2）存储保护。 存储保护的方法与页式存储管理很相似，在此不再赘述。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
5．分配物理块的策略在为作业分配物理块时，将涉及三个问题,第一,确定为保证作业正常运行所需要的最少物理块数； 第二,为每个作业分配的物理块，其数目是固定的还是可变的； 第三,对各作业所分配的物理块数，是采取平均分配算法还是根据作业的大小按比例分配等。
（ 1）最小物理块数。 最小物理块数是指能保证作业正常运行所需要的最少物理块数。它与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
（ 2）页面分配和臵换策略。 在页式虚拟存储管理系统中，可采取两种分配策略，即固定分配策略和可变分配策略。在进行臵换时，
也可采取两种策略，即全局臵换和局部臵换。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
6．作业在主存中块数的分配算法在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个作业，可以采取下述几种方法。
（ 1）平均分配算法。 这是将系统中所有可供分配的物理块，平均分配给各个作业。
（ 2）按比例分配算法。 这是根据作业的大小按比例分配物理块。
（ 3）优先权分配算法。 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的主存空间。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法页面臵换算法 是确定该淘汰哪一页的一种策略。臵换算法的优劣将直接影响系统的效率。不适当的算法可能会导致作业发生“抖动”现象，即刚被换出的页很快又被访问，需重新调入，而刚被换入的页，很快又要被换出的现象。一个好的页面臵换算法，应具有较低的缺页中断率。常用的页面臵换算法有：
（ 1）最佳臵换算法。 从主存中移出永远不需要的页，若无这样的页，则移出最长时间不需要访问的页。该算法只具有理论意义。
如图 3-29所示的臵换实例，发生了 9次缺页中断，缺页中断率：
9/20=45%。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法
（ 2）先进先出臵换算法（ FIFO）。
该算法淘汰最早进入主存的页面。因为，最早进入的页面，不再使用的可能性比最近调入的页面要大。先进先出臵换算法实现简单，只要把各调入主存的页按其进入主存的先后顺序连成一个队列即可，总是淘汰队首的那一页。
（ 3）最近最久未使用算法（ LRU）。
该算法选择在最近一段时间内最久没有使用过的页淘汰掉。它依据的是程序局部性原理。 最近最久未使用算法是利用一个特殊的栈来保存当前使用的各个页的页号。每当访问某页时，考察栈内是否有与此相同的页号，若有则将该页的页号从栈中抽出，再将它压入栈顶。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法
（ 4）最近最不经常使用算法（ LFU）
该算法选择到当前时间为止被访问次数最少的页臵换。其实现方法是为每页设臵一个访问计数器，每当页面被访问时，该页面的访问计数器就加,1”；发生缺页时，淘汰计数器值最小的页，同时将所有计数器清,0”。
（ 5）最近未使用算法（ NUR）
该算法将最近一段时间未引用过的页面换出。采用该种臵换算法，效率较高，但是，系统开销较大。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
8．管理特点
（ 1）作业可以不必全部装入主存，就能运行。事先要把作业分成大小相等的“页”，把主存分成与页大小相等的块，先装入一些必需的页，运行时再装入所需要的页。
（ 2）这样与全部装入主存的存储管理方式相比，可以节省主存空间，增加并发执行的作业个数，提高系统的利用率。
（ 3）由于运行时，没有把作业全部装入主存，其余页是在运行时，利用中断和页面臵换算法装入的。这样，增加了程序运行的时间，加大了系统的硬件开销。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-8】 在一个页式虚拟存储管理系统中，一个程序的页面走向为 6,0,1,2,0,3,0,4,2,3，分别采用最佳臵换算法、先进先出臵换算法和最近最久未使用算法，完成下列要求。设分配给该程序的存储块数 M=3，每调进一个新页就发生一次缺页中断。
（ 1）试完成下表：
（ 2）求缺页中断次数 F和缺页率 f。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 解 】 （ 1）采用最佳臵换算法。
缺页中断次数 F=6，缺页率 f=6/10=60%。
（ 2）采用先进先出臵换算法。
缺页中断次数 F=9，缺页率 f=9/10=90%。
（ 3）采用最近最久未使用算法。
缺页中断次数 F=8，缺页率 f=8/10=80%。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-9】 在一个页式虚拟存储管理系统中，假定作业的页面走向为 2,3,2,1,5,2,4,5,3,2,5,2。试用先进先出臵换算法，分别计算出当系统分配给一个作业的物理块数为 2,3,4时，
程序访问过程中所发生的缺页次数，并说明是什么问题？
【 解 】 （ 1）当物理块数为 2时，按先进先出臵换算法的缺页次数为
10次，如下表所示：
（ 2）物理块数为 3时，按先进先出臵换算法的缺页次数为 9次，
如下表所示：
（ 3）物理块数为 4时，按先进先出臵换算法的缺页次数为 6次，
如下表所示：
这说明了随着分配给作业的物理块数的增多，作业的缺页次数会减少。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-10】 在一个页式虚拟存储管理系统中，主存容量为
1MB，被划分为 256块，每块为 4KB。现有一作业，它的页表如下：
（ 1）若给定一逻辑地址为 9016，其物理地址为多少？
（ 2）若给定一逻辑地址为 12300，给出其物理地址的计算过程。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 解 】
（ 1）逻辑地址为 9016时，因为 9016/4096 商为 2，余数为 824，所以页号为 2，页内地址为 824。从页表中可知，
该页被装入主存的第 32块。假设用户区的起始地址为
1000，则其物理地址为,32*4*1024+824+1000 =
132896
（ 2）根据（ 1）可知,12300/4096 商为 3，余数为 12，
即页号为 3，页内地址为 12。由页表可知，该页在辅存中，
产生缺页中断，中断处理程序将该页从外存装入主存相应的块中，把块号填入页表中，再进行地址转换。
第 3章 存储器管理返回
3.1 存储器管理概述
3.2 单用户连续存储管理方式
3.3 固定分区存储管理方式
3.4 可变分区存储管理方式
3.5 页式存储管理方式
3.6 段式存储管理方式
3.7 段页式存储管理方式
3.8 虚拟存储管理方式本章结束！
3.1 存储器管理概述
3.1.1 存储器管理的主要任务存储器管理的主要任务 是为用户作业分配主存空间,提高主存的使用效率,并从逻辑上扩充主存空间,使主存在成本,速度和规模之间获得较好的权衡 。
第 3章 存储器管理
3.1 存储器管理概述
3.1.2 存储器管理的主要功能
1．主存空间的分配和回收主存分配的主要任务是采用一定的数据结构，按照一定的算法为每一道程序分配主存空间，使它们“各得其所”，并记录主存空间的使用情况和作业的分配情况。
主存空间的回收是指当一个作业运行结束后，必须归还所占用的主存空间，即在记录主存空间使用情况的数据结构中进行修改，并且把记录作业分配情况的数据结构删除。
2．地址转换将用户程序的逻辑地址转换为运行时的物理地址的过程称为地址转换，也称为地址映射（即重定位）。
第 3章 存储器管理
3.1 存储器管理概述
3.1.2 存储器管理的主要功能
3．主存空间的共享与保护在多道程序设计系统中，同时进入主存执行的作业可能需要调用相同的程序或数据，这就是主存的共享。例如，调用编译程序进行编译，把这个编译程序存放在某个区域中，各作业要调用时就访问这个区域，因此这个区域就是共享的。同样也可以实现公共数据的共享。
在实现主存分配与共享时，必须解决主存中信息的保护问题。
存储保护的工作一般由硬件和软件配合实现。
4．主存空间的扩充提供虚拟存储器的管理功能，使用户编写程序时不必考虑主存的实际容量，使计算机系统有一个比实际主存容量大得多的存储空间。这样就可以运行较多的程序和较大的程序。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
1．源程序的执行过程在多道程序环境下，程序要运行必须先将程序和数据装入主存。那么，如何将一个用户源程序变为一个在主存中可执行的程序呢？通常需要经过编译、链接和装入等几个步骤，其控制步骤如图 3-1所示。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
2．程序的装入将一个装入程序代码装入主存时，可以采用三种方式：
（ 1）绝对装入方式。 绝对装入方式是由装入程序根据装入程序代码中的地址将程序和数据装入主存。
（ 2）可重定位方式。 可重定位方式是由装入程序根据主存当前的实际使用情况，将装入程序代码装入到主存适当的地方。
（ 3）动态运行时装入方式。 绝对装入方式只能将装入程序代码装入到主存中事先指定的位臵。
第 3章 存储器管理
3.1 存储器管理概述
3.1.3 程序的装入与链接
3．程序的链接链接程序的功能是将经过编译或汇编后所得到的一组目标程序以及它们所需要的库函数装配成一个完整的装入程序代码。实现链接的方法有三种：
（ 1）静态链接。
（ 2）装入时动态链接。
（ 3）运行时动态链接。
第 3章 存储器管理
3.1 存储器管理概述
3.1.4 存储管理方式对主存的存储管理方式，根据是否把作业全部装入，全部装入后是否装入到一个连续的存储区域，可以分为如图 3-3所示的几种管理方式。
第 3章 存储器管理返回
3.2 单用户连续存储管理方式
3.2.1 基本原理这是最早出现的一种存储管理方式 。
在主存中仅驻留一道程序,整个用户区被一用户独占 。 当用户作业空间大于用户区时,该作业不能装入 。
这种分配方式仅能用于单用户单任务的操作系统中,不能用于多用户系统和单用户多任务系统中 。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
1．主存空间的分配采用单用户连续存储管理方式时，主存分为两个分区，即系统区和用户区，如图 3-4所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
1．主存空间的分配
（ 1）系统区是仅提供给操作系统使用的主存区，它可以以驻留在主存的低地址部分，也可以驻留在主存的高地址部分。
（ 2）用户区是指除系统区以外的主存空间，提供给用户使用。
在这种管理方式下，主存分配的流程如图 3-5所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.2 主存空间的分配与回收
2．主存空间的回收作业一旦进入主存，就要等到它结束后，系统才能回收作业所占用的空间。在这种管理方式下，回收主存空间不需要做任何操作，直接装入第二个作业即可。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
1．地址转换因为主存所有空间归一个用户作业使用，所以它采用静态分配方式，即在作业被装入主存时，一次性完成地址转换。
采用这种管理方式时，处理器设臵两个寄存器：界限寄存器和重定位寄存器。界限寄存器用来存放主存用户区的长度，重定位寄存器用来存放用户区的起始址。一般情况下这两个寄存器的内容是不变的，只有当操作系统占有的存储区域改变时才会改变。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
1．地址转换地址转换过程如图 3-6所示。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.3 地址转换与存储保护
2．存储保护处理器在执行指令时，检查逻辑地址是否小于界限寄存器的值。若小于，则与重定位寄存器中的基址相加，产生物理地址，
到主存中去执行。否则，产生一个“地址越界”中断信号，由操作系统进行处理，以达到存储保护的目的。
第 3章 存储器管理
3.2 单用户连续存储管理方式
3.2.4 管理特点
(1)管理简单。 它把主存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。
它需要很少的软硬件支持，且便于用户了解和使用。
(2)在主存中的作业 不必考虑移动 的问题，并且主存的回收不需要任何操作。
(3)资源利用率低。 不管用户区有多大，它一次只能装入一个作业，这样就造成了存储空间的浪费，使系统整体资源利用率不高。
(4)这种分配方式 不支持虚拟存储器 的实现。
第 3章 存储器管理返回
3.3 固定分区存储管理方式
3.3.1 基本原理固定分区存储管理方式是最早使用的一种可以运行多道程序的存储管理方式。它要求把作业全部装入主存，且装入一个连续的存储空间。
在这种管理方式下，把主存中可以分配的用户区预先划分成若干个大小固定的区域，每一个区域称为一个分区，每个分区可以装入一个作业，一个作业也只能装入一个分区中。这样就可以装入多个作业，使它们并发执行。当有一个空闲分区时，便可以从外存的后备作业队列中，选择一个适当大小的作业装入该分区；
当该作业运行结束时，又可以从后备作业队列中选择另一个作业装入该分区。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
1．采用的数据结构在固定分区存储管理方式下，为了记录各个分区的使用情况，
方便主存空间的分配与回收操作，就建立了一张分区分配表。分区分配表的内容包括分区序号、始址、大小、状态。如表 3-1所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配在作业分配之前，根据主存分区的划分情况，在分区分配表中填入每个分区的起始地址（简称始址）、大小，在状态栏中一律填入,0”，表示该分区可用。当作业装入时填入作业名。
当有作业申请主存空间时，主存空间的分配步骤为：从作业队列中取出队首作业，检查分区分配表，选择状态标志为,0”的分区，并将作业地址空间的大小与状态标志为,0”的分区的大小进行比较，当所有分区长度都不能容纳该作业时，则该作业暂时不能装入，显示主存不足的信息。当某一个分区长度能容纳该作业时，
则把作业装入该分区，并把作业名填到该分区的状态栏里，然后，
再分配下一个作业。
在这种管理方式下，主存空间的分配流程如图 3-7所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配例如，某台计算机的主存大小为 500KB，前 100KB
为系统区，其余的空间为用户区，并将其划分为四个分区，划分情况如图 3-8所示。各分区的初始状态为,0”，
表示可用。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
2．主存空间的分配现有一个作业申请队列 J1,J2,J3,J4,J5，大小分别为
30KB,20KB,40KB,100KB,70KB，按固定分区分配主存空间后，分区分配表和主存的变化如图 3-9所示。作业 J5处于等待状态。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.2 主存空间的分配与回收
3．主存空间的回收当作业运行结束时，系统根据作业名到分区分配表中查找作业所在的分区，把该分区的状态标志臵为,0”，表示该分区空闲，
可以用来装入新的作业。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.3 地址转换与存储保护
1．地址转换由于作业在执行时不会改变分区的个数和大小，所以地址转换采用静态重定位方式。
地址转换过程 是,CPU获得的逻辑地址首先与下限寄存器的值相加，产生物理地址；然后与上限寄存器的值比较，若大于上限寄存器的值，产生“地址越界”中断信号，由相应的中断处理程序处理；若不大于上限寄存器的值，则该物理地址就是合法地址，它对应于主存中的一个存储单元。地址转换过程如图 3-10所示。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.3 地址转换与存储保护
2．存储保护系统设臵了一对寄存器，称为“下限寄存器”和“上限寄存器”。它们记录当前作业在主存中的下限和上限地址。当系统转换该作业指令的逻辑地址时，必须核对表达式“下限地址 <= 物理地址 <= 上限地址”是否成立。若成立，就转换。否则，就产生
“地址越界”中断信号，停止转换。从而实现存储保护。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.4 管理特点
(1)一个作业只能装入一个分区,不能装入两个或多个相邻的分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入。
(2)通过对“分区分配表”的改写，来实现对主存空间的分配与回收。 作业在执行时，不会改变存储区域，
所以采用静态地址重定位方式易于实现，且系统开销小。
(3)当分区较大作业较小时,仍然浪费许多主存空间,
并且分区总数固定,限制了并发执行的作业数目 。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.5 对固定分区的改进一个分区只装入一个作业，分区的其他部分闲臵不用，降低了主存的利用率。可以采用下列方法提高主存的利用率：
（ 1）根据经常出现的作业的大小和数量来划分分区，尽可能地使各个分区充分利用。
（ 2）划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区。各分区按从小到大的顺序登记在分区表中。
（ 3）按作业对主存的需求量排成多个作业队列，一个作业队列对应一个分区，互不借用。
第 3章 存储器管理
3.3 固定分区存储管理方式
3.3.6 举例
【 例 3-1】 在某系统中采用固定分区分配管理方式，主存分区（单位字节）情况如图 3-11（ a）所示。现有大小为 1KB,9KB,33KB、
121KB的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明主存浪费有多大？
【 解 】 采用固定分区存储管理方式，作业进入系统后的分配情况如图 3-11（ b）所示，
主存浪费 512KB-20KB-(1KB+9KB+33KB+121KB)=328KB。
第 3章 存储器管理返回
3.4 可变分区存储管理方式
3.4.1 基本原理可变分区存储管理方式又称为动态分区存储管理方式。它是根据用户作业的大小，在作业要求装入主存时，动态地划分分区，
使分区的大小正好适应作业的要求。采用这种存储管理方式，分区的大小是不定的，分区的数目也是不定的。
可变分区存储管理方式必须解决三个问题：
一是分区分配中所用的数据结构，
二是分区的分配算法，
三是分区的分配和回收。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
1．采用的数据结构为了实现可变分区分配，系统中必须配臵相应的数据结构，
用来记录主存的使用情况，包括空闲分区的情况和已分分区的情况，为作业分配主存空间提供依据。为此，设臵了两张表，即 已分分区表 和 空闲分区表,如表 3-2和表 3-3所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
2．主存空间的分配分配主存时，先分配小地址，再分配大地址。空闲分区表中记录的排列也是从小地址向大地址排列的。首次分配时，只有一个空闲区。
主存的分配过程如下：首先初始化已分分区表（ 0个记录）和空闲分区表
（ 1个记录），整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小。其次，从作业队列中取出队首作业，在空闲分区表中查找一个不小于作业大小的空闲区，装入作业。在已分分区表中增加一条记录，填上该作业所占用分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。然后，再分配下一个作业，直到所有作业分配完毕。
在这种管理方式下，主存空间的分配流程如图 3-12 所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 1）最先适应分配算法（ FF）
它要求空闲分区表中的记录按地址递增的顺序排列。在每次分配主存时，总是从第 1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区。一部分分配给作业，另一部分仍作为空闲区。
它的特点是分配算法简单，容易产生过多的主存碎片。主存碎片是指小的不能使用的主存空间；这种算法把大的空闲区分成了小的空闲区，当有大作业要求分配时，不能满足要求，降低了系统的效率。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 2）最优适应分配算法（ BF）
它是从所有的空闲分区中挑选一个能满足作业要求的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲分区表中，分配时，顺序查找。
它的优点是解决了大作业的分配问题，不足是容易产生主存碎片，降低了主存空间的利用率。另外收回主存时，要按长度递增顺序插入到空闲分区表中，增加了系统开销（操作系统所占有的系统资源和所需要的处理器的时间称为“系统开销”）。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
3．常用的主存分配算法
（ 3）最坏适应分配算法（ WF）
它每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小而成为主存碎片。为实现这种算法，把空闲区按长度递减的次序登记在空闲分区表中，分配时，顺序查找。
它的优点是不会产生过多的碎片。不足是影响大作业的分配。
另外收回主存时，要按长度递减的顺序插入到空闲分区表中，增加了系统开销。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.2 主存空间的分配与回收
4．主存空间的回收当一个作业运行结束后，在已分分区表中找到该作业，根据该作业所占主存的始址和大小，去修改空闲分区表相应的记录。
其修改情况分为四种，如图 3-13所示（斜线部分为被作业占有的主存区域）。
（ 1）回收的分区前后没有相邻的空闲分区。
（ 2）回收分区的前面有相邻的空闲区。
（ 3）回收分区的后面有相邻的空闲分区。
（ 4）回收分区的前后都有相邻的空闲分区。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.3 地址转换与存储保护
1．地址转换因为空闲分区的个数和大小，以及作业的个数和大小都不能预先确定，所以，可变分区存储管理方式一般采用动态重定位方式装入作业。它需要设臵硬件地址转换机构：两个专用寄存器
（即基址寄存器和限长寄存器）以及一些加法、比较电路。地址转换如图 3-14所示 。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.3 地址转换与存储保护
2．存储保护系统设臵了一对寄存器，称为“基址寄存器”和“限长寄存器”，用它记录当前在 CPU中运行作业在主存中所占分区的始址和末址。当处理器执行该作业的指令时必须核对表达式“始址 <=
物理地址 <= 末址”是否成立。若成立，就执行该指令，否则就产生“地址越界”中断信号，停止执行该指令。
当作业运行结束让出处理器时，调度程序将选择另一个可以运行的作业，同时修改当前运行作业的分区号和基址寄存器、限长寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.4 管理特点
(1)分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业个数决定的。
(2)分区的大小由作业的大小决定，提高了主存的使用效率。
(3)在主存分配过程中，会产生许多主存碎片，造成主存空间的浪费。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.5 采用技术
1．移动技术在连续分配主存的方式中，必须把一个系统程序或用户程序装入到一个连续的主存空间。如果在系统中有若干个小的分区，
其总容量大于要装入的程序，但是，由于它们不邻接，该程序也不能装入主存。
在此情况下，若想把作业装入，可以采用的一种方法是，移动主存中的所有作业，使它们相邻接。这样，原来分散的多个主存碎片便拼接成了一个大的空闲分区，从而可以装入作业。这种通过移动把多个分散的小分区拼接成大分区的方法称为“拼接”
或“紧凑”。这种改变作业在主存中位臵的工作称为“移动”。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.5 采用技术
2．对换技术对换技术 是指把主存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据，换入到主存的技术。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 例 3-2】 主存有两个空闲区 F1,F2，如图 3-15（ a）所示。 F1
为 220KB,F2为 120KB，另外依次有 J1,J2,J3三个作业请求加载运行，它们的主存需求量分别是 40KB,160KB,100KB，试比较最先适应分配算法、最优适应分配算法和最坏适应分配算法的性能。
【 解 】 根据作业和主存空闲区的情况，以及作业分配算法的处理步骤，在最先适应分配算法和最坏适应分配算法中，可以给所有作业分配主存空间。在最优适应分配算法中，还有作业 J3不能分配，如图 3-15（ b）所示。
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 例 3-3】 下表给出了某系统中的空闲分区表，系统采用可变分区存储管理策略。现有以下作业序列,96KB,20KB,200KB。若用最先适应分配算法和最优适应分配算法来处理这个作业序列，
试问哪一种算法可以满足该作业序列的请求，为什么？
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 解 】 （ 1）按最先适应分配算法分配主存。
作业 96KB被分配到第 4个分区（假设在已分分区表中的分区序号为 3），作业 20K被分配到第 1个分区，作业 200K没有足够的空间不能分配。已分分区表和空闲分区表的情况如下所示：
第 3章 存储器管理
3.4 可变分区存储管理方式
3.4.6 举例
【 解 】 （ 2）按最优适应分配算法分配主存。
作业 96K被分配到第 5个分区（假设在已分分区表中的分区序号为
3），作业 20K被分配到第 1个分区，作业 200K被分配到第 4个分区。在这种分配方式下，三个作业可以全部装入，满足作业序列的请求。其已分分区表和空闲分区表的情况如下所示。
第 3章 存储器管理返回
3.5 页式存储管理方式
3.5.1 基本原理在页式存储管理方式中，将用户作业的地址空间分成若干个大小相同的区域，称为页面或 页,并为每个页从,0”开始编号；
相应地，主存空间也分成与页大小相同的若干个存储 块,称为物理块或页框，并且采用同样的方式为它们进行编号，从 0开始：
0块,1块,…,n-1块。
程序的逻辑地址由页号和页内地址组成，页号的长度决定了分页的多少，页内地址的长度决定了页面的大小。在为作业分配主存时，以块为单位将作业中的若干页分别装入到多个不相邻接的块中。作业执行时根据逻辑地址中的页号找到它所在的块号，
再确定当前指令要访问的物理地址。它的地址转换属于动态重定位，由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为,页内碎片,。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
1．采用的数据结构为了实现页式存储管理方式，系统设臵了主存分配表 (如表 3-5
所示 )、位示图 (如图 3-16所示 )和页表 (如表 3-4所示 )，记录主存空间的使用情况和每个作业的分配情况。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
2．主存空间的分配首先，系统初始化位示图，即把位示图中的标志位全部臵为,0”，空闲块数臵为主存的块数。其次，在进行主存分配时，从作业队列中取出队首作业，
计算该作业的页数，然后，与位示图中的空闲块数比较，若不能满足作业空间的要求，则作业不能装入，显示主存不足的信息，把该作业放到队尾或删除该作业；若能满足作业的空间要求，则为该作业建立页表，并根据位示图中主存块的状态标志，找出标志为,0”的那些位，臵上占用标志,1”，根据该位在位示图中的字号和位号，利用下列公式可以计算出该页所对应的块号。
根据计算得块号，把作业页装入对应的主存块中，并在页表中填入对应的块号，直到所有作业页全部装入。最后，修改位示图中空闲块数，即原有空闲块数减去本次占用的块数（页数），并在主存分配表中增加一条记录，登记该作业的作业名、页表始址和页表的长度。直到所有作业全部装入主存。主存空间的分配流程如图 3-17所示。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.2 主存空间的分配与回收
3．主存空间的回收当一个作业执行结束，则应收回该作业所占用的主存块。根据主存分配表中的记录，取出该作业的页表。从该作业的页表中取出每一个归还的块号，计算出该块在位示图中的位臵，将占用标志位臵,0”。最后，把归还的块数加入到空闲块数中，删除该作业的页表，并把分区分配表中该作业的记录删除。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.3 地址转换与存储保护
1．地址转换。 两个与地址计算有关的方法。
一是，由逻辑地址计算出页号和页内地址的计算方法如下：
页号 = 逻辑地址 / 页长 （商）
页内地址 = 逻辑地址 mod 页长 （余数）
二是，由块号计算物理地址的计算方法为：
物理地址 = 块号 * 块长 + 块内地址 + 用户区基址页式地址转换过程如图 3-18所示（页长为 2KB）
第 3章 存储器管理
3.5 页式存储管理方式
3.5.3 地址转换与存储保护
2．页的共享和保护
（ 1）页的共享。 页的共享可以节省主存空间。页式存储管理能方便地实现多个作业共享程序和数据。共享的方法是使各自页表中的有关表目指向共享信息的主存块。如表 3-6所示，页表 1所代表作业的第 2页与页表 2所代表作业的第 1页共享第 9块主存空间。
（ 2）页的保护。 在页式存储管理方式下的保护有三种情况：共享页的保护、不同作业所占空间的保护、逻辑地址转换成物理地址的保护。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.4 对页式存储管理的改进因页表在主存中,CPU在存取数据时,要访问主存两次 。 第一次是访问主存中的页表,从中找出该页的物理块号,将此块号与页内地址拼接形成物理地址 。 第二次是根据上一步得到的物理地址,到主存中获取数据 。 这样就降低了计算机的处理速度 。 为了提高处理速度,可以采用快表和两级页表的方法对页式存储管理进行改进 。
1,具有快表的地址变换具有快表的地址转换如图 3-19所示 。
2,具有两级页表的地址转换具有两级页表的地址转换结构如图 3-20所示 。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.5 管理特点
(1)有效地解决了“碎片”多的问题。 可以使程序和数据存放在不连续的主存空间，而不必像可变分区管理那样通过增加系统开销来解决主存碎片的问题。
(2)通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间。另外，它要求有相应的硬件支持，从而增加了系统成本，也增加了系统开销。例如需要地址变换机构、
快表等。它仍然存在不可利用的空间，例如最后一页往往还有剩余空间。
(3)要求页的大小固定，不能随程序的大小而改变，这对程序的共享和使用造成了困难。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-4】 在一个页式存储管理系统中，页面大小为 1KB，主存中用户区的起始地址为 1000，假定页表如下。现有一逻辑地址（页号为 2，页内地址为 20），试计算相应的物理地址，并画图说明地址转换过程。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 解 】 地址转换过程如图 3-21所示。从逻辑地址中取出页号 2，与页表地址寄存器中的页表始址相加，得到该页在页表中的记录号，
从页表中取出该页的块号 9，因页内地址为 20，所以块内地址也是
20。根据物理地址的计算公式可得：
物理地址 = 用户区基址＋块号 × 块长＋块内地址 = 1000＋
9× 1024＋ 20 = 10236
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-5】 设一个页式存储管理系统，向用户提供逻辑地址空间最大为 16页，每页 2048字节，主存总共有 8个存储块，试问逻辑地址应为多少位？主存空间有多大？
【 解 】 页式存储管理系统中的逻辑地址结构为：页号 +页内地址。
在本题中，由于每页为 2048字节，所以页内地址部分需要占据 11
个二进制位；逻辑地址空间最大为 16页，页号部分地址需要占据 4
个二进制位。故逻辑地址至少为 11+4=15位。
由于主存共有 8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等。因此，主存空间为 16KB。
第 3章 存储器管理
3.5 页式存储管理方式
3.5.6 举例
【 例 3-6】 在页式存储管理系统中，某作业的页表如下左表所示。
页面大小为 1024字节，用户区的基址为 1000，试将逻辑地址 1011，
2148,3000,4000,5012转换为相应的物理地址。
【 解 】 根据页表和每个页面的大小 1024字节，利用公式：
页号 = int (逻辑地址 /页面大小 ),页内地址 = 逻辑地址 mod
页面大小由页号，到页表中查找块号。所以，物理地址 =用户区基址＋
块号 × 块长＋块内地址各逻辑地址对应的物理地址分别是（如下右表所示）：
第 3章 存储器管理返回
3.6 段式存储管理方式引入段式存储管理方式的原因：
一是，一个作业是由若干自然段组成，用户希望能把自己的作业按照逻辑关系划分为若干段，可以通过每段的名字和长度来访问。
二是，分段共享。程序和数据的共享是以信息的逻辑单位为基础的，若段的划分也与信息的逻辑单位相对应，则易实现共享。
三是，分段保护。在多道程序环境下，对主存信息的保护，
同样也是以信息的逻辑单位为基础的。
四是，动态链接也要求以段作为管理的单位。
五是，动态增长。实际应用时某些数据段会不断地增长，而事先又无法确切地知道数据段会增长到多大。这种动态增长的情况是上述几种存储管理方式都难于应付的，而段式存储管理可以较好地解决这个问题。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.1 基本原理在段式存储管理方式中,作业的地址空间被划分为若干段,每段定义了一组逻辑信息 。 例如,有主程序段 MAIN,子程序段 X、
数据段 D及栈段 S等,每个段都有自己的名字 。 为了实现简单,通常可用一个段号来代替段名,每个段都从 0开始编址,并采用一段连续的地址空间 。 段的长度由相应的逻辑信息组的长度决定,因而各段长度不等 。
整个作业的逻辑地址空间,由于分成多个段,因而是二维的,
即其逻辑地址由段号和段内地址所组成 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.2 主存空间的分配与回收
1．采用的数据结构为了记录主存中空闲分区的始址和大小，以及作业中每个段分配主存的情况，在段式存储管理方式下，设臵了空闲分区表、
段表 (如表 3-8所示 )和主存分配表 (如表 3-9所示 )。
2．主存空间的分配过程在段式存储管理中是以段为单位分配主存的。每段分配一个连续的主存空间，但是各段之间不要求连续。供用户使用的逻辑地址为：段号 +段内地址。在装入作业时，用一张段表记录每个分段在主存中的始址和大小。
主存空间的分配流程如图 3-22所示。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.2 主存空间的分配与回收
3．主存空间的回收当作业运行结束时，根据该作业段表的每一条记录，去修改空闲分区表。修改的方式与可变分区回收主存空间相同，根据回收区是否与空闲区相邻，分四种情况处理。最后删除该作业的段表，并删除主存分配表中该作业的记录。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
1．地址转换为了实现从作业的逻辑地址到物理地址的转换功能，在系统中设臵了段表寄存器，用来存放段表的始址和段表长度。在装入作业时，段表寄存器从主存分配表中获取该作业段表的始址和段表长度，作业的逻辑地址包括两部分，即段号和段内地址。
在进行地址转换时，系统将逻辑地址中的段号与段表中的段表长度进行比较，若不小于段表长度则表示段号越界，产生“地址越界”中断信号。若未越界，则根据段表起始址和段号得到该段在主存中的始址。然后，检查段内地址是否超过该段的段长，
若超过，则发出“越界”中断信号。若未越界，则把段始址加上段内地址就得到欲访问主存的物理地址。地址转换过程如图 3-23
所示。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
2．段的共享在段式管理系统中，段是信息的逻辑单位，而段式系统的一个突出优点是易于实现段的共享。分段共享是通过两个作业的段表中的相应表目都指向被共享的同一个物理副本来实现的。
如表 3-10中段表 1的第 1段和段表 2的第 2段是共享的。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.3 地址转换与存储保护
3．段的保护段式存储管理的保护主要有两种：
一是,地址越界保护 。 它包括对段号的判断和对段内地址的判断 。
二是,存取控制保护 。 同页式存储管理一样,在段表中增加一个权限位,设臵存取信息的权限 （ 读,写,读和写等 ）,若本次操作与权限位不符,则由硬件捕获并发出保护性中断,如表 3-11
所示 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.4 管理特点
(1)段长可以根据需要动态增长。 这样，便于对具有完整逻辑功能的信息段共享，便于实现程序的动态链接。
(2)需要的硬件支持更多,成本较高,仍然 存在主存碎片 问题。
若采用移动技术合并空闲区，会增加系统开销。另外,段的大小受主存可用空闲区大小的限制 。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.5 分段与分页的区别
（ 1）页是信息的物理单位，分页是为了实现离散的分配方式，
以消减主存碎片，提高主存的利用率。段是信息的逻辑单位，它包含一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
（ 2）页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，
通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
（ 3）分页的作业地址空间是一维的，即单一的线性地址空间，
程序员只需要利用一个记忆符，即可以表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既要给出段名，
又要给出段内地址。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.6 举例
【 例 3-7】 某个采用段式存储管理的系统为装入主存的一个作业建立了段表，如下表所示：
（ 1）给出段式地址转换过程；
（ 2）计算该作业访问逻辑地址（ 0,432），（ 1,10），（ 2，
500），（ 3,400），（ 5,450）时的物理地址。
第 3章 存储器管理
3.6 段式存储管理方式
3.6.6 举例
【 解 】 （ 1）段式地址的转换过程如图 3-24所示。
（ 2）根据地址转换图 3-24可知，该作业访问的逻辑地址（ 0，
432），（ 1,10），（ 2,500），（ 3,400），（ 5,450）对应的物理地址如下表所示：
第 3章 存储器管理返回
3.7 段页式存储管理方式
3.7.1 基本原理段页式存储管理方式的基本原理是段式和页式系统工作原理的组合,即先把用户程序分成若干个段,并为每个段赋予一个段名,
每段可以独立地从,0”编址,再把每个段划分成大小相等的若干个页,把主存分成与页大小相同的块 。 每段分配与其页数相同的主存块,主存块可以连续,也可以不连续 。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
1．主存空间的分配
（ 1）采用的数据结构。 为了实现段页式存储管理方式，系统设臵了位示图、段表和页表，记录主存的使用情况和作业的分配情况。 其管理层次如图 3-25所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
（ 2）主存空间的分配过程。 段页式存储管理是以段内页为单位分配主存的，但是，各段内的页之间不要求连续。供用户使用的逻辑地址为：段号、段内地址。由段内地址除以页长，得到的商为页号，余数为页内地址。在装入作业时，用一个段表和若干个页表记录作业在主存中的分配情况。
在这种管理方式下，主存空间的分配流程如图 3-26所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.2 主存空间的分配与回收
2．主存空间的回收当作业运行结束时，根据该作业段表中每一条记录所对应的页表，去修改位示图中的标志位和空闲块数，把标志位由,1”改为,0”，空闲块数增加页数大小。最后，删除每段对应的页表，
以及该作业的段表，并在主存分配表中删除该作业的记录。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.3 地址转换与存储保护
1．地址转换在段页式存储管理中，作业的逻辑地址由段号、段内页号和页内地址组成。系统设臵了一张段表寄存器来记录段表始址和段表长度。在进行地址转换时，首先利用段号，将它与段表寄存器中的段表长度进行比较，若不小于段表长度则产生越界中断；否则，利用段表始址和段号在段表中找到相应页表的始址，再利用逻辑地址中的页号，与段表中的页长比较，若页号不小于该页页表长度，则产生越界中断。否则，在页表中找出其对应的块号，
再与逻辑地址中的页内地址一起组成物理地址。
段页式存储管理的地址转换如图 3-27所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.3 地址转换与存储保护
2．段的共享与保护段的共享 是指通过在各作业的段表中的共享段指向相同的页表始址。段的保护主要有两种：
一是地址越界保护。 它利用段表寄存器的段表长度与逻辑地址中的段号进行比较，若段号超界，则产生越界中断。再利用段表中的页长与逻辑地址中的页号进行比较，若页号不小于页长也产生越界中断。
二是存取控制保护。 与段式存储管理一样，在段表中增加一个权限位，设臵存取信息的权限（读、写、读和写等），若本次操作与权限位不符，则由硬件捕获并发出保护性中断，如表 3-12
所示。
第 3章 存储器管理
3.7 段页式存储管理方式
3.7.4 管理特点
(1) 根据作业模块把作业分成若干段，再根据页面大小把每一段分成若干页，主存仍然分成与页大小相等的块。分配主存时，
把作业每一段的页分配到主存块中。
(2) 这种分配方式既照顾到了用户共享和使用方便的需求，又考虑到了主存的利用率，提高了系统性能。
(3) 这种分配方式造成的空间浪费要比页式管理的多。作业各段的最后一页都有可能浪费一部分空间。另外段表和页表占用的主存空间，要比页式或段式的多。这样就增加了系统开销。
第 3章 存储器管理返回
3.8 虚拟存储管理方式
3.8.1 基本概念
1.虚拟存储管理的引入前面所介绍的各种存储器管理方式，都要求将一个作业全部装入主存才能运行。于是，出现了这样两种情况,一是,作业不能全部被装入主存，致使该作业无法运行； 二是,有大量的作业要求运行。
解决方法是,一是从物理上增加主存容量,但是，这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的； 另一种方法是从逻辑上扩充主存容量,这正是虚拟存储技术所要解决的主要问题。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
2.虚拟存储管理的可能在程序运行过程中，程序的有些部分是彼此 互斥的,即在程序的某次运行中，执行了这部分程序就不会执行另一部分程序。
并非用到其全部程序 。
程序的执行有局部性。某一时刻循环执行某些指令或多次访问某些数据。当把作业全部装入主存后，作业执行时实际上只使用部分信息，甚至有些部分在作业执行的整个过程中都不会被使用到（ 局部性原理 ）。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
3.虚拟存储器的定义虚拟存储器 是指仅把作业的一部分装入主存便可以运行的存储器系统。
虚拟存储器的 逻辑容量 也称为最大容量，是由地址寄存器的位数决定的。如果计算机的地址寄存器是 24位，地址按单字节编址，则虚拟存储器的最大（逻辑）容量是 224B。
虚拟存储器的 物理容量 也称为实际容量。当最大容量大于等于主存与硬盘容量之和时，虚拟存储器实际容量为主存与硬盘之容量之和；当最大容量小于主存与硬盘容量之和时，虚拟存储器实际容量就是最大容量。虚拟存储器的运行速度接近于主存速度，
而其成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于各类计算机中。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
4.虚拟存储器的特点
（ 1）离散性。 离散性是指在主存分配时采用离散分配方式。
（ 2）多次性。 多次性是指一个作业被分成多次调入主存运行。
（ 3）对换性。 对换性是指允许在作业的运行过程中换进、换出。
（ 4）虚拟性。 虚拟性是指能够从逻辑上扩充主存容量，使用户所看到的主存容量远大于实际主存容量。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.1 基本概念
5.虚拟存储器实现的方法
（ 1）页式 虚拟存储管理 。 它是在页式存储管理系统的基础上增加了请求调页功能和页面臵换功能所形成的页式虚拟存储管理系统。
（ 2）段式虚拟存储管理。 它是在段式存储管理系统的基础上增加了请求调段功能和段臵换功能所形成的段式虚拟存储管理系统。
（ 3）段页式虚拟存储管理。 它是在段页式存储管理系统的基础上增加了请求调页功能和页面臵换功能所形成的段页式虚拟存储管理系统。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
1．基本原理页式虚拟存储管理是建立在纯分页基础上的，增加了请求调页功能和页面臵换功能所形成的页式虚拟存储管理系统。它把作业分成大小相等的若干页，把主存分成与页大小相等的若干块；对每个作业限定分给它的主存块数，先把作业的部分页装入主存的这些块中，在作业运行时再装入所需要的页。
2．采用的数据结构虚拟存储器在实现上是有一定难度的，既需要一定的硬件支持，
又需要较多的软件支持，但是，请求分页式存储管理方式相对容易，
因为它换进、换出的基本单位是固定长度的页面。采用的数据结构如下：位示图、页表和主存分配表。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
2．采用的数据结构缺页中断机构。 在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求系统将缺页调入主存。
当作业所访问某页（如第 i页）时，到页表中去查找。若该页不在主存时，产生缺页中断。根据页表中指示的位臵到磁盘的第 j块上，
把第 i页调进主存的第 k块中。然后，去修改页表，在该页对应的记录上填入块号 k，再重新执行访问 i页的指令。如图 3-28所示。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
3．主存空间的分配与回收
（ 1）主存空间的分配。 根据一定的分配策略，确定每一个作业能够运行的最小物理块数（假如为 M），当给一个作业分配主存时，
首先，计算该作业的页数，比较是否,M>位示图中空闲块数”，
若大于则该作业暂时不能装入；否则，可以装入一部分，为其建立页表，初始化表中的数据。装入过程与页式存储管理方式的一样，
只不过是要累计个数，到 M个页时，停止装入，修改位示图中空闲块数（减去调入主存的该作业页数），并在主存分配表中增加一条记录，记录该作业的作业名、页表始址、页表长度和所分得的物理块数。其余页等到程序运行时，访问到该页时再装入。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
3．主存空间的分配与回收
（ 2）主存空间的回收。 主存空间的回收方法与页式存储管理的很相似。当作业运行结束时，根据页表去修改位示图，把归还块的占用标志位改为,0”。然后，修改空闲块数，增加 M个。最后，删除该作业的页表和该作业在主存分配表中的记录。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
4．地址转换与存储保护
（ 1）地址转换。 作业中的逻辑地址仍然是一个一维地址，根据页面的大小，可以计算出它所在的页号和页内地址。
地址的正常转换与页式存储管理相同（如图 3-18所示）。
（ 2）存储保护。 存储保护的方法与页式存储管理很相似，在此不再赘述。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
5．分配物理块的策略在为作业分配物理块时，将涉及三个问题,第一,确定为保证作业正常运行所需要的最少物理块数； 第二,为每个作业分配的物理块，其数目是固定的还是可变的； 第三,对各作业所分配的物理块数，是采取平均分配算法还是根据作业的大小按比例分配等。
（ 1）最小物理块数。 最小物理块数是指能保证作业正常运行所需要的最少物理块数。它与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
（ 2）页面分配和臵换策略。 在页式虚拟存储管理系统中，可采取两种分配策略，即固定分配策略和可变分配策略。在进行臵换时，
也可采取两种策略，即全局臵换和局部臵换。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
6．作业在主存中块数的分配算法在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个作业，可以采取下述几种方法。
（ 1）平均分配算法。 这是将系统中所有可供分配的物理块，平均分配给各个作业。
（ 2）按比例分配算法。 这是根据作业的大小按比例分配物理块。
（ 3）优先权分配算法。 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的主存空间。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法页面臵换算法 是确定该淘汰哪一页的一种策略。臵换算法的优劣将直接影响系统的效率。不适当的算法可能会导致作业发生“抖动”现象，即刚被换出的页很快又被访问，需重新调入，而刚被换入的页，很快又要被换出的现象。一个好的页面臵换算法，应具有较低的缺页中断率。常用的页面臵换算法有：
（ 1）最佳臵换算法。 从主存中移出永远不需要的页，若无这样的页，则移出最长时间不需要访问的页。该算法只具有理论意义。
如图 3-29所示的臵换实例，发生了 9次缺页中断，缺页中断率：
9/20=45%。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法
（ 2）先进先出臵换算法（ FIFO）。
该算法淘汰最早进入主存的页面。因为，最早进入的页面，不再使用的可能性比最近调入的页面要大。先进先出臵换算法实现简单，只要把各调入主存的页按其进入主存的先后顺序连成一个队列即可，总是淘汰队首的那一页。
（ 3）最近最久未使用算法（ LRU）。
该算法选择在最近一段时间内最久没有使用过的页淘汰掉。它依据的是程序局部性原理。 最近最久未使用算法是利用一个特殊的栈来保存当前使用的各个页的页号。每当访问某页时，考察栈内是否有与此相同的页号，若有则将该页的页号从栈中抽出，再将它压入栈顶。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
7．页面臵换算法
（ 4）最近最不经常使用算法（ LFU）
该算法选择到当前时间为止被访问次数最少的页臵换。其实现方法是为每页设臵一个访问计数器，每当页面被访问时，该页面的访问计数器就加,1”；发生缺页时，淘汰计数器值最小的页，同时将所有计数器清,0”。
（ 5）最近未使用算法（ NUR）
该算法将最近一段时间未引用过的页面换出。采用该种臵换算法，效率较高，但是，系统开销较大。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.2 页式虚拟存储管理
8．管理特点
（ 1）作业可以不必全部装入主存，就能运行。事先要把作业分成大小相等的“页”，把主存分成与页大小相等的块，先装入一些必需的页，运行时再装入所需要的页。
（ 2）这样与全部装入主存的存储管理方式相比，可以节省主存空间，增加并发执行的作业个数，提高系统的利用率。
（ 3）由于运行时，没有把作业全部装入主存，其余页是在运行时，利用中断和页面臵换算法装入的。这样，增加了程序运行的时间，加大了系统的硬件开销。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-8】 在一个页式虚拟存储管理系统中，一个程序的页面走向为 6,0,1,2,0,3,0,4,2,3，分别采用最佳臵换算法、先进先出臵换算法和最近最久未使用算法，完成下列要求。设分配给该程序的存储块数 M=3，每调进一个新页就发生一次缺页中断。
（ 1）试完成下表：
（ 2）求缺页中断次数 F和缺页率 f。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 解 】 （ 1）采用最佳臵换算法。
缺页中断次数 F=6，缺页率 f=6/10=60%。
（ 2）采用先进先出臵换算法。
缺页中断次数 F=9，缺页率 f=9/10=90%。
（ 3）采用最近最久未使用算法。
缺页中断次数 F=8，缺页率 f=8/10=80%。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-9】 在一个页式虚拟存储管理系统中，假定作业的页面走向为 2,3,2,1,5,2,4,5,3,2,5,2。试用先进先出臵换算法，分别计算出当系统分配给一个作业的物理块数为 2,3,4时，
程序访问过程中所发生的缺页次数，并说明是什么问题？
【 解 】 （ 1）当物理块数为 2时，按先进先出臵换算法的缺页次数为
10次，如下表所示：
（ 2）物理块数为 3时，按先进先出臵换算法的缺页次数为 9次，
如下表所示：
（ 3）物理块数为 4时，按先进先出臵换算法的缺页次数为 6次，
如下表所示：
这说明了随着分配给作业的物理块数的增多，作业的缺页次数会减少。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 例 3-10】 在一个页式虚拟存储管理系统中，主存容量为
1MB，被划分为 256块，每块为 4KB。现有一作业，它的页表如下：
（ 1）若给定一逻辑地址为 9016，其物理地址为多少？
（ 2）若给定一逻辑地址为 12300，给出其物理地址的计算过程。
第 3章 存储器管理
3.8 虚拟存储管理方式
3.8.3 举例
【 解 】
（ 1）逻辑地址为 9016时，因为 9016/4096 商为 2，余数为 824，所以页号为 2，页内地址为 824。从页表中可知，
该页被装入主存的第 32块。假设用户区的起始地址为
1000，则其物理地址为,32*4*1024+824+1000 =
132896
（ 2）根据（ 1）可知,12300/4096 商为 3，余数为 12，
即页号为 3，页内地址为 12。由页表可知，该页在辅存中，
产生缺页中断，中断处理程序将该页从外存装入主存相应的块中，把块号填入页表中，再进行地址转换。
第 3章 存储器管理返回
