64. C
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 64. C
编译后的程序需要经过链接才能装载，而链接后形成的目标程序中的地址也就是逻辑地址。以C语言为例：C程序经过预处理 $\rightarrow$ 编译 $\rightarrow$ 汇编 $\rightarrow$ 链接产生了可执行文件，其中链接的前一步是产生可重定位的二进制目标文件。C语言采用源文件独立编译的方法，如程序main.c, file1.c, file2.c, file1.h, file2.h在链接的前一步生成了main.o, file1.o, file2.o，这些目标模块的逻辑地址都从0开始，但只是相对于该模块的逻辑地址。链接器将这三个文件、libc和其库文件链接成一个可执行文件，从而形成整个程序的完整逻辑地址空间。
例如，file1.o的逻辑地址为 $0\sim 1023$ ，main.o的逻辑地址为 $0\sim 1023$ ，假设链接时将file1.o链接在main.o之后，则链接之后file1.o对应的逻辑地址应为 $1024\sim 2047$ 。
## 65. D
多级页表不仅不会加快地址的变换速度，还会因为增加更多的查表过程，使地址变换速度减慢；也不会减少缺页中断的次数，相反，若访问过程中多级的页表都不在内存中，则会大大增加缺页的次数，并不会减少页表项所占的字节数，而多级页表能够减少页表所占的连续内存空间，即当页表太大时，将页表再分级，把每张页表控制在一页之内，减少页表所占的连续内存空间。
## 66. D
分段系统的逻辑地址 $A$ 到物理地址 $E$ 之间的地址变换过程如图3.16所示。
① 从逻辑地址 $A$ 中取出前几位为段号 $S$ ，后几位为段内偏移量 $W$ ，注意段式存储管理的题目中，逻辑地址一般以二进制数给出，而页式存储管理的题目中，逻辑地址一般以十进制数给出，读者要注意具体问题具体分析。
② 比较段号 $S$ 和段表长度 $M$ ，若 $S \geqslant M$ ，则产生越界异常，否则继续执行。
③ 在段表中查询段号对应的段表项，段号 $S$ 对应的段表项地址 $=$ 段表始址 $F +$ 段号 $S \times$ 段表项长度。取出段表项中该段的段长 $C$ ，若 $W \geqslant C$ ，则产生越界中断，否则继续执行。
④ 取出段表项中该段的基址 $b$ ，计算 $E = b + W$ ，用得到的物理地址 $E$ 去访问内存。
题目中段号为2的段长为300，小于段内地址400，因此发生越界异常，选项D正确。
## 67. B
回收始址为60K、大小为140KB的分区时，它与表中第一个分区和第四个分区合并，成为始址为20K、大小为380KB的分区，剩余3个空闲分区。在回收内存后，算法会对空闲分区链按分区大小由小到大进行排序，表中的第二个分区排第一。
## 68. B
段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的，因此在内存中仅保存一份段S的内容，选项A正确。段S对进程 $\mathrm{P_1}$ 、 $\mathrm{P_2}$ 来说，使用位置可能不同，所以在不同进程中的逻辑段号可能不同，选项B错误。段表项存放的是段的物理地址（包括段始址和段长度），对共享段S来说物理地址唯一，选项C正确。为了保证进程可以顺利使用段S，段S必须确保在没有任何进程使用它（可在段表项中设置共享进程计数）后才能被删除，选项D正确。
## 69. A
题中给出的是十六进制地址，首先将它转化为二进制地址，然后用二进制地址去匹配题中对应的地址结构。转换为二进制地址和地址结构的对应关系如下图所示。
<!-- page: 220 -->
前10位、11～20位、21～32位分别对应页目录号、页号和页内偏移。把页目录号、页号单独拿出，转换为十六进制时缺少的位数在高位补零，0000 1000 0001，0001 0000 0001分别对应081H，101H，选项A正确。
70. C
最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用的内存块，所以最佳适应算法最容易产生最多的内存碎片。
71. B
在多级页表中，页表基址寄存器存放的是顶级页表的起始物理地址，所以存放的是一级页表的起始物理地址。
72. C
进程R和S共享数据data，说明它们都映射了同一个共享内存段，于是这个段在物理内存中的位置（页框号）必然相同，但这两个段在不同进程的地址空间中的位置（页号）可以不同。因此，p1和p2不一定相等，f1和f2一定相等。
73. A
伙伴算法的一次回收过程可能要进行多次合并。例如，当回收大小为 $2^{\prime}$ 的空闲分区时，若之前已存在一个大小为 $2^{\prime}$ 的空闲分区（这两个分区称为一对伙伴），则将其与伙伴分区合并成大小为 $2^{\prime \prime 1}$ 的空闲分区；合并后，若还存在一个大小为 $2^{\prime \prime 1}$ 的空闲分区，则继续与其伙伴分区合并成大小为 $2^{\prime \prime 2}$ 的空闲分区，以此类推。综上所述，伙伴算法每次回收分区时，仅合并大小相等的空闲分区，选项A正确。
二、综合应用题
01.【解答】
采用首次适应算法时，96KB大小的作业进入4号空闲分区，20KB大小的作业进入1号空闲分区，这时空闲分区如下表所示。
[tbl-90.md](tbl-90.md)
此时再无空闲分区可以满足200KB大小的作业，所以该作业序列请求无法满足。
采用最佳适应算法时，作业序列分别进入5、1、4号空闲分区，可以满足其请求。分配处理之后的空闲分区表见下表：
[tbl-91.md](tbl-91.md)
02.【解答】
1）最先适配的内存分配情况如下图中的(a)所示。
<!-- page: 221 -->
(a)
(b)
内存中的空块为：
第一块：始址 290K，大小 10KB；第二块：始址 400K，大小 112KB。
2）最佳适配的内存分配情况如下图中的(b)所示。
内存中的空块为：
第一块：始址 240K，大小 60KB；第二块：超始地址 450K，大小 62KB。
3）若随后又要申请80KB，则最先适配算法可以分配成功，而最佳适配算法则没有足够大的空闲区分配。这说明最先适配算法尽可能地使用了低地址部分的空闲区域，留下了高地址部分的大的空闲区，更有可能满足进程的申请。
03. 【解答】
1）由题图所示的逻辑地址结构可知：页或段的最大个数为 $2^{5} = 32$。若左图是段式管理，则段始址12加上偏移量586，远超第1段的段始址15，超过第4段的段始址20，所以左图是页式变换，而右图满足段式变换。对于页式管理，由逻辑地址的位移量位数可知，一页的大小为2KB。
2）对图中的页式地址变换，其物理地址为 $12 \times 2048 + 586 = 25162$；对图中的段式地址变换，其物理地址为 $4000 + 586 = 4586$。
04. 【解答】
1）由段表知，第0段内存始址为210，段长为500，因此逻辑地址(0、430)是合法地址，对应的物理地址为 $210 + 430 = 640$。
2）由段表知，第1段内存始址为2350，段长为20，因此逻辑地址(1、10)是合法地址，对应的物理地址为 $2350 + 10 = 2360$。
3）由段表知，第2段内存始址为100，段长为90，逻辑地址(2、500)的段内位移500超过了段长，因此为非法地址。
4）由段表知，第3段内存始址为1350，段长为590，因此逻辑地址(3、400)是合法地址，对应的物理地址为 $1350 + 400 = 1750$。
5）由段表知，第4段内存始址为1938，段长为95，逻辑地址(4、112)的段内位移112超过了段长，因此为非法地址。
6）由段表知，不存在第5段，因此逻辑地址(5、32)为非法地址。
05. 【解答】
页面大小为1KB，所以低10位为页内偏移地址；用户编程空间为32个页面，即逻辑地址高5位为虚页号；主存为16个页面，即物理地址高4位为物理块号。
<!-- page: 222 -->
逻辑地址 0AC5H 转换为二进制是 000 1010 1100 0101B，虚页号为 2(00010B)，映射至物理块号 4，因此系统访问物理地址 12C5H(01 0010 1100 0101B)。
逻辑地址 1AC5H 转换为二进制是 001 1010 1100 0101B，虚页号为 6(00110B)，不在页面映射表中，会产生缺页中断，系统进行缺页中断处理。
逻辑地址 3AC5H 转换为二进制是 011 1010 1100 0101B，页号为 14，而该用户程序只有 10 页，因此系统产生越界中断。
## 注意
当将十六进制地址转换为二进制地址时，我们可能习惯性地写为 16 位，这是容易犯错的细节。例如，题中的逻辑地址为 15 位，物理地址为 14 位。逻辑地址 0AC5H 的二进制表示为 000 1010 1100 0101B，对应物理地址 12C5H 的二进制表示为 01 0010 1100 0101B。这一点应该引起注意。
## 06. 【解答】
1）页面的大小为 (64/16)KB = 4KB，该进程共有 4 页，所以该进程的总长度为 4×4KB = 16KB。
2）页面大小为 4KB，因此低 12 位为页内偏移地址；主存分为 16 块，因此内存物理地址高 4 位为主存块号。
页号为 0 的页面被装入主存的第 9 块，因此该地址在内存中的始址为 1001 0000 0000 0000B，即 9000H。
页号为 1 的页面被装入主存的第 0 块，因此该地址在内存中的始址为 0000 0000 0000 0000B，即 0000H。
页号为 2 的页面被装入主存的第 1 块，因此该地址在内存中的始址为 0001 0000 0000 0000，即 1000H。
页号为 3 的页面被装入主存的第 14 块，因此该地址在内存中的始址为 1110 0000 0000 0000，即 E000H。
3）逻辑地址为 (0, 0)，因此内存地址为 (9, 0) = 1001 0000 0000 0000B，即 9000H。
逻辑地址为 (1, 72)，因此内存地址为 (0, 72) = 0000 0000 0100 1000B，即 0048H。
逻辑地址为 (2, 1023)，因此内存地址为 (1, 1023) = 0001 0011 1111 1111，即 13FFH。
逻辑地址为 (3, 99)，因此内存地址为 (14, 99) = 1110 0000 0110 0011，即 E063H。
## 07. 【解答】
要注意题目中的逻辑地址使用哪种进制的数给出，若是十进制，则一般通过整数除法和求余得到页号和页内偏移，若用其他进制给出，则一般转换成二进制，然后按照地址结构划分为页号部分和页内偏移部分，再把页号和页内偏移计算出来。
页面大小为 64B，因此页内位移为 6 位，进程代码段长度为 702B，因此需要 11 个页面，编号为 0～10。
1）八进制逻辑地址 0105 的二进制表示为 0 0100 0101B。逻辑页号为 1，此页号可在快表中查找到，得页帧号为 F1；页内位移为 5，因此物理地址为 (F1, 5)。
2）八进制逻辑地址 0217 的二进制表示为 0 1000 1111B。逻辑页号为 2，此页号可在快表中查找到，得页帧号为 F2；页内位移为 15，因此物理地址为 (F2, 15)。
3）八进制逻辑地址 0567 的二进制表示为 1 0111 0111B。逻辑页号为 5，此页号不在快表中，在内存页表中可以查找到，得页帧号为 F5；页内位移为 55，因此物理地址为 (F5, 55)。
4）八进制逻辑地址 01120 的二进制表示为 0010 0101 0000B。逻辑页号为 9，此页号不在快表中，在内存页表中可以查找到，得页帧号为 F9；页内位移为 16，因此物理地址为 (F9, 16)。
<!-- page: 223 -->
5）八进制逻辑地址02500的二进制表示为0101 0100 0000B。逻辑页号为21，此页号已超过页表的最大页号10，因此产生越界中断。
**注意**
根据题中条件无法得知逻辑地址位数，所以在其二进制表示中，其位数并不一致，只是根据八进制表示进行转换。若已知逻辑地址空间大小或位数，则二进制表示必须保持一致。
**08.【解答】**
页表在主存时，实现一次存取需要访问主存两次：第一次是访问页表，获得所需访问数据所在页面的物理地址；第二次才是根据这个物理地址存取数据。
1）因为页表在主存，所以CPU必须访问主存两次，即实现一次页面访问的存取时间是 $1.5 \times 2 = 3 \mu \mathrm{s}$
2）系统增加快表后，在快表中找到页表项的概率为 $85\%$，所以实现一次页面访问的存取时间为 $0.85 \times (0 + 1.5) + (1 - 0.85) \times 2 \times 1.5 = 1.725 \mu \mathrm{s}$
**09.【解答】**
1）在页式存储管理中，访问指令或数据时，首先要访问内存中的页表，查找到指令或数据所在页面对应的页表项，然后根据页表项查找访问指令或数据所在的内存页面。需要访问内存2次。
段式存储管理同理，需要访问内存2次。段页式存储管理，首先要访问内存中的段表，然后访问内存中的页表，最后访问指令或数据所在的内存页面，需要访问内存3次。
对于比较复杂的情况，如多级页表，若页表划分为 $N$ 级，则需要访问内存 $N + 1$ 次。若系统中有快表，则在快表命中时，只需要访问内存1次。
2）按1）中的访问过程分析，有效存取时间为
$$
(0.2 + 1) \times 85\% + (0.2 + 1 + 1) \times (1 - 85\%) = 1.35 \mu \mathrm{s}
$$
3）同理可计算得
$$
(0.2 + 1) \times 50\% + (0.2 + 1 + 1) \times (1 - 50\%) = 1.7 \mu \mathrm{s}
$$
从结果可以看出，快表的命中率对访存时间影响非常大。当命中率从 $85\%$ 降低到 $50\%$ 时，有效存取时间增加 $0.35 \mu \mathrm{s}$。因此在页式存储系统中，应尽可能地提高快表的命中率，从而提高系统效率。
**10.【解答】**
1）位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，其值为“0”时表示对应盘块空闲，为“1”时表示已分配，地址空间分页，每页为1KB，则对应的盘块大小也为1KB，主存总容量为256KB，可分成256个盘块，长5.2KB的作业需要占用6页空间，假设页号与物理块号都从0开始，则根据位示图可得到页表内容如下：
[tbl-92.md](tbl-92.md)
2）页式存储管理中有内存碎片的存在，会存在内部碎片。为该作业分配内存后，会产生内
<!-- page: 224 -->
存碎片，因为此作业大小为 5.2KB，占 6 页，前 5 页满，最后一页只占 0.2KB 的空间，因此内存碎片得大小为 1KB - 0.2KB = 0.8KB。
3）64MB 内存，一页大小为 4KB，共可分成 $64\mathrm{K} \times 1\mathrm{K} / 4\mathrm{K} = 2^{14}$ 个物理盘块，在位示图中每个盘块占 1 位，共占 $2^{14}$ 位空间，因为 $1\mathrm{B} = 8$ 位，所以此位示图共占 2KB 空间的内存。
## 11. 【解答】
1）因为主存按字节编址，页内偏移量是 12 位，所以页大小为 $2^{12}\mathrm{B} = 4\mathrm{KB}$。页表项数为 $2^{32} / 4\mathrm{K} = 2^{20}$，因此该一级页表最大为 $2^{20} \times 4\mathrm{B} = 4\mathrm{MB}$。
2）页目录号可表示为(((unsigned int)(LA))>>22) & 0x3FF。这里采用的方法是逻辑右移 22 位，再和 3FF（10 个 1）进行逻辑与运算，得到 10 位的页目录号。这种方法虽然效率较高，但比较难想到，采用 LA/2²² 的写法来取高 10 位的页目录号也是可以的。页表索引可表示为(((unsigned int)(LA))>>12) & 0x3FF。这里也可采用 (LA/2¹²)%2¹⁰ 的方法来获取中间 10 位的页表索引号。
3）代码页面 1 的逻辑地址为 0000 8000H，表明其位于第 8 个页处，对应页表中的第 8 个页表项，所以第 8 个页表项的物理地址 = 页表始址 + 8 × 页表项的字节数 = 0020 0000H + 8 × 4 = 0020 0020H。由此可得如下图所示的答案。
## 3.2 虚拟内存管理
在学习本节时，请读者思考以下问题：
1）为什么要引入虚拟内存？
2）虚拟内存空间的大小由什么因素决定？
3）虚拟内存是怎么解决问题的？会带来什么问题？
读者要掌握虚拟内存解决问题的思想，了解各种替换算法的优劣，掌握虚实地址的变换方法。
## 3.2.1 虚拟内存的基本概念
### 1. 传统存储管理方式的特征
3.1 节讨论的各种内存管理策略都是为了同时将多个进程保存在内存中，以便允许进行多道程序设计。它们都具有以下两个共同的特征：
1）一次性。作业必须一次性全部装入内存后，才能开始运行。这会导致两个问题：①当作业很大而不能全部被装入内存时，将使该作业无法运行；②当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序并发度的下降。
2）驻留性。作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程会因等待 I/O 而被阻塞，可能处于长期等待状态。
由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，
<!-- page: 225 -->
而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
## 2. 局部性原理
要真正理解虚拟内存技术的思想，首先必须了解著名的局部性原理。从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，又适用于数据结构。局部性原理表现在以下两个方面：
### 前言前言
页面置换算法的时间局部性分析（2012）
1）时间局部性。程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。
2）空间局部性。一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存。
## 3. 虚拟存储器的定义和特征
### 前言前言
虚拟存储器的特点（2012）
基于局部性原理，在程序装入时，仅需将程序当前运行要用到的少数页面（或段）装入内存，而将其余部分暂留在外存，便可启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序，这个过程就是请求调页（或请求调段）功能。当内存空间不够时，由操作系统负责将内存中暂时用不到的信息换出到外存，从而腾出空间存放将要调入内存的信息，这个过程就是页面置换（或段置换）功能。这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（均对用户透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。但容量大只是一种错觉，是虚的。虚拟存储器有以下三个主要特征：
1）多次性。无须在作业运行时一次性全部装入内存，而是允许被分成多次调入内存，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚未调入的那部分程序或数据时，再将它们调入。多次性是虚拟存储器最重要的特征。
2）对换性。在作业运行时无须一直常驻内存，而是允许在作业运行过程中，将那些暂不使用的程序和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换进）。正是由于对换性，才使得虚拟存储器得以正常运行。
3）虚拟性。从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际容量。这是虚拟存储器所表现出的最重要特征，也是实现虚拟存储器的最重要目标。
## 4. 虚拟内存技术的实现
虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
虚拟内存的实现有以下三种方式：
- 请求分页存储管理。
<!-- page: 226 -->
- 请求分段存储管理。
- 请求段页式存储管理。
不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：
- 一定容量的内存和外存。
- 页表机制（或段表机制），作为主要的数据结构。
- 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。
- 地址变换机构，逻辑地址到物理地址的变换。