银行家算法是一种最有代表性的避免死锁的算法。

简介(安全状态 不安全状态)

数据结构

银行家算法原理

算法的实现(初始化 银行家算法 安全性检查算法)

算法（C++实现）

简介

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

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

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

安全状态

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

不安全状态

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

数据结构

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]

银行家算法原理

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

为保证资金的安全，银行家规定：

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

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

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

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

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

运行平台：Windows XP VS2005

编程语言：C#

算法的实现

初始化

由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。

银行家算法

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。

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

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

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

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

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];

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

安全性检查算法

（1)设置两个工作向量Work=AVAILABLE;FINISH

(2)从进程集合中找到一个满足下述条件的进程，

FINISH==false;

NEED<=Work;

如找到，执行（3)；否则，执行（4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work+=ALLOCATION;

Finish=true;

GOTO 2

(4)如所有的进程Finish= true，则表示安全；否则系统不安全。

银行家算法流程图

算法（C++实现）

#include<iostream>

using namespace std;

#include<string.h>

#include<stdio.h>

#define False 0

#define True 1

int Max[100][100]={0};//各进程所需各类资源的最大需求

int Avaliable[100]={0};//系统可用资源

char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源

int Need[100][100]={0};//还需要资源

int Request[100]={0};//请求资源向量

int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系统可提供资源

int M=100;//作业的最大数为100

int N=100;//资源的最大数为100

void showdata()//显示资源矩阵

{

int i,j;

cout<<"系统目前可用的资源[Avaliable]:"<<endl;

for(i=0;i<N;i++)cout<<name[i]<<" ";

cout<<endl;

for (j=0;j<N;j++)cout<<Avaliable[j]<<" ";//输出分配资源

cout<<endl;

cout<<" Max Allocation Need"<<endl;

cout<<"进程名 ";

for(j=0;j<3;j++){

for(i=0;i<N;i++)cout<<name[i]<<" ";

cout<<" ";

}

cout<<endl;

for(i=0;i<M;i++){

cout<<" "<<i<<" ";

for(j=0;j<N;j++)cout<<Max[i][j]<<" ";

cout<<" ";

for(j=0;j<N;j++)cout<<Allocation[i][j]<<" ";

cout<<" ";

for(j=0;j<N;j++)cout<<Need[i][j]<<" ";

cout<<endl;

}

}

int changdata(int i)//进行资源分配

{

int j;

for (j=0;j<M;j++) {

Avaliable[j]=Avaliable[j]-Request[j];

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

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

}

return 1;

}

int safe()//安全性算法

{

int i,k=0,m,apply,Finish[100]={0};

int j;

int flag=0;

for(i=0;i<N;i++)

{

Work[i]=Avaliable[i];

}

for(i=0;i<M;i++){

apply=0;

for(j=0;j<N;j++){

if (Finish[i]==False&&Need[i][j]<=Work[j]){

apply++;

if(apply==N){

for(m=0;m<N;m++)Work[m]=Work[m]+Allocation[i][m];//变分配数

Finish[i]=True;

temp[k]=i;i=-1;

k++;flag++;

}

}

}

}

for(i=0;i<M;i++){

if(Finish[i]==False){

cout<<"系统不安全"<<endl;//不成功系统不安全

return -1;

}

}

cout<<"系统是安全的！"<<endl;//如果安全，输出成功

cout<<"分配的序列：";

for(i=0;i<M;i++){//输出运行进程数组

cout<<temp[i];

if(i<M-1) cout<<"->";

}

cout<<endl;

return 0;

}

void share()//利用银行家算法对申请资源对进行判定

{

char ch;

int i=0,j=0;

ch='y';

cout<<"请输入要求分配的资源进程号（0-"<<M-1<<"):";

cin>>i;//输入须申请的资源号

cout<<"请输入进程 "<<i<<" 申请的资源："<<endl;

for(j=0;j<N;j++){

cout<<name[j]<<":";

cin>>Request[j];//输入需要申请的资源

}

for (j=0;j<N;j++){

if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错

{

cout<<"进程 "<<i<<"申请的资源大于它需要的资源";

cout<<" 分配不合理，不予分配！"<<endl;

ch='n';

break;

}

else {

if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，若大于则

{

//出错

cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源";

cout<<" 分配出错，不予分配！"<<endl;

ch='n';

break;

}

}

}

if(ch=='y') {

changdata(i);//根据进程需求量变换资源

showdata();//根据进程需求量显示变换后的资源

safe();//根据进程需求量进行银行家算法判断

}

}

