408 真题做题本·操作系统部分

第 2 章 进程管理

2.1 进程与线程

1. 【2010】下列选项中, 导致创建新进程的操作是（ ）。 I. 用户登录成功 II. 设备分配 III. 启动程序执行

A. 仅 I、 II
B. 仅 II、 III
C. 仅 I、 III
D. I、 II、 III

答案： C 解析： 用户登录成功后，系统通常要为该用户创建相应的用户进程；启动程序执行也要创建承载该程序的新进程。设备分配只是给已有进程分配资源，不会因此创建新进程。因此仅 I、III 正确。

2. 【2011】在支持多线程的系统中, 进程 P 创建的若干个线程不能共享的是（ ）。

A. 进程 P 的代码段
B. 进程 P 中打开的文件
C. 进程 P 的全局变量
D. 进程中某线程的栈指针

答案： D 解析： 同一进程内的线程共享进程的代码段、全局变量和已打开文件等资源；每个线程必须有独立的运行现场，包括程序计数器、寄存器组和栈，因此某线程的栈指针不能与其他线程共享。

3. 【2012】下列关于进程和线程的叙述中, 正确的是（ ）。

A. 不管系统是否支持线程, 进程都是资源分配的基本单位
B. 线程是资源分配的基本单位, 进程是调度的基本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间

答案： A 解析： 进程是系统进行资源分配和保护的基本单位；在线程系统中，线程通常是处理机调度的基本单位。用户级线程的管理和切换可由用户态线程库完成，不必得到内核支持；同一进程内的线程共享地址空间。

4. 【2014】一个进程的读磁盘操作完成后, 操作系统针对该进程必做的是（ ）。

A. 修改进程状态为就绪态
B. 降低进程优先级
C. 给进程分配用户内存空间
D. 增加进程时间片大小

答案： A 解析： 进程发出读磁盘请求后通常由执行态转为阻塞态。磁盘读操作完成时，相应中断处理程序会解除该进程的等待条件，使其由阻塞态转为就绪态，因此操作系统必然要把其状态改为就绪态并放入就绪队列。

5. 【2014】下列关于管道 (Pipe) 通信的叙述中, 正确的是（ ）。

A. 一个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可能被阻塞
D. 一个管道只能有一个读进程或一个写进程对其操作

答案： C 解析： 普通管道通常是半双工的，容量由内核缓冲区大小决定，而不是由磁盘容量决定。管道为空时读进程可能阻塞，管道已满时写进程也可能阻塞；一个管道可以存在多个读者或写者，只需由系统保证相应同步。

6. 【2015】下列选项中, 会导致进程从执行态变为就绪态的事件是（ ）。

A. 执行 P(wait) 操作
B. 申请内存失败
C. 启动 I/O 设备
D. 被高优先级进程抢占

答案： D 解析： 执行 P(wait) 操作、申请资源失败或启动 I/O 都可能使进程等待某个事件，从执行态转为阻塞态；被更高优先级进程抢占时，原进程仍具备运行条件，只是暂时失去 CPU，因此转为就绪态。

7. 【2018】下列选项中, 可能导致当前进程 P 阻塞的事件是（ ）。 I. 进程 P 申请临界资源 II. 进程 P 从磁盘读数据 III. 系统将 CPU 分配给高优先权的进程

A. 仅 I
B. 仅 II
C. 仅 I、 II
D. I、 II、 III

答案： C 解析： 申请临界资源时，若资源正被占用，进程 P 可能阻塞；从磁盘读数据通常也要等待 I/O 完成，因而可能阻塞。系统把 CPU 分配给高优先权进程时，P 只是被抢占，由执行态转为就绪态，不是阻塞态。

8. 【2019】下列关于线程的描述中,错误的是（ ）。

A. 内核级线程的调度由操作系统完成
B. 操作系统为每个用户级线程建立一个线程控制块
C. 用户级线程间的切换比内核级线程间的切换效率高
D. 用户级线程可以在不支持内核级线程的操作系统上实现

答案： B 解析： 内核级线程由操作系统管理，内核为其维护线程控制块并完成调度。用户级线程由用户态线程库管理，操作系统通常只感知进程或内核级线程，不会为每个用户级线程建立内核线程控制块。

9. 【2019】下列选项中, 可能将进程唤醒的事件是（ ）。 I. I/O 结束 II. 某进程退出临界区 III. 当前进程的时间片用完

A. 仅 I
B. 仅 III
C. 仅 I、 II
D. I、 II、 III

答案： C 解析： I/O 结束会使等待该 I/O 的进程具备运行条件；某进程退出临界区并释放同步资源，也可能唤醒等待该资源的进程。当前进程时间片用完只会使当前进程由执行态转为就绪态，不会唤醒其他阻塞进程。

10. 【2020】下列关于父进程与子进程的叙述中,错误的是（ ）。

A. 父进程与子进程可以并发执行
B. 父进程与子进程共享虚拟地址空间
C. 父进程与子进程有不同的进程控制块
D. 父进程与子进程不能同时使用同一临界资源

答案： B 解析： 父进程和子进程可以并发执行，且分别拥有独立的 PCB。创建子进程时，子进程可继承父进程地址空间的内容，但二者具有逻辑上独立的虚拟地址空间；即使采用写时复制，也不能说它们共享同一虚拟地址空间。

11. 【2021】下列操作中, 操作系统在创建新进程时, 必须完成的是（ ）。 I. 申请空白的进程控制块 II. 初始化进程控制块 III. 设置进程状态为执行态

A. 仅 I
B. 仅 I、 II
C. 仅 I、 III
D. 仅 II、 III

答案： B 解析： 创建进程时必须申请空白 PCB，并填写进程标识、资源信息和上下文等内容以完成初始化。新进程通常先进入就绪态，只有被调度程序选中后才进入执行态，因此不必在创建时设置为执行态。

12. 【2022】下列事件或操作中, 可能导致进程 P 由执行态变为阻塞态的是（ ）。 I. 进程 P 读文件 II. 进程 P 的时间片用完 III. 进程 P 申请外设 IV. 进程 P 执行信号量的 wait（ ） 操作

A. 仅 I、 IV
B. 仅 II、 III
C. 仅 III、 IV
D. 仅 I、 III、 IV

答案： D 解析： 读文件、申请外设都可能因等待 I/O 而阻塞；执行 wait() 时，若所申请的同步资源不可用，也会阻塞。时间片用完只会导致进程由执行态转为就绪态。因此 I、III、IV 正确。

13. 【2023】下列由当前线程引起的事件或执行的操作中,可能导致该线程由执行态变为就绪态的是（ ）。

A. 键盘输入
B. 缺页异常
C. 主动出让 CPU
D. 执行信号量的 wait（ ） 操作

答案： C 解析： 线程主动出让 CPU 后仍然具备运行条件，只是放弃当前处理机，因此通常由执行态转为就绪态。缺页异常和执行 wait() 可能使线程等待事件而阻塞；键盘输入通常唤醒的是等待输入的线程，并非使当前执行线程转为就绪态。

14. 【2024】下列选项中, 操作系统在终止进程时不一定执行的是（ ）。

A. 终止子进程
B. 回收进程占用的设备
C. 释放进程控制块
D. 回收为进程分配的内存

答案： A 解析： 进程终止时，操作系统必须回收其占用的内存、设备等资源，并释放 PCB。是否同时终止其子进程取决于操作系统的进程管理策略，子进程也可能被其他进程接管，因此终止子进程不是必然操作。

15. 【2024】在支持页式存储管理的系统中, 进程切换时操作系统需要执行的操作是（ ）。 I. 更新程序计数器的值 II. 更新栈基址寄存器的值 III. 更新页表基地址寄存器的值

A. 仅 III
B. 仅 I、 II
C. 仅 I、 III
D. I、 II、 III

答案： D 解析： 进程切换需要保存旧进程并恢复新进程的处理机现场，因此要更新程序计数器和栈相关寄存器。页式存储系统中，不同进程通常使用不同页表，切换地址空间时还要更新页表基地址寄存器。因此 I、II、III 均需要。

16. 【2024】若进程 P 中的线程 T 先打开文件, 得到文件描述符 fd, 再创建两个线程 Ta 和 Tb, 则下列资源中, Ta 与 Tb 可共享的是（ ）。 I. 进程 P 的地址空间 II. 线程 T 的栈 III. 文件描述符 fd

