51. D
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 51. D
中断处理阶段运行的是中断处理程序，中断处理结束后，需要返回原程序或重新选择程序运行，而后者需要进行进程调度，例如在时间片轮转调度中，时钟中断处理结束后，若当前进程的时间片用完，则会发生进程调度。当前进程阻塞时，将其放入阻塞队列，若就绪队列不空，则调度新进程执行。进程执行结束会导致当前进程释放CPU，并从就绪队列中选择一个进程获得CPU。进程时间片用完，会导致当前进程让出CPU，同时选择就绪队列的队首进程获得CPU。
## 52. C
需要注意的是，在0时刻， $\mathrm{P_0}$ 获得CPU也是一次进程调度，所以0时刻调度进程 $\mathrm{P_0}$ 获得CPU： $10\mathrm{ms}$ 时 $\mathrm{P_2}$ 进入就绪队列，调度 $\mathrm{P_2}$ 抢占获得CPU： $15\mathrm{ms}$ 时 $\mathrm{P_3}$ 进入就绪队列，调度 $\mathrm{P_3}$ 抢占获得CPU： $25\mathrm{ms}$ 时 $\mathrm{P_3}$ 执行完毕，调度 $\mathrm{P_2}$ 获得CPU： $40\mathrm{ms}$ 时 $\mathrm{P_2}$ 执行完毕，调度 $\mathrm{P_0}$ 获得CPU： $130\mathrm{ms}$ 时 $\mathrm{P_0}$ 执行完毕，调度 $\mathrm{P_1}$ 获得CPU： $190\mathrm{ms}$ 时 $\mathrm{P_1}$ 执行完毕，结束：总共调度6次。
## 53. B
采用抢占式优先权调度算法，三个作业的执行顺序如下图所示。
周转时间 = 完成时间 - 到达时间。 $\mathrm{P_1}$ 的周转时间 = $115 - 0 = 115\mathrm{ms}$；$\mathrm{P_2}$ 的周转时间 = $75 - 20 = 55\mathrm{ms}$；$\mathrm{P_3}$ 的周转时间 = $43 - 30 = 13\mathrm{ms}$，所以平均周转时间 = $(115 + 55 + 13) / 3 = 61\mathrm{ms}$。
## 54. C
系统使用时间片轮转调度算法，最初共有10个进程处于就绪队列，进程P处于队尾，时间片大小为 $5\mathrm{ms}$。假设当 $t = 0$ 时开始进程调度，就绪队列的前9个进程依次运行一个时间片，则当 $t = 45\mathrm{ms}$ 时调度进程P运行，运行 $5\mathrm{ms}$ 后，当 $t = 50\mathrm{ms}$ 时又开始新一轮循环。进程P所需的CPU时间为 $25\mathrm{ms}$，共需5轮循环，其他进程所需的CPU时间都比进程P的长，这5轮循环中其余9个进程都不会运行结束，因此进程P的周转时间为 $50\times 5 = 250\mathrm{ms}$。
## 55. D
进程切换时，需要进行上下文切换，主要完成：①将当前CPU中各寄存器的内容保存到当前进程的PCB中；②将新进程的现场信息装入CPU的各个寄存器。③将控制转至新进程执行，即更新程序计数器（PC）的值。栈基址寄存器用来指明系统内核栈位置的寄存器，页表基址寄存器用来指明当前进程顶级页表基地址的寄存器，属于进程控制信息。因此，选项I、II、III均需要更新。
<!-- page: 104 -->
## 二、综合应用题
### 01.【解答】
多级反馈队列调度算法能较好地满足各种类型用户的需要。对终端型作业用户而言，由于它们提交的作业大多属于交互型作业，作业通常比较短小，系统只要能使这些作业在第1级队列所规定的时间片内完成，便可使终端型作业用户感到满意；对短批处理作业用户而言，它们的作业开始时像终端型作业一样，若仅在第1级队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间，对于稍长的作业，通常也只需要在第2级队列和第3级队列中各执行一个时间片即可完成，其周转时间仍然较短；对长批处理作业用户而言，它们的长作业将依次在第1,2,…,n级队列中运行，然后按时间片轮转方式运行，用户不必担心其作业长期得不到处理。
### 02.【解答】
由题意可知，各类进程之间采用优先级调度算法，而同类进程内部采用时间片轮转调度算法。因此，系统首先对优先级为4的进程 $\mathrm{P_1},\mathrm{P_2},\mathrm{P_3}$ 采用时间片轮转调度算法运行；当 $\mathrm{P_1},\mathrm{P_2},\mathrm{P_3}$ 均运行结束或没有可运行的进程（$\mathrm{P_1},\mathrm{P_2},\mathrm{P_3}$ 都处于等待态；或者其中部分进程已运行结束，其余进程处于等待态）时，对优先级为3的进程 $\mathrm{P_4},\mathrm{P_5}$ 采用时间片轮转调度算法运行。在此期间，若未结束的 $\mathrm{P_1},\mathrm{P_2},\mathrm{P_3}$ 有一个转为就绪态，则当前时间片用完后又回到优先级4进行调度。类似地，当 $\mathrm{P_1} \sim \mathrm{P_5}$ 均运行结束或没有可运行进程（$\mathrm{P_1} \sim \mathrm{P_5}$ 都处于等待态；或者其中部分进程已运行结束，其余进程处于等待态）时，对优先级为2的进程 $\mathrm{P_6},\mathrm{P_7},\mathrm{P_8}$ 采用时间片轮转调度算法运行，一旦 $\mathrm{P_1} \sim \mathrm{P_5}$ 中有一个转为就绪态，当前时间片用完后立即回到相应的优先级进行时间片轮转调度。
### 03.【解答】
抢占式优先级调度算法，三个作业执行的顺序如下图所示。
作业 $\mathrm{P_1}$ 的优先级最高，周转时间等于运行时间， $T_{1} = 80\mathrm{ms}$ ；作业 $\mathrm{P_2}$ 的等待时间为 $10\mathrm{ms}$ ，运行时间为 $80\mathrm{ms}$ ，周转时间 $T_{2} = (10 + 80)\mathrm{ms} = 90\mathrm{ms}$ ；作业 $\mathrm{P_3}$ 的等待时间为 $40\mathrm{ms}$ ，运行时间为 $50\mathrm{ms}$ ，因此周转时间 $T_{3} = 90\mathrm{ms}$ 。
三个作业从进入系统到全部运行结束，时间为 $90\mathrm{ms}$ 。CPU与外设都是独占设备，运行时间分别为各作业的使用时间之和。CPU运行时间为 $[(10 + 10) + 20 + 30]\mathrm{ms} = 70\mathrm{ms}$ ， $\mathrm{D}_1$ 为 $(30 + 20 + 20)\mathrm{ms} = 70\mathrm{ms}$ ， $\mathrm{D}_2$ 为 $(30 + 40)\mathrm{ms} = 70\mathrm{ms}$ ，因此利用率均为 $70 / 90 = 77.8\%$ 。
### 04.【解答】
作业A、B、C的优先级依次递减，采用不可抢占的优先级调度。
在时刻40，作业C释放CPU，优先级较高的作业A获得CPU；在时刻60，作业A释放CPU，优先级较高的作业B获得CPU；在时刻100，作业B释放CPU，优先级高的作业A获得CPU；在时刻110，作业A释放CPU，作业C获得CPU；在时刻130，作业C释放CPU，作业B获得CPU；在时刻160，作业B释放CPU，作业A获得CPU。运行图如下所示。
<!-- page: 105 -->
1）最早结束的是作业B。
2）最后结束的是作业A。
3）三个作业从开始到全部执行结束，经历时间为 210ms，因为是单CPU系统，CPU运行时间为各个作业的CPU运行时间之和，即 $[(20 + 10 + 20) + (40 + 30) + (40 + 20)]\mathrm{ms} = 180\mathrm{ms}$ 因此CPU的利用率为 $180 / 210 = 85.7\%$ 。
# 05.【解答】
1）作业执行情况可以用如下的甘特图来表示。
FCFS:
[tbl-19.md](tbl-19.md)
RR:
[tbl-20.md](tbl-20.md)
SJF:
[tbl-21.md](tbl-21.md)
优先级：
[tbl-22.md](tbl-22.md)
2）各个作业对应于各个算法的周转时间和加权周转时间见下表。
[tbl-23.md](tbl-23.md)
所以，FCFS的平均周转时间为13.4，平均加权周转时间为7.26。
RR的平均周转时间为9.2，平均加权周转时间为2.84。
SJF的平均周转时间为7，平均加权周转时间为1.74。
非剥夺式优先级调度算法的平均周转时间为12，平均加权周转时间为6.36。
# 注意
SJF的平均周转时间肯定是最短的，计算完毕后可以利用这个性质进行检验。
# 06.【解答】
1）具有两道作业的批处理系统，内存只存放两道作业，它们采用抢占式优先级调度算法竞争
<!-- page: 106 -->
CPU，而将作业调入内存采用的是短作业优先调度。8:00，作业1到来，此时内存和CPU空闲，作业1进入内存并占用CPU；8:20，作业2到来，内存仍有一个位置空闲，因此将作业2调入内存，又由于作业2的优先数高，相应的进程抢占CPU，在此期间8:30作业3到来，但内存此时已无空闲，因此等待。直至8:50，作业2执行完毕，此时作业3、4竞争空出的一道内存空间，作业4的运行时间短，因此先调入，但它的优先数低于作业1，因此作业1先执行。到9:10时，作业1执行完毕，再将作业3调入内存，且由于作业3的优先数高而占用CPU。所有作业进入内存的时间及结束的时间见下表。
[tbl-24.md](tbl-24.md)
2）平均周转时间为 $(70 + 30 + 90 + 90) / 4 = 70\mathrm{min}$ 。
## 07. 【解答】
1）按照可抢先式短进程优先调度算法，进程运行时间见下表。
[tbl-25.md](tbl-25.md)
- 时刻0，进程 $\mathrm{P}_1$ 到达并占用处理器运行。
- 时刻1，进程 $\mathrm{P}_2$ 到达，因其预计运行时间短，因此抢夺处理器进入运行，$\mathrm{P}_1$ 等待。
- 时刻2，进程 $\mathrm{P}_3$ 到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。
- 时刻3，进程 $\mathrm{P}_4$ 到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。
- 时刻5，进程 $\mathrm{P}_2$ 运行结束，调度器在就绪队列中选择短进程，$\mathrm{P}_4$ 符合要求，进入运行，进程 $\mathrm{P}_1$ 和进程 $\mathrm{P}_3$ 则还在就绪队列等待。
- 时刻10，进程 $\mathrm{P}_4$ 运行结束，调度器在就绪队列中选择短进程，$\mathrm{P}_1$ 符合要求，再次进入运行，而进程 $\mathrm{P}_3$ 则还在就绪队列等待。
- 时刻17，进程 $\mathrm{P}_1$ 运行结束，只剩下进程P3，调度其运行。
- 时刻26，进程 $\mathrm{P}_3$ 运行结束。
平均周转时间 $= \left[(17 - 0) + (5 - 1) + (26 - 2) + (10 - 3)\right] / 4 = 13$ 。
2）时间片轮转算法按就绪队列的FCFS进行轮转，在时刻2，$\mathrm{P}_1$ 被挂到就绪队列队尾，队列顺序为 $\mathrm{P}_2, \mathrm{P}_3, \mathrm{P}_1$ ，此时 $\mathrm{P}_4$ 还未到达。按时间片轮转算法的进程时间分配见下表。
[tbl-26.md](tbl-26.md)
平均周转时间 $= ((22 - 0) + (12 - 1) + (26 - 2) + (23 - 3)) / 4 = 19.25$ 。
## 08. 【解答】
在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列。进程调度程序总是选择队列中的第一个进程运行，且仅能运行一个时间片。在使用完一个时间片后，即使进程并未完成其运行，也必须将处理器交给下一个进程。时间片轮转调度算法是绝对可抢先
<!-- page: 107 -->
的算法，由时钟中断来产生。
时间片的长短对计算机系统的影响很大。若时间片大到让一个进程足以完成其全部工作，则这种算法就退化为先来先服务算法。若时间片很小，则处理器在进程之间的转换工作会过于频繁，处理器真正用于运行用户程序的时间将减少，系统开销将增大。时间片的大小应能使分时用户得到好的响应时间，同时也使系统具有较高的效率。
由题目给定条件可知：
1）每秒产生120个时钟中断，每次中断的时间为 $1 / 120 \approx 8.3\mathrm{ms}$ ，其中中断处理耗时为 $500\mu \mathrm{s}$ ，那么其开销为 $500\mu \mathrm{s} / 8.3\mathrm{ms} = 6\%$ 。
2）每次进程切换需要1次调度、1次切换，所以需要耗时 $1\mathrm{ms} + 2\mathrm{ms} = 3\mathrm{ms}$ ，每24个时钟为一个时间片， $24 \times 8.3\mathrm{ms} = 200\mathrm{ms}$ 。一次切换所占CPU的时间比 $3\mathrm{ms} / 200\mathrm{ms} = 1.5\%$ 。
3）为提高CPU的效率，一般情况下要尽量减少时钟中断的次数，如由每秒120次降低到100次，以延长中断的时间间隔。或将每个时间片的中断数量（时钟数）加大，如由24个中断加大到36个。也可优化中断处理程序，减少中断处理开销，如将每次 $500\mu \mathrm{s}$ 的时间降低到 $400\mu \mathrm{s}$ 。若能这样，则时钟中断和进程切换的总开销占CPU的时间比为 $(36\times 400\mu \mathrm{s} + 1\mathrm{ms} + 2\mathrm{ms}) / (1 / 100\times 36)\approx 4.8\%$ 。
## 09.【解答】
作业的响应比可表示为
$$
\text {响 应 比} = \frac {\text {等 待 时间} + \text { 要求 服 务 时间}}{\text { 要求 服 务 时间}}
$$
在时刻8:00，系统中只有一个作业 $\mathrm{J}_1$ ，因此系统将它投入运行。在 $\mathrm{J}_1$ 完成（10:00）时， $\mathrm{J}_2$ ， $\mathrm{J}_3$ ， $\mathrm{J}_4$ 的响应比分别为 $(90 + 40) / 40, (60 + 25) / 25, (30 + 30) / 30$ ，即3.25,3.4,2，因此应先将 $\mathrm{J}_3$ 投入运行。在 $\mathrm{J}_3$ 完成（10:25）时， $\mathrm{J}_2$ ， $\mathrm{J}_4$ 的响应比分别为 $(115 + 40) / 40, (55 + 30) / 30$ ，即3.875,2.83，因此应先将 $\mathrm{J}_2$ 投入运行，待它运行完毕时（11:05），再将 $\mathrm{J}_4$ 投入运行， $\mathrm{J}_4$ 的结束时间为11:35。
可见作业的执行次序为 $\mathrm{J}_1, \mathrm{J}_3, \mathrm{J}_2, \mathrm{J}_4$ ，各作业的运行情况见下表，它们的周转时间分别为120min, 155min, 85min, 125min，平均周转时间为121.25min。
[tbl-27.md](tbl-27.md)
## 10.【解答】
上述5个作业的运行情况如下图所示。
<!-- page: 108 -->
本题涉及作业和进程两方面的调度，一个作业首先需要被调入内存，创建相应的进程，然后竞争 CPU，获得 CPU 的资源来执行。本题的条件是有两道作业的批处理系统，所以内存中同时最多只有两个进程存在，且同时最多只有一个进程能够获得 CPU 资源。
在 10:00，因为只有 J₁ 到达，因此将它调入内存，并将 CPU 调度给它。
在 10:10，J₂ 到达，因此将 J₂ 调入内存，但 J₁ 只需再执行 25min，因此 J₁ 继续执行。
虽然 J₃, J₄, J₅ 分别在 10:15, 10:20 和 10:30 到达，但因为时内存中已存放了两道作业，因此不能马上将它们调入内存。
在 10:35，J₁ 结束。此时 J₃, J₄, J₅ 的响应比 [根据题意，响应比 = (等待时间 + 估计运行时间)/ 估计运行时间] 分别为 65/45, 35/20, 35/30，因此将 J₄ 调入内存，并将 CPU 分配给内存中运行时间最短者，即 J₄。
在 10:55，J₄ 结束。此时 J₃, J₅ 的响应比分别为 85/45, 55/30，因此将 J₃ 调入内存，并将 CPU 分配给估计运行时间较短的 J₂。
在 11:25，J₂ 结束，作业调度程序将 J₅ 调入内存，并将 CPU 分配给估计运行时间较短的 J₅。
在 11:55，J₃ 结束，将 CPU 分配给 J₃。
在 12:40，J₃ 结束。
通过上述分析，可知：
1）作业 1 的执行时间片段为 10:00—10:35（结束）。
作业 2 的执行时间片段为 10:55—11:25（结束）。
作业 3 的执行时间片段为 11:55—12:40（结束）。
作业 4 的执行时间片段为 10:35—10:55（结束）。
作业 5 的执行时间片段为 11:25—11:55（结束）。
2）它们的周转时间分别为 35min, 75min, 145min, 35min, 85min，因此它们的平均周转时间为 75min。
## 11. 【解答】
1）因为采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，所以会出现饥饿现象。
2）一种动态优先数计算方法为 priority = nice + k₁ × cpuTime - k₂ × waitTime，其中 k₁ > 0，k₂ > 0，分别用来调整 cpuTime 和 waitTime 在 priority 中所占的比例。若一个进程的运行时间较长，则其 cpuTime 就增加，进而降低其优先级；若一个进程的等待时间较长，则其 waitTime 增加，进而会提高其优先级。于是，waitTime 就可使长时间等待的进程优先数减少，进而避免出现饥饿现象。
## 2.3 同步与互斥
在学习本节时，请读者思考以下问题：
1）为什么要引入进程同步的概念？
2）不同的进程之间会存在什么关系？
3）当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗？
用 PV 操作解决进程之间的同步互斥问题是这一节的重点，统考中频繁考查这一内容，请读者务必多加练习，掌握好求解该类问题的方法。
<!-- page: 109 -->
## 2.3.1 同步与互斥的基本概念
在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。下面举一个简单的例子来帮大家理解这个概念。例如，让系统计算 $1 + 2 \times 3$，假设系统产生两个进程：一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后，但实际上操作系统具有异步性，若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生，而这种机制就是本节要讨论的内容。
## 1. 临界资源
**创建阅读** ➔ 给定代码的同步互斥分析（2016、2021、2023）
虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。
**创建阅读** ➔ 临界区和临界资源的分析（2024）
对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可将临界资源的访问过程分成4个部分：
1）进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
2）临界区。进程中访问临界资源的那段代码，也称临界段。
3）退出区。将正在访问临界区的标志清除。
4）剩余区。代码中的其余部分。
```c
while(true){
entry section; //进入区
critical section; //临界区
exit section; //退出区
remainder section; //剩余区
}
```