void addresources(){//添加资源

int n,flag;

cout<<"请输入需要添加资源种类的数量：";

cin>>n;

flag=N;

N=N+n;

for(int i=0;i<n;i++){

cout<<"名称：";

cin>>name[flag];

cout<<"数量：";

cin>>Avaliable[flag++];

}

showdata();

safe();

}

void delresources(){//删除资源

char ming;

int i,flag=1;

cout<<"请输入需要删除的资源名称：";

do{

cin>>ming;

for(i=0;i<N;i++)

if(ming==name[i]){

flag=0;

break;

}

if(i==N)

cout<<"该资源名称不存在，请重新输入：";

}

while(flag);

for(int j=i;j<N-1;j++){

name[j]=name[j+1];

Avaliable[j]=Avaliable[j+1];

}

N=N-1;

showdata();

safe();

}

void changeresources(){//修改资源函数

cout<<"系统目前可用的资源[Avaliable]:"<<endl;

for(int i=0;i<N;i++)

cout<<name[i]<<":"<<Avaliable[i]<<endl;

cout<<"输入系统可用资源[Avaliable]:"<<endl;

cin>>Avaliable[0]>>Avaliable[1]>>Avaliable[2];

cout<<"经修改后的系统可用资源为"<<endl;

for (int k=0;k<N;k++)

cout<<name[k]<<":"<<Avaliable[k]<<endl;

showdata();

safe();

}

void addprocess(){//添加作业

int flag=M;

M=M+1;

cout<<"请输入该作业的最打需求量[Max]"<<endl;

for(int i=0;i<N;i++){

cout<<name[i]<<":";

cin>>Max[flag][i];

Need[flag][i]=Max[flag][i]-Allocation[flag][i];

}

showdata();

safe();

}

int main()//主函数

{

int i,j,number,choice,m,n,flag;

char ming;

cout<<"*****************资源管理系统的设计与实现*****************"<<endl;

cout<<"请首先输入系统可供资源种类的数量：";

cin>>n;

N=n;

for(i=0;i<n;i++){

cout<<"资源"<<i+1<<"的名称：";

cin>>ming;

name[i]=ming;

cout<<"资源的数量：";

cin>>number;

Avaliable[i]=number;

}

cout<<endl;

cout<<"请输入作业的数量：";

cin>>m;

M=m;

cout<<"请输入各进程的最大需求量（"<<m<<"*"<<n<<"矩阵）[Max]:"<<endl;

for(i=0;i<m;i++)

for(j=0;j<n;j++)

cin>>Max[i][j];

do{

flag=0;

cout<<"请输入各进程已经申请的资源量（"<<m<<"*"<<n<<"矩阵）[Allocation]:"<<endl;

for(i=0;i<m;i++)

for(j=0;j<n;j++){

cin>>Allocation[i][j];

if(Allocation[i][j]>Max[i][j])

flag=1;

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

}

if(flag)

cout<<"申请的资源大于最大需求量，请重新输入！\";

}

while(flag);

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全

while(true){

cout<<"**************银行家算法演示***************"<<endl;

cout<<" 1:增加资源 "<<endl;

cout<<" 2:删除资源 "<<endl;

cout<<" 3:修改资源 "<<endl;

cout<<" 4:分配资源 "<<endl;

cout<<" 5:增加作业 "<<endl;

cout<<" 0:离开 "<<endl;

cout<<"*******************************************"<<endl;

cout<<"请选择功能号：";

cin>>choice;

switch(choice){

case 1: addresources();break;

case 2: delresources();break;

case 3: changeresources();break;

case 4: share();break;

case 5: addprocess();break;

case 0: choice=0;break;

default: cout<<"请正确选择功能号（0-5)!"<<endl;break;

}

}

return 1;

}