A. 仅 I
B. 仅 I、 III
C. 仅 II、 III
D. I、 II、 III

答案： B 解析： 同一进程中的线程共享进程地址空间以及进程打开的文件描述符表，因此 Ta、Tb 可共享地址空间和文件描述符 fd。每个线程有各自独立的栈和栈指针，线程 T 的栈不属于 Ta、Tb 的共享运行现场。

2.2 CPU 调度与上下文切换

1. 【2009】下列进程调度算法中, 综合考虑进程等待时间和执行时间的是（ ）。

A. 时间片轮转调度算法
B. 短进程优先调度算法
C. 先来先服务调度算法
D. 高响应比优先调度算法

答案： D 解析： 高响应比优先调度算法的响应比为 $R=\frac{W+S}{S}=1+\frac{W}{S}$，其中 $W$ 为等待时间，$S$ 为要求服务时间，因此它同时考虑了进程的等待时间和执行时间。

2. 【2010】下列选项中, 降低进程优先级的合理时机是（ ）。

A. 进程的时间片用完
B. 进程刚完成 I/O, 进入就绪队列
C. 进程长期处于就绪队列中
D. 进程从就绪态转为运行态

答案： A 解析： 时间片用完说明进程已连续占用了一段 CPU 时间，适当降低其优先级有利于照顾交互型或 I/O 型进程。刚完成 I/O 或长期等待的进程通常应提高而不是降低优先级。

3. 【2011】下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先

答案： B 解析： 高响应比优先算法在服务时间较短时具有短任务优先倾向，同时等待时间越长，响应比越大，因此长期等待的作业最终会获得调度，可避免饥饿。非抢占式短任务优先可能使长作业长期得不到执行。

4. 【2012】一个多道批处理系统中仅有 P1 和 P2 两个作业, P2 比 P1 晚 5ms 到达, 它们的计算和 I/O 操作顺序如下: P1: 计算 60ms,I/O80ms, 计算 20ms P2: 计算 120ms,I/O40ms, 计算 40ms 若不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。

A. 240ms
B. 260ms
C. 340ms
D. 360ms

答案： B 解析： 一种最短完成方案为：P1 在 $0\sim 60\mathrm{ms}$ 计算，随后在 $60\sim 140\mathrm{ms}$ 做 I/O；P2 在 $60\sim 180\mathrm{ms}$ 计算；P2 做 I/O 的 $180\sim 220\mathrm{ms}$ 内，P1 于 $180\sim 200\mathrm{ms}$ 完成最后计算；最后 P2 在 $220\sim 260\mathrm{ms}$ 完成计算。故总时间为 $260\mathrm{ms}$。

5. 【2012】若某单处理器多进程系统中有多个就绪态进程,则下列关于处理机调度的叙述中,错误的是（ ）。

A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度

答案： C 解析： 进程处于临界区时仍可能因时钟中断等原因被抢占，操作系统并不要求临界区内绝对禁止处理机调度；互斥机制只要求其他进程不能同时进入同一临界区。进程结束、创建新进程以及系统调用返回用户态等时机都可能触发调度。

6. 【2013】某系统正在执行三个进程 P1、 P2 和 P3, 各进程的计算 (CPU) 时间和 I/O 时间比例如下表所示。为提高系统资源利用率, 合理的进程优先级设置应为（ ）。

进程	计算时间	I/O 时间
P1	90%	10%
P2	50%	50%
P3	15%	85%

A. $P_1>P_2>P_3$
B. $P_3>P_2>P_1$
C. $P_2>P_1=P_3$
D. $P_1>P_2=P_3$

答案： B 解析： P3 的 I/O 比例最高，应给予最高优先级，使其尽快发出 I/O 请求并释放 CPU；P1 的 CPU 计算比例最高，优先级应最低。这样可尽量让 CPU 与 I/O 设备并行工作，提高系统资源利用率，因此应为 $P3>P2>P1$。

7. 【2014】下列调度算法中, 不可能导致饥饿现象的是（ ）。

A. 时间片轮转
B. 静态优先数调度
C. 非抢占式短作业优先
D. 抢占式短作业优先

答案： A 解析： 时间片轮转按就绪队列循环分配 CPU，只要时间片有限且进程一直处于就绪队列中，每个进程最终都能得到时间片，因此不会发生饥饿。静态优先数和短作业优先都可能使低优先级进程或长作业长期等待。

8. 【2016】某单 CPU 系统中有输入和输出设备各 1 台, 现有 3 个并发执行的作业, 每个作业的输入、计算和输出时间均分别为 2ms、 3ms 和 4ms, 且都按输入、计算和输出的顺序执行, 则执行完 3 个作业需要的时间最少是（ ）。

A. 15ms
B. 17ms
C. 22ms
D. 27ms

答案： B 解析： 三个作业可形成流水执行：作业 1 的输入、计算、输出分别为 $0\sim 2$、$2\sim 5$、$5\sim 9$；作业 2 为 $2\sim 4$、$5\sim 8$、$9\sim 13$；作业 3 为 $4\sim 6$、$8\sim 11$、$13\sim 17$。故最短总时间为 $17\mathrm{ms}$。

9. 【2017】下列有关基于时间片的进程调度的叙述中,错误的是（ ）。

A. 时间片越短, 进程切换的次数越多, 系统开销也越大
B. 当前进程的时间片用完后, 该进程状态由执行态变为阻塞态
C. 时钟中断发生后, 系统会修改当前进程在时间片内的剩余时间
D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

答案： B 解析： 时间片用完后，当前进程仍具备继续运行的条件，只是被剥夺 CPU，因此应由执行态转为就绪态，而不是阻塞态。其余叙述均符合时间片轮转调度的特点。

10. 【2017】假设 4 个作业到达系统的时刻和运行时间如下表所示。系统在 t = 2 时开始作业调度。

作业	到达时刻	运行时间
J1	0	3
J2	1	3
J3	1	2
J4	3	1

若分别采用先来先服务和短作业优先调度算法, 则选中的作业分别是（ ）。

A. J2、 J3
B. J1、 J4
C. J2、 J4
D. J1、 J3

答案： D 解析： 在 $t=2$ 时，J1、J2、J3 均已到达。先来先服务按到达先后选择最早到达的 J1；短作业优先在已到达作业中选择运行时间最短的 J3。因此分别为 J1、J3。

11. 【2018】某系统采用基于优先权的非抢占式进程调度策略, 完成一次进程调度和进程切换的系统时间开销为 1μs。在 T 时刻就绪队列中有 3 个进程 P1、 P2 和 P3。其在就绪队列中的等待时间、需要的 CPU 时间和优先权见下表。若优先权值大的进程优先获得 CPU, 从 T 时刻起系统开始进程调度。

进程	等待时间	需要的 CPU 时间	优先权
P1	30μs	12μs	10
P2	15μs	24μs	30
P3	18μs	36μs	20

则系统的平均周转时间为（ ）。

A. 54μs
B. 73μs
C. 74μs
D. 75μs

答案： D 解析： 按优先权依次执行 P2、P3、P1。计入每次调度和切换的 $1\mu s$，从 T 时刻起三者完成时刻分别为 $25$、$62$、$75\mu s$。加上此前等待时间，周转时间分别为 $15+25=40$、$18+62=80$、$30+75=105\mu s$，平均值为 $\frac{40+80+105}{3}=75\mu s$。

12. 【2018】当定时器产生时钟中断后, 由时钟中断服务程序更新的部分内容是（ ）。 I. 内核中时钟变量的值 II. 当前进程占用 CPU 的时间 III. 当前进程在时间片内的剩余执行时间

A. 仅 I、 II
B. 仅 II、 III
C. 仅 I、 III
D. I、 II、 III

答案： D 解析： 时钟中断处理程序需要更新系统时钟，统计当前进程已占用的 CPU 时间，并扣减其时间片剩余值，以便判断是否需要抢占。因此 I、II、III 均会更新。

13. 【2019】系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法,时间片为 10ms; 就绪队列 Q2 采用短进程优先调度算法; 系统优先调度 Q1 队列中的进程, 当 Q1 为空时系统才会调度 Q2 中的进程; 新创建的进程首先进入 Q1;Q1 中的进程执行一个时间片后, 若未结束, 则转入 Q2。若当前 Q1、 Q2 为空, 系统依次创建进程 P1、 P2 后即开始进程调度。 P1、 P2 需要的 CPU 时间分别为 30ms 和 20ms, 则进程 P1、 P2 在系统中的平均等待时间为（ ）。

