死锁

1.死锁的概念

1.1死锁的定义

多个进程并发执行，由于竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法推进，这就是死锁现象。

例如：系统中只有一台打印机和一台输入设备，若进程p1正在占用输入设备，同时又提出使用打印机的请求；而进程p2正在占用打印机，同时又提出请求输入设备的请求。这样两个进程相互无休止地互相等待，均无法继续执行，此时这两个进程进入死锁状态。

1.2死锁产生的原因

①系统资源的竞争

只有对不可剥夺资源的竞争（如打印机） 才可能产生死锁，对可剥夺资源的竞争是不会产生死锁的。

②进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。如1.1的例子。

③死锁产生的必要条件： 死锁产生必须同时满足以下四个条件，任意一条不成立，便不会产生死锁：

• 互斥条件： 各个进程必须互斥的对系统分配的资源（临界资源）进行排他性使用。
• 不可剥夺条件： 进程使用完临界资源之前，不能被其他资源强行夺走，只能自行释放。
• 请求并保持条件：进程已经保持了一个临界资源，但又提出了新的申请临界资源要求，而该临界资源被其他进程占有，此时，请求进程被阻塞，但又保持对自己占有的临界资源保持不放。
• 循环等待条件: 存在一种进程资源的循环等待链条，每个进程已获得的临界资源同时被下一个资源所请求。

2.死锁的预防

预防死锁只需要破坏死锁的四个必要条件之一即可：

①破坏互斥条件

②破坏不可剥夺条件： 当进程的新资源不可取得时，释放自己已有的资源，待以后需要时重新申请。 但这种方法可能导致迁移阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。

③破坏请求并保持条件：进程在运行前一次申请完它所需要的全部资源，在它的资源为满足前，不把它投入运行。一旦投入运行，这些资源都归它所有，不能被剥夺。但这种方法系统资源被严重浪费，而且可能导致饥饿现象，由于个别进程长时间占用某个资源，导致等待该资源的进程迟迟无法运行。

④破坏循环等待条件： 给资源编号，规定每个进程必须按编号递增地顺序请求资源，同类资源一次性申请完。这种方法存在问题是发生作业使用资源地顺序与系统规定的顺序不同，造成系统地浪费，并且给编程带来麻烦。

这四种方法都有各自的缺陷，我们一般不采用。

3.死锁的避免

避免死锁同样属于事先预防地策略，但不是破坏死锁地必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

3.1系统安全状态

允许进程动态地申请资源，但系统在进行资源分配之前，先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。

安全状态：系统能按照某种进程推进顺序为每个进程分配其所需地资源，直至满足每个进程对资源地最大需求，使每个进程可顺序完成。

并非所有不安全状态都是死锁状态，但当系统进入不安全状态后便可能进入死锁状态；只要处于死锁状态，则一定处于不安全序列状态。

如：进程p1,p2,p3，共有12台磁带机。在t时刻，p1，p2，p3所需要资源和已分配资源如下表：

在t时刻是安全的，因为存在一个安全序列p2、p1、p3，按照这个顺序分配资源，每个进程都能顺利完成。

3.2银行家算法

银行家算法是著名的死锁避免算法，核心思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 规定：

• 进程运行前先声明对各种资源的最大需求量
• 若银行家资金能够达到进程声明的最大需求量便能将所有资金收回，否则一分钱受不了，产生坏账。

例:某时刻进程的资源使用情况如下表，此时的安全序列为：

安全序列不存在，此时已经处于不安全序列状态。

判断过程如下：

• 可用资源(0, 2, 1)大于p1进程所需，可以成功完成p1进程回收p1资源后，可用资源为(0, 2, 1) + (2, 0, 0) = (2, 2, 1)。
• 可用资源(2, 1, 1)大于p4进程所需，可以成功完成p4资源，回收p4资源后，可用资源为(2, 2, 1) + (0, 0, 1) = (2, 2, 2)。
• 可用资源(2, ,2 , 2)既无法完成p2进程所需，又不够p3进程所需，为不安全序列状态。

4.死锁的检测和解除

若系统在分配资源是不采取任何措施，应该提供死锁检测和避免手段。

4.1资源分配图

用圆圈代表一个进程，用框代表一类资源。从进程到资源的有向边称为请求边，表示该进程从该类资源申请一个资源；从从资源到进程的边称为分配边，表示该类资源已有一个资源分配给该进程。

如：进程p1已经分配了2个R1资源，并请求了一个R2资源；进程p2分配了一个R1，一个R2资源，并申请了一个R1资源。

