2.4死锁¶

2.4.1 资源分类¶

可重用资源和可消耗性资源

比较项	可重用资源	消耗型资源
定义	使用后可以重复利用的资源，对该类资源的请求和释放通常是利用系统调用来实现的	一次性使用后就不可重复使用的资源，是在进程运行期间，由进程动态地创建和消耗的，通常是由生产者进程创建，由消费者进程消耗
典型例子	+ 硬件：处理器、I / O通道、主和副存储器、设备等 + 软件：文件、数据库和信号量等数据结构	在I/O缓冲区的中断、信号、消息等
分配与释放模式	在使用完成后会释放，供其他进程继续使用	使用后不再存在，需要重新生成或获取
其他性质	1. 资源不能被删除且在任何时刻只能有一个进程使用； 2. 这些资源在被释放后可再次使用。通常需要进行互斥或同步机制来防止资源竞争。	1. 每一类可消耗资源的单元数目在进程运行期间是可以不断变化的，可以是0或者很多； 2. 进程在运行过程中可以不断地创造可消耗性资源，并将其放入该类资源的缓冲区，以增加其数目；也可以请求若干个该类资源用于消耗并不再返回；
死锁可能性	存在被多个进程同时请求而导致死锁的可能，eg：每个进程占用一部分资源并请求其它资源	不容易导致死锁，但是仍有可能，例如进程间相互等待接收对方的消息
管理方式	采用资源分配表、互斥锁等方法管理	需要有生产者-消费者机制或信号机制
使用场景	多用户系统、共享系统资源	网络通信、作业处理等

可抢占性资源和不可抢占性资源

比较项	可抢占资源	不可抢占资源
定义	可以在被分配后中断并分配给其他进程, 例如优先级调度中的抢占处理机、在内存紧张时将一个进程从内存调到外存上抢占其内存空间	一旦分配后不可中断，只能由持有进程释放
典型例子	CPU、内存、网络带宽	打印机、文件、锁、数据库事务等临界资源
分配方式	可以中断当前持有者并重新分配	一旦分配，需等待当前持有者主动释放
死锁可能性	由于可以中断,一般来说不会死锁	资源不能被中断，容易导致死锁
管理方式	需要某种调度策略（如抢占式调度）	需要资源等待和释放策略
使用场景	多任务调度、动态资源分配	事务处理、设备使用、批量作业

2.4.2 常见并发缺陷(了解即可)¶

非死锁缺陷：
违反原子性缺陷：违反了多次内存访问中预期的可串行性(即代码段本意是原子的，但是在执行过程中并没有强制实现原子性)。例如在多线程中两个线程对同一个变量检查并修改，但是运行过程中由于线程切换发生类似引用空指针的错误导致程序崩溃。解决方案：给共享资源的访问加锁；
违反顺序缺陷：两个进程内存访问的预期顺序被打破了(即A应该在B之前执行，然而实际运行并不是这个顺序)；修复方案：通过条件变量或者信号量加入同步。
死锁(deadlock)缺陷

2.4.3 死锁的概念¶

死锁、饥饿、死循环的区别

	死锁	饥饿	死循环
定义	在并发环境下，各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。	由于长期得不到想要的资源，某进程无法向前推进的现象；比如短进程优先算法中如果有源源不断的短进程到来，那么长进程就会一直得不到处理机；	进程在没有满足终止条件时会无限循环
发生原因	循环等待对方手里的资源	优先级倒置、资源分配不公平或错误	编程错误、逻辑错误或资源竞争
例子	死锁状态下的银行家算法问题	低优先级进程无法获得CPU时间片、内存等	空循环、忘记更新循环条件等
进程状态	阻塞态	阻塞态(得不到I/O设备)或就绪态(上不了处理机)	运行态
解决方法	预防、检测和解决死锁	资源分配公平、优先级正确、控制资源使用	修改程序逻辑、添加终止条件或优化算法
处于该种状态的进程数量	两个或两个以上	可能只有一个，也可能大于1个	大于等于1个

三者都是进程无法顺利向前推进的现象(故意设计的死循环除外)，死锁和饥饿是管理者(OS)的问题，死循环是被管理者的问题。

