这是本节的多页打印视图。点击此处打印.

操作系统

1: 存储管理
2: 进程管理
3: 死锁
4: CPU 调度

1 - 存储管理

1

以下哪种页面置换算法会受到 Belady 异常的影响？（）

正确答案：A

解释：

Belady 异常是指在特定场景下，增加物理内存页框数反而导致缺页中断次数增多的反直觉现象
该现象仅出现在 FIFO 页面置换算法中
其本质是 FIFO 的队列特性与工作集分布之间的矛盾
LRU 和 Optimal 算法则不会出现这种异常

2

磁盘中的交换空间（swap space）主要用于什么？（）

正确答案：B

解释：

交换分区主要用于存储进程数据
当物理内存不足时，操作系统会将部分内存数据转移到磁盘的交换空间中
这是虚拟内存管理的重要组成部分
更多细节可参考相关资料

3

增加计算机的 RAM 通常会提高性能，因为（）。

正确答案：C
当 RAM 更多时，物理内存中映射的虚拟页数会增加，因此发生的页面错误更少。
页面错误会导致性能下降，因为需要从二级存储设备加载页面。

4

某计算机系统支持 32 位虚拟地址和 32 位物理地址。由于虚拟地址空间与物理地址空间大小相同，操作系统设计者决定完全移除虚拟内存。以下哪一项是正确的？（）

正确答案：C
解析：
为了支持虚拟内存，需要内存管理单元（MMU）的特殊硬件支持。由于操作系统设计者决定完全移除虚拟内存，因此不再需要内存管理的硬件支持。

5

虚拟内存是（）。

正确答案：C

解析：

虚拟内存本质上是操作系统提供的一种逻辑内存抽象机制，其特点包括：

虚拟性：并非真实存在的物理存储设备，而是通过地址映射实现的逻辑扩展
容量扩展：通过将磁盘空间作为后备存储，突破物理内存容量限制
透明性：对应用程序而言，无需感知具体物理内存分布
分页/分段管理：采用请求调页/调段机制实现内存与外存的数据交换
因此选项 C 准确描述了虚拟内存的本质特征，而选项 B 混淆了物理主存与虚拟内存的概念。

6

页面错误发生在什么时刻？（）

正确答案：B

解释：

页面错误（Page Fault）是指当程序访问的页面不在物理内存中时触发的异常。
触发条件：
- 请求的页面已在虚拟地址空间中映射。
- 该页面当前未被加载到物理内存中。
此时操作系统会从磁盘（如交换分区或页文件）中读取所需页面并加载到内存中。

7

抖动现象发生在什么时候？（）

正确答案：B

抖动发生在系统中的进程所需内存超过可用内存时。如果进程没有“足够”的页面，页面错误率会非常高。这会导致：

CPU 利用率低
操作系统大部分时间用于磁盘交换

这种行为就叫做抖动现象。

8

一台计算机使用 46 位虚拟地址、32 位物理地址和三级分页页表组织。页表基址寄存器存储一级表（T1）的起始地址，该表恰好占用一个页面。每个 T1 条目存储二级表（T2）页面的起始地址。每个 T2 条目存储三级表（T3）页面的起始地址。每个 T3 条目存储 32 位的页表项（PTE）。该计算机使用的处理器具有 1MB 16 路组相联、虚拟索引物理标记的缓存，缓存块大小为 64 字节。这台计算机的页面大小是多少 KB？（）

正确答案：C

设页面大小为 $ x $ 位：

T1 表大小
$ \text{T1 大小} = 2^x $ 字节（因 T1 恰好占用一个页面）
T1 条目数
$ \text{条目数} = \frac{2^x}{4} $（每个 PTE 为 32 位即 4 字节）
$\Rightarrow$ 二级页表数量 = $ \frac{2^x}{4} $
二级页表总大小
$ \text{二级页表总大小} = \left( \frac{2^x}{4} \right) \times 2^x $
T2 条目数与三级页表数量
$ \text{T2 条目数} = \left( \frac{2^x}{4} \right)^2 $
$\Rightarrow$ 三级页表数量 = $ \left( \frac{2^x}{4} \right)^2 $
三级页表总大小
$ \text{三级页表总大小} = \left( \frac{2^x}{4} \right)^2 \times 2^x $
所有三级页表中的总页数
$ \text{总页数} = \left( \frac{2^x}{4} \right)^3 = 2^{3x - 6} $
虚拟内存页数
$ \text{虚拟内存页数} = \frac{2^{46}}{2^x} = 2^{46 - x} $
方程求解
$$ 2^{3x - 6} = 2^{46 - x} \Rightarrow 3x - 6 = 46 - x \Rightarrow 4x = 52 \Rightarrow x = 13 $$
页面大小计算
$ 2^{13} $ 字节 = 8 KB

9

考虑以下虚拟页面引用序列：1, 2, 3, 2, 4, 1, 3, 2, 4, 1。在一个运行于主存大小为 3 个页面帧（初始为空）的按需分页虚拟内存系统中。设 OPTIMAL、LRU 和 FIFO 分别表示对应页面置换策略下的页面错误次数。则（）。

正确答案：B

先进先出（FIFO）：操作系统通过队列维护内存中的所有页面，队首为最老的页面。当需要替换时选择队首页面移除。
最佳置换（OPTIMAL）：该算法替换未来最长不使用的页面。
最近最少使用（LRU）：该算法替换最近最久未使用的页面。

解答
虚拟页面引用序列为 1, 2, 3, 2, 4, 1, 3, 2, 4, 1，主存页面帧大小为 3。

FIFO：总页面错误数为 6
OPTIMAL：总页面错误数为 5
LRU：总页面错误数为 9

因此，OPTIMAL=5，FIFO=6，LRU=9，关系为 OPTIMAL < FIFO < LRU。选项（B）正确。

10

某计算机的页面错误服务时间为 10ms，平均内存访问时间为 20ns。若每 10⁶ 次内存访问会生成一次页面错误，则该内存的有效访问时间是多少？（）

正确答案：B

解析：

设定变量：
- 页面错误率 $ P = \frac{1}{10^6} $
- 页面错误服务时间 $ T_{\text{page}} = 10 \ \text{ms} = 10 \times 10^6 \ \text{ns} $
- 内存访问时间 $ T_{\text{mem}} = 20 \ \text{ns} $
有效访问时间公式：
$$ T_{\text{effective}} = P \times T_{\text{page}} + (1 - P) \times T_{\text{mem}} $$
代入计算：
$$ T_{\text{effective}} = \left(\frac{1}{10^6}\right) \times 10 \times 10^6 + \left(1 - \frac{1}{10^6}\right) \times 20 $$
$$ = 10 + 20 \times \left(1 - \frac{1}{10^6}\right) $$
$$ \approx 10 + 20 = 30 \ \text{ns} $$
结论： 有效访问时间约为 30 ns。

11

一个系统使用 FIFO 页面置换策略。它有 4 个页面帧，初始时没有加载任何页面。系统首先按某种顺序访问 100 个不同的页面，然后以相反的顺序再次访问相同的 100 个页面。总共会发生多少次缺页中断？（）

正确答案：A

解析：

首次访问阶段
- 系统访问 100 个全新页面，页面帧初始为空
- 每次访问均触发缺页中断（共 100 次）
逆序访问阶段
- 前 4 个页面（原序列末尾的 4 个页面）仍保留在页面帧中 → 无缺页中断
- 第 5 至第 100 个页面（共 96 次）：
  - 采用 FIFO 策略替换最老页面 → 每次访问均需替换 → 96 次缺页中断
总计
$100 \text{（首次）} + 96 \text{（逆序）} = 196$ 次缺页中断

12

页表中每个表项的必要内容是（）。

正确答案：B

解析

页框号 是页表项必须包含的核心内容，用于建立虚拟地址与物理地址的映射关系。
虚拟页号 通常作为页表的索引字段，其作用是定位页表项以获取对应的 页框号。
其他扩展信息（如访问权限）属于附加属性，非必要组成。
更详细的实现原理可参考操作系统内存管理章节。

13

与单级页表相比，多级页表在将虚拟地址转换为物理地址时更受真实系统的青睐，这是因为（）。

正确答案：B
页表的大小可能变得太大，无法容纳在连续的空间中。
参见此处。
这就是为什么通常将页表划分为多个层级的原因。

14

一个处理器使用 36 位物理地址和 32 位虚拟地址，页面帧大小为 4 KB。每个页表项的大小为 4 字节。虚拟到物理地址的转换使用三级页表，其中虚拟地址的使用方式如下：

位 30-31 用于索引一级页表
位 21-29 用于索引二级页表
位 12-20 用于索引三级页表
位 0-11 用作页内偏移

在一级、二级和三级页表的页表项中，分别需要多少位来寻址下一级页表（或页面帧）？（）

正确答案：D

解析

虚拟地址大小 = 32 位
物理地址大小 = 36 位
物理内存大小 = $2^{36}$ 字节
页面帧大小 = 4K 字节 = $2^{12}$ 字节
偏移量所需的位数（或访问页面帧内位置所需的位数）= 12。
访问物理内存帧所需的位数 = 36 - 12 = 24。
因此，在三级页表中，需要 24 位来访问一个条目。
虚拟地址的 9 位用于访问二级页表条目，且二级页表条目的大小为 4 字节。因此，二级页表的大小为 $(2^9)×4 = 2^{11}$ 字节。这意味着有 $(2^{36})/(2^{11})$ 个可能的位置可以存储此页表。因此，二级页表需要 25 位来寻址它。
同样地，一级页表需要 25 位来寻址它。

15

虚拟内存系统采用先进先出（FIFO）页面置换策略，并为进程分配固定数量的页框。考虑以下两个陈述：

P：增加分配给进程的页面框数量有时会提高页面错误率。
Q：某些程序不表现出局部性引用。

以下哪一项是正确的？（）

正确答案：B

解释

FIFO 算法特性

先进先出（FIFO）页面置换算法：
这是最简单的页面置换算法。操作系统通过队列维护内存中的所有页面，队首页面是最旧的页面。当需要替换页面时，选择队首页面进行移除。

贝拉迪异常（Belady’s Anomaly）

FIFO 算法存在 贝拉迪异常：
该现象表明，增加页面框数量可能导致页面错误率上升。

陈述分析

陈述 P
结论：正确
依据：FIFO 算法受贝拉迪异常影响，特定引用模式下增加页框数反而导致更多缺页中断。
陈述 Q
结论：正确
依据：局部性通常源于循环对数组等数据结构的索引访问。我们可编写无循环的程序，使其不具有局部性引用。

因果关系判定

尽管 P 和 Q 均正确，但 Q 并非 P 的原因。
贝拉迪异常的发生与特定的页面引用模式相关，而 Q 描述的是程序本身的特性，二者无直接因果关系。

16

一个进程被分配了 3 个页面帧。假设该进程的页面最初都不在内存中。进程产生以下页面引用序列（引用字符串）：1, 2, 1, 3, 7, 4, 5, 6, 3, 1。如果使用最佳页面置换策略，上述引用字符串会产生多少次页面错误？（）

正确答案：A

最佳页面置换策略会在发生页面错误时向前查看以确定替换哪个帧。

初始状态：所有页面不在内存
访问顺序：1 → 2 → 1 → 3 → 7 → 4 → 5 → 6 → 3 → 1

页面替换过程：

[1]  [2]  [3]   ← 初始加载（3次页面错误）
[1]  [2]  [3]   ← 访问1（命中）
[1]  [2]  [3]   ← 访问3（命中）
[1]  [2]  [7]   ← 替换3（预测3之后不再使用）→ 第4次页面错误
[1]  [2]  [4]   ← 替换7（预测7之后不再使用）→ 第5次页面错误
[1]  [5]  [4]   ← 替换2（预测2之后不再使用）→ 第6次页面错误
[6]  [5]  [4]   ← 替换1（预测1之后不再使用）→ 第7次页面错误

关键逻辑：
最佳置换算法选择未来最久不会被使用的页面进行替换。最终共发生 7 次页面错误，对应选项 A。

17

考虑上题中给出的数据。

最近最少使用（LRU）页面置换策略是对最优页面置换策略的一种实用近似。对于上述引用字符串，与最优页面置换策略相比，LRU 策略会产生多少额外的页面错误？（）

正确答案：C

LRU 置换策略：替换掉最近最久未使用的页面。

给定字符串： 1, 2, 1, 3, 7, 4, 5, 6, 3, 1

123 // 初始加载页面 1、2、3，发生 3 次页面错误
173 → 替换 7（页面 3 被移除）
473 → 替换 4（页面 1 被移除）
453 → 替换 5（页面 7 被移除）
456 → 替换 6（页面 3 被移除）
356 → 替换 3（页面 4 被移除）
316 → 替换 1（页面 5 被移除）

总计 9 次页面错误。

18

一台计算机有二十个物理页框，初始时包含编号为 101 到 120 的页面。现在一个程序按顺序访问编号为 1、2、…、100 的页面，并重复该访问序列三次。以下哪种页面置换策略与最优页面置换策略在该程序中经历的页面错误次数相同？（）

正确答案：D

最优页面置换算法会换出其下一次使用时间最远的页面。

在本题中，计算机有 20 个页框，初始时页框中装入了编号 101 到 120 的页面。然后程序按顺序访问编号 1 到 100 的页面，并重复该访问序列三次。

前 20 次对页面 1 到 20 的访问必然导致页面错误。当访问第 21 个页面时，再次发生页面错误。被换出的页面是 20 号页面，因为它的下一次使用时间最远。
当访问第 22 个页面时，21 号页面会被换出，因为它下一次使用时间最远。

在这种情况下，上述最优页面置换算法实际上等效于最近最多使用（MRU）策略：

第一轮迭代（1-100）：所有页面均不在页框中，前 20 个页面（1-20）依次装入 20 个页框，后续页面（21-100）每次访问都会替换第 20 个页框中的页面，因此页面错误次数为 100 次。
第二轮迭代（1-19）存在 | （20-99）不存在 | （100）存在：替换发生在第 19 个页框，页面错误次数为 100 - 19 - 1 = 80 次。
第三轮迭代（1-18）存在 | （19-98）不存在 | （99-100）存在：替换发生在第 18 个页框，页面错误次数为 100 - 18 - 2 = 80 次。
第四轮迭代（1-17）存在 | （17-97）不存在 | （98-100）存在：替换发生在第 17 个页框，页面错误次数为 100 - 17 - 3 = 80 次。

总页面错误次数：100 + 80 + 80 + 80 = 340 次。
同时，最近最多使用（MRU）策略也会在相同位置进行页面替换，因此产生的页面错误次数与最优算法相同。（假设给定的 101-120 页面无效或为空）

后进先出（LIFO）置换策略的行为与最优算法不同：

它会产生 343 次页面错误。从第 21 个页面开始，所有页面都替换到第 20 个页框中，因此每轮迭代的命中次数从第二轮开始减少到 19 次。
总页面错误次数：100 + 81 + 81 + 81 = 343 次。

19

考虑一个带有 TLB 的分页硬件。假设整个页表和所有页面都在物理内存中。搜索 TLB 需要 10 ms，访问物理内存需要 80 ms。如果 TLB 命中率为 0.6，则有效内存访问时间（以 ms 为单位）是（）。

正确答案：B

解释

TLB 基础概念

TLB（Translation Lookaside Buffer） 是页表的高速缓存，用于加速虚拟地址到物理地址的转换。
页表存储在物理内存中，记录虚拟地址与物理地址的映射关系。

TLB 命中与未命中场景

场景	时间组成
TLB 命中	`TLB_search_time + memory_access_time`
TLB 未命中	`TLB_search_time + 2 × memory_access_time`

有效访问时间（EAT）计算公式

EAT = 命中率 × (TLB 访问时间 + 内存访问时间) + (1 - 命中率) × (TLB 访问时间 + 2 × 内存访问时间)

具体数值代入

已知条件：

TLB 搜索时间 = 10 ms
内存访问时间 = 80 ms
TLB 命中率 = 0.6

计算过程：

$$ \begin{align*} \text{T}_{\text{eff}} &= 0.6 \times (10 + 80) + 0.4 \times (10 + 2 \times 80) \\ &= 0.6 \times 90 + 0.4 \times 170 \\ &= 54 + 68 \\ &= 122 \ \text{ms} \end{align*} $$

结论

因此，有效内存访问时间为 122 ms，对应选项 B。

20

当缓存命中时，读操作的内存访问时间为 1 ns，缓存未命中时为 5 ns；写操作命中缓存时为 2 ns，未命中时为 10 ns。执行一条指令序列包含 100 次指令获取操作、60 次内存操作数读取和 40 次内存操作数写入。缓存命中率为 0.9。执行该指令序列的平均内存访问时间（单位：ns）是（）。

正确答案：B

问题要求计算以下总时间除以总指令数：

100 次获取操作
60 次操作数读取
40 次内存操作数写入

总指令数 = 100 + 60 + 40 = 200

100 次获取操作耗时（获取=读取）
= 100 × ((0.9 × 1) + (0.1 × 5))
// 1 表示缓存命中时的读取时间

= 140 ns
// 0.9 为缓存命中率

60 次读取操作耗时 = 60 × ((0.9 × 1) + (0.1 × 5)) = 84 ns

40 次写入操作耗时 = 40 × ((0.9 × 2) + (0.1 × 10)) = 112 ns
// 2 和 10 分别表示缓存命中/未命中时的写入时间

200 次操作总耗时 = 140 + 84 + 112 = 336 ns

平均耗时 = 总耗时 ÷ 操作数 = 336 ÷ 200 = 1.68 ns

21

一个 CPU 生成 32 位虚拟地址。页面大小为 4 KB。处理器有一个可容纳 128 个页表项的转换后备缓冲器（TLB），并且是 4 路组相联的。TLB 标记的最小尺寸是（）。

正确答案：C

虚拟内存如果每次都需要通过在内存中查找关联物理页来翻译地址，效率会很低。解决方案是将最近的翻译缓存在一个转换后备缓冲器（TLB）中。TLB 包含固定数量的插槽，这些插槽包含页表项，用于将虚拟地址映射到物理地址。

解答

页面大小 = 4KB = 2¹² → 偏移量需要 12 位
CPU 生成 32 位虚拟地址 → 页框所需总位数 = 32 - 12 = 20 位
TLB 是 4 路组相联，总容量 128 个页表项（2⁷）→ 组数 = 2⁷ / 4 = 2⁵ → 需 5 位 寻址组
标记位数 = 20 - 5 = 15 位

选项 (C) 是正确答案。

22

在虚拟内存环境中，运行进程必须分配的最小页框数由以下哪项决定？（）

正确答案：A

虚拟内存管理包含两个核心任务：
- 页面替换策略：决定哪些页框被替换
- 页框分配策略：确定进程应分配的最小页框数
最小页框数的确定逻辑：
进程必须分配的绝对最小页框数取决于系统架构特性，具体体现为：
单条（机器）指令可能访问的页面数量决定了所需页框的下限
结论：
因此，影响最小页框数的关键因素是指令集架构，选项 (A) 为正确答案

23

考虑一个采用两级分页机制的系统，常规内存访问耗时 150 ns，处理页面错误需 8 ms。平均指令需要 100 ns 的 CPU 时间和两次内存访问。TLB 命中率为 90%，页面错误率为每 10000 条指令发生一次。求有效平均指令执行时间（）？

正确答案：D

请注意题目中页面错误率是每 10000 条指令发生一次页面错误。由于每条指令需要两次内存访问，因此计算平均指令执行时间时需要双倍的地址转换时间。当 TLB 未命中时，需要访问两次页表。假设 TLB 访问时间为 0。

因此：

计算公式分解：

平均 CPU 执行时间
= 100 ns
地址转换时间
- TLB 命中（90%）：无需访问页表 → 0
- TLB 未命中（10%）：需访问两级页表 → 2 × 150 ns = 300 ns
- 单次内存访问的地址转换时间：0.9 × 0 + 0.1 × 300 = 30 ns
- 两次内存访问总地址转换时间：2 × 30 = 60 ns
内存获取时间
- 每次内存访问耗时 150 ns
- 两次内存访问总时间：2 × 150 = 300 ns
页面错误时间
- 页面错误概率：1/10000
- 页面错误处理时间：8 ms = 8,000,000 ns
- 平均页面错误时间：(1/10000) × 8,000,000 = 800 ns

最终计算：

总时间 = 100 (CPU) + 60 (地址转换) + 300 (内存访问) + 800 (页面错误)
       = 1260 ns

24

在一个具有 32 位虚拟地址和 1 KB 页面大小的系统中，使用单级页表进行虚拟地址到物理地址的转换是不切实际的，因为（）。

正确答案：C

关键分析：
- 32 位地址空间意味着虚拟地址范围为 $2^{32}$ 字节（4 GB）。
- 每个页面大小为 1 KB（$2^{10}$ 字节），因此页表项数量为 $2^{32} / 2^{10} = 2^{22}$ 个。
- 假设每个页表项占用 4 字节，则总页表大小为 $2^{22} \times 4 = 16,777,216$ 字节（约 16 MB）。
- 单级页表需一次性分配如此大内存，对系统资源造成显著压力，导致内存开销过大。
对比其他选项：
- A/B 与页表设计无关，碎片问题主要由进程管理引起。
- D 中地址转换计算复杂度与页表层级无关，硬件可高效处理。
结论：单级页表因内存消耗过高而不适用于大地址空间场景。

25

与使用静态链接库相比，以下哪项不是使用共享动态链接库的优势（）？

正确答案：

C
参考静态库与动态库的差异：

静态库在编译时完成链接，生成的可执行文件包含完整的库代码
动态库在运行时按需加载，具有以下特点：
- 可执行文件体积更小（多个程序共享同一库）
- 支持库版本热更新（无需重新链接程序）
- 可能增加系统缺页率（因延迟加载机制）

程序启动速度方面，静态库由于已预先链接，通常比动态库稍快。因此选项 C 不属于动态库优势。

26

某处理器使用两级页表进行虚拟地址到物理地址的转换。两级页表均存储在主存中。虚拟地址和物理地址均为 32 位宽，内存按字节寻址。在虚拟地址到物理地址的转换中，虚拟地址的最高 10 位用作一级页表的索引，接下来的 10 位用作二级页表的索引，最低 12 位作为页内偏移。假设两级页表的页表项均为 4 字节宽。此外，处理器具有一个命中率为 96% 的转译后备缓冲器（TLB），用于缓存最近使用的虚拟页号和对应的物理页号。处理器还具有一个命中率为 90% 的物理地址缓存。主存访问时间为 10 ns，缓存访问时间为 1 ns，TLB 访问时间也为 1 ns。

假设不发生缺页中断，访问一个虚拟地址的平均时间大约为（保留小数点后一位）：（）

正确答案：D

可能的情况包括：

TLB 命中 & 缓存命中
- TLB 访问时间 (1 ns) + 缓存访问时间 (1 ns) = 2 ns
TLB 命中 & 缓存未命中
- TLB 访问时间 (1 ns) + 主存访问时间 (10 ns) = 11 ns
TLB 未命中 & 缓存命中
- TLB 访问时间 (1 ns) + 两级页表访问 (2×10 ns) + 缓存访问时间 (1 ns) = 22 ns
TLB 未命中 & 缓存未命中
- TLB 访问时间 (1 ns) + 两级页表访问 (2×10 ns) + 主存访问时间 (10 ns) = 31 ns

计算公式：

= 0.96 × 0.9 × 2   （TLB 命中 & 缓存命中）
+ 0.96 × 0.1 × 11  （TLB 命中 & 缓存未命中）
+ 0.04 × 0.9 × 22  （TLB 未命中 & 缓存命中）
+ 0.04 × 0.1 × 31  （TLB 未命中 & 缓存未命中）
= 3.8 ns ≈ 4 ns

为什么是 22 和 31？

22 ns：当 TLB 未命中时需访问 TLB (1 ns)，通过两级页表获取物理地址（2 次主存访问 × 10 ns），再从缓存中读取数据 (1 ns)，总计 $1 + 2 \times 10 + 1 = 22$ ns。
31 ns：当 TLB 未命中且缓存未命中时，需访问 TLB (1 ns)，通过两级页表获取物理地址（2 次主存访问 × 10 ns），再从主存读取数据 (10 ns)，总计 $1 + 2 \times 10 + 10 = 31$ ns。

27

一个处理器使用两级页表进行虚拟地址到物理地址的转换。两级页表均存储在主存中。虚拟地址和物理地址均为 32 位宽，内存按字节寻址。在地址转换时，虚拟地址的最高 10 位作为一级页表索引，接下来的 10 位作为二级页表索引，最低 12 位作为页内偏移。假设两级页表的页表项均为 4 字节宽。此外，处理器具有命中率为 96% 的转译后备缓冲器（TLB），缓存最近使用的虚拟页号与对应物理页号。处理器还具有命中率为 90% 的物理地址缓存。主存访问时间为 10ns，缓存访问时间为 1ns，TLB 访问时间也为 1ns。

假设某个进程的虚拟地址空间仅包含以下页面：从虚拟地址 0x00000000 开始的两个连续代码页，从虚拟地址 0x00400000 开始的两个连续数据页，以及从虚拟地址 0xFFFFF000 开始的一个栈页。该进程所需的页表存储空间大小为（）：

正确答案：C

给定地址的二进制分解如下：

32 位被分解为 10 位 (L2) | 10 位 (L1) | 12 位（偏移）

各页面起始地址的二进制表示：

第一个代码页：
0x00000000 = 0000 0000 00 | 00 0000 0000 | 0000 0000 0000

下一个代码页起始于
0x00001000 = 0000 0000 00 | 00 0000 0001 | 0000 0000 0000

第一个数据页：
0x00400000 = 0000 0000 01 | 00 0000 0000 | 0000 0000 0000

下一个数据页起始于
0x00401000 = 0000 0000 01 | 00 0000 0001 | 0000 0000 0000

唯一栈页：
0xFFFFF000 = 1111 1111 11 | 11 1111 1111 | 0000 0000 0000

页表结构分析：

二级页表：只需 1 个页表，包含以下 3 个不同条目：
- 0000 0000 00
- 0000 0000 01
- 1111 1111 11
一级页表：每个二级页表条目需对应 1 个一级页表，因此共需 3 个一级页表
总计：4 个页表（1 个二级 + 3 个一级）

页表存储空间计算：

每个页表大小 = 2^10 * 4B = 4KB（因为 L1/L2 索引各占 10 位）
总存储空间 = 4 个页表 × 4KB = 16KB

