第 3 章 进程调度与死锁¶
依据：《操作系统概论（2017年版）》第三章、书前自学考试大纲、附录习题答案。大纲能力层次以“考核内容与考核要求”为准。调度和银行家算法中的数值均按题目给定条件推演；算法名称缩写沿用教材。
复习导航¶
| 大纲条目 | 层次 | 笔记位置与目标 |
|---|---|---|
| 1.1 进程调度功能；1.2 调度时机 | 识记 | 第 1 节：能定义、列出调度入口时机 |
| 2.1 选择准则 | 识记 | 第 2 节：能说明各种指标的侧重点 |
| 2.2 周转、平均周转、平均带权周转 | 简单应用 | 第 3 节：会算单作业和平均值 |
| 2.3 六种算法及抢占时机 | 领会 | 第 4 节：说明规则、适用情形及局限 |
| 2.4 实时条件、EDF、LLF | 领会 | 第 5 节：说明条件并跟踪截止时间／松弛度 |
| 2.5 多处理机类型、分配与调度 | 识记 | 第 6 节：区分分类与三种调度方式 |
| 3.1—3.3 死锁定义、原因、必要条件 | 领会 | 第 7 节：用资源等待关系分析四个条件 |
| 4.1 死锁预防 | 识记 | 第 8 节：说明破坏哪个必要条件 |
| 4.2 安全／不安全状态 | 识记 | 第 9 节：会判断安全序列，区分不安全和死锁 |
| 4.2 银行家算法 | 简单应用 | 第 10 节：会算 Need、试分配和安全性 |
| 4.3 检测、解除，死锁定理 | 识记 | 第 11 节：会化简资源图并说出解除方式 |
大纲将平均时间计算和银行家算法列为应用题；调度算法要求理解规则与实现思路，多处理机调度要求识记。
1 调度功能与时机（1.1、1.2）¶
进程调度由内核中的调度程序完成：从就绪态进程中选择一个，把 CPU 分配给它。进程调度分配的是 CPU 使用权。作业调度则从外存后备队列中选择作业装入内存。两者作用于不同阶段。
教材列出的重新调度时机有五类：当前进程正常或异常结束；进程阻塞；中断返回；抢占式系统中出现新的高优先级进程；当前时间片用完。
2 调度准则（2.1）¶
| 准则 | 含义／关注点 |
|---|---|
| 周转时间短 | 从提交到完成经过的总时间；用户等待体验 |
| 响应时间快 | 从请求提交到首次得到响应；交互系统关注 |
| 保证截止时间 | 最迟开始或完成的时限；实时系统关注 |
| 吞吐量高 | 单位时间完成的作业数 |
| CPU 利用率好 | 尽量减少处理机空闲 |
这些指标反映了不同的系统目标。缩短短作业的等待，可能使长作业等得更久；较小的时间片有利于交互响应，却增加切换开销。调度算法因此要结合批处理、分时或实时等服务要求来选择。
3 周转时间与计算（2.2，简单应用）¶
对作业 i：
周转时间 Ti = 完成时刻 - 提交时刻
平均周转时间 T = ΣTi / n
带权周转时间 Wi = Ti / 服务时间 Tsi
平均带权周转时间 W = Σ(Ti / Tsi) / n
服务时间是作业在 CPU 上执行的总时间。周转时间包含后备队列等待、就绪队列等待、CPU 执行和 I/O 等待，因此 Ti >= Tsi。若有时间片切换，执行时间要累计。遇到不同的时间单位或时刻格式，先统一换算再计算。
自编核算例¶
单 CPU，非抢占 FCFS，P1、P2 分别在 0、1 到达，服务时间为 3、2。P1 运行区间 [0,3]，P2 为 [3,5]。
| 进程 | 到达 | 开始 | 完成 | 服务 | 周转 | 带权周转 |
|---|---|---|---|---|---|---|
| P1 | 0 | 0 | 3 | 3 | 3 | 1 |
| P2 | 1 | 3 | 5 | 2 | 4 | 2 |
平均周转时间为 (3+4)/2=3.5，平均带权周转时间为 (1+2)/2=1.5。P2 等待时间是 3−1=2，周转时间则是 5−1=4。
4 进程调度算法（2.3，领会）¶
调度准则确定评价目标，调度算法规定每次从就绪集合中选哪个进程。规则不同，执行顺序就不同，等待、响应和周转时间也随之改变。
| 算法 | 选择规则 | 优点与局限 |
|---|---|---|
| FCFS 先来先服务 | 选最先进入就绪队列者，通常非抢占 | 简单；长进程在前会使短进程等待很久；偏有利于 CPU 繁忙进程 |
| SPF 短进程优先 | 在就绪进程中选估计服务时间最短者，教材描述为运行到完成或阻塞再调度 | 可降低平均等待／周转；长进程可能饥饿；运行时间依赖估计，不保证紧迫任务优先 |
| 优先权 | 选优先级最高的就绪进程 | 可按任务重要性调度；定义须看系统是数值大优先还是数值小优先 |
| RR 时间片轮转 | 就绪队列按 FIFO；运行一个时间片，未完成则放队尾 | 适合分时交互；片太短切换开销大，太长响应变慢；片足够大时近似 FCFS |
| 多级队列 | 按属性固定分入不同就绪队列，各队列可有自己的优先级和算法 | 开销较低；分类固定、灵活性差，低优先级队列可饥饿 |
| 多级反馈队列 | 进程可按反馈规则在不同优先级队列间移动；教材典型规则为高优先级队列时间片较短 | 兼顾短作业响应与长作业进展；规则较复杂，具体实现因系统而异 |
抢占、非抢占与优先级¶
- 非抢占式：进程获得 CPU 后一直运行，直到完成或阻塞／主动放弃；新来的高优先级进程先等待。
- 抢占式：符合抢占条件时剥夺当前进程 CPU。教材列出立即抢占，或等待最近一次时钟中断再抢占。
- 静态优先级：创建时确定，运行中不变。动态优先级：随执行进展或等待时间等因素改变。
- 饥饿：就绪进程长期得不到 CPU。老化（等待越久逐步提高优先级）是教材列出的缓解方法。
RR 推演时，每次从队首取进程，运行 min(时间片, 剩余服务时间)；未完成则放回队尾。推演过程要记录各进程的到达、完成和空闲区间。新进程的入队时机按题目条件处理。
SPF 每次只比较已经到达且可运行的进程。教材所述 SPF 是非抢占算法，不等同于短剩余时间优先。
5 实时系统调度（2.4，领会）¶
实现实时调度需要四项条件：必要的调度信息（就绪时间、开始／完成截止时间、处理时间、资源要求、优先级）；足够的系统处理能力；适当的抢占机制；快速的中断响应和进程切换。
周期任务的处理能力条件：
单处理机：Σ(Ci / Pi) <= 1
n 个处理机：Σ(Ci / Pi) <= n
其中 Ci 为任务处理时间，Pi 为周期时间。
| 算法 | 优先依据 | 执行规则 |
|---|---|---|
| EDF 最早截止时间优先 | 截止时间最早者优先 | 就绪队列按截止时间排序；可用于抢占或非抢占 |
| LLF 最低松弛度优先 | 松弛度最小者优先 | L = 截止时间 T − 当前时刻 Tc − 剩余处理时间 Ts；选 L 最小者 |
LLF 的松弛度由当前时刻和剩余处理时间共同决定，需要在调度过程中不断更新。松弛度相同时按题设规则选择。EDF 直接比较截止时间，与按到达时间排序的 FCFS 不同。
6 多处理机调度（2.5，识记）¶
| 分类角度 | 类型 | 含义 |
|---|---|---|
| 耦合程度 | 紧密耦合 | 多处理机共享主存和 I/O，由统一 OS 管理 |
| 耦合程度 | 松弛耦合 | 多台计算机各有本地存储与 I/O，可独立工作并通信 |
| 处理器控制关系 | 对称多处理（SMP） | 处理器地位对等，调度和工作分配较分布 |
| 处理器控制关系 | 非对称多处理 | 主处理器控制系统，其他处理器执行分配任务 |
多处理机调度方式：
- 自调度：处理器从共享就绪队列自行选取工作。实现较简单、负载可动态分配；共享队列竞争、调度不匹配等会带来开销，合作线程也不一定同时获得处理器。
- 成组调度：把同一应用的一组相关线程同时调度到多个处理器，减少相互等待和调度频率；需要协调分配多个 CPU。
- 专用处理器分配：应用执行期间为其线程专门分配处理器，减少切换、可加速执行；线程阻塞时对应处理器可能空闲，资源利用率低。
7 死锁定义、原因与四个必要条件（3.1—3.3，领会）¶
调度能安排可运行进程使用 CPU，却无法让等待条件尚未满足的进程继续执行。多个进程相互等待对方持有的资源时，就要分析是否已经形成死锁。
死锁：多个进程竞争共享资源，各自等待其他进程占有的资源，因而都不能继续推进，这种僵持状态就是死锁。产生的原因是竞争共享资源，且分配资源的顺序不当。
死锁发生必须同时满足四个必要条件：
| 条件 | 含义 | 典型破坏思路 |
|---|---|---|
| 互斥 | 资源一次只允许一个进程使用 | 允许共享，但许多临界资源无法取消互斥 |
| 请求和保持 | 已持有资源，同时等待新资源 | 一次申请全部资源，或申请新资源前释放已有资源 |
| 不剥夺 | 已分配资源不能强行收回 | 不能立即满足新请求时，按规则收回已有资源 |
| 环路等待 | 存在循环等待链 | 对资源类型编号，按同一顺序申请 |
四项是“必要条件”：若发生死锁，四项同时成立。排除任一项可预防死锁；但单独观察到某些资源互斥，并不能据此断言必然死锁。
例如，A、B 各只有一个实例，均不可共享且不可剥夺。P1 持有 B 并等待 A，P2 持有 A 并等待 B。两个进程都无法释放对方所需的资源，因而形成死锁。
8 死锁预防（4.1，识记）¶
死锁预防的思路是保证至少一个必要条件不成立。互斥通常是某些资源的固有属性，不适合一概取消，教材因此重点讲摒弃其余三个条件：
| 摒弃的条件 | 做法 | 代价／限制 |
|---|---|---|
| 请求和保持 | 运行前一次性申请所需资源；或申请新资源前释放已有资源 | 资源需求难以预知，资源可能闲置，并发性下降 |
| 不剥夺 | 新申请无法满足时，按策略释放／抢占已持资源 | 实现复杂；某些资源不适合抢占，可能要回滚 |
| 环路等待 | 资源类型排序，进程按递增次序申请 | 限制申请顺序、降低灵活性，可能浪费资源 |
上述预防方法通过限制资源申请或占有方式，排除死锁的必要条件。死锁避免是另一种思路：允许进程动态申请资源，但分配之前先检查结果是否安全。银行家算法属于这一类。
9 安全状态与不安全状态（4.2，识记）¶
若能找到一个进程序列，使每个进程轮到自己时都能被满足，系统就处于安全状态。满足它的是当前可用资源，加上前面进程完成后释放的资源；该序列称安全序列。找不到这样的序列，就是不安全状态。
不安全不等于已经死锁。不安全说明不能保证存在安全完成次序，系统可能进一步进入死锁。处于安全状态则可以避免进入死锁。
单一资源类型下有直观判法。逐个寻找 Need <= Available 的进程，假设它完成并归还已占资源 Allocation，更新可用量，再继续检查。
10 银行家算法（4.2，简单应用）¶
银行家算法把安全状态的判断用于每一次资源申请。它先试算请求获准后的状态，再检查是否仍存在让全部进程完成的安全序列。
设有 n 个进程、m 类资源：
| 数据 | 含义 |
|---|---|
| Available[j] | 当前 j 类资源可用数量 |
| Max[i,j] | 进程 i 对 j 类资源的最大需求 |
| Allocation[i,j] | 已分给进程 i 的 j 类资源 |
| Need[i,j] | 进程 i 尚需资源，Need = Max − Allocation |
| Requesti | 进程 i 本次提出的请求向量 |
向量不等式逐项比较。X <= Y 表示每一种资源都不超过对应分量，不是把各分量求和后再比较。
10.1 安全性检查¶
Work = Available；所有Finish[i] = false。- 找一个
Finish[i] = false且Need[i] <= Work的进程。 - 假设它运行完毕：
Work = Work + Allocation[i]，置Finish[i] = true，记下进程序列。 - 重复检查。若所有进程 Finish 为 true，安全；否则若找不到可继续者，不安全。
10.2 资源请求检查¶
进程 i 请求 Requesti 时：
- 若
Requesti > Needi，超过声明的最大需求，拒绝该请求。 - 若
Requesti > Available，现有资源不足，进程等待。 - 否则做试分配：
Available -= Requesti；Allocation[i] += Requesti；Need[i] -= Requesti。 - 对试分配后的状态运行安全性检查。安全则确认分配；不安全则撤销试分配，令进程等待。
10.3 教材例题状态核对¶
教材的 A、B、C 三类资源例题中，初始 Available=(3,3,2)，安全序列为 <p1,p3,p4,p2,p0>。p1 请求 (1,0,2) 后，Available=(2,3,0)、Need1=(0,2,0)。试分配后的状态仍然安全，因此可以分配。
安全性检查的记录应包含三项：每一步的 Work，所选进程的 Need，以及该进程完成后归还的 Allocation。Work 增加的只是原来已经分配给进程的资源。当前可用量满足不了某一个进程，并不表示整个状态不安全，其他进程可能先完成并释放资源。
11 死锁检测、资源分配图与解除（4.3，识记）¶
死锁检测允许系统先分配资源，之后再定期或在特定条件下检测。检测时机要权衡死锁发生的频率、受影响的进程数和检测开销。教材的资源分配图中，圆圈表示进程，方框表示资源类型，方框内的小圆圈表示该类资源的实例。请求边由进程指向资源，分配边由资源实例指向进程。
死锁定理：系统处于死锁状态，当且仅当资源分配图不可完全简化。化简时反复找一个可化简的进程：它既不阻塞，又非孤立，剩余请求还能被满足。假设它完成并释放所占资源，再消去与它相关的边。全部进程都能消去，图就可完全简化；仍有无法消去的进程，图就不可完全简化。不可把“图上有环”无条件当成死锁，资源类型有多个实例时须按化简条件分析。
检测到死锁后的解除方式：
- 终止所有死锁进程；或逐个终止，直到死锁解除。选择牺牲进程时要权衡若干代价：优先级、已经运行的时间、还需时间、资源类型及数量、需终止多少进程、是否交互式。
- 抢占部分进程所占资源，打破等待环。此时需决定抢占对象，必要时回滚到安全状态，并避免反复抢占同一进程造成饥饿。
12 教材本章习题¶
题目取自教材第三章习题，答案依据教材附录。
12.1 单项选择题¶
1. 影响时间片大小选择的主要因素有（ ）。
答案与解析
参考答案：A。
时间片直接影响轮转系统的响应时间；实际选择还要兼顾进程数和切换开销。
2. 关于多级队列调度算法，下列说法正确的是（ ）。
答案与解析
参考答案：C。
多级队列可为各队列配置不同优先权和调度算法；进程固定属于某队列，跨队列移动是多级反馈队列的特点。
3. 某系统中有 4 个并发进程，都需要同类资源 3 个。该系统不会发生死锁的最少资源数是（ ）。
答案与解析
参考答案：D。
最坏情况是每个进程先各占 2 个，共占 8 个；再有第 9 个资源即可让一个进程取得第 3 个资源并完成、释放资源，随后其他进程依次完成。一般 n 个进程各需 k 个同类资源时，足以保证不死锁的资源数为 n(k−1)+1。
12.2 填空题¶
1. FCFS 适合进程，不利于进程。
答案与解析
长；短。
2. 采用基于静态优先权的调度算法时，若不断有高优先权进程进入就绪队列，低优先权进程可能进入___状态。
答案与解析
饥饿。
3. ___算法是用来避免死锁的算法。
答案与解析
银行家。
4. S 为死锁状态的___条件是当且仅当 S 状态的资源分配图是不可完全简化的。
答案与解析
充分。教材附录按此空格给出答案；完整死锁定理的表述见本章第 11 节。
12.3 简答题¶
1. 进程调度的功能是什么？
答案与解析
内核调度程序按策略和算法从就绪进程中选择一个，为其分配 CPU，使其进入执行状态。
2. 说明什么是时间片轮转调度算法。
答案与解析
就绪进程按先来先服务排队；队首进程运行一个时间片，完成则退出，未完成则回到队尾；时间片到期后重新调度。时间片过短会增加切换开销，过长则响应变慢。
3. 什么是多级队列调度算法？
答案与解析
按进程属性将就绪队列划分为多个独立队列，进程进入系统后固定分配到一个队列；各队列可有不同优先级和调度算法。调度开销较低，但灵活性较差，低优先级队列可能饥饿。
4. 什么是自调度方式？有什么优缺点？
答案与解析
多个处理器从共享就绪队列自行选择进程或线程。优点是实现简单、可动态分配负载；缺点是队列竞争和调度开销，合作线程也可能因未同时运行而相互等待。
5. 什么是死锁？引起死锁的原因是什么？
答案与解析
多个进程竞争共享资源，各自等待其他进程占有的资源而都不能继续推进，这种僵持状态称为死锁。其原因是竞争共享资源且资源分配顺序不当。
12.4 简单应用：银行家算法¶
题目： 考虑系统某一时刻的状态，资源列顺序为 A、B、C、D。 | 进程 | Allocation | Max | Available | |---|---|---|---| | p0 | (0,0,1,2) | (0,0,1,2) | (1,5,2,0) | | p1 | (1,0,0,0) | (1,7,5,0) | | | p2 | (1,3,5,4) | (2,3,5,6) | | | p3 | (0,6,3,2) | (0,6,5,2) | | | p4 | (0,0,1,4) | (0,6,5,6) | |
用银行家算法回答：
- Need 矩阵是什么？
- 系统是否处于安全状态？
- 若 p1 请求
(0,4,2,0)，能否立即满足？
答案与解析
（1）计算 Need。 Need = Max − Allocation，逐资源列相减：
| 进程 | Need (A,B,C,D) |
|---|---|
| p0 | (0,0,0,0) |
| p1 | (0,7,5,0) |
| p2 | (1,0,0,2) |
| p3 | (0,0,2,0) |
| p4 | (0,6,4,2) |
（2）检查初始安全性。 初始 Work = Available = (1,5,2,0)。按 Need[i] <= Work 逐项比较，并在假设进程完成后加回其 Allocation：
| 步骤 | 进程 | Need | 完成前 Work | 完成后 Work = Work + Allocation |
|---|---|---|---|---|
| 1 | p0 | (0,0,0,0) | (1,5,2,0) | (1,5,3,2) |
| 2 | p2 | (1,0,0,2) | (1,5,3,2) | (2,8,8,6) |
| 3 | p3 | (0,0,2,0) | (2,8,8,6) | (2,14,11,8) |
| 4 | p4 | (0,6,4,2) | (2,14,11,8) | (2,14,12,12) |
| 5 | p1 | (0,7,5,0) | (2,14,12,12) | (3,14,12,12) |
因此存在安全序列 <p0,p2,p3,p4,p1>，系统处于安全状态。
（3）检查 p1 的请求。 请求 (0,4,2,0) 不超过 Need1=(0,7,5,0)，也不超过 Available=(1,5,2,0)，可以试分配：
Available = (1,5,2,0) - (0,4,2,0) = (1,1,0,0)
Allocation1 = (1,0,0,0) + (0,4,2,0) = (1,4,2,0)
Need1 = (0,7,5,0) - (0,4,2,0) = (0,3,3,0)
对试分配状态进行安全性检查：
| 步骤 | 进程 | Need | 完成前 Work | 完成后 Work |
|---|---|---|---|---|
| 1 | p0 | (0,0,0,0) | (1,1,0,0) | (1,1,1,2) |
| 2 | p2 | (1,0,0,2) | (1,1,1,2) | (2,4,6,6) |
| 3 | p3 | (0,0,2,0) | (2,4,6,6) | (2,10,9,8) |
| 4 | p4 | (0,6,4,2) | (2,10,9,8) | (2,10,10,12) |
| 5 | p1 | (0,3,3,0) | (2,10,10,12) | (3,14,12,12) |
仍存在安全序列 <p0,p2,p3,p4,p1>，所以该请求可以立即满足。
13 闭卷复习与计算检查（补充）¶
| 自测题（自编） | 参考答案与辨析 |
|---|---|
| 周转时间与响应时间分别看哪个时刻？ | 周转时间从提交到完成；响应时间从提交到首次响应。 |
| SPF 在 t 时刻选择作业，能否选择尚未到达的最短作业？ | 不能，必须只从当时已到达的就绪集合选。 |
| 不安全状态是否等于已经死锁？ | 不等于；不安全说明不能保证全部进程按声明的最大需求完成。 |
| 安全性检查中，进程完成后 Work 增加什么？ | 增加它原来持有的 Allocation，不能增加 Max 或 Need。 |
| Need 恰好等于 Work 时能否满足？ | 能，使用逐分量小于等于。 |
| 资源图有环是否必然死锁？ | 每类单实例的相应模型中环可判死锁；多实例时有环不一定，需检查可化简性。 |
调度计算以到达时刻、服务时间和调度规则为依据。在每个调度时刻更新就绪集合，即可确定下一段执行区间，再从完整时间轴上读出各进程的完成时刻。随后分别计算周转时间和带权周转时间，再求平均值。时间片边界若恰有新进程到达，要明确“新到达者与时间片用完者谁先入队”，并在全题保持一致。
银行家算法先由 Need=Max−Allocation 确定剩余需求。接着检查 Request≤Need 和 Request≤Available 两个条件。两项条件都满足才做试分配：更新 Available、Allocation 和 Need，然后检查所得状态的安全性。存在安全序列时确认分配，否则撤销试分配并让申请者等待。安全性检查寻找的是可完成顺序，不能要求所有进程同时满足 Need≤Available。
自编安全性练习：单类资源，Available=1；P0 的 Allocation=1、Need=1；P1 的 Allocation=1、Need=2。先完成 P0，Work 从 1 变为 2；再完成 P1，Work 变为 3。因此状态安全。若只看 P1 不满足就立即判为不安全，就遗漏了可先完成的 P0。
分析具体死锁时，要把资源的占有和等待关系分别对应到互斥、请求和保持、不剥夺、循环等待四个条件。处理方法按介入阶段区分：预防是排除必要条件；避免是在分配时保持状态安全；检测是识别已经发生的死锁；解除则通过终止进程或抢占资源恢复运行。