死锁产生的原因
对系统资源的竞争：当各进程竞争不可抢占性资源时，若该类资源数目满足不了多个进程的需要，使得进程在运行过程中因争夺资源而陷入僵局，从而导致死锁。
进程推进顺序不当：进程运行过程中，请求和释放资源的顺序不当同样会导致死锁。例如并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又在申请资源R1，二者会因为申请的资源被对方占有而阻塞，从而发生死锁。
信号量的使用不当：如生产者消费者问题中，如果实现互斥的P操作在实现同步的P操作之前就有可能导致死锁；
由可消耗性资源引起的死锁：如果多个进程之间通信时，对消息的receive和send操作的顺序没有处理好，都在先等待receive消息再send消息，导致这几个进程永远阻塞在receive操作上，因为在等待一条永远不会发出的消息，于是产生死锁。

总之对不可剥夺资源的不合理分配，可能导致死锁。

死锁产生的必要条件：产生死锁必须同时满足以下四个条件，只要任意一个条件不满足，死锁就不会发生。
互斥条件：任何时刻只能有一个进程使用一个资源实例

只有对必须互斥使用的资源的争夺才会导致死锁，如临界资源、锁等。像内存、CPU、扬声器这种可以同时让多个进程使用的资源是不会导致死锁的，因为进程不用阻塞等待这种资源。

不可剥夺(抢占)条件：进程所获得的资源在未使用完成之前，不能由其他进程强行夺走，只能主动释放。

请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

循环并等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁。如果同类资源数大于1，即使有循环等待，等待链中的一个进程可能从等待链以外的进程那里获得自己的资源，从而打破死锁。但是如果系统中每类资源都只有一个，那么循环等待就是死锁的充要条件了。

由以上四个必要条件，可得以下常用结论：

若系统有 x 个进程，每个进程需要 y 个资源，则该系统必然不会发生死锁的最少资源是 \(x\*(y-1) + 1\)个。
若系统有 x 个资源，每个进程需要 y 个资源，则该系统可能发生死锁的最小进程数为 \(\left\lceil \dfrac{x}{y-1} \right\rceil\)。

【推导思路】系统有 x 个进程，每个进程已拥有 y-1 个资源，此时如果资源总数刚好为 x*(y-1) 个，意味着资源已用完，则一定发生死锁，此时再多加一个资源，令其中一个进程获得所需的最大资源，则死锁解除。即使每个进程所需资源数各不相同，一样可以按此思路分析。

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

A. 2

B. 3

C. 4

D. 5

解析

答案：C

已知：每个进程最多需要 3 台打印机，共有 K 个进程。
最坏情况：每个进程都只分到了 3-1 = 2 台打印机，并且都在请求第 3 台。此时系统被占用的打印机总数为 2K。
安全条件：要想不发生死锁，系统此时必须至少还能掏出 1 台打印机来打破僵局。即系统总资源数。
计算：解得，即。这意味着当进程数 K 为 1, 2, 3 时，系统绝不会死锁。
题目设问：“可能会发生死锁的 K 的最小值是”。既然是绝对安全的，那么一旦越过这个界限，K=4 就是第一个可能发生死锁的情况（4个进程各拿2台，8台全耗尽，全都在等）。

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

A. 9

B. 10

C. 11

D. 12

解析

答案：B

已知：三个进程分别需要 3、4、5 台设备。
最坏情况：三个进程分别拿到了 2、3、4 台设备。此时占用的设备总数为 2 + 3 + 4 = 9 台。
安全条件：只要系统还能额外提供 1 台设备，就能让其中一个进程顺利执行完毕并释放资源。
计算：因此，确保不发生死锁的最小设备数 n = 9 + 1 = 10 台。

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

A. 2

B. n

C. n+1

D. 2n

解析

答案：C

已知：n 个进程，每个进程需 2 个资源。
最坏情况：n 个进程每个都拿到了 2-1 = 1 个资源。此时占用总资源数为。
安全条件：需要再加 1 个资源打破僵局。
计算：不发生死锁至少需要的资源总数为 n + 1。

死锁的处理策略：

2.4.4 死锁预防¶