28

以下哪项不是一种存储形式？（）

正确答案：C

选项解析：

指令缓存 - 用于存储频繁使用的指令
指令寄存器 - CPU 控制单元的一部分，用于存储当前正在执行的指令
指令操作码 - 它是机器语言指令中指定要执行操作的部分
TLB - 用于存储虚拟内存到物理地址的最近转换，以加快访问速度

结论说明：
除了“指令操作码”以外，其余选项都是存储形式。因此，C 是正确答案。

29

最佳页面置换算法会选择（）的页面。

正确答案：B

最佳页面置换算法会选择未来最久才被访问的页面进行替换。例如，当需要换出页面时，如果有两个可选页面：

一个将在 5 秒后被使用
另一个将在 10 秒后被使用

则算法会优先换出 10 秒后才会被使用的页面。因此选项 B 正确。

30

动态链接可能导致安全问题的原因是（）。

正确答案：B

动态链接 和 动态库 不需要复制代码，只需在二进制文件中放置库的名称即可。实际链接发生在程序运行时，此时二进制文件和库都在内存中。动态库（运行时链接的库）的示例包括 Linux 中的 .so 和 Windows 中的 .dll。

在动态链接中，直到运行时才知道搜索动态库的路径。

31

以下哪项陈述是错误的？（）

正确答案：D

解析：

虚拟内存 不会直接减少 上下文切换的开销
上下文切换的开销主要与以下操作相关：
- 保存和恢复进程状态（如寄存器、页表等）
虚拟内存通过分页/分段机制 可能增加 这部分操作的复杂性
因此该选项描述错误

32

将程序各部分分配加载地址并调整代码和数据以反映所分配地址的过程称为（）

正确答案：C

重定位是链接器 - 加载器在将程序从外部存储复制到主存时执行的过程。其核心操作包括：

链接器通过搜索文件和库
用实际可用的内存地址替换库的符号引用

因此，选项 (C) 是正确答案。若发现上述内容存在疏漏或错误，欢迎在下方评论区指正。

33

考虑一台具有 64MB 物理内存和 32 位虚拟地址空间的机器。如果页面大小为 4KB，页表的大致大小是多少？（）

正确答案：C

依次计算如下指标：

物理地址空间 = 64MB = $2^{26}$ B
虚拟地址 = 32 位，因此虚拟地址空间 = $2^{32}$ B
页面大小 = 4KB = $2^{12}$ B
页数 = $\frac{2^{32}}{2^{12}} = 2^{20}$ 页
帧数 = $\frac{2^{26}}{2^{12}} = 2^{14}$ 帧

页表大小由页表项数量与每项大小决定：

$$ \text{页表大小} = 2^{20} \times 14\text{位} \approx 2^{20} \times 16\text{位} = 2^{20} \times 2\text{B} = 2\text{MB} $$

关键点：页表项需记录帧号（14 位）及控制位（如有效/无效标志），实际存储需向上取整至 16 位（即 2 字节）。最终页表大小为 $2^{20} \times 2\text{B} = 2\text{MB}$。

34

假设页面错误的平均服务时间为 10 ms，而内存访问需要 1 ms。那么 99.99% 的命中率会导致平均内存访问时间为多少？（）

正确答案：D

当发生页面请求时：

命中情况：若页面存在于内存中，仅需执行一次内存访问（1 ms）。
未命中情况：若页面不在内存中，需先经历页面错误服务时间（10 ms），再执行内存访问（1 ms）。

设：

命中率 $ p = 99.99% $
内存访问时间 $ t_1 = 1 \ \mu s $
页面错误服务时间 $ t_2 = 10 \ ms = 10{,}000 \ \mu s $

平均内存访问时间公式为：

$$ \text{平均时间} = p \cdot t_1 + (1 - p) \cdot (t_2 + t_1) $$

代入数值计算：

$$ = 0.9999 \cdot 1 + 0.0001 \cdot (10{,}000 + 1) \ = 0.9999 + 1.0001 \ = 1.9999 \ \mu s $$

35

考虑六个大小分别为 200 KB、400 KB、600 KB、500 KB、300 KB 和 250 KB 的内存分区（KB 表示千字节）。这些分区需要按顺序分配给四个大小分别为 357 KB、210 KB、468 KB 和 491 KB 的进程。如果使用最佳适配算法，哪些分区未被分配给任何进程？（）

正确答案：A

最佳适应算法会为新进程在足够大的分区中选择最小的块进行分配。因此内存块的分配顺序如下：

357 KB → 选择 400 KB 分区
210 KB → 选择 250 KB 分区
468 KB → 选择 500 KB 分区
491 KB → 选择 600 KB 分区

最终未被分配的分区为 200 KB 和 300 KB。

36

一个计算机系统实现 8 KB 的页面和 32 位的物理地址空间。每个页表项包含一个有效位、一个脏位、三个权限位以及翻译信息。如果进程的页表最大尺寸为 24 兆字节，则系统支持的虚拟地址长度是（）位。

正确答案：A

最大虚拟地址长度可通过计算页表项的最大数量来确定：

页表项大小计算
- 物理地址空间：32 位
- 页面大小：8 KB → 需 13 位偏移量（$2^{13} = 8192$）
- 物理帧号位数：$32 - 13 = 19$ 位
- 页表项总位数：1（有效位）+ 1（脏位）+ 3（权限位）+ 19（物理地址）= 24 位
页表项数量计算
- 页表最大尺寸：24 MB = $24 \times 2^{20}$ 字节
- 每个页表项大小：24 位 = 3 字节
- 页表项总数：$\frac{24 \times 2^{20}}{3} = 8 \times 2^{20} = 2^{23}$ 个
虚拟地址空间计算
- 虚拟地址空间 = 页表项数量 × 页面大小
- $2^{23} \times 8\text{KB} = 2^{23} \times 2^{13} = 2^{36}$ 字节
- 因此虚拟地址长度为 36 位

37

以下哪一项不是同一进程的线程所共享的？（）

正确答案：A

参考线程一节：

线程无法共享栈（用于维护函数调用）
因为其可能具有各自的函数调用序列

每个线程拥有独立的栈空间以支持不同的调用上下文，而地址空间、文件描述符表和消息队列为线程间共享资源。

38

考虑一个全相联缓存，共有 8 个缓存块（编号 0-7），并有以下内存块请求序列：

4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7

如果使用 LRU 替换策略，内存块 7 最终会存储在哪个缓存块中？（）

正确答案：B

缓存块数量 = 8。给定请求序列：4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7。

初始状态
缓存块从 0 到 7 依次为：4 3 25 8 19 6 16 35
（注：25 和 8 是最久未使用的，因此后续 16 和 35 进入缓存块）
处理过程
- 45 替换最久未使用的 19 → 45 3 25 8 19 6 16 35
- 22 替换最久未使用的 25 → 45 22 25 8 19 6 16 35
- 3 已存在，更新使用时间 → 45 22 25 8 3 6 16 35
- 16 和 25 已存在，更新使用时间
最终状态
处理完所有请求后：45 22 25 8 3 7 16 35
内存块 7 位于第 5 个缓存块（索引从 0 开始计数）

因此，答案是 B

39

在某个特定的 Unix 操作系统中，每个数据块大小为 1024 字节。每个节点包含 10 个直接数据块地址和三个额外地址：一个用于单级间接块，一个用于双级间接块，一个用于三级间接块。此外，每个块可以容纳 128 个块的地址。以下哪一项最接近该文件系统的最大文件大小？（）

正确答案：B

解析：

基本参数
- 数据块大小 = 1024 字节
- 单个块可存储地址数 = 128

各类型地址对应容量

直接地址：10 × 1024 B  
单级间接：128 × 1024 B  
双级间接：128² × 1024 B  
三级间接：128³ × 1024 B

总容量计算

总容量 = (10 + 128 + 128² + 128³) × 1024
       = (10 + 128 + 16384 + 2097152) × 1024
       = 2113674 × 1024 B
       ≈ 2.0157 GB ≈ 2 GB

结论
最接近的选项为 2GB

40

一个磁盘有 200 个磁道（编号 0 到 199）。在某一时刻，它正在处理从第 120 号磁道读取数据的请求，而上一次服务的请求是针对第 90 号磁道。当前待处理的请求（按到达顺序）为：

30、70、115、130、110、80、20、25。

对于磁盘调度策略 SSTF（最短寻道时间优先）和 FCFS（先来先服务），磁头将改变方向多少次？（）

正确答案：C

SSTF 算法分析

调度路径：90→120→115→110→130→80→70→30→25→20
方向变化：
- 120→115（下降）
- 110→130（上升）
- 130→80（下降）

FCFS 算法分析

调度路径：90→120→30→70→115→130→110→80→20→25
方向变化：
- 120→30（下降）
- 30→70（上升）
- 130→110（下降）
- 20→25（上升）

因此，SSTF 有 3 次方向变化，FCFS 有 4 次方向变化，最终答案为 C。

41

在一个虚拟内存系统中，虚拟地址大小为 32 位，物理地址大小为 30 位，页面大小为 4 KB，每个页表项的大小为 32 位。主存按字节寻址。以下哪一项是每个页表项中可用于存储保护和其他信息的最大位数？（）

正确答案：D

虚拟地址空间：2³² 字节
物理地址空间：2³⁰ 字节
页面/帧大小：4 KB = 2¹² 字节
物理帧数量：2³⁰ ÷ 2¹² = 2¹⁸ → 需 18 位表示帧号
页表项结构：32 位总长度 = 帧号 (18 位) + 其他信息 (14 位)

因此，页表项中最多可分配 14 位 用于存储保护标志等附加信息。

42

考虑一个具有 4 组、总共 8 个高速缓存块（编号 0-7）的 2 路组相联高速缓存，主内存有 128 个块（编号 0-127）。如果采用 LRU（最近最少使用）策略进行高速缓存块替换，且初始时高速缓存中没有当前任务的任何内存块，请问在以下内存块引用序列后，高速缓存中会包含哪些内存块？

引用序列为：0 5 3 9 7 0 16 55

正确答案：C

这是一个 2 路组相联高速缓存，即 K=2。

高速缓存中的组数为 4（S=4，编号 0-3），总共有 8 个块（N=8，编号 0-7），每组包含 2 个块。

主内存有 128 个块（M=128，编号 0-127）。当引用主内存块 X 时，它会被放置到高速缓存中编号为 (X mod S) 的组内。该组内的任意位置均可存放，但如果组已满，则需根据替换策略（此处为 LRU）替换掉最久未使用的块。具体过程如下：

替换步骤解析

引用块与对应组的关系（X→组号=X mod 4）

0→0：组 0 有两个空位，块 0 可放入任一位置。
5→1：组 1 有两个空位，块 5 可放入任一位置。
3→3：组 3 有两个空位，块 3 可放入任一位置。
9→1：组 1 剩余一个空位，块 9 放入该位置 → 组 1 已满（块 5 成为 LRU 候选）。
7→3：组 3 剩余一个空位，块 7 放入该位置 → 组 3 已满（块 3 成为 LRU 候选）。
0→0：块 0 已在高速缓存中（组 0），无需操作。
16→0：组 0 已满 → 根据 LRU 策略替换最久未使用的块 0 → 新增块 16。
55→3：组 3 已满（块 3 和 7）→ 根据 LRU 策略替换最久未使用的块 3 → 新增块 55。

最终状态

高速缓存中保留的主内存块为：
0, 5, 7, 9, 16, 55
（注：块 3 被块 55 替换，因此不在最终结果中）

43

考虑一个具有 40 位虚拟地址和 16KB 页面大小的计算机系统。如果该系统为每个进程使用一级页表，且每个页表项需要 48 位，则每个进程的页表大小为（）MB。

正确答案：A

虚拟地址空间大小：$2^{40}$ 字节
页面大小：$16\text{KB} = 2^{14}$ 字节
页表项数量：$\frac{2^{40}}{2^{14}} = 2^{26}$ 个
单个页表项大小：$\frac{48}{8} = 6$ 字节
总页表大小：$2^{26} \times 6$ 字节
转换为兆字节（MB）： $$ \frac{2^{26} \times 6}{2^{20}} = 6 \times 2^6 = 6 \times 64 = 384\text{MB} $$

因此，选项 A 是正确答案。

44

考虑一个具有十个物理页框的计算机系统。该系统提供了一个访问序列（a₁, a₂, …, a₂₀, a₁, a₂, …, a₂₀），其中每个 aᵢ 为数字。最后进先出（LIFO）页面置换策略与最佳（Optimal）页面置换策略在缺页中断次数上的差值是（）。

正确答案：B

LIFO 策略分析：

第一轮访问 a₁-a₁₀：由于初始无缓存，全部产生缺页中断，共 10 次。
第二轮访问 a₁₁-a₂₀：每次访问均替换最新加载的页框（遵循 LIFO 原则），因此 a₁₁-a₂₀ 再次产生 10 次缺页中断。
第三轮访问 a₁-a₉：这些页已存在于物理页框中，无需中断。
第四轮访问 a₁₀-a₂₀：从 a₁₀ 开始逐个替换栈顶页框，直到 a₂₀，共产生 11 次缺页中断。

总缺页中断次数：10 + 10 + 11 = 31

Optimal 策略分析：

第一轮访问 a₁-a₁₀：同样产生 10 次缺页中断。
第二轮访问 a₁₁-a₂₀：每次选择未来最久未使用的页框进行替换（a₁₀-a₁₉ 各自后续不再被使用），因此 a₁₁-a₂₀ 产生 10 次缺页中断。
第三轮访问 a₁-a₉：页已存在，无需中断。
第四轮访问 a₁₀-a₁₉：每次替换未来最久未使用的页框（如 a₁ 替换 a₁₀），共产生 10 次缺页中断。
最终访问 a₂₀：页已存在，无需中断。

总缺页中断次数：10 + 10 + 10 = 30

差值计算：
LIFO 缺页中断数 (31) - Optimal 缺页中断数 (30) = 1

45

下列左侧列出了一些操作系统抽象概念，右侧列出了它们所抽象的硬件组件或机制。以下哪一组配对是正确的？（）


A. 线程	1. 中断
B. 虚拟地址空间	2. 内存
C. 文件系统	3. CPU
D. 信号	4. 磁盘

正确答案：C

线程：由 CPU 调度执行的基本单元
虚拟地址空间：通过内存管理机制实现的进程地址映射
文件系统：提供对磁盘存储设备的逻辑访问接口
信号：属于中断机制的一种软件级实现形式

各选项对应关系如下：

A-3（线程→CPU）
B-2（虚拟地址空间→内存）
C-4（文件系统→磁盘）
D-1（信号→中断）

46

分页系统使用了一个转换后备缓冲器（TLB）。TLB 访问需要 10 ns，主存访问需要 50 ns。如果 TLB 命中率为 90%，且没有页面故障，那么有效访问时间（以 ns 为单位）是多少？（）

正确答案：C

有效访问时间 = 命中率 × 命中时的时间 + 未命中率 × 未命中时的时间

参数定义
- TLB 访问时间：10 ns
- 主存访问时间：50 ns
- TLB 命中率：90%
计算逻辑
1. 命中场景（90% 概率）：
  需要访问 TLB（10 ns） + 访问主存（50 ns） → 总耗时 10 + 50 = 60 ns
2. 未命中场景（10% 概率）：
  访问 TLB（10 ns） + 访问主存（50 ns） + 再次访问主存（50 ns） → 总耗时 10 + 50 + 50 = 110 ns
最终公式代入
$$ \text{有效访问时间} = 0.90 \times 60\text{ns} + 0.10 \times 110\text{ns} = 65\text{ns} $$

47

假设主存初始为空，仅包含 4 个页面，每个页面大小为 16 字节。CPU 生成以下虚拟地址序列，并采用 最近最少使用（LRU）页面置换策略：0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92

该序列会导致多少次页面错误？最终主存中保留的页面编号是什么？（）

正确答案：B

页面划分
每个页面大小为 16 字节，因此虚拟地址对应的页面号为 地址 // 16。
- 地址序列转换为页面号：
  - 0 → 0
  - 4 → 0
  - 8 → 0
  - 20 → 1
  - 24 → 1
  - 36 → 2
  - 44 → 2
  - 12 → 0
  - 68 → 4
  - 72 → 4
  - 80 → 5
  - 84 → 5
  - 28 → 1
  - 32 → 2
  - 88 → 5
  - 92 → 5
模拟过程（主存容量为 4 页，采用 LRU 策略）：
- 初始状态：空
- 访问 0（页面 0）→ 缺页（当前页面：[0]）
- 访问 4（页面 0）→ 命中
- 访问 8（页面 0）→ 命中
- 访问 20（页面 1）→ 缺页（[0,1]）
- 访问 24（页面 1）→ 命中
- 访问 36（页面 2）→ 缺页（[0,1,2]）
- 访问 44（页面 2）→ 命中
- 访问 12（页面 0）→ 命中
- 访问 68（页面 4）→ 缺页（[0,1,2,4]）
- 访问 72（页面 4）→ 命中
- 访问 80（页面 5）→ 缺页（替换最久未使用的页面 0 → [1,2,4,5]）
- 访问 84（页面 5）→ 命中
- 访问 28（页面 1）→ 命中
- 访问 32（页面 2）→ 命中
- 访问 88（页面 5）→ 命中
- 访问 92（页面 5）→ 命中
统计结果
共发生 7 次页面错误，最终主存中的页面为 1, 2, 4, 5。

48

将以下左侧虚拟内存管理中使用的标志位与下表右侧的不同用途进行匹配（）。

位名称	功能
I. Dirty	a. 标记页面是否有效
II. R/W	b. 写回策略
III. Reference	c. 页面保护
IV. Valid	d. 页面替换策略

正确答案：D

解析

各标志位功能说明

脏位
标记页面是否被修改过。当需要替换页面时，若该位为 1 则需写回磁盘（用于写回策略）。
读/写位（R/W）
控制页面访问权限，决定是否允许写入操作（用于页面保护）。
引用位
记录页面是否被访问过，辅助页面置换算法判断哪些页面最近未被使用（用于页面置换策略）。
有效位
标识页面是否已加载到主存。若为 0 表示页面不在内存中，触发缺页中断（即页面初始化过程）。

正确答案依据

选项 D 的匹配关系（I-b, II-c, III-d, IV-a）准确反映了上述标志位与功能的对应逻辑。

49

假设我在虚拟内存中实现了新的页面置换算法叫做 Geek 算法，该算法的工作策略如下：

内存中的每个页面维护一个计数器，当页面被引用且未发生缺页中断时，该计数器递增。
如果发生缺页中断，则用新页面替换物理页面中计数为零或最小的页面；若存在多个计数为零或最小的页面，则使用 FIFO 策略进行替换。

请计算使用该算法处理以下参考字符串时发生的缺页中断次数（假设初始有三个空闲的物理页框）：
A B C D A B E A B C D E B A D

正确答案：C

根据算法规则逐步分析参考字符串：

A → 缺页（0 次命中）
当前页框：[A]
计数器：{A:1}
B → 缺页
页框：[A,B]
计数器：{A:1, B:1}
C → 缺页
页框：[A,B,C]
计数器：{A:1, B:1, C:1}
D → 缺页（页框已满）
- 替换条件：计数最小的页面（A/B/C 均计数 1）
- FIFO 策略：替换最早加入的 A
  页框：[D,B,C]
  计数器：{D:1, B:1, C:1}
A → 缺页
- 替换条件：D/B/C 均计数 1
- FIFO 策略：替换 D
  页框：[A,B,C]
  计数器：{A:1, B:1, C:1}
B → 命中
- B 计数 +1 → {A:1, B:2, C:1}
E → 缺页
- 替换条件：A/C 均计数 1
- FIFO 策略：替换 A
  页框：[E,B,C]
  计数器：{E:1, B:2, C:1}
A → 缺页
- 替换条件：E/C 均计数 1
- FIFO 策略：替换 E
  页框：[A,B,C]
  计数器：{A:1, B:2, C:1}
B → 命中
- B 计数 +1 → {A:1, B:3, C:1}
C → 命中
- C 计数 +1 → {A:1, B:3, C:2}
D → 缺页
- 替换条件：A 计数 1
  页框：[D,B,C]
  计数器：{D:1, B:3, C:2}
E → 缺页
- 替换条件：D 计数 1
  页框：[E,B,C]
  计数器：{E:1, B:3, C:2}
B → 命中
- B 计数 +1 → {E:1, B:4, C:2}
A → 缺页
- 替换条件：E 计数 1
  页框：[A,B,C]
  计数器：{A:1, B:4, C:2}
D → 缺页
- 替换条件：A 计数 1
  页框：[D,B,C]
  计数器：{D:1, B:4, C:2}

总计发生 11 次缺页中断，对应选项 C。

50

无法在不支持以下功能的硬件上实现多用户、多处理操作系统（）：

a) 地址转换
b) 磁盘传输的直接内存存取（DMA）
c) 至少两种 CPU 执行模式（特权和非特权）
d) 请求分页

正确答案：C

正确答案应为 (a) 和 (c)，因为：

地址转换是多道程序设计所必需的，以确保进程不能访问其他进程的内存。
CPU 执行模式至少需要两种（特权和非特权），以便特权模式能够控制非特权模式用户的资源分配。

DMA 和请求分页虽然提高了操作系统的性能，但并非多道程序设计的必要条件。由于选项中未单独列出 (a) 和 (c)，因此最佳选择是包含这两项的选项 (C)。
所以，选项 (C) 是正确的。

51

以下哪些选项是虚拟内存的优势（）？

a) 平均而言，内存访问速度更快。
b) 可以为进程提供受保护的地址空间。
c) 链接器可以分配与程序在物理内存中加载位置无关的地址。
d) 可以运行大于物理内存大小的程序。

正确答案：C

解析：

A 选项错误：页面交换会增加时间开销，而虚拟内存的概念相比直接访问物理内存会减慢执行速度。
B 选项正确：没有虚拟内存时，进程直接访问物理内存，难以实现受保护的地址空间。
C 选项错误：可以通过其他方法独立于程序加载位置分配地址。
D 选项正确：虚拟内存允许进程使用比物理内存地址空间更大的虚拟地址空间，并在物理内存满时在物理内存和虚拟内存之间交换页面。

结论：
(b) 和 (d) 是正确的陈述。

52

可以使用自由链表或位图来跟踪磁盘空闲空间。磁盘地址需要 $d$ 位。对于一个包含 13 个块的磁盘，其中有 $F$ 个是空闲的，请说明在什么条件下自由链表占用的空间比位图更少（）？

53

局部性原理意味着进程所进行的页面引用（）。

正确答案：

B
解释：

局部性原理包含 时间局部性 和 空间局部性 两种形式
时间局部性 表明程序倾向于重复访问最近访问过的数据或指令（如循环结构）
空间局部性 表明程序倾向于访问相邻的存储位置（如数组遍历）
因此，选项 B 正确描述了这种概率性的访问模式
其他选项均存在绝对化表述（如“始终”），与局部性原理的实际特性不符

54

抖动（Thrashing）带来的结果是（）。

正确答案：C

解析

抖动是指进程频繁地进行页面置换操作的现象
当系统发生抖动时，进程的页面频繁调入调出内存
这会导致大量的页面 I/O 操作，显著降低系统效率
因此"意味着过多的页面 I/O"是抖动最直接的表现特征

55

页表中某页面的脏位的功能是（）。

正确答案：A

功能说明：脏位用于判断当某个页面被修改后需要替换时，是否需要执行写回操作
工作原理：通过脏位可以确定是否需要将修改后的数据写回磁盘或保留原状
结论：因此，页表中页面的脏位能够避免在分页设备上进行不必要的写入操作

56

以下哪个选项是错误的？（）

正确答案：A

解析

外部碎片：指系统中存在足够分散的小空闲内存区域，但它们无法满足当前请求的连续内存需求（即空间不连续）
内部碎片：指已分配内存块中未被使用的部分，通常由于分配单元大于实际需求所致
分页机制特性：
- 不会产生外部碎片（通过固定大小页框实现）
- 可能存在内部碎片（最后一页可能未填满）
分段机制特性：
- 可能产生外部碎片（各段大小不一导致空闲区难以利用）

选项 A 的描述将内外碎片定义完全颠倒，因此是错误的。

57

考虑一个在按需分配内存页面的操作系统上运行的进程。如果对应的内存页在内存中可用，系统的平均内存访问时间为 M 单位；如果内存访问导致页面错误，则平均时间为 D 单位。实验测量显示该进程的平均内存访问时间为 X 单位。以下哪一个是该进程经历的页面错误率的正确表达式？

正确答案：B

平均内存访问时间 = （1 - 页面错误率） × 内存无页面错误时的访问时间 + 页面错误率 × 内存有页面错误时的访问时间。公式推导：

$$X = (1 - p)M + pD$$

$$X = M + p(D - M)$$

$$p = \frac{X - M}{D - M}$$

58

以下哪项关于虚拟内存的说法是不正确的（）？

正确答案：B

选项分析：
- A: 正确。虚拟内存允许程序使用比物理内存更大的地址空间，从而支持编写大型程序。
- B: 错误。虚拟内存通过分页机制减少不必要的 I/O 操作，而非增加。此选项描述与实际相反。
- C: 正确。虚拟内存技术扩展了可用的可寻址内存空间。
- D: 正确。页面置换算法优化了进程切换效率，使交换过程更高效。
结论：
因此，选项 B 的说法不正确，正确答案为 B。

59

一个内存管理系统有 64 个页面，每个页面大小为 512 字节。物理内存包含 32 个页框。逻辑地址和物理地址分别需要多少位？（）

正确答案：C

虚拟地址计算
虚拟内存空间 = 页面数量 × 页面大小 = 64 × 512 B = $2^6 \times 2^9$ B = $2^{15}$ B
需要 15 位表示逻辑地址
物理地址计算
物理内存空间 = 页框数量 × 页框大小 = 32 × 512 B = $2^5 \times 2^9$ B = $2^{14}$ B
需要 14 位表示物理地址

因此，逻辑地址需 15 位，物理地址需 14 位，选项 C 正确。

60

在分段方案中考虑以下段表：

SegmentID	Base	Limit
0	200	200
1	500	12510
2	1527	498
3	2500	50

当请求的逻辑地址为段号 2 且偏移量为 1000 时会发生什么？（）

正确答案：B

解析：

段 2 的基地址 = 1527
段 2 的限长 = 498
可访问的有效地址范围：1527 至 1527 + 498 = 2025
请求的偏移量 1000 对应的物理地址：1527 + 1000 = 2527
由于 2527 > 2025，该访问超出了段 2 的合法范围
因此操作系统会触发 分段错误陷阱（Segmentation Fault Trap）

