银行家算法 2.txt

数据结构 假设有M个进程N类资源

实验二：银行家算法 
一、目的和要求 
银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 
二、实验内容 
1．设计进程对各类资源最大申请表示及初值确定。 
2．设定系统提供资源初始状况。 
3．设定每次某个进程对各类资源的申请表示。 
4．编制程序，依据银行家算法，决定其申请是否得到满足。 
三、说明 
1．数据结构 
假设有M个进程N类资源，则有如下数据结构： 
MAX[M*N] M个进程对N类资源的最大需求量 
AVAILABLE[N] 系统可用资源数 
ALLOCATION[M*N] M个进程已经得到N类资源的资源量 
NEED[M*N] M个进程还需要N类资源的资源量 
2．银行家算法 
设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。 
(1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 
(2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 
(3)系统试探分配资源，修改相关数据： 
AVAILABLE=AVAILABLE-REQUEST 
ALLOCATION=ALLOCATION+REQUEST 
NEED=NEED-REQUEST 
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 
3．安全性检查 
(1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE 
(2)从进程集合中找到一个满足下述条件的进程， 
FINISH[i]=FALSE 
NEED<=WORK 
如找到，执行(3)；否则，执行(4) 
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 
WORK=WORK+ALLOCATION 
FINISH=TRUE 
GO TO 2 
(4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。 
四、程序流程图 
银行家算法流程图： 


五、实验总结与体会 
操作系统是计算机系统中必不可少的系统软件。它是计算机系统中各种资源的管理者和各种活动的组织者、指挥者。银行家算法是为了使系统保持安全状态。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 
通过上面这个例子，我们看到银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。 
本次实验为时两天多，总体上来说实验是比较成功的。由于时间仓促，做的不是很完美，敬请谅解。 

附件 
操作说明：根据提示输入本次申请资源的进程号和申请资源数，如图： 


如资源申请成功，显示本次的申请后的一个进程安全执行序列。如图： 


如资源申请不成功，则恢复申请前的资源状况。如图： 


如对I类申请数大于进程还需要I类资源的资源量或大于系统可用I类资源数。如图： 

源程序清单 
#include "string.h" 
#include "iostream.h" 
#define M 5 //总进程数 
#define N 3 //总资源数 
#define FALSE 0 
#define TRUE 1 

//M个进程对N类资源最大资源需求量 
int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; 
//系统可用资源数 
int AVAILABLE[N]={10,5,7}; 
//M个进程已经得到N类资源的资源量 
int ALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}; 
//M个进程还需要N类资源的资源量 
int NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; 
int Request[N]={0,0,0}; 


void main() 
{ 
int i=0,j=0; 
char flag='Y'; 
void showdata(); 
void changdata(int); 
void rstordata(int); 
int chkerr(int); 

showdata(); 
while(flag=='Y'||flag=='y') 
{ 
i=-1; 
while(i<0||i>=M) 
{ 
cout<<" 请输入需申请资源的进程号（从0到"<<M-1<<"，否则重输入!）:"; 
cin>>i; 
if(i<0||i>=M)cout<<" 输入的进程号不存在，重新输入!"<<endl; 
} 
cout<<" 请输入进程"<<i<<"申请的资源数"<<endl; 
for (j=0;j<N;j++) 
{ 
cout<<" 资源"<<j<<": "; 
cin>>Request[j]; 
if(Request[j]>NEED[i][j]) 
{ 
cout<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的资源量!"; 
cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; 
flag='N'; 
break; 
} 
else 
{ 
if(Request[j]>AVAILABLE[j]) 
{ 
cout<<" 进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!"; 
cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; 
flag='N'; 
break; 
} 
} 
} 
if(flag=='Y'||flag=='y') 
{ 
changdata(i); 
if(chkerr(i)) 
{ 
rstordata(i); 
showdata(); 
} 
else 
showdata(); 
} 
else 
showdata(); 
cout<<endl; 
cout<<" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: "; 
cin>>flag; 
} 
} 


void showdata() 
{ 
int i,j; 
cout<<" 系统可用的资源数为:"<<endl<<endl; 
cout<<" "; 
for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<AVAILABLE[j]; 
cout<<endl; 
// cout<<endl; 
// cout<<" 各进程资源的最大需求量:"<<endl<<endl; 
// for (i=0;i<M;i++) 
// { 
// cout<<"进程"<<i<<":"; 
// for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<MAX[i][j]; 
// cout<<endl; 
// } 
cout<<endl; 
cout<<" 各进程还需要的资源量:"<<endl<<endl; 
for (i=0;i<M;i++) 
{ 
cout<<"进程"<<i<<":"; 
for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<NEED[i][j]; 
cout<<endl; 
} 
cout<<endl; 
cout<<" 各进程已经得到的资源量: "<<endl<<endl; 
for (i=0;i<M;i++) 
{ 
cout<<"进程"<<i<<":"; 
for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<ALLOCATION[i][j]; 
cout<<endl; 
} 
cout<<endl; 
}; 

void changdata(int k) 
{ 
int j; 
for (j=0;j<N;j++) 
{ 
AVAILABLE[j]=AVAILABLE[j]-Request[j]; 
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; 
NEED[k][j]=NEED[k][j]-Request[j]; 
} 

}; 

void rstordata(int k) 
{ 
int j; 
for (j=0;j<N;j++) 
{ 
AVAILABLE[j]=AVAILABLE[j]+Request[j]; 
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; 
NEED[k][j]=NEED[k][j]+Request[j]; 
} 

}; 

int chkerr(int s) 
{ 
int WORK,FINISH[M],temp[M]; 
int i,j,k=0; 
for(i=0;i<M;i++)FINISH[i]=FALSE; 
for(j=0;j<N;j++) 
{ 
WORK=AVAILABLE[j]; 
i=s; 
while(i<M) 
{ 
if (FINISH[i]==FALSE&&NEED[i][j]<=WORK) 
{ 
WORK=WORK+ALLOCATION[i][j]; 
FINISH[i]=TRUE; 
temp[k]=i; 
k++; 
i=0; 
} 
else 
{ 
i++; 
} 
} 
for(i=0;i<M;i++) 
if(FINISH[i]==FALSE) 
{ 
cout<<endl; 
cout<<" 系统不安全!!! 本次资源申请不成功!!!"<<endl; 
cout<<endl; 
return 1; 
} 
} 
cout<<endl; 
cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl; 
cout<<endl; 
cout<<" 本次安全序列："; 
for(i=0;i<M;i++)cout<<"进程"<<temp[i]<<"->"; 
cout<<endl<<endl;; 
return 0; 
};