4.2死锁定理

简化资源分配图可检测系统状态S是否为死锁状态。简化方法如下：

• 找出既不阻塞又不孤点的进程Pi(找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量)。
• 消除与Pi所有相邻的请求边和分配边，使之成为孤立的节点。
• 循环以上两条。

总结来说就是：依次消除与不阻塞进程相邻的边，直到无边可消除。

如果能消除所有的边，则没有产生死锁；否则产生死锁。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

例如：p1是既不阻塞又不孤点的进程，消去与它相邻的所有边。

p2既不阻塞又不孤点，消去与它相邻的所有边。

消去了所有边，不是死锁状态。

4.3死锁解除

一旦检测出死锁，就应该立即采取措施来接触死锁。死锁解除的主要方法有：

• 资源剥夺法。 挂起某些死锁进程，抢占它的资源，分配给其他死锁进程。
• 撤销进程法。 强制撤销部分进程并剥夺这些进程的资源，让其他进程顺利执行。
• 进程回退法。

1 死锁的定义

死锁是一组互相竞争系统资源或进行通信的进程间的永久阻塞。当一组进程中的每一个进程都在等待某个事件，而仅有这组进程中被阻塞的其他进程才可触发该事件时，就称这组进程发生了死锁。死锁在没有外界干预的情况下是永久性的。

2 死锁的条件

死锁有3个必要条件：

1. 互斥：一次只有一个进程可以使用一个资源，其他进程不能访问已经分配给其他进程的资源。
2. 不可剥夺：不能够抢占其他进程已有的资源。
3. 占有且等待：如果一个进程尝试获取一个资源没有成功，那么会进入等待状态，并且这个进程持有的资源不会被释放。

除此之外，要产生死锁，最关键的条件是循环等待：

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

第4个条件是前3个条件的潜在结果，之所以产生循环等待是因为有前三个条件。

解决死锁的方式有3种：

• 预防死锁
• 避免死锁
• 检测死锁并从中恢复。

3 预防死锁

死锁预防策略是试图设计一种方式来排除发生死锁的可能性，预防策略分为两类：

• 间接死锁预防方法，即防止前三个必要条件中任何一个条件的发生
• 直接死锁预防方法，即防止循环等待条件发生。

互斥条件

互斥条件一般不可能禁止，某些资源必须同一时间只能由一个进程操作才能保证其安全性。

占有且等待

为了预防占有且等待条件条件，可以要求进程一次性请求所有资源，如果无法一次性请求那么就进行等待。但是这样做存在的问题有：

• 一个进程可能会被阻塞很长时间，以等待可以一次性获取到所有资源的时机。
• 从实际角度出发，进程在持有一部分资源的时候就可以继续正常运行，其次某个资源该进程只会持有一小部分时间，大部分时间都不会使用该资源。
• 进程可能无法预知它将来需要的资源

不可抢占

预防不可抢占的策略有以下几种：

• 当占有某个资源的进程在进一步尝试获取其它资源时被拒绝，那么该进程必须释放自己占有的资源，在必要时可以尝试重新获取这个被释放的资源。
• 当一个进程请求的资源被其他资源占有时，操作系统可以抢占这个持有资源的进程，要求它释放资源。

循环等待

循环等待的预防可以通过定义资源获取的访问顺序。若定义资源获取序列 { A , B , C , D } \{A,B,C,D\} {A,B,C,D}，当获取到资源 $B$ 时，只能够尝试获取资源 $C$ 或者 $D$。当然这个预防方式可能是低效的，可能会在没有必要的情况下拒绝资源的获取。

4 死锁避免

解决死锁问题的另一种方法是死锁避免，它和死锁预防的差别很小，可以把它理解为死锁预防的一种特例。
死锁避免策略在允许三个必要条件存在的条件下，来确保永远不会达到死锁点。

4.1 死锁避免方法

死锁避免方法有：

• 若一个进程的请求会导致死锁，那么不启动该进程。
• 若一个进程增加的资源请求会导致死锁，则不允许这个资源的分配。

相比死锁预防策略，死锁避免策略并发性更强。但是在使用中也有诸多限制：

• 必须事先声明每个进程请求的最大资源
• 分配的资源数量必须是固定的
• 在占有资源时，进程不能够退出
• 所讨论的进程的执行顺序必须没有任何同步要求的限制

我们先考虑第一个死锁避免方式，考虑一个有着 $n$ 个进程和 $m$ 种不同类型资源的系统，定义以下向量和矩阵。

