第五课 存储器管理 (Memory Management)
教学 目的,
存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充大主存，对主存信息实现有效保护是存储器管理主要任务，
也是各种不同存储管理方法的目标。“瓶颈”问题。
教学要求：
熟悉 存储管理目的和 功能，掌握地址重定位的概念。
熟悉 单一连续分配,固定分区分配,动态分区分配 实现 原理；
掌握 可变式分区分配的 数据结构和 分配 回收算法,掌握 动态重定位分区分配 实现 原理和分配 算法。
熟悉 覆盖与交换 的概念。
熟练掌握 分页存储管理 原理,熟练掌握 基本的地址变换机构和具有快表的地址变换机构,了解两级页表机制 。
掌握 分段存储管理 原理和 分段地址变换机构,掌握分页和分段比较，熟 悉 分页和分段的共享，掌握 段页 式 存储管理 原理和 地址变换机构。
5.1 存储管理概述存储管理目的和 功能：
1。 主存储器 （ 内存 ） 的分配和回收内存分配的主要任务是为每一道程序分配内存空间,使它们
,各得其所,。 使程序员无须关心存储分配问题,由 OS完成 。
2。 存储保护内存保护的任务是确保每道程序都在自己的内存空间运行,
互不干扰 。 程序与 OS也互不干扰 。
3。 地址映射,一个应用程序经编译后 ----若干个目标程序 — 链接形成可装入程序 。 逻辑地址 ----物理地址 。
4。 内存 扩充内存 扩充的任务是从逻辑上来扩充内存容量,使用户认为系统所拥有的内存空间远比其实际的内存空间 （ 硬件 RAM） 大的多 。
请求调入和置换功能 。
提高主存储器的利用率,减少不可用的存储空间 （ 称为,零头 ）,允许 多道程序 动态共享主存 。
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接一个用户源程序变为一个可在内存中执行的程序要做：
1）编译 用户源代码 —>几个目标模块 /程序。
2）链接 由链接程序把目标模块 +它们所需库函数 —>可装入模块。
3）装入 由装入程序把装入模块 —>内存。
例：一个 PASCAL源程序。
5.2.1 程序的装入装入模块内存
OS
用户区
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接例：一个可执行程序 ball.exe/play.exe,直接输入 ball/play即可，
装入程序?内存运行（涉及到内存分配问题）。
一次装入?静态分配问题（一次性地把进程所需资源分配给它）。
部分装入?动态分配问题绝对装入可重定位装入运行时装入一、绝对装入方式（适应于单用户系统）汇编 8088中启动各个段。
由编程人员指定位置装入内存 /或编译程序对源程序编译时，所用的是实际存储地址。若是多用户，必须默契，实际工作中不可能。所以多用户系统不采用该方式。
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接二、可重定位装入在装入时才确定对进程 /作业的内存分配，需采用下述两个技术手段：
1）把逻辑地址与物理地址分开；
2）对逻辑地址采用地址重定位；
两个概念：地址空间和存储空间。
1,地址空间在源程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合称为,名字空间,。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以,0”作为参考地址的模块。然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行。我们把目标模块中的地址称为相对地址（或称为“逻辑地址”），而把相对地址的集合称为“相对地址空间”或简称为,地址空间,。
2、存储空间 主存中一系列存储信息的物理单元的集合。这些单元的编号成为物理地址或绝对地址。
5.2程序的装入和链接
3,什么是 地址重定位？
装配模块虽然具有统一的地址空间,但是仍是以,0” 作为参考地址,即是浮动的 。 要把它装入内存执行,就要确定装入内存的实际物理地址,并修改程序中与地址有关的代码,这一过程称为 地址重定位 。 即从逻辑地址?物理地址相对地址?绝对地址程序的名字空间,地址空间和存储空间之间的关系如图所示：
汇编 /编译 地址重定位连 接 装 入名字空间 地址空间 存储空间
（ 相对地址 /逻辑地址空间 ） （ 绝对地址 /物理地址空间 ）
符 号源 程 序 相对目标程序 （ 装配模块 ）
绝对目标程序
4、地址重定位类型地址重定位完成把相对地址转换成内存中的绝对地址，这个过程称为地址映射
（ map）。 按照重定位的时机，可分为静态重定位和动态重定位。
1）静态重定位静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的 。
在一些早期的系统中都有一个装入程序 （ 加载程序 ）,它负责将用户程序装入系统,并将用户程序中使用的访问内存的逻辑地址转换成物理地址 。 如图所示 。
地址重定位 -2
0,10000：
100 LOAD 1,2500 10100,LOAD 1,12500
2500,365 12500,365
2600,12600：
程序的地址空间 内存的地址空间例如,LOAD 1,2500 这条指令是把相对地址为 2500的存储单元的内容 365装入 1号累加器 。 而这时内容为 365的存储单元的实际物理地址为 12500（ 起始地址 10000+相对地址 2500）,所以
LOAD 1,2500 这条指令中的直接地址码要作相应的修改,即改为 LOAD 1,12500。
地址重定位 -3
在程序中需要修改的位置称为重定位项。程序装入内存中的起始地址称为重定位因子。为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表。所以操作系统的装入程序要把装入模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，加上重定位因子得到欲修改位置的实际地址，最后对实际地址中的内容再加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。
静态重定位虽然有无须硬件支持的优点，但是也存在明显的缺点：一是程序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。
2001年 9月 20日 9时 23分 计算机操作系统
2） 动态重定位动态地址映射动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的 。
系统中设置了重定位寄存器 。
地址重定位 -3
地址重定位 -4
动态重定位动态重定位是指在程序执行过程中进行地址重定位,即在每次访问内存单元前才进行地址变换 。 动态重定位可使装配模块不加任何修改就装入内存,但是它需要硬件 — 重定位寄存器的支持 。
下图给出了 动态重定位的示意图 。
程序的目标模块在装入内存时,与地址有关的指令都无须进行修改,如在图 中 LOAD 1,2500这条指令中仍保持相对地址 2500。 当该模块被操作系统调度到处理机上执行时,操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址 （ 图 中该模块的基地址为 0）,然后将其差值装入重定位寄存器 。 当 CPU取一条访问内存的指令时,地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加,再根据和值作为内存的绝对地址去访问该单元的数据 。
1000
动态重定位的示意图重定位寄存器
10000
0,10000：
100,LOAD 1,2500 10100,LOAD 1,2500
+
2500,365 12500,365
2600,12600：
程序的地址空间 内存的地址空间地址重定位 -5
由此可见，动态重定位是在指令执行过程中动态进行，这样可以带来两个好处：
⑴目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。⑵一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。
三、动态运行时装入方式内存较小时，实际运行时换入换出，且使用的内存区域大小也可改变。
不是一次性装入，而是多次装入。
装入模块内存
OS
用户区
5.2.2 程序的链接用户程序的上机过程：
1）编译 用户源代码 —>几个目标模块 /程序。
2）链接 由链接程序把目标模块 +它们所需库函数 —>可装入模块。
3）执行 由装入程序把装入模块 —>内存 —> 执行。
一,静态链接：一次性地把若干目标模块链接成一个装入模块,以后不再拆开 。
P136图 5-4。
需解决的问题：
1,对相对地址的修改 。
编译把用户源代码 —>几个目标模块,其起始地址都为 0,每个模块中的地址都是相对于这个 0地址的 。
2,变换外部调用符号 。
把每个模块中的外部调用符号?相对地址 。
二,装入时动态链接：边装入内存边链接 。 在装入一个目标模块时,若发生一个外部模块调用,将引起装入程序去找出相应的外部模块,并将它装入内存；同时也要修改目标模块中的相对地址 。
优点,1,可单独修改各个目标模块,易修改,而静态链接不可能修改 。
2,装入时动态链接易于实现共享 。 而静态链接必须 COPY。
5.2.2 程序的链接三,运行时动态链接装入时动态链接,但一旦装入,模块就无法改变,而且每次执行时的装入模块都相同 。 实际上,每次运行时装入模块不完全相同,
例 ERROR处理模块 --->执行时链接的方式 。 这样做,有一些模块不用事先装入内存,可节省存储空间 。
5.3 各种存储管理方案
5.3.1单一用户（连续区）存储管理单用户在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供 OS使用，一个供用户使用。这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在 8位和 16
位微机上 CP/M和 MS-DOS操作系统。它将内存分为两个区：
系统区：仅供操作系统使用，通常设置在内存的低段；
用户区：指除系统区以外的全部内存空间，提供给用户使用。
这种存储分配方式由于用在单用户、单任务的操作系统中。 地址映射和 存储保护措施 如下图 。
内存 OS
用户
OS
用户
OS
…
用户
OS
界限寄存器 重定位寄存器 (基址 )
+CPU <
内存地址错逻辑地址 Y
N 物理地址
5.3 各种存储管理方案
2001年 9月 20日 9时 23分 计算机操作系统基址,限长寄存器保护法用的是程序的逻辑地址 。
在这种存储管理技术中,系现设置一个专用寄存器,称为基地址寄存器,当一个进程 （ 或程序,作业 ） 被调度运行时,系统首先从 PCB中取出该进程的首地址装入基地址寄存器中,在该进程运行的过程中实现动态地址映射 。
5.3 各种存储管理方案
60K 非法区用户非法区64K
基址寄存器限长寄存器
60K
124K
5.3.2 固定分区 (Fixed Partitioning)分配
1、概念固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。
例：开机，由引导程序把 OS?内存,OS接管整个机子（软 /硬件资源），内存分区由 OS事先指定好，每个分区个数、长度已固定，再为每个用户分配相应分区。
主要适用于多道程序，几个分区 几个作业。
2、划分分区方法
1）大小相等。
2）大小不等。 P140图 5-6。
3、内存分配及管理。
系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和 内存分配图 如下所示。
0k：
20k：
第 1分区 （ 16kb）
36k：
第 2分区 （ 32kb）
（ 已分配 ）
68k：
第 3分区 （ 64kb）
（ 已分配 ）
132k：
第 4分区 （ 124kb）
（ 未分配 ）
256k：
（ b） 内存分配图区号 大小 起址 标志
1 16KB 20K 已分配
2 32KB 36K 已分配
3 64KB 68K 已分配
4 124KB 132K 未分配
(a) 分区说明表固定式分区实现技术简单
，但是内存的利用率不高，
适用于作业的大小和多少事先都比较清楚的系统中。它用于 60年代的 IBM-360的 MFT
操作系统中。例：有一 10K的作业到，如何分配？ 60K的作业到，如何分配？
内零头操作系统作业 A（ 16k）
作业 B（ 26k）
作业 C（ 56k）
5.3.2 固定分区 (Fixed Partitioning)分配
5.3.3动态 /可变式 (Dynamic Partitioning)分区分配
1,概念：
可变式分区是指在作业装入内存时,从可用的内存中划出一块连续的区域分配给它,且分区大小正好等于该作业的大小 。 可变式分区中分区的大小和分区的个数都是可变的,而且是根据作业的大小和多少动态地划分,因此又称为动态式分区 。 这种存储管理技术是固定式分区的改进,既可以获得较大的灵活性,又能提高内存的利用率 。
2,可变式分区的分配和释放的基本思想是：
在分配时,首先找到一个足够大的空闲分区,即这个空闲区的大小比作业要求的要大,系统则将这个空闲分区分成两部分：一部分成为已分配的分区,剩余的部分仍作为空闲区 。 在回收撤除作业所占领的分区时,要检查回收的分区是否与前后空闲的分区相领接,若是,则加以合并,使之成为一个连续的大空间 。
Example Dynamic
Partitioning
Operating
System
Process 1 320 K
Process 2
Process 3
224 K
288 K
64 K
Operating
System
Process 1 320 K
Process 3
224 K
288 K
64 K
Operating
System
Process 1 320 K
Process 3 288 K
64 K
Process 4 128 K
96 K
Example Dynamic
Partitioning
Operating
System
320 K
Process 3 288 K
64 K
Process 4 128 K
96 K
Operating
System
Process 3 288 K
64 K
Process 4 128 K
96 K
Process 2 224 k
96 K
动态 /可变式分区分配 -1
3。可变式分区数据结构
空闲区表形式空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。
空闲区链形式为了实现对空闲分区的分配和链接，在每个分区的起始部分，
设置一些用于控制分区分配的信息（如分区的大小和状态位），
以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。
P141图 5-7/5-8。
0k：
20k：
52k：
116k：
164k：
260k：
512k：
（ c） 内存分配图可变式分区数据结构图表序号 P大小 起址 状态
1 48k 116k 空闲
2 252k 260k 空闲
3 — — 空表目
4 — — 空表目
5 — — 空表目
（ a） 空闲分区表操作系统作业 1（ 32k）
作业 2（ 64k）
空闲区 （ 48k）
作业 4（ 96k）
空闲区 （ 252k）
前向指针N+
2
0
0 后向指针N+
2
0
0
N个字节可用
（ b ）空闲链结构
4 分区分配 算法 (Partitioning Placement Algorithm)
1） 最佳适应算法 （ Best Fit）,它从全部空闲区中找出能满足作业要求的,且大小最小的空闲分区,这种方法能使碎片尽量小 。 为适应这种算法,空闲分区表
（ 空闲区链 ） 中的空闲分区要 按大小 从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配 。 看似最佳,实则未必 。 因为这样做导致小的空闲区越来越多 。
2） 首次适应算法 （ First Fit）,从 空闲分区表 的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法目的在于减少查找时间 。 为适应这种算法,空闲分区表 （ 空闲区链 ） 中的空闲分区要按地址由低到高进行排序 。
3） 循环首次适应算法,该算法是首次适应算法的变种 。 在分配内存空间时,不再每次从表头 （ 链首 ） 开始查找,而是从上次找到的空闲区的下一个空闲区开始查找,直到找到第一个能满足要求的的空闲区为止,并从中划出一块与请求大小相等的内存空间分配给作业 。 该算法能使内存中的空闲区分布得比较均匀 。
4） 最坏适应算法,从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业； 空闲 分区按大小由大到小排序 。
外零头,经过一段时间的分配与回收后,内存中存在很多很小的空闲块 。 每一个都很小,不足以满足分配要求 。 这些空闲块称为外零头 。
Dynamic Partitioning
Placement Algorithm
Last
allocated
block (14K)
Before After
8K 8K
12K 12K
22K
18K
6K 6K
8K 8K
14K 14K
6K
2K
36K 20K
Next Fit
Free block
Allocated block
Best Fit
First Fit
例,分配一个 16KB分区
5 UNIX分配 回收算法（采用 空闲分区表 结构和 首次适应算法）
UNIX空闲分区表 数据结构
Coremap
m_addr
m_size
…,.
m_addr
m_size=0
…,..
m_addr
m_size
m_addr
m_size
m_addr
m_size
m_addr
m_size
空闲分区表中的空闲分区要 按 地址从低到高连续排序，最后一个空闲分区中
m_size为 0表示以上表目空白。空闲分区表起始地址为 coremap
分配和释放的基本思想是：在分配时，
首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，
使之成为一个连续的大空间。
UNIX 分配 算法框图申请分配一个 u.size大小的分区从头开始查表是否检索完毕？ 本次无法分配
m.size>u.size
m.size-u.size≤size？
从 该 分 区 中 划 出
u.size大小的分区继续检索下一个表项将该表目以上的所有表目下移一格将该分区分配给申请者修改有关的数据结构返 回
Y
N
N
UNIX 回收算法当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如下图 所示，其中 F1,F2表示回收区的前、后空闲区）,
当回收区既不与 F1领接，又不与 F2领接时（如 A）,应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。
当回收区只与插入点的前一个分区 F1相领接时（如 B）,应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改 F1分区表目的大小 m_size即可。
当回收区只与插入点的后一个分区 F2相领接时（如 C）,将把两个空闲区合并，修改 F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。
UNIX 回收算法
当回收区与插入点的前,后两个分区 （ F1和 F2） 都相领接时 （ 如
D）,合并三个分区,用 F1表目的起址作为新空闲区的起址,修改其大小为三块分区之和,最后取消 F2的表目 。
A B C D F1
回收区
F2
回收区
F2
回收区
F1
回收区
UNIX 回收算法框图是否否是是 否将该表目以上的所有表目上移一格,并插入新释放的可用区表目顺序地检索可用资源表直至找到某表目的
m.addr>aa或 m.size=0
不是第一个表目与前一可用区相邻？与后一可用分区相邻且不为空表目？
把所释放的可用区与前一分区合并所释放的可用区与一可用区合并所释放可用区的 size=0
与后一可用区 相邻
？
与后一可用区合并将该表目以上的所有表目下移一格返 回
mfree
是否
5.3.4 动态重定位分区分配
1。 拼接 /紧凑可变式分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，
另一方面系统在拼接时要耗费较多的时间。
2.动态重定位实现紧凑所需的允许作业在运行过程中在内存中移动的技术必须获得硬件支持。只有具有动态重定位硬件机构的计算机系统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括重定位寄存器和加法器。
动态重定位分区分配
3,动态重定位分区分配算法动态重定位分区管理中何时进行存储器紧缩有二种不同的解决办法：
在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，
此法很花费机时。
当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但表格管理复杂。采用此法的动态重定位分区分配算法框图如下：
动态重定位分区分配 算法框图
N N
Y Y
请求分配
u.size分区检索空闲分区链 （ 表 ）
无法分配返回空闲分区总和
≥ u.size
找到大于
u.size的可用区否？
进行紧凑形成连续空闲区修改有关的数据结构按动态分区方式进行分配修改有关的数据结构返回分区号及首址
5.4 覆盖与交换
(1)覆盖技术
1,覆盖的概念为了能在小的内存空间中运行大的作业，许多机器（如 PDP－
11,IBM－ PC） 都采用了“覆盖”技术。覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间。
覆盖技术通常与单用户连续分配、固定分区和可变分区等存储管理技术配合使用。它不但用于用户作业的运行中，而且还常用于操作系统本身的运行中。
覆盖技术覆盖技术的基本概念可用下图来加以说明，一个作业由一个主程序段 MAIN主若干程序／数据段组成，其调用关系如 a所示，我们把树形关系中常驻内存的段 ―― 主程序段 MAIN叫根段，其余覆盖部分分成层次,A0与 B0为一层，组成一个覆盖段 0，同理 A1,A2与 B1组成覆盖段 1，在 A3和 A4组成覆盖段 2，同一时间内同一覆盖段的各程序段（称为覆盖），只有一个覆盖在执行可被引用，它不能调用同层中的其它覆盖。
如不采用覆盖技术，该作业要求 270K主存，采用覆盖技术后只要求 160K主存。
覆盖技术
（ a） (b)
MAIN
20K
A0
30K
B0
40K
A1
60K
A2
30K
B1
30K
A3
20K
A4
40K
覆盖段 0
40K
覆盖段 1
60K
覆盖段 2
40K
MAIN
A0
A1 A2
A3 A4
B1
B0
2.覆盖处理
覆盖结构的输入
PDP－ 11的 RSX－ 22H提供覆盖描述语言 ODL来描述结构，并构成覆盖描述文件，如上图用 ODL语言表示如下：
ROOT MAIN－（ A0－（ A1,A2－（ A3,A4））,B0－（ B1，
B2））；
END
覆盖数据结构用户将覆盖描述文件随目标程序一起提交系统，系统根据覆盖描述文件形成一个覆盖数据结构。该数据结构对每个覆盖段有一个描述信息，它包括覆盖段号、覆盖数、当前覆盖号、覆盖区始址、覆盖区长度、起始盘区号等。系统根据覆盖调度程序和覆盖调度结构自动地将各程序段装入运行。
（ 2）交换（对换）技术交换技术最早用在麻省理工学院的兼容分时系统 CTSS中，该系统是单用户系统，所有用户都驻留在外存的后备队列中，每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。这是早期的简单分时系统，它采用早期的交换（调进／凋出）
来满足多个程序共享主存的需要。
1。多道程序环境下的对换在多道程序环境下为了提高内存和 CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。
UNIX早期已引入对换功能并一直保留至今,UNIX系统设置一个对换进程完成以上功能。为了实现进程对换，系统必须能实现对对换空间的管理，进程换入和进程换出等三项功能。
交换（对换）技术
2。对换空间的管理外存分为文件区和对换区。文件区用户存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分散方式；
对换区用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。
UNIX对换区采用空闲分区表和首次适应算法的动态分区管理，
类同早期内存管理。
3。进程的换出与换入当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞和睡眠状态的进程换出，如无则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。而当内存又空时对换进程在对换区中选择换出时间长的处于就绪态的进程调入。
5.5 分页存储管理的基本方法问题的提出：
分区存储管理的主要问题是碎片问题。
在采用分区存储管理的系统中，会形成一些非常小的分区，
最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。
造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。
5.5 分页存储管理的基本方法
5.5.1 纯分页存储管理原理
1,分页分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域,称为页 /页面,相应地,将内存空间划分成与页相同大小的若干个物理块,称为块或页框 /物理块 。 在为进程分配内存时,以页面为单位进行分配 。 将进程中的若干页分别装入多个不相邻接的块中 。
进程 1
进程 2
进程 3
进程 1
进程 1
进程 2
进程 2
进程 3
进程 2
纯分页存储管理原理 -1
2。 地址结构分页系统的地址结构如下图 所示,它由两部分组成：前一部分为页号 P； 后一部分为位移量 W,即页内地址 。 图中的地址长度为 32位,其中 0～ 11位为页内地址 （ 每页的大小为 4K）,12～ 31位为页号,所以允许地址空间的大小最多为 1M个页 。
31 12 11 0
3。页表在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图 所示 ）。每个页在页表中占一个表项，
记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
页号 P 位移量 W
纯分页存储管理原理 -2
页表是页式存储管理的数据结构,它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。
页号 内存块号 存取控制 状态 其它
0
1
2
3
0
1
2
3
4
5
6
7
用户程序 页 表 内 存页号 块号
0 2
1 4
2 5
3 7
5.5.2 地址变换机构页表可以完成从逻辑地址 — 物理地址的映射；
地址空间 — 存储空间的映射。 如何完成？
地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。
1。基本的地址变换机构
1）几点说明
（ 1）进程访问某个逻辑地址时，地址变换机构自动地把有效地址 /相对地址分为 2部分?页号与页内地址；
（ 2） 页内地址（ 0~1023）与块内地址 /页框内地址（ 0~1023）一一对应，无须转换。
（ 3）页表通常存放于内存中，必须有一个存放页表的起始地址。
在系统中设置页表寄存器，用来存放页表在内存的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的 PCB中，当该进程被调度时，就将它们装入页表寄存器。
（ 4）将物理地址?物理地址寄存器中 块号块内地址
5.5.2 地址变换机构
2）实现过程首先由进程访问的逻辑地址 页内地址页号?与页表寄存器中的页表长度比较?ERROR中断页号 *页表项长度 +页表在内存的始址（页表寄存器中）
计算出该页在页表项中的位置查页表，得该页物理块号块内地址物理块号 装入物理地址寄存器中未越界越界地址变换机构 -1
越界中断页表寄存器 逻辑地址 2500
页号 块 号
0
1
2
每页 1KB(1024) 物理地址 5572
5*1024+452
块号 5 块内地址 452
页 号 2 页内地址 452页表始址页表长度 ﹥
=
2
4
5
2。具有快表的地址变换机构
如果页表存放在内存中,则每次访问内存时,CPU存取一个数据必须访问两次内存 第 1次,访问内存中的页表?物理地址
第 2次再访问内存,去存取物理地址中的数据
从而使计算机的处理速度降低了 1/2。
为了提高地址变换的速度,在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器,称为,联想存储器,或
,快表,。
快表内容,用以存放当前访问的那些页表项 。
此时地址变换过程为：在 CPU给出有效地址后,地址变换机构自动地将页号送入高速缓存,确定所需要的页是否在快表中 。 若是,
则直接读出该页所对应的物理块号,送入物理地址寄存器；若在快表中未找到对应的页表项,则需再访问内存中的页表,找到后,
把从页表中读出的页表项存入快表中的一个寄存器单元中,以取代一个旧的页表项 。
具有快表的地址变换机构 -1
由于成本的原因，快表不可能做得很大，通常只能存放 16~512个页表项。例如，在 Intel80486中有 32个。这对中、小型作业来说，
已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。
由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到 80%～ 90%。例如，假设检索联想存储器的时间为 20ns，
访问内存的时间为 100ns,访问联想存储器的的命中率为 85%，则
CPU存取一个数据的平均时间为 T=0.85*120+0.15*220=135ns，
所以访问时间只增加 35%。如果不引入联想存储器，其访问将延长一倍（达 200ns）。
具有快表的地址变换机构 -2
越界中断页表寄存器 逻辑地址页号 块号页 号 块 号 0 2
0 1 4
1 2 5
2
快 表页 表 物理地址页 号 页内地址页表始址 页表长度 ﹥
2
4
5
块号 块内地址输入寄存器
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算虚地址结构 (程序字 )
虚地址是用户程序中的逻辑地址 /相对地址 /有效地址,它包括页号和页内地址 （ 页内位移 ） 。
区分页号和页内地址的依椐是页的大小,页内地址占虚地址的低位部分,页号占虚地址的高位部分 。
假定页面大小 1024字节,虚地址共占用 2个字节 (16位 )
页号 页内地址 （ 位移量 ）
P W
15 10 9 0
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---虚地址结构
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
1,虚地址 （ 逻辑地址,程序地址 ） 以十六进制,八进制,二进制的形式给出
将虚地址转换成二进制的数；
按页的大小分离出页号和位移量 （ 低位部分是位移量,高位部分是页号 ） ；
根据题意产生页表 ；
将位移量直接复制到内存地址寄存器的低位部分；
以页号查页表,得到对应页装入内存的块号,并将块号转换成二进制数填入地址寄存器的高位部分,从而形成内存地址 。
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
2.虚地址以十进制数给出
页号＝虚地址 DIV 页大小
位移量＝虚地址 mod 页大小
根据题意产生页表；
以页号查页表,得到对应页装入内存的块号
内存地址＝块号 × 页大小＋位移量
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
例 1：有一系统采用页式存储管理,有一作业大小是 8KB,页大小为 2KB,依次装入内存的第 7,9,A、
5块,试将虚地址 0AFEH,1ADDH转换成内存地址 。
虚地址 0AFEH
0000 1010 1111 1110
P＝ 1 W＝ 010 1111 1110
MR＝ 0100 1010 1111 1110
＝ 4AFEH
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
虚地址 1ADDH
0001 1010 1101 1101
P＝ 3
W＝ 010 1101 1101
MR＝ 0010 1010 1101 1101＝
2ADDH
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
虚地址 3412
P＝ 3412 ％ 2048 ＝ 1
W＝ 3412 mod 2048
＝ 1364
MR=9*2048+1364=19796
虚地址 3412的内存地址
是,19796
例 2：有一系统采用页式存储管理，有一作业大小是 8KB,页大小为 2KB,依次装入内存的第 7,9,10,5块，试将虚地址 7145,3412转换成内存地址。
2001年 9月 20日 9时 23分 计算机操作系统
虚地址 7145
P＝ 7145 ％ 2048 ＝ 3
W＝ 7145 mod 2048
＝ 1001
MR=5*2048+1001=11241
虚地址 7145的内存地址是：
11241
关于分页的地址变换计算 ---页式地址映射
5.5.3 两级页表机制
80386的逻辑地址有 232B,如 页面大小为 4KB（ 212B）,则页表项达
1M个，每个页表项占用 4B,故每个进程的页表占用 4MB内存空间，
还要求是连续的，显然这是不现实的。
在 80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。
两级页表机制
两级页表系统将 32位逻辑地址空间的地址分成三段：其中,页表目录号 （ 外层页号 p1） 和页号 （ 外层页内地址 p2） 两项各占 10位,偏移量 （ 页内地址 d） 占 12位 。 每页的大小为 4KB。 由于物理块号和页表的物理地址都占 4个字节,使每页中包含 1024个页表项,所以页表目录和页表的大小也都是 4KB,即一页 。 在 80386中设置了一个外层页表寄存器 （ CR3）,用于存放页表目录的基址 。 两级页表的逻辑地址结构和 两级页表的 地址变换机构图如下：
31 22 21 12 11 0
外层页表 页表 物理地址 返回外层页号 p1 外层页内地址 p2 页内地址 d
外层页表寄存器 + + b d
两级页表机制图第 0页页表 （ 物理块号 10） 内 存
0
1
0 ┇
1 1023
2 第 1页页表 （ 物理块号 25）
0
1
┇
1023
第 N页页表 （ 物理块号 120）
0
1
外层页 表 ┇
1023
10
25
120
12
14
32
35
151
152
0
1
……
12
13
14
……
32
33
34
35
……
151
152
……
5.6 分段存储管理
5.6.1 分段存储管理方式的引入分页从根本上克服了外零头（地址空间、物理空间都分割）。
内存利用率缺点：无论信息内容如何，按页长分割，分割后 ---内存，有可能主程序未能全部进入内存,-----执行速度降低。所以考虑以逻辑单位?内存如
PL
最后一个单元可能未占满，还有内零头，
平均浪费 PL/2大小的空间主程序函数数组工作区进程 主程序函数数组工作区分段存储管理方式的引入分页从根本上克服了外零头（地址空间、物理空间都分割）。
内存利用率缺点：无论信息内容如何，按页长分割，分割后 内存，有可能主程序未能全部进入内存,执行速度降低。所以考虑以逻辑单位 内存如分段存储管理方式的引入 -1
1。 便于编程通常用户常常把自己的作业按照逻辑关系划分成若干个段,每个段都有自己的名字,且都从零开始编址,这样,用户程序再执行中可用段名和段内地址进行访问 。
例如,LOAD 1,[A] | <D> 这条指令的含义是将分段 A中的 D单元内的值读入寄存器 1。
2。 分段共享在实现程序和数据的共享时,常常以信息的逻辑单位为基础,而分页系统中的每一页只是存放信息的物理单位,其本身没有完整的意义,因而不便于实现信息的共享,而段却是信息的逻辑单位,有利于信息的共享 。
3。分段保护 信息保护是对相对完整意义的逻辑单位（段）进行保护。
4。动态链接通常一个源程序经过编译后所形成的若干个目标程序，还需再经过链接，形成可执行代码后才能运行，这种在装入时进行的链接称为 静态链接 。 动态链接 是指在作业运行之前，并不把几个目标程序段都链接起来，而是先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段（目标程序）
调入内存并链接起来。所以，动态链接是以段为基础的。
5。动态增长在实际系统中，往往有些数据段会不断地增长，而事先却无法知道数据段会增长到多大，分段存储管理方式可以较好地解决这个问题。
5.5.2 分段系统的基本原理一,分段的基本思想：
在分段存储管理方式中,作业的地址空间按逻辑关系被划分为若干个段,每个段定义了一组完整的逻辑信息 （ 如有主程序段,子程序段,数据段及堆栈段等 ）,
每个段都有自己的段名,且有一个段号 。 段都是从 0开始编址的一段连续的地址空间,各段长度是不等的,由逻辑信息长度决定 。 对应的内存划分也是以段为单位划分,每一个段在内存中占据连续空间 （ 内存随机分割,需要多少分配多少 ）,但各段之间可以不连续 。
二,概念
1,地址结构分段系统的地址结构如下图 所示,逻辑地址由段号 （ 名 ） 和段内地址两部分组成 。
在该地址结构中,允许一个作业最多有 64 K个段,每个段的最大长度为 64 KB。
31 16 15 0
段 号 段 内 地 址分段系统的基本原理 -1
2．段表在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。在系统中为每个进程建立一张段映射表，简称为,段表,。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为,基址,）
和段的长度，如下图所示。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。
内存空间
0
40k：
80k：
120k：
150k：
分段系统的基本原理 -2段表的作用图作业空间
MAIN） =0
0 段 表
15K 段号 段长 基址
（ X） =1 0
0 1
7K
（ D） =2 2
0
8K 3
（ S） =3
0
10K
15K 40K
7K 80K
8K 120K
10K 150K
（ MAIN）
=0 15K
（ X） =1
7K
（ D） =2
8K
（ S） =3
10K
0
15k
地址变换机构 -1
三 地址变换机构
1、段表寄存器：为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。
2、过程：
在进行地址变换时，系统将逻辑地址中的段号 S与段表长度 TL进行比较。若 S≥TL,表示段号太大，访问越界，于是产生越界中断信号；
若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址 d是否超过该段的段长 SL。 若超过，即 d≥SL,同样发出越界中断信号；若未越界，则将该段的基址与段内地址 d相加，得要访问的内存物理地址。
5.5.2 地址变换机构
2 实现过程首先由逻辑地址 段内地址 d
段号?与段表寄存器中的段表长度比较?ERROR中断段号 *段表项长度 +段表在内存的始址（段表寄存器中）
计算出该段在段表项中的位置段内地址 d与段表中的段长 SL比较 d>=SL越界段内地址 d+段表中的该段的起始地址物理地址未越界越界
3 地址变换机构段表寄存器 越界中断 逻辑地址
段号 段长 SL 基址
0
1
2
3
段表始址 段表长度
TL
段号 S 位移量 d
2 100
﹥ =
15K 40K
7K 80K
8K 120K
10K 150K 物理地址
120k+100
4,分页和分段比较：
分 页 分 段目的 为了 提高 内存 的 利用率；
为了能更好地满足用户的需要。
页 / 段单位 划分页是 信息 的物 理 单位,页的 大小 是 固定的,而 且由 系 统确定。
段是信息的逻 辑单位,它含有一组意义 相对完整的信息。段的长度是不固定的，由用户确定。
作 业 地址空间单一 的线 性地 址 空间二维 的，标识 一个地址 需给 出段 名和段内 地址。
内存 分配以页 架为 单位 离 散分配,无 外碎 片,
所以也无紧缩问题以段为单位离散分配，类同可变分区，会产生许多分散的小自由分区――外碎片，造成主存利用率低，需采用紧缩解决碎片问题，但紧缩需化机时；
分页和分段比较 -1
分 页 分 段共 享 和存 取 访问控制在同一页面中包含 共享的程序和私用的 数据，使共享和存取 访问控制困难；
便 于 共 享 段 逻 辑 上 完 整 信 息 共 享 有 价 值,
提 高 主 存 利 用 率 ； 便 于 控 制 存 取 访 问,
段 是 逻 辑 上 完 整 信 息 可 根 据 各 段 信 息 决定存取访问权动 态 连接不能动态连接； 提 供 动 态 连 接 的 便 利,运 行 中 不 用 的 模块可以不连接调入，节省内存空间动 态 增长不能动态增长 便 于 处 理 变 化 的 数 据 结 构 段,可 动 态 增长
2001年 9月 20日 9时 23分 计算机操作系统物理存储器的结构是个一维的线性空间,容量是有限的 。
用户程序结构：
一维空间一个用户程序就是一个程序,并且程序和数据是不分离的；
二维空间 程序由主程序和若干个子程序 （ 或函数 ） 组成,并且程序与数据是分离的；
n维空间 即一个大型程序,由一个主模块和多个子模块组成,其中
,各子模块又由主程序和子程序 （ 或函数 ） 组成 。
5.6.3 共享与保护
1、可重入代码 (Reentrant Code):
又称为,纯代码,(Pure Code),在实现段共享时，需要用到可重入代码 (Reentrant Code) 。 它是一种允许多个进程同时访问的代码，
是一种不允许任何进程对其进行修改的代码。
在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区 (属于该进程私有 )中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。
2、例
EDITOR
PC
160KB的可重入代码
40KB的数据区设同时有 40个用户并发执行并使用该 EDITOR,40*（ 160+40）
=8MB空间支持。如果代码可重入，内存只保留 1份 COPY即可，
40*40+160=1760KB。
2001年 9月 20日 9时 23分 计算机操作系统共享与保护 -1
段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。分段系统中，每个进程的段表中设置一个段表项。图是分段系统中共享 editor编辑程序的示意图。 P161/P162图 5-24/5-25。
共享与保护 -2
进程 1 段 表
80
240
280
进程 2
380
420
段长 基址
160 80
40 240
editor
DATA1
editor
DATA2
段长 基址
160 80
40 380
editor
DATA1
DATA2
5.6.4 段页式存储管理方式分页和分段存储管理方式都各有其优缺点 。 如果对两种存储管理方式,各取所长,后,则可以形成一种新的存储管理方式的系统 ——
段页式系统 。 这种新系统既具有分页系统能有效地提高内存利用率的优点,又具有分段系统能很好地满足用户需要的长处,显然是一种比较有效的存储管理方式 。
1,基本原理段页式系统的基本原理是先将 整个主存划分成大小相等的存储块
（ 页架 ）,把 用户程序 按程序的逻辑关系 分为若干个段,并为每个段赋予一个段名,再把每个段划分成若干页,以页架为单位离散分配 。 在段页式系统中,其地址结构由段号,段内页号和页内地址三部分组成,作业地址空间的结构如图 下 所示 。
段号 （ S） 段内页号 （ P） 页内地址 （ W）
段页式存储管理方式 -1
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，
段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程。
段表、页表的作用段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
段 表段表大小段表始址页号 状态 存储块号
0 1
1 1
2 1
3 0
4 1
页 表页号 状态 存储块号
0 1
1 1
2 1
3 0
4 1
页 表段表寄存器操作系统主存
2．地址变换过程在段页式系统中,有一个段表寄存器,存放段表始址和段长 TL。
在进行地址变换时,首先利用段号 S,将它与段长 TL进行比较 。
若 S＜ TL,表示未越界,于是利用段表始址和段号求出该段对应的段表项在段表中的位置,从中得到该段的页表始址,并利用逻辑地址中的段内页号 P来获得对应页的页表项位置,从中读出该页所在的物理块号 b,再用块号 b和页内地址构成物理地址 。
下图 说明 了段页式系统中的地址变换机构 。
在段页式系统中,为了获得一条指令或数据,需三次访问内存：
第一次访问内存中的段表,从中取得页表始址；第二次访问内存中的页表,从中取出该页所在的物理块号,并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据 。 显然,这使访问内存的次数增加了近两倍 。 为了提高执行的速度,在地址变换机构中增设一高速缓冲寄存器 。 每次访问它时,都同时利用段号和页号去检索高速缓存 。
段页式系统的地址变换机构段表寄存器 越界中断段表始址 段表长度
+
段号 （ S） 段内页号 （ P） 页内地址 （ W）﹥
+ 块 号 b 块内地址段 表
0
1
2
3
页 表
0
1
2
3
习题
1,静态重定位是在作业的﹎﹎ A﹎﹎ 中进行的,动态重定位是在作业的﹎﹎ B﹎﹎ 中进行的 。
A,B,（ 1） 编译过程； （ 2） 装入过程； （ 3） 修改过程； （ 4） 执行过程 。
2,在首次适应算法中,要求空闲分区按﹎﹎ A﹎﹎ 顺序链接成空闲分区链；在最佳适应算法中是按﹎﹎ B﹎﹎ 顺序形成空闲分区链；最坏适应算法是按﹎﹎ C﹎﹎ 顺序形成空闲分区链 。
A,B,C,（ l） 空闲区首址递增； （ 2） 空闲区首址递减； （ 3） 空闲区大小递增； （ 4） 空闲区大小递减 。
习题 -1
3,在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区表项数减 1的情况是﹎﹎ A﹎﹎,造成空闲区表项数增 1的情况是﹎﹎ B﹎
﹎,造成空闲区表项数不变、某项的始址改变、长度增加的情况是
﹎﹎ C﹎﹎,造成空闲区表项数不变、某项的始址改变、长度不变的情况是﹎﹎ D﹎﹎,造成空闲区表项数不变、某项的始址不变、
长度增加的情况是﹎﹎ E﹎﹎。
A,B,C,D,E：（ 1） 无上邻（低址）空闲区，也无下邻（高址）
空闲区；（ 2）有上邻（低址）空闲区，但无下邻（高址）空闲区；
（ 3）有下邻（高址）空闲区，但无上邻（低址）空闲区；（ 4）有上邻（低址）空闲区，也有下邻（高址）空闲区；（ 5）不可能的。
4,试述 UNIX Ⅵ 主存 管理的 数据结构和分配,回收原理。
5,详述在设有快表的分页存储管理系统中，一个虚地址转换成物理内存地址的过程。
习题 -2
6.某系统采用页式存储器管理,页长为 1K(1024)字,某作业的地址空间如图所示,主存大小为 10K,其中 0块和 1块为操作系统占用,该作业分页后分别装入到主存的 2,4,8块中去,当前正在运行该作业 。
(1)请填写页表项,页 号 块 号
0 ﹎﹎ A﹎﹎
1 ﹎﹎ B﹎﹎
2 ﹎﹎ C﹎﹎
(2)作业装入主存时,逻辑地址 400,1129,2468所给指令,数据所在的存储单元地址分别为 (400-D)+E,(1129-F)+G和 (2468-H)+I； 其中﹎﹎ D﹎﹎,﹎﹎ F﹎﹎ 和﹎﹎ H﹎﹎ 分别为三指令,数据所在页的页首地址；﹎﹎ E﹎﹎,﹎﹎ G﹎﹎ 和﹎﹎ I﹎﹎ 分别为三指令,
数据所在存储块的块首地址 。
(3)试分析执行 JMP 3080后的情况为﹎﹎ J﹎﹎ 。
习题 -3
逻辑地址 作业的地址空间 存储单元地址
0 ┌───────┐
400│ MOV R0,2468 │(400 -D)+E
,│ │
1129│JMP 3080 │(1129 -F)+G
,│ │
2468│ 12468 │(2468 -H)+I
,│ │
3060└───────┘
A,B,C,(1)1 (2)2 (3)3 (4)4 (5)5 (6)6 (7)7 (8)8
(9)9 (10)0
D— I,(1)0 (2)1024 (3)2048 (4)3072 (5)4096 (6)5120
(7)6144 (8)7168 (9)8192 (10)9216
J,(1)跳到地址 3080的指令执行； (2)产生越界中断； (3)以上二者都不是；
习题 -4
7,考虑一个分页系统,其页表存放在内存,
① 如果内存读写周期为 1.0us,则 CPU从内存取一条指令或一个操作数需时间为﹎﹎ A﹎﹎ 。
② 如果设立一个可存放 8个页表表项的快表,80%的地址变换可通过快表完成,内存平均存取周期为﹎﹎ B﹎﹎ (假设快表的访问时间可以忽略不计 )。
A,B,(1)1.0μ s (2)1.1μ s (3)1.2μ s (4)1.3μ s (5)1.6μ s
(6)2.0μ s (7)3.0μ s
8,由固定分区方式发展为分页存储管理方式的主要推动力是﹎﹎ A﹎
﹎； 由分页系统发展为分段系统,进而又发展为段页式系统的主要动力分别是﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎ 。
A,B,C,（ l） 提高内存利用率； （ 2） 提高系统吞吐量； （ 3） 满足用户需要； （ 4） 更好地满足多道程序运行的需要 。 （ 5） 既满足用户需要,又提高内存利用率 。
9.段式存贮管理与页式存贮管理有什么异同?
教学 目的,
存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充大主存，对主存信息实现有效保护是存储器管理主要任务，
也是各种不同存储管理方法的目标。“瓶颈”问题。
教学要求：
熟悉 存储管理目的和 功能，掌握地址重定位的概念。
熟悉 单一连续分配,固定分区分配,动态分区分配 实现 原理；
掌握 可变式分区分配的 数据结构和 分配 回收算法,掌握 动态重定位分区分配 实现 原理和分配 算法。
熟悉 覆盖与交换 的概念。
熟练掌握 分页存储管理 原理,熟练掌握 基本的地址变换机构和具有快表的地址变换机构,了解两级页表机制 。
掌握 分段存储管理 原理和 分段地址变换机构,掌握分页和分段比较，熟 悉 分页和分段的共享，掌握 段页 式 存储管理 原理和 地址变换机构。
5.1 存储管理概述存储管理目的和 功能：
1。 主存储器 （ 内存 ） 的分配和回收内存分配的主要任务是为每一道程序分配内存空间,使它们
,各得其所,。 使程序员无须关心存储分配问题,由 OS完成 。
2。 存储保护内存保护的任务是确保每道程序都在自己的内存空间运行,
互不干扰 。 程序与 OS也互不干扰 。
3。 地址映射,一个应用程序经编译后 ----若干个目标程序 — 链接形成可装入程序 。 逻辑地址 ----物理地址 。
4。 内存 扩充内存 扩充的任务是从逻辑上来扩充内存容量,使用户认为系统所拥有的内存空间远比其实际的内存空间 （ 硬件 RAM） 大的多 。
请求调入和置换功能 。
提高主存储器的利用率,减少不可用的存储空间 （ 称为,零头 ）,允许 多道程序 动态共享主存 。
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接一个用户源程序变为一个可在内存中执行的程序要做：
1）编译 用户源代码 —>几个目标模块 /程序。
2）链接 由链接程序把目标模块 +它们所需库函数 —>可装入模块。
3）装入 由装入程序把装入模块 —>内存。
例：一个 PASCAL源程序。
5.2.1 程序的装入装入模块内存
OS
用户区
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接例：一个可执行程序 ball.exe/play.exe,直接输入 ball/play即可，
装入程序?内存运行（涉及到内存分配问题）。
一次装入?静态分配问题（一次性地把进程所需资源分配给它）。
部分装入?动态分配问题绝对装入可重定位装入运行时装入一、绝对装入方式（适应于单用户系统）汇编 8088中启动各个段。
由编程人员指定位置装入内存 /或编译程序对源程序编译时，所用的是实际存储地址。若是多用户，必须默契，实际工作中不可能。所以多用户系统不采用该方式。
2001年 9月 20日 9时 23分 计算机操作系统
5.2程序的装入和链接二、可重定位装入在装入时才确定对进程 /作业的内存分配，需采用下述两个技术手段：
1）把逻辑地址与物理地址分开；
2）对逻辑地址采用地址重定位；
两个概念：地址空间和存储空间。
1,地址空间在源程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合称为,名字空间,。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以,0”作为参考地址的模块。然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行。我们把目标模块中的地址称为相对地址（或称为“逻辑地址”），而把相对地址的集合称为“相对地址空间”或简称为,地址空间,。
2、存储空间 主存中一系列存储信息的物理单元的集合。这些单元的编号成为物理地址或绝对地址。
5.2程序的装入和链接
3,什么是 地址重定位？
装配模块虽然具有统一的地址空间,但是仍是以,0” 作为参考地址,即是浮动的 。 要把它装入内存执行,就要确定装入内存的实际物理地址,并修改程序中与地址有关的代码,这一过程称为 地址重定位 。 即从逻辑地址?物理地址相对地址?绝对地址程序的名字空间,地址空间和存储空间之间的关系如图所示：
汇编 /编译 地址重定位连 接 装 入名字空间 地址空间 存储空间
（ 相对地址 /逻辑地址空间 ） （ 绝对地址 /物理地址空间 ）
符 号源 程 序 相对目标程序 （ 装配模块 ）
绝对目标程序
4、地址重定位类型地址重定位完成把相对地址转换成内存中的绝对地址，这个过程称为地址映射
（ map）。 按照重定位的时机，可分为静态重定位和动态重定位。
1）静态重定位静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的 。
在一些早期的系统中都有一个装入程序 （ 加载程序 ）,它负责将用户程序装入系统,并将用户程序中使用的访问内存的逻辑地址转换成物理地址 。 如图所示 。
地址重定位 -2
0,10000：
100 LOAD 1,2500 10100,LOAD 1,12500
2500,365 12500,365
2600,12600：
程序的地址空间 内存的地址空间例如,LOAD 1,2500 这条指令是把相对地址为 2500的存储单元的内容 365装入 1号累加器 。 而这时内容为 365的存储单元的实际物理地址为 12500（ 起始地址 10000+相对地址 2500）,所以
LOAD 1,2500 这条指令中的直接地址码要作相应的修改,即改为 LOAD 1,12500。
地址重定位 -3
在程序中需要修改的位置称为重定位项。程序装入内存中的起始地址称为重定位因子。为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表。所以操作系统的装入程序要把装入模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，加上重定位因子得到欲修改位置的实际地址，最后对实际地址中的内容再加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。
静态重定位虽然有无须硬件支持的优点，但是也存在明显的缺点：一是程序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。
2001年 9月 20日 9时 23分 计算机操作系统
2） 动态重定位动态地址映射动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的 。
系统中设置了重定位寄存器 。
地址重定位 -3
地址重定位 -4
动态重定位动态重定位是指在程序执行过程中进行地址重定位,即在每次访问内存单元前才进行地址变换 。 动态重定位可使装配模块不加任何修改就装入内存,但是它需要硬件 — 重定位寄存器的支持 。
下图给出了 动态重定位的示意图 。
程序的目标模块在装入内存时,与地址有关的指令都无须进行修改,如在图 中 LOAD 1,2500这条指令中仍保持相对地址 2500。 当该模块被操作系统调度到处理机上执行时,操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址 （ 图 中该模块的基地址为 0）,然后将其差值装入重定位寄存器 。 当 CPU取一条访问内存的指令时,地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加,再根据和值作为内存的绝对地址去访问该单元的数据 。
1000
动态重定位的示意图重定位寄存器
10000
0,10000：
100,LOAD 1,2500 10100,LOAD 1,2500
+
2500,365 12500,365
2600,12600：
程序的地址空间 内存的地址空间地址重定位 -5
由此可见，动态重定位是在指令执行过程中动态进行，这样可以带来两个好处：
⑴目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。⑵一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。
三、动态运行时装入方式内存较小时，实际运行时换入换出，且使用的内存区域大小也可改变。
不是一次性装入，而是多次装入。
装入模块内存
OS
用户区
5.2.2 程序的链接用户程序的上机过程：
1）编译 用户源代码 —>几个目标模块 /程序。
2）链接 由链接程序把目标模块 +它们所需库函数 —>可装入模块。
3）执行 由装入程序把装入模块 —>内存 —> 执行。
一,静态链接：一次性地把若干目标模块链接成一个装入模块,以后不再拆开 。
P136图 5-4。
需解决的问题：
1,对相对地址的修改 。
编译把用户源代码 —>几个目标模块,其起始地址都为 0,每个模块中的地址都是相对于这个 0地址的 。
2,变换外部调用符号 。
把每个模块中的外部调用符号?相对地址 。
二,装入时动态链接：边装入内存边链接 。 在装入一个目标模块时,若发生一个外部模块调用,将引起装入程序去找出相应的外部模块,并将它装入内存；同时也要修改目标模块中的相对地址 。
优点,1,可单独修改各个目标模块,易修改,而静态链接不可能修改 。
2,装入时动态链接易于实现共享 。 而静态链接必须 COPY。
5.2.2 程序的链接三,运行时动态链接装入时动态链接,但一旦装入,模块就无法改变,而且每次执行时的装入模块都相同 。 实际上,每次运行时装入模块不完全相同,
例 ERROR处理模块 --->执行时链接的方式 。 这样做,有一些模块不用事先装入内存,可节省存储空间 。
5.3 各种存储管理方案
5.3.1单一用户（连续区）存储管理单用户在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供 OS使用，一个供用户使用。这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在 8位和 16
位微机上 CP/M和 MS-DOS操作系统。它将内存分为两个区：
系统区：仅供操作系统使用，通常设置在内存的低段；
用户区：指除系统区以外的全部内存空间，提供给用户使用。
这种存储分配方式由于用在单用户、单任务的操作系统中。 地址映射和 存储保护措施 如下图 。
内存 OS
用户
OS
用户
OS
…
用户
OS
界限寄存器 重定位寄存器 (基址 )
+CPU <
内存地址错逻辑地址 Y
N 物理地址
5.3 各种存储管理方案
2001年 9月 20日 9时 23分 计算机操作系统基址,限长寄存器保护法用的是程序的逻辑地址 。
在这种存储管理技术中,系现设置一个专用寄存器,称为基地址寄存器,当一个进程 （ 或程序,作业 ） 被调度运行时,系统首先从 PCB中取出该进程的首地址装入基地址寄存器中,在该进程运行的过程中实现动态地址映射 。
5.3 各种存储管理方案
60K 非法区用户非法区64K
基址寄存器限长寄存器
60K
124K
5.3.2 固定分区 (Fixed Partitioning)分配
1、概念固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。
例：开机，由引导程序把 OS?内存,OS接管整个机子（软 /硬件资源），内存分区由 OS事先指定好，每个分区个数、长度已固定，再为每个用户分配相应分区。
主要适用于多道程序，几个分区 几个作业。
2、划分分区方法
1）大小相等。
2）大小不等。 P140图 5-6。
3、内存分配及管理。
系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和 内存分配图 如下所示。
0k：
20k：
第 1分区 （ 16kb）
36k：
第 2分区 （ 32kb）
（ 已分配 ）
68k：
第 3分区 （ 64kb）
（ 已分配 ）
132k：
第 4分区 （ 124kb）
（ 未分配 ）
256k：
（ b） 内存分配图区号 大小 起址 标志
1 16KB 20K 已分配
2 32KB 36K 已分配
3 64KB 68K 已分配
4 124KB 132K 未分配
(a) 分区说明表固定式分区实现技术简单
，但是内存的利用率不高，
适用于作业的大小和多少事先都比较清楚的系统中。它用于 60年代的 IBM-360的 MFT
操作系统中。例：有一 10K的作业到，如何分配？ 60K的作业到，如何分配？
内零头操作系统作业 A（ 16k）
作业 B（ 26k）
作业 C（ 56k）
5.3.2 固定分区 (Fixed Partitioning)分配
5.3.3动态 /可变式 (Dynamic Partitioning)分区分配
1,概念：
可变式分区是指在作业装入内存时,从可用的内存中划出一块连续的区域分配给它,且分区大小正好等于该作业的大小 。 可变式分区中分区的大小和分区的个数都是可变的,而且是根据作业的大小和多少动态地划分,因此又称为动态式分区 。 这种存储管理技术是固定式分区的改进,既可以获得较大的灵活性,又能提高内存的利用率 。
2,可变式分区的分配和释放的基本思想是：
在分配时,首先找到一个足够大的空闲分区,即这个空闲区的大小比作业要求的要大,系统则将这个空闲分区分成两部分：一部分成为已分配的分区,剩余的部分仍作为空闲区 。 在回收撤除作业所占领的分区时,要检查回收的分区是否与前后空闲的分区相领接,若是,则加以合并,使之成为一个连续的大空间 。
Example Dynamic
Partitioning
Operating
System
Process 1 320 K
Process 2
Process 3
224 K
288 K
64 K
Operating
System
Process 1 320 K
Process 3
224 K
288 K
64 K
Operating
System
Process 1 320 K
Process 3 288 K
64 K
Process 4 128 K
96 K
Example Dynamic
Partitioning
Operating
System
320 K
Process 3 288 K
64 K
Process 4 128 K
96 K
Operating
System
Process 3 288 K
64 K
Process 4 128 K
96 K
Process 2 224 k
96 K
动态 /可变式分区分配 -1
3。可变式分区数据结构
空闲区表形式空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。
空闲区链形式为了实现对空闲分区的分配和链接，在每个分区的起始部分，
设置一些用于控制分区分配的信息（如分区的大小和状态位），
以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。
P141图 5-7/5-8。
0k：
20k：
52k：
116k：
164k：
260k：
512k：
（ c） 内存分配图可变式分区数据结构图表序号 P大小 起址 状态
1 48k 116k 空闲
2 252k 260k 空闲
3 — — 空表目
4 — — 空表目
5 — — 空表目
（ a） 空闲分区表操作系统作业 1（ 32k）
作业 2（ 64k）
空闲区 （ 48k）
作业 4（ 96k）
空闲区 （ 252k）
前向指针N+
2
0
0 后向指针N+
2
0
0
N个字节可用
（ b ）空闲链结构
4 分区分配 算法 (Partitioning Placement Algorithm)
1） 最佳适应算法 （ Best Fit）,它从全部空闲区中找出能满足作业要求的,且大小最小的空闲分区,这种方法能使碎片尽量小 。 为适应这种算法,空闲分区表
（ 空闲区链 ） 中的空闲分区要 按大小 从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配 。 看似最佳,实则未必 。 因为这样做导致小的空闲区越来越多 。
2） 首次适应算法 （ First Fit）,从 空闲分区表 的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法目的在于减少查找时间 。 为适应这种算法,空闲分区表 （ 空闲区链 ） 中的空闲分区要按地址由低到高进行排序 。
3） 循环首次适应算法,该算法是首次适应算法的变种 。 在分配内存空间时,不再每次从表头 （ 链首 ） 开始查找,而是从上次找到的空闲区的下一个空闲区开始查找,直到找到第一个能满足要求的的空闲区为止,并从中划出一块与请求大小相等的内存空间分配给作业 。 该算法能使内存中的空闲区分布得比较均匀 。
4） 最坏适应算法,从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业； 空闲 分区按大小由大到小排序 。
外零头,经过一段时间的分配与回收后,内存中存在很多很小的空闲块 。 每一个都很小,不足以满足分配要求 。 这些空闲块称为外零头 。
Dynamic Partitioning
Placement Algorithm
Last
allocated
block (14K)
Before After
8K 8K
12K 12K
22K
18K
6K 6K
8K 8K
14K 14K
6K
2K
36K 20K
Next Fit
Free block
Allocated block
Best Fit
First Fit
例,分配一个 16KB分区
5 UNIX分配 回收算法（采用 空闲分区表 结构和 首次适应算法）
UNIX空闲分区表 数据结构
Coremap
m_addr
m_size
…,.
m_addr
m_size=0
…,..
m_addr
m_size
m_addr
m_size
m_addr
m_size
m_addr
m_size
空闲分区表中的空闲分区要 按 地址从低到高连续排序，最后一个空闲分区中
m_size为 0表示以上表目空白。空闲分区表起始地址为 coremap
分配和释放的基本思想是：在分配时，
首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，
使之成为一个连续的大空间。
UNIX 分配 算法框图申请分配一个 u.size大小的分区从头开始查表是否检索完毕？ 本次无法分配
m.size>u.size
m.size-u.size≤size？
从 该 分 区 中 划 出
u.size大小的分区继续检索下一个表项将该表目以上的所有表目下移一格将该分区分配给申请者修改有关的数据结构返 回
Y
N
N
UNIX 回收算法当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如下图 所示，其中 F1,F2表示回收区的前、后空闲区）,
当回收区既不与 F1领接，又不与 F2领接时（如 A）,应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。
当回收区只与插入点的前一个分区 F1相领接时（如 B）,应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改 F1分区表目的大小 m_size即可。
当回收区只与插入点的后一个分区 F2相领接时（如 C）,将把两个空闲区合并，修改 F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。
UNIX 回收算法
当回收区与插入点的前,后两个分区 （ F1和 F2） 都相领接时 （ 如
D）,合并三个分区,用 F1表目的起址作为新空闲区的起址,修改其大小为三块分区之和,最后取消 F2的表目 。
A B C D F1
回收区
F2
回收区
F2
回收区
F1
回收区
UNIX 回收算法框图是否否是是 否将该表目以上的所有表目上移一格,并插入新释放的可用区表目顺序地检索可用资源表直至找到某表目的
m.addr>aa或 m.size=0
不是第一个表目与前一可用区相邻？与后一可用分区相邻且不为空表目？
把所释放的可用区与前一分区合并所释放的可用区与一可用区合并所释放可用区的 size=0
与后一可用区 相邻
？
与后一可用区合并将该表目以上的所有表目下移一格返 回
mfree
是否
5.3.4 动态重定位分区分配
1。 拼接 /紧凑可变式分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，
另一方面系统在拼接时要耗费较多的时间。
2.动态重定位实现紧凑所需的允许作业在运行过程中在内存中移动的技术必须获得硬件支持。只有具有动态重定位硬件机构的计算机系统，才有可能采取动态重定位可变分区多道管理技术，系统的硬件包括重定位寄存器和加法器。
动态重定位分区分配
3,动态重定位分区分配算法动态重定位分区管理中何时进行存储器紧缩有二种不同的解决办法：
在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，
此法很花费机时。
当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但表格管理复杂。采用此法的动态重定位分区分配算法框图如下：
动态重定位分区分配 算法框图
N N
Y Y
请求分配
u.size分区检索空闲分区链 （ 表 ）
无法分配返回空闲分区总和
≥ u.size
找到大于
u.size的可用区否？
进行紧凑形成连续空闲区修改有关的数据结构按动态分区方式进行分配修改有关的数据结构返回分区号及首址
5.4 覆盖与交换
(1)覆盖技术
1,覆盖的概念为了能在小的内存空间中运行大的作业，许多机器（如 PDP－
11,IBM－ PC） 都采用了“覆盖”技术。覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间。
覆盖技术通常与单用户连续分配、固定分区和可变分区等存储管理技术配合使用。它不但用于用户作业的运行中，而且还常用于操作系统本身的运行中。
覆盖技术覆盖技术的基本概念可用下图来加以说明，一个作业由一个主程序段 MAIN主若干程序／数据段组成，其调用关系如 a所示，我们把树形关系中常驻内存的段 ―― 主程序段 MAIN叫根段，其余覆盖部分分成层次,A0与 B0为一层，组成一个覆盖段 0，同理 A1,A2与 B1组成覆盖段 1，在 A3和 A4组成覆盖段 2，同一时间内同一覆盖段的各程序段（称为覆盖），只有一个覆盖在执行可被引用，它不能调用同层中的其它覆盖。
如不采用覆盖技术，该作业要求 270K主存，采用覆盖技术后只要求 160K主存。
覆盖技术
（ a） (b)
MAIN
20K
A0
30K
B0
40K
A1
60K
A2
30K
B1
30K
A3
20K
A4
40K
覆盖段 0
40K
覆盖段 1
60K
覆盖段 2
40K
MAIN
A0
A1 A2
A3 A4
B1
B0
2.覆盖处理
覆盖结构的输入
PDP－ 11的 RSX－ 22H提供覆盖描述语言 ODL来描述结构，并构成覆盖描述文件，如上图用 ODL语言表示如下：
ROOT MAIN－（ A0－（ A1,A2－（ A3,A4））,B0－（ B1，
B2））；
END
覆盖数据结构用户将覆盖描述文件随目标程序一起提交系统，系统根据覆盖描述文件形成一个覆盖数据结构。该数据结构对每个覆盖段有一个描述信息，它包括覆盖段号、覆盖数、当前覆盖号、覆盖区始址、覆盖区长度、起始盘区号等。系统根据覆盖调度程序和覆盖调度结构自动地将各程序段装入运行。
（ 2）交换（对换）技术交换技术最早用在麻省理工学院的兼容分时系统 CTSS中，该系统是单用户系统，所有用户都驻留在外存的后备队列中，每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。这是早期的简单分时系统，它采用早期的交换（调进／凋出）
来满足多个程序共享主存的需要。
1。多道程序环境下的对换在多道程序环境下为了提高内存和 CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。
UNIX早期已引入对换功能并一直保留至今,UNIX系统设置一个对换进程完成以上功能。为了实现进程对换，系统必须能实现对对换空间的管理，进程换入和进程换出等三项功能。
交换（对换）技术
2。对换空间的管理外存分为文件区和对换区。文件区用户存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分散方式；
对换区用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。
UNIX对换区采用空闲分区表和首次适应算法的动态分区管理，
类同早期内存管理。
3。进程的换出与换入当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞和睡眠状态的进程换出，如无则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。而当内存又空时对换进程在对换区中选择换出时间长的处于就绪态的进程调入。
5.5 分页存储管理的基本方法问题的提出：
分区存储管理的主要问题是碎片问题。
在采用分区存储管理的系统中，会形成一些非常小的分区，
最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。
造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。
5.5 分页存储管理的基本方法
5.5.1 纯分页存储管理原理
1,分页分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域,称为页 /页面,相应地,将内存空间划分成与页相同大小的若干个物理块,称为块或页框 /物理块 。 在为进程分配内存时,以页面为单位进行分配 。 将进程中的若干页分别装入多个不相邻接的块中 。
进程 1
进程 2
进程 3
进程 1
进程 1
进程 2
进程 2
进程 3
进程 2
纯分页存储管理原理 -1
2。 地址结构分页系统的地址结构如下图 所示,它由两部分组成：前一部分为页号 P； 后一部分为位移量 W,即页内地址 。 图中的地址长度为 32位,其中 0～ 11位为页内地址 （ 每页的大小为 4K）,12～ 31位为页号,所以允许地址空间的大小最多为 1M个页 。
31 12 11 0
3。页表在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图 所示 ）。每个页在页表中占一个表项，
记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
页号 P 位移量 W
纯分页存储管理原理 -2
页表是页式存储管理的数据结构,它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。
页号 内存块号 存取控制 状态 其它
0
1
2
3
0
1
2
3
4
5
6
7
用户程序 页 表 内 存页号 块号
0 2
1 4
2 5
3 7
5.5.2 地址变换机构页表可以完成从逻辑地址 — 物理地址的映射；
地址空间 — 存储空间的映射。 如何完成？
地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。
1。基本的地址变换机构
1）几点说明
（ 1）进程访问某个逻辑地址时，地址变换机构自动地把有效地址 /相对地址分为 2部分?页号与页内地址；
（ 2） 页内地址（ 0~1023）与块内地址 /页框内地址（ 0~1023）一一对应，无须转换。
（ 3）页表通常存放于内存中，必须有一个存放页表的起始地址。
在系统中设置页表寄存器，用来存放页表在内存的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的 PCB中，当该进程被调度时，就将它们装入页表寄存器。
（ 4）将物理地址?物理地址寄存器中 块号块内地址
5.5.2 地址变换机构
2）实现过程首先由进程访问的逻辑地址 页内地址页号?与页表寄存器中的页表长度比较?ERROR中断页号 *页表项长度 +页表在内存的始址（页表寄存器中）
计算出该页在页表项中的位置查页表，得该页物理块号块内地址物理块号 装入物理地址寄存器中未越界越界地址变换机构 -1
越界中断页表寄存器 逻辑地址 2500
页号 块 号
0
1
2
每页 1KB(1024) 物理地址 5572
5*1024+452
块号 5 块内地址 452
页 号 2 页内地址 452页表始址页表长度 ﹥
=
2
4
5
2。具有快表的地址变换机构
如果页表存放在内存中,则每次访问内存时,CPU存取一个数据必须访问两次内存 第 1次,访问内存中的页表?物理地址
第 2次再访问内存,去存取物理地址中的数据
从而使计算机的处理速度降低了 1/2。
为了提高地址变换的速度,在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器,称为,联想存储器,或
,快表,。
快表内容,用以存放当前访问的那些页表项 。
此时地址变换过程为：在 CPU给出有效地址后,地址变换机构自动地将页号送入高速缓存,确定所需要的页是否在快表中 。 若是,
则直接读出该页所对应的物理块号,送入物理地址寄存器；若在快表中未找到对应的页表项,则需再访问内存中的页表,找到后,
把从页表中读出的页表项存入快表中的一个寄存器单元中,以取代一个旧的页表项 。
具有快表的地址变换机构 -1
由于成本的原因，快表不可能做得很大，通常只能存放 16~512个页表项。例如，在 Intel80486中有 32个。这对中、小型作业来说，
已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。
由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到 80%～ 90%。例如，假设检索联想存储器的时间为 20ns，
访问内存的时间为 100ns,访问联想存储器的的命中率为 85%，则
CPU存取一个数据的平均时间为 T=0.85*120+0.15*220=135ns，
所以访问时间只增加 35%。如果不引入联想存储器，其访问将延长一倍（达 200ns）。
具有快表的地址变换机构 -2
越界中断页表寄存器 逻辑地址页号 块号页 号 块 号 0 2
0 1 4
1 2 5
2
快 表页 表 物理地址页 号 页内地址页表始址 页表长度 ﹥
2
4
5
块号 块内地址输入寄存器
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算虚地址结构 (程序字 )
虚地址是用户程序中的逻辑地址 /相对地址 /有效地址,它包括页号和页内地址 （ 页内位移 ） 。
区分页号和页内地址的依椐是页的大小,页内地址占虚地址的低位部分,页号占虚地址的高位部分 。
假定页面大小 1024字节,虚地址共占用 2个字节 (16位 )
页号 页内地址 （ 位移量 ）
P W
15 10 9 0
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---虚地址结构
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
1,虚地址 （ 逻辑地址,程序地址 ） 以十六进制,八进制,二进制的形式给出
将虚地址转换成二进制的数；
按页的大小分离出页号和位移量 （ 低位部分是位移量,高位部分是页号 ） ；
根据题意产生页表 ；
将位移量直接复制到内存地址寄存器的低位部分；
以页号查页表,得到对应页装入内存的块号,并将块号转换成二进制数填入地址寄存器的高位部分,从而形成内存地址 。
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
2.虚地址以十进制数给出
页号＝虚地址 DIV 页大小
位移量＝虚地址 mod 页大小
根据题意产生页表；
以页号查页表,得到对应页装入内存的块号
内存地址＝块号 × 页大小＋位移量
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
例 1：有一系统采用页式存储管理,有一作业大小是 8KB,页大小为 2KB,依次装入内存的第 7,9,A、
5块,试将虚地址 0AFEH,1ADDH转换成内存地址 。
虚地址 0AFEH
0000 1010 1111 1110
P＝ 1 W＝ 010 1111 1110
MR＝ 0100 1010 1111 1110
＝ 4AFEH
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
虚地址 1ADDH
0001 1010 1101 1101
P＝ 3
W＝ 010 1101 1101
MR＝ 0010 1010 1101 1101＝
2ADDH
2001年 9月 20日 9时 23分 计算机操作系统关于分页的地址变换计算 ---页式地址映射
虚地址 3412
P＝ 3412 ％ 2048 ＝ 1
W＝ 3412 mod 2048
＝ 1364
MR=9*2048+1364=19796
虚地址 3412的内存地址
是,19796
例 2：有一系统采用页式存储管理，有一作业大小是 8KB,页大小为 2KB,依次装入内存的第 7,9,10,5块，试将虚地址 7145,3412转换成内存地址。
2001年 9月 20日 9时 23分 计算机操作系统
虚地址 7145
P＝ 7145 ％ 2048 ＝ 3
W＝ 7145 mod 2048
＝ 1001
MR=5*2048+1001=11241
虚地址 7145的内存地址是：
11241
关于分页的地址变换计算 ---页式地址映射
5.5.3 两级页表机制
80386的逻辑地址有 232B,如 页面大小为 4KB（ 212B）,则页表项达
1M个，每个页表项占用 4B,故每个进程的页表占用 4MB内存空间，
还要求是连续的，显然这是不现实的。
在 80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制：基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表，其中的每个表目所存放的才是页的物理块号。
两级页表机制
两级页表系统将 32位逻辑地址空间的地址分成三段：其中,页表目录号 （ 外层页号 p1） 和页号 （ 外层页内地址 p2） 两项各占 10位,偏移量 （ 页内地址 d） 占 12位 。 每页的大小为 4KB。 由于物理块号和页表的物理地址都占 4个字节,使每页中包含 1024个页表项,所以页表目录和页表的大小也都是 4KB,即一页 。 在 80386中设置了一个外层页表寄存器 （ CR3）,用于存放页表目录的基址 。 两级页表的逻辑地址结构和 两级页表的 地址变换机构图如下：
31 22 21 12 11 0
外层页表 页表 物理地址 返回外层页号 p1 外层页内地址 p2 页内地址 d
外层页表寄存器 + + b d
两级页表机制图第 0页页表 （ 物理块号 10） 内 存
0
1
0 ┇
1 1023
2 第 1页页表 （ 物理块号 25）
0
1
┇
1023
第 N页页表 （ 物理块号 120）
0
1
外层页 表 ┇
1023
10
25
120
12
14
32
35
151
152
0
1
……
12
13
14
……
32
33
34
35
……
151
152
……
5.6 分段存储管理
5.6.1 分段存储管理方式的引入分页从根本上克服了外零头（地址空间、物理空间都分割）。
内存利用率缺点：无论信息内容如何，按页长分割，分割后 ---内存，有可能主程序未能全部进入内存,-----执行速度降低。所以考虑以逻辑单位?内存如
PL
最后一个单元可能未占满，还有内零头，
平均浪费 PL/2大小的空间主程序函数数组工作区进程 主程序函数数组工作区分段存储管理方式的引入分页从根本上克服了外零头（地址空间、物理空间都分割）。
内存利用率缺点：无论信息内容如何，按页长分割，分割后 内存，有可能主程序未能全部进入内存,执行速度降低。所以考虑以逻辑单位 内存如分段存储管理方式的引入 -1
1。 便于编程通常用户常常把自己的作业按照逻辑关系划分成若干个段,每个段都有自己的名字,且都从零开始编址,这样,用户程序再执行中可用段名和段内地址进行访问 。
例如,LOAD 1,[A] | <D> 这条指令的含义是将分段 A中的 D单元内的值读入寄存器 1。
2。 分段共享在实现程序和数据的共享时,常常以信息的逻辑单位为基础,而分页系统中的每一页只是存放信息的物理单位,其本身没有完整的意义,因而不便于实现信息的共享,而段却是信息的逻辑单位,有利于信息的共享 。
3。分段保护 信息保护是对相对完整意义的逻辑单位（段）进行保护。
4。动态链接通常一个源程序经过编译后所形成的若干个目标程序，还需再经过链接，形成可执行代码后才能运行，这种在装入时进行的链接称为 静态链接 。 动态链接 是指在作业运行之前，并不把几个目标程序段都链接起来，而是先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段（目标程序）
调入内存并链接起来。所以，动态链接是以段为基础的。
5。动态增长在实际系统中，往往有些数据段会不断地增长，而事先却无法知道数据段会增长到多大，分段存储管理方式可以较好地解决这个问题。
5.5.2 分段系统的基本原理一,分段的基本思想：
在分段存储管理方式中,作业的地址空间按逻辑关系被划分为若干个段,每个段定义了一组完整的逻辑信息 （ 如有主程序段,子程序段,数据段及堆栈段等 ）,
每个段都有自己的段名,且有一个段号 。 段都是从 0开始编址的一段连续的地址空间,各段长度是不等的,由逻辑信息长度决定 。 对应的内存划分也是以段为单位划分,每一个段在内存中占据连续空间 （ 内存随机分割,需要多少分配多少 ）,但各段之间可以不连续 。
二,概念
1,地址结构分段系统的地址结构如下图 所示,逻辑地址由段号 （ 名 ） 和段内地址两部分组成 。
在该地址结构中,允许一个作业最多有 64 K个段,每个段的最大长度为 64 KB。
31 16 15 0
段 号 段 内 地 址分段系统的基本原理 -1
2．段表在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。在系统中为每个进程建立一张段映射表，简称为,段表,。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为,基址,）
和段的长度，如下图所示。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。
内存空间
0
40k：
80k：
120k：
150k：
分段系统的基本原理 -2段表的作用图作业空间
MAIN） =0
0 段 表
15K 段号 段长 基址
（ X） =1 0
0 1
7K
（ D） =2 2
0
8K 3
（ S） =3
0
10K
15K 40K
7K 80K
8K 120K
10K 150K
（ MAIN）
=0 15K
（ X） =1
7K
（ D） =2
8K
（ S） =3
10K
0
15k
地址变换机构 -1
三 地址变换机构
1、段表寄存器：为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。
2、过程：
在进行地址变换时，系统将逻辑地址中的段号 S与段表长度 TL进行比较。若 S≥TL,表示段号太大，访问越界，于是产生越界中断信号；
若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址 d是否超过该段的段长 SL。 若超过，即 d≥SL,同样发出越界中断信号；若未越界，则将该段的基址与段内地址 d相加，得要访问的内存物理地址。
5.5.2 地址变换机构
2 实现过程首先由逻辑地址 段内地址 d
段号?与段表寄存器中的段表长度比较?ERROR中断段号 *段表项长度 +段表在内存的始址（段表寄存器中）
计算出该段在段表项中的位置段内地址 d与段表中的段长 SL比较 d>=SL越界段内地址 d+段表中的该段的起始地址物理地址未越界越界
3 地址变换机构段表寄存器 越界中断 逻辑地址
段号 段长 SL 基址
0
1
2
3
段表始址 段表长度
TL
段号 S 位移量 d
2 100
﹥ =
15K 40K
7K 80K
8K 120K
10K 150K 物理地址
120k+100
4,分页和分段比较：
分 页 分 段目的 为了 提高 内存 的 利用率；
为了能更好地满足用户的需要。
页 / 段单位 划分页是 信息 的物 理 单位,页的 大小 是 固定的,而 且由 系 统确定。
段是信息的逻 辑单位,它含有一组意义 相对完整的信息。段的长度是不固定的，由用户确定。
作 业 地址空间单一 的线 性地 址 空间二维 的，标识 一个地址 需给 出段 名和段内 地址。
内存 分配以页 架为 单位 离 散分配,无 外碎 片,
所以也无紧缩问题以段为单位离散分配，类同可变分区，会产生许多分散的小自由分区――外碎片，造成主存利用率低，需采用紧缩解决碎片问题，但紧缩需化机时；
分页和分段比较 -1
分 页 分 段共 享 和存 取 访问控制在同一页面中包含 共享的程序和私用的 数据，使共享和存取 访问控制困难；
便 于 共 享 段 逻 辑 上 完 整 信 息 共 享 有 价 值,
提 高 主 存 利 用 率 ； 便 于 控 制 存 取 访 问,
段 是 逻 辑 上 完 整 信 息 可 根 据 各 段 信 息 决定存取访问权动 态 连接不能动态连接； 提 供 动 态 连 接 的 便 利,运 行 中 不 用 的 模块可以不连接调入，节省内存空间动 态 增长不能动态增长 便 于 处 理 变 化 的 数 据 结 构 段,可 动 态 增长
2001年 9月 20日 9时 23分 计算机操作系统物理存储器的结构是个一维的线性空间,容量是有限的 。
用户程序结构：
一维空间一个用户程序就是一个程序,并且程序和数据是不分离的；
二维空间 程序由主程序和若干个子程序 （ 或函数 ） 组成,并且程序与数据是分离的；
n维空间 即一个大型程序,由一个主模块和多个子模块组成,其中
,各子模块又由主程序和子程序 （ 或函数 ） 组成 。
5.6.3 共享与保护
1、可重入代码 (Reentrant Code):
又称为,纯代码,(Pure Code),在实现段共享时，需要用到可重入代码 (Reentrant Code) 。 它是一种允许多个进程同时访问的代码，
是一种不允许任何进程对其进行修改的代码。
在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区 (属于该进程私有 )中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。
2、例
EDITOR
PC
160KB的可重入代码
40KB的数据区设同时有 40个用户并发执行并使用该 EDITOR,40*（ 160+40）
=8MB空间支持。如果代码可重入，内存只保留 1份 COPY即可，
40*40+160=1760KB。
2001年 9月 20日 9时 23分 计算机操作系统共享与保护 -1
段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。分段系统中，每个进程的段表中设置一个段表项。图是分段系统中共享 editor编辑程序的示意图。 P161/P162图 5-24/5-25。
共享与保护 -2
进程 1 段 表
80
240
280
进程 2
380
420
段长 基址
160 80
40 240
editor
DATA1
editor
DATA2
段长 基址
160 80
40 380
editor
DATA1
DATA2
5.6.4 段页式存储管理方式分页和分段存储管理方式都各有其优缺点 。 如果对两种存储管理方式,各取所长,后,则可以形成一种新的存储管理方式的系统 ——
段页式系统 。 这种新系统既具有分页系统能有效地提高内存利用率的优点,又具有分段系统能很好地满足用户需要的长处,显然是一种比较有效的存储管理方式 。
1,基本原理段页式系统的基本原理是先将 整个主存划分成大小相等的存储块
（ 页架 ）,把 用户程序 按程序的逻辑关系 分为若干个段,并为每个段赋予一个段名,再把每个段划分成若干页,以页架为单位离散分配 。 在段页式系统中,其地址结构由段号,段内页号和页内地址三部分组成,作业地址空间的结构如图 下 所示 。
段号 （ S） 段内页号 （ P） 页内地址 （ W）
段页式存储管理方式 -1
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，
段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程。
段表、页表的作用段号 状态 页表大小 页表始址
0 1
1 1
2 1
3 0
4 1
段 表段表大小段表始址页号 状态 存储块号
0 1
1 1
2 1
3 0
4 1
页 表页号 状态 存储块号
0 1
1 1
2 1
3 0
4 1
页 表段表寄存器操作系统主存
2．地址变换过程在段页式系统中,有一个段表寄存器,存放段表始址和段长 TL。
在进行地址变换时,首先利用段号 S,将它与段长 TL进行比较 。
若 S＜ TL,表示未越界,于是利用段表始址和段号求出该段对应的段表项在段表中的位置,从中得到该段的页表始址,并利用逻辑地址中的段内页号 P来获得对应页的页表项位置,从中读出该页所在的物理块号 b,再用块号 b和页内地址构成物理地址 。
下图 说明 了段页式系统中的地址变换机构 。
在段页式系统中,为了获得一条指令或数据,需三次访问内存：
第一次访问内存中的段表,从中取得页表始址；第二次访问内存中的页表,从中取出该页所在的物理块号,并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据 。 显然,这使访问内存的次数增加了近两倍 。 为了提高执行的速度,在地址变换机构中增设一高速缓冲寄存器 。 每次访问它时,都同时利用段号和页号去检索高速缓存 。
段页式系统的地址变换机构段表寄存器 越界中断段表始址 段表长度
+
段号 （ S） 段内页号 （ P） 页内地址 （ W）﹥
+ 块 号 b 块内地址段 表
0
1
2
3
页 表
0
1
2
3
习题
1,静态重定位是在作业的﹎﹎ A﹎﹎ 中进行的,动态重定位是在作业的﹎﹎ B﹎﹎ 中进行的 。
A,B,（ 1） 编译过程； （ 2） 装入过程； （ 3） 修改过程； （ 4） 执行过程 。
2,在首次适应算法中,要求空闲分区按﹎﹎ A﹎﹎ 顺序链接成空闲分区链；在最佳适应算法中是按﹎﹎ B﹎﹎ 顺序形成空闲分区链；最坏适应算法是按﹎﹎ C﹎﹎ 顺序形成空闲分区链 。
A,B,C,（ l） 空闲区首址递增； （ 2） 空闲区首址递减； （ 3） 空闲区大小递增； （ 4） 空闲区大小递减 。
习题 -1
3,在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区表项数减 1的情况是﹎﹎ A﹎﹎,造成空闲区表项数增 1的情况是﹎﹎ B﹎
﹎,造成空闲区表项数不变、某项的始址改变、长度增加的情况是
﹎﹎ C﹎﹎,造成空闲区表项数不变、某项的始址改变、长度不变的情况是﹎﹎ D﹎﹎,造成空闲区表项数不变、某项的始址不变、
长度增加的情况是﹎﹎ E﹎﹎。
A,B,C,D,E：（ 1） 无上邻（低址）空闲区，也无下邻（高址）
空闲区；（ 2）有上邻（低址）空闲区，但无下邻（高址）空闲区；
（ 3）有下邻（高址）空闲区，但无上邻（低址）空闲区；（ 4）有上邻（低址）空闲区，也有下邻（高址）空闲区；（ 5）不可能的。
4,试述 UNIX Ⅵ 主存 管理的 数据结构和分配,回收原理。
5,详述在设有快表的分页存储管理系统中，一个虚地址转换成物理内存地址的过程。
习题 -2
6.某系统采用页式存储器管理,页长为 1K(1024)字,某作业的地址空间如图所示,主存大小为 10K,其中 0块和 1块为操作系统占用,该作业分页后分别装入到主存的 2,4,8块中去,当前正在运行该作业 。
(1)请填写页表项,页 号 块 号
0 ﹎﹎ A﹎﹎
1 ﹎﹎ B﹎﹎
2 ﹎﹎ C﹎﹎
(2)作业装入主存时,逻辑地址 400,1129,2468所给指令,数据所在的存储单元地址分别为 (400-D)+E,(1129-F)+G和 (2468-H)+I； 其中﹎﹎ D﹎﹎,﹎﹎ F﹎﹎ 和﹎﹎ H﹎﹎ 分别为三指令,数据所在页的页首地址；﹎﹎ E﹎﹎,﹎﹎ G﹎﹎ 和﹎﹎ I﹎﹎ 分别为三指令,
数据所在存储块的块首地址 。
(3)试分析执行 JMP 3080后的情况为﹎﹎ J﹎﹎ 。
习题 -3
逻辑地址 作业的地址空间 存储单元地址
0 ┌───────┐
400│ MOV R0,2468 │(400 -D)+E
,│ │
1129│JMP 3080 │(1129 -F)+G
,│ │
2468│ 12468 │(2468 -H)+I
,│ │
3060└───────┘
A,B,C,(1)1 (2)2 (3)3 (4)4 (5)5 (6)6 (7)7 (8)8
(9)9 (10)0
D— I,(1)0 (2)1024 (3)2048 (4)3072 (5)4096 (6)5120
(7)6144 (8)7168 (9)8192 (10)9216
J,(1)跳到地址 3080的指令执行； (2)产生越界中断； (3)以上二者都不是；
习题 -4
7,考虑一个分页系统,其页表存放在内存,
① 如果内存读写周期为 1.0us,则 CPU从内存取一条指令或一个操作数需时间为﹎﹎ A﹎﹎ 。
② 如果设立一个可存放 8个页表表项的快表,80%的地址变换可通过快表完成,内存平均存取周期为﹎﹎ B﹎﹎ (假设快表的访问时间可以忽略不计 )。
A,B,(1)1.0μ s (2)1.1μ s (3)1.2μ s (4)1.3μ s (5)1.6μ s
(6)2.0μ s (7)3.0μ s
8,由固定分区方式发展为分页存储管理方式的主要推动力是﹎﹎ A﹎
﹎； 由分页系统发展为分段系统,进而又发展为段页式系统的主要动力分别是﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎ 。
A,B,C,（ l） 提高内存利用率； （ 2） 提高系统吞吐量； （ 3） 满足用户需要； （ 4） 更好地满足多道程序运行的需要 。 （ 5） 既满足用户需要,又提高内存利用率 。
9.段式存贮管理与页式存贮管理有什么异同?