61

使用下图所示的页表，将物理地址 25 转换为虚拟地址。地址长度为 16 位，页面大小为 2048 字，物理内存大小为四个页框。

Page	Present(1-In 0-out)	Frame
0	1	3
1	1	2
2	1	0
3	0	-

正确答案：(D)

已知虚拟地址长度为 16 位，页面大小为 2¹¹字节。因此：

页面数量 = 2¹⁶ / 2¹¹ = 2⁵
物理地址 = （页框数） × （每个页框大小） = 4 × 2¹¹ = 2¹³

物理地址 25₁₀ = 13 位二进制表示为 (0000000011001)₂
其中前两位表示页框号，后 11 位表示页内偏移量：(00 00000011001)₂

根据页表：

帧号 00 映射到页号 2
页号 2 = (00010)₂
页内偏移量 = (00000011001)₂

因此，16 位虚拟地址 = (00010 00000011001)₂ = 4121₁₀

选项 D 正确。

62

一台计算机有 16 页的虚拟地址空间，但主存大小只有 4 个帧。初始时内存为空。一个程序按顺序引用虚拟页面 0、2、4、5、2、4、3、11、2、10。如果使用 LRU 页面置换算法，会发生多少次页面错误？（）

正确答案：C

解析：

初始状态
内存为空，可用帧数 4 个。

页面引用序列分析
按顺序处理每个页面请求，记录内存状态及页面错误：

步骤	访问页面	内存状态（当前帧）	是否页面错误	替换页面
1	0	[0]	是	-
2	2	[0, 2]	是	-
3	4	[0, 2, 4]	是	-
4	5	[0, 2, 4, 5]	是	-
5	2	[0, 2, 4, 5]	否	-
6	4	[0, 2, 4, 5]	否	-
7	3	[0, 2, 3, 5]	是	4（LRU）
8	11	[0, 2, 3, 11]	是	5（LRU）
9	2	[0, 2, 3, 11]	否	-
10	10	[0, 2, 3, 10]	是	11（LRU）

关键逻辑
- 页面错误条件：目标页面不在内存中。
- LRU 策略：当内存满时，移除最近最久未被访问的页面。
- 替换规则：每次页面错误后，选择时间戳最早的页面替换。
统计结果
共发生 7 次页面错误（步骤 1-4、7-8、10）。

63

以下哪项/哪些可能是导致系统抖动的原因（）？

正确答案：B

当多道程序度持续增加时，由于每个进程的内存空间不足，会导致缺页次数增加，而进程执行几乎无法推进。这种情况称为抖动。

结论：选项 (B) 是正确答案
解析：
抖动现象主要由内存资源过度分配引发。当系统中运行的程序过多（选项 B），每个进程可分配的物理页数减少，导致频繁的页面置换和缺页中断，最终形成"抖动"。
页面大小过小（选项 A）虽然会增加页表开销，但不会直接导致抖动；LRU/FIFO（选项 C/D）是常见的页面置换算法，其选择与抖动无直接因果关系。

64

考虑一个由 8 页组成、每页 1024 字的逻辑地址空间，映射到有 32 帧的物理内存。物理地址和逻辑地址各有多少位？（）

正确答案：C

逻辑地址计算
- 页号字段位数：$\log_2 8 = 3$ 位
- 偏移量位数：$\log_2 1024 = 10$ 位
- 总位数：3 + 10 = 13 位
物理地址计算
- 帧号字段位数：$\log_2 32 = 5$ 位
- 偏移量位数：$\log_2 1024 = 10$ 位
- 总位数：5 + 10 = 15 位

选项 C 正确。

65

设 Pi 和 Pj 是两个进程，R 表示从内存中读取的变量集合，W 表示写入内存的变量集合。对于这两个进程的并发执行，以下哪项条件 不成立？（）

正确答案：C

关键分析：
- 当两个进程同时读取同一变量（R(Pi) ∩ R(Pj) ≠ Ф）时，并发执行不会导致冲突。
- 因此选项 C 的条件“R(Pi) ∩ R(Pj) = Ф”并非必须满足的条件。
- 其他选项（A、B、D）描述的互斥关系是保证并发安全性的必要条件。

66

如果在 32 位机器中页面大小为 4K 字节，则页表的大小是（）

正确答案：C

解析过程：

物理地址大小：32 位
逻辑地址大小：32 位
页面大小：4KB = $2^{12}$ B

步骤 1：计算页面数量

$$ \text{页面数量} = \frac{\text{逻辑地址空间}}{\text{页面大小}} = \frac{2^{32}}{2^{12}} = 2^{20} $$

步骤 2：计算页表大小

页表项大小：32 位系统中每个页表项占 4 字节（$2^2$ B） $$ \text{页表大小} = \text{页面数量} \times \text{页表项大小} = 2^{20} \times 2^2 = 2^{22} \ \text{B} = 4 \ \text{MB} $$

结论：选项 (C) 正确。

67

考虑一个使用四级页表的 32 位机器。如果 TLB 命中率为 98%，搜索 TLB 需要 20 ns，访问主存需要 100 ns，那么有效内存访问时间是多少 ns（）？

正确答案：B

对于四级页表方案，有效内存访问时间（EAT）计算公式为：
$$ \text{EAT} = H_{\text{TLB}} \times T_{\text{TLB}} + (1 - H_{\text{TLB}})[T_{\text{TLB}} + 4 \times T_m] + T_m $$

其中：

$ H_{\text{TLB}} $：TLB 命中率
$ T_{\text{TLB}} $：TLB 搜索时间
$ T_m $：内存访问时间

计算步骤：

代入已知参数：
- $ H_{\text{TLB}} = 0.98 $
- $ T_{\text{TLB}} = 20 \ \text{ns} $
- $ T_m = 100 \ \text{ns} $
代入公式计算： $$ \begin{align*} \text{EAT} &= (0.98 \times 20) + 0.02(20 + 4 \times 100) + 100 \\ &= 19.6 + 0.02(20 + 400) + 100 \\ &= 19.6 + 8.4 + 100 \\ &= 128 \ \text{ns} \end{align*} $$

选项 (B) 正确。

68

下面关于页面错误（Page Fault）的说法正确的是（）

正确答案：D

触发机制：
- 当在缓存中找不到目标页面时，系统会查询主存
- 若主存中同样缺失该页面，则触发页面错误
处理流程：
1. 执行页面错误服务例程
2. 从磁盘调入所需页面至内存
3. 更新页表以反映最新映射关系

因此，选项 (D) 正确。

69

临界区是一个程序段（）

正确答案：C

关键概念：临界区是指在并发编程中需要被保护的代码区域
核心作用：用于管理对共享资源的互斥访问
技术原理：
- 多线程/进程环境下，共享资源的并发访问可能引发数据竞争
- 通过同步机制（如信号量）确保同一时刻只有一个执行流进入临界区
- 典型应用场景包括文件操作、内存共享等需要原子性保障的场景

因此，选项 C 正确。

70

考虑一个小型的 2 路组相联高速缓存，包含四个块。在选择替换块时，使用最近最少使用（LRU）策略。对于以下块地址序列 8、12、0、12、8，缓存未命中的次数是（）：

正确答案：C

解析：

初始状态：缓存为空。
访问块 8：未命中，缓存中加入块 8。
访问块 12：未命中，缓存中加入块 12。
访问块 0：未命中，缓存已满，根据 LRU 策略替换最早使用的块 8，缓存更新为 [0, 12]。
再次访问块 12：命中，更新 LRU 状态（12 变为最近使用的块）。
再次访问块 8：未命中，缓存中无块 8，根据 LRU 策略替换最早使用的块 0，缓存更新为 [8, 12]。

总结：
未命中发生在第 1、2、3、5 次访问，共 4 次未命中。

71

在分页内存中，页面命中率为 0.40。访问辅存中页面所需时间为 120 ns，访问主存中页面所需时间为 15 ns。访问页面所需的平均时间是（）。

正确答案：D

计算公式
平均访问时间 = 命中率 × 主存访问时间 + （1 - 命中率） × 辅存访问时间
代入数值
$$ \text{平均访问时间} = 0.4 \times 15 + 0.6 \times 120 $$
分步计算
$$ = 6 + 72 $$
最终结果 $$ = 78\ \text{ns} $$

因此，选项 D 正确。

72

以下哪些陈述是正确的？（）

(a) 当有足够的总内存空间满足请求但可用空间 不连续 时，存在外部碎片。

(b) 内存碎片可以是内部的也可以是外部的。

Code:

正确答案：C

关于 (a)：该陈述描述的是外部碎片的定义本身。当系统有足够总内存但无法找到连续可用空间时，必然存在外部碎片。因此 (a) 的表述是错误的，因为它将外部碎片的存在条件与结果混淆了。
关于 (b)：内存碎片确实分为内部碎片（分配单元未被完全利用）和外部碎片（分散的小空闲区），因此 (b) 正确。
关于 (c)：通过压缩技术（如移动进程位置）可以合并外部碎片，这是解决外部碎片的有效方法之一，因此 (c) 正确。

综上，正确答案为 仅 (b) 和 (c)，对应选项 (C)。

73

内存中的页面信息也称为页表。页表中每个条目的基本内容是（）。

正确答案：C

解析

页表的核心功能是实现虚拟地址到物理地址的映射。每个页表项存储的是页框号（Page Frame Number, PFN），用于与虚拟页号组合形成完整的物理地址。
页表项通常包含以下字段：

有效位（Valid Bit）：标记该页是否已加载到内存
页框号（Page Frame Number）：物理内存中对应页框的编号
访问权限（Protection Bits）：控制读/写/执行权限
修改位（Dirty Bit）：记录页面是否被修改过
引用位（Reference Bit）：记录页面是否被访问过

因此，页表中每个条目的基本内容是页框号，其他信息属于附加属性而非核心内容。

74

考虑为新进程分配内存。假设内存中现有的所有碎片都无法完全满足该进程的内存需求。因此，无论在哪个现有碎片中进行分配，都会产生一个更小的新碎片。以下哪一项陈述是正确的？（）

正确答案：C

A 如果首次适应分区的大小小于下次适应分区的大小，可能不成立。
B 如果最差适应和首次适应位于同一分区，可能不成立。
C 始终正确，因为最佳适应算法始终产生最小的碎片。
D 完全错误。

75

考虑一个使用一级页表的分页系统，该页表驻留在主存中，并通过 TLB（转换后备缓冲器）进行地址转换。每次主存访问需要 100 ns（ns），TLB 查找需要 20 ns。每次页面在磁盘与主存之间的传输需要 5000 ns。假设 TLB 命中率为 95%，缺页率是 10%。假设在所有缺页中，有 20% 的情况需要先将脏页写回磁盘，然后再从磁盘读取所需页面。忽略 TLB 更新时间。

平均内存访问时间（单位：ns，四舍五入到小数点后一位）是多少？（）

正确答案：A

已知以下信息：

M = 100 ns
T = 20 ns
D = 5000 ns
h = 0.95
p = 0.1
d = 0.2

计算公式推导
平均内存访问时间由三部分组成：

TLB 命中时：直接访问 TLB（20ns） + 主存访问（100ns）
TLB 未命中但无缺页：需两次主存访问（页表查询 + 数据访问）
TLB 未命中且发生缺页：
- 80% 情况：仅读取页面（5000ns + 100ns）
- 20% 情况：先写回脏页（5000ns）再读取（5000ns + 100ns）

完整公式如下：

$$ \begin{align*} &= h \times (T + M) \\ &\quad + (1 - h)\left[(1 - p) \times 2M \right.\\ &\quad\quad\quad\quad + p\left((1 - d)(D + M) + d(2D + M)\right)\\ &\quad\quad\quad\quad \left. + T\right] \end{align*} $$

数值代入计算

$$ \begin{align*} &= 0.95 \times (20 + 100) \\ &\quad + 0.05\left[0.9 \times 200 \right.\\ &\quad\quad\quad\quad + 0.1\left(0.8 \times 5100 + 0.2 \times 10100\right)\\ &\quad\quad\quad\quad \left. + 20\right] \\ &= 154.5 \text{ ns} \end{align*} $$

选项 A 正确。

76

在操作系统中，以下关于分页的陈述哪些是正确的？（）

正确答案：A

解析

正确（A）：分页通过将物理内存划分为固定大小的页框，避免了不同进程之间因大小不一导致的外部碎片问题。
错误（B）：页面大小直接影响内部碎片程度。页面越大，未被利用的空间比例越高；页面越小，内部碎片总量可能增加但单个碎片比例降低。
错误（C）：分页需要维护页表等数据结构，这会占用额外内存空间。
错误（D）：多级分页的主要目的是减少页表占用的连续内存空间，而非支持不同大小的页面。

77

以下哪项最能描述使用内存映射 I/O 的计算机？（）

正确答案：B

解析：

内存映射 I/O 的核心特征是 统一地址空间，即内存和 I/O 设备共享同一地址范围
通过 地址映射机制，I/O 设备的寄存器被绑定到特定地址值
CPU 访问地址时，根据地址范围自动判断目标是物理内存还是 I/O 设备
选项 (B) 准确描述了这种 “I/O 端口像内存地址一样被访问” 的特性

其他选项对比：

选项	错误原因
A	描述的是独立 I/O 模式（如 x86 的 IN/OUT 指令）
C	属于通道 I/O 的工作方式
D	与内存管理单元无关

78

一个使用 300 GB 磁盘的文件系统，其文件描述符包含 8 个直接块地址、1 个间接块地址和 1 个双重间接块地址。每个磁盘块的大小为 128 字节，每个磁盘块地址的大小为 8 字节。该文件系统中文件的最大可能大小是（）：

正确答案：B

解析：

直接块总大小
- 直接块数量 × 每个磁盘块大小 = 8 × 128 B = 1024 B
一级间接块容量
- 单个磁盘块可存储地址数 = 128 B / 8 B = 16 个地址
- 一级间接块总容量 = 16 个地址 × 128 B = 2048 B
二级间接块容量
- 第一层间接块地址数 = 16 个
- 第二层间接块地址数 = 16 个 × 16 个 = 256 个地址
- 二级间接块总容量 = 256 个地址 × 128 B = 32768 B
最大文件总大小
- 总容量 = 1024 B + 2048 B + 32768 B = 35840 B
- 转换为 Kbytes：35840 B ÷ 1024 B/KiB ≈ 35 KiB

79

在 Unix 文件系统中，非常大的文件的数据块是通过以下哪种方式分配的？（）

正确答案：D

Unix 文件系统使用了索引分配的扩展形式。其特点包括：

多级索引结构
- 直接块（Direct Blocks）
- 单间接块（Single Indirect Block）
- 双间接块（Double Indirect Block）
- 三间接块（Triple Indirect Block）
扩展性设计
通过多级间接块的嵌套组合，可支持超大文件存储，同时避免传统索引分配中固定大小索引表的限制。

80

一个类 Unix 风格的 i 节点包含 10 个直接指针、1 个单级间接指针、1 个双级间接指针和 1 个三级间接指针。磁盘块大小为 1 Kbyte，磁盘块地址为 32 位，但使用 48 位整数进行寻址。最大可能的文件大小是多少？（）

正确答案：C

解析：

磁盘块参数
- 磁盘块大小 = 1Kbyte（1024 字节）
- 地址长度 = 48 位（6 字节），而非 32 位
- 每块可存储地址数 = 1024 / 6 ≈ 170.66 → 取近似值 2⁸

最大文件大小计算

总块数 = 直接指针 + 单级间接 + 双级间接 + 三级间接
       = 10 + 2⁸ + (2⁸ × 2⁸) + (2⁸ × 2⁸ × 2⁸)
       ≈ 2²⁴ 块

最终文件大小
- 每块大小 = 2¹⁰ 字节（1Kbyte）
- 总大小 = 2²⁴ × 2¹⁰ = 2³⁴ 字节

2 - 进程管理

1

考虑以下代码片段：

if (fork() == 0) {
    a=a+5;
    printf("%d,%d\n",a,&a);
} else {
    a=a–5;
    printf("%d, %d\n",a,&a);
}

设父进程打印的值为 $u$、$v$，子进程打印的值为 $x$、$y$。以下哪一项是正确的？

正确答案：C

解析：

fork() 行为：
- 子进程返回值为 0
- 父进程返回子进程的进程 ID
变量操作：
- 子进程执行 a = a + 5 → 结果为 x
- 父进程执行 a = a - 5 → 结果为 u
- 数学关系推导：x = u + 10
地址分析：
- 物理地址：父子进程不同（因 fork() 复制）
- 虚拟地址：通过 fork() 复制机制，子进程继承父进程的虚拟地址空间
- 打印结果验证：v = y（地址相同）
关键结论：
- 数值关系：u + 10 = x
- 地址关系：v = y
- 正确选项为 C

2

原子操作 fetch-and-set x, y 无条件地将内存位置 x 设置为 1，并在不允许任何其他访问内存位置 x 的情况下获取 x 的旧值并存储进入 y。考虑以下对二进制信号量的 P 和 V 函数的实现：

void P (binary_semaphore *s) {
  unsigned y;
  unsigned *x = &(s->value);
  do {
     fetch-and-set x, y;
  } while (y);
}

void V (binary_semaphore *s) {
  S->value = 0;
}

以下哪一项是正确的？（）

正确答案：A

解释：

P() 函数的工作原理
- 使用 fetch-and-set 操作将内存位置 x（即 s->value）设置为 1，并读取其旧值到 y。
- 如果 y 不为 0，则进入 while 循环，持续尝试获取锁。
死锁风险分析
- 若未启用上下文切换（即无法调度其他进程），则当前进程会陷入无限循环，无法退出 P()。
- 此时，由于没有其他进程能执行 V() 将 s->value 置为 0，循环条件始终成立，导致死锁。

3

一个共享变量 x 的初始值为 0，由四个并发进程 W、X、Y 和 Z 进行如下操作：进程 W 和 X 会从内存中读取 x，将其加 1 后写回内存，然后终止；进程 Y 和 Z 则从内存中读取 x，将其减 2 后写回内存，然后终止。每个进程在读取 x 之前会执行计数信号量 S 的 P 操作（即等待），在将 x 写入内存后执行 V 操作（即信号）。信号量 S 的初始值为 2。所有进程执行完毕后，x 的最大可能值是多少？

正确答案：D

进程可以以多种方式运行，以下是一种使 x 达到最大值的情况：信号量 S 初始值为 2

进程 W 执行
- S = 1
- x = 1（但未立即写回内存）
进程 Y 执行
- S = 0
- x = -2（执行减 2 操作）
- S = 1（释放信号量）
进程 Z 执行
- S = 0
- x = -4（再次减 2）
- S = 1（释放信号量）
进程 W 完成写回
- x = 1（最终写回内存）
- S = 2（释放信号量）
进程 X 执行
- S = 1
- x = 2（加 1 操作完成）
- S = 2（释放信号量）

4

某个计算生成两个数组 a 和 b，满足以下条件：
对于 0 ≤ i < n，有 a[i] = f(i)，且 b[i] = g(a[i])。
假设该计算被分解为两个并发进程 X 和 Y，其中 X 计算数组 a，Y 计算数组 b。
两个进程使用两个二进制信号量 R 和 S（初始值均为 0）。数组 a 由两个进程共享。进程结构如下所示：


private i;
for (i=0; i < n; i++) {
   a[i] = f(i);
   ExitX(R, S);
}

进程X


private i;
for (i=0; i < n; i++) {
   EntryY(R, S);
   b[i] = g(a[i]);
}

进程Y

以下哪一项代表 ExitX 和 EntryY 的正确实现？（）


ExitX(R, S) {
  P(R);
  V(S);
}

EntryY(R, S) {
  P(S);
  V(R);
}


ExitX(R, S) {
  V(R);
  V(S);
}

EntryY(R, S) {
  P(R);
  P(S);
}


ExitX(R, S) {
  P(S);
  V(R);
}

EntryY(R, S) {
  V(S);
  P(R);
}


ExitX(R, S) {
  V(R);
  P(S);
}

EntryY(R, S) {
  V(S);
  P(R);
}

正确答案：C

解析

由于 b[i] = g(a[i])，所以对于每一个数据，进程 B 必须在 A 计算完 a[i] 之后再计算 b[i]。

目标约束：既不发生死锁，也不让二进制信号量的值超过 1
各选项分析：
- A: 会导致死锁
- B: 可能使信号量的值在 1 到 n 之间变化
- C: 正确实现，通过互斥操作保证同步
- D: 在某些情况下可能导致信号量 R 和 S 的值达到 2

5

三个并发进程 X、Y 和 Z 分别执行不同的代码段，这些代码段访问并更新某些共享变量。在进入其代码段之前，进程 X 对信号量 a、b 和 c 执行 P 操作（即 wait）；进程 Y 对信号量 b、c 和 d 执行 P 操作；进程 Z 对信号量 c、d 和 a 执行 P 操作。每个进程在其代码段执行完成后，会对其三个信号量执行 V 操作（即 signal）。所有信号量均为二进制信号量，初始值为 1。以下哪一项代表了进程调用 P 操作的无死锁顺序？

正确答案：B

解析

选项 A 可能导致死锁。想象一种情况：进程 X 已获取 a，进程 Y 已获取 b，进程 Z 已获取 c 和 d。此时形成循环等待。
选项 C 也可能导致死锁。想象一种情况：进程 X 已获取 b，进程 Y 已获取 c，进程 Z 已获取 a。此时形成循环等待。
选项 D 也可能导致死锁。想象一种情况：进程 X 已获取 a 和 b，进程 Y 已获取 c。X 和 Y 形成相互等待。

6

两个并发进程 P1 和 P2 使用四个共享资源 R1、R2、R3 和 R4，如下所示：


Compute;
Use R1;
Use R2;
Use R3;
Use R4;


Compute;
Use R1;
Use R2;
Use R3;
Use R4;

两个进程同时启动，每个资源一次只能被一个进程访问。进程间存在以下资源调度约束：

P2 必须在 P1 访问 R1 之前完成对 R1 的使用
P1 必须在 P2 访问 R2 之前完成对 R2 的使用
P2 必须在 P1 访问 R3 之前完成对 R3 的使用
P1 必须在 P2 访问 R4 之前完成对 R4 的使用

除此之外没有其他调度约束。若仅使用二进制信号量来强制执行上述调度约束，至少需要多少个二进制信号量？（）

正确答案：B

解析

需要使用两个信号量 A 和 B，其中 A 的初始值为 0，B 的初始值为 1。

semaphore A = 0;
semaphore B = 1;

P1() {
    Compute;
    Wait(A);
    Use R1;
    Use R2;
    Signal(B);
    Wait(A);
    Use R3;
    Use R4;
    Signal(B);
}

P2() {
    Compute;
    Wait(B);
    Use r1;
    Signal(A); 
    Wait(B);
    Use R2;
    Use R3;
    Signal(A);
    Wait(B);
    Use R4;
    Signal(B);
}

在进程 P1 中，起初由于信号量 A = 0，控制流程会被卡在 Wait(A) 的 while 循环中。而在进程 P2 中，Wait(B) 会将信号量 B 的值减为 0。接下来，P2 使用资源 R1，并将信号量 A 的值加一，使得进程 P1 能够进入其临界区并使用资源 R1。

因此，P2 会在 P1 获取资源 R1 之前，先完成对 R1 的使用。

此时，在 P2 中，B 的值为 0，所以 P2 无法使用资源 R2，必须等待 P1 使用完 R2 并调用 Signal(B) 来将 B 的值加一。这样，P1 会在 P2 获取 R2 之前，先完成对 R2 的使用。

随后，由于信号量 A 又变为 0，P1 无法继续执行，再次卡在 Wait(A) 的 while 循环中。此时，P2 使用资源 R3，并将信号量 A 的值加一，使得 P1 能够进入临界区使用 R3。因此，P2 会在 P1 获取 R3 之前，先完成对 R3 的使用。

最后，P1 使用资源 R4，并将 B 的值加一，使得 P2 可以进入临界区使用 R4。由此可见，P1 会在 P2 获取 R4 之前，先完成对 R4 的使用。

综上所述，选项 (B) 正确。

7

一个进程执行以下代码：

fork();
fork();
fork();

创建的子进程总数是（）？

正确答案：C

让我们为这三行 fork() 添加标签：

fork(); // 第 1 行  
fork(); // 第 2 行  
fork(); // 第 3 行

      L1      // 第 1 行将创建 1 个子进程  
    /    \  
  L2     L2   // 第 2 行将创建 2 个子进程  
  / \    / \  
L3 L3   L3 L3 // 第 3 行将创建 4 个子进程

我们也可以通过直接公式计算子进程数量。n 个 fork 语句时，子进程数总是 2ⁿ – 1。

8

Fetch_And_Add(X,i) 是一个原子指令，它会读取内存位置 X 的值，将其增加 i，并返回 X 的旧值。该指令用于以下伪代码中实现忙等待锁。L 是一个初始化为 0 的无符号整型共享变量。值 0 表示锁可用，非零值表示锁不可用。

假设我们使用该原子指令实现如下自旋锁：

AcquireLock(L) {
    while (Fetch_And_Add(L,1))
        L = 1;
}
ReleaseLock(L) {
    L = 0;
}

则此实现方式（）：

正确答案：B

仔细观察下面的 while 循环：

while (Fetch_And_Add(L,1))
    L = 1; // 等待进程可能在此处执行
           // 刚好在锁被释放后立即执行
           // 并将 L 设置为 1。

考虑一种情况：某个进程刚释放锁并使 L=0。此时若有另一个进程正在等待锁（即执行 AcquireLock() 函数），则在 L 被设为 0 后，等待进程可能立即执行 L=1。此时锁是可用的，但 L=1。由于 L=1，等待进程（以及后续任何新到达的进程）都无法退出 while 循环。

上述问题可通过修改 AcquireLock() 解决：

AcquireLock(L){
    while (Fetch_And_Add(L,1)) {
        // Do Nothing
    }
}

溢出仅当比 ‘int’ 类型大小更多的进程执行 while 循环的检查条件但未执行 L=1 时才会发生（需要抢占）。但当 L=1 时，进程会在 while 循环中重复，不会发生溢出，因为每次对 L 的递增后，L 都会被重新设置为 1。选项 (b) 比选项 (a) 更优。

9

在用户模式和内核模式之间切换所需的时间为 t1，而切换两个进程所需的时间为 t2。以下哪项是正确的？（）