破坏互斥条件：若允许系统资源都能共享使用，则系统不会进入死锁状态。
比如：SPOOLing技术，操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备，比如用该技术把打印机改造为共享设备…
Herlihy提出了设计各种无等待(wait-free)数据结构的思想，即通过强大的硬件指令，可以将需要互斥访问某种资源的那段代码构造成不需要锁的数据结构，这样便破坏了互斥条件(详情见OSTEP 第32章)

缺点：有的资源本身就是非共享的，例如一个互斥锁不能同时被多个进程所共享，这种资源不可以被改造成可共享资源。并且有些地方还得保护这种互斥性，因此这种方法通常不太可行。

破坏不剥夺条件：方案一：当请求新的资源得不到满足时，立即释放保持的所有资源；方案二：当某个进程需要的资源被其他进程所占有时，可以由OS协助将想要的资源强行剥夺。\ 缺点：
实现起来很复杂，且需付出很大代价；
释放已获得的资源可能造成进程前一阶段工作的失效，即便采取了某些防范措施，也还会使进程前后两次运行的信息不连续。因此这种方法通常适用于状态容易保存和恢复的资源，如CPU寄存器和内存。一般不适用于其他资源，如互斥锁、信号量、打印机、CD刻录机这一类资源。
反复地申请和释放资源会大大增加系统开销，降低系统吞吐量。
可能会导致进程饥饿。
破坏请求并保持条件：为了能破坏“请求并保持条件”，系统必须做到：当一个进程在请求资源时，它不能持有不可抢占资源。可通过以下两个不同的协议实现：
协议1：采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足以前，不让它投入运行。可通过”要求进程申请资源的系统调用在所有其他系统调用之前进行“
协议2：是对协议1的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的的、且已用完的全部资源，然后再请求新的所需资源。第二种协议不但能使进程更快地完成任务，提高设备的利用率，还可以减少进程发生饥饿的机率。

缺点：这个方案需要我们准确地知道需要哪些资源，并且提前抢到这些资源。有些资源可能仅在运行初期或运行快结束时才使用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会降低并发，造成严重的资源浪费，资源利用率极低；另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件：最实用也是最经常采用的预防技术。可以采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源R_i，则该进程在以后的资源申请中就只能申请编号大于R_i的资源。

缺点：

不方便增加新的设备，可能需要重新分配所有的编号；
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
必须按规定次序申请资源，用户编程麻烦。

聪明的程序员根据锁的地址做为获取锁的顺序，按照地址从高到低，或者从低到高的顺序加锁，do_something()函数就可以保证不论传入参数是什么顺序，函数都会用固定的顺序加锁。因此在获取多个锁时，通过简单的技巧，就可以确保简单有效的无死锁实现。——OSTEP

2.4.5 死锁避免¶

预防与检测解除方案的折中：不事先破坏死锁必要条件，而是在资源动态分配中防止系统进入不安全状态；

安全序列：指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
如果分配了资源以后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利地执行下去。当然如果有进程提前归还了部分资源，那系统也有可能重新回到安全状态，不过在分配资源以前总是要考虑最坏的情况。
如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁。(处于不安全状态不一定发生死锁，但发生死锁时一定是在不安全状态)，一定要形成了阻塞环才是死锁，单个进程阻塞不是死锁。
因此可以在资源分配以前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是”银行家算法“的核心思想。

银行家算法：

银行家算法步骤：

检查此次申请是否超过了之前声明的最大需求数；
检查此时系统剩余的可用资源是否还能满足这次请求；
试探着分配，更改各数据结构；
用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。

【2011-27】某时刻进程的资源使用情况如下表所示。

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

此时的安全序列是（）。

A. P1, P2, P3, P4

C. P1, P4, P3, P2

B. P1, P3, P2, P4

D. 不存在

解析

本题选 D

们需要模拟银行家算法的安全性检测过程。当前系统可用资源为 (0, 2, 1)。

第 1 步： 寻找 尚需资源 (Need) <= 可用资源 (Available) 的进程。

P1 的需求是 (0, 0, 1) <= (0, 2, 1)，满足条件。P1 可以执行。
P1 执行完毕后，释放其已分配的资源 (2, 0, 0)。
此时新的可用资源 = 之前的可用资源 + P1 释放的资源 = (0, 2, 1) + (2, 0, 0) = (2, 2, 1)。

