28. 【解答】
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 28. 【解答】
1）代码 C₁ 执行对 B 的写操作，且 P₁ 和 P₂ 需要互斥执行 C₁，因此 C₁ 的代码是临界区。
2）有一组互斥关系和一组同步关系。互斥关系为：P₁ 和 P₂ 需要互斥访问缓冲区 B；同步关系为：P₁ 执行 C₁ 后，P₂ 才能执行 C₂。缓冲区 B 初始为空，且最大容量为 1，因此可不用定义互斥信号量 mutex。因为在缓冲区大小为 1 的条件下，同步信号量 S 就可同时保证 P₁ 和 P₂ 互斥访问 B，符合题意“尽可能定义少的信号量”的要求。进程 P₁ 和 P₂ 的同步伪代码如下。
[tbl-39.md](tbl-39.md)
3）缓冲区 B 初始非空，因此仅需一个互斥信号量 mutex 来保证 P₁ 和 P₂ 互斥访问 B 即可。进程 P₁ 和 P₂ 的互斥伪代码如下。
[tbl-40.md](tbl-40.md)
## 2.4 死锁
在学习本节时，请读者思考以下问题：
1）为什么会产生死锁？产生死锁有什么条件？
2）有什么办法可以解决死锁问题？
学完本节，读者应了解死锁的由来、产生条件及基本解决方法，区分避免死锁和预防死锁。
### 2.4.1 死锁的概念
#### 1. 死锁的定义
在多道程序系统中，由于进程的并发执行，极大提升了系统效率。然而，多个进程的并发执行也带来了新的问题——死锁。所谓死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待对方手里的资源），使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。
下面通过一些实例来说明死锁现象。
先看生活中的一个实例。在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。若有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述冲突情况：此时，左边的汽车占有桥面左边
<!-- page: 161 -->
的一段，右边的汽车占有桥面右边的一段，要想过桥则需等待左边或右边的汽车向后行驶以退出桥面。但若左右两边的汽车都只想向前行驶，则两辆汽车都无法过桥。
在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程 $\mathrm{P_1}$ 正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程 $\mathrm{P_2}$ 所占用，而 $\mathrm{P_2}$ 在未释放打印机之前，又提出请求使用正被 $\mathrm{P_1}$ 占用的输入设备。这样，两个进程相互无休止地等待下去，均无法继续向前推进，此时两个进程陷入死锁状态。
## 2. 死锁与饥饿
一组进程处于死锁状态是指组内的每个进程都在等待一个事件，而该事件只可能由组内的另一个进程产生。与死锁相关的另一个问题是饥饿，即进程在信号量内无穷等待的情况。
产生饥饿的主要原因是：当系统中有多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序，有的分配策略可能是不公平的，即不能保证等待时间上界的存在。在这种情况下，即使系统未发生死锁，某些进程也可能长时间等待。当等待时间给进程的推进带来明显影响时，称发生了饥饿。例如，当有多个进程需要打印文件时，若系统分配打印机的策略是最短文件优先，则长文件的打印任务将因短文件的源源不断到来而被无限期推迟，最终导致饥饿，甚至“饿死”。饥饿并不表示系统一定会死锁，但至少有一个进程的执行被无限期推迟。
死锁和饥饿的共同点都是进程无法顺利向前推进的现象。
死锁和饥饿的主要差别：①发生饥饿的进程可以只有一个；而死锁是因循环等待对方手里的资源而导致的，因此，若有死锁现象，则发生死锁的进程必然大于或等于两个。②发生饥饿的进程可能处于就绪态（长期得不到CPU，如SJF算法的问题），也可能处于阻塞态（如长期得不到所需的I/O设备，如上述举例）；而发生死锁的进程必定处于阻塞态。
## 3. 死锁产生的原因
**创建速度** 单类资源竞争时发生死锁的临界条件的分析（2009、2014）
### （1）系统资源的竞争
通常系统中拥有的不可剥夺资源（如磁带机、打印机等），其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源（如CPU和主存）的竞争是不会引起死锁的。
### （2）进程推进顺序非法
请求和释放资源的顺序不当，也同样会导致死锁。例如，进程 $\mathrm{P_1}, \mathrm{P_2}$ 分别保持了资源 $\mathrm{R_1}, \mathrm{R_2}$，而 $\mathrm{P_1}$ 申请资源 $\mathrm{R_2}$、$\mathrm{P_2}$ 申请资源 $\mathrm{R_1}$ 时，两者都会因为所需资源被占用而阻塞，于是导致死锁。
信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，也会使得这些进程无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。
## 4. 死锁产生的必要条件
产生死锁必须同时满足以下4个条件，只要其中任一条件不成立，死锁就不会发生。
1）互斥条件。进程要求对所分配的资源（如打印机）进行排他性使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2）不可剥夺条件。进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）。
3）请求并保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
<!-- page: 162 -->
4）循环等待条件。存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合 $\{P_1, P_2, \dots, P_n\}$，其中 $P_i$ 等待的资源被 $P_{i+1}$（$i = 0, 1, \dots, n-1$）占有，$P_n$ 等待的资源被 $P_0$ 占有，如图2.13所示。
直观上看，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求 $P_i$ 等待的资源必须由 $P_{i+1}$ 来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备，$P_0$ 和 $P_K$ 各占有一台，且 $K$ 不属于集合 $\{0, 1, \dots, n\}$。$P_n$ 等待一台输出设备，它可从 $P_0$ 或 $P_K$ 获得。因此，虽然 $P_n, P_0$ 和其他一些进程形成了等待环，但 $P_K$ 不在圈内，若 $P_K$ 释放了输出设备，则可打破循环等待，如图2.14所示。因此循环等待只是死锁的必要条件。
图2.13 循环等待
图2.14 满足条件但无死锁
资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。
要注意区分不可剥夺条件与请求并保持条件。下面用一个简单的例子进行说明：若你手上拿着一个苹果（即便你不打算吃），别人不能将你手上的苹果拿走，则这就是不可剥夺条件；若你左手拿着一个苹果，允许你右手再去拿一个苹果，则这就是请求并保持条件。
## 5. 死锁的处理策略
为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。
1）死锁预防。设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个。
2）避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态。
3）死锁的检测及解除。无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。
预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。
死锁的几种处理策略的比较见表2.5。
表 2.5 死锁处理策略的比较
[tbl-41.md](tbl-41.md)
<!-- page: 163 -->
## 2.4.2 死锁预防
**前景追踪** ▶ 死锁预防的特点（2019）
预防死锁的发生只需破坏死锁产生的4个必要条件之一即可。
### 1. 破坏互斥条件
若将只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且为了系统安全，很多时候还必须保护这种互斥性。
### 2. 破坏不可剥夺条件
当一个已经保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，进程已占有的资源会被暂时释放，或者说是被剥夺了，从而破坏了不可剥夺条件。
该策略实现起来比较复杂。释放已获得的资源可能造成前一阶段工作的失效，因此这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。反复地申请和释放资源既影响进程推进速度，又增加系统开销，进而降低了系统吞吐量。
### 3. 破坏请求并保持条件
要求进程在请求资源时不能持有不可剥夺资源，可以通过两种方法实现：
1）采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源。在它的资源未满足前，不让它投入运行。在进程的运行期间，不会再提出资源请求，从而破坏了“请求”条件。在等待期间，进程不占有任何资源，从而破坏了“保持”条件。
2）允许进程只获得运行初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源。
方法一的实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或快结束时才使用，而且会导致“饥饿”现象，由于个别资源长期被其他进程占用，将导致等待该资源的进程迟迟不能开始运行。方法二则改进了这些缺点。
### 4. 破坏循环等待条件
为了破坏循环等待条件，可以采用顺序资源分配法。首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完。也就是说，一个进程只在已经占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能再逆向申请小编号的资源，因此不会产生循环等待的现象。
这种方法的缺点：编号必须相对稳定，因此不便于增加新类型设备；尽管在编号时已考虑到大多数进程使用这些资源的顺序，但是进程实际使用资源的顺序还是可能和编号的次序不一致，这就会造成资源的浪费；此外，必须按规定次序申请资源，也会给用户编程带来麻烦。
## 2.4.3 死锁避免
避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在每次分配资源的过程中，都要分析此次分配是否会带来死锁风险，只有在不产生死锁的情况下，系统才会为其分配资源。这种方法所施加的限制条件较弱，可以获得较好的系统性能。
### 1. 系统安全状态
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次
<!-- page: 164 -->
分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。
所谓安全状态，是指系统能按某种进程推进顺序（$\mathrm{P}_1, \mathrm{P}_2, \dots, \mathrm{P}_n$）为每个进程 $\mathrm{P}_i$ 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。此时称 $\mathrm{P}_1, \mathrm{P}_2, \dots, \mathrm{P}_n$ 为安全序列（可能有多个）。若系统无法找到一个安全序列，则称系统处于不安全状态。
## 衛區通訊 ▶ 系统安全状态的分析（2018）
假设系统有三个进程 $\mathrm{P}_1, \mathrm{P}_2$ 和 $\mathrm{P}_3$，共有 12 台磁带机。$\mathrm{P}_1$ 需要 10 台，$\mathrm{P}_2$ 和 $\mathrm{P}_3$ 分别需要 4 台和 9 台。假设在 $T_0$ 时刻，$\mathrm{P}_1, \mathrm{P}_2$ 和 $\mathrm{P}_3$ 已分别获得 5 台、2 台和 2 台，尚有 3 台未分配，见表 2.6。
表 2.6 资源分配
[tbl-42.md](tbl-42.md)
在 $T_0$ 时刻是安全的，因为存在一个安全序列 $\mathrm{P}_2, \mathrm{P}_1, \mathrm{P}_3$，只要系统按此进程序列分配资源，那么每个进程都能顺利完成。也就是说，当前可用资源数为 3，先将 2 台分配给 $\mathrm{P}_2$ 以满足其最大需求，$\mathrm{P}_2$ 结束并归还资源后，系统有 5 台可用；接下来给 $\mathrm{P}_1$ 分配 5 台以满足其最大需求，$\mathrm{P}_1$ 结束并归还资源后，剩余 10 台可用；最后分配 7 台给 $\mathrm{P}_3$，这样 $\mathrm{P}_3$ 也能顺利完成。
若在 $T_0$ 时刻后，系统分配 1 台给 $\mathrm{P}_3$，剩余可用资源数为 2，此时系统进入不安全状态，因为此时已无法再找到一个安全序列。当系统进入不安全状态后，便可能导致死锁。例如，将剩下的 2 台分配给 $\mathrm{P}_2$，这样，$\mathrm{P}_2$ 完成后只能释放 4 台，既不能满足 $\mathrm{P}_1$ 又不能满足 $\mathrm{P}_3$，致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，即导致死锁。
若系统处于安全状态，则一定不会发生死锁；若系统进入不安全状态，则有可能发生死锁（处于不安全状态未必就会发生死锁，但发生死锁时一定是处于不安全状态）。
## 2. 银行家算法
## 衛區通訊 ▶ 银行家算法的特点（2013、2019）
银行家算法是最著名的死锁避免算法，其思想是：将操作系统视为银行家，操作系统管理的资源视为银行家管理的资金，进程请求资源相当于用户向银行家贷款。进程运行之前先声明对各种资源的最大需求量，其数量不应超过系统的资源总量。当进程在运行中申请资源时，系统必须先确定是否有足够的资源分配给该进程。若有，再进一步试探在将这些资源分配给进程后，是否会使系统处于不安全状态。若不会，则将资源分配给它，否则让进程等待。
### （1）数据结构描述
假设系统中有 $n$ 个进程，$m$ 类资源，在银行家算法中需要定义下面 4 个数据结构。
1）可利用资源向量 Available: 含有 $m$ 个元素的数组，其中每个元素代表一类可用的资源数量。Available $[j] = K$ 表示此时系统中有 $K$ 个 $\mathbf{R}_j$ 类资源可用。
2）最大需求矩阵 Max: $n \times m$ 矩阵，定义系统中 $n$ 个进程中的每个进程对 $m$ 类资源的最大需求。Max $[i, j] = K$ 表示进程 $\mathbf{P}_i$ 需要 $\mathbf{R}_j$ 类资源的最大数量为 $K$。
3）分配矩阵 Allocation: $n \times m$ 矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation $[i, j] = K$ 表示进程 $\mathbf{P}_i$ 当前已分得 $\mathbf{R}_j$ 类资源的数量为 $K$。
4）需求矩阵 Need: $n \times m$ 矩阵，表示每个进程接下来最多还需要多少资源。Need $[i, j] = K$ 表示进程 $\mathbf{P}_i$ 还需要 $\mathbf{R}_j$ 类资源的数量为 $K$。
上述三个矩阵间存在下述关系：
<!-- page: 165 -->
Need = Max - Allocation
通常，Max 矩阵和 Allocation 矩阵是题中的已知条件，而求出 Need 矩阵是解题的第一步。
（2）银行家算法描述
设 Request_i 是进程 P_i 的请求向量，Request_i[j] = K 表示进程 P_i 需要 j 类资源 K 个。当 P_i 发出资源请求后，系统按下述步骤进行检查：
① 若 Request_i[j] ≤ Need[i, j]，则转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
② 若 Request_i[j] ≤ Available[j]，则转向步骤③；否则，表示尚无足够资源，P_i 必须等待。
③ 系统试探着将资源分配给进程 P_i，并修改下面数据结构中的数值：
Available = Available - Request_i;
Allocation[i, j] = Allocation[i, j] + Request_i[j];
Need[i, j] = Need[i, j] - Request_i[j];
④ 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 P_i，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P_i 等待。
（3）安全性算法
设置工作向量 Work，表示系统中的剩余可用资源数量，它有 m 个元素，在执行安全性算法前，令 Work = Available。
① 初始时安全序列为空。
② 从 Need 矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于或等于 Work 向量，找到后，将对应的进程加入安全序列；若找不到，则执行步骤④。
③ 进程 P_i 进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，所以应执行 Work = Work + Allocation[i]，其中 Allocation[i] 是 Allocation 矩阵中对应的行，返回步骤②。
④ 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。
看完上面对银行家算法的过程描述后，可能有眼花缭乱的感觉，现在通过举例来加深理解。
3. 安全性算法举例
前期演练 ▶ 银行家算法的安全序列分析（2011、2012、2018、2020、2022）
假定系统中有 5 个进程 {P₀, P₁, P₂, P₃, P₄} 和三类资源 {A, B, C}，各种资源的数量分别为 10, 5, 7，在 T₀ 时刻的资源分配情况见表 2.7。
T₀ 时刻的安全性。利用安全性算法对 T₀ 时刻的资源分配进行分析。
表 2.7 T₀ 时刻的资源分配表
[tbl-43.md](tbl-43.md)
<!-- page: 166 -->
① 从题目中我们可以提取 Max 矩阵和 Allocation 矩阵，这两个矩阵相减可得到 Need 矩阵：
$$
\begin{array}{l}
\left[ \begin{array}{ccc}
7 & 5 & 3 \\
3 & 2 & 2 \\
9 & 0 & 2 \\
2 & 2 & 2 \\
4 & 3 & 3 \\
\end{array} \right] - \left[ \begin{array}{ccc}
0 & 1 & 0 \\
2 & 0 & 0 \\
3 & 0 & 2 \\
2 & 1 & 1 \\
0 & 0 & 2 \\
\end{array} \right] = \left[ \begin{array}{ccc}
7 & 4 & 3 \\
1 & 2 & 2 \\
6 & 0 & 0 \\
0 & 1 & 1 \\
4 & 3 & 1 \\
\end{array} \right] \\
\text{Max} \quad \text{Allocation} \quad \text{Need}
\end{array}
$$
② 然后，将 Work 向量与 Need 矩阵的各行进行比较，找出比 Work 矩阵小的行。例如，在初始时，
$$
(3, 3, 2) > (1, 2, 2)
$$
$$
(3, 3, 2) > (0, 1, 1)
$$
对应的两个进程分别为 $\mathbf{P}_1$ 和 $\mathbf{P}_3$，这里我们选择 $\mathbf{P}_1$（也可选择 $\mathbf{P}_3$）暂时加入安全序列。
③ 释放 $\mathbf{P}_1$ 所占的资源，即将 $\mathbf{P}_1$ 进程对应的 Allocation 矩阵中的一行与 Work 向量相加：
$$
(3 \quad 3 \quad 2) + (2 \quad 0 \quad 0) = (5 \quad 3 \quad 2) = \text{Work}
$$
此时需求矩阵更新为（去掉了 $\mathbf{P}_1$ 对应的一行）：
$$
\begin{array}{l}
P_0 \left[ \begin{array}{ccc}
7 & 4 & 3 \\
6 & 0 & 0 \\
0 & 1 & 1 \\
4 & 3 & 1 \\
\end{array} \right] \\
P_1
\end{array}
$$
再用更新的 Work 向量和 Need 矩阵重复步骤②。利用安全性算法分析 $T_0$ 时刻的资源分配情况如表 2.8 所示，最后得到一个安全序列 $\{\mathrm{P}_1, \mathrm{P}_3, \mathrm{P}_4, \mathrm{P}_2, \mathrm{P}_0\}$。
表 2.8 $T_0$ 时刻的安全序列的分析
[tbl-44.md](tbl-44.md)