正确答案：C

解析

进程切换机制：进程切换（或上下文切换）必须在内核模式下执行。其完整流程包含：
1. 用户模式 → 内核模式切换
2. 保存当前进程的 PCB（进程控制块）
3. 加载目标进程的 PCB
4. 内核模式 → 用户模式切换
时间对比分析：
- t1（模式切换）：仅需修改硬件状态标志位，耗时极短
- t2（进程切换）：除模式切换外，还需执行 PCB 的保存/恢复等复杂操作
- 因此必然满足 t1 < t2

10

线程通常被定义为“轻量级进程”，因为操作系统（OS）为线程维护的数据结构比为进程维护的小。关于这一点，以下哪项是正确的？（）

正确答案：C

解析

线程共享进程的地址空间。虚拟内存与进程相关，而非线程。
线程是 CPU 利用的基本单位，包含程序计数器、栈和一组寄存器（以及线程 ID）。
选项分析：
- 选项 A：操作系统不仅维护 CPU 寄存器，还维护栈、代码文件和数据文件。因此该选项错误。
- 选项 B：每个线程都维护独立的栈，因此该选项错误。
- 选项 C：操作系统不会为单个线程维护任何虚拟内存状态，这是正确的。
- 选项 D：操作系统还会维护其他信息（如 CPU 寄存器、栈、程序计数器等），因此该选项错误。

11

考虑进程 P1 和 P2 访问临界区时使用的如下方法。共享布尔变量 S1 和 S2 的初始值是随机分配的：


while (S1 == S2) ;
Critical Section
S1 = S2;


while (S1 != S2) ;
Critical Section
S2 = !S1;

关于上述方案，以下哪项描述是正确的？（）

正确答案：A

互斥性（Mutual Exclusion）

该方案确保：

P1 仅在 S1 != S2 时进入临界区，
P2 仅在 S1 == S2 时进入临界区，二者永不同时成立，因此保证互斥性。

进展性（Progress）

如果只有一个进程希望进入临界区，且另一个进程不打算进入，那么该进程应该能够进入临界区。但在此方案中，两个变量的更新取决于彼此的退出行为。因此，即使 P1 不想进入临界区，它不更新 S1 也可能阻止 P2 进入。故不满足进展性。

12

以下程序包含 3 个并发进程和 3 个二进制信号量。信号量初始化为 S0 = 1，S1 = 0，S2 = 0。进程 P0 将打印 ‘0’ 多少次？（）


while (true) {
    wait(S0);
    print '0';
    signal(S1);
    signal(S2);
}

Process P0


wait(S1);
signal(S0);

Process P1


wait(S2);
signal(S0);

Process P2

正确答案：C

解析

P1 和 P2 都只有一条语句，会各执行一次就结束。每次 P0 运行后，它会分别 signal S1 和 S2，允许一次 P1 和一次 P22的执行，每次分别只增加一个 S0。所以每执行完一次 P0，P2 和 P3 都必须各执行一次才能再次唤醒 P0。

但问题是 P2 和 P3 各只有一次机会，执行完之后就无法再次执行。

所以 P1 一共会执行三次循环，然后就在 wait(S0) 的地方阻塞住，答案是正好三次，选择 C。

13

使用测试并设置（test-and-set）指令实现进程临界区的 enter_CS() 和 leave_CS() 函数如下所示：

void enter_CS(X) {
    while test-and-set(X);
}
void leave_CS(X) {
   X = 0;
}

在上述方案中，X 是与临界区关联的内存位置，初始值为 0。现在考虑以下陈述：
I. 上述临界区问题的解决方案是无死锁的
II. 该方案是无饥饿的
III. 进程以先进先出（FIFO）顺序进入临界区
IV. 同一时间可能有多个进程进入临界区

以上陈述中哪些为真？（）

正确答案：A

解析：

上述方案是一个简单的测试并设置解决方案，确保不会发生死锁，但未使用任何队列来避免饥饿或保证 FIFO 顺序。

陈述 I 正确：test-and-set 指令通过原子操作确保至少有一个进程能进入临界区，因此方案本身是无死锁的。
陈述 II 错误：由于缺乏优先级或队列机制，某些进程可能长期无法进入临界区，导致饥饿。
陈述 III 错误：算法未维护请求顺序，无法保证 FIFO 顺序。
陈述 IV 错误：test-and-set 的原子性确保每次只有一个进程能进入临界区。

14

一个进程执行以下代码：

for (i = 0; i < n; i++)
    fork();

创建的子进程总数是（）

正确答案：B

解析

    F0       // 第一次 fork 会创建 1 个子进程
   / \
  F1 F1      // 第二次 fork 会创建 2 个子进程
 / \ / \
F2 F2 F2 F2  // 第三次 fork 会创建 4 个子进程
...

对上述树结构中 i=0 到 n-1 的所有层级求和，得到的结果是 2ⁿ-1。因此，子进程的数量为 2ⁿ–1。
创建的总进程数为（子进程数）+1。
注意：最大进程数为 2ⁿ，可能因 fork 失败而有所变化。

15

考虑以下关于用户级线程和内核级线程的陈述。以下哪一项是错误的？（）

正确答案：D

解析

内核级线程由操作系统管理，因此线程操作在内核代码中实现。内核级线程可以通过将线程分配到不同处理器上利用多处理器系统。如果一个线程阻塞，不会导致整个进程阻塞。内核级线程也有一些缺点：由于管理开销，它们比用户级线程更慢；内核级上下文切换涉及更多步骤，而不仅仅是保存一些寄存器；此外，它们不可移植，因为实现依赖于操作系统。

选项 (A): 内核级线程的上下文切换时间比用户级线程长。
正确。因为用户级线程由用户管理，内核级线程由操作系统管理。内核级线程管理涉及许多开销，而用户级线程管理没有这些开销。因此内核级线程的上下文切换时间更长。
选项 (B): 用户级线程不需要任何硬件支持。
正确。因为用户级线程由用户管理和库实现，不需要硬件支持。
选项 (C): 相关的内核级线程可以在多处理器系统的不同处理器上调度。
正确。
选项 (D): 阻塞一个内核级线程会阻塞所有相关线程。
错误。因为内核级线程由操作系统管理，如果一个线程阻塞，不会导致所有线程或整个进程阻塞。

16

两个进程 P1 和 P2 需要访问一段代码的临界区。考虑以下同步构造：其中 wants1 和 wants2 是初始化为 false 的共享变量。关于上述结构，以下哪个陈述是正确的？


while (true) {
  wants1 = true;
  while (wants2 == true);
  /* Critical Section */
  wants1 = false;
}
/* Remainder section */


while (true) {
  wants2 = true;
  while (wants1 == true);
  /* Critical Section */
  wants2 = false;
}
/* Remainder section */

正确答案：D

有限等待定义：在某个进程请求进入其临界区后到该请求被满足之前，其他进程进入其临界区的次数存在一个上限。

互斥机制分析：

互斥用于防止对共享资源的同时访问。通过临界区实现，即进程或线程访问共享资源的代码段。
解决方案：两个进程 P1 和 P2 需要访问代码的临界区。此处 wants1 和 wants2 是初始化为 false 的共享变量。
互斥验证：当 wants1 和 wants2 同时为 true 时，两个进程都会进入 while 循环并相互等待对方完成，这会导致无限循环从而引发死锁。假设 P1 在临界区（意味着 wants1=true，wants2 可以是 true 或 false），此时 P2 无法进入临界区，反之亦然，这满足了互斥属性。

有限等待验证：

由于每次请求后进入临界区的进程数量有上限，因此也满足有限等待条件。

结论：

此算法 不能防止死锁（当两个进程同时设置 wants 标志为 true 时会发生死锁）
但 能确保互斥（同一时间只有一个进程能进入临界区）

17

以下哪一项是错误的？（）

正确答案：D

用户级线程由用户进程实现，内核级线程由操作系统实现。操作系统不识别用户级线程，但能识别内核级线程。

用户线程：
- 实现简单，上下文切换时间短，无需硬件支持
- 若一个用户级线程执行阻塞操作，则整个进程会被阻塞
- 示例：Java 线程、POSIX 线程
内核线程：
- 实现复杂，上下文切换时间较长，需要硬件支持
- 若一个内核级线程执行阻塞操作，其他线程仍可继续执行
- 示例：Windows、Solaris 系统

18

考虑以下使用信号量的生产者-消费者问题的过程：以下哪一项是正确的？（）

semaphore n = 0;
semaphore s = 1;

void producer() {
    while (true) {
        produce();
        semWait(s);
        addToBuffer();
        semSignal(s);
        semSignal(n);
    }
}

void consumer() {
    while (true) {
        semWait(s);
        semWait(n);
        removeFromBuffer();
        semSignal(s);
        consume();
    }
}

正确答案：C
最初，缓冲区中没有元素。
信号量 s=1 且信号量 n=0。
我们假设当缓冲区为空时，控制权首先交给消费者。semWait(s) 会减少信号量’s’的值。
现在，s=0 且 semWait(n) 会减少信号量’n’的值。
由于信号量’n’的值变为小于 0，控制权会卡在函数 semWait() 的 while 循环中，从而导致死锁。
因此，如果消费者在缓冲区为空时成功获取信号量 s，则会发生死锁。

19

考虑两个进程 P1 和 P2 访问受二进制信号量 SX 和 SY 保护的共享变量 X 和 Y，SX 和 SY 均初始化为 1。P 和 V 表示通常的信号量操作符，其中 P 减少信号量值，V 增加信号量值。P1 和 P2 的伪代码如下：

P1 : While true do {
   L1 : ................
   L2 : ................
   X = X + 1;
   Y = Y - 1;
   V(SX);
   V(SY);
 }

P2 : While true do {
   L3 : ................
   L4 : ................
   Y = Y + 1;
   X = Y - 1;
   V(SY);
   V(SX);
}

为了避免死锁，L1、L2、L3 和 L4 处的正确操作符分别是（）？

正确答案：D

解析

选项 A：
- 在 L1（P(SY)）处，即进程 P1 请求 SY 锁，而该锁由进程 P2 持有；
- 在 L3（P(SX)）处，P2 请求 SX 锁，而该锁由 P1 持有。
- 此处存在循环等待条件，意味着死锁。
选项 B：
- 在 L1（P(SX)）处，即进程 P1 请求 SX 锁，而该锁由进程 P2 持有；
- 在 L3（P(SY)）处，P2 请求 SY 锁，而该锁由 P1 持有。
- 同样存在循环等待条件，导致死锁。
选项 C：
- 在 L1（P(SX)）处，即进程 P1 请求 SX 锁；
- 在 L3（P(SY)）处，P2 请求 SY 锁。
- 但 SX 和 SY 无法被其所属进程 P1 和 P2 释放。
- （注：此描述存在矛盾，实际应通过统一顺序获取资源以避免死锁）
选项 D：
- 所有进程均按相同顺序请求资源（先 P(SX) 再 P(SY)），
- 避免了循环等待条件，从而防止死锁发生。
- 符合银行家算法中“有序资源分配法”的原则。

20

假设我们想使用二进制信号量 S 和 T 同步两个并发进程 P 和 Q。进程 P 和 Q 的代码如下所示：


while (1) {
W:
   print '0';
   print '0';
X:
}

进程 P


while (1) {
Y:
   print '1';
   print '1';
Z:
}

进程 Q

同步语句只能插入在 W、X、Y 和 Z 这四个位置。以下哪一项操作序列始终会导致输出以 '001100110011...' 开头？

正确答案：B

解析

初始化状态：S = 1，T = 0
执行流程：
1. 进程 P 首先获得执行权：
  - 执行 P(S) 操作，S 减至 0
  - 打印 '00'
  - 执行 V(T) 操作，T 增至 1
2. 进程 Q 获得执行权：
  - 执行 P(T) 操作，T 减至 0
  - 打印 '11'
  - 执行 V(S) 操作，S 恢复为 1
3. 循环往复：
  - S 和 T 的值在每次循环中交替控制进程 P 和 Q 的执行权限
最终输出序列：00 11 00 11 ...
结论：选项 B 的信号量配置与操作顺序满足题目要求

21

以下哪项本身不会主动中断正在运行的进程？（）

正确答案：C
调度程序不会主动中断进程。它是在中断（如定时器中断、I/O 中断或系统调用）发生后，由操作系统内核调用，用于决定是否切换当前进程。调度程序负责实现进程调度策略，但不是中断的来源。

22

在进程上下文切换时，以下哪项内容不一定需要被保存？（）

正确答案：B

解析：
在进程上下文切换时，操作系统需要保存当前进程的状态以便后续恢复。通常包括：

通用寄存器（A）：必须保存，因为它们存储了进程执行时的临时数据。
程序计数器（C）：必须保存，用于记录下一条要执行的指令地址。
TLB（B）：其内容在进程切换时可能被刷新，但并非必须显式保存，因为页表基址寄存器会改变，导致 TLB 失效，系统会自动清空或无效化 TLB，无需手动保存。

因此，B 项不一定需要被保存，正确答案为 B。

23

以下两个共享变量 B（初始值为 2）的函数 P1 和 P2 并发执行。

P1() {
    C = B – 1;
    B = 2 * C;  
}

P2() {
    D = 2 * B;
    B = D - 1;
}

执行后，B 可能取的不同值的数量是（）：

正确答案：A

并发进程可能有以下几种执行方式：

执行方式一
C = B – 1; // C = 1
B = 2 * C; // B = 2
D = 2 * B; // D = 4
B = D - 1; // B = 3
执行方式二
C = B – 1; // C = 1
D = 2 * B; // D = 4
B = D - 1; // B = 3
B = 2 * C; // B = 2
执行方式三
C = B – 1; // C = 1
D = 2 * B; // D = 4
B = 2 * C; // B = 2
B = D - 1; // B = 3
执行方式四
D = 2 * B; // D = 4
C = B – 1; // C = 1
B = 2 * C; // B = 2
B = D - 1; // B = 3
执行方式五
D = 2 * B; // D = 4
B = D - 1; // B = 3
C = B – 1; // C = 2
B = 2 * C; // B = 4

通过上述所有可能的执行路径分析，最终 B 的不同取值包括：

2（由执行方式一、二、三、四产生）
3（由执行方式一、二、三、四产生）
4（由执行方式五产生）

因此，B 的不同可能值共有 3 个：2、3 和 4。

24

进程 X 和 Y 需要访问一个临界区。考虑以下由两个进程使用的同步构造。其中，varP 和 varQ 是共享变量，且初始值均为 false。以下哪一项陈述是正确的？（）


/* other code for process X */
while (true) {
    varP = true;
    while (varQ == true) {
        /* Critical Seciton */
        varP = false;
    }
}
/* other code for process X */

Process X


/* other code for process Y */
while (true) {
    varQ = true;
    while (varP == true) {
        /* Critical Seciton */
        varQ = false;
    }
}
/* other code for process Y */

Process Y

正确答案：A

解析：

互斥失效分析
当两个进程同时尝试进入临界区时，由于两个共享变量 varP 和 varQ 都为 true，因此两者会被同时允许进入临界区。这直接违反了互斥原则（Mutual Exclusion），即同一时刻只能有一个进程在临界区内执行。
死锁预防机制
死锁的四个必要条件包括：互斥、持有并等待、不可抢占和循环等待。由于本方案未能满足互斥这一前提条件，因此死锁根本无法形成。换句话说，只要互斥未被满足，死锁就不可能发生。

综上，该方案虽然避免了死锁风险，但未能实现基本的互斥保护，故正确答案为 A。

25

在某操作系统中，尝试使用以下策略进行死锁预防：为每个进程分配一个唯一的时间戳。如果一个进程被终止，则其在重新启动时仍保留原始时间戳。设 Ph 是当前持有资源 R 的进程，Pr 是请求该资源的进程，T(Ph) 和 T(Pr) 分别表示它们的时间戳。系统根据以下规则进行调度决策：

if (T(Pr) < T(Ph))
    then kill Pr
else wait

关于该策略的以下哪项说法是正确的？

正确答案：A

解析

死锁预防机制
- 请求进程的时间戳始终小于持有进程的时间戳
- 被终止的进程以相同时间戳重启，其时间戳不会超过当前最大值
- 新到达的较小时间戳进程会被直接终止，打破循环等待条件
饥饿可能性
- 较小时间戳的进程可能因持续被终止而无法获取资源
- 即使重启后仍保持原时间戳，可能导致无限等待

综上，该方案通过时间戳策略实现死锁预防，但存在进程长期无法执行的风险。答案选 A

26

信号量变量 full、empty 和 mutex 分别初始化为 0、n 和 1。进程 P1 反复每次向大小为 n 的缓冲区添加一个项目，进程 P2 反复每次从同一缓冲区移除一个项目，使用如下程序实现。在程序中，K、L、M 和 N 是未指定的语句。

P1 {
    while (1) {
        K;
        P(mutex);
        Add an item to the buffer;
        V(mutex);
        L;
    }
}

P2 {
    while (1) {
        M;
        P(mutex);
        Remove an item from the buffer;
        V(mutex);
        N;
    }
}

语句 K、L、M 和 N 分别是：（）

正确答案：D

解析：

进程 P1 是生产者，进程 P2 是消费者。
信号量 full 初始化为 0，表示缓冲区中没有项目。
信号量 empty 初始化为 n，表示缓冲区有 n 个空间。

在 进程 P1 中：

对 empty 执行等待操作（P(empty)），表示如果缓冲区无空间则 P1 无法继续生产；
对 full 执行信号操作（V(full)），表示已向缓冲区添加一个项目。

在 进程 P2 中：

对 full 执行等待操作（P(full)），表示如果缓冲区为空则消费者无法消费；
对 empty 执行信号操作（V(empty)），表示消费后缓冲区增加一个空间。

因此选项 (D) 正确。

27

考虑以下两个进程的同步解决方案。

进程 0
进入：循环 while (turn == 1);
（临界区）
退出：turn = 1;

进程 1
进入：循环 while (turn == 0);
（临界区）
退出：turn = 0;

共享变量 turn 初始化为零。以下哪一项是正确的？（）

正确答案：C

互斥要求：防止对共享资源的同时访问。由于信号量 turn 初始化为零，且此信号量值仅在给定进程的临界区之后改变。因此，这确保了每次最多只有一个进程在临界区中，即互斥要求得到满足。

进展要求：进程最终应能完成。但进程 1 初始时无法直接进入临界区，因为信号量值为 0，只有在进程 0 执行后，进程 1 才能进入临界区。因此，进展要求未被满足。

有限等待要求：任何进程都不应无限期地等待资源。进程 1 可以直接进入，也可以在进程 0 之后进入临界区。因此，有限等待要求得到满足。

结论：选项 (C) 是正确的。

28

考虑一个非负计数信号量 S。操作 P(S) 会将 S 减 1，V(S) 会将 S 加 1。在执行过程中，以某种顺序发起了 20 次 P(S) 操作和 12 次 V(S) 操作。使得至少有一个 P(S) 操作仍处于阻塞状态的 S 的最大初始值是（）。

正确答案：A
20-7=13 将在阻塞状态下，当我们执行 12 次 V(S) 操作时，会使 12 个进程从阻塞状态获得执行机会。因此这里会剩下 1 个进程处于队列（阻塞状态）。此处假设如果一个进程正在临界区中，则不会被其他进程阻塞。

29

以下代码包含两个可以并行运行的线程（生产者和消费者）。此外，S 和 Q 是配备标准 P 和 V 操作的二进制信号量。

semaphore S = 1, Q = 0; integer x;

producer:
    while (true) do
        P(S);
        x = produce();
        V(Q);
    done

consumer:
    while (true) do
        P(Q);
        consume(x);
        V(S);
    done

关于上述程序，以下哪项是正确的？（）

正确答案：D

信号量是一种硬件或软件标记变量，其值表示公共资源的状态。其目的是锁定正在使用的资源。需要该资源的进程会检查信号量以确定资源状态，并据此决定是否继续执行。在多任务操作系统中，通过信号量技术实现活动同步。信号量上定义了wait和signal操作：进入临界区由wait操作控制，退出临界区由signal操作处理。wait和signal操作也称为 P 和 V 操作。信号量 (S) 的操作规则如下：

P(S)操作将信号量值减 1。若结果为负数，则 P 操作会被阻塞直到条件满足。
V(S)操作将信号量值加 1。

解析：消费者仅在生产者生成物品后才能消费，而生产者（除第一次外）必须在消费者消费完当前物品后才能生成新物品。

生产者流程：
- 初始时 S=1，P(S) 使 S 变为 0 → 生成物品 x → V(Q) 使 Q 变为 1。
- 下一次循环时 S 仍为 0，P(S) 会阻塞生产者。
消费者流程：
- P(Q) 使 Q 变为 0 → 消费物品 x → V(S) 唤醒被阻塞的生产者。
- 此时生产者从生成 x 的位置继续执行。

因此，消费者总是在生产者生成新值前消费当前值。

选项分析：

A) 不会发生死锁，因为生产者和消费者使用不同的信号量（无持有并请求）。
B) 不会发生饥饿，因为生产者和消费者交替执行且具有有限等待时间。
C) 生产者生成的物品不会丢失，因为每次生成后都会被消费者消费。
D) 正确，消费者在生产者生成新值前必须消费当前值。

30

一个操作系统实现了一项策略，要求进程在请求新资源之前必须释放所有已持有的资源。从以下选项中选择正确的陈述（）：

正确答案：B

解释：

资源饥饿可能发生：进程在持有当前资源时若需申请新资源，必须先释放已有资源。这种机制可能导致进程反复申请/释放资源却始终无法获得全部所需资源，从而陷入饥饿状态。
死锁不可能发生：该策略强制进程在请求新资源前释放所有已占资源，直接破坏了死锁的"不可抢占"条件，同时消除了循环等待的可能性。

31

考虑以下进程 P1 和 P2 的 C 代码。初始值为 a=4，b=0，c=0。


1. if (a < 0)
2.     c = b-a;
3. else
4.     c = b+a;


1. b = 10;
2. a = -3;

如果 P1 和 P2 并发执行，a、b、c 是两个进程的共享变量，两个进程都执行结束后，变量 c 的值不可能是以下选项中的那一个？（）

正确答案：C

解析

由于 P1 和 P2 并发执行，所以可能存在多种情况，接下来逐一进行分析：

P1(1,3,4): a = 4, b = 0, c = b+a = 4，选项 A 可能
P1(1,3) → P2(1,2) → P1(4): a = -3, b = 10, c = b+a = 7，选项 B 可能
P2(1,2) → P1(1,2): a = -3, b = 10, c = b-a = 13，选项 D 可能

所以选项 C 是不可能出现的，答案选择 C。

32

当操作系统从进程 A 切换到进程 B 时，以下哪项操作通常不会执行？（）

正确答案：C

解析：

进程换出内存的情况
在上下文切换期间，进程不会被换出内存到磁盘。进程通常在挂起时才会被换出内存到磁盘。
TLB 失效操作
在上下文切换过程中，操作系统会使 TLB（Translation Lookaside Buffer，转换后备缓冲区）失效，以确保 TLB 与当前运行的进程一致。
结论
因此，选项 (C) 是错误的。

33

在使用 “最佳适配” 算法为 “作业” 分配 “内存分区” 的计算机系统中，遇到以下情况：


分区大小（KB）	4K 8K 20K 2K
作业需求（KB）	2K 14K 3K 6K 10K 20K 2K
执行时间	4 10 2 1 4 1 8 6

问 20K 的作业何时完成？（）

正确答案：D

内存分区为 4k、8k、20k、2k。由于采用最佳适配分配算法，该算法会将进程分配到最小且足够容纳的空闲分区中。

作业分配过程如下：

2k 的作业进入 2k 分区并运行（4 单位时间）
14k 的作业进入 20k 分区并运行（10 单位时间）
3k 的作业进入 4k 分区并运行（2 单位时间）
6k 的作业进入 8k 分区并运行（1 单位时间）
10k 的作业进入 20k 分区并运行（1 单位时间）
20k 的作业进入 20k 分区并运行（8 单位时间）

总完成时间计算：
$$10\ (\text{14k}) + 1\ (\text{10k}) + 8\ (\text{20k}) = 19\ \text{单位时间}$$

因此，20k 作业的总完成时间为 19 单位时间，正确答案为 “这些都不对”。

34

一个并发系统包含 3 个进程，以非抢占式和互斥方式共享资源 R。这些进程具有唯一的优先级范围 1…3（3 为最高优先级）。需要同步这些进程，确保资源始终分配给最高优先级的请求者。系统伪代码如下：

Shared Data
    mutex: semaphore = 1; /* 初始化为1 */
    proceed[3]: semaphore = 0; /* 所有初始化为0 */
    R_requested[3]: boolean = false; /* 所有初始化为false */
    busy: boolean = false; /* 初始化为false */

Code for processes
begin process
    my-priority: integer;
    my-priority := ____; /* 范围1...3 */
    repeat
        request_R(my-priority);
        P(proceed[my-priority]);
        {使用共享资源R}
        release_R(my-priority);
    forever
end process;

Procedures
procedure request_R(priority);
    P(mutex);
    if busy = true then
        R_requested[priority] := true;
    else
    begin
        V(proceed[priority]);
        busy := true;
    end
    V(mutex);

请给出过程 release_R 的伪代码。

procedure release_R(priority);
    P(mutex);
    busy := false;
    next_priority := 0;
    for i from 3 downto 1 do
        if R_requested[i] = true then
            next_priority := i;
            break;
    if next_priority > 0 then
    begin
        R_requested[next_priority] := false;
        V(proceed[next_priority]);
        busy := true;
    end
    V(mutex);

解释：

互斥保护
使用 P(mutex) 和 V(mutex) 包裹整个操作，确保对共享数据的访问互斥。
资源释放逻辑
- 将 busy 标志设为 false，表示资源已释放。
- 从最高优先级（3）到最低优先级（1）遍历 R_requested 数组，寻找第一个请求资源的进程。
- 若找到等待的进程（next_priority > 0），则：
  - 清除其请求标志 R_requested[next_priority]。
  - 通过 V(proceed[next_priority]) 唤醒该进程。
  - 设置 busy := true，表示资源已被重新分配。
优先级调度
通过降序遍历优先级，确保每次释放资源后，优先级最高的等待进程能立即获得资源使用权，满足题目要求。

35

下图中的进程状态转换图所代表的是（）

