2021 年春《操作系统》期末试卷

考试日期为 2021 年 6 月 10 日。除排版和明显的 OCR 标点外，题面按源试卷转录；源文件末尾附有答案，我把它们放在各题后的折叠区域中。答案只做转录，不代替校订：源答案留空、表述不完整或可能存在笔误的地方会原样说明。

一、判断题（每题 1 分，共 10 分）

中断方式的数据传送是在中断处理时由 CPU 控制完成的；而在 DMA 方式下，数据传送过程不经过 CPU，是在 DMA 控制器的控制下完成的。（　）
管道机制中的数据只存在于内存中。（　）
在一个磁盘上设置多个分区能改善磁盘设备 I/O 性能。（　）
分页存储管理技术，是用于虚存管理的技术，但也可以用于物理内存管理。（　）
简单地说，进程是程序的执行过程。因而，进程和程序是一一对应的。（　）
操作系统中的 Spooling 技术，实质是将独占设备转换为共享设备的技术。（　）
将二进制证书转换为文本以便打印是设备无关软件层负责的。（　）
一个物理硬盘可以分成多个逻辑硬盘分区进行面向用户文件系统的管理。（　）
设备控制器是一块能控制一台或多台外围设备与 CPU 并行工作的硬件。（　）
在内存管理中，地址空间不能小于物理内存空间。（　）

查看源文件答案

二、单项选择题（每题 2 分，共 20 分）

1. 用户态事件

下列选项中，不可能在用户态发生的事件是（　）。

A. 系统调用

B. 外部中断

C. 进程切换

D. 缺页

2. 线程共享

在支持多线程的系统中，进程 P 创建的若干个线程不能共享的是（　）。

A. 进程 P 的代码段

B. 进程 P 中打开的文件

C. 进程 P 的全局变量

D. 进程 P 中某线程的栈指针

3. `read` 系统调用

若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（　）。

I. 若该文件的数据不在内存，则该进程进入阻塞状态。

II. 请求 read 系统调用会使 CPU 从用户态切换到核心态。

III. read 系统调用的参数应包含文件的名称。

A. 仅 I、II

B. 仅 I、III

C. 仅 II、III

D. I、II 和 III

4. 磁盘调度

假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有磁道访问请求序列 35、45、12、68、110、180、170、195，采用 SCAN（电梯）调度算法得到的磁道访问序列是（　）。

A. 110，170，180，195，68，45，35，12

B. 110，68，45，35，12，170，180，195

C. 110，170，180，195，12，35，45，68

D. 12，35，45，68，110，170，180，195

5. 页面置换

系统为某进程分配了 4 个页框，该进程已访问的页号序列为 2、0、2、9、3、4、2、8、2、4、8、4、5。若下一页的页号为 7，依据 LRU 算法，应淘汰的页号是（　）。

A. 2

B. 3

C. 4

D. 8

6. 记录式文件

对记录式文件，操作系统为用户存取文件信息的最小单位是（　）。

A. 字符

B. 数据项

C. 记录

D. 文件

7. 多进程操作系统

在一个多进程操作系统中，以下说法正确的是（　）。

A. 如果一个用户进程进入死循环，则其他进程永远不可能获得执行。

B. 如果一个用户进程进入死循环，操作系统可以终止该用户进程执行。

C. 如果一个用户进程执行“跳转到 0 地址”的指令，操作系统内核会立即崩溃。

D. 如果一个用户进程执行“除以 0”的指令，操作系统内核会立即崩溃。

8. 缓冲技术

缓冲技术用于（　）。

A. 协调主机和设备交换信息的速度差异

B. 提供主、辅存接口

C. 减少设备故障

D. 扩充相对地址空间

9. 实时操作系统

实时操作系统追求的目标是（　）。

A. 高吞吐率

B. 充分利用内存

C. 快速响应

D. 减少系统开销

10. 设备名

在操作系统中，用户在使用 I/O 设备时，通常采用（　）。

A. 物理设备名

B. 逻辑设备名

C. 虚拟设备名

D. 设备牌号

查看源文件答案

三、填空题（每空 1 分，共 10 分）

静态变量通常被装载到 ________ 段中，局部变量通常被装载到 ________ 段。
操作系统中虚拟内存机制有效的基础是程序访存的 ________ 原理。
一个进程的页面走向为 5、4、3、2、4、5、4、1、5、2、5、4、5、2、1，系统中共有 3 个物理内存页，开始时物理页中没有调入任何页面。使用最优页面淘汰算法的缺页次数为 ________ 次，使用 FIFO 页面淘汰算法的缺页次数为 ________ 次。
银行家算法是 ________ 死锁的方法。
从磁盘将 1 块数据传送到缓冲区用时 50 ms，将缓冲区中数据传送到用户区用时 20 ms，CPU 处理 1 块数据用时 60 ms。如果有很多块数据需要处理，采用单缓冲区传送磁盘数据，则系统吞吐能力约为 ________ 块/s（ $1\ \mathrm{s}=1000\ \mathrm{ms}$ ）。
按数据组织分类，设备分为两类：________ 和 ________。
在文件系统中，“.”通常表示 ________ 目录。