A. 25ms
B. 20ms
C. 15ms
D. 10ms

答案： C 解析： P1 先在 Q1 执行 $10\mathrm{ms}$ 后转入 Q2，P2 再在 Q1 执行 $10\mathrm{ms}$ 后转入 Q2。Q1 为空后，Q2 按短进程优先先执行剩余 $10\mathrm{ms}$ 的 P2，再执行剩余 $20\mathrm{ms}$ 的 P1。P1 等待 $20\mathrm{ms}$，P2 等待 $10\mathrm{ms}$，平均等待时间为 $15\mathrm{ms}$。

14. 【2020】下列与进程调度有关的因素中, 在设计多级反馈队列调度算法时需要考虑的是（ ）。 I. 就绪队列的数量 II. 就绪队列的优先级 III. 各就绪队列的调度算法 IV. 进程在就绪队列间的迁移条件

A. 仅 I、 II
B. 仅 III、 IV
C. 仅 II、 III、 IV
D. I、 II、 III、 IV

答案： D 解析： 设计多级反馈队列时，需要确定队列数量、各队列优先级、每个队列内部采用的调度算法，以及进程在不同队列之间上升或下降的迁移条件，因此 I、II、III、IV 都需要考虑。

15. 【2021】下列内核的数据结构或程序中, 分时系统实现时间片轮转调度需要使用的是（ ）。 I. 进程控制块 II. 时钟中断处理程序 III. 进程就绪队列 IV. 进程阻塞队列

A. 仅 II、 III
B. 仅 I、 IV
C. 仅 I、 II、 III
D. 仅 I、 II、 IV

答案： C 解析： 时间片轮转需要用 PCB 保存进程现场和调度信息，需要时钟中断处理程序在时间片到期时触发抢占，还需要就绪队列按轮转顺序组织可运行进程。阻塞队列属于一般进程管理结构，但不是实现时间片轮转调度本身的必要条件。

16. 【2021】下列事件中, 可引起进程调度程序执行的是（ ）。 I. 中断处理结束 II. 进程阻塞 III. 进程执行结束 IV. 进程的时间片用完

A. 仅 I、 III
B. 仅 II、 IV
C. 仅 III、 IV
D. I、 II、 III、 IV

答案： D 解析： 中断处理结束后可能重新判断是否需要抢占；进程阻塞、执行结束都会使当前 CPU 空闲而必须调度；时间片用完也要重新选择进程。因此四种事件都可能引起调度程序执行。

17. 【2022】进程 P0、 P1、 P2 和 P3 进入就绪队列的时刻、优先级 (值越小优先权越高) 及 CPU 执行时间如下表所示:

进程	进入就绪队列的时刻	优先级	CPU 执行时间
P0	0ms	15	100ms
P1	10ms	20	60ms
P2	10ms	10	20ms
P3	15ms	6	10ms

若系统采用基于优先权的抢占式进程调度算法, 则从 0ms 时刻开始调度, 到 4 个进程都运行结束为止, 发生进程调度的总次数为（ ）。

A. 4
B. 5
C. 6
D. 7

答案： C 解析： 调度过程为：$0\mathrm{ms}$ 选 P0；$10\mathrm{ms}$ P2 到达并抢占 P0；$15\mathrm{ms}$ P3 到达并抢占 P2；$25\mathrm{ms}$ P3 结束后选 P2；$40\mathrm{ms}$ P2 结束后选 P0；P0 结束后再选 P1。共发生 6 次进程选择，即 6 次调度。

18. 【2023】进程 P1、P2 和 P3 进入就绪队列的时刻、优先级 (值越大优先权越高) 以及 CPU 的执行时间如下表所示。

进程名	进入就绪队列的时刻	优先级	CPU 的执行时间
P1	0ms	1	60ms
P2	20ms	10	42ms
P3	30ms	100	13ms

若系统采用基于优先权的抢占式 CPU 调度算法, 从 0ms 时刻开始进行调度, 则 P1、 P2 和 P3 的平均周转时间为（ ）。

A. 60ms
B. 61ms
C. 70ms
D. 71ms

答案： B 解析： P1 在 $0\sim 20\mathrm{ms}$ 运行；P2 到达后抢占 P1，在 $20\sim 30\mathrm{ms}$ 运行；P3 到达后抢占 P2，在 $30\sim 43\mathrm{ms}$ 完成；随后 P2 在 $43\sim 75\mathrm{ms}$ 完成，P1 在 $75\sim 115\mathrm{ms}$ 完成。周转时间分别为 $115$、$55$、$13\mathrm{ms}$，平均为 $\frac{115+55+13}{3}=61\mathrm{ms}$。

19. 【2024】假设某系统使用时间片轮转调度算法进行 CPU 调度, 时间片大小为 5ms, 系统共有 10 个进程,初始时均处于就绪队列,执行结束前仅处于执行态或就绪态。若队尾的进程 P 所需 CPU 时间最短, 时间为 25ms, 在不考虑系统开销的情况下, 则进程 P 的周转时间为（ ）。

A. 200ms
B. 205ms
C. 250ms
D. 295ms

答案： C 解析： P 初始位于 10 个进程的队尾，每轮要等前面 9 个进程各执行一个 $5\mathrm{ms}$ 时间片后才执行。P 需要 $25/5=5$ 个时间片；在其完成前，其余进程所需 CPU 时间不小于 $25\mathrm{ms}$，故每轮均有 10 个进程。P 在第 5 轮末完成，周转时间为 $5\times 10\times 5=250\mathrm{ms}$。

20. 【2016】某进程调度程序采用基于优先数 (priority) 的调度策略, 即选择优先数最小的进程运行, 进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数,引入运行时间 cpuTime 和等待时间 waitTime,初值均为 0。进程处于执行态时, cpuTime 定时加 1,且 waitTime 置 0; 进程处于就绪态时, cpuTime 置 0, waitTime 定时加 1。请回答下列问题: (1) 若调度程序只将 nice 的值作为进程的优先数, 即 priority = nice, 则可能会出现饥饿现象, 为什么? (2) 使用 nice、 cpuTime 和 waitTime 设计一种动态优先数计算方法, 以避免产生饥饿现象, 并说明 waitTime 的作用。

答案： （1）静态优先数可能使低优先级进程长期得不到运行。（2）可令 $priority=nice+cpuTime-waitTime$（必要时可对各项设置权重或上下界）。 解析： （1）若始终只按 nice 选择优先数最小的进程，当高优先级进程不断到达或长期存在时，优先数较大的进程可能一直无法获得 CPU，从而产生饥饿。

（2）一种可行设计为：

$priority=nice+cpuTime-waitTime$。

进程运行时 cpuTime 增大，使 priority 增大、动态优先权降低，抑制其长期占用 CPU；进程在就绪队列等待时 waitTime 增大，使 priority 减小、动态优先权提高。waitTime 实现“老化”，保证等待足够久的进程最终可以被选中，从而避免饥饿。

21. 【2023】 (8 分) 进程 P 通过执行系统调用从键盘接收一个字符的输入。已知此过程中与进程 P 相关的操作包括: ①将进程 P 插入就绪队列；②将进程 P 插入阻塞队列；③将字符从键盘控制器读入系统缓冲区；④启动键盘中断处理程序；⑤进程 P 从系统调用返回；⑥用户在键盘上输入字符。 以上编号① ∼ ⑥仅用于标记操作, 与操作的先后顺序无关。请回答下列问题。 (1) 按照正确的操作顺序, 操作①的前一个和后一个操作分别是上述操作中的哪一个？操作⑥的后一个操作是上述操作中的哪一个? (2) 在上述哪个操作之后, CPU 一定从进程 P 切换到其他进程？在上述哪个操作之后 CPU 调度程序才能选中进程 P 执行？ (3) 完成上述哪个操作的代码属于键盘驱动程序？ (4) 键盘中断处理程序执行时, 进程 P 处于什么状态？ CPU 处于内核态还是用户态？