正确答案：B
解析：
具备抢占式调度器的操作系统允许高优先级进程中断当前运行的低优先级进程，从而实现更灵活的资源分配。进程状态转换图中若包含"就绪 → 运行"的双向箭头（即运行态可被抢占），则表明系统支持抢占式调度。

36

以下哪个选项是错误的？（）

正确答案：B

解析

错误原因：实际情况下，进程的创建和管理开销较大，而线程由于共享进程资源，开销较小。
结论：因此，选项 (B) 的描述与事实相反，属于错误选项。

37

以下哪项不是同一进程中的所有线程共享的？
I. 程序计数器
II. 栈
III. 寄存器
IV. 地址空间

正确答案：C

解析

关键概念：线程是进程内的执行单元，多个线程共享进程的资源，但拥有独立的控制流。
私有资源：
- 程序计数器（记录当前执行指令位置）
- 栈（存储函数调用时的局部变量和返回地址）
- 寄存器（保存线程执行时的临时数据）
共享资源：
- 地址空间（包括代码段、数据段、堆等内存区域）
结论：选项 (C) 正确，因为 I、II 和 III 都是线程私有资源，而 IV 是唯一共享的资源。

38

当进程 L 执行期间设备控制器发出中断后，会发生以下事件：

(P) 处理器将进程 L 的状态压入控制栈。
(Q) 处理器完成当前指令的执行。
(R) 处理器执行中断服务程序。
(S) 处理器从控制栈中弹出进程 L 的状态。
(T) 处理器根据中断加载新的 PC 值。

上述事件发生的正确顺序是（）？

正确答案：A

因此，选项 (A) 是正确的。

中断响应流程
- 首先，处理器需完成当前正在执行的指令（Q），这是中断响应的基本原则。
上下文切换准备
- 完成当前指令后，处理器根据中断向量表加载新的程序计数器（PC）值（T），定位到中断服务程序入口。
状态保存
- 在跳转执行中断服务前，处理器将进程 L 的当前状态（如寄存器内容）压入控制栈（P），以保证中断返回后能恢复执行。
中断服务执行
- 处理器开始执行中断服务程序（R），处理设备控制器的中断请求。
状态恢复与返回
- 中断服务完成后，处理器从控制栈中弹出之前保存的进程状态（S），恢复现场并继续执行被中断的进程。

该顺序严格遵循操作系统中断处理的标准流程，确保系统稳定性和进程连续性。

39

用户级线程是程序员可见的线程，但内核并不知道它们的存在。操作系统内核支持并管理内核级线程。三种不同的模型关联了用户级线程和内核级线程。以下哪些陈述是正确的？（）
(a)
(i) 多对一模型将多个用户线程映射到一个内核线程
(ii) 一对一模型将一个用户线程映射到一个内核线程
(iii) 多对多模型将多个用户线程映射到较少或相等数量的内核线程

(b)
(i) 多对一模型将多个内核线程映射到一个用户线程
(ii) 一对一模型将一个内核线程映射到一个用户线程
(iii) 多对多模型将多个内核线程映射到较少或相等数量的用户线程

正确答案：A
在多对多模型中，我们映射的是内核线程而非用户线程。所以选项 (A) 是正确的。

40

以下程序的输出是什么？

main( )
{
    int a = 10;
    if ((fork ( ) == 0))
        a++;
    printf (“%d\\n”, a );
}

正确答案：11 和 11

A
解析：

fork() 系统调用会创建当前进程的副本（子进程）
父进程中 fork() 返回子进程 PID（非 0 值），条件不成立不执行 a++
子进程中 fork() 返回 0，条件成立执行 a++ 使 a=11
两个进程分别执行 printf 输出各自的 a 值
最终输出结果为两行：
- 父进程输出 10
- 子进程输出 11
注意：由于进程调度顺序不确定，输出顺序可能为 10\n11 或 11\n10

41

互斥问题发生于（）

正确答案：B

解释：

互斥问题的核心场景：当多个进程需要访问同一资源时（如内存、文件或设备）
触发条件：缺乏同步机制导致并发访问冲突
典型表现：数据不一致、竞争条件等问题
解决目标：通过互斥机制确保同一时刻仅一个进程能操作临界资源

42

临界区是指（）：

正确答案：A

解析：

正确答案 A：临界区（Critical Section）指程序中访问共享资源的代码段，其核心特性是互斥性——同一时刻仅允许一个进程/线程执行该代码段，以避免数据竞争和不一致问题。
选项 B 错误：死锁是多个进程因资源循环等待导致的僵局，属于并发控制的问题范畴，与临界区的定义无直接关联。
选项 C 错误：临界区的互斥性要求严格限定为单个执行体，“有限数量"描述不符合其本质特征。
选项 D 错误：临界区是操作系统理论中的通用概念，Windows NT 的实现方式（如使用内核对象）仅为具体技术方案之一。

43

在某一时刻，计数信号量的值为 10。经过以下哪种操作后，其值会变为 7？

(a) 3 次 V 操作
(b) 3 次 P 操作
(c) 5 次 V 操作和 2 次 P 操作
(d) 2 次 V 操作和 5 次 P 操作

以下哪个选项正确？（）

正确答案：C

操作说明

P 操作：等待操作会使计数信号量的值 减 1
V 操作：信号操作会使计数信号量的值 加 1

初始状态
当前计数信号量的值 = 10

选项分析

(a) 3 次 V 操作 → 10 + 3 = 13 ❌
(b) 3 次 P 操作 → 10 - 3 = 7 ✅
(c) 5 次 V 操作 + 2 次 P 操作 → 10 + 5 - 2 = 13 ❌
(d) 2 次 V 操作 + 5 次 P 操作 → 10 + 2 - 5 = 7 ✅

结论
选项 (b) 和 (d) 的结果均为 7，因此 选项 (C) 正确。

44

有三个进程 P1、P2 和 P3 共享一个信号量以同步某个变量。
信号量的初始值为 1。假设信号量的负值表示当前有多少个进程在等待队列中。
进程按以下顺序访问该信号量：

(a) P2 需要访问
(b) P1 需要访问
(c) P3 需要访问
(d) P2 退出临界区
(e) P1 退出临界区

最终信号量的值将是（）。

正确答案：A

解析过程：

初始值 S = 1
- P2 访问时，S -= 1 → S = 0（无进程等待）
P1 访问时，S -= 1 → S = -1（1 个进程等待）
P3 访问时，S -= 1 → S = -2（2 个进程等待）
P2 退出时，S += 1 → S = -1（1 个进程等待）
P1 退出时，S += 1 → S = 0（无进程等待）

结论：最终信号量值为 0，因此选项 (A) 正确。

45

在某一计算时刻，计数信号量的值为 7。随后对该信号量执行了 20 次 P 操作和 x 次 V 操作。若信号量的新值为 5，则 x 的值为（）：

正确答案：A

解析

P 操作：将信号量值减 1
V 操作：将信号量值加 1
初始信号量值 = 7
经过 20 次 P 操作后：
7 - 20 = -13
再经过 x 次 V 操作后：
-13 + x = 5
解得：
x = 5 + 13 = 18
因此选项 (A) 正确。

46

用户级线程相比内核级线程的一个缺点是（）：

正确答案：A

用户级线程的优势：

调度依赖于应用程序
线程切换不需要内核模式权限
用户级线程中用于线程管理的库过程是本地过程
用户级线程创建和管理速度快
用户级线程可以在任何操作系统上运行

用户级线程的劣势：

在典型操作系统中，大多数系统调用会阻塞整个进程
多线程应用程序不支持多处理

因此选项 (A) 正确。

47

考虑一个包含七个进程（A 到 G）和六种资源（R 到 W）的系统。
资源所有权如下：

进程 A 持有 R，并请求 T
进程 B 未持有任何资源，但请求 T
进程 C 未持有任何资源，但请求 S
进程 D 持有 U，并请求 S 和 T
进程 E 持有 T，并请求 V
进程 F 持有 W，并请求 S
进程 G 持有 V，并请求 U

该系统是否发生死锁？如果是，请指出哪些进程陷入死锁。（）

正确答案：C

解析

资源请求链分析
- 进程 D → T → E → V → G → U → D 形成闭环：
  - D 持有 U，请求 T（被 E 占用）
  - E 持有 T，请求 V（被 G 占用）
  - G 持有 V，请求 U（被 D 占用）
- 此闭环满足死锁的四个必要条件（互斥、持有并等待、不可抢占、循环等待）。
排除无关进程
- A 请求 T 被 E 阻塞，但 A 未参与闭环。
- B 请求 T 被 E 阻塞，但 B 未持有任何资源。
- C 请求 S 被 D/F 阻塞，但 C 未持有资源。
- F 请求 S 被 D/C 阻塞，但 F 未参与闭环。
结论
只有 D、E、G 三者构成闭环且相互等待，因此它们陷入死锁。

48

一个 CPU 调度算法决定了其已安排进程的执行顺序。给定 n 个进程在单个处理器上进行调度，可能有多少种不同的调度顺序？

正确答案：C

对于 n 个进程在单个处理器上的调度，可能存在 n! 种不同的调度顺序。
示例：假设操作系统有 4 个进程 P1、P2、P3 和 P4 需要调度。调度第一个进程时有 4 种选择，从剩余三个进程中可选 3 种，依此类推。因此总共有 4×3×2×1=4! 种调度方式。

选项（C）正确。

49

进程在遇到 I/O 指令后所处的状态是（）

正确答案：B

解析

就绪状态：进程刚被创建时，会被放入就绪队列
运行状态：当进程开始执行时，处于运行状态
阻塞状态：一旦进程开始进行输入/输出操作，它会进入阻塞状态

50

以下哪种策略用于解决优先级反转问题？（）

正确答案：A

解析

优先级反转是调度中的一个场景，当高优先级进程被低优先级进程间接抢占，从而导致进程相对优先级的倒置。
解决方案：通过暂时提升低优先级进程的优先级，使其无法抢占高优先级进程，即可消除此问题。
结论：选项 (A) 正确。

51

考虑一个拥有十二个磁带驱动器的系统，其中包含三个进程 P1、P2 和 P3。
进程 P1 最多需要十个磁带驱动器，进程 P2 最多需要四个磁带驱动器，进程 P3 最多需要九个磁带驱动器。假设在时间 t1 时，进程 P1 持有五个磁带驱动器，进程 P2 持有两个磁带驱动器，进程 P3 持有三个磁带驱动器。此时系统处于（）。

正确答案：B

解析

进程需求分析
- P1 当前持有 5 个磁带驱动器，还需 5 个（共需 10 个）
- P2 当前持有 2 个磁带驱动器，还需 2 个（共需 4 个）
- P3 当前持有 3 个磁带驱动器，还需 6 个（共需 9 个）
系统资源状态
- 总驱动器数：12 个
- 已分配：10 个（5+2+3）
- 剩余空闲：2 个
资源分配逻辑
- 剩余 2 个可分配给 P2，满足其需求后释放 4 个驱动器
- 释放的 4 个仍无法满足 P1（需 5 个）或 P3（需 6 个）
- 无足够资源继续推进其他进程
结论
系统无法找到一条安全序列，因此处于 不安全状态
所以选项 (B) 是正确的。

52

在操作系统中，操作的不可分割性意味着（）：

正确答案：C

解析：

不可分割性（原子性）的核心特征是操作在执行过程中不会被中断
选项分析：
- A 错误：可分割的操作才可能发生中断
- B 错误：竞态条件通常出现在非原子操作场景
- C 正确：不可分割性保证了处理器无法抢占当前执行的操作
- D 错误：并非所有选项都成立
结论： 不可分割性通过禁止处理器抢占，确保操作序列的完整性和一致性，因此选项（C）正确

53

就绪队列中有三个进程。当当前运行的进程请求 I/O 时，会发生多少次进程切换？（）

正确答案：A

解析：

当前运行的进程发起 I/O 请求后，会从运行状态转为阻塞状态
操作系统会从就绪队列中选择一个进程（通常为队首进程）投入运行
此过程涉及两次状态变更（运行→阻塞 + 就绪→运行），但实际进程切换操作仅发生 1 次

选项（A）正确。

54

以下哪项是操作系统中有效进程状态转换的正确定义？（）

正确答案：B

解析

进程状态转换图（抢占式调度）

选项 1：唤醒：就绪 → 运行
错误。当进程被唤醒时，其状态应从阻塞状态转为就绪状态，而非从就绪到运行。
选项 2：调度：就绪 → 运行
正确。调度器会根据明确算法，将 CPU 分配给就绪队列中的某个进程。
选项 3：阻塞：就绪 → 运行
错误。进程被阻塞通常是因为被其他进程抢占或因 I/O 操作。此时进程状态应从运行状态转为阻塞状态。
选项 4：时间片耗尽：就绪 → 运行
错误。当进程执行时间片到期时，定时器中断会使其状态从运行状态转为就绪队列。

结论

因此，选项 (B) 正确。

55

下列配对的正确匹配是（）

(A) 磁盘检查 (1) 轮转法
(B) 批处理 (2) 扫描算法
(C) 分时 (3) 后进先出
(D) 栈操作 (4) 先进先出

正确答案：D

选项 (D) 正确：

A: 磁盘检查 - (2) 磁盘检查使用多种扫描算法，如 FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK 等。
B: 批处理 - 在批处理中，进程严格按照先进先出（FIFO）顺序执行。
C: 分时 - 在轮转调度算法中，进程以分时方式执行 CPU 任务，每个进程有固定的时间片。
D: 栈操作 - 栈遵循后进先出（LIFO）原则。

56

考虑三个 CPU 密集型进程，它们分别需要 10、20 和 30 个时间单位，并且在时间 0、2 和 6 到达。如果操作系统实现最短剩余时间优先调度算法，需要多少次上下文切换？（不计算时间零点和结束时的上下文切换。）

正确答案：B

解析：
根据最短剩余时间优先（SRTF）调度规则，每次选择剩余时间最短的进程执行。具体过程如下：

时间 0-2：进程 P1（需 10 单位）开始执行。
时间 2：进程 P2 到达（剩余时间 20），当前 P1 剩余 8 单位。由于 8 < 20，P1 继续执行。
时间 6：进程 P3 到达（剩余时间 30），此时 P1 剩余 4 单位。仍选择 P1 执行。
时间 6：P1 完成（总耗时 6 单位）。此时 P2 剩余 20，P3 剩余 30。选择 P2 执行。
时间 6-16：P2 执行 10 单位后，剩余 10。此时 P3 剩余 30，P2 继续执行。
时间 16：P2 完成。此时 P3 剩余 30，开始执行至结束。

上下文切换分析：

第一次切换：P1 被 P2 抢占（时间 6）。
第二次切换：P2 被 P3 抢占（时间 16）。

最终共发生 2 次上下文切换。

57

进程是（）：

正确答案：C

解析

进程是指正在执行的程序。当需要执行某个程序时，其进程映像会被创建在主存中，并被放入就绪队列。随后 CPU 会分配给该进程并开始执行。

选项分析
- A. 磁盘上保存的高级语言程序 → 属于静态存储的源代码或编译后的可执行文件
- B. 主存中的内容 → 泛指内存数据，未体现动态执行特性
- C. 正在执行的程序 → 符合进程的定义（动态执行实体）
- D. 辅存中的作业 → 指待处理的作业，尚未进入内存

因此，选项（C）正确。

58

在操作系统中，哪种操作系统的名称是指能够及时读取并响应事件的？（）

正确答案：C

解析：

实时操作系统（RTOS）的核心特性是在严格的时间限制内完成事件处理
其设计目标是确保关键任务在截止时间前获得确定性响应
与普通分时系统不同，实时系统对响应延迟有可预测性和可靠性要求
常见应用场景包括工业控制、航空航天、医疗设备等对时效性敏感的领域

选项（C）正确。

59

Fork 系统调用的功能是（）

正确答案：D

fork() 通过复制调用进程来创建一个新进程。新进程（称为子进程）是调用进程（称为父进程）的完全副本，但以下情况除外：

子进程拥有自己唯一的进程 ID，且该 PID 与任何现有进程组的 ID 都不匹配。
子进程的父进程 ID 与父进程的进程 ID 相同。
子进程不会继承父进程的内存锁和信号量调整。
子进程不会从父进程继承未完成的异步 I/O 操作，也不会继承父进程的任何异步 I/O 上下文。

因此，选项 (D) 正确。

60

哲学家就餐问题是一个（）

正确答案：B

解析：用餐哲学家问题是一个经典 IPC 问题。
结论：选项 (B) 正确。

61

处于阻塞状态的任务（）

正确答案：D

当进程请求了某些输入/输出并正在等待资源时，它会处于等待或阻塞状态。

因此，选项 (D) 是正确的。

62

在使用非抢占式调度的系统中，就绪队列中有四个进程，其预计运行时间分别为 5、18、9 和 12。应按照什么顺序运行这些进程以最小化等待时间（）？

正确答案：B

解析：

进程应按最短作业优先（SJF）的方式执行，以获得最低的等待时间。
因此，正确的顺序是 5、9、12、18。
选项 (B) 正确。

63

在某个计算时刻，计数信号量的值为 10。随后对该信号量执行了 12 次 P 操作和 “x” 次 V 操作。若信号量的最终值为 7，则 x 的值为（）：

正确答案：B

解析过程：

初始信号量值为 10
执行 12 次 P 操作后： $$ 10 - 12 = -2 $$
执行 x 次 V 操作后： $$ -2 + x = 7 \implies x = 9 $$

结论： 因此选项（B）正确。

64

考虑以下关于采用抢占式调度系统中进程状态转换的陈述：

I. 运行态进程可以转为就绪态。
II. 就绪态进程可以转为运行态。
III. 阻塞态进程可以转为运行态。
IV. 阻塞态进程可以转为就绪态。

以上陈述中哪些是正确的？（）

正确答案：C

解析：

根据采用抢占式调度系统的进程状态转换规则：阻塞态进程不能直接转为运行态。

因此，只有陈述 I、II 和 IV 是正确的。选项 (C) 正确。

65

在某一计算时刻，计数信号量的值为 7。随后对该信号量执行了 20 次 P（等待）操作和 15 次 V（信号）操作。该信号量的最终值是多少？（）

正确答案：C

初始值：7
执行 20 次 P 操作后：7 – 20 = -13
执行 15 次 V 操作后：-13 + 15 = 2
因此，选项 C 正确。

66

进程 P1 和 P2 使用以下代码中的 critical_flag 实现互斥。假设主程序中将 critical_flag 初始化为 FALSE。

get_exclusive_access() {
    if (critical_flag == FALSE) {
        critical_flag = TRUE;
        critical_region();
        critical_flag = FALSE;
    }
}

考虑以下两个陈述：

i. P1 和 P2 可能同时访问临界区。
ii. 此方法可能导致死锁。

以下哪项正确？（）

正确答案：C

关键分析
- 当 P1 执行至 critical_flag = TRUE; 后被中断，P2 检查 critical_flag 仍为 FALSE，因此可进入临界区。此时两个进程同时处于临界区，验证了 (i) 的正确性。
- 关于 (ii)，由于每次进入临界区后都会重置 critical_flag 为 FALSE，不存在标志位为 TRUE 而无进程占用的场景，因此不会发生死锁。
结论
陈述 (i) 正确，陈述 (ii) 错误。

67

考虑以下三个线程 T1、T2 和 T3 在单处理器上执行，使用三个二进制信号量变量 S1、S2 和 S3 进行同步，通过标准的 wait() 和 signal() 操作。线程可以在任何顺序和任何时间进行上下文切换。哪种信号量初始化方式会打印出序列 BCABCABCA…？


while(true) {
    wait(S3);
    print("C");
    signal(S2);
}


while(true) {
    wait(S1);
    print("B");
    signal(S3);
}


while(true) {
    wait(S2);
    print("A");
    signal(S1);
}

正确答案：C
若初始时 S1 = 1，S2 = 0，S3 = 0，则进程 T2 可成功执行 wait(S1);，而 T1 和 T3 分别卡在 wait(S3); 和 wait(S2); 上。T2 打印 B 后执行 signal(S3)，随后卡在 wait(S1);（此过程中打印 B）。此时进程 T1 可成功执行 wait(S3);，然后打印“C”，接着执行 signal(S2); 并卡在 wait(S3);（此过程中打印 C）。之后进程 T3 可成功执行 wait(S2);，打印“A”，再执行 signal(S1); 并卡在 wait(S2);（此过程中打印 A）。此后 T2 又可成功执行 wait(S1);。该过程不断重复，最终输出序列为 BCABCABCA…。因此选项 C 是正确答案。

68

屏障（Barrier）是一种同步构造，其中一组进程需要进行全局同步。即集合中的每个进程都必须到达屏障并等待其他所有进程也到达后，所有进程才能一起离开屏障。假设集合中进程数量为三个，S 是一个二进制信号量，具有常规的 P 和 V 操作。考虑以下带有行号的 C 语言实现：

void barrier(void) {
    1: P(S);
    2: process_arrived++;
    3: V(S);
    4: while(process_arrived != 3);
    5: P(S);
    6: process_left++;
    7: if(process_left == 3){
    8:     process_arrived = 0;
    9:     process_left = 0;
   10: }
   11: V(S);
}

变量 process_arrived 和 process_left 在所有进程中共享，并初始化为零。在并发程序中，当三个进程需要进行全局同步时会调用该屏障函数。

以下哪一项可以修正该实现中的问题？（）

正确答案：B

解析：

问题本质：当前实现存在竞态条件，当多个进程重复调用屏障时，process_arrived 可能超过 3，导致后续进程无法正常退出屏障。
关键逻辑缺陷：
- 第 2 行 process_arrived++ 需要确保仅在首次进入屏障时执行。
- 当 process_arrived 和 process_left 重置为 0 后，若未阻塞新进程，会导致计数器再次溢出。

选项 B 的修正机制：

// 修改后的伪代码示意
void barrier(void) {
    if (process_arrived != 0) {
        P(S); // 等待前一轮屏障完成
    }
    // 原有逻辑...
}

通过在屏障开始处添加对 process_arrived 是否为 0 的判断，可确保新进程不会干扰上一轮的同步状态，从而避免死锁。

其他选项分析：
- A 选项直接减少计数器，无法解决多轮同步的问题。
- C 选项禁用上下文切换违背并发设计原则。
- D 选项改变变量作用域无法消除共享资源竞争。

3 - 死锁

1

一台计算机有六个磁带驱动器，有 n 个进程竞争使用它们。每个进程可能需要两个驱动器。为了使系统处于无死锁状态，n 的最大值是多少（）？

正确答案：B

解析：

已知磁带驱动器总数为 6，每个进程需要 2 个驱动器。
极端情况分析：若每个进程先被分配 1 个驱动器，则最多可分配 6 个进程。此时所有进程均持有 1 个资源并等待第 2 个资源，形成循环等待，必然发生死锁。
避免死锁策略：根据银行家算法原理，为防止死锁需预留至少一个资源供系统调度。因此需减少 1 个进程，即 $ n_{\text{max}} = 6 - 1 = 5 $。

综上，选项 (B) 正确。

2

每个进程 Pi（i=1…9）的代码如下：

repeat
    P(mutex)
    {Critical section}
    V(mutex)
forever

P10 的代码与此相同，但将 P(mutex) 替换为 V(mutex)。在任意时刻，最多有多少个进程可以同时处于临界区？

正确答案：D

分析过程

常规进程行为
- 初始时互斥量值设为 1，因此每次只能允许一个进程进入临界区。
- 假设 P1 进入临界区后，其余进程（P2-P9）均因 P(mutex) 操作被阻塞。
P10 的特殊作用
- P10 的代码通过 V(mutex) 操作释放互斥量资源。
- 每次执行 V(mutex) 会唤醒一个阻塞进程，使其进入临界区。
- 由于 P10 持续运行，其不断执行 V(mutex) 可逐步解除所有阻塞进程。
最大并发数推导
- 最终所有 9 个常规进程（P1-P9）均可进入临界区。
- 加上 P10 自身，理论上最多有 10 个进程 同时处于临界区。

补充说明

循环结构保证 P10 永远执行，持续提供资源释放能力。
题目要求的是“可能存在的最大值”，因此答案为 10。

因此选项 (D) 正确。

3

解决“就餐哲学家问题”并避免死锁的一种方法是（）：

正确答案：C

在“就餐哲学家问题”中，通过让某一位特定哲学家先拿左边的叉子再拿右边的叉子，同时让其他所有哲学家先拿右边的叉子再拿左边的叉子，可以避免死锁条件。

选项 (C) 是正确的。

4

某计算机系统使用银行家算法处理死锁。其当前状态如下表所示，其中 P0、P1、P2 是进程，R0、R1、R2 是资源类型。


     R0  R1  R2
P0   4   1   2 
P1   1   5   1 
P2   1   2   3

最大需求


     R0   R1   R2
P0   1    0    2 
P1   0    3    1 
P2   1    0    2

当前分配量


R0    R1    R2
2     2     0

系统可用

a) 证明系统可以处于该状态；
b) 当进程 P0 请求一个 R1 类型资源时，系统会如何处理？

5

一个系统共享 9 个磁带驱动器。进程的当前分配和最大需求如下所示：以下哪项最能描述系统的当前状态？（）

进程	当前分配	最大需求
P1	3	7
P2	1	6
P3	3	5

正确答案：C

解析

资源分配分析：
- 系统总磁带驱动器：9 个
- 已分配数量：3 (P1) + 1 (P2) + 3 (P3) + 0 (P4) = 7 个
- 剩余可用资源：9 - 7 = 2 个
资源分配顺序：
1. 优先满足 P3（需求 2 个）→ 可用资源更新为 5
2. 满足 P2（需求 5 个）→ 可用资源更新为 6
3. 满足 P1（需求 6 个）→ 可用资源更新为 9
最终问题：
- 进程 P4 需求为 10 个，但系统最多可提供 9 个 → 无法满足
- 因此系统处于 不安全状态，且存在 死锁风险

选项（C）正确。

6

考虑一个系统中有 3 个进程共享 4 个同类型资源实例。每个进程最多可以请求 K 个实例。资源实例只能一次请求或释放一个。始终避免死锁的最大 K 值是（）。

正确答案：B
已知：进程数（P）= 3，资源数（R）= 4。
无死锁条件为：R ≥ P(N − 1) + 1
其中 R 表示总资源数，P 表示进程数，N 表示每个资源的最大需求量。
代入得：4 ≥ 3(N − 1) + 1 → 3 ≥ 3(N − 1) → 1 ≥ (N − 1) → N ≤ 2
因此，始终避免死锁的最大 K 值为 2。选项 (B) 正确。