• 系统中每种资源的总量：$$R=(R_1,R_2,\cdots ,R_m)$$
• 当前剩余的资源总量：$$V=(V_1,V_2,\cdots ,V_m)$$
• 进程 $i$ 对资源 $j$ 的需求矩阵，用$C_{ij}$表示，下面矩阵 $C$ 给出了每个进程对每种资源的最大需求，每行表示一个进程对所有类型资源的请求。为了避免死锁，这个矩阵必须事先声明：
  $$C=\left[\begin{array}{ccccc}{C}_{11}& C_{12}& C_{13}& \cdots & C_{1m}\\ C_{21}& C_{22}& C_{23}& \cdots & C_{2m}\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ C_{n1}& C_{n2}& C_{n3}& \cdots & C_{nm}\end{array}\right]$$
• 当前分配给进程 $i$ 的资源 $j$，用$A_{ij}$表示，使用矩阵 $A$表示当前资源的分配情况：
  $$A=\left[\begin{array}{ccccc}{A}_{11}& A_{12}& A_{13}& \cdots & A_{1m}\\ A_{21}& A_{22}& A_{23}& \cdots & A_{2m}\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ A_{n1}& A_{n2}& A_{n3}& \cdots & A_{nm}\end{array}\right]$$

从中可以看出以下关系成立：

• 对所有资源 $j$，要么资源可用，要么已经被分配给进程,即：$$R_j=V_j+\sum _N^{i=1}{A}_{ij}$$
• $C_{ij}\le R_i$，对所有的 $i$、$j$，任何一个进程对任何一种资源的请求都不能够超过系统中该资源的总量。
• $A_{ij}\le C_{ij}$，对所有的 $i$、$j$，分配给任何一个进程的任何一种资源都不会超过这个进程最初声明的此资源最大请求量。

所以死锁避免的策略为：若一个新的进程资源需求会导致死锁，则拒绝启动这个新进程，仅当
$$R_j\ge C_{j(n+1)}+\sum _n^{i=1}{C}_{ij}，j\in [0,m]$$
时才启动一个新进程$P_{n+1}$。当然这个策略不是最优的，它只假设了最坏的情况，即所有进程同时发出它们的最大请求。

4.2 银行家算法

第二个死锁避免方式又称银行家算法，需要定义安全状态和不安全状态，安全状态指至少一个资源分配序列不会导致死锁，即所有进程都能够顺利运行到结束，不安全状态指非安全的一个状态。

为了准确描述银行家算法，我们给出一个例子：

一共有4个进程和3种资源，资源总量的向量 $R=(9,3,6)$，每个进程对每种资源的最大需求矩阵 $C=\left[\begin{array}{ccc}3& 2& 2\\ 6& 1& 3\\ 3& 1& 4\\ 4& 2& 2\end{array}\right]$，假设当前资源分配矩阵$A$ 为：$A=\left[\begin{array}{ccc}1& 0& 0\\ 6& 1& 2\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]$，问当前状态是否为安全状态？或者说，可用资源能否满足当前的分配情况和任何一个进程的最大需求？

从上述条件可知，发现剩余资源向量为$V=(0,1,1)$。
观察进程$P_1$，发现$P_1$是不可能在此时正常结束的，因为进程$P_1$还需要2个$R_1$资源、两个$R_2$资源和两个$R_3$资源。
观察进程$P_2$，发现进程只需要一个$R_3$资源就达到了所需的最大资源，从而可以顺利运行完成。当$P_2$进程执行结束后，资源便会归还给资源池。

$P_2$进程在获得到一个$R_3$资源并运行结束后，此时的资源分配矩阵$A=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 0\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]$，可用资源向量$V=(6,2,3)$。
现在再来看进程$P_1$，发现进程$P_1$可以正常完成，假设现在选择$P_1$进程执行并运行结束后，资源分配矩阵$A=\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]$
现在还差进程$P_3$和进程$P_4$等待执行，此时剩余资源向量$V=(7,2,3)$，下一步也可以正常将全部资源分配给$P_3$并执行完成，最后再分配给$P_4$进程。
至此4个进程全部执行完成，执行顺序为$P_2\to P_1\to P_3\to P_4$。

总的来说，银行家算法就是当进程请求一组资源时，先判断这个进程在请求了指定的资源后能不能处于安全状态，如果可以，就同意这个请求，如果不行，则阻塞该进程直到能够满足。