答案： （1）①的前一操作是③，后一操作是⑤；⑥的后一操作是④。 （2）②之后 CPU 一定切换到其他进程；①之后调度程序才可能选中 P。 （3）③。 （4）P 处于阻塞态，CPU 处于内核态。 解析： 完整顺序可写为：进程 P 执行读键盘系统调用但尚无输入，于是执行②进入阻塞队列；随后用户执行⑥输入字符，触发④键盘中断处理程序；驱动程序执行③，把字符从控制器读入系统缓冲区；系统再执行①，将等待输入的 P 唤醒并插入就绪队列；P 被重新调度后执行⑤，从系统调用返回。

P 在②后不再具备运行条件，CPU 必须切换到其他进程；只有①完成后 P 才重新具备被调度的资格。③直接访问并处理键盘控制器，属于键盘驱动程序。中断发生时 P 尚未被唤醒，仍为阻塞态；中断处理程序在内核态运行。

2.3 进程同步

1. 【2010】进程 P0 和 P1 的共享变量定义及其初值为:

若进程 P0 和 P1 访问临界资源的类 C 伪代码实现如下:

C

boolean flag[2];
int turn = 0;
flag[0] = FALSE; flag[1] = FALSE;

C

void P0（ ）  // 进程 P0
{
    while (TRUE) {
        flag[0] = TRUE; turn = 1;
        while (flag[1] && (turn == 1));
        临界区;
        flag[0] = FALSE;
    }
}

void P1（ ）  // 进程 P1
{
    while (TRUE) {
        flag[1] = TRUE; turn = 0;
        while (flag[0] && (turn == 0));
        临界区;
        flag[1] = FALSE;
    }
}

则并发执行进程 P0 和 P1 时产生的情形是（ ）。

A. 不能保证进程互斥进入临界区, 会出现“饥饿”现象
B. 不能保证进程互斥进入临界区,不会出现“饥饿”现象
C. 能保证进程互斥进入临界区,会出现“饥饿”现象
D. 能保证进程互斥进入临界区,不会出现“饥饿”现象

答案： D 解析： 该算法是 Peterson 两进程互斥算法。flag[i] 表示进程 $P_i$ 希望进入临界区，turn 在双方同时提出请求时决定让哪一方先进入。若两个进程同时置位自己的 flag，最后一次写入 turn 的进程会等待，另一个进程进入临界区，因此可保证互斥。退出临界区时进程会清除自己的 flag，且 turn 机制能够保证有限等待，不会产生饥饿。

2. 【2010】设与某资源关联的信号量初值为 3, 当前值为 1。若 M 表示该资源的可用个数, N 表示等待该资源的进程数, 则 M、 N 分别是（ ）。

A. 0、 1
B. 1、 0
C. 1、 2
D. 2、 0

答案： B 解析： 记录型信号量的值大于等于 0 时，表示当前可用资源数；其绝对值只有在信号量小于 0 时才表示等待进程数。当前值为 1，说明尚有 1 个资源可用，且没有进程因申请该资源而等待，所以 $M=1$，$N=0$。

3. 【2011】有两个并发执行的进程 P1 和 P2, 共享初值为 1 的变量 x。 P1 对 x 加 1,P2 对 x 减 1。加 1 和减 1 操作的指令序列分别如下所示:

asm

// 加 1 操作
load R1, x      /* 取 x 到寄存器 R1 中 */
inc R1
store x, R1     /* 将 R1 的内容存入 x */

// 减 1 操作
load R2, x
dec R2
store x, R2

两个操作完成后, x 的值（ ）。

A. 可能为 -1 或 3
B. 只能为 1
C. 可能为 0、 1 或 2
D. 可能为 -1、 0、 1 或 2

答案： C 解析： 若两个操作串行执行，无论先加后减还是先减后加，最终均有 $x=1$。若两个进程先后读取到初值 1，再分别计算 2 和 0，则最后执行写回的进程决定最终值：加 1 进程最后写回时 $x=2$，减 1 进程最后写回时 $x=0$。因此可能值为 0、1 或 2。

4. 【2016】使用 TSL(Test and SetLock) 指令实现进程互斥的伪代码如下所示:

C

do {
    ...
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ...
} while (TRUE);

下列与该实现机制相关的叙述中, 正确的是（ ）。

A. 退出临界区的进程负责唤醒阻塞态进程
B. 等待进入临界区的进程不会主动放弃 CPU
C. 上述伪代码满足“让权等待”的同步准则
D. while(TSL(&lock)) 语句应在关中断状态下执行

答案： B 解析： TSL 是原子指令。锁已被占用时，等待进程会不断执行 TSL 进行忙等，并不会阻塞或主动让出 CPU，因此 B 正确，C 错误。退出临界区的进程只需把 lock 置为 FALSE，不负责显式唤醒等待进程；TSL 本身已保证原子性，无须在关中断状态下执行。

5. 【2016】进程 P1 和 P2 均包含并发执行的线程, 部分伪代码描述如下所示。下列选项中, 需要互斥执行的操作是（ ）。

进程 P1	进程 P2
int x = 0;``Thread1（ ）``{ int a;`` a = 1; x += 1;``}``Thread2（ ）``{ int a;`` a = 2; x += 2;``}	int x = 0;``Thread3（ ）``{ int a;`` a = x; x += 3;``}``Thread4（ ）``{ int b;`` b = x; x += 4;``}

A. a = 1 与 a = 2
B. a = x 与 b = x
C. x += 1 与 x += 2
D. x += 1 与 x += 3

答案： C 解析： 同一进程内的线程共享该进程的全局变量，而不同进程具有相互独立的地址空间。进程 P1 的 Thread1 和 Thread2 共同访问 P1 的全局变量 x，且 x += 1、x += 2 都是读—改—写操作，必须互斥执行。局部变量 a 分别位于各线程自己的栈中，不共享；P1 与 P2 中名称同为 x 的变量也属于不同地址空间。

6. 【2016】下列关于管程的叙述中,错误的是（ ）。

A. 管程只能用于实现进程的互斥
B. 管程是由编程语言支持的进程同步机制
C. 任何时候只能有一个进程在管程中执行
D. 管程中定义的变量只能被管程内的过程访问

答案： A 解析： 管程既能利用其入口互斥实现互斥访问，也能通过条件变量及 wait、signal 操作实现进程同步，因此并非“只能”实现互斥。管程通常由编程语言及其运行系统提供支持；管程内部数据只能由管程过程访问，并且任一时刻至多允许一个进程在管程内活动。

7. 【2018】属于同一进程的两个线程 thread1 和 thread2 并发执行, 共享初值为 0 的全局变量 x。 thread1 和 thread2 实现对全局变量 x 加 1 的机器级代码描述如下:

asm

thread1:
mov R1, x      /* (x) -> R1 */
inc R1         /* (R1) + 1 -> R1 */
mov x, R1      /* (R1) -> x */

thread2:
mov R2, x      /* (x) -> R2 */
inc R2         /* (R2) + 1 -> R2 */
mov x, R2      /* (R2) -> x */

在所有可能的指令执行序列中, 使 x 的值为 2 的序列个数是（ ）。

A. 1
B. 2
C. 3
D. 4

答案： B 解析： 每个线程内部的 3 条指令顺序不能改变。要使最终 $x=2$，后执行加 1 的线程必须在另一线程写回 1 之后再读取 x。这只可能是 thread1 的 3 条指令全部完成后再执行 thread2，或 thread2 的 3 条指令全部完成后再执行 thread1，共 2 种。其他交错方式都会使两个线程都读取到 0，最终仅写回 1。

8. 【2018】若 x 是管程内的条件变量, 则当进程执行 x.wait（ ） 时所做的工作是（ ）

A. 实现对变量 x 的互斥访问
B. 唤醒一个在 x 上阻塞的进程
C. 根据 x 的值判断该进程是否进入阻塞状态
D. 阻塞该进程, 并将之插入 x 的阻塞队列中

答案： D 解析： 条件变量本身不保存普通数据值，也不是互斥锁。进程执行 x.wait() 后会释放管程的使用权，进入阻塞态，并被插入条件变量 x 对应的等待队列；唤醒等待进程应使用 x.signal()。

9. 【2018】下列同步机制中, 可以实现让权等待的是（ ）。

A. Peterson 方法
B. swap 指令
C. 信号量方法
D. TestAndSet 指令

