银行家算法

什么是银行家算法：

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

要解释银行家算法，必须先解释 *** 作系统安全状态和不安全状态。

安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j <i )当前占有资源量之和。

安全状态

如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态

不存在一个安全序列。不安全状态不一定导致死锁。

原理：

我们可以把 *** 作系统看作是银行家， *** 作系统管理的资源相当于银行家管理的资金，进程向 *** 作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全,银行家规定:

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客

(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款

(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.

*** 作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

程序举例：

已知进程{P0,P1,P2,P3,P4}，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源

（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；

（2）若进程P2提出请求Request(0，1，0)，用银行家算法程序验证系统能否将资源分配给它。

程序代码：

P1进程提出的请求，可以分配。

P2进程不能分配，因为请求的B类资源超过了它的最大值。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define MAXSIZE 50

void main()

{

unsigned int Available[MAXSIZE] //可利用资源向量

unsigned int Max[MAXSIZE][MAXSIZE] //最大需求矩阵

unsigned int Allocation[MAXSIZE][MAXSIZE]//已分配矩阵

unsigned int Need[MAXSIZE][MAXSIZE] //需求矩阵

unsigned int Request[MAXSIZE] //请求向量

unsigned int Work[MAXSIZE]//工作向量

bool Finish[MAXSIZE] //是否有足够资源分配给进程,使之运行完成

unsigned int SafeSequence[MAXSIZE] //安全序列

int i,j

int p//请求资源的进程的下标

int temp = 0 //安全序列下标

int total = 0

int N

int M

printf("请输入进程数N=")

scanf("%d",&N)

printf("请输入资源种类数M=")

scanf("%d",&M)

//用户输入数据,初始化Available数组

printf("初始化可用资源数组:\n")

for(i=0i<Mi++)

{

printf("\t%c类资源:",65+i)

scanf("%d",&Available[i])

}

//用户输入数据,初始化Max数组

printf("初始化最大需求数组:\n")

for(i=0i<Ni++)

{

printf("\tP%d进程最大需要\n",i)

for(j=0j<Mj++)

{

printf("\t\t%c类资源:",65+j)

scanf("%d",&Max[i][j])

}

}

//用户输入数据,初始化Allocation数组

printf("初始化已分配资源数组:\n")

for(i=0i<Ni++)

{

printf("\tP%d进程已分配\n",i)

for(j=0j<Mj++)

{

printf("\t\t%c类资源:",65+j)

scanf("%d",&Allocation[i][j])

}

}

//初始化Need数组

for(i=0i<Ni++)

for(j=0j<Mj++)

{

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

}

//进程发出资源请求后检查

do

{

printf("资源请求:\n")

printf("\t输入请求资源的进程下标:")

scanf("%d",&p)

printf("\t进程P%d请求\n",p)

//初始化请求向量

for(i=0i<Mi++)

{

printf("\t\t%c类资源:",65+i)

scanf("%d",&Request[i])

}

for(i=0i<Mi++) //检查Request <= Need ?

if(Request[i] >Need[p][i])

{

printf("\t请求的%c类资源数超过它所宣布的最大值!\n",65+i)

break

}

if(i == M) //通过上层检查,继续检查Request <= Available ?

{

for(i=0i<Mi++)

if(Request[i] >Available[i])

{

printf("\t尚无足够%c类资源,P%d须等待!\n",65+i,p)

break

}

}

if(i == M) //尝试分配

{

for(i=0i<Mi++)

{

Available[i] -= Request[i]

Allocation[p][i] += Request[i]

Need[p][i] -= Request[i]

}

}

}while(i<M)

//初始化Work,Finish向量

for(i=0i<Mi++)

{

Work[i] = Available[i]

}

for(i=0i<Ni++)

{

Finish[i] = false

}

//安全性算法

do

{

total = temp

for(i=0i<Ni++)

{

if(Finish[i] == false)

{

for(j=0j<Mj++)

if(Need[i][j] >Work[j])

{

break

}

if(j == M) //各类资源都满足Need <= Work

{

for(j=0j<Mj++)

{

Work[j] += Allocation[i][j]//释放资源

}

Finish[i] = true

SafeSequence[temp++] = i //加入安全序列

}

}

}

}while(total != temp) //所有进程检查一遍之后，如果安全序列有变化，则进行下一轮

//否则说明所有的Finish都为true,或者因没有安全序列退出循环

if(temp == N)

{

printf("安全序列:")

for(temp=0temp<Ntemp++)

{

printf("P%d ",SafeSequence[temp])

}

}

else

{

printf("系统处于不安全状态!不能分配!\n")

}

getchar()

getchar()

}

这个程序还行，输入有点麻烦，我自己编写的是用文件输入系统描述信息的，但是缺少说明，怕你搞不明白。希望对你有所帮助！

银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。

�7�4 与预防死锁的几种方法相比较，限制条件少，资源利用程度提高了。

�7�4 缺点：该算法要求客户数保持固定不变，这在多道程序系统中是难以做到的；该算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素；由于要寻找一个安全序列，实际上增加了系统的开销.

Banker algorithm 最重要的一点是：保证 *** 作系统的安全状态！这也是 *** 作系统判断是否分配给一个进程资源的标准！那什么是安全状态？举个小例子，进程 P 需要申请 8 个资源（假设都是一样的），已经申请了 5 个资源，还差 3 个资源。若这个时候 *** 作系统还剩下 2 个资源。很显然，这个时候 *** 作系统无论如何都不能再分配资源给进程 P 了，因为即使全部给了他也不够，还很可能会造成死锁。若这个时候 *** 作系统还有 3 个资源，无论 P 这一次申请几个资源， *** 作系统都可以满足他，因为 *** 作系统可以保证 P 不死锁，只要他不把剩余的资源分配给别人，进程 P 就一定能顺利完成任务。 为什么银行家算法是可行的呢？这里需要严格的证明一下。不管任何时候， *** 作系统分配资源的时候都可以保证当前接受资源的进程不会陷入死锁，因为 *** 作系统总是可以满足该进程需要的资源的。假设有 n 个进程 {p1, p2, p3, … pn} ，最后一个分配到资源的是 pi ， pi 还需要 mi 个资源，假设此时 *** 作系统还有 m 个资源剩余。那么很显然 m>=mi ！而且如果之后 *** 作系统又把资源分配给其他进程了，假设是 pj ， pj 还需要 mj 个资源，同理可知 m>=mj ！也就是说在所有的进程中，还需要的资源数总是有小于 m 的！这样就可以保证资源数永远不会为 0 ，即使可能暂时性为 0 。另外，还需要保证资源数不会减少！而且，所有已经分配到资源的进程总有一天会归还它所拥有的资源！根据 *** 作系统再分配的时候的状态即可判定。

---