7

在一个系统中，存在三种资源类型：E、F 和 G。四个进程 P0、P1、P2 和 P3 并发执行。初始时，进程通过名为 Max 的矩阵声明其最大资源需求。例如，Max[P2, F] 表示 P2 所需的最大 F 资源实例数。任意状态下分配给各进程的资源实例数由名为 Allocation 的矩阵给出。

考虑一个系统状态，其 Allocation 矩阵如下所示，且当前可用资源仅包含 3 个 E 实例和 3 个 F 实例。

从死锁避免的角度来看，以下哪一项是正确的？（）

正确答案：A

根据银行家算法：

初始可用资源为 (3, 3, 0)
可满足 P0 或 P2 的需求，选择 P0 <3, 3, 0>
- 完成后资源变为 (3, 3, 0)+(1, 0, 1)=(4, 3, 1)
选择 P2 <0, 3, 0>
- 完成后资源变为 (4, 3, 1)+(1, 0, 3)=(5, 3, 4)
选择 P1 <1, 0, 2>
- 完成后资源变为 (5, 3, 4)+(1, 1, 2)=(6, 4, 6)
选择 P3 <3, 4, 1>
- 完成后资源变为 (6, 4, 6)+(2, 0, 0)=(8, 4, 6)

安全序列：P0→P2→P1→P3
因此选项 (A) 正确。

8

Dijkstra 银行家算法解决了什么问题？（）

正确答案：D

解析

银行家算法是荷兰计算机科学家 Edsger Dijkstra 提出的一种经典算法
属于 死锁避免（Deadlock Avoidance）策略的核心实现
通过动态检测资源分配请求是否会导致系统进入不安全状态，从而决定是否允许该请求
在进程申请资源时，会预先模拟分配后系统的安全性，若存在安全序列则批准请求，否则拒绝
与死锁预防不同，它允许死锁条件存在但通过谨慎的资源分配策略避免进入死锁状态

9

单个资源时会发生死锁吗？（）

正确答案：D

发生死锁需要满足以下 4 个条件：

互斥（Mutual Exclusion）
不可抢占（No pre-emption）
持有并等待（Hold and wait）
循环等待（Circular wait）

当资源只有一个时，持有并等待和循环等待的条件会被消除。假设进程不能无限期占用资源，则每当一个进程执行完毕后，另一个进程就能获得该资源。因此死锁不可能发生。

所以选项 (D) 正确。

10

以下哪项不是死锁的必要条件？（）

正确答案：B

死锁发生的四个必要条件为：

互斥：资源不能共享，一次只能被一个进程占用
不可抢占：资源只能由持有它的进程主动释放
持有并等待：进程在等待新资源时不会释放已持有的资源
循环等待：存在一个进程链，每个进程都在等待下一个进程所持有的资源

选项 (B) 正确。

11

系统共有 9 个某类资源，当前处于安全状态，如下表所示。以下哪个进程执行顺序是安全的？（）

Process	Used	Max
P1	2	7
P2	1	6
P3	2	5
P4	1	4

正确答案：D

应用银行家算法，各进程的 Need 矩阵为：

Process	Used	Max	Need
P1	2	7	5
P2	1	6	5
P3	2	5	3
P4	1	4	3

当前可用资源数 = 可用资源 - 已分配资源 = 9 - 6 = 3

排除逻辑：

若首先满足 P4 的请求，则其执行后最多释放 4 个资源（1+3）
后续分配给 P1 或 P2（两者均需 5 个资源）时：
- 当前可用资源 4 < 需求 5 → 无法满足需求
因此选项 (A)、(B)、(C) 均被排除

✅ 选项 (D) 正确

12

当进程因死锁而回滚时，可能产生的负面作用是（）

正确答案：A

当进程因死锁而回滚时，产生的负面作用是饥饿。

回滚操作可能导致进程重新进入死锁状态
此时进程可能需要无限期等待资源
最终形成资源分配无法满足的饥饿现象

其他选项分析：

设备利用率低属于系统性能问题，与死锁回滚无直接关联
周期窃取（Cycle Stealing）是 DMA 技术中的概念，与死锁处理无关
系统吞吐量受多种因素影响，但并非死锁回滚的直接后果

13

考虑一个拥有 m 个相同类型资源的系统。这些资源由三个进程 A、B、C 共享，它们的峰值需求分别为 3、4、6。确保死锁永不发生的最小 m 值是（）。

正确答案：A

解析

进程 P1 的资源需求 R₁ = 3
进程 P2 的资源需求 R₂ = 4
进程 P3 的资源需求 R₃ = 6

确保死锁永不发生的最小资源数计算公式为：
(R₁ - 1) + (R₂ - 1) + (R₃ - 1) + 1 = (3 - 1) + (4 - 1) + (6 - 1) + 1 = 11

选项 (A) 正确。

14

在死锁的四个必要条件中，哪个条件要求进程对其所需的资源声明独占控制？（）

正确答案：B

互斥是指一个或多个资源为非共享资源（同一时间仅允许一个进程使用），即进程对其所需的资源声明独占控制。

因此，选项 (B) 是正确的。

15

考虑一个拥有相同类型 n 资源的系统。这些资源由三个进程 A、B、C 共享，它们的峰值需求分别为 3、4 和 6。问当 n 取何值时不会发生死锁？（）

正确答案：D

解析：
根据死锁预防原则，系统要避免死锁需满足以下条件：

各进程最大需求减 1 之和 + 1 ≤ 资源总数 $$ \text{所需最少资源数} = (3-1) + (4-1) + (6-1) + 1 = 11 $$
当资源总数n ≥ 11时，系统始终存在安全分配序列

因此选项 (D) 正确。

16

考虑以下进程及其资源需求情况：

进程	资源类型 1: 已分配	资源类型 1: 最大需求	资源类型 2: 已分配	资源类型 2: 最大需求
P1	1	2	1	3
P2	1	3	1	2
P3	2	4	1	4

假设系统中共有资源类型 1 的实例 5 个，资源类型 2 的实例 4 个。预测该系统的状态（）。

正确答案：C

进程	资源类型 1: 已分配	资源类型 1: 最大需求	资源类型 1: 需求	资源类型 2: 已分配	资源类型 2: 最大需求	资源类型 2: 需求
P1	1	2	1	1	3	2
P2	1	3	2	1	2	2
P3	2	4	2	1	4	3

可用资源
- 类型 1:5 - 4 = 1
- 类型 2:4 - 3 = 1

当前仅有的 1 个类型 1 和 1 个类型 2 资源无法满足任何进程的需求，因此系统处于不安全状态。
选项 (C) 正确。

17

考虑以下系统运行 $n$ 个进程的快照。进程 $i$ 持有 $X_i$ 个资源 $R$ 的实例，$1 \le i \le n$。当前，所有 $R$ 的实例都被占用。此外，对于所有 $i$，进程 $i$ 在持有其已有的 $X_i$ 实例的同时，还请求了额外的 $Y_i$ 实例。恰好存在两个进程 $p$ 和 $q$，使得 $Y_p = Y_q = 0$。以下哪一项可以作为保证系统不会进入死锁状态的必要条件？

正确答案：B
由于 $p$ 和 $q$ 都不需要额外资源，它们都可以完成并释放 $X_p + X_q$ 个资源，而无需请求任何额外资源。如果 $p$ 和 $q$ 释放的资源足以满足另一个等待 $Y_k$ 资源的进程的需求，则系统不会进入死锁状态。

18

一个系统包含三个程序，每个程序运行时需要三个磁带单元。为了确保系统永远不会发生死锁，该系统至少需要（）个磁带单元。

正确答案：B

解析

当系统拥有 6 个磁带单元时：
三个程序各持有 2 个资源，同时各自请求第 3 个资源，形成循环等待，最终导致死锁。
当系统拥有 7 个磁带单元时：
至少有一个程序可以获取全部 3 个所需资源，完成执行后释放资源，打破循环等待条件，从而避免死锁。

19

一个系统有 6 个相同的资源，N 个进程竞争这些资源。每个进程最多请求 2 个资源。以下哪个 N 的值可能导致死锁？（）

正确答案：D

当发生死锁时，进程数量应超过可用资源数量，导致每个进程持有至少一个资源并无限等待另一个资源的情况。在 6 个相同资源的情况下，每个进程最多请求 2 个资源。因此，要发生死锁，进程数量需要满足 $2 \times \text{进程数} > 6$。我们来验证选项：

(A) 1 个进程
$2 \times 1 = 2$ 资源，少于 6。不会死锁。
(B) 2 个进程
$2 \times 2 = 4$ 资源，仍少于 6。不会死锁。
(C) 3 个进程
$2 \times 3 = 6$ 资源，等于可用资源。如果每个进程请求 2 个资源并持有它们，则可能没有剩余资源供其他进程继续执行，从而导致死锁。
(D) 4 个进程
$2 \times 4 = 8$ 资源，超过可用资源。每个进程可能持有 2 个资源，导致没有剩余资源供其他进程继续执行，从而引发死锁。因此，可能导致死锁的 N 值是 (D) 4。

20

考虑以下在具有互斥资源的系统中防止死锁的策略：

I. 进程应在执行开始时获取所有所需资源。如果任何资源不可用，则释放已获取的所有资源。
II. 资源被唯一编号，进程只能按递增的资源编号请求资源。
III. 资源被唯一编号，进程只能按递减的资源编号请求资源。
IV. 资源被唯一编号。进程只能请求当前所持资源编号更大的资源。

上述哪些策略可用于防止死锁？（）

正确答案：D

解析

策略 I 通过要求进程一次性获取所有所需资源，避免了“持有并等待”这一死锁必要条件。
策略 II、III 和 IV 通过限制资源请求的顺序（递增、递减或仅允许请求更高编号的资源），消除了“循环等待”这一死锁必要条件。

21

操作系统按照以下方式处理资源请求：一个进程（请求某些资源，使用一段时间后退出系统）在其启动时被分配一个唯一的时间戳。这些时间戳随时间单调递增。我们用 TS(P) 表示进程 P 的时间戳。

当进程 P 请求资源时，操作系统执行以下操作：

(i) 如果没有其他进程当前持有该资源，操作系统将资源分配给 P。
(ii) 如果有某个进程 Q 持有该资源且 TS(Q) < TS(P)，操作系统使 P 等待该资源。
(iii) 如果有某个进程 Q 持有该资源且 TS(Q) > TS(P)，操作系统重启 Q 并将资源分配给 P。（重启意味着从进程中收回资源、终止它并以相同的时间戳重新启动）

当进程释放资源时，操作系统将资源分配给等待该资源的进程中时间戳最小的那个（如果有的话）。

a). 是否可能发生死锁？如果可能，请说明原因；否则，请证明。
b). 进程 P 是否可能发生饥饿？如果可能，请说明原因；否则，请证明。

22

临界区是程序的一个段，该程序段的功能是（）

正确答案：C

解析

临界区 是进程访问 共享资源 的程序部分
它包含 共享变量 或 共享数据
程序的其余部分称为 非临界区 或 剩余部分

选项（C）正确

23

考虑以下生产者 - 消费者同步问题的解决方案。共享缓冲区大小为 N。定义了三个信号量 empty、full 和 mutex，其初始值分别为 0、N 和 1。信号量 empty 表示缓冲区中可供消费者读取的可用槽位数量；信号量 full 表示缓冲区中可供生产者写入的可用槽位数量。代码中的占位符变量 P、Q、R 和 S 可以被分配为 empty 或 full。有效的信号量操作是：wait() 和 signal()。以下哪一组对 P、Q、R 和 S 的赋值能产生正确的解决方案？


do {
    wait(P);
    wait(mutex);
    // Add item to buffer
    signal(mutex);
    signal(Q);
} while(1);


do {
    wait(R);
    wait(mutex);
    // Consume item from buffer;
    signal(mutex);
    signal(S);
} while(1);

正确答案：C

已知 Empty = 0 Full = N Mutex = 1。由于 empty 信号量的初始值为 0，因此第一次尝试时无法对 empty 执行 wait 操作。注意：empty 信号量表示已填充的槽位数，因此生产者进程必须处理 empty 和 mutex 信号量；full 信号量表示空闲槽位数，因此消费者进程必须处理 full 和 mutex 信号量。

排除错误选项的原因：

选项 (A)：会导致饥饿，生产者无法获取 empty 信号量（初始为 0）。
选项 (B)：同样导致饥饿，消费者无法获取 full 信号量（初始为 N，但逻辑错误）。
选项 (D)：消费者因 empty 信号量初始为 0 而无法开始消费，实现错误。

选项 (C) 正确的原因：

P:empty：生产者通过 wait(empty) 确保缓冲区有空位可写入。
Q:full：消费者通过 wait(full) 确保缓冲区有数据可读取。
R:full：生产者写入后通过 signal(full) 增加可用数据量。
S:empty：消费者读取后通过 signal(empty) 增加可用空位。

该顺序保证了无死锁且无饥饿的同步机制。

24

以下哪项关于死锁预防和死锁避免方案的描述是不正确的？（）

正确答案：A

死锁预防：通过防止四个必要条件中的至少一个来避免死锁

互斥 – 可共享资源不需要互斥；不可共享资源必须满足互斥。
持有并等待 – 必须保证进程请求资源时不持有其他资源。要求进程在开始执行前申请所有所需资源，或仅允许进程在未持有任何资源时申请资源。这可能导致资源利用率低和饥饿问题。限制了请求的方式。
不可抢占 – 如果持有资源的进程请求无法立即分配的资源，则释放当前持有的所有资源。被抢占的资源加入进程等待列表。只有当进程重新获得旧资源和新请求资源后才能重启。
循环等待 – 对所有资源类型定义全序关系，并要求进程按递增顺序请求资源。

死锁避免：当调度器发现启动进程或授予资源请求可能导致未来死锁时，将拒绝该请求。死锁避免算法动态检查资源分配状态以确保不会出现循环等待条件。资源分配状态由可用资源数、已分配资源数及进程的最大需求定义。

选项解析：

(A) 在死锁预防中，如果结果状态是安全的，则资源请求总是被授予 → 错误。死锁预防通过确保四个必要条件之一不成立来处理死锁。即使结果状态是安全的，资源请求也可能不被授予（例如，为打破“持有并等待”条件）。
(B) 在死锁避免中，如果结果状态是安全的，则资源请求总是被授予 → 正确。死锁避免中，若状态安全则授予请求，因为此时进程可以继续持有其他资源。
(C) 死锁避免比死锁预防的限制更少 → 正确。死锁预防可能在安全状态下拒绝请求（如强制一次性申请所有资源），而死锁避免仅在状态不安全时拒绝。
(D) 死锁避免需要预先了解资源需求 → 正确。死锁避免需预测资源分配后的系统状态是否安全，因此需要进程声明最大资源需求。

25

如果系统中有三个进程 P1、P2 和 P3 正在运行，它们对同类资源的最大需求分别为 3、4 和 5。为确保系统永远不会发生死锁，至少需要多少个资源？

正确答案：D

设 P1 所需资源数为 $ R_1 = 3 $，
P2 所需资源数为 $ R_2 = 4 $，以此类推…
确保不会发生死锁所需的最小资源数：

$$ (R_1 - 1) + (R_2 - 1) + (R_3 - 1) + 1 = (3 - 1) + (4 - 1) + (5 - 1) + 1 = 2 + 3 + 4 + 1 = 10 $$

选项 (D) 是正确的。

26

考虑一个拥有 m 个同类资源的系统。这些资源由三个进程 A、B、C 共享，它们的峰值需求分别为 3、4、6。为确保系统永远不会发生死锁，m 的最小值是（）。

正确答案：A

解析：
避免死锁所需的最少资源数计算公式为：

$$ \sum_{i=1}^{y} (m_i - 1) + 1 $$

其中：

$ m_i $ 表示第 i 个进程的峰值需求
$ y $ 表示进程总数

代入本题数据：

$$ (3-1) + (4-1) + (6-1) + 1 = 2+3+5+1 = 11 $$

当系统资源数 ≥ 11 时，可保证至少有一个进程能获得全部所需资源并完成执行，释放其占用资源，从而避免死锁。因此选项 (A) 正确。

27

三个并发进程 X、Y 和 Z 分别执行访问和更新某些共享变量的不同代码段。进程 X 在进入代码段前对信号量 a、b 和 c 执行 P 操作（即 wait）；进程 Y 对信号量 b、c 和 d 执行 P 操作；进程 Z 对信号量 c、d 和 a 执行 P 操作。每个进程完成代码段的执行后，会对其三个信号量执行 V 操作（即 signal）。所有信号量均为二进制信号量，初始值为 1。以下哪一项表示进程调用 P 操作的无死锁顺序？

正确答案：B

解析：

选项 A 可能导致死锁
- 场景示例：进程 X 获取 a，进程 Y 获取 b，进程 Z 获取 c 和 d → 形成循环等待链（X 等待 b，Y 等待 c，Z 等待 a）
选项 C 可能导致死锁
- 场景示例：进程 X 获取 b，进程 Y 获取 c，进程 Z 获取 a → 形成循环等待链（X 等待 a，Y 等待 b，Z 等待 c）
选项 D 可能导致死锁
- 场景示例：进程 X 获取 a 和 b，进程 Y 获取 c → 形成相互等待（X 等待 c，Y 等待 a 或 b）
选项 B 是唯一无死锁的方案
- 完成顺序为 Z→X→Y
- 资源分配路径：Z 先获取 a/c/d → X 获取 b/a/c → Y 获取 b/c/d
- 不存在循环等待条件，满足银行家算法的安全序列要求

28

考虑一个具有 4 种资源的系统：R1（3 个单位）、R2（2 个单位）、R3（3 个单位）、R4（2 个单位）。系统采用非抢占式资源分配策略。在任意时刻，如果请求无法完全满足，则不会被处理。

有三个进程 P1、P2 和 P3 独立执行时的资源请求如下：


t=0: 请求 2 个单位的 R2  
t=1: 请求 1 个单位的 R3  
t=3: 请求 2 个单位的 R1  
t=5: 释放 1 个单位的 R2 和 1 个单位的 R1  
t=7: 释放 1 个单位的 R3  
t=8: 请求 2 个单位的 R4  
t=10: 完成

进程 P1


t=0: 请求 2 个单位的 R3  
t=2: 请求 1 个单位的 R4  
t=4: 请求 1 个单位的 R1  
t=6: 释放 1 个单位的 R3  
t=8: 完成

进程 P2


t=0: 请求 1 个单位的 R4  
t=2: 请求 2 个单位的 R1  
t=5: 释放 2 个单位的 R1  
t=7: 请求 1 个单位的 R2  
t=8: 请求 1 个单位的 R3  
t=9: 完成

进程 P3

若所有三个进程从时间 t=0 开始并发运行，以下哪项陈述是正确的？（）

正确答案：A

分析过程
1. 按照时间轴逐步模拟资源分配：
  - t=0: P1 获取 R2(2), P2 获取 R3(2), P3 获取 R4(1)
  - t=1: P1 获取 R3(1)
  - t=2: P2 获取 R4(1), P3 获取 R1(2)
  - t=3: P1 获取 R1(2)
  - t=4: P2 获取 R1(1)
  - t=5: P1 释放 R2(1) + R1(1)，此时可用资源 R2=1, R1=1
  - t=7: P1 释放 R3(1)，P3 获取 R2(1)
  - t=8: P1 获取 R4(2)，P3 获取 R3(1)
  - t=9: P3 完成
  - t=10: P1 完成
2. 关键验证点
  - 所有资源请求均能按需分配
  - 不存在循环等待条件（各进程最终释放全部资源）
  - 最终所有进程均完成执行
结论
根据死锁检测算法，系统始终处于安全状态，因此选择 A。

29

一个系统有 $n$ 个资源 $R_0, \cdots, R_{n-1}$ 和 k 个进程 P₀, …, Pₖ₋₁。每个进程 Pᵢ 的资源请求逻辑实现如下：

if (i % 2 == 0) {
    if (i < n) request Ri;
    if (i+2 < n) request Ri+2;
}
else {
    if (i < n) request Rn-i;
    if (i+2 < n) request Rn-i-2;
}

在以下哪种情况下可能发生死锁？（）

正确答案：B

选项 B 是答案

资源数量 n=21，进程数量 k=12

进程 {P₀, P₁,…,P₁₁} 发出以下资源请求：
R₀, R₂₀, R₂, R₁₈, R₄, R₁₆, R₆, R₁₄, R₈, R₁₂, R₁₀, R₁₀

示例解析
P₀ 请求 R₀（0%2==0 且 0 < 21）
P₁₀ 请求 R₁₀
P₁₁ 请求 R₁₀（n-i = 21-11 = 10）

死锁成因

由于不同进程请求相同的资源（如 R₁₀ 被 P₁₀ 和 P₁₁ 同时请求），当资源分配顺序不当且无法满足所有进程的请求时，可能发生死锁。

30

一个操作系统在管理三个进程 P0、P1 和 P2 对三种资源类型 X、Y 和 Z 的分配时，使用银行家算法进行死锁避免。下表展示了当前系统状态。其中，Allocation 矩阵显示了每个进程当前分配的每种资源数量，Max 矩阵显示了每个进程在其执行过程中所需的每种资源最大数量。

          Allocation          Max
         X   Y   Z         X   Y   Z
P0       0   0   1         8   4   3
P1       3   2   0         6   2   0
P2       2   1   1         3   3   3

目前仍有 3 个单位的 X 资源、2 个单位的 Y 资源和 2 个单位的 Z 资源可用。系统当前处于安全状态。考虑以下两个独立的额外资源请求：

REQ1: P0 请求 0 个 X 单位，
0 个 Y 单位和 2 个 Z 单位
REQ2: P1 请求 2 个 X 单位，
0 个 Y 单位和 0 个 Z 单位

以下哪一项是正确的？（）

正确答案：B

解析

这是当前的安全状态：

AVAILABLE（可用资源）：X=3，Y=2，Z=2

      MAX        ALLOCATION
    X  Y  Z       X  Y  Z
P0  8  4  3       0  0  1
P1  6  2  0       3  2  0
P2  3  3  3       2  1  1

现在，如果允许请求 REQ1，状态将变为：

AVAILABLE：X=3，Y=2，Z=0

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  3       8  4  0
P1  6  2  0       3  2  0       3  0  0
P2  3  3  3       2  1  1       1  2  2

在当前资源可用的情况下，我们可以满足 P1 的需求。状态将变为：

AVAILABLE：X=6，Y=4，Z=0

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  3       8  4  0
P1  6  2  0       3  2  0       0  0  0
P2  3  3  3       2  1  1       1  2  2

此时，由于缺少 Z 资源，我们无法满足 P0 或 P2 的需求。因此，系统将进入死锁状态。 ⇒ 我们不能允许 REQ1。

现在，在当前安全状态下，如果我们接受 REQ2：

AVAILABLE：X=1，Y=2，Z=2

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  1       8  4  2
P1  6  2  0       5  2  0       1  0  0
P2  3  3  3       2  1  1       1  2  2

在该资源可用情况下，可以服务 P1（也可以服务 P2）。状态变为： AVAILABLE：X=7，Y=4，Z=2

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  1       8  4  2
P1  6  2  0       5  2  0       0  0  0
P2  3  3  3       2  1  1       1  2  2

现在我们可以服务 P2。状态变为：

AVAILABLE：X=10，Y=7，Z=5

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  1       8  4  2
P1  6  2  0       5  2  0       0  0  0
P2  3  3  3       2  1  1       0  0  0

最后我们服务 P0。状态变为： AVAILABLE：X=18，Y=11，Z=8

      MAX        ALLOCATION       NEED
    X  Y  Z       X  Y  Z       X  Y  Z
P0  8  4  3       0  0  1       0  0  0
P1  6  2  0       5  2  0       0  0  0
P2  3  3  3       2  1  1       0  0  0

所得到的状态是一个安全状态。 ⇒ 可以允许 REQ2。

因此，只有 REQ2 可以被允许。所以，正确的选项是 B。

31

假设有 $n$ 个进程 $P_1, \cdots, P_n$ 共享 $m$ 个相同的资源单元，这些资源可以一次一个地被保留和释放。进程 $P_i$ 的最大资源需求为 $s_i$，其中 $s_i > 0$。以下哪一项是确保不会发生死锁的充分条件？

正确答案：C

解释：
要确保系统不会发生死锁，一个充分条件是所有进程的最大资源需求之和满足以下条件：

$$\sum_{i=1}^{n} s_i \le (m + n - 1)$$

原因：
- 如果总需求满足此条件，则至少存在一个进程能够获得所需的所有资源并完成执行。
- 该进程完成后会释放其占用的资源，使得其他进程有机会继续运行。
- 这样可以打破死锁的四个必要条件之一（循环等待），从而避免死锁的发生。

32

以下哪项不是有效的死锁预防方案？（）

正确答案：C

题目：以下哪项不是有效的死锁预防方案？

选项如下： A. 在请求新资源之前释放所有资源 B. 为资源唯一编号，并且永远不要请求比上次请求的编号更低的资源。 C. 在释放任何资源后，永不请求资源 D. 执行前分配所有所需资源解析

为了预防死锁，需要破坏死锁的四个必要条件之一：

互斥（资源不能被共享）
占有且等待（一个进程持有资源并等待其他资源）
不剥夺（已经分配的资源不能被强制剥夺）
循环等待（存在一个等待资源的环）

逐个分析选项：

A. 在请求新资源之前释放所有资源 → 破坏了占有且等待条件，是有效的预防策略。
B. 为资源唯一编号，并且永远不要请求比上次请求的编号更低的资源 → 避免了循环等待，也是经典的死锁预防方法。
C. 在释放任何资源后，永不请求资源 → 这个策略过于极端，实际上不可行，也不是有效的死锁预防方案。它限制了程序合理地分阶段申请资源的能力。
D. 执行前分配所有所需资源 → 这也是一种经典策略，称为一次性分配策略，可以避免死锁。

因此，C 选项不是有效的死锁预防方案。

33

考虑以下针对临界区问题的解决方案。共有 $n$ 个进程：$P_0, P_1, \cdots, P_{n-1}$。在代码中，函数 pmax 返回一个不小于其任何参数的整数。对于所有 i，t[i] 被初始化为零。关于上述解决方案，以下哪一项是正确的？（）

do {
    c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;
    for every j != i in {0,...,n-1} {
        while (c[j]);
        while (t[j] != 0 && t[j]<=t[i]);
    }
    Critical Section;
    t[i]=0;
    Remainder Section;
} while (true);

