考研分区
-
2023年2月12日发(作者：)考研操作系统-内存与虚拟(三)
(总分：212.00，做题时间：90分钟)
一、判断题(总题数：11，分数：44.00)
1.页式存储管理中，用户应将自己的程序划分成若干大小相等的页面。
A.正确
B.错误√
用户无需将程序划分为页面，这个工作由操作系统自动完成。
判断下面关于存储器管理功能的论述是否正确：
（分数：8.00）
(1).即使在多道程序设计环境下，用户也能设计用内存物理地址直接访问内存的程序。
A.正确√
B.错误
在多道编程时，用户可使用汇编指令或其他特殊指令来分配使用物理内存空间。
(2).为了提高内存保护的灵活性，内存保护通常由软件实现。
A.正确
B.错误√
内存保护通常由硬件实现，目的是提高内存访问的效率。
(3).交换技术已不是现代操作系统中常用的一种技术。
A.正确
B.错误√
现代的段式或段页式存储管理仍然使用交换技术。
(4).虚拟存储器能在物理上扩充内存容量。
A.正确
B.错误√
虚拟存储器并不增加物理上的内存容量，而是增加虚存容量。
2.按最先适应算法分配的分区，一定与作业要求的容量大小最接近。
A.正确
B.错误√
该算法是分配第一个能够容纳作业的分区，而这个分区并不一定与作业要求的容量大小最接近。
3.对于请求分页式存储管理系统，若把页面的大小增加一倍，则缺页中断次数会减少一半。
A.正确
B.错误√
页面大小的增加可导致缺页次数的减少，但它们之间的数量关系却并不清楚。
4.在一个分页系统中，根据需要，页面的大小可以不相等。
A.正确√
B.错误
页面确实可以依据需要进行调整，但一个系统同时使用几种页面尺寸容易导致管理复杂，因此并不常用。
判断以下有关可变分区管理的说法是否正确：
（分数：8.00）
(1).最差适应算法总是挑选最大的空闲区用于分割，使得剩下的分区仍可使用。
A.正确√
B.错误
(2).可变分区管理常采用的内存分配算法包括最先适应、最佳适应和最差适应算法。
A.正确√
B.错误
(3).最先适应算法实现简单，但碎片过多使内存空间利用率降低。
A.正确
B.错误√
最先适应算法在实际中效果不错，碎片较少。
(4).最佳适应算法是最好的算法，但后到的较大作业很难得到满足。
A.正确
B.错误√
最佳适应算法满足大作业的能力不错，但碎片较多。
判断下面关于重定位的说法是否正确：
（分数：8.00）
(1).绝对地址是内存空间的地址编号。
A.正确√
B.错误
绝对地址就是物理内存地址，即内存空间的地址编号。
(2).用户程序中使用的从0地址开始的地址编号是逻辑地址。
A.正确√
B.错误
用户编程空间是虚拟地址空间，里面的每个地址都是逻辑地址，编号从0开始。
(3).动态重定位中装入内存的作业仍保持原来的逻辑地址。
A.正确√
B.错误
动态重定位装入的作业保持原来的逻辑地址，但在执行时这些逻辑地址需要被转换为内存物理地址才能真
正使用。
(4).静态重定位中，地址转换工作是在作业装入过程中完成的。
A.正确√
B.错误
静态重定位在装入过程完成地址转换。
判断下面关于分页系统的页面大小的说法是否正确：
（分数：6.00）
(1).页面大的好处是页表较小。
A.正确√
B.错误
页面大可减少虚拟空间的页面数，从而减少页表尺寸。
(2).页面小的好处是可以减少由内部碎片引起的内存浪费。
A.正确√
B.错误
内部碎片一般为最后一个页面的一半，页面越小，浪费越小。
(3).通常，影响磁盘访问时间的主要因素不在于页面的大小，所以使用时可优先考虑大的页面。
A.正确√
B.错误
磁盘访问时间主要是寻道和旋转时间，与页面大小关系不大。
5.段页式结合了段式和页式的优点，所以段页式的内部碎片和页式的一样少。
A.正确
B.错误√
段页式由于一个程序分为多段，而每个段都存在内部碎片，因此其碎片将比页式系统多。
6.可变式分区解决了碎片问题。
A.正确
B.错误√
可变式分区通过变换区间的大小，可适当降低碎片问题，但无法从根本上解决碎片问题。
7.可重入代码又称为“纯代码”，是一种允许多个进程同时访问的代码，在执行过程中不允许有任何改变。
A.正确√
B.错误
可重入代码就是允许多个进程同时访问的代码。它必定不能包括数据，否则一个进程改变了数据，则另外
的进程就可能不能正确运行。
二、应用题(总题数：21，分数：168.00)
8.在某多道程序系统中，供用户使用的内存空间为100KB，磁带机2台，打印机1台。系统采用可变式分
区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入、输出操作的时间忽略不计。现
有一作业序列如下表所示：
作业到达时间计算时间min要求内存KB
申请磁带机
数
申请打印机
数
18:00251511
28:2010301
38:2020601
48:3020201
58:35151011
假设作业调度采用先来先服务算法，优先分配内存的低地址区域且不准移动已在内存中的作业，试解答如
下问题：
(1)作业的调度顺序是什么?
(2)平均周转时间是多少?
(3)作业什么时候全部执行完成?
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)8:00作业1首先到达，将获得内存和所需其他资源，即15KB内存、1台打印机、1台磁带
机。20分钟后，作业2、3同时到达，二者中作业2的设备请求不能满足，无法推进。因此作业3获得所
需资源，即60KB内存和1台磁带机。8:25时，作业1结束，作业2可以获得其所需的30KB内存和1台打
印机，从而往前推进。8:30时，作业4到达，但作业2、3仍然在进行，作业4的内存需求不能满足，处
于等待状态。8:35，作业2结束，作业4可以获得其所需的20KB内存和1台磁带机，往前推进。此时作业
5也到达，其所需资源均能满足，因此也往前推进。8:40时，作业3结束。8:50，作业5结束，8:55，作
业4结束。因此，作业调度川页序为：1、3、2、4、5。
(2)从前面的分析可知，作业1周转时间为25分钟，作业2为15分钟，作业3为20分钟，作业4为25分
钟，作业5为15分钟。平均周转时间为(25+15+20+25+15)/5=20分钟。
(3)从上面的分析可知，作业执行全部结束的时间是8:55。)
9.在一个请求分页存储管理系统中，容量为1MB的主存被划分为256块，每块大小为4KB。现有一作业，
其页表如下表所示。
页号块号状态
0240
1360
2320
3—1
4—1
试问：
(1)若给定逻辑地址为9016(十进制)，求其物理地址。
(2)若给定逻辑地址为12300(十进制)，其物理地址又如何?
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)主存分成256块，说明一共能存放256个页面。每块大小为4KB，说明页内地址所占位数
为12位。而十进制地址9016可以表示为：10，也就是页面号为2，页内地址为(十
进制的824)。从页表可知页面2存放在物理内存的块32。因此，最后的物理地址为：32×4KB+824=128KB+824。
(2)若给定逻辑地址为12300，按与(1)中同样的方法处理可得其页号为3。从页表可知该页未装入主存，因
而产生缺页中断。随后中断处理程序将该页装入主存，然后进行地址变换。)
10.有一个系统内存容量为1024KB，有8个作业同时到达，各作业需要的内存量和运行时间如下表所示：
作业编号需要内存量(KB)运行时间(s)
11403
2801
31003
4602
5501
6303
7152
8203
假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，系统有足够多的CPU，分配到内存的作
业都可以立即运行。问：
(1)1s后，内存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接?
(2)2s后，其内存空白区按上述两种算法如何链接?
(3)在(2)后，此时有一个作业9要求进入内存，它需要的内存量为12KB，按上述两种算法，将把哪一块空
白区分给它?
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)由于8个作业同时进入，系统按照作业编号顺序分配内存，所有作业形成一片连续的内存
占用空间。在1s后，作业2和作业5结束，出现两个内存空闲区，如下图所示。
注意上述结果与采用何种适用算法无关。
(2)在2s后，作业4和作业7结束，内存占用和闲置情况如下图所示：
注意上述结果与采用何种适用算法无关。
(3)如果新作业9要进入内存，按照首次适应算法，作业9将进入作业3上面的空闲区，情况如下图所示：
如果采用最佳适应算法，则作业9将进入作业6上面的空闲区，如下图所示：
)
11.在一个请求分页管理中，一个程序的页面访问顺序为4，3，2，1，4，3，5，4，3，2，1，5。系统采
用的页面替换算法为LRU页面置换算法。
(1)当分配给程序4个存储块时，求出缺页中断的次数。
(2)当分配给程序5个存储块时，求出缺页中断的次数。
(3)以上结果说明了什么?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(当分配给程序4个存储块时，缺页中断情况如下表所示：
时刻1112
访问页面432143543215
内存页面
432143543215
43214354321
4321435432
432111543
缺页++++++++
缺页中断的次数为8次。
(2)当分配给程序5个存储块时，利用LRU页面置换算法缺页中断情况如下表所示：
时刻1112
访问页面432143543215
内存页面
432143543215
43214354321
4321435432
432111543
222154
缺页+++++
缺页中断的次数为5次。
(3)以上结果说明：采用LRU页面置换算法的情况下，增加主存容量将降低缺页中断的次数。
)
12.已知某系统页面长为4KB，页表项为4B，采用多层分页策略映射64位虚拟地址空间，若限定最高层页
表占1页，问需要采用几层分页策略?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(根据题意，一个页面有记录4KB/4B=1000个。64位虚拟地址空间共有页面264/4KB=252个。最高
层页表只有1页，则第2层有1000页，第3层有1000000页，到第6层时有页面1015＞252。因此需要采用
6层分页策略。
这个题目也可以这样来解：由于每层页表的大小都不超过一页，所以每层的页号不超过10位。由于层数n
需要满足不等式10×n+12≥64，所以采用6层。)
13.在请求分页存储管理系统中，设一个作业访问页面的序列为4，3，2，1，4，3，5，4，3，2，1，5。
设分配给该作业的存储空间有4块，且最初未装入任何页。试计算FIFO和LRU算法的失页率。
（分数：8.00）
__________________________________________________________________________________________
正确答案：(采用FIFO页面置换算法时，该作业运行时缺页情况如下表所示：
时刻1112
访问页面432143543215
内存页面
432111543215
43222154321
4333215432
444321543
缺页++++++++++
从表中可以看出，缺页中断次数为10；失页率为f=10/12=83%。
采用LRU页面置换算法时，该作业运行时缺页情况如下表所示：
时刻1112
访问页面432143543215
内存页面
432143543215
43214354321
4321435432
432111543
缺页++++++++
从表中可以看出，缺页中断次数为8，失页率为8/12=67%。
)
14.在页式虚拟存储管理系统中，假定驻留集为M个页帧(初始所有页帧均为空)，在长为P的引用串中具有
Ⅳ个不同页号(N＞M)，对于FIFO和LRU两种页面替换算法，试求出缺页中断的上限和下限，说明理由。
（分数：8.00）
__________________________________________________________________________________________
正确答案：(不管采用什么替换算法，由于有N个不同的页面，且初始情况下驻留集为M个页帧均为空，因
此缺页的下限都是N。对于FIFO来说，缺页中断的上限出现在以轮转方式访问所有页面时，则每次访问均
产生一个缺页中断，即上限为P。对于LRU替换算法来说，缺页中断上限出现在每次访问的都是前面M个
页面以外的页面时，此时每次访问均产生缺页中断，即上限为P。)
15.一个计算机有Cache和一个用作虚拟内存的磁盘。若从Cache中读取一个字所用的时间为Ans，从内存
中将一个字读入Cache的时间为Bns，从磁盘中将一个字调入内存的时间为Cns。若在Cache中读取一个字
的命中率是(n-1)/n，在内存中读取一个字的命中率是(m-1)/m，则平均访问时间是多少?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(平均访问时间是[(n-1)/n]·A+[(m-1)/m]·B+[1-(n-1)/n-(m-1)/m]·C。这里假定从内存读入
Cache时和从磁盘读入到内存时，数据也同时传给处理器。)
16.有一矩阵varA:array[1..100，1..100]ofinteger以行为先进行存储。有一个虚存系统，物理内存
共有三页，其中一页用来存放程序，其余两页用于存放数据。假设程序已在内存中占一页，其余两页空闲。
程序A：
fori:=1to100do
forj:=1to100do
A[i,j]:=0;
程序B：
forj:=1to100do
fori:=1to100do
A[i,j]:=0;
若每页可存放200个整数，程序A和程序B的执行过程各会发生多少次缺页?若每页只能存放100个整数呢?
以上说明了什么问题?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(有两个内存块可以用来存放数组信息，每个主存块可存放200个数组元素，数组中的元素按行
编址。对于程序A来说，其访问顺序也是按行进行，由于每行有100个元素，每访问两行遇到一次缺页中
断。如果采用FIFO或LRU页面调度算法，一共产生50次缺页中断。
对于程序B来说，其访问顺序按列进行，与数组的按行存储顺序不一致，每访问两个数组元素将发生一次
缺页中断。如果采FIFO或LRU页面调度算法，一共产生5000次缺页中断。
若每页只能存放100个整数，对于程序A，数组的存储顺序与访问顺序一致，每访问一行数组遇到一次缺
页中断。如果采用FIFO或LRU页面调度算法，会产生100次缺页中断。对于程序B，数组的存储顺序与访
问顺序不一致，每访问一个数组元素遇到一次缺页中断。如果采用FIFO或LRU页面调度算法，一共产生
10000次缺页中断。
以上结果说明：页面越大，缺页中断次数越少；页面越小，缺页中断次数越多。)
17.有5个待运行作业J1、J2、J3、J4、J5，各自预计运行时间分别是9、6、3、5和7。假定这些作业同时
到达，并且在一台处理机上按单道方式执行。讨论采用哪种调度算法和哪种运行次序将使平均周转时间最
短。平均周转时间为多少?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(按小作业优先算法的平均周转时间最短。此时作业执行顺序为J3，J4，J2，J5，J1，平均周转时
间为：
T=[3+(3+5)+(3+5+6)+(3+5+6+7)+(3+5+6+7+9)]/5=15.2)
18.设作业的虚拟地址宽度为24位，其中高8位为段号，低16位为段内相对地址。试问：
(1)一个作业最多可以有多少段?
(2)每段的最大长度为多少字节?
(3)某段式存储管理采用如下段表，试计算[0，430]、[1，50]、[2，30]、[3，70]的主存地址。其中方括
号内的前一元素为段号，后一元素为段内地址。当无法进行地址变换时，应说明产生何种中断。
段号段长
主存起始地
址
是否在主存
06002100是
1402800是
2100否
3804000是
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)一个作业最多可以有28=254个段。
(2)每段的最大长度为216=655365字节=64KB。
(3)逻辑地址[0，430]的主存地址为：2100+430=2530。
逻辑地址[1，50]的段内地址超过段长，无法进行地址变换，将产生越界中断。
逻辑地址[2，30]所在的第2段没有驻存在内存中，无法进行地址变换，将产生缺段中断。
逻辑地址[3，70]的主存地址为：4000+70=4070。)
19.某请求页式系统允许用户空间为32个页面(每页1KB)，主存为16KB，若一个用户程序有10页长，某时
刻该进程的页表如下所示：
虚页号物理块号是否在TLB中
08是
17是
24否
310否
45否
53是
62是
其他无效
问：(1)计算虚地址0AC5H、1AC5H对应的物理地址。
(2)页表存放在主存中，对主存的一次存取需要1.5ns，对TLB表的查找时间忽略为0，试问这两次访问共
耗费多少时间?
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)32个页面需要用5位来区分，页内地址需要10位。虚地址0AC5H的页号为2，页内地址为
1011000101。从页表可知，其物理块号为4，因此，其物理地址为1=12C5H。虚地址1AC5H的
页号为6，页内地址为1011000101。根据页表可知，该虚地址对应的物理块号为2，其物理地址为
1=0AC5H。
(2)第1次访问TLB没有命中，因此需要查找页表，再访问主存一次，总计时间为3ns。第2个虚地址在TLB
中，只需要一次内存访问，总时间为1.5ns。)
20.一台机器有48位虚地址和32位物理地址，页面是8K，问在页表中需要多少个页表项?一个倒置的页表
需要多少个页表项呢?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(48位虚地址共有248/8K=235个页面，即需要235个页表项。如果使用反转页表，则一共有232/8K=219
个页面，即需要219个页表项。)
21.某程序在逻辑地址100处有一条指令LOAD1，500，而500单元内存放数据51888。假设程序被分配到
内存起始地址为5000的单元时，采用下述各种方式下的该指令与其物理地址及相应的地址变换过程。
(1)静态重定位。
(2)采用重定位寄存器实现动态重定位。
(3)采用页表方式，页面大小为100B，其各页存放到50，51，52，…，59物理块上。
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)采用静态重定位时，所有逻辑到物理地址的转换在程序装入时完成。由于程序被分配到内
存起始地址为5000的单元，该条指令所处单元将为5000+100=5100。而数据所处的500逻辑单元所处的物
理地址为5000+500=5500，即指令将变为：LOAD15500。
(2)采用重定位寄存器实现动态重定位时，地址转换在需要访问时动态完成。由于程序被分配到内存起始地
址为5000的单元，重定位寄存器的取值为5000。该条指令所处的地址仍然为100。在访问地址100时，系
统将在其上加上5000，获得物理地址5100。由于是动态重定位，指令在装入内存时维持不变。在实际执行
该指令时，将在地址500处寻找数据。此时系统将对该地址进行动态翻译，加上5000，获得物理地址为
5000+500=5500。
(3)采用页式方式时，由于页面大小为100B，逻辑地址100将处于第1个页面(从0号页面开始计数)，地
址500处于第5个页面。其页内偏差(页内地址)均为0。根据题意，这两个页面分别处于物理块51和55
上。因此，其物理地址分别为51×100+0=5100和55×100+0=5500。)
22.假定存储器空闲块有如下结构：
请构造一串内存请求序列，首次适应分配算法能满足该请求序列，而最佳适应分配算法则不能。
（分数：8.00）
__________________________________________________________________________________________
正确答案：(150、250、250、500。该请求序列在首次适应分配算法情况下可以满足；而最佳适应分配算法
下，作业1将获得250B中的150B，接下来的250B将获得350B中的250B，接下来的250B将获得500B中
的250B，剩下的500B将无法得到满足。
)
23.在一个分页存储管理系统中，页面大小为4KB，系统中的地址占24位，给定页表如下。
页号P块号B
03
14
29
37
(1)计算逻辑地址(页号为3，页内地址为100)的物理地址。
(2)说明地址变换过程。
（分数：8.00）
__________________________________________________________________________________________
正确答案：((1)逻辑地址(页号为3，页内地址为100)的物理地址为：7×4KB+100=28KB+100=28772。
(2)在请求分页存储管理方案中，系统是通过页表来进行地址转换的。先将逻辑地址分解成页号P和页内地
址w两部分，然后通过查页表获得页号P对应的物理块号B。将物理块号乘以页面大小，再将页内地址W
加到其上即获得最终的物理地址，即变换公式如下：
物理地址=块号×页面大小+页内地址)
24.一台计算机为每个进程提供655365字节的地址空间，划分为4K字节的页。一个特定的程序有32768字
节的正文、163865字节的数据和15870字节的堆栈。这个程序能装入地址空间吗?如果页面长度是512字
节，能装得下这个程序吗?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(如果划分为4K字节的页面，则每个进程空间大小为65536/4K=16个页面。对于题目给定的特
定程序来说，其正文占32768/4K=8个页面，数据占16386/4K=5个页面，堆栈占15870/4K=4个页面，总共
需要17个页面，因此不能装入。
如果划分为512字节的页面，则每个进程空间大小为65536/512=128个页面。对于题目给定的特定程序来
说，其正文占32768/512=64个页面，数据占16386/512=33个页面，堆栈占15870/512=31个页面，总共需
要128个页面，因此正好装入。)
25.假定某页式虚拟存储器中，内存的平均访问时间为1μs，辅存的平均访问时间为10ms，问：如果希望
虚拟存储器的平均访问时间仅比内存的增加10%，则需要页面失效率是多少?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(设失效率为m，则根据题意，m应满足不等式(1-m)+m×10000≤1.1，求解该等式可得m≤0.01%，
即页面失效率不能超过0.01%。注意本题解答时假定命中时仅有内存访问，未命中时仅有辅存访问。)
26.设作业A、B、C的大小分别为30K、70K和50K，它们依次请求内存分配。内存现有大小分别为100K、
50K的两个空闲区F1、F2，如下图所示。分别采用最佳适应算法和最差适应算法，画出内存分配情况示意
图。
（分数：8.00）
__________________________________________________________________________________________
正确答案：(采用最佳适应算法，内存分配情况如下图所示。
从上图可以看出，在最佳适应算法下，C的内存请求将得不到满足。
按最差适应算法，内存分配情况如下图所示。
从上图可以看出，按最差适应算法，三个作业的内存请求全部得到满足。)
27.在一个32位计算机的虚拟页式存储管理系统中，怎样解决页表非常庞大的问题?请给出具体解决方案
(假设页面大小为4K，用户空间为2GB，每个内存块用4字节表示)。
（分数：8.00）
__________________________________________________________________________________________
正确答案：(用户空间为2GB，页面大小为4K，则页表的记录数为2GB/4K=524288(这里采用的转换率是
1G=1024M=1024×1024K)。由于每个内存块在页表里占用4个字节，页表所占内存空间为524288×4=2097152
字节=2M。要减少这个空间，可以使用多级页表或反转页表。由于题目没有给出物理内存大小，反转页表的
大小无法计算。如果采用多级页表，计算如下：2M的空间一共需要占用2M/4K=512个页面，顶级页表占用
一页，一共可以记录1024个次级页表的页面数，这个数目已经超过页表的总页面数，因此分为两级页表即
可解决问题。
)
28.人们观察到在两次页故障之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，页故障的
平均间隔也加倍。假设一条普通指令需要1μs，但若发生了页面故障就需要2001μs。一个程序运行了60s，
期间发生了1500次页面故障，如果该页面的可用内存是原来的2倍，这个程序运行需要多少时间?
（分数：8.00）
__________________________________________________________________________________________
正确答案：(设该程序共执行指令条数为n，根据题意，运行60s中发生1500次缺页中断，n必满足等式：
1500×2001+(n-1500)=60000000，即n=57000000。在内存页面数加倍后，缺页中断次数降低一半，程序运
行时间将为：750×2001+(57000000-750)=58500000μs=58.5s。)