第 2 步： 使用新的可用资源 (2, 2, 1) 检查剩余进程。

P2 的需求是 (1, 3, 2)。其中 R2 需要 3，但目前只有 2，不满足。
P3 的需求是 (1, 3, 1)。其中 R2 需要 3，但目前只有 2，不满足。
P4 的需求是 (2, 0, 0) <= (2, 2, 1)，满足条件。P4 可以执行。
P4 执行完毕后，释放资源 (0, 0, 1)。
新的可用资源 = (2, 2, 1) + (0, 0, 1) = (2, 2, 2)。

第 3 步： 使用 (2, 2, 2) 再次检查剩余的 P2 和 P3。

P2 的需求 (1, 3, 2)，R2 依然不够（需要 3，只有 2）。
P3 的需求 (1, 3, 1)，R2 依然不够（需要 3，只有 2）。

结论： 无论是 P2 还是 P3 都无法获得足够的 R2 来继续执行，系统无法使所有进程顺利执行完毕，即不存在安全序列。

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

进程	已分配资源			资源最大需求
	R1	R2	R3	R1
P0	3	2	3	5
P1	4	0	3	5
P2	4	0	5	4
P3	2	0	4	4
P4	3	1	4	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

首先计算当前可用资源 (Available) 和各个进程的尚需资源 (Need)。

已分配资源总和 = (16, 3, 19)。
可用资源 = 资源总数 - 已分配总和 = (18, 6, 22) - (16, 3, 19) = (2, 3, 3)。
各进程 Need = 资源最大需求 - 已分配资源：

P0 Need = (5, 5, 10) - (3, 2, 3) = (2, 3, 7)
P1 Need = (5, 3, 6) - (4, 0, 3) = (1, 3, 3)
P2 Need = (4, 0, 11) - (4, 0, 5) = (0, 0, 6)
P3 Need = (4, 2, 5) - (2, 0, 4) = (2, 2, 1)
P4 Need = (4, 2, 4) - (3, 1, 4) = (1, 1, 0) 根据选项直接验证 D 选项的序列：P3 -> P4 -> P2 -> P1 -> P0

P3： Need (2, 2, 1) <= (2, 3, 3) (Avail)，执行并释放分配的 (2, 0, 4)。新 Avail = (2, 3, 3) + (2, 0, 4) = (4, 3, 7)。
P4： Need (1, 1, 0) <= (4, 3, 7) (Avail)，执行并释放分配的 (3, 1, 4)。新 Avail = (4, 3, 7) + (3, 1, 4) = (7, 4, 11)。
P2： Need (0, 0, 6) <= (7, 4, 11) (Avail)，执行并释放分配的 (4, 0, 5)。新 Avail = (7, 4, 11) + (4, 0, 5) = (11, 4, 16)。
P1： Need (1, 3, 3) <= (11, 4, 16) (Avail)，执行并释放分配的 (4, 0, 3)。新 Avail = (11, 4, 16) + (4, 0, 3) = (15, 4, 19)。
P0： Need (2, 3, 7) <= (15, 4, 19) (Avail)，完全满足。该序列可以顺利走通，因此存在此安全序列。

【2013-32】下列关于银行家算法的叙述中，正确的是（）。

A. 银行家算法可以预防死锁

B. 当系统处于安全状态时，系统中一定无死锁进程

C. 当系统处于不安全状态时，系统中一定会出现死锁进程

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

解析

答案：B

A 错误： 银行家算法属于死锁避免（Deadlock Avoidance）算法，而不是死锁预防（Deadlock Prevention）。死锁预防是指通过破坏死锁的四个必要条件来彻底根除死锁；而死锁避免是在资源动态分配过程中防止系统进入不安全状态。
B 正确： 安全状态是指系统能按某种进程推进顺序分配资源，使每个进程都能顺利完成。只要处于安全状态，就一定存在安全序列，也就一定不会发生死锁。
C 错误： 不安全状态仅仅是指系统找不到一个安全序列，它有可能导致死锁，但不一定必然发生死锁（因为进程的实际资源请求不一定会同时达到最大值）。
D 错误： 银行家算法没有破坏任何死锁必要条件（破坏请求和保持条件属于死锁预防策略）。

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