查看源文件答案

.data，.text
源答案未填写。
4，8
检测
14
块设备，字符设备
当前

四、内存管理（共 15 分）

一个 32 位虚拟存储系统采用两级页表结构，每个页面大小为 4096 字节。逻辑地址的第 22 到 31 位是第一级页表（页目录）的索引，第 12 到 21 位是第二级页表的索引，页内偏移占第 0 到 11 位。每个页表（目录）项包含 20 位物理页框号和 12 位标志位。

该系统的逻辑地址空间一共有多少字节？（1 分）
第一级页表共有多少页目录项？第二级页表共有多少页表项？（2 分）
假设第二级页表的起始逻辑地址为 0x1FC00000，请给出逻辑地址 0x01234567 对应的页目录项的逻辑地址。（3 分。提示：先根据自映射找出一级页表的起始逻辑地址。）
假设第二级页表的起始逻辑地址为 0x1FC00000，请给出一级页表对应的页目录项的逻辑地址。（3 分）
假设逻辑地址 0x12345678 对应的第二级页表的物理地址为 0x00007000，请给出该逻辑地址对应页表项的物理地址，以及该逻辑地址对应页目录项中包含的物理页框号。（6 分）

查看源文件答案

以下保留源答案的计算过程；其中第 3、5 小题所用地址或术语与题面不完全一致，我不替源文件改写。

逻辑地址有 32 位，因此逻辑地址空间有 $2^{32}$ 个字节。
页目录索引和页表索引均为 10 位，因此有 $2^{10}$ 个页目录项和 $2^{10}$ 个页表项。

源答案写作：

PTbase = 0x01234567 & 0xfffff000 = 0x01234000
0x01234000 | (0x01234000 >> 12 << 2) |
(0x01234000 >> 22 << 2) = 0x12348d20

源答案写作：

0x1FC00000 | (0x1FC00000 >> 12 << 2) |
(0x1FC00000 >> 22 << 2) = 0x1fc7f1fc

源答案先算出页内偏移：

0x12345678 & 0xfff = 0x678
0x00007000 | 0x678 = 0x00007678

五、进程同步与互斥（共 15 分）

一条自动生产线上有 4 个机器人 R1—R4。R1、R2 分别不断生产零件 X、Y；R3 不断把 X、Y 装配成零件 Z；R4 不断把 Z 加工成成品 P。

所有机器人通过一个共享零件暂存区传递零件。暂存区最多放 10 个零件，每次只允许一个机器人访问。R1、R2 必须等 R3 取走此前的 X、Y 后才能放入新零件，即暂存区中 X 和 Y 的数量分别不超过 1。

请用 PV 操作给出 4 个机器人的同步互斥过程，定义信号量、初值并作必要注释。除信号量外，不应定义其他变量。

R1 的主要动作：produceX()、putX()。
R2 的主要动作：produceY()、putY()。
R3 的主要动作：getX()、getY()、produceZ()、putZ()。
R4 的主要动作：getZ()、produceP()。
只有 get 或 put 开头的暂存区访问动作需要互斥；produce 开头的生产动作可以并发。

查看源文件答案

empty   = Semaphore(10); // 暂存区可以放 10 个零件
full_x  = Semaphore(0);  // 零件 X 满缓冲区
full_y  = Semaphore(0);  // 零件 Y 满缓冲区
full_z  = Semaphore(0);  // 零件 Z 满缓冲区
mutex   = Semaphore(1);  // 机器人互斥访问缓冲区
block_x = Semaphore(1);  // 生产一个零件 X 后阻塞
block_y = Semaphore(1);  // 生产一个零件 Y 后阻塞

main() {
  cobegin {
    R1();
    R2();
    R3();
    R4();
  } coend
}

R1() {
  P(block_x);
  produceX();
  P(empty);
  P(mutex);
  putX();
  V(mutex);
  V(full_x);
}

R2() {
  P(block_y);
  produceY();
  P(empty);
  P(mutex);
  putY();
  V(mutex);
  V(full_y);
}

R3() {
  P(full_x);
  getX();
  P(full_y);
  getY();
  produceZ();
  P(mutex);
  putZ();
  V(mutex);
  V(full_z);
  V(empty);
  V(block_x);
  V(block_y);
}

R4() {
  P(full_z);
  getZ();
  produceP();
  V(empty);
}

六、进程调度（共 10 分）

5 个进程的到达时间、运行时间和优先级如下。