再举个例子，同样是4个进程3种资源，资源总量和需求矩阵和上述例子相同，假设初始资源分配矩阵$A=\left[\begin{array}{ccc}1& 0& 0\\ 5& 1& 1\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]$。

可以计算出剩余资源向量$V=(1,1,2)$，现在考虑进程$P_1$，假设$P_1$请求一个$R_1$资源和一个$R_3$资源，如果同意了，那么资源分配矩阵$A=\left[\begin{array}{ccc}2& 0& 1\\ 5& 1& 1\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]$，$V=(0,1,1)，$此时可以得到每个进程需要的资源矩阵：$C-A=\left[\begin{array}{ccc}1& 2& 1\\ 1& 0& 2\\ 1& 0& 3\\ 4& 2& 0\end{array}\right]$
这是个不安全的状态，因为每个进程都需要至少一个$R_1$资源，因此进程$P_1$的请求将会被拒绝，因为如果请求了有可能会导致死锁。

银行家算法不能够准确预测死锁，它的策略是将死锁的可能性降到0。

5 死锁检测

死锁检测不会限制资源访问或者约束进程的行为，当发生死锁时，通过死锁的检测来解除死锁状态。

死锁检测的一个常用算法描述如下：
使用上述定义的矩阵$C$和矩阵$A$，然后定义一个请求矩阵 $Q$，$Q_{ij}$表示进程$i$正在请求的$j$类资源的数量。执行以下步骤：

1. 首先标记矩阵$A$ 中一行全为0的进程，因为没有分配资源的进程不存在死锁。
2. 初始化向量 $W$，令$W=V$（$V$为未分配给进程的每种资源的总量）
3. 查找下标 $i$，忽略已经标记的进程$P_i$，使$Q$的第$i$行小于等于$W$，即$Q_{ik}\le W_k$。如果在$Q$中找不到这样行，终止算法。
4. 如果找到，标记进程$P_i$，并把矩阵$A$中相应的行与$W$相加，即$W_k=W_k+A_{ik}$。

当上述算法执行结束后，每个未被标记的进程都存在死锁。该算法不能预防死锁，它只能确定是否存在死锁。

现在定义资源需求矩阵为$Q=\left[\begin{array}{ccccc}0& 1& 0& 0& 1\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 1\\ 1& 0& 1& 0& 1\end{array}\right]$，资源总量$R=(2,1,1,2,1)$，此时：资源分配矩阵$A=\left[\begin{array}{ccccc}1& 0& 1& 1& 0\\ 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\end{array}\right]$，$V=(0,0,0,0,1)$，问现在是否存在死锁？

按照算法执行步骤：

1. 标记$P_4$，因为矩阵$A$ 中 $P_4$ 所在的行全为0。
2. 令$W=V$，此时 $W=(0,0,0,0,1)$
3. 进程$P_3$请求小于等于$W$，因此标记$P_3$，令$W=W+A_3=(0,0,0,0,1)+(0,0,0,1,0)=(0,0,0,1,0)$
4. 不存在其他未标记进程$P_i$在$Q_i$中小于等于$W$，此时终止算法。此时$P_1$和$P_2$尚未标记，表示两个进程存在死锁

参考资料：《操作系统精髓与设计》

目标

• 了解如何预防mysql死锁

  参考：mysql查看看开启事务_mysql如何查看正在运行的事务和事务上加的锁

  【MySQL】如何阅读死锁日志

  查找现在的sql 谁持有行锁

  mysql 查看锁等待

以下实例演示基于 MySQL 5.7.33版本 Innodb引擎

mysql 5.7 版本官方文档：https://dev.mysql.com/doc/refman/5.7/en/innodb-locking-transaction-model.html 理论内容很多借鉴官方文档的描述

在第一篇文章中，提出一个问题：

• Mysql事务之间出现死锁，会造成什么影响？

  答：除非非常频繁的事务死锁出现，导致一些业务事务根本无法执行。会导致业务出现问题。因此死锁并不危险，在mysql死锁检测机制下，会自动选择回滚某个阻塞的事务。所以我们必须编写事务回滚后的动作（比如重新发起事务等）

此篇将来详情回答这个问题。以下内容多从Mysql官方文档中摘录。

死锁出现后，mysql做了什么事情？

当启用死锁检测（默认）时， InnoDB自动检测事务 死锁并回滚一个或多个事务以打破死锁。 InnoDB尝试选择要回滚的小事务，其中事务的大小由插入、更新或删除的行数决定。如果使用innodb_deadlock_detect变量禁用死锁检测 ，则 InnoDB依赖 innodb_lock_wait_timeout设置在死锁情况下回滚事务。因此，即使您的应用程序逻辑是正确的，您仍然必须处理必须重试事务的情况。