A. 不存在安全序列，系统处于不安全状态

B. 存在多个安全序列，系统处于安全状态

C. 存在唯一安全序列 P3、P1、P2，系统处于安全状态

D. 存在唯一安全序列 P3、P2、P1，系统处于安全状态

解析

答案：A

系统总资源：4
已分配资源：P1(2) + P2(1) + P3(0) = 3。
可用资源：4 - 3 = 1。
计算各进程的尚需资源：

P1 Need = 4 - 2 = 2
P2 Need = 3 - 1 = 2
P3 Need = 1 - 0 = 1

模拟分配：当前只有 1 个可用资源，只能满足 P3（Need=1）。P3 获得资源执行完毕后，释放其已分配的资源（P3 已分配资源是 0）。所以 P3 结束后，可用资源依然是 1 + 0 = 1。此时，P1 和 P2 尚需资源都是 2，而可用资源只有 1，两者都无法继续执行。系统发生死锁。
因此，不存在安全序列，系统处于不安全状态。

【2019-30】下列关于死锁的叙述中，正确的是（）。

Ⅰ. 可以通过剥夺进程资源解除死锁

Ⅱ. 死锁的预防方法能确保系统不发生死锁

Ⅲ. 银行家算法可以判断系统是否处于死锁状态

Ⅳ. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

A. 仅Ⅱ、Ⅲ

B. 仅Ⅰ、Ⅱ、Ⅳ

C. 仅Ⅰ、Ⅱ、Ⅲ

D. 仅Ⅰ、Ⅲ、Ⅳ

解析

答案：B

Ⅰ 正确： 解除死锁的常用方法包括：剥夺资源、撤销进程（或终止进程）、进程回退等。
Ⅱ 正确： 死锁的预防方法（如破坏互斥、请求与保持、不剥夺、循环等待这四个必要条件）从机制上彻底杜绝了死锁产生的条件，所以能确保系统不发生死锁（代价通常是资源利用率低）。
Ⅲ 错误： 银行家算法是死锁避免算法。判断系统是否已经处于死锁状态应该使用死锁检测算法（如资源分配图化简法、死锁定理）。
Ⅳ 正确： 死锁的定义就是多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用这些进程都将永远不能再向前推进。既然是互相等待，必然至少有两个或两个以上的进程处于阻塞态。

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

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

A. 存在安全序列P1、P2、P3

B. 存在安全序列P2、P1、P3

C. 存在安全序列P2、P3、P1

D. 不存在安全序列

解析

答案：B

计算可用资源 (Available)： A 类资源已分配：2+2+1=5，剩余 = 6-5=1。 B 类资源已分配：3+1+2=6，剩余 = 6-6=0。初始可用资源 = (1, 0)。
计算尚需资源 (Need = 需求总量 - 已分配数量)：

P1 Need = (4-2, 4-3) = (2, 1)
P2 Need = (3-2, 1-1) = (1, 0)
P3 Need = (3-1, 4-2) = (2, 2)

寻找安全序列：

当前仅 P2 的 Need (1, 0) <= 可用资源 (1, 0)，所以 P2 必须第一个执行。P2 执行后释放 (2, 1)，新可用资源 = (1, 0) + (2, 1) = (3, 1)。
接下来检查 P1 和 P3：P1 Need (2, 1) <= (3, 1) 满足；P3 Need (2, 2) 的 B 资源不满足。因此 P1 必须第二个执行。P1 释放 (2, 3)，新可用资源 = (3, 1) + (2, 3) = (5, 4)。
最后执行 P3，Need (2, 2) <= (5, 4)，满足。序列为 P2, P1, P3。

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

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

A. 1

B. 2

C. 3

D. 4

解析

答案：B

当前可用资源为 (1, 3, 2)。检查各进程的尚需资源：

P0: (0, 2, 1) <= (1, 3, 2) （满足）
P1: (1, 2, 3) > (1, 3, 2) （C资源不满足）
P2: (0, 1, 3) > (1, 3, 2) （C资源不满足）

可以看出，第一步只能运行 P0。 P0 运行完毕后，回收它已分配的资源 (2, 0, 1)。新的可用资源 = (1, 3, 2) + (2, 0, 1) = (3, 3, 3)。

