The Dead Lock

产生死锁的原因和必要条件

死锁相关定义

永久（可重用）性资源

• 可抢占性资源: 是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺
• 不可抢占性资源: 当系统把这类资源分配给某进程后，就不能强行收回，只能在进程用完后自行释放。临时性（消耗性）资源
• 只可使用一次的资源

死锁 Dead Lock：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。

• 死锁会造成进程无法执行
• 死锁会造成系统资源的极大浪费(资源没法释放)

产生死锁的原因

• 竞争资源
• 进程间推进顺序不当

产生死锁的必要条件

1. 互斥条件:进程对分配到的资源进行排它性使用
2. 请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又被其他进程占有，请求进程阻塞，但对已经获得的资源不释放
3. 不剥夺条件:进程已获得的资源在未使用完之前，不能被剥夺，只能在使用完时自己释放
4. 环路等待条件:发生死锁时，必然存在进程—资源的环形链

资源分配图

资源分配图 Resource Allocation Graph(RAG)：用来描述进程和资源之间的关系，以及资源之间的竞争关系。它是有向图，说明了系统资源、进程状态，其中每个资源、进程用节点表示，圆点表示资源的一个示例，一个资源可拥有多个实例

1.竞争不可抢占性资源引起死锁

2.竞争临时性资源引起进行死锁
临时性资源，可以创造（生产）和撤消（消耗）的资源，也称之为消耗性资源，如信号量、消息、buffer 中的数据等资源
例如：S1、S2 和 S3 是临时性资源，是由进程 P1、P2 和 P3 产生的消息。如果消息通信处理顺序不当也会发生死锁。

3. 进程推进顺序不当引起死锁
联合进程图(Joint Progress Diagram)记录共享资源的多个进程的执行进展

竞争资源，未必产生死锁。是否产生死锁，还取决于动态执行和应用程序细节

1
2

P: 申请A，申请B，释放A，释放B
Q: 申请B，申请A，释放B，释放A

预防死锁的方法

1. 预防死锁 Deadlock Prevention：设置某些限制条件，破坏四个必要条件中的一个或几个。
   优点：容易实现
   缺点:系统资源利用率和吞吐量降低
2. 避免死锁 Deadlock Avoidance：在资源的动态分配过程用某种方法防止系统进入不安全状态。
   优点：较弱限制条件可获得较高系统资源利用率和吞吐量。
   缺点：有一定实现难度。
   死锁避免的两种方法：
   • 若一个进程的请求会导致死锁，则不启动进程
   • 若一个进程增加的资源请求会导致死锁，则不允许这一资源分配
3. 检测死锁 Deadlock Detection：预先不采取任何限制，也不检查系统是否已进入不安全区，通过设置检测机构，检测出死锁后解除。
4. 解除死锁 Unlocking deadlock：常用撤消或挂起一些进程，回收一些资源。

预防死锁和避免死锁是两种不同的概念，两者都是事先防范死锁的发生，但是方法不同。
预防死锁是在系统设计时就考虑到死锁的可能性，采取措施避免死锁的发生，而避免死锁是在系统运行时，根据系统的状态，采取措施避免死锁的发生。

预防死锁：破坏死锁的必要条件，施加的条件比较严格，可能会影响到进程的并发执行。
避免死锁：资源动态分配，施加的限制条件较弱一些，有利于进程的并发执行。

摒弃请求和保持条件

第一种协议：系统要求所有进程一次性申请所需的全部资源，只要有一种资源要求不能满足，即使是已有的其它各资源，也全部不分配给该进程，而让其等待

• 优点：简单、易于实现且很安全。
• 缺点：资源严重浪费；进程延迟运行。

第二种协议：允许一个进程只获得运行初期所需的资源后便开始运行。进程运行过程中再逐步释放已分配给自己的、且已使用完毕的全部资源，然后再请求新的所需资源
优点：使进程更快地完成任务，提高设备的利用率，减少进程发生饥饿的概率