答案： C 解析： 记录型信号量的 wait 操作在资源不可用时可将进程阻塞，并让出 CPU，满足“让权等待”。Peterson 方法、swap 和 TestAndSet 通常采用忙等方式，等待进程仍不断检查条件，不能实现让权等待。

10. 【2020】下列准则中, 实现临界区互斥机制必须遵循的是（ ）。 I. 两个进程不能同时进入临界区 II. 允许进程访问空闲的临界资源 III. 进程等待进入临界区的时间是有限的 IV. 不能进入临界区的执行态进程立即放弃 CPU

A. 仅 I、 IV
B. 仅 II、 III
C. 仅 I、 II、 III
D. 仅 I、 III、 IV

答案： C 解析： 临界区互斥机制必须满足空闲让进、忙则等待和有限等待，因此 I、II、III 正确。IV 对应“让权等待”，它是提高效率的重要原则，但忙等型互斥算法也能正确实现互斥，所以不是所有互斥机制都必须满足的条件。

11. 【2009】三个进程 P1、 P2、 P3 互斥使用一个包含 N ($N>0$) 个单元的缓冲区。 P1 每次用 produce（ ） 生成一个正整数并用 put（ ） 送入缓冲区某一空单元中;P2 每次用 getodd（ ） 从该缓冲区中取出一个奇数并用 countodd（ ） 统计奇数个数; P3 每次用 geteven（ ） 从该缓冲区中取出一个偶数并用 counteven（ ） 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动, 并说明所定义信号量的含义 (要求用伪代码描述)。

答案： 设信号量如下：

• empty=N：缓冲区中空单元的数量；
• odd=0：缓冲区中奇数的数量；
• even=0：缓冲区中偶数的数量；
• mutex=1：实现对缓冲区的互斥访问。

C

semaphore empty = N, odd = 0, even = 0, mutex = 1;

process P1() {
    while (TRUE) {
        int x = produce();
        wait(empty);
        wait(mutex);
        put(x);
        signal(mutex);
        if (x % 2 == 1)
            signal(odd);
        else
            signal(even);
    }
}

process P2() {
    while (TRUE) {
        wait(odd);
        wait(mutex);
        int x = getodd();
        signal(mutex);
        signal(empty);
        countodd(x);
    }
}

process P3() {
    while (TRUE) {
        wait(even);
        wait(mutex);
        int x = geteven();
        signal(mutex);
        signal(empty);
        counteven(x);
    }
}

解析： 生产者放入产品前必须确认存在空单元，消费者取出产品前必须确认存在相应奇偶性的产品。mutex 保护缓冲区内部结构，防止多个进程同时执行 put、getodd 或 geteven。生产者应先完成实际放入，再增加 odd 或 even；消费者应先取得相应产品，再增加 empty。各进程均按“同步信号量在前、互斥信号量在后”的顺序执行 wait，可避免占有互斥锁后因条件不满足而阻塞。

12. 【2011】某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下:

Text

Cobegin {
    process 顾客 {
        从取号机获取一个号码;
        等待叫号;
        获取服务;
    }

    process 营业员 {
        while (TRUE) {
            叫号;
            为客户服务;
        }
    }
} Coend

请添加必要的信号量和 P/V (或 wait（ ）、 signal（ ）) 操作, 实现上述过程中的互斥与同步。要求写出完整的过程, 说明信号量的含义并赋初值。

答案： 设：

• seat=10：空闲等待座位数；
• ticket=1：取号机互斥信号量；
• customer=0：已经取号并等待叫号的顾客数；
• called=0：营业员已经叫号、允许一位顾客接受服务。

C

semaphore seat = 10, ticket = 1;
semaphore customer = 0, called = 0;

process 顾客() {
    wait(seat);

    wait(ticket);
    从取号机获取一个号码;
    signal(ticket);

    signal(customer);
    wait(called);
    signal(seat);       // 被叫号后离开等待座位
    获取服务;
}

process 营业员() {
    while (TRUE) {
        wait(customer);
        叫号;
        signal(called);
        为客户服务;
    }
}

解析： seat 限制等待区中至多有 10 位顾客；ticket 保证取号机一次只被一位顾客使用；customer 使营业员在无人等待时阻塞；called 使顾客在营业员叫号前不能直接接受服务。营业员每次只发出一次 signal(called)，因此一次只唤醒一位等待顾客。顾客被叫号后即离开等待座位，所以此时归还 seat。

13. 【2013】某博物馆最多可容纳 500 人同时参观, 有一个出入口, 该出入口一次仅允许通过一个人。参观者的活动描述如下:

Text

cobegin
参观者进程 i：
{
    ...
    进门；
    ...
    参观；
    ...
    出门；
    ...
}
coend

请添加必要的信号量和 P/V (或 wait（ ）、 signal（ ）) 操作, 以实现上述过程中的互斥与同步。要求写出完整的过程,说明信号量的含义并赋初值。

答案： 设 capacity=500 表示馆内剩余容量，door=1 表示出入口的互斥使用权。

C

semaphore capacity = 500;
semaphore door = 1;

cobegin
process 参观者 i {
    wait(capacity);
    wait(door);
    进门;
    signal(door);

    参观;

    wait(door);
    出门;
    signal(door);
    signal(capacity);
}
coend

解析： 进入前执行 wait(capacity)，保证已经获准入馆但尚未离馆的人数不超过 500。进门和出门都必须经过同一个出入口，因此两种操作共用二元信号量 door 进行互斥。参观者完成出门后才释放一个容量名额。

14. 【2014】系统中有多个生产者进程和多个消费者进程,共享一个能存放 1000 件产品的环形缓冲区 (初始为空)。当缓冲区未满时, 生产者进程可以放入其生产的一件产品, 否则等待；当缓冲区未空时,消费者进程可以从缓冲区取走一件产品,否则等待。要求一个消费者进程从缓冲区连续取出 10 件产品后,其他消费者进程才可以取产品。请使用信号量 P/V (wait（ ）、 signal（ ）) 操作实现进程间的互斥与同步, 要求写出完整的过程, 并说明所用信号量的含义和初值。

答案： 设：

• empty=1000：空缓冲单元数；
• full=0：已有产品数；
• mutex=1：环形缓冲区互斥信号量；
• consumerMutex=1：消费者组互斥信号量，保证同一消费者连续取 10 件。

C

semaphore empty = 1000, full = 0;
semaphore mutex = 1, consumerMutex = 1;

process 生产者() {
    while (TRUE) {
        item x = produce();
        wait(empty);
        wait(mutex);
        put(x);
        signal(mutex);
        signal(full);
    }
}

process 消费者() {
    while (TRUE) {
        wait(consumerMutex);
        for (int i = 0; i < 10; ++i) {
            wait(full);
            wait(mutex);
            item x = get();
            signal(mutex);
            signal(empty);
            consume(x);
        }
        signal(consumerMutex);
    }
}

解析： empty 与 full 实现生产者和消费者之间的同步，mutex 保证对环形缓冲区的插入、删除操作互斥。某消费者取得 consumerMutex 后，在释放它之前连续执行 10 次取产品操作，因此其他消费者不能在这 10 次之间取产品。生产者不使用 consumerMutex，仍可在消费者等待产品期间继续生产，避免不必要地降低并发度。

15. 【2015】 (9 分) 有 A、 B 两人通过信箱进行辩论, 每个人都从自己的信箱中取得对方的问题。 将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设 A 的信箱最多放 M 个邮件, B 的信箱最多放 N 个邮件。初始时 A 的信箱中有 x 个邮件 ($0<x<M$),B 的信箱中有 y 个 ($0<y<N$)。 辩论者每取出一个邮件, 邮件数减 1。 A 和 B 两人的操作过程描述如下所示。

Text

Cobegin
A {
    while (TRUE) {
        从 A 的信箱中取出一个邮件;
        回答问题并提出一个新问题;
        将新邮件放入 B 的信箱;
    }
}

B {
    while (TRUE) {
        从 B 的信箱中取出一个邮件;
        回答问题并提出一个新问题;
        将新邮件放入 A 的信箱;
    }
}
CoEnd

当信箱不为空时,辩论者才能从信箱中取邮件,否则需要等待。当信箱不满时,辩论者才能将新邮件放入信箱, 否则需要等待。请添加必要的信号量和 P/V (或 wait、 signal) 操作, 以实现上述过程的同步。要求写出完整过程, 并说明信号量的含义和初值。