此时再检查剩余的 P1 和 P2：

P1 的需求是 (1, 2, 3) <= (3, 3, 3) （满足）
P2 的需求是 (0, 1, 3) <= (3, 3, 3) （满足）

因为 P1 和 P2 现在都可以满足条件，所以先运行谁都可以（运行完任何一个释放资源后，另一个自然也能满足）。因此产生了两个安全序列分支：

P0 -> P1 -> P2
P0 -> P2 -> P1 共有 2 个安全序列。

2.4.6 死锁检测和解除¶

死锁检测算法会根据系统真实情况设置合适的时间间隔，每隔一段时间执行来检测系统是否存在死锁，否则可能会浪费系统资源而没有有效进程的推进。

若系统既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁，在这种情况下，系统应该提供两个算法：

死锁检测算法：用于检测系统状态，以确定系统中是否已经发生了死锁；
死锁解除算法：从死锁状态中恢复的算法；

2.4.6.1死锁的检测¶

为了能对系统是否已发生了死锁进行检测，必须：

用某种数据结构来保存资源的请求和分配信息；
提供一种算法，利用上述信息来检测系统是否已进入死锁状态；
该数据结构就是资源分配图，其构成有：

名称	解释
进程结点	对应一个进程
资源结点	对应一类资源，一些资源可能有多个
进程结点→资源节点的边	表示进程想申请几个资源(每条边代表一个)
资源结点→进程节点	表示已经为进程分配了几个资源(每条边代表一个)

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程...

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）。

如果最终不能消除所有边，那么此时就是发生了死锁。最终还连着边的那些进程就是处于死锁状态的进程。

使用死锁检测算法简化资源分配图：
(1): 在资源分配图中，找出既不阻塞又不是孤点的进程 P1（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如上图中，R1 没有空闲资源，R2有一个空闲资源。)若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源。
(2): 消去它所有的请求边和分配变，使之成为孤立的结点。(在上图中，P1 是满足这一条件的进程结点，于是将P1 的所有边消去。)
(3): 进程 P1所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在上图中，P2就满足这样的条件。根据上述方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的。
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。注意，并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。

【2016-25】系统中有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

一道经典的很多人问的真题：

【2015-26】若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中，正确的是（）。

Ⅰ. S1会限制用户申请资源的顺序，而S2不会

Ⅱ. S1需要进程运行所需资源总量信息，而S2不需要

Ⅲ. S1不会给可能导致死锁的进程分配资源，而S2会

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

Answer

解答：

Ⅰ错误。限制用户申请资源的顺序属于死锁预防方法。死锁预防是指在设计系统时，通过确定资源分配算法，排除发生死锁的可能性。具体做法是破坏产生死锁的四个必要条件之一。这里主要指的是破坏“循环等待”条件：①静态资源分配法：把系统中所有的资源编号，进程在申请资源时必须严格按资源编号的递增次序进行。

综上，I前半句错误，后半句正确。

II正确。S1 采用死锁避免方法，需要获取进程运行所需资源的总量信息，以便进行安全性检查和资源分配的决策，这是为了避免将资源分配给可能导致死锁的进程，经典算法如银行家算法。而 S2 采用死锁检测方法，不需要知道进程运行所需资源的总量信息，它只需要跟踪系统中的资源分配情况和进程之间的资源请求关系（也就是说只需要知道当前申请的资源数量即可），以判断是否存在死锁。

为什么死锁检测不需要知道进程运行所需资源总量信息，因为死锁检测只是在某个时间点按照各进程所需资源和分配到的资源画资源分配图看能不能化简，以此检查系统中有没有发生死锁，他并不保证当前系统中不会发生死锁，再决定如何解除死锁，因此它并不需要知道。

Ⅲ正确。S1 采用死锁避免方法，会避免给可能导致死锁的进程分配资源，以确保系统的安全性。而 S2 采用死锁检测方法，不会阻止资源的分配。它会周期性地检测系统中是否存在死锁，并采取适当的措施来解决已经发生的死锁情况。

s2的死锁检测只考虑当前进程是否会死锁，只关注当下的时间点，而s1中的死锁避免中的银行家算法需要考虑整体的一个情况，包括未来会不会发生死锁，也就是是否会进入不安全状态。

