死锁

基本概念

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

之所以发生这种情况，是因为操作系统追求尽可能充分地利用系统中所有的资源和尽可能让更多的进程投入运行以提高系统中资源的利用率，提高系统的吞吐量而造成“资源相对短缺”的情形。

产生死锁的起因

1）死锁的起因是并发进程的资源竞争。

2）产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。

3）显然，由于资源的有限性，我们不可能为所有要求资源的进程无限制地提供资源。

4）但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。

产生死锁的必要条件

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

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

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

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

处理死锁的方法

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

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

3、死锁的检测。保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待。

银行家算法

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

1、安全与不安全状态

安全状态是指系统至少存在一个安全序列<P1, P2, …, Pn>，按照这个序列为进程分配资源，直到满足最大需求，每个进程都可顺序完成。

若系统不存在这样一个安全序列，则系统处于不安全状态。

2、银行家算法的原理

1)把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。

2)操作系统按照银行家制定的规则为进程分配资源。

3)当进程首次申请资源时，要测试该进程对资源的最大需求量

4)如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。

5)当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。

6)若超过则拒绝分配资源。若能满足则按当前的申请量分配资源，否则推迟分配

3、银行家算法需要用到的数据结构

1)可利用资源向量Available ，是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。

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

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

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

Need[i,j]=Max[i,j]-Allocation[i,j]

4、银行家算法的描述

设进程P提出请求REQUEST [i]，则银行家算法按如下规则进行判断。

1)如果REQUEST [P] [i]<= NEED[P][i]，则转(2)；否则，出错。

2)如果REQUEST [P] [i]<= AVAILABLE[i]，则转(3)；否则，出错。

3)系统试探分配资源，修改相关数据：

AVAILABLE[i]-=REQUEST[P][i]; ALLOCATION[P][i]+=REQUEST[P][i]; NEED[P][i]-=REQUEST[P][i];

4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待

5、安全性算法

安全性算法是银行家算法的组成部分。

在银行家算法中，对进程提出的资源请求进行预分配后，需要检查这种分配是否会造成系统进入不安全状态。

如果不会进入不安全状态，称为安全检查性通过，分配成立；否则，撤销预分配，系统回到原来的安全状态，请求资源的进程被挂起。

描述：

1）设Work和Finish为长度m和n的向量。按如下方式初始化，

即Work=Available且对于i=0,1,…,n-1，Finish[i]=false。

2）查找这样的i使其满足

   a.Finish[i]=false   b.Needi≤Work

   如果没有这样的i存在，就转到第4步。

3）Work=Work+Allocationi

   Finish[i]=true

   返回到第2步。

4）如果对所有i，Finish[i]=true,那么系统处于安全状态。否则系统处于不安全状态

死锁检测与解除

死锁的解除

当发现死锁时，应立即把它们从死锁中解脱出来，常采用的两种方法是：

1）剥夺资源，从其它进程剥夺足够数量的资源给死锁进程。

2）撤消进程，撤消的原则是：为解除死锁状态所需撤消的进程数目最小；撤消进程所付出的代价最小。