答案： 设：

• Afull=x、Aempty=M-x：A 信箱中的邮件数和空位置数；
• Bfull=y、Bempty=N-y：B 信箱中的邮件数和空位置数。

C

semaphore Afull = x, Aempty = M - x;
semaphore Bfull = y, Bempty = N - y;

Cobegin
process A {
    while (TRUE) {
        wait(Afull);
        从 A 的信箱中取出一个邮件;
        signal(Aempty);

        回答问题并提出一个新问题;

        wait(Bempty);
        将新邮件放入 B 的信箱;
        signal(Bfull);
    }
}

process B {
    while (TRUE) {
        wait(Bfull);
        从 B 的信箱中取出一个邮件;
        signal(Bempty);

        回答问题并提出一个新问题;

        wait(Aempty);
        将新邮件放入 A 的信箱;
        signal(Afull);
    }
}
CoEnd

解析： A 是 A 信箱的唯一取件者、B 信箱的唯一投件者；B 则相反，因此每个信箱都只有一个生产者和一个消费者，题设下无须额外设置互斥信号量。full 保证信箱非空时才能取件，empty 保证信箱未满时才能投件。每次取件后立即增加对应空位置数，每次投件后再增加对应邮件数。

16. 【2019】有 n (n≥3) 位哲学家围坐在一张圆桌边, 每位哲学家交替地就餐和思考。在圆桌中心有 m (m≥1) 个碗, 每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后, 才能就餐, 进餐完毕, 将碗和筷子放回原位, 并继续思考。为使尽可能多的哲学家同时就餐, 且防止出现死锁现象, 请使用信号量的 P/V 操作 [wait（ ）、 signal（ ） 操作] 描述上述过程中的互斥与同步,并说明所用信号量及初值的含义。

答案： 设 chopstick[i]=1 表示第 i 根筷子可用，设 bowl=min(m,n-1) 表示允许同时进入取筷子阶段的哲学家数，同时也代表可用碗数。

C

semaphore chopstick[0 ... n-1] = {1, 1, ..., 1};
semaphore bowl = min(m, n - 1);

process philosopher(i) {
    while (TRUE) {
        think();

        wait(bowl);
        wait(chopstick[i]);
        wait(chopstick[(i + 1) % n]);

        eat();

        signal(chopstick[(i + 1) % n]);
        signal(chopstick[i]);
        signal(bowl);
    }
}

解析： 每根筷子由一个二元信号量保护。若碗数少于哲学家数，则至多有 m 位哲学家参与取筷子；若碗数不少于哲学家数，则把允许参与取筷子的哲学家数限制为 $n-1$，保证至少有一位哲学家不占有筷子，从而破坏形成环路等待的条件。bowl 的初值取 $\min (m,n-1)$ 不会降低系统实际能够达到的最大同时就餐人数，因为相邻哲学家本来就不能同时就餐，最多只能有 $\lfloor n/2\rfloor$ 人同时就餐。

17. 【2020】现有 5 个操作 A、 B、 C、 D 和 E, 操作 C 必须在 A 和 B 完成后执行, 操作 E 必须在 C 和 D 完成后执行,请使用信号量的 wait（ ）、 signal（ ） 操作 (P/V 操作) 描述上述操作之间的同步关系,并说明所用信号量及其初值。

答案： 设 SA=0、SB=0、SC=0、SD=0，分别表示操作 A、B、C、D 是否已经完成。

C

semaphore SA = 0, SB = 0, SC = 0, SD = 0;

process PA {
    A;
    signal(SA);
}

process PB {
    B;
    signal(SB);
}

process PC {
    wait(SA);
    wait(SB);
    C;
    signal(SC);
}

process PD {
    D;
    signal(SD);
}

process PE {
    wait(SC);
    wait(SD);
    E;
}

解析： C 在执行前分别等待 A 和 B 的完成信号，因此只有 A、B 都完成后才能执行。E 在执行前分别等待 C 和 D 的完成信号，因此只有 C、D 都完成后才能执行。A、B、D 之间没有先后约束，可以并发执行。

18. 【2017】某进程中有 3 个并发执行的线程 thread1、 thread2 和 thread3, 其伪代码如下所示:

C

// 复数的结构类型定义
typedef struct
{
    float a;
    float b;
} cnum;

cnum x, y, z;  // 全局变量

// 计算两个复数之和
cnum add(cnum p, cnum q) {
    cnum s;
    s.a = p.a + q.a;
    s.b = p.b + q.b;
    return s;
}

thread1
{
    cnum w;
    w = add(x, y);
    ...
}

thread2
{
    cnum w;
    w = add(y, z);
    ...
}

thread3
{
    cnum w;
    w.a = 1;
    w.b = 1;
    z = add(z, w);
    y = add(y, w);
    ...
}

请添加必要的信号量和 P/V (或 wait（ ）、 signal（ ）) 操作, 要求确保线程互斥访问临界资源, 并且最大限度地并发执行。

答案： 变量 x 只读，无须保护；变量 y、z 可能被 thread3 修改，分别设置二元信号量 my=1、mz=1。

C

semaphore my = 1, mz = 1;

thread1 {
    cnum w;
    wait(my);
    w = add(x, y);
    signal(my);
    ...
}

thread2 {
    cnum w;
    wait(my);
    wait(mz);
    w = add(y, z);
    signal(mz);
    signal(my);
    ...
}

thread3 {
    cnum w;
    w.a = 1;
    w.b = 1;

    wait(mz);
    z = add(z, w);
    signal(mz);

    wait(my);
    y = add(y, w);
    signal(my);
    ...
}

解析： thread1 只需与 thread3 对 y 的修改互斥；thread2 同时读取 y 和 z，所以读取期间需要同时锁住两者；thread3 对 z、y 的修改彼此独立，可分别加锁后立即释放，以提高并发度。所有需要同时获取两个锁的线程均按 my、mz 的固定顺序加锁，可避免因加锁次序相反而产生死锁。

19. 【2021】下表给出了整型信号量 S 的 wait（ ） 和 signal（ ） 操作的功能描述, 以及采用开 / 关中断指令实现信号量操作互斥的两种方法如下。

功能描述

C

Semaphore S;
wait(S) {
    while (S <= 0);
    S = S - 1;
}

signal(S) {
    S = S + 1;
}

方法 1

C

Semaphore S;
wait(S) {
    关中断;
    while (S <= 0);
    S = S - 1;
    开中断;
}

signal(S) {
    关中断;
    S = S + 1;
    开中断;
}

方法 2

C

Semaphore S;
wait(S) {
    关中断;
    while (S <= 0) {
        开中断;
        关中断;
    }
    S = S - 1;
    开中断;
}

signal(S) {
    关中断;
    S = S + 1;
    开中断;
}

回答以下问题: (1) 为什么在 wait（ ） 和 signal（ ） 操作中对信号量 S 的访问必须互斥执行？ (2) 分别说明方法 1 和方法 2 是否正确。若不正确, 请说明理由。 (3) 用户程序能否使用开 / 关中断指令实现临界区互斥？为什么？

答案：

1. 对 S 的判断、修改必须作为不可分割的原子操作互斥执行，否则会发生竞争，导致信号量值和实际资源使用情况不一致。

2. 方法 1 错误；方法 2 正确。

3. 用户程序不能直接用开 / 关中断指令实现互斥。 解析：

4. 例如当 $S=1$ 时，两个进程若同时判断出 S>0，就可能都继续执行减 1 并进入临界区，从而破坏互斥；wait 与 signal 并发修改 S 时也可能发生更新丢失。因此访问 S 的关键步骤必须原子执行。

5. 方法 1 在 S<=0 时保持关中断并持续忙等。在单处理机系统中，当前进程无法被中断或调度出去，能够执行 signal(S) 的进程也无法运行，因而可能永久等待。方法 2 在每次发现 S<=0 时暂时开中断，使其他进程或中断处理程序有机会运行并执行 signal；对 S 的检查与减 1，以及加 1 操作仍在关中断区间内，因而可以保证互斥。

6. 开 / 关中断属于特权指令，只能在内核态执行。若允许用户程序任意关中断，可能使系统长期无法响应中断和进行调度，破坏系统安全与稳定。