进程 ID	到达时间	运行时间	优先级数
A	0	3	4
B	1	1	2
C	3	5	5
D	6	2	6
E	8	2	1

假设系统中没有其他进程，请分别按先来先服务（FCFS）、最短剩余时间优先（SRTF）、时间片轮转（RR）和静态优先级（Priority）调度，填写每个时刻在 CPU 上运行的进程 ID，并求各算法的平均等待时间。

RR 的时间片固定为 1；时间片耗尽后，当前进程加入就绪队列队尾。
优先级数越高，越优先被调度。
不考虑进程上下文切换开销；新进程在到达时刻即处于就绪状态并可被调度。
本题把等待时间定义为进程到达时刻与第一次被调度执行时刻之差。

时刻	FCFS	SRTF	RR	Priority
0
1
2
3
4
5
6
7
8
9
10
11
12
平均等待时间

查看源文件答案

时刻	FCFS	SRTF	RR	Priority
0	A	A	A	A
1	A	B	B	A
2	A	A	A	A
3	B	A	C	C
4	C	C	A	C
5	C	C	C	C
6	C	D	D	D
7	C	D	C	D
8	C	E	E	C
9	D	E	D	C
10	D	C	C	B
11	E	C	E	E
12	E	C	C	E
平均等待时间	1.8	1.2	2.2	2.4

源答案中的平均值计算为：

\begin{aligned} T_{\mathrm{FCFS}} &= (0+2+1+3+3)/5 = 1.8,\\ T_{\mathrm{SRTF}} &= (1+0+5+0+0)/5 = 1.2,\\ T_{\mathrm{RR}} &= (2+0+5+2+2)/5 = 2.2,\\ T_{\mathrm{Priority}} &= (0+9+0+0+3)/5 = 2.4. \end{aligned}

七、死锁（共 10 分）

系统中有 3 个进程 P1、P2、P3，运行这些进程需要 4 类资源 R1、R2、R3、R4。某时刻的资源状态如下。

进程	已分配 R1	已分配 R2	已分配 R3	已分配 R4	最多还需 R1	最多还需 R2	最多还需 R3	最多还需 R4
P1	0	0	1	0	2	0	0	1
P2	2	0	0	1	1	0	1	0
P3	0	1	2	0	2	1	0	0

当前可用资源为：

R1	R2	R3	R4
2	1	0	0

如果 3 个进程同时发出最大资源请求，请画出资源分配图，并用资源分配图化简的方法检测是否存在死锁。（5 分）
如果此时 P2 请求 1 个 R1，为避免产生死锁，请根据银行家算法判断是否可以满足 P2 的请求。（5 分）

查看源文件答案

第 1 小题在源答案中留空。

第 2 小题给出的资源变化表如下：

状态	R1	R2	R3	R4
当前	2	1	0	0
P3 结束	2	2	2	0
分配给 P2	1	2	1	0
P2 请求 R1	0	2	1	0
P2 结束	4	2	2	1
分配给 P1	2	2	2	0
P1 结束	4	2	3	1

源答案结论：可以满足 P2 的请求。

八、文件系统（共 10 分）

许多类 Unix 文件系统都采用索引方式组织文件，并用 i 节点（inode）存储文件或目录的属性信息和数据块地址。

某索引文件系统采用 512 字节的数据块和 4 字节的数据块地址。每个 i 节点含 10 个直接索引、1 个一级间接索引、1 个二级间接索引和 1 个三级间接索引。该文件系统中的文件最大为多少 KB？（5 分）
若要读取文件 /tmp/foo，请给出从根目录开始查找文件并读取数据的主要步骤。为简化，假设根目录内容可直接从内存读取，且不考虑间接索引。（5 分）

查看源文件答案

源答案令文件块大小 $s=512$ 字节、块地址大小 $t=4$ 字节，因此 $s/t=128$ 。其计算写作：
$(10+128+128^2+128^3)\times512=1056837\ \mathrm{KB}.$
源答案列出的步骤为：
- 根目录内容已在内存，因此直接从内存读取 tmp 目录内容。
- 读取 foo 的 inode 需要一次磁盘读取；从 foo 的目录项取得 inode 号，再由此读出 foo 的 inode。
- 读取 foo 的内容还需要一次磁盘读取。

2021 年春《操作系统》期末试卷

一、判断题（每题 1 分，共 10 分）

二、单项选择题（每题 2 分，共 20 分）

1. 用户态事件

2. 线程共享

3. read 系统调用

4. 磁盘调度

5. 页面置换

6. 记录式文件

7. 多进程操作系统

8. 缓冲技术

9. 实时操作系统

10. 设备名

三、填空题（每空 1 分，共 10 分）

四、内存管理（共 15 分）

五、进程同步与互斥（共 15 分）

六、进程调度（共 10 分）

七、死锁（共 10 分）

八、文件系统（共 10 分）

评论

3. `read` 系统调用