死锁的概念

死锁(Deadlock)，这里指的是进程死锁。它是操作系统或软件运行的一种状态：在多任务系统下，当一个或多个进程等待系统资源，而资源又被进程本身或其他进程占用时，就形成了死锁。

所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。

计算机系统产生死锁的根本原因就是资源有限且进程间推进顺序不当

出现死锁的条件

• 互斥条件

• 即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。

• 不剥夺条件

• 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。

• 请求和保持条件

• 进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。

• 环路条件

                                                    这里写图片描述

处理死锁

• 死锁预防、死锁避免
• 死锁检测、死锁恢复

死锁预防

死锁的预防是保证系统不进入死锁状态的一种策略。

它的基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。

• 破坏“请求和保持”条件

• 即允许进程同时访问某些资源。
• 但是，有的资源是不允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。
• 所以，这种办法并无实用价值。

• 破坏“不剥夺”条件

• 即允许进程强行从占有者那里夺取某些资源。

• 破坏“环路等待”条件

• 可以实行资源预先分配策略。

死锁的避免

死锁的避免指在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。

死锁的检测和恢复

保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。

死锁检测算法主要是检查是否有循环等待。

死锁检测算法是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。检测方法有进程-资源有向图和死锁定理

一旦发生死锁，就利用资源剥夺法或进程撤销法解除死锁。

• 1)撤消陷于死锁的全部进程；
• 2)逐个撤消陷于死锁的进程，直到死锁不存在；
• 3)从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
• 4)从另外的进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。

鸵鸟算法

最简单的方法，就是忽略死锁。

据说(尽管很多人认为不可能)鸵鸟遇到无法避免的危险时就把头埋在沙子里，对出现的危险不管不顾。

操作系统处理死锁的一种策略是不预防、不避免，对可能出现的死锁采取放任的态度，称作鸵鸟算法。

当出现死锁的概率很小，并且出现之后处理死锁会花费很大的代价时，执行死锁避免的开销很大，还不如不做处理。因此，鸵鸟算法是平衡性能和复杂性的一种方法。

….啥都不处理也能叫做成一个算法….

银行家算法

银行家算法是一种最有代表性的避免死锁的算法。又被称为“资源分配拒绝”法。

• 一、安全状态

• 所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{ P1 ，P2 …Pn}就是安全序列。
• 如果存在这样一个安全序列，则系统是安全的。

• 二、由安全状态向不安全状态的转换

• 对于处于安全状态的系统，当某进程请求某些资源后，系统不再安全，也就是说，不存在一个安全序列，那么，此时系统处于不安全状态。

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

• 　(1) 可利用资源向量Available。
• (2) 最大需求矩阵Max。　
• (3) 分配矩阵Allocation。　　
• (4) 需求矩阵Need。

设Requesti是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。

(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j] = Available[j] - Request i[j];

Allocation[i, j] = Allocation[i, j] + Request i[j];

Need[i, j] = Need[i, j] - Request i[j];

(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待