摒弃不剥夺条件

进程在需要资源时才提出请求，一个已经保持了某些资源的进程，再提出新的资源要求而不能立即得到满足时，必须释放已经保持的所有资源，待以后需要时再重新申请。
Cons:实现复杂，代价大；延长了进程的周转时间，增加系统开销，降低系统吞吐量。

摒弃环路等待条件

系统将所有资源按类型进行线性排队（常用-不常用），并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，按序号递减的次序释放

假设我们的系统有三种资源：A、B、C，我们将它们按照使用频率进行排序，得到的序列是 A（最常用）-> B -> C（最不常用）。然后，我们给每种资源分配一个序号：A=1，B=2，C=3。
在这种策略下，所有的进程必须按照资源序号递增的顺序请求资源,按照资源序号递减的顺序释放资源。

避免死锁的方法

安全状态:是指系统能按某种进程顺序 〈P1, P2, …, Pn〉，来为每个进程 Pi 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成,则称这是一个安全序列。安全序列的实质是:序列中的每一个进程 Pi 到运行完成尚需的资源量不超过系统当前剩余的资源量与所有在它之前的进程 P1, P2, …, Pi-1 所占用的资源量之和。
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

• 并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能有进入死锁状态。
• 系统处于安全状态时，不会进入死锁状态。

死锁避免策略并不能确切的预测死锁，仅仅是预料死锁的可能性并确保永远不会出现这种可能性。
死锁避免比死锁预防限制少，但使用中也有许多限制：

• 必须事先声明每个进程请求的最大资源。
• 考虑的进程必须是无关的，执行的顺序必须没有任何同步的要求。
• 分配的资源数目必须是固定的。
• 在占有资源时，进程不能退出。

🌟 银行家算法思想 死锁避免策略

银行家算法的基本思想

避免死锁的关键在于如何准确的预测是否会出现死锁，从而避免死锁。最有代表性的避免死锁的算法是 Dijkstra 在 1965 年提出的银行家算法。该算法可用于银行发放一笔贷款前，预测该笔贷款是否会引起银行资金周转问题。
银行的资金就类似于计算机系统的资源，贷款业务类似于计算机的资源分配。银行家算法能预测一笔贷款业务对银行是否是安全的，该算法也能预测一次资源分配对计算机系统是否是安全的。

1. 当前状态下，某进程申请资源；
2. 系统假设将资源分给该进程，满足它的需求；
3. 检查分配后的系统状态是否是安全的，如果是安全，就确认本次分配；如果系统是不安全的，就取消本次分配并阻塞该进程(这一步也被称为安全性算法)

银行家算法的数据结构

为实现银行家算法，系统中必须设置若干数据结构

1. 可利用资源向量 Available这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j]= K，则表示系统中现有 $R_j$ 类资源 K 个。

2. 最大需求矩阵 Max这是一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max[i,j]=K，则表示进程 i 需要 $R_j$ 类资源的最大数目为 K。

3. 分配矩阵 Allocation这也是一个 n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,j]=K，则表示进程 i 当前已分得 $R_j$ 类资源的数目为 K。