7. 【2022】某进程的两个线程 T1 和 T2 并发执行 A、 B、 C、 D、 E 和 F 共 6 个操作, 其中 T1 执行 A、 E 和 F,T2 执行 B、 C 和 D。右图表示上述 6 个操作的执行顺序所必须满足的约束:C 在 A 和 B 完成后执行, D 和 E 在 C 完成后执行, F 在 E 完成后执行。请使用信号量的 wait（ ）、 signal（ ） 操作描述 T1 和 T2 之间的同步关系,并说明所用信号量的作用及其初值。

Text

A ─┐
   ├──> C ───> D
B ─┘      └──> E ───> F

答案： 设 SA=0 表示 A 尚未完成，SC=0 表示 C 尚未完成。

C

semaphore SA = 0, SC = 0;

thread T1 {
    A;
    signal(SA);

    wait(SC);
    E;
    F;
}

thread T2 {
    B;
    wait(SA);
    C;
    signal(SC);
    D;
}

解析： 在 T2 内部，B 本来就在 C 之前，因此 C 只需额外等待 A 的完成信号；在 T1 内部，F 本来就在 E 之后，因此只需让 E 等待 C 的完成信号。D 位于 T2 中 C 的后面，自然满足 D 在 C 后执行。使用两个初值为 0 的信号量即可实现全部跨线程约束。

21. 【2023】 (7 分) 现要求学生使用 swap 指令和布尔型变量 lock 实现临界区互斥。 lock 为线程间共享的变量。 lock 的值为 TRUE 时线程不能进入临界区,为 FALSE 时线程能够进入临界区。某同学编写的实现临界区互斥的伪代码如下图 (a) 所示。

图 (a)：某同学编写的伪代码

C

bool lock = FALSE;  // 共享变量
...
bool key = TRUE;
if (key == TRUE)
    swap key, lock;  // 交换 key 和 lock 的值
临界区;
lock = TRUE;
...

图 (b)：newSwap（ ） 的代码

C

void newSwap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

请回答下列问题。 (1) 图 (a) 的伪代码中哪些语句存在错误？将其改为正确的语句 (不增加语句条数)。 (2) 图 (b) 给出了交换两个变量值的函数 newSwap（ ） 的代码, 是否可以用函数调用语句 “newSwap(&key,&lock)” 代替指令 “swap key, lock” 以实现临界区互斥? 为什么?

答案：

1. 将 if (key == TRUE) 改为 while (key == TRUE)；将退出临界区后的 lock = TRUE 改为 lock = FALSE。修改后为：

C

bool lock = FALSE;
...
bool key = TRUE;
while (key == TRUE)
    swap key, lock;
临界区;
lock = FALSE;
...

2. 不能用普通函数 newSwap(&key,&lock) 代替原子 swap 指令。 解析： 当锁空闲时，lock=FALSE。线程令 key=TRUE 后执行原子交换，可得到 key=FALSE、lock=TRUE，从而退出循环并进入临界区；锁被占用时交换后 key 仍为 TRUE，线程继续循环等待。若只使用 if，交换一次后无论是否取得锁都会继续进入临界区；退出时必须把锁恢复为 FALSE 才表示锁空闲。newSwap 由多条普通指令组成，执行过程中可能发生线程切换，两个线程可能交错读写 key 和 lock，不具备不可分割的原子性，因而不能保证互斥。

3. 【2024】 (8 分) 计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中, 缓冲区 B 用于存放一个数据分组, 对 B 的操作有 C1、 C2 和 C3。 C1 将一个数据分组写入 B 中, C2 从 B 中读出一个数据分组, C3 对 B 中的数据分组进行修改。要求 B 为空时才能执行 C1,B 非空时才能执行 C2 和 C3。请回答下列问题。 (1) 假设进程 P1 和 P2 都需要执行 C1, 实现 C1 的代码是否为临界区？为什么？ (2) 假设 B 初始为空, 进程 P1 执行 C1 一次, 进程 P2 执行 C2 一次。请定义尽可能少的信号量,并用 wait（ ）, signal（ ） 操作描述进程 P1 和 P2 之间的同步或互斥关系,说明所用信号量的作用及其初值。 (3) 若 B 初始不为空, 进程 P1 和 P2 各执行 C3 一次, 请定义尽可能少的信号量, 用 wait（ ）, signal（ ） 操作描述进程 P1 和 P2 之间的同步或互斥关系,说明所用信号量的作用及其初值。

答案：

1. 是临界区。P1、P2 都会写共享缓冲区 B，若并发执行 C1，可能相互覆盖数据并破坏 B 的一致性，因此必须互斥。
2. 只需一个同步信号量 full=0，表示 B 中是否已有可供读取的数据分组：

C

semaphore full = 0;

process P1 {
    C1;
    signal(full);
}

process P2 {
    wait(full);
    C2;
}

3. 只需一个二元互斥信号量 mutex=1：

C

semaphore mutex = 1;

process P1 {
    wait(mutex);
    C3;
    signal(mutex);
}

process P2 {
    wait(mutex);
    C3;
    signal(mutex);
}

解析： 第（2）问中 B 初始为空，P2 必须等待 P1 写入后才能读取；由于每个进程各执行一次，full 所建立的先写后读顺序已经排除了同时访问，无须再设置互斥信号量。第（3）问中 B 已非空，不存在“等待数据产生”的同步问题，但两个进程都会修改同一数据分组，必须用二元信号量保证两次 C3 串行执行。

2.4 死锁

1. 【2009】某计算机系统中有 8 台打印机, 由 K 个进程竞争使用, 每个进程最多需要 3 台打印机。 该系统可能会发生死锁的 K 的最小值是（ ）。

A. 2
B. 3
C. 4
D. 5

答案： C 解析： 若有 K 个进程，每个进程先各占有 2 台打印机，再继续申请第 3 台，则可能发生死锁。要出现这种状态，至少需要满足 $2K\le 8$，且 8 台打印机全部被占有。取 $K=4$ 时，每个进程各占 2 台，所有进程都等待第 3 台，正好可能形成死锁；当 $K\le 3$ 时，即使每个进程各占 2 台，仍至少剩余 2 台，可使某进程获得第 3 台并完成。因此最小值为 4。

2. 【2011】某时刻进程的资源使用情况如下表所示:

进程	已分配 R1	已分配 R2	已分配 R3	尚需 R1	尚需 R2	尚需 R3	可用 R1	可用 R2	可用 R3
P1	2	0	0	0	0	1	0	2	1
P2	1	2	0	1	3	2	0	2	1
P3	0	1	1	1	3	1	0	2	1
P4	0	0	1	2	0	0	0	2	1

此时的安全序列是（ ）。

A. P1,P2,P3,P4
B. P1,P3,P2,P4
C. P1,P4,P3,P2
D. 不存在

答案： D 解析： 初始可用资源向量为 $(0,2,1)$，只有 P1 的尚需量 $(0,0,1)$ 能够满足。P1 完成并释放资源后，可用量变为 $(2,2,1)$；此时只有 P4 的尚需量 $(2,0,0)$ 能够满足。P4 完成后，可用量为 $(2,2,2)$，但 P2、P3 对 R2 的尚需量均为 3，仍不能完成，因此不存在能够使所有进程依次完成的安全序列。

3. 【2012】假设 5 个进程 P0、 P1、 P2、 P3、 P4 共享三类资源 R1、 R2、 R3, 这些资源总数分别为 18, 6,22。 T0 时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。

进程	已分配 R1	已分配 R2	已分配 R3	资源最大需求 R1	资源最大需求 R2	资源最大需求 R3
P0	3	2	3	5	5	10
P1	4	0	3	5	3	6
P2	4	0	5	4	0	11
P3	2	0	4	4	2	5
P4	3	1	4	4	2	4

A. P0,P2,P4,P1,P3
B. P1,P0,P3,P4,P2
C. P2,P1,P0,P3,P4
D. P3,P4,P2,P1,P0

答案： D 解析： 已分配资源总量为 $(16,3,19)$，故初始可用资源为 $(18,6,22)-(16,3,19)=(2,3,3)$。各进程尚需资源分别为：

$P_0:(2,3,7)$，$P_1:(1,3,3)$，$P_2:(0,0,6)$，$P_3:(2,2,1)$，$P_4:(1,1,0)$。

