死锁定义为一组相互竞争系统资源或进行通信的进程间的永久阻塞。

当一组进程中的每个进程都在等待某个事件，而仅有这组进程中被阻塞的其他进程才可触发该事件时，就称这组进程发生了死锁。

因为没有事件能够被触发，因此死锁是永久性的。

通过联合进程图，描述了两个进程竞争两个资源的进展情况：

1. Q获得B，然后获得A；再后释放B和A；当P恢复执行时，可以获得全部资源。
2. Q获得B，然后获得A；P执行并阻塞在对A的请求上；Q释放B和A；当P恢复执行时，它可以获得全部资源。
3. Q获得B；然后P获得A；由于在继续执行时，Q阻塞在A上而P阻塞在B上，因而死锁不可避免。
4. P获得A；然后Q获得B；由于在继续执行时，Q阻塞在A上而P阻塞在B上，因而死锁不可避免。
5. P获得A，然后获得B；Q执行并阻塞在对B的请求上；P释放A和B；当Q恢复执行时，它可以获得全部资源。
6. P获得A，然后获得B；再后释放A和B；当Q恢复执行时，它可以获得全部资源。

死锁的条件

死锁有三个必要条件

1. 互斥： 一次只有一个进程可以使用一个资源。
2. 占有且等待： 当一个进程等待其他进程时，继续占有已分配的资源。
3. 不可抢占： 不能强行抢占进程已占有的资源。

这三个只是死锁存在的必要条件，而不是充分条件。要产生死锁，还需要第四个条件：

4. 循环等待： 存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

假设前三个条件存在，只要不发生不可解的循环等待，死锁还是不会发生。因此这四个条件一起构成了死锁的充分必有条件。

预防死锁

死锁预防，是试图设计一种系统来排除发生死锁的可能性。

1. 间接死锁预防：防止三个必要条件中的任何一个条件的发生；
2. 直接思索预防：防止循环等待的发生。

互斥不可能被禁止

如果需要对资源进行互斥访问，那么操作系统必须支持互斥。

预防占有且等待

为了预防占有且等待条件，可以要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足。这种方法有两个方面的低效性：

1. 一个进程可能被阻塞很长时间；

   如果进程只需要一部分资源就可以继续执行，但却被阻塞很长时间以等待满足其所有的资源请求。

   其次，分配给一个进程的资源可能会在很长一段时间不会被进程使用，且不能被其他进程使用。

2. 一个进程可能事先并不知道所需要的所有资源。

例：Java利用等待-通知机制预防占有且等待

预防不可抢占

• 被拒则放弃已占。

  占有某些资源的一个进程进一步申请资源被拒绝时，则必须释放其最初占有的资源，必要时，可再次申请这些资源和其他资源。

• 抢占其他进程的资源。

  一个进程请求资源，该资源被另一个进程占用时，操作系统可以抢占另一个进程，要求他释放资源。（只有任意两个进程的优先级都不同的条件下，该方案才能预防死锁）

只有在资源状态可以很容易被保存和恢复的情况下，才是实用的。

预防循环等待

循环等待条件可通过定义资源类型的线性顺序来预防。若一个进程已分配了R型的资源，
则其接下来请求的资源只能是那些排在R类型之后的资源。

循环等待的预防方法可能是低效的，会使进程执行速度变慢，且可能在没有必要的情况下拒绝资源访问。

避免死锁

死锁避免（Deadlock Avoidance）允许三个必要条件存在，但通过明智的选择，确保不会达到死锁点。
与死锁预防相比，进程执行的效率更高，可允许更多的并发。

设在一个有 $n$ 个进程和 $m$ 种不同类型资源的系统中：

• 系统中各种资源（Resource）的集合：

$R = \{R_1, R_2, ..., R_n\}$

• 未分配给进程的各种资源的集合：

$V = \{V_1, V_2, ..., V_n\}$

• Claim矩阵，其中 $C_{ij}$ 表示进程 $i$ 对资源 $j$ 的需求：

$C = \begin{bmatrix} C_{11} & C_{12} & ... & C_{1m} \\\\ C_{21} & C_{22} & ... & C_{2m} \\\\ ... & ... & \ddots & ... \\\\ C_{n1} & C_{n2} & ... & C_{nm} \end{bmatrix}$

• Allocation矩阵，其中 $A_{ij}$ 表示当前分配给进程 $i$ 的资源 $j$ ：

$A = \begin{bmatrix} A_{11} & A_{12} & ... & A_{1m} \\\\ A_{21} & A_{22} & ... & A_{2m} \\\\ ... & ... & \ddots & ... \\\\ A_{n1} & A_{n2} & ... & A_{nm} \end{bmatrix}$

Claim 矩阵给出了每个进程对每种资源的最大需求，为了避免死锁，该矩阵信息必须有进程事先声明。

从中可以看出以下关系：

1. $R_j = V_j + \displaystyle\sum_{i=1}^N A_{ij}$ 。

   所有资源要么可用，要么已被分配。

2. $C_{ij} \leqslant R_{ij}$ 。

   任何一个进程对任何一种资源的请求都不能超过系统中这种资源的总量。

3. $A_{ij} \leqslant C_{ij}$ 。

   分配给任何一个进程的任何一种资源都不会超过这个进程最初声明的此资源的最大请求量。

进程请求会导致死锁则拒绝启动

仅当

$R_j \geqslant C_{(n+1)j} + \displaystyle\sum_{i=1}^n C_{ij}$

才启动一个新进程 $P_{n+1}$ 。即，满足所有当前进程的最大请求量及新的进程请求时，才会启动该进程。

这种策略不是最优的，因为它假设了最坏的情况：所有进程同时发出它们的最大请求。

新增的资源请求会导致死锁则拒绝分配

此策略又称 银行家算法 。

检测死锁