Mysql 发生了死锁，真的严重吗？

死锁是事务数据库中的一个经典问题，但它们并不危险，除非它们非常频繁以至于您根本无法运行某些事务。通常，您必须编写应用程序，以便它们随时准备在事务因死锁回滚时重新发出事务。

• 如果由于死锁而失败，请随时准备重新发出事务。死锁并不危险。再试一次

死锁排查

查看InnoDB用户事务中的最后一个死锁，请使用 SHOW ENGINE INNODB STATUS

如果频繁的死锁突出了事务结构或应用程序错误处理的问题，则启用 innodb_print_all_deadlocks将所有死锁的信息打印到 mysqld错误日志。

这是mysql5.7官方文档提供的思路。

其他的一些命令

-- 以下sql 在出现阻塞事务，可能才能打印相关信息
-- mysql如何查看正在运行的事务
mysql> select * from information_schema.innodb_trx;
-- 查看事务加锁的类型
mysql> select * from information_schema.INNODB_LOCKS;
-- 查看等待锁的事务
mysql>SELECT * FROM INFORMATION_SCHEMA.INNODB_LOCK_WAITS;
-- mysql 查看锁等待
show processlist
 

减少死锁策略

• 使用事务而不是LOCK TABLES语句
• 将插入或更新数据的事务保持得足够小，以至于它们不会长时间保持打开状态
• 当不同的事务更新多个表或大范围的行时，在每个事务中使用相同的操作顺序（如 SELECT ... FOR UPDATE）
• 在SELECT ... FOR UPDATE和 UPDATE ... WHERE 语句中使用的列上创建索引
• 在进行一组相关更改后立即提交事务，以减少它们发生冲突的可能性。特别是，不要让交互式 mysql会话长时间处于打开状态并带有未提交的事务。
• 如果您使用锁定读取（SELECT … FOR UPDATE或 SELECT … LOCK IN SHARE MODE），请尝试使用较低的隔离级别，例如READ COMMITTED
• 当修改一个事务中的多个表或同一个表中的不同行集时，每次都以一致的顺序执行这些操作。然后事务形成明确定义的队列并且不会死锁。例如，组织数据库操作到功能在应用程序中，或调用存储程序，而不是编码的多个相似序列 INSERT，UPDATE以及 DELETE在不同的地方语句。
• 将精心挑选的索引添加到您的表中，以便您的查询扫描更少的索引记录并设置更少的锁。使用 EXPLAIN SELECT以确定哪些索引MySQL认为最适合您的查询。
• 使用较少的锁定。如果您可以允许 a SELECT从旧快照返回数据，请不要向其添加FOR UPDATE or LOCK IN SHARE MODE子句。在READ COMMITTED 这里使用隔离级别很好，因为同一事务中的每个一致性读取都从它自己的新快照中读取。
• 如果没有其他帮助，请使用表级锁序列化您的事务。表级锁可防止对表的并发更新，从而避免死锁，但代价是繁忙系统的响应速度变慢。
• 序列化事务的另一种方法是创建一个仅包含一行的辅助“信号量”表。让每个事务在访问其他表之前更新该行。这样，所有事务都以串行方式发生。请注意，InnoDB 即时死锁检测算法也适用于这种情况，因为序列化锁是行级锁。对于 MySQL 表级锁，必须使用超时方法来解决死锁。

也看到过一些文章写，如果允许出现更多的隔离问题，可以使用更低的隔离级别，来减少死锁产生（插入间隙锁）。

禁用死锁检测

在高并发系统上，当大量线程等待同一个锁时，死锁检测会导致速度变慢。有时，禁用死锁检测并在innodb_lock_wait_timeout 发生死锁时依赖事务回滚设置可能更有效 。可以使用该innodb_deadlock_detect 变量禁用死锁检测 。

Mysql 参数配置

其中有一些不是默认参数值，仅供参考。

开启performance_schema 分析现有sql 锁信息

注意：开启此参数，需要重复数据库实例，生产环境谨慎开启。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ngcjmTs3-1639031096455)(file://F:/img/image-20211102143821245.png?lastModify=1637656359)]

听说点赞关注的人，身体健康，一夜暴富，升职加薪迎娶白富美!!!

点我领取每日福利
微信公众号：耿子blog
GitHub地址：gengzi
文章如有错误，欢迎各位大佬指正。