正确答案：A

解析

互斥性分析

互斥性得到满足：所有在进程 i 之前启动的其他进程 j 必须具有较小的值（即 t[j] < t[i]），因为函数 pMax() 返回一个不小于其任何参数的整数。
执行机制：当 j 进程退出临界区时，它会将 t[j]设为 0；随后循环会选择下一个进程。因此，当 i 进程进入临界区时，所有在 i 进程之前启动的进程 j 都不在其临界区中。
结论：同一时间只有一个进程在执行其临界区。

死锁与进展条件

死锁可能发生：由于 while (t[j] != 0 && t[j] <=t[i]) 这一条件，当 j 进程的值等于 i 进程的值（即 t[j] == t[i]）时可能发生死锁。
进展条件未满足：由于死锁的存在，进展条件也无法满足（即进展=无死锁），因为没有进程能够通过阻止其他进程来取得进展。

有界等待条件

有界等待未满足：如果 t[j] == t[i] 是可能的，则可能导致饥饿（即无限等待）。这种情况源于相同的原因——死锁的可能性导致无法保证有限次等待后进入临界区。

34

一个操作系统包含 3 个用户进程，每个进程需要 2 个资源单位 R。为确保永远不会发生死锁，R 的最小资源单位数是（）。

正确答案：C

总进程数为 3，每个进程需要 2 个资源单位。

如果我们给每个进程分配 1 个资源，则总资源数为 1+1+1=3，但此时必然会发生死锁，因为每个进程都持有 1 个资源并等待另一个资源。如果再增加 1 个资源（3+1=4），则死锁将不会发生（即当进程 1 完成执行后会释放 2 个资源，这 2 个资源可被其他进程使用）。

结论分析：

资源数 = 3：每个进程各持 1 个资源，形成循环等待 → 死锁
资源数 ≥ 4：至少有一个进程能获得全部所需资源并完成执行，释放资源供其他进程使用 → 避免死锁

因此，系统至少需要 4 个资源单位 才能保证不死锁。选项 (C) 正确。

35

进程 $P_1$ 和 $P_2$ 使用两个共享资源 $R_1$ 和 $R_2$。每个进程对每个资源的访问具有特定优先级。设 $T_{ij}$ 表示进程 $P_i$ 访问资源 $R_j$ 的优先级。若 $T_{ik}$ > $T_{jk}$，则进程 $P_i$ 可以从进程 $P_j$ 处抢占资源 $R_h$。

已知以下条件：

$T_{11} > T_{21}$
$T_{12} > T_{22}$
$T_{11} < T_{21}$
$T_{12} < T_{22}$

以下哪项条件能确保 P1 和 P2 永远不会发生死锁？（）

正确答案：C

关键分析

死锁预防核心：若所有资源始终分配给单个进程，则系统处于安全状态，无法形成循环等待。
条件解析：
- 当满足 (I) 和 (II) 时，R1 和 R2 同时分配给 P1
- 当满足 (III) 和 (IV) 时，R1 和 R2 同时分配给 P2
执行流程：
- 被分配资源的进程完成执行 → 释放全部资源 → 另一进程获得资源并继续执行
结论：
- 条件组合 (I)+(II) 或 (III)+(IV) 均可打破死锁必要条件（循环等待）
- 因此选项 C 正确

36

信号量用于解决以下哪些问题？（）

I. 竞态条件
II. 进程同步
III. 互斥
IV. 以上都不是

正确答案：B

信号量（Semaphore）是操作系统中用于协调多个进程访问共享资源的机制。其核心作用包括：

进程同步（II）
通过P/V操作（或称wait/signal），信号量可以控制进程执行顺序，确保某些操作按预期时序完成。
互斥（III）
当信号量初始值为 1 时，可作为互斥锁（Mutex）使用，保证同一时刻只有一个进程进入临界区。
竞态条件（I）的间接解决
虽然信号量本身不直接解决竞态条件（Race Condition），但通过实现互斥和同步，能有效避免因资源竞争导致的竞态问题。因此选项 I 的表述存在误导性。

综上，正确答案为 B（II 和 III）。

37

一个操作系统有 13 个磁带驱动器。现有三个进程 P1、P2 和 P3。P1 的最大需求为 11 个磁带驱动器，P2 为 5 个，P3 为 8 个。当前 P1 已分配 6 个，P2 已分配 3 个，P3 已分配 2 个。以下哪个执行序列代表安全状态（）？

正确答案：A

进程资源分配
- P1: 最大需求 11 / 当前分配 6
- P2: 最大需求 5 / 当前分配 3
- P3: 最大需求 8 / 当前分配 2
- 系统总资源：13 个磁带驱动器（已分配 11 个，剩余 2 个）
资源需求分析
- P1 需求：11 - 6 = 5 个
- P2 需求：5 - 3 = 2 个
- P3 需求：8 - 2 = 6 个
安全序列验证
1. 初始可用资源：2 个
  - 可满足 P2 的需求（2 ≤ 2），执行 P2 后释放 3 个 → 可用资源变为 5 个
2. 可用资源 5 个
  - 满足 P1 的需求（5 ≤ 5），执行 P1 后释放 6 个 → 可用资源变为 11 个
3. 可用资源 11 个
  - 满足 P3 的需求（6 ≤ 11），执行 P3 后释放 2 个 → 全部资源回收
结论
存在可行的安全序列 P2 → P1 → P3，因此选项 (A) 正确。

38

进程 P1 和 P2 存在生产者 - 消费者关系，通过一组共享缓冲区进行通信。


repeat
    获取一个空缓冲区
    填充数据
    返回一个满缓冲区
forever

P1 操作流程


repeat
    获取一个满缓冲区
    清空数据
    返回一个空缓冲区
forever

P2 操作流程

增加缓冲区数量可能会导致以下哪些结果？（）

I. 提高请求满足率（吞吐量）
II. 降低死锁发生的可能性
III. 提升实现正确性的便利性

正确答案：C

解析

I. 提高请求满足率（吞吐量）
增加缓冲区数量可以提升系统同时处理的数据量，因此会提高吞吐量。
II. 降低死锁发生的可能性
缓冲区数量与死锁概率无直接关联。
III. 提升实现正确性的便利性
更多缓冲区可能使同步逻辑更复杂。

结论：因此正确答案是 仅 I。

39

考虑一个拥有 m 个相同类型资源的系统。这些资源由三个进程 P1、P2 和 P3 共享，它们的峰值需求分别为 2、5 和 7 个资源。当 m 取何值时不会发生死锁？（）

正确答案：B

避免死锁的条件

系统总资源数需满足：
$ m \geq \text{各进程峰值需求之和} $
计算：
$ m \geq 2 + 5 + 7 = 14 $
因此选项 (B) 正确。

40

假设系统中有 4 个进程正在运行，共有 12 个资源 R 的实例。
每个进程的最大需求和当前分配如下：根据当前分配情况，系统是否处于安全状态？如果是，安全序列是什么？

进程	最大需求	当前分配
P1	8	3
P2	9	4
P3	5	2
P4	3	1

正确答案：C

解析

当前分配：P1=3，P2=4，P3=2，P4=1 → 总计 10 个资源
剩余资源：12 - 10 = 2 个
最大需求：
- P1: 5
- P2: 5
- P3: 3
- P4: 2

执行流程分析：

P4 执行：释放 3 个资源（当前分配 1，需释放 1）→ 剩余 2 + 1 = 3
P3 执行：消耗 3 个资源 → 剩余 3 - 3 = 0
P1/P2 执行：此时剩余 0 + 2（P3 释放）= 2 个资源，仍不足满足 P1/P2 需求
- 需等待 P3 完成后再释放 2 个资源（P3 当前分配 2）→ 剩余 2 + 2 = 4
- 此时仍不足 5 个资源，需继续等待
- 实际应为 P4 执行后释放 1 个资源（当前分配 1），剩余 2 + 1 = 3
- P3 执行后释放 2 个资源（当前分配 2），剩余 3 + 2 = 5
- 此时 P1 和 P2 各需 5 个资源，可任选其一先执行
- 优先选择 P1 → 顺序为 P4 → P3 → P1 → P2

结论：存在可行的安全序列 P4→P3→P1→P2，对应选项 (C) 正确。

41

考虑一个包含 n 个进程和 m 种资源类型的系统。检查系统是否处于安全状态的安全算法的时间复杂度为（）：

正确答案：D

该算法需要进行三重嵌套循环：

外层循环：遍历所有资源类型（m 次）
中层循环：遍历所有进程（n 次）
内层循环：每次分配检查时可能再次遍历所有进程（n 次）

因此总时间复杂度为 $O(m \times n \times n) = O(mn^2)$。

42

一个系统有四个进程和五个可分配资源。当前的分配、最大需求和可用资源如下：

进程	Allocated（已分配）	Maximum（最大需求）	Available（可用）
A	1 0 2 1 1	1 1 2 1 3	0 0 x 1 1
B	2 0 1 1 0	2 2 2 1 0
C	1 1 0 1 0	2 1 3 1 0
D	1 1 1 1 0	1 1 2 2 1

请计算使上述系统处于安全状态的最小 x 值是（）。

正确答案：D

分析过程：

当 x=1 时

进程 D 将执行并释放 1 1 2 2 1 个实例
此时其他进程均无法执行（A 需求 [0,1,0,0,2] 无法满足）

当 x=2 时

进程 D 执行并释放 1 1 3 2 1 个实例
随后进程 C 执行并释放 2 2 3 3 1 个实例
通过这些空闲实例：
- 进程 B 可以执行
- 进程 A 无法执行（其需求 5 个资源中的 2 个实例永远无法满足）

因此系统仍不处于安全状态。

结论

无论 x 取何值，系统都无法找到一条安全序列满足所有进程需求，故 选项 (D) 正确。

4 - CPU 调度

1

考虑三个进程（进程 ID 分别为 0、1、2），其 CPU 执行时间片分别为 2、4 和 8 个时间单位。所有进程在时间零点到达。采用最长剩余时间优先（LRTF）调度算法。当出现平局时，优先选择进程 ID 较小的进程。平均周转时间是（）：

正确答案：A

设这三个进程为 p0、p1 和 p2。它们将按以下顺序执行：p2 p1 p2 p1 p2 p0 p1 p2 p0 p1 p2
0 4 5 6 7 8 9 10 11 12 13 14
进程的周转时间是指从进程提交到其完成的总时间。

p0 的周转时间：12（12 - 0）
p1 的周转时间：13（13 - 0）
p2 的周转时间：14（14 - 0）

$$ \text{平均周转时间} = \frac{12 + 13 + 14}{3} = 13 $$

2

考虑三个同时到达的进程，其总执行时间分别为 10、20 和 30 个单位。每个进程首先花费 20% 的时间进行 I/O 操作，接着 70% 的时间进行计算，最后 10% 的时间再次进行 I/O 操作。操作系统使用最短剩余计算时间优先调度算法，在运行进程因 I/O 阻塞或完成计算周期时调度新进程。假设所有 I/O 操作可以尽可能重叠。CPU 空闲时间占总时间的百分比是多少？（）

正确答案：B

设三个进程为 p0、p1 和 p2，其执行时间分别为 10、20 和 30。p0 首先花费 2 个单位时间进行 I/O，7 个单位时间进行 CPU 计算，最后 1 个单位时间进行 I/O。p1 首先花费 4 个单位时间进行 I/O，14 个单位时间进行 CPU 计算，最后 2 个单位时间进行 I/O。p2 首先花费 6 个单位时间进行 I/O，21 个单位时间进行 CPU 计算，最后 3 个单位时间进行 I/O。

空闲   p0    p1     p2    空闲
0    2     9     23     44     47

总耗时：47 单位时间
空闲时间：2（初始 I/O） + 3（最终 I/O） = 5 单位时间
空闲时间占比：(5/47) × 100 ≈ 10.6%

关键分析：

进程按最短剩余计算时间优先调度
I/O 操作可并行执行，因此不影响 CPU 调度
时间线显示 CPU 在 [0,2) 和 [44,47) 区间空闲
总时间由最长计算链决定（p2 的 21 单位计算 + 其他进程的交错执行）

3

考虑三个 CPU 密集型进程，它们分别需要 10、20 和 30 个时间单位，并且到达时间分别为 0、2 和 6。如果操作系统实现最短剩余时间优先调度算法，需要多少次上下文切换？（不计算时间零点和结束时的上下文切换）

正确答案：B

设三个进程为 P0、P1 和 P2，其到达时间分别为 0、2 和 6，CPU 突发时间分别为 10、20 和 30。

调度过程如下：

时间 0：P0 是唯一可用进程，开始运行
时间 2：P1 到达，但 P0 剩余时间（8）仍小于 P1 的突发时间（20），继续执行
时间 6：P2 到达，此时 P0 剩余时间（4）仍小于 P2 的突发时间（30），继续执行
时间 10：P0 完成，此时 P1 剩余时间（20）小于 P2 的剩余时间（30），发生第一次上下文切换（P0 → P1）
时间 30：P1 完成，此时仅剩 P2 运行，发生第二次上下文切换（P1 → P2）

最终结论：

上下文切换发生在 P0 → P1 和 P1 → P2 两个时刻
总计 2 次上下文切换（不含初始启动和最终结束）

4

以下哪种进程调度算法可能导致饥饿（）：

正确答案：C

解析：

最短作业优先（SJF） 算法存在饥饿风险
当系统持续接收大量短作业时，长作业会因始终处于等待队列末尾而无法获得 CPU 资源
典型场景：若不断有新短作业到达，长作业可能无限期推迟执行
对比其他选项：
- FIFO 采用先来先服务原则，保证所有作业按顺序执行
- 轮转法通过时间片机制确保每个作业周期性获得执行机会

5

如果轮转算法的时间片非常大，那么它相当于（）。

正确答案：A
解析：
当时间片非常大时，每个进程在时间片内都能完成其任务，因此调度器会依次处理每个进程，相当于先来先服务（FCFS）调度算法。

6

以下关于 SJF（最短作业优先调度）的说法中，哪一个是错误的？（）

S1：它会导致最小的平均等待时间
S2：它可能导致饥饿

正确答案：D

解释：

SJF 和最短剩余时间优先算法 都可能导致饥饿。
- 当就绪队列中存在长进程，且持续有更短进程到达时，长进程可能长时间得不到执行。
SJF 的优点与局限性
- 在给定进程集合中，SJF 能提供最小的平均等待时间（最优）。
- 但实际应用中，难以准确预知下一个作业的执行时间。
更多细节可参考 进程调度 相关内容。

7

一种调度算法将优先级与进程的等待时间成正比分配。每个进程初始优先级为零（最低优先级）。调度器每 T 个时间单位重新评估进程优先级并决定下一个调度的进程。如果所有进程均无 I/O 操作且在时间零同时到达，以下哪项是正确的？（）

正确答案：B

该调度算法的工作方式类似于时间片大小为 T 的轮转调度。

当一个进程轮到执行并运行了 T 个时间单位后，其等待时间变为最小值
并在其他所有进程各获得 T 个时间单位的执行机会后再次轮到它执行

8

考虑表中的三个进程 P1、P2 和 P3。

Process	Arrival time	Time Units Required
P1	0	5
P2	1	7
P3	3	4

在 FCFS（先来先服务）和 RR2（时间片为 2 个时间单位的轮转调度）策略下，这三个进程的完成顺序是（）？

正确答案：C

FCFS 的顺序显然是 P1、P2、P3，排序 B、D 选项

RR2 调度过程解析：

时间片设置：固定为 2 个时间单位
进程分配顺序：
p1, p2, p1, p3, p2, p1, p3, p2, p2
关键时间点事件：
- t=2：p2 开始执行，p1 进入就绪队列
- t=3：p3 到达，加入就绪队列（此时队列顺序为 p1 → p3）
- t=4：重新执行 p1
- t=6：首次执行 p3
核心机制：涉及就绪队列管理与时间片轮转规则

所以 RR2 的完成顺序 为 P1、P3、P2

9

考虑以下三个进程 P0、P1 和 P2 的到达时间与执行时间表：

进程	到达时间	执行时间
P0	0 ms	9 ms
P1	1 ms	4 ms
P2	2 ms	9 ms

使用 抢占式最短作业优先调度算法。仅在进程到达或完成时进行调度。这三个进程的平均等待时间是多少？（）

正确答案：A

解析

根据抢占式最短作业优先调度规则：

时间线分析：
- t=0ms：仅 P0 可运行，开始执行。
- t=1ms：P1 到达，剩余执行时间为 8ms（P0 剩余 8ms），P1 执行时间 4ms 更短 → 抢占 P0。
- t=2ms：P2 到达，P1 剩余 3ms，P2 执行时间 9ms → 继续执行 P1。
- t=5ms：P1 完成，此时 P0 剩余 8ms，P2 剩余 9ms → 选择 P0（剩余时间更短）。
- t=13ms：P0 完成，此时 P2 剩余 9ms → 开始执行 P2。
- t=22ms：P2 完成。
各进程完成时间：
- P0: 13ms
- P1: 5ms
- P2: 22ms
等待时间计算：
- 等待时间 = 完成时间 - 到达时间 - 执行时间
- P0: 13 - 0 - 9 = 4ms
- P1: 5 - 1 - 4 = 0ms
- P2: 22 - 2 - 9 = 11ms
平均等待时间：(4 + 0 + 11) / 3 = 5.0ms

10

以下哪些说法是正确的？（）

I. 最短剩余时间优先调度可能导致饥饿
II. 抢占式调度可能导致饥饿
III. 轮转法（Round Robin）在响应时间上优于先来先服务（FCFS）

正确答案：D

I) 最短剩余时间优先调度是最短作业优先调度的抢占式版本。在 SRTF 中，首先调度 CPU 执行时间片最短的作业。由于这一过程，较短的进程持续到达可能导致长 CPU 执行时间片的进程永远无法获得 CPU，从而引发饥饿。

II) 抢占式调度意味着一个进程在执行完成前可能被中断，其他进程开始执行。被中断的进程之后可以从中断处继续执行。在抢占式调度中，假设进程 P1 正在 CPU 中执行，随后更高优先级的进程 P2 进入就绪队列，则 P1 会被抢占，P2 开始执行。如果就绪队列中持续有更高优先级的进程到达，P1 始终被抢占，可能发生饥饿。

III) 轮转法比 FCFS 提供更好的响应时间。在 FCFS 中，进程执行直到其全部时间片用完；而在轮转法中，进程仅执行一个时间片长度。因此，轮转法调度通过规定时间间隔后为所有进程分配 CPU，从而改善了响应时间。

综上，I、II、III 均正确，对应选项 (D)。

11

在以下单处理器系统的进程状态转换图中，假设就绪状态中始终存在一些进程。现在考虑以下陈述：

I. 如果一个进程执行了转换 D，则会立即导致另一个进程执行转换 A。
II. 当另一个进程 P1 处于运行状态时，处于阻塞状态的进程 P2 可以执行转换 E。
III. 操作系统使用抢占式调度。
IV. 操作系统使用非抢占式调度。

以上哪些陈述是正确的？（）

正确答案：C

解析

A 是错误的，并没有规定一个进程终止后，另一个进程会立刻进入就绪（Ready）状态。这取决于是否有可运行的进程以及长期调度器的调度情况。

B 是正确的。阻塞状态的进程变为就绪状态，与是否有进程正在运行没有依赖关系。

C 是正确的，D是错误的。因为存在从运行态到就绪态的 C 转换。

所以答案选择 C。

12

一个操作系统使用最短剩余时间优先（SRTF）进程调度算法。考虑以下进程的到达时间和执行时间：

Process	执行时间	到达时间
P1	20	0
P2	25	15
P3	10	30
P4	15	45

进程 P2 的总等待时间是多少？（）

正确答案：B

解析：

算法原理
最短剩余时间（SJF）是一种抢占式调度方法，始终选择剩余执行时间最短的进程运行。当新进程到达时，若其剩余时间比当前运行进程更短，则立即抢占 CPU。
甘特图执行流程
- 0-15：仅 P1 存在，运行至时间 15
- 15-20：P2 到达（剩余 25），P1 剩余 15，继续运行至完成
- 20-30：P2 开始运行（剩余 25）
- 30-40：P3 到达（剩余 10），抢占 P2，P3 运行至完成
- 40-45：P2 恢复运行（剩余 15），继续执行
- 45-55：P4 到达（剩余 15），P2 剩余 10，继续运行至完成
关键计算
- 完成时间：55
- 周转时间 = 完成时间 - 到达时间 = 55 - 15 = 40
- 等待时间 = 周转时间 - 执行时间 = 40 - 25 = 15

13

进程 A、B 和 C 各自执行一个包含 100 次迭代的循环。在每次迭代中，进程执行一次需要 $ t_c $ ms CPU 时间的计算操作，然后发起一次持续 $ t_{io} $ ms的 I/O 操作。假设运行这些进程的计算机具有足够的 I/O 设备，且操作系统为每个进程分配不同的 I/O 设备。此外，操作系统的调度开销可以忽略不计。各进程的特性如下：

Process id	$ t_c $	$ t_{io} $
A	100 ms	500 ms
B	350 ms	500 ms
C	200 ms	500 ms

这三个进程分别在 0、5 和 10 ms时刻启动，在采用纯时间片轮转调度（时间片为 50 ms）的分时系统中运行。进程 C 完成其第一次 I/O 操作的时间是（）ms。

正确答案：B

执行过程分析
三个进程 A、B 和 C 以时间片轮转方式运行，时间片为 50ms。
进程启动时间为 0、5 和 10 ms。

初始阶段执行顺序
A, B, C, A
- 每个进程执行 50ms CPU 时间
- 总耗时：50 + 50 + 50 + 50 = 200ms
- 此时 A 已完成 100ms 计算并开始 I/O
后续执行阶段
B, C, B, C, B, C
- 每个进程执行 50ms CPU 时间
- 总耗时：50 × 6 = 300ms
- 累计总时间：200ms + 300ms = 500ms

关键时间点

进程 C 在 500ms 时刻开始 I/O
I/O 持续时间为 500ms
因此 C 将在 1000ms 时刻完成第一次 I/O

14

一个操作系统使用最短剩余时间优先调度算法进行进程的抢占式调度。考虑以下进程集合及其到达时间和 CPU 突发时间（单位：ms）：

Process	Arrival Time	Burst Time
P1	0	12
P2	2	4
P3	3	6
P4	8	5

这些进程的平均等待时间（单位：ms）是（）。

正确答案：C

突发时间 - 进程完成执行所需的总 CPU 时间
等待时间 - 进程在就绪队列中等待获得 CPU 的时间

上述进程的甘特图如下：

P1: 0 → 2 ms
P2: 2 → 6 ms
P3: 6 → 12 ms
P4: 12 → 17 ms
P1: 17 → 27 ms

调度过程解析

初始执行
- 进程 P1 在时间 0 到达，开始执行
- 2 个时间单位后 P2 到达，其突发时间为 4 个单位，而 P1 的剩余时间为 10 个单位
- 根据最短剩余时间优先规则，CPU 抢占 P1 执行 P2
后续调度
- P2 执行完成后，系统比较剩余进程的剩余时间
- P3（剩余 6 单位）比 P1（剩余 10 单位）更短，继续执行 P3
- P3 完成后，P4（剩余 5 单位）比 P1（剩余 10 单位）更短，执行 P4
- 最终由 P1 完成剩余执行

等待时间计算

进程	计算公式	结果（ms）
P1	17（开始执行时间） - 2（首次被抢占时间）	15
P2	直接执行无等待	0
P3	6（开始执行时间） - 3（到达时间）	3
P4	12（开始执行时间） - 8（到达时间）	4

总等待时间 = 15 + 0 + 3 + 4 = 22
平均等待时间 = 22 / 4 = 5.5

因此答案选 C。

15

考虑以下进程集合，其到达时间和 CPU 突发时间（单位：ms）如下所示：

Process	Arrival Time	Burst Time
P1	0	5
P2	1	3
P3	2	3
P4	4	1

使用抢占式最短剩余处理时间优先（SJT）算法时，这些进程的平均周转时间是多少？

正确答案：A

执行的甘特图如下：
P1 P2 P4 P3 P1
1  4  5  8  12

周转时间 = 完成时间 - 到达时间
各进程具体计算如下：

P1: 12 - 0 = 12
P2: 4 - 1 = 3
P3: 8 - 2 = 6
P4: 5 - 4 = 1

总周转时间 = 12 + 3 + 6 + 1 = 22
平均周转时间 = 22 / 4 = 5.50

16

一个单处理器计算机系统仅有两个进程，这两个进程交替进行 10ms 的 CPU 计算和 90ms 的 I/O 操作。两个进程几乎同时创建。两个进程的 I/O 可以并行执行。以下哪种调度策略会导致该系统的 CPU 利用率最低（在长时间内）？

正确答案：D

当使用时间片轮转调度时
已知时间片为 5ms。考虑进程 P 和 Q。
假设 P 使用 5ms 的 CPU 后，Q 使用 5ms 的 CPU。因此在第 15ms 时 P 开始 I/O，在第 20ms 时 Q 开始 I/O。由于 I/O 可并行执行，P 在第 105ms（15+90）完成 I/O，Q 在第 110ms（20+90）完成 I/O。因此可以看出，CPU 在第 20ms 到第 105ms 期间处于空闲状态。
即当使用时间片轮转调度时：

CPU 空闲时间 = 85ms
CPU 利用率 = 20/105 = 19.05%

当使用先来先服务调度或最短剩余时间优先调度时
假设 P 使用 10ms 的 CPU 后开始 I/O。在第 11ms 时 Q 开始处理，Q 使用 10ms 的 CPU。

P 在第 100ms（10+90）完成 I/O
Q 在第 110ms（20+90）完成 I/O
在第 101ms 时 P 再次使用 CPU。因此：
- CPU 空闲时间 = 80ms
- CPU 利用率 = 20/100 = 20%

由于仅涉及两个进程且 I/O 时间远大于 CPU 时间，“为两个进程分配不同优先级的静态优先级调度"会退化为先来先服务或最短剩余时间优先调度。
因此，时间片轮转调度将导致最低的 CPU 利用率。

17

以下哪种调度算法是非抢占式的？（）

正确答案：B

解析

轮转法：当时间片到期时会发生抢占
先进先出：无抢占，进程一旦开始运行会持续到完成才会让出 CPU
多级队列调度：当高优先级进程到达时会发生抢占
带反馈的多级队列调度：当高优先级进程到达或高优先级队列的时间片到期需要将进程移至低优先级队列时会发生抢占