4. 需求矩阵 Need这也是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need[i,j]=K，则表示进程 i 还需要 $R_j$ 类资源 K 个，方能完成其任务。

   设 $Request_i$ 是进程 $P_i$ 的请求向量，如果 $Request_i[j] = K$，表示进程 $P_i$ 需要 K 个 $R_j$ 类型的资源。当 Pi 发出资源请求后，系统按下述步骤进行检查：
   (1) 如果 $Request_i[j] \leq Need[i,j]$，便转向步骤 2；否则认为出错，因为它所申请的资源数已超过它所宣布的需要的资源数。
   (2) 如果 $Request_i[j] \leq Available[j]$，便转向步骤(3)；否则， 表示尚无足够资源，Pi 须等待。
   (3) 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：
   $Available[j]=Available[j]-Requesti[j];$
   $Allocation[i,j]=Allocation[i,j]+Requesti[j];$
   $Need[i,j]=Need[i,j]-Requesti[j];$
   (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。

   

安全性算法

(1) 设置两个向量：
工作向量 Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在执行安全算法开始时，Work 初始化为 Available;
Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先初始化 Finish[i]=false; 当有足够资源分配给进程时， 再令 Finish[i]=true。
(2) 从进程集合中找到一个能满足下述条件的进程：
$Finish[i] = false$
$Need[i,j] \leq Work[j]$
若找到， 执行步骤(3)，否则，执行步骤(4)。
(3) 当进程 Pi 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
$Work[j]=Work[j]+Allocation[i,j];$
$Finish[i]=true;$
go to step 2;
(4) 如果所有进程的$Finish[i]=true$都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

安全性算法

Q
在银行家算法中，若出现下述的资源分配情况：

Process	Max	Allocation	Available
P0	0 0 4 4	0 0 3 2	1 6 2 2
P1	2 7 5 0	1 0 0 0	1 6 2 2
P2	3 6 10 10	1 3 5 4	1 6 2 2
P3	0 9 8 4	0 3 3 2	1 6 2 2
P4	0 6 6 10	0 0 1 4	1 6 2 2

1）该状态是否安全？
2）若进程 P2 提出请求 Request（1，2，2，2）后，系统能否将资源分配给它？
3）如果系统立即满足 P2 的上述请求，系统是否立即进入死锁状态？

A

(1) 安全的，一个可能的安全序列为 {P0，P3，P4，P1，P2}或{P0，P3，P1，P4， P2}

(2) P2 发出请求向量$Request（1，2，2，2）$后，系统按照银行家算法进行检查：
$Request_2（1，2，2，2）\le Need_2（2，3，5，6）$
$Request_2（1，2，2，2）\le Available（1，6，2，2）$
系统先假定可为 P2 分配资源，并修改$Available,Allocation_2,Need_2$向量
$Availabe=（0，4，0，0）,Allocation_2=（2，5，7，6）
Need_2=(1,1,3,4)$
进行安全性检查：此时对所有进程，条件 $Need_i≦ Available（0，4，0，0）$都不成立，即 $Available$ 不能满足任何进程的请求，故系统进入不安全状态。因此，当进程 P2 提出请求 $Request（1，2，2，2）$后，系统不能将资源分配给它
(3) 系统立即满足进程 P2 的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并未因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。

死锁的检测与解除

如果系统不愿意附加太多约束条件预防死锁，也不希望系统额外开销预测并避免死锁，那么，只能允许死锁出现，然后，再解除它。因此，系统需要利用某种方法来检测死锁。

死锁检测

化简资源分配图—检测死锁

资源分配图(Resource Allocation Graph)
该图是由一组结点 N 和一组边 E 所组成的一个对偶G＝（N,E），其中：

1. 把 N 分为两个互斥的子集，即一组进程结点P={P1,P2，…，Pn}和一组资源结点R={R1, R2 ，…， Rn}，N＝PUR
2. 凡属于 E 中的一个边 e∈E 都连接着 P 中的一个结点和 R 中的一个结点
   e={Pi,Rj}表示进程 Pi 请求一个单位的 $R_j$ 资源
   e={Rj,Pi}表示把一个单位的资源 $R_j$ 分配给进程 Pi

Steps:
第一步:先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的（即系统有足够的空闲资源分配给它）
第二步:把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来
第三步:重复一二步
第四步:最后，若所有的资源和进程都可以变成孤立的点。这样的图就叫做“可完全简化”

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

死锁检测中的数据结构

• 可利用资源向量 $Available$，它表示了 m 类资源中每一类资源的可用数目。
• 把不再占用资源的进程(即向量 $Allocation$ 和 $Request$ 为 0 的进程)记入 L 表中， 即$L = L_i\cup L$$
• 从进程集合中找到一个 $Request_i \le Work$ 的进程，做如下处理：① 将其资源分配图简化，释放出资源，增加工作向量 $Work=Work+Allocation_i$。 ② 将它记入 L 表中。
• 若不能把所有进程都记入 L 表中， 便表明系统状态 S 的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。

1
2
3
4
5
6
7
8
9
10

Work = Available;
L = {Li| Allocation_i = 0 ∩ Request_i = 0};
for(i=1; Pi not in L; i++){
   if Requesti≤Work{
      Work=Work+Allocation_i;
      Li=Pi；
      L=Li∪L;
   }
}
deadlock= !(L={p1, p2, …, pn});

例题
p 个进程共享 m 个同类资源，每一资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放，并且每个进程对该类资源的最大需求量小于该类资源的数目。设所有进程对资源的最大需要之和小于 p+m。试证：在系统中不会发生死锁。
证明：假设系统发生死锁。
设 Max(i)为进程 i 的最大资源需求量，Need(i)为进程 i 尚需资源量，Allocation(i)为已分配资源量，则系统在任意时刻有：
$\sum_{i=1}^{p}Max(i) = \sum_{i=1}^{p} Need(i) + \sum_{i=1}^{p}Allocation(i) \lt p+ m①$
系统发生死锁，则一方面说明所有 m 个资源都应该已经分配出去：$\sum_{i=1}^{p} Allocation(i)=m②$
另一方面，进程将处于无限等待状态之中。
由 ① ② 可以得到：$\sum_{i=1}^{p} Need(i) \lt p③$
即死锁后 p 个进程还需要的资源量之和少于 p，这就意味着此刻至少有一个进程譬如 j，已经获得了所需要的全部资源数，即$Need（j）=0$。但是系统发生死锁时，每个进程至少还需要一个资源单位，即$\sum_{i=1}^{p} Need(i) \geq p$，与等式 ③ 矛盾。此外，既然该进程已经获得了所需要的全部资源数，那么就能完成其任务并释放占有的资源，以保证系统能进一步前进，这与前面的假定死锁矛盾。

死锁的解除

当发现有进程死锁时，常采用的两种方法是解除死锁：

1. 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
2. 撤消进程。最简单的撤消进程的方法，是使全部死锁进程都夭折掉；或者按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。

按照解除死锁复杂度递增的顺序列出解除死锁的方法：

1. 撤消死锁进程 -该方法是目前操作系统中解除死锁的常用方法。
2. 把死锁进程恢复到前一个检查点，重新执行每个进程。
3. 按照某种原则逐个选择死锁进程进行撤消，直到解除系统死锁。
4. 按照某种原则逐个剥夺进程资源，直到解除死锁。

第三种和第四种方法需要选择系统付出代价最小的进程，最小代价原则：

• 到目前为止，花费处理机的时间最少的进程；
• 到目前为止，产生输出最少的进程；
• 估计未执行部分最多的进程；
• 到目前为止，已获得资源量最少的进程；
• 优先级最低的进程。
  为把系统从死锁状态中解脱出来，所花费的代价(最小)可表示为：
  $R(S)_{min} = \sum_{1\lt i\lt j\lt n} min{C_{ij}}$
• $R(S)_{min}$ 表示从死锁状态中解脱出来的最小代价。
• $C_{ui}$, $C_{uj}$, $C_{uk}$, … 表示各个死锁参与者（例如线程、进程或事务）需要付出的代价。这些代价可能是不同的，因为每个参与者可能在不同的状态，需要执行的操作也可能不同。
• $min{C_{ui}}$, $min{C_{uj}}$, $min{C_{uk}}$, … 表示选择每个死锁参与者需要付出的最小代价。这是因为在解决死锁时，通常会选择使得总代价最小的策略。