综上，仅Ⅱ、Ⅲ正确。

本题选B。

补充：死锁的检测和恢复算法执行的时间点为（）

A.死锁发生时

B.进程向操作系统申请资源分配时

C.每隔一段时间或当 CPU 利用率显著降低时

D.操作系统发生终止类错误时

解析

【答案】C

死锁检测和恢复操作系统处理死锁的一种策略。这种策略允许死锁发生，但操作系统会不断监视系统进展情况，判断死锁是否真的发生。一旦死锁发生，则采取专门的措施解除死锁。

我们来逐项分析为什么选 C，而不选其他选项：

A. 死锁发生时（逻辑错误）这是一个逻辑悖论。操作系统只有运行了检测算法之后，才能知道“死锁发生了”。在运行算法之前，系统是不知道当前状态是否处于死锁的，因此无法以“死锁发生”作为触发点。
B. 进程向操作系统申请资源分配时（开销过大）如果在每次进程申请资源时都运行一次死锁检测算法，系统的开销将非常巨大。

死锁检测通常涉及对资源分配图的遍历及环路检测，或者使用类似于银行家算法的安全序列检测，时间复杂度较高（例如或）。
如果每一个 malloc 或资源请求都触发一次全盘检测，系统性能将严重下降。
注意：死锁避免（如银行家算法）确实是在每次请求时判断安全性，但那是为了“避免”，而本题问的是“检测”。

C. 每隔一段时间或当 CPU 利用率显著降低时执行（正确，折中方案）为了在“及时发现死锁”和“降低系统开销”之间取得平衡，通常采用的方法是：

定时检测：每隔一段时间（例如每隔 5 分钟，或每隔 1 小时）运行一次检测算法。
CPU 利用率低时检测：当 CPU 利用率降到某个阈值（例如 40%）以下时，说明系统中可能有很多进程因为死锁而阻塞，此时触发检测。这种方式既不会过多占用 CPU 资源，也能在一定时间内发现死锁。

D. 操作系统发生终止类错误时（不准确）
死锁的表现通常是进程互相等待、系统停滞、吞吐量下降，而不是直接导致操作系统崩溃或报出终止错误。发生错误时往往已经无法挽回或属于其他类型的故障。

2.4.6.2死锁的解除¶

一旦检测出死锁的发生，就应该立即解除死锁。

解除死锁的主要方法有：

资源剥夺法: 挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿.
撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

如果采用了撤销部分进程或资源剥夺法的方法，可以根据\ 进程优先级、已执行多长时间、还要多久能完成、进程已经使用了多少资源、进程是交互式的还是批处理式等来决定确定哪个(或哪些）死锁进程应该终止或被剥夺资源。

在解除死锁的过程中如何确保不会发生饥饿？即如何保证资源不会总是从同一个进程中被抢占。

如果一个系统是基于代价来选择牺牲进程，那么同一进程可能总是被选为牺牲的。结果这个进程永远不会完成指定任务，从而饿死。因此我们可以在代价的考虑因素中加上回滚次数。

思考题：假设系统中有下述 3 种解决死锁的方法：

（1）银行家算法；

（2）检测死锁，终止处于死锁状态的进程，释放该进程所占有的资源；

（3）资源预分配。

简述上述哪种方法允许最大的并发性？请按“并发性”从大到小对上述 3 种方法进行排序。

答案

①题中给出的3种方法中，检测死锁能允许更多的进程无须等待地向前推进，并发性最大。因为该方法允许进程最大限度地申请并分配资源，直至出现死锁，再由系统解决死锁。

②银行家算法允许进程自由申请资源，只是在某个进程申请资源时会检查系统是否处于安全状态，若是，则可立即分配；若不是，则拒绝。其并发性的大小次于检测死锁这一方法。

③最后是资源预分配，因为此方法要求进程在运行之前申请所需的全部资源，这会使许多进程因申请不到全部资源而无法开始，得到部分资源的进程也会因未得到全部资源而不释放已占用的资源，所以此方法会导致资源浪费。

因此，上述3种方法按并发性从大到小排序为：检测死锁、银行家算法、资源预分配。