2007-08-23
银行家算法 - [Algorithms]
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://conoon.blogbus.com/logs/7872511.html
#include<iostream>
using namespace std;
int M,N;
int temp=0;
int **maximum;
int *available;
int **allocate;
int **need;
bool *finish;
int *work;
int *process;
int *request;
void restore(int p);
void print();
void check(int p){
bool flag=false;
for(int i=0;i<N;i++){ //检查是否有进程finish[i]=false&need[i]<work
if(finish[i]==false){
int j=0;
for(;j<M;j++){
if(need[i][j]>work[j])
break;
}
if(j==M){ //如果有这样的进程设置finish=true
for(int k=0;k<M;k++)
work[k]+=allocate[i][k];
process[temp++]=i+1;
finish[i]=true;
flag=true;
}
}
}
if(flag==false){ //如果所有进程都不符合条件，判断是否所有finish[i]=true,
int k=0; //如果是，则系统处于安全状态，否则系统处于不安全状态
for(;k<N;k++){
if(finish[k]==false){ cout<<"系统处于不安全状态!资源分配失败！"<<endl;
restore(p);
break;}
}
if(k==N){
cout<<"系统处于安全状态！"<<endl;
printf("安全序列为：\n");
for(int i=0;i<N-1;i++)
printf("进程%d->",process[i]);
printf("进程%d\n",process[N-1]);
restore(p);
}
}
else check(p);
};
void print(){
printf("\n现有资源数：\n");
for(int i=0;i<M;i++) cout<<"资源"<<i+1<<"\t";
cout<<endl;
for(int i=0;i<M;i++) cout<<available[i]<<"\t";
cout<<endl;
cout<<"最大需求资源数："<<endl;
for(int i=0;i<N;i++){
cout<<"进程"<<i+1<<"\t";
for(int j=0;j<M;j++)
cout<<maximum[i][j]<<"\t";
cout<<endl;
}
cout<<"已分配资源数："<<endl;
for(int i=0;i<N;i++){
cout<<"进程"<<i+1<<"\t";
for(int j=0;j<M;j++)
cout<<allocate[i][j]<<"\t";
cout<<endl;
}
cout<<"还需要资源数："<<endl;
for(int i=0;i<N;i++){
cout<<"进程"<<i+1<<"\t";
for(int j=0;j<M;j++)
cout<<need[i][j]<<"\t";
cout<<endl;
}
};
void init()
{
cout<<endl;
cout<<"请输入资源种类数：";
cin>>M;
cout<<endl;
cout<<"请输入进程个数：";
cin>>N;
maximum=new int*[N];
available=new int[M];
allocate=new int*[N];
need=new int*[N];
finish=new bool[N];
work=new int[M];
process=new int[N];
request=new int[M];
for(int i=0;i<N;i++){
maximum[i]=new int[M];
allocate[i]=new int[M];
need[i]=new int[M];
}
cout<<endl;
cout<<"请输入每个资源的现有数量：(输入用回车结束)"<<endl;
for(int i=0;i<M;i++){
cout<<"进程"<<i+1<<":";
cin>>available[i];
}
cout<<endl;
cout<<"请输入每个进程的最大资源需求数："<<endl;
cout<<"资源数量之间用空格隔开"<<endl;
for(int i=0;i<N;i++){
cout<<"第"<<i+1<<"个进程：";
for(int j=0;j<M;j++)
cin>>maximum[i][j];
}
cout<<endl;
cout<<"请输入每个进程已分配的资源数："<<endl;
for(int i=0;i<N;i++){
cout<<"第"<<i+1<<"个进程：";
for(int j=0;j<M;j++)
cin>>allocate[i][j];
for(int k=0;k<M;k++)
if(allocate[i][k]>maximum[i][k]){
cout<<"第"<<k+1<<"个已分配资源超过最大资源需求数!请重新分配"<<endl;
i--;
break;
}
}
for(int i=0;i<N;i++) //need[][]初始化
for(int j=0;j<M;j++)
need[i][j]=maximum[i][j]-allocate[i][j];
};
void input(){ //输入每个进程的需求数
print();
cout<<"请输入请求资源的进程号(从1到"<<N<<"):"; //输入请求资源数
int p=-1;
cin>>p;
while(p<=0||p>N){
cout<<"进程号不存在，请重新输入:";
cin>>p;
}
cout<<endl;
cout<<"请输入每个资源的请求数量:"<<endl;
for(int i=0;i<M;i++){
cout<<"资源"<<i+1<<":";
cin>>request[i];
if(request[i]>need[p-1][i]){
cout<<"请求的资源数大于还需要的资源数，请重新请求。"<<endl;
i--;
}
else if(request[i]>available[i]){
cout<<"请求的资源数大于现有的资源数，请重新请求。"<<endl;
i--;
}
}
for(int i=0;i<M;i++){ //预分配
allocate[p-1][i]+=request[i];
need[p-1][i]-=request[i];
available[i]-=request[i];
}
for(int k=0;k<M;k++) //work初始化
work[k]=available[k];
for(int i=0;i<N;i++) //finish初始化
finish[i]=false;
print();
check(p);
};
void restore(int p){
for(int i=0;i<M;i++){
allocate[p-1][i]-=request[i];
need[p-1][i]+=request[i];
available[i]+=request[i];
}
};
void destory(){
for(int i=0;i<N;i++){
delete[] maximum[i];
delete[] allocate[i];
delete[] need[i];
}
delete[] maximum;
delete[] allocate;
delete[] need;
delete[] available;
delete[] finish;
delete[] work;
delete[] process;
delete[] request;
};
void main(){
char f=’y’;
init();
while(f==’y’||f==’Y’){
input();
cout<<endl;
cout<<"是否继续银行家算法演示？(是则输入Y或y,否则输入n或N):";
cin>>f;
}
destory();
}
随机文章：
收藏到：Del.icio.us
