操作系统——银行家算法避免死锁问题

当计算机中出现死锁后我们认为死锁是一个不安全的状态，我们要用银行家算法来进行避免死锁也就是避免进入不安全的状态。

我们首先先提出一个问题来引出银行家算法：

假定系统中存在3个进程p1,p2,p3。他们需要同一种资源这种资源共有12份资源该如何分配。各个进程现在分配的资源和需要的最大资源详见下表

我们可以发现先将p2满足之后将其释放可用资源就变成了5，然后满足p1满足之后可用资源就成了10，然后去满足p3就可以发现三个进程全都完成了。

当然这些都是我们人自己去做的计算机中进程成千上万那我们又该怎么去解决呢这里就给出了银行家算法。

在探讨一个算法之前我们总是首先要聊的是这个算法数据结构。

1、可用资源Available是长度为m的一维数组其中每一个元素表示一类可以利用的资源数目。例如Available[j]=K，表示系统中现在第j类资源有K个

2、最大需求矩阵Max是一个n*m的矩阵，它定义系统中n个进程中每一个进程对m类资源的需求数量。例如Max[i,j]=K表示进程i需要j类资源最多K个。

3、分配矩阵Allocation是一个n*m的矩阵，跟Max矩阵很相似。表示系统已经给每一类进程了分配了多少每一类资源数目，例如Allocation[i,j]=K表示进程i已经分配了j类资源K个。

4、需求矩阵Need矩阵表示各进程最多还需要多少资源。例如Need[i,j]=K表示进程i还需要j类资源K个。与上两个矩阵的关系：Max[i,j] - Allocation[i,j]= Need[i,j]

算法步骤：

用长度为m的一维数组Request i表示进程此次申请的各种资源数，例如Request i[j]=K就是进程pi需要j类资源K个。

(1)如果Request i[j]≤Need[i,j],便可以进行步骤(2),否则认为它申请的超过了它最大所需要的就出错

(2)如果Request i[j]≤Available[i,j]便可以进行步骤(3),否则认为它所申请的资源说明超过了现在系统中可以用的最大数量需要等待，注意是等待不是出错。

(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进程等待。

系统所执行的安全性算法可描述如下：

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

注意：系统处于不安全状态未必死锁，但死锁时一定处于不安全状态，系统处于安全状态一定不会死锁。