操作系统 银行家算法

银行家算法

Dijkstra的银行家算法是最具有代表性的避免死锁的算法，这个算法因能用于银行系统现金贷款的发放而得名。

安全状态

所谓安全状态，是指系统能按某种进程顺序（P1，P2，…，Pn）（称<P1,P2,…,Pn>为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
避免死锁的实质在于:系统进行资源分配时,如何使系统不进入安全状态。

系统处于不安全状态后,不一定进入死锁状态,但是,只要系统处于安全状态,系统便一定不会进入死锁状态。

相关数据结构

Available ——可利用的资源数 Available[j]=K 表示系统中现有Rj类资源K个
Max ——资源最大需求数 Max[i,j]=K 表示进程i需要Rj类资源的最大数目为K
Allocation ——已分配资源数 Allocation[i,j]=K 表示进程i当前已分得Rj类资源的数目为K
Need ——还需资源数 Need[i,j]=K 表示进程i还需要Rj类资源K个
存在关系 —— Need[i,j] = MAx[i,j] - Allocation[i,j]

银行家算法

Request_i[j] = K,表示进程Pi需要K个Rj类型的资源.当Pi发出资源请求后,系统按如下步骤进行检查:

1. 如果Request_i[j] ≤ Need[i,j],便转向步骤2；否则认为出错,因为他所需要的资源数超过它所宣布的资源最大需求数。
2. 如果Request_i[j] ≤ Available[i,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等待。
   

安全性算法(设置向量)

1. 首先设置两个向量: ① ** Work ** 表示系统可以提供给进程继续运行所需的各类资源数目。在执行安全算法开始时,Work:=Available。 ②** Finish ** 表示系统是否有足够的资源分配给进程,使之运行完成。开始时Finish[i]:=false；当有足够资源分配给进程时,令Finish[i]:=true。

2. 再从进程集合中找到一个能满足下述条件的进程: ① Finish[i] = false； ② Need[i,j] ≤ Work[i]； 若找到,执行步骤3,否则,执行步骤4。

3. 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行 :
   Work[j]:= Work[i]+ Allocation[i,j] ; Finish[i]:= true ;
   go to step 2;

4. 如果所有进程的Finish[i] = true都满足,则表示系统处于安全状态；否则,系统处于不安全状态。