按 D 的顺序检查：P3 可完成，释放后可用量为 $(4,3,7)$；P4 完成后为 $(7,4,11)$；P2 完成后为 $(11,4,16)$；P1 完成后为 $(15,4,19)$；最后 P0 也能完成。因此 D 是安全序列。

4. 【2013】下列关于银行家算法的叙述中, 正确的是（ ）。

A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程
C. 当系统处于不安全状态时,系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

答案： B 解析： 银行家算法属于死锁避免算法，而不是死锁预防算法；它并不直接破坏死锁的四个必要条件。安全状态意味着至少存在一个安全序列，所有进程均可按该序列完成，所以当前一定没有死锁。不安全状态只表示未来存在发生死锁的可能，并不意味着当前已经死锁或以后一定死锁。

5. 【2014】某系统有 n 台互斥使用的同类设备, 三个并发进程分别需要 3、 4、 5 台设备, 可确保系统不发生死锁的设备数 n 最小为（ ）。

A. 9
B. 10
C. 11
D. 12

答案： B 解析： 对最大需求分别为 3、4、5 的三个进程，最坏情况下它们分别占有 2、3、4 台设备并继续等待 1 台。若设备总数至少为

$(3-1)+(4-1)+(5-1)+1=10$，

则在最坏情况下仍至少有 1 台空闲设备，可使某个进程取得最后一台设备、完成并释放全部资源，随后其他进程也可继续完成。因此确保不发生死锁的最小设备数为 10。

6. 【2015】若系统 S1 采用死锁避免方法, S2 采用死锁检测方法。下列叙述中, 正确的是（ ）。 I. S1 会限制用户申请资源的顺序, 而 S2 不会 II. S1 需要进程运行所需资源总量信息, 而 S2 不需要 III. S1 不会给可能导致死锁的进程分配资源,而 S2 会

A. 仅 I、 II
B. 仅 II、 III
C. 仅 I、 III
D. I、 II、 III

答案： B 解析： 死锁避免方法在每次分配前判断分配后系统是否仍安全，通常需要预先知道进程的最大资源需求；死锁检测只根据当前分配和请求情况判断，无须知道进程运行全过程的最大需求，所以 II 正确。死锁避免会拒绝可能使系统进入不安全状态的分配，而死锁检测允许系统先分配资源、发生死锁后再检测与解除，所以 III 正确。限制资源申请顺序属于死锁预防中破坏循环等待条件的方法，不是死锁避免算法的必然要求，因此 I 错误。

7. 【2016】系统中有 3 个不同的临界资源 R1、 R2 和 R3, 被 4 个进程 P1、 P2、 P3 及 P4 共享。各进程对资源的需求为:P1 申请 R1 和 R2,P2 申请 R2 和 R3,P3 申请 R1 和 R3,P4 申请 R2。若系统出现死锁, 则处于死锁状态的进程数至少是（ ）。

A. 1
B. 2
C. 3
D. 4

答案： C 解析： P4 只申请一种资源 R2，不可能单独构成“占有一种资源并等待另一种资源”的环路。任意两个 P1、P2、P3 之间都不能形成完整循环，例如 P1 可占有 R1 等待 R2，P2 可占有 R2，但 P2 还需要等待 R3，而 R3 只能由第三个进程占有。可构造最小死锁环：P1 占有 R1 等待 R2，P2 占有 R2 等待 R3，P3 占有 R3 等待 R1。因此至少有 3 个进程处于死锁状态。

8. 【2018】假设系统中有 4 个同类资源, 进程 P1、 P2 和 P3 需要的资源数分别为 4、 3 和 1、 P1、 P2 和 P3 已申请到的资源数分别为 2、 1 和 0, 则执行安全性检测算法的结果是（ ）。

A. 不存在安全序列, 系统处于不安全状态
B. 存在多个安全序列,系统处于安全状态
C. 存在唯一安全序列 P3,P1,P2, 系统处于安全状态
D. 存在唯一安全序列 P3,P2,P1, 系统处于安全状态

答案： A 解析： 当前已分配资源数为 $2+1+0=3$，所以可用资源数为 1。P1、P2、P3 尚需资源数分别为 2、2、1，只有 P3 能先满足。但 P3 当前未占有资源，完成后不会释放新的资源，可用资源仍为 1；此后 P1、P2 都还需要 2 个资源，均不能完成。因此不存在安全序列，系统处于不安全状态。

9. 【2019】下列关于死锁的叙述中,正确的是（ ）。 I. 可以通过剥夺进程资源解除死锁 II. 死锁的预防方法能确保系统不发生死锁 III. 银行家算法可以判断系统是否处于死锁状态 IV. 当系统出现死锁时, 必然有两个或两个以上的进程处于阻塞态

A. 仅 II、 III
B. 仅 I、 II、 IV
C. 仅 I、 II、 III
D. 仅 I、 III、 IV

答案： B 解析： 解除死锁的方法包括资源剥夺、撤销进程和进程回退，因此 I 正确。死锁预防通过破坏死锁的至少一个必要条件，可确保系统不发生死锁，因此 II 正确。银行家算法用于在分配前判断系统是否仍处于安全状态，属于死锁避免算法，不能把“不安全”直接等同于“已经死锁”，所以 III 错误。死锁由一组进程循环等待资源形成，至少有两个进程因等待资源而阻塞，因此 IV 正确。

10. 【2020】某系统中有 A、 B 两类资源各 6 个, t 时刻资源分配及需求情况如下表所示:

进程	A 已分配数量	B 已分配数量	A 需求总量	B 需求总量
P1	2	3	4	4
P2	2	1	3	1
P3	1	2	3	4

t 时刻安全性检测结果是（ ）。

A. 存在安全序列 P1,P2,P3
B. 存在安全序列 P2,P1,P3
C. 存在安全序列 P2,P3,P1
D. 不存在安全序列

答案： B 解析： A、B 两类资源的已分配总数分别为 5 和 6，因此初始可用资源向量为 $(1,0)$。各进程尚需资源分别为 P1：$(2,1)$，P2：$(1,0)$，P3：$(2,2)$。只有 P2 能先完成，释放资源后可用量变为 $(3,1)$；此时 P1 可以完成，释放后可用量变为 $(5,4)$；最后 P3 完成。因此存在安全序列 P2、P1、P3。

11. 【2021】若系统中有 $n(n\ge 2)$ 个进程, 每个进程均需要使用某类临界资源 2 个, 则系统不会发生死锁所需的该类资源总数至少是（ ）。

A. 2
B. $n$
C. $n+1$
D. $2n$

答案： C 解析： 每个进程最多需要 2 个同类资源。最不利的分配情况是 $n$ 个进程各占有 1 个资源，并且都继续申请第 2 个资源。若资源总数只有 $n$ 个，此时没有空闲资源，所有进程都会相互等待，从而可能发生死锁。

若资源总数为 $n+1$，则即使 $n$ 个进程各占有 1 个资源，系统中仍有 1 个空闲资源。该资源可分配给任意一个进程，使其获得所需的第 2 个资源并执行完毕；该进程释放资源后，其他进程便可依次完成。因此，保证系统不发生死锁所需的最少资源数为 $n+1$。

12. 【2022】系统中有三个进程 P0、 P1、 P2 及三类资源 A、 B、 C。若某时刻系统分配资源的情况如下表所示, 则此时系统中存在的安全序列的个数为（ ）。

进程	已分配 A	已分配 B	已分配 C	尚需 A	尚需 B	尚需 C	可用 A	可用 B	可用 C
P0	2	0	1	0	2	1	1	3	2
P1	0	2	0	1	2	3	1	3	2
P2	1	0	1	0	1	3	1	3	2

A. 1
B. 2
C. 3
D. 4

答案： B 解析： 初始可用资源向量为 $(1,3,2)$。三个进程的尚需资源向量分别为：

$P_0:(0,2,1)$，$P_1:(1,2,3)$，$P_2:(0,1,3)$。

初始时只有 P0 的尚需量不超过可用量，因此安全序列必须以 P0 开始。P0 完成后释放已分配资源 $(2,0,1)$，可用资源变为

$(1,3,2)+(2,0,1)=(3,3,3)$。

此时 P1 和 P2 均可完成：

• 若先执行 P1，再执行 P2，则得到安全序列 P0、P1、P2；
• 若先执行 P2，再执行 P1，则得到安全序列 P0、P2、P1。

除此之外不存在其他安全序列，因此安全序列共有 2 个。