因此，B 是正确答案。

18

考虑一组在单处理器机器上运行的 n 个任务，其已知的运行时间分别为 r₁, r₂, …, rₙ。以下哪种处理器调度算法会导致最大的吞吐量？（）

正确答案：B

解释：

吞吐量定义：单位时间内完成的任务总数（包含等待时间与执行时间）。
最短作业优先（SJF）特性：
- 优先调度执行时间最短的任务。
- 短任务快速完成，减少整体等待时间。
优势分析：
- 最大化 CPU 利用率，最小化任务周转时间。
- 在相同时间内可完成更多任务，从而提升吞吐量。
结论：相比其他调度策略，SJF 更有利于提高系统吞吐量，因此选项 (B) 正确。

19

考虑一个单处理器系统，执行三个任务 T1、T2 和 T3。每个任务由无限序列的作业（或实例）组成，分别以 3 ms、7 ms 和 20 ms 的间隔周期性到达。每个任务的优先级与其周期成反比，可用任务按优先级顺序调度，最高优先级任务先调度。T1、T2 和 T3 的每个实例分别需要 1 ms、2 ms 和 4 ms 的执行时间。已知所有任务最初在第 1 ms 开始时到达，且允许任务抢占，则第一个 T3 实例完成执行的时间为（）ms。

正确答案：C

T1、T2 和 T3 的周期分别为 3ms、7ms 和 20ms。由于优先级与周期成反比，因此 T1 优先级最高，其次是 T2，最后是 T3。T1、T2 和 T3 的每个实例分别需要 1ms、2ms 和 4ms 的执行时间。初始时所有 T1、T2 和 T3 都准备好获取处理器，优先选择 T1。
T1、T2 和 T3 的第二个实例将分别在 3ms、7ms 和 20ms 到达。第三个实例将分别在 6ms、14ms 和 40ms 到达。

时间区间	任务
0-1	T1
1-2	T2
2-3	T2
3-4	T1 [T1 的第二个实例到达]
4-5	T3
5-6	T3
6-7	T1 [T1 的第三个实例到达] [因此 T3 被抢占]
7-8	T2 [T2 的第二个实例到达]
8-9	T2
9-10	T1 [T1 的第四个实例到达]
10-11	T3
11-12	T3 [T3 的第一个实例完成]

20

对于具有 n 个 CPU 的计算机系统，就绪状态中进程的最大数量是（）

正确答案：D

解析

理解就绪状态：在操作系统中，就绪状态是指进程已准备好执行但正在等待 CPU 时间的状态。这些进程存储在就绪队列中。

就绪状态中进程的最大数量：就绪队列中可以容纳的进程数量不依赖于 CPU 数量（n）。其容量由系统内存或调度策略等其他因素决定，而非 CPU 数量。

关键点

CPU 数量（n）仅决定同时可并发执行的进程数（即最多有 n 个进程处于运行状态）。
就绪状态理论上可以包含无限数量的等待进程。

最终答案

D（与 n 无关）

21

对于下表中列出的进程，以下哪种调度方案将产生最低的平均周转时间？

Process	到达时间	处理时间
A	0	3
B	1	6
C	4	4
D	6	2

正确答案：C

周转时间是指从程序/进程/线程/任务（Linux）提交执行到返回完整输出给用户所需的时间总和。周转时间 = 完成时间 - 到达时间。

FCFS = 先来先服务（A, B, C, D）
SJF = 非抢占式最短作业优先（A, B, D, C）
SRT = 最短剩余时间（A(3), B(1), C(4), D(2), B(5)）
RR = 时间片轮转（时间片大小为 2）（A(2), B(2), A(1), C(2), B(2), D(2), C(2), B(2)）

Pr	到达时间	处理时间	FCFS	SJF	SRT	RR
A	0	3	3-0=3	3-0=3	3-0=3	5-0=5
B	1	6	9-1=8	9-1=8	15-1=14	15-1=14
C	4	4	13-4=9	15-4=11	8-4=4	13-4=9
D	6	2	15-6=9	11-6=5	10-6=4	11-6=5
		平均值：	7.25	6.75	6.25	8.25

结论：最短剩余时间优先调度算法产生的平均周转时间最小。

22

我们希望在一个单处理器系统上调度三个进程 P1、P2 和 P3。进程的优先级（最高为最大）、CPU 时间需求和到达时间如下表所示：

进程	优先级（最高）	CPU 时间需求	到达时间（hh:mm:ss）
P1	10（最高）	20 秒	00:00:05
P2	9	10 秒	00:00:03
P3	8（最低）	15 秒	00:00:00

我们可以选择使用 抢占式 或 非抢占式 调度策略。在 抢占式调度 中，后到达的高优先级进程可以中断当前正在运行的低优先级进程；而在非抢占式调度中，后到达的高优先级进程必须等待当前正在执行的进程完成后才能被调度到处理器上。

问题：使用 抢占式 和 非抢占式 调度时，P2 的周转时间（从到达时间到完成时间）分别是多少？（）

正确答案：D

非抢占式调度分析：

执行顺序：P3 → P1 → P2
时间线：
- 0 → 15（P3 完成）
- 15 → 35（P1 完成）
- 35 → 45（P2 完成）
周转时间 = 45 - 3 = 42 秒

抢占式调度分析：

执行顺序：P3 → P3 → P3 → P2 → P2 → P1 → P2 → P3
时间线：
- 0 → 1（P3）
- 1 → 2（P3）
- 2 → 3（P2 开始）
- 3 → 4（P2 被 P1 抢占）
- 4 → 5（P1 开始）
- 5 → 25（P1 完成）
- 25 → 33（P2 完成）
- 33 → 45（P3 完成）
周转时间 = 33 - 3 = 30 秒

23

考虑一组任意的 CPU 密集型进程，它们具有不等长的 CPU 突发时间，并同时提交到计算机系统。以下哪种进程调度算法能够最小化就绪队列中的平均等待时间？

正确答案：A

解析

核心概念
- 周转时间：进程从开始到完成所花费的总时间
- 等待时间：进程已准备好运行但未被 CPU 调度器执行的时间
算法特性对比

算法类型	平均等待时间表现	是否存在饥饿风险	适用场景
最短作业优先 (SJF)	最优	否（非抢占时）	所有进程同时到达
最短剩余时间优先 (SRTF)	接近最优	是（需注意）	动态到达的短任务场景
轮转法 (RR)	中等	否	需公平性的交互式系统
优先级调度	差	是	实时系统或特殊需求场景

关键结论

在所有 CPU 调度算法中，最短作业优先（SJF）提供最小的平均等待时间
最短剩余时间优先（SRTF）是 SJF 的抢占版本，当所有进程同时到达时不会出现饥饿问题
本题条件满足"所有进程同时提交"，因此 SRTF 可实现最优调度效果
其他选项均无法达到最小化平均等待时间的目标

24

以下哪种磁盘调度策略最有可能提供最高的吞吐量？（）

正确答案：B

解析：

核心原理：下一个最近柱面（SSTF, 最短寻道时间优先）通过优先选择距离当前磁头位置最近的请求，显著减少磁头移动总距离。
性能优势：
- 高吞吐量：频繁访问相邻柱面可快速完成多个请求，提升整体处理效率。
- 低延迟：较短的寻道时间降低了单个请求的响应时间。
局限性：可能导致某些请求长期得不到服务（饥饿现象）。
对比其他选项：
- 先来先服务（FCFS）：按顺序处理，无优化，吞吐量较低。
- 电梯算法（SCAN）：虽平衡性能与公平性，但寻道路径较长，吞吐量略低于 SSTF。
- 最远柱面：反向操作，增加磁头移动距离，效率最低。

综上，选项 (B) 是最优解。

25

考虑以下进程，其到达时间和 CPU 突发长度（单位：ms）如下所示。使用的调度算法是抢占式最短剩余时间优先。这些进程的平均周转时间是（）ms。

Process	Arrival Time	Burst Time
P1	0	10
P2	3	6
P3	7	1
P4	8	3

正确答案：A

抢占式最短剩余时间优先调度算法意味着将选择当前剩余执行时间最短的进程在 CPU 上运行。根据下图 Gantt 图的调度和执行情况，周转时间（TAT）= 完成时间（CT）- 到达时间（AT）。

P1 的 TAT = 20 - 0 = 20
P2 的 TAT = 10 - 3 = 7
P3 的 TAT = 8 - 7 = 1
P4 的 TAT = 13 - 8 = 5

因此，平均 TAT = 所有进程的总 TAT / 进程数量 = (20 + 7 + 1 + 5)/4 = 33/4 = 8.25
故选项（A）为正确答案。

26

考虑 $n$ 个作业 $J_1, J_2, \cdots, J_n$，其中作业 $J_i$ 的执行时间为 $t_i$，且具有非负整数权重 $w_i$。作业的加权平均完成时间定义为 $\frac{\sum_{i=1}^{n} w_i T_i}{\sum_{i=1}^{n} w_i}$，其中 $T_i$ 是作业 $J_i$ 的完成时间。假设只有一个处理器可用，为了最小化作业的加权平均完成时间，必须按照什么顺序执行这些作业？

正确答案：D

解析

核心思路：该问题属于贪心算法的经典应用场景。目标是最小化加权平均完成时间，需通过数学推导确定最优排序准则。
数学推导：
- 假设两个相邻作业 $J_i$ 和 $J_j$，若交换顺序后总成本降低，则当前顺序非最优。
- 比较两种排列方式的成本差值，发现当 $\frac{w_i}{t_i} \geq \frac{w_j}{t_j}$ 时，应优先执行 $J_i$。
结论：按权重与执行时间比值（$\frac{w_i}{t_i}$）从大到小排序，能保证全局最优解。
反例验证：
- 若按 $w_i$ 排序（选项 B），可能因某作业耗时过长导致后续高权重作业延迟。
- 若按 $w_i t_i$ 排序（选项 C），未考虑单位时间内的权重收益。
- 若按 $t_i$ 排序（选项 A），完全忽略权重差异，无法体现优先级。

27

假设在一个单处理器系统中，每个进程需要 3 秒的服务时间。如果新进程以每分钟 10 个进程的速率到达，则估算系统中 CPU 忙碌的时间占比（）？

正确答案：C

解析

到达率：10 个进程/分钟 → 1 个进程每 6 秒（1/10 分钟）
服务时间：每个进程 3 秒
计算公式：$\frac{3}{6} \times 100\% = 50\%$

28

考虑 $n$ 个进程以轮转方式共享 CPU。假设每次进程切换需要 $s$ 秒，那么轮转时间 $q$ 必须满足什么条件才能使进程切换带来的开销最小化，同时保证每个进程至少每 $t$ 秒能获得一次 CPU 使用权？（）

正确答案：A

每个进程将获得 q 秒的 CPU 时间，且每个进程希望在 t 秒后再次获得 CPU。因此，当当前进程再次获得 CPU 时，会有 (n-1) 个进程已经运行过一次。每个进程切换需要 s 秒。

可以看出，P1 离开并再次到达时，发生了 n 次上下文切换和 (n-1) 个进程。因此方程为：

$$ q(n-1) + ns \leq t $$

进一步推导得：

$$ q(n-1) \leq t - ns $$
$$ q \leq \frac{t - ns}{n-1} $$

所以选项 (A) 正确。

29

四个作业按顺序 A、B、C、D 在时间 0 同时到达单处理器系统。它们的 CPU 执行时间需求分别为 4、1、8、1 时间单位。在时间片大小为一个时间单位的轮转调度下，作业 A 的完成时间是（）：

正确答案：D

解析
在轮转调度中，每个作业按时间片轮流执行。初始队列为 [A(4), B(1), C(8), D(1)]，时间片为 1 单位。

时间 0-1：执行 A（剩余 3），队列变为 [B(1), C(8), D(1), A(3)]
时间 1-2：执行 B（剩余 0，完成）
时间 2-3：执行 C（剩余 7），队列变为 [D(1), A(3), C(7)]
时间 3-4：执行 D（剩余 0，完成）
时间 4-5：执行 A（剩余 2），队列变为 [C(7), A(2)]
时间 5-6：执行 C（剩余 6），队列变为 [A(2), C(6)]
时间 6-7：执行 A（剩余 1），队列变为 [C(6), A(1)]
时间 7-8：执行 C（剩余 5），队列变为 [A(1), C(5)]
时间 8-9：执行 A（剩余 0，完成）

最终，作业 A 在第 9 个时间单位完成，故选 D。

30

考虑以下 CPU 进程，其到达时间（单位：ms）和 CPU 执行时间（单位：ms）如下表所示（除进程 P4 外）：

进程	到达时间	执行时间
P1	0	5
P2	1	1
P3	3	3
P4	4	x

若所有进程的平均等待时间为 2 ms，并使用抢占式最短剩余时间优先调度算法进行调度，则 x 的值为（）。

正确答案：B

解析过程

假设条件：若 x 取值为 2，则甘特图如下所示。
完成时间：
- P1 完成时间：6
- P2 完成时间：2
- P3 完成时间：11
- P4 完成时间：8
周转时间：
- P1 周转时间：6（6-0）
- P2 周转时间：1（2-1）
- P3 周转时间：8（11-3）
- P4 周转时间：4（8-4）
等待时间：
- P1 等待时间：1（6-5）
- P2 等待时间：0（1-1）
- P3 等待时间：5（8-3）
- P4 等待时间：2（4-2）
平均等待时间计算：
(1 + 0 + 5 + 2) ÷ 4 = 8 ÷ 4 = 2

结论：选项 (B) 正确。

31

哪个模块将 CPU 的控制权交给由短期调度器选中的进程（）？

正确答案：A

解析

存在三种类型的调度器：
- 短期调度器
- 中期调度器
- 长期调度器
分派器（Dispatcher）是操作系统中负责将 CPU 控制权移交给短期调度器所选进程的核心组件
其工作流程包含以下关键步骤：
1. 接收短期调度器分配的进程
2. 执行上下文切换（Context Switch）
3. 将 CPU 寄存器状态加载到目标进程
4. 启动目标进程的执行

因此选项（A）正确。

32

考虑以下四个进程，其到达时间和 CPU 执行时间（单位：ms）如下所示。使用抢占式短作业优先调度算法时的平均等待时间是（）。

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

正确答案：A

解析：

首先需通过甘特图确定各进程的执行顺序与时间分配
计算各进程的等待时间：
- P1 等待时间：9ms
- P2 等待时间：0ms
- P3 等待时间：15ms
- P4 等待时间：2ms
平均等待时间计算公式： $$ \text{平均等待时间} = \frac{\text{各进程等待时间之和}}{\text{进程总数}} = \frac{9+0+15+2}{4} = \frac{26}{4} = 6.5 $$
因此选项 (A) 正确

33

以下哪项陈述是正确的（）？

正确答案：A

解释：

抖动是指发送信号或数据之间的变化/偏移。

硬实时操作系统：用于对时间要求严格的敏感系统（如发动机控制系统、卫星发射系统）
软实时操作系统：允许一定程度的延迟（如手机、在线数据库系统）

因此，硬实时操作系统需要最小化抖动以满足严格的时间约束。

34

以下哪种调度算法可能导致饥饿？（）

a. 先来先服务
b. 时间片轮转
c. 优先级
d. 最短作业优先
e. 最短剩余时间优先

正确答案：B

解析

先来先服务（FCFS）：若一个执行时间极长的进程排在其他进程之前，虽然其他进程需要等待较长时间，但它们最终会获得执行机会，因此不会发生饥饿。
时间片轮转：每个进程都会按固定时间片轮流执行，不存在饥饿问题。
优先级调度：若持续有高优先级进程到达，则低优先级进程将发生饥饿现象。
最短作业优先（SJF）：若持续有短执行时间的进程到达，则长执行时间的进程可能长期等待而发生饥饿。
最短剩余时间优先（SRTF）：由于总是优先执行剩余时间最短的进程，长执行时间的进程可能发生饥饿。

因此，选项 (C) 是正确的。

35

五个作业 A、B、C、D 和 E 正在就绪队列中等待。它们的预计运行时间分别为 9、6、3、5 和 x。所有作业在时间零时进入就绪队列。如果 3 < x < 5，要使平均响应时间最小，它们必须按（）顺序运行。

正确答案：B

我们通过最小化平均等待时间来求解，并取 x = 4

BT: 执行时间（Burst Time）
CT: 完成时间（Completion Time）
P: 作业（Process）
AWT: 平均等待时间（Average Waiting Time）
AT: 到达时间（Arrival Time）
WT: 等待时间（Waiting Time）

选项 (B) 给出的序列能获得最小的平均等待时间

36

考虑三个 CPU 密集型进程 P1、P2、P3，它们分别需要 20、10 和 30 个时间单位，到达时间分别为 1、3 和 7。假设操作系统采用最短剩余时间优先（抢占式调度）算法，则需要进行**（）**次上下文切换（假设就绪队列开始时和结束时的上下文切换不计入）。

正确答案：A

解释

根据最短剩余时间优先（SRTF）调度算法，上下文切换发生在以下三个时刻：

时间 3：进程 P1 被新到达的进程 P2 抢占。
时间 13：进程 P2 完成后，进程 P1 恢复执行。
时间 13 之后：进程 P1 在运行过程中被新到达的进程 P3 抢占（若存在）。

尽管实际计算中可能仅出现两次切换，但根据题目设定及答案选项，此处需确认三次上下文切换的发生。因此，选项 (A) 正确。

37

以下哪项不是 CPU 调度算法设计中的优化标准？（）

正确答案：A

解析：最小 CPU 利用率不是优化标准
- CPU 调度算法的核心目标是提高系统资源利用率与效率
- 典型优化指标包括：
  - 最大吞吐量（单位时间内完成的任务数）
  - 最小周转时间（任务从提交到完成的时间）
  - 最小等待时间（任务在就绪队列中的等待时长）
- 反向思维：降低 CPU 利用率会违背调度算法的设计初衷，因此 A 为干扰项

38

在一个使用单处理器的系统中，每分钟有六个新进程到达，每个进程需要七秒的服务时间。CPU 的利用率是多少？（）

正确答案：A

解析：

每分钟进程数 = 6 个
每个进程的突发时间 = 7 秒
一分钟内的 CPU 利用时间 = 6 × 7 = 42 秒
CPU 利用率 = 有用时间 / 总时间 × 100 = (42/60) × 100 = 70%

39

关于多级反馈队列处理器调度算法，以下哪项描述不正确？（）

正确答案：C

对于多级反馈队列处理器调度算法：

队列具有不同的优先级
每个队列可以使用不同的调度算法
进程不会被永久分配到某个队列
该算法可以配置以匹配特定设计中的系统

选项 (C) 是正确答案。

40

考虑以下关于常用两级 CPU 调度的合理性的描述：

I. 当内存太小无法容纳所有就绪进程时使用。
II. 因为其性能与 FIFO 相同。
III. 因为它便于将一组进程放入内存中并从中进行选择。
IV. 因为它不允许调整核心中的进程集合。

以下哪项是正确的？（）

正确答案：D

描述 I：当内存太小无法容纳所有就绪进程时，两级 CPU 调度被采用。
描述 III：它便于将一组进程放入内存中并从中进行选择。

错误描述解析：

描述 II 错误，因为两级调度的性能并不等同于 FIFO（先进先出），其设计目的是优化内存使用而非性能匹配。
描述 IV 错误，因为两级调度允许动态调整核心中的进程集合，以适应系统需求变化。

41

在以下哪种调度准则中，上下文切换永远不会发生？（）

正确答案：C

解析

非抢占式调度算法具有不可中断的特性
进程一旦开始执行就必须运行到完成或主动让出 CPU
因此不会出现强制性的上下文切换操作
典型代表如非抢占式短作业优先算法

42

考虑以下一组进程，假设它们在时间 0 到达。考虑 CPU 调度算法最短作业优先（SJF）和轮转法（RR）。对于 RR，假设进程按 P1、P2、P3、P4 的顺序调度。如果 RR 的时间片为 4ms，则 SJF 和 RR 的平均周转时间（以ms为单位）的绝对差值（四舍五入到小数点后两位）是（）。

正确答案：B

根据最短作业优先（SJF）CPU 调度算法，甘特图如下所示。因此，平均周转时间（TAT）为：

$$ \frac{(21 - 0) + (13 - 0) + (2 - 0) + (6 - 0)}{4} = 10.5 $$

根据时间片为 4 的轮转法（RR）CPU 调度算法，甘特图如下所示。因此，平均周转时间（TAT）为：

$$ \frac{(18 - 0) + (21 - 0) + (10 - 0) + (14 - 0)}{4} = 15.75 $$

最终差值计算：

$$ |SJF(TAT) - RR(TAT)| = |10.5 - 15.75| = 5.25 $$

选项（B）正确。

43

如果轮转调度策略中使用的时间片大于任何进程执行所需的最大时间，那么该策略将（）

正确答案：C

解释：

轮转调度（RR）在时间片下以**先来先服务（FCFS）**的方式执行进程
当时间片长度超过所有进程最大执行时间时，每个进程都会在单次时间片内完成
此时调度顺序完全取决于进程到达的先后顺序，与 FCFS 完全一致

44

考虑以下进程集合，其到达时间和所需 CPU 执行时间（单位：ms）如下表所示：

进程	到达时间	执行时间
P1	0	4
P2	2	2
P3	3	1

在采用时间片为 2 ms 的轮转调度算法时，这些进程的完成顺序是（）？

正确答案：B

解析

使用时间片 tq=2ms 的轮转调度算法时，进程的完成顺序为 P2, P1, P3。选项 (B) 正确。具体分析如下：

时间片分配规则
- 时间片固定为 2ms，每次从就绪队列中选择一个进程执行，直到时间片耗尽或进程完成。
- 若进程未完成，则将其放回就绪队列末尾继续等待。
执行过程分解
- t=0~2ms：P1 开始执行，剩余执行时间为 2ms。
- t=2ms：P2 到达，加入就绪队列；P1 时间片用完，剩余 2ms，重新入队。
- t=2~4ms：P2 执行完成（总执行时间 2ms）。
- t=4ms：P3 到达，加入就绪队列；P1 剩余 2ms，继续执行至 t=6ms 完成。
- t=6ms：P3 执行 1ms 完成。
完成顺序
- P2 在 t=4ms 完成，P1 在 t=6ms 完成，P3 在 t=7ms 完成。
- 因此最终完成顺序为 P2 → P1 → P3。

45

下表显示了就绪队列中的进程及其完成作业所需的时间：

进程	时间（ms）
P1	10
P2	5
P3	20
P4	8
P5	15

如果使用时间片为 5 ms 的轮转调度算法，那么该队列中进程的平均等待时间是多少？（）

正确答案：B

进程的等待时间 = 在就绪队列中等待的总时间。
等待时间 = 完成时间 - 执行时间

P1 的等待时间 = 30 - 10 = 20
P2 的等待时间 = 10 - 5 = 5
P3 的等待时间 = 58 - 20 = 38
P4 的等待时间 = 38 - 8 = 30
P5 的等待时间 = 53 - 15 = 38

平均等待时间 = (20 + 5 + 38 + 30 + 38) / 5 = 131/5 = 26.2

46

轮转（Round Robin）算法的性能在很大程度上取决于（）

正确答案：D

在轮转算法中，时间片的大小起着非常重要的作用：

时间片过小：上下文切换次数会增加，这被视为浪费时间，导致 CPU 利用率下降。
时间片过大：较大的时间片会使轮转调度退化为先来先服务（FCFS）调度算法。

因此，选项（D）正确。

47

考虑一组 5 个进程，其到达时间、所需 CPU 时间和优先级如下所示（数字越小优先级越高）：

进程	到达时间（ms）	所需 CPU 时间	优先级
P1	0	10	5
P2	0	5	2
P3	2	3	1
P4	5	20	4
P5	10	2	3

如果 CPU 调度策略是 非抢占式优先级调度，则平均等待时间将是（）：

正确答案：C

解析

等待时间 = 周转时间 - 执行时间
周转时间 = 完成时间 - 到达时间

进程	到达时间（ms）	所需 CPU 时间	优先级	周转时间	等待时间
P1	0	10	5	40 - 0 = 40	40 - 10 = 30
P2	0	5	2	5 - 0 = 5	5 - 5 = 0
P3	2	3	1	8 - 2 = 6	6 - 3 = 3
P4	5	20	4	28 - 5 = 23	23 - 20 = 3
P5	10	2	3	30 - 10 = 20	20 - 2 = 18

平均等待时间 = (30 + 0 + 3 + 3 + 18) / 5 = 10.8
因此，选项 (C) 正确。

48

四个作业按顺序 A、B、C、D 在单处理器系统上于时间 0 到达。它们的 CPU 突发时间需求分别为 4、1、8、1 时间单位。在时间片为 1 时间单位的轮转调度下，作业 A 的完成时间是（）：

正确答案：D

使用时间片为 1 的轮转算法时，各进程的到达时间为 0，其执行顺序为：

A（剩余 3）
B（剩余 0）
C（剩余 7）
D（剩余 0）
A（剩余 2）
C（剩余 6）
A（剩余 1）
C（剩余 5）
A（剩余 0）

总共经历 9 个时间片后，作业 A 完成执行。因此，完成时间为 9。

正确选项是 (D)。

49

考虑一组在单处理器机器上运行的 n 个任务，已知其运行时间分别为 r₁、r₂、…、rₙ。以下哪种处理器调度算法会导致最大的吞吐量？（）

正确答案：B

解析：

吞吐量是指单位时间内完成的任务总数，即等待时间和执行时间的总和。
最短作业优先调度是一种选择等待队列中执行时间最短的进程优先执行的调度策略。
在该策略下，短作业会优先执行，这意味着 CPU 利用率最大，因此可以完成最多的任务数。
综上，选项 (B) 正确。

50

考虑下表中所示的一组进程，其到达时间（ms）、要求服务时间（ms）和优先级（0 为最高优先级）。所有进程均无 I/O 突发时间。使用抢占式优先级调度算法时，进程 P1 的等待时间（ms）是（）。

Process	Arrival	Burst Time	Priority
P1	0	11	2
P2	5	28	0
P3	12	2	3
P4	2	10	1
P5	9	16	4

正确答案：C

解析：

等待时间计算公式：完成时间 - 到达时间 - 执行时间
具体计算过程：
完成时间 = 49 ms
到达时间 = 0 ms
执行时间 = 11 ms
等待时间 = 49 - 0 - 11 = 38

因此选项 (C) 正确。