首页 > 代码库 > 操作系统之银行家算法
操作系统之银行家算法
一、需求分析
1、进程的状态有：就绪，等待和完成。当系统不能满足进程的资源请求时，进程出于等待状态。资源需求总量表示进程运行过程中对资源的总的需求量。已占资源量表示进程目前已经得到但还为归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。陷入每个进程的资源需求总量不应超过系统拥有的资源总量。
2、银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。
(1)查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程，如果能，则转B）。
(2)将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。
重复第(1)步(2)步，直到所有进程都标记为终止进程，或知道一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。
二、系统结构设计
1、设计分析
当某个进程对某类资源提出请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。
2、数据结构
（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可利用资源的数目，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可利用资源的数目，其数值随该类资源的分配和回首而动态的改变，如果Available=K，则代表Rj类资源K个。
（2）最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
（3）分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
（4）需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程还需要各类资源数。
3、银行家算法
设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按照以下步骤进行检查：
A：如果Requesti[j]<=Need[i,j]，执行B，否则认为出错，因为它需要的资源数已经超过它所宣布的最大值。
B: 如果Requesti[j]<=Available[j]，转向步骤C，否则尚无足够资源，Pi必须等待。
C:系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j]:= Available[j]- Requesti[j];
Allocation[i,j]:=Allocation[i,j]+ Requesti[j];
Need[i,j]:= Need[i,j]- Requesti[j];
D:系统执行安全性算法，检查此次自奥运分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配，否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
设置WORK[R]是系统可提供给进程继续运行所需的各类资源数目, 刚开始 系统可提供给进程继续运行所需的j类资源数目,FINISH[i]检查安全性是否通过。
4、程序流程图
三、总结和体会
通过在刘玉宏老师的帮助下，我成功的完成了这次课程设计，虽然其中存在很多的不足。在这个银行家算法课程设计中，利用二维数组作为基本的数据结构用以存储资源及进程信息，利用check()函数来判断进程执行是否安全，通过二维数组和distribute ()和restore()函数很好的解决了进程的分配及撤销问题。
实验中我使用当一个进程不满足安全状态时紧接着查找它的下一个进程，若下一个进程满足则给予分配资源，然后又返回从头开始才找满足安全状态的进程，经过刘老师的课堂讲解我知道还可以按照进程的编号从小到大一次下循环查找，直到进程执行完毕。
不同的算法可以实现相同的功能，这是我从本次实验中深深体会到的，因而在今后的学习中遇到问题我会尝试着用的不同的方法来解决，有时候换个角度可以很方便的解决问题。
四、主要算法清单
#include <string.h>
#include <iostream.h>
#define FALSE 0
#define TRUE 1
#define W 10
#define R 10
int M ; //总进程数
int N ; //资源种类
int All[W];//各种资源的数目总和
int Max[W][R]; //M个进程对N类资源最大资源需求量
int Available[R]; //系统可用资源数
int Allocation[W][R]; //M个进程已经得到N类资源的资源量
int Need[W][R]; //M个进程还需要N类资源的资源量
int Request[R]; //请求资源个数
void output() //输出资源分配情况
{
int i,j;
cout<<endl<<"*************************"<<endl;
cout<<"各种资源的总数量:"<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<All[j]<<endl;
cout<<endl;
cout<<"*************************"<<endl;
cout<<"目前各种资源可利用的数量为:"<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<Available[j]<<endl;
cout<<endl<<endl;
cout<<"*************************"<<endl;
cout<<"各进程还需要的资源数量:"<<endl;
for (j=0;j<N;j++)
{ cout<<" 资源"<<j<<" "; }
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<": ";
for (j=0;j<N;j++)
cout<<Need[i][j]<<" ";;
cout<<endl;
}
cout<<endl;
cout<<"**************************"<<endl;
cout<<"各进程已经分配得到的资源量: "<<endl<<endl;
for (j=0;j<N;j++)
{ cout<<" 资源"<<j<<" "; }
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<": ";
for (j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
void distribute(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];//第k个进程对第j中资源还需要的资源量
}
}
void restore(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 check() //检查安全性
{
int WORK[R],FINISH[W];//WORK[R]是系统可提供给进程继续运行所需的各类资源数目
int i,j;
for(j=0;j<N;j++) WORK[j]=Available[j];//刚开始 系统可提供给进程继续运行所需的j类资源数目 等于j类可用资源数目
for(i=0;i<M;i++) FINISH[i]=FALSE;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(FINISH[i]==FALSE&&Need[i][j]<=WORK[j])
{
WORK[j]=WORK[i]+Allocation[i][j];
}
}
FINISH[i]=TRUE;
}
for(i=0;i<M;i++)
{
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 系统不安全! 本次资源申请不成功!!!"<<endl;
cout<<endl;
return 1;
}
else
{
cout<<endl;
cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl;
cout<<endl;
}
}
return 0;
}
void bank() //银行家算法
{
int i=0,j=0;
char flag=‘Y‘;
while(flag==‘Y‘||flag==‘y‘)
{
i=-1;
while(i<0||i>=M)
{
cout<<"***********************************"<<endl;
cout<<endl<<" 请输入需申请资源的进程号:";
cin>>i;
if(i<0||i>=M) cout<<" 输入的进程号不存在，重新输入!"<<endl;
}
for (j=0;j<N;j++)
{
cout<<" 资源"<<j<<": ";
cin>>Request[j];
if(Request[j]>Need[i][j]) //若请求的资源数大于进程还需要i类资源的资源量j
{
cout<<endl<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的数量!";
cout<<" 若继续执行系统将处于不安全状态!"<<endl;
flag=‘N‘;
break;
}
else
{
if(Request[j]>Available[j]) //若请求的资源数大于可用资源数
{
cout<<endl<<" 进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的数量!";
cout<<" 若继续执行系统将处于不安全状态!"<<endl;
flag=‘N‘;
break;
}
}
}
if(flag==‘Y‘||flag==‘y‘)
{
distribute(i); //调用change(i)函数，改变资源数
if(check()) //若系统安全
{
restore(i); //调用restore(i)函数，恢复资源数
output(); //输出资源分配情况
}
else //若系统不安全
output(); //输出资源分配情况
}
else //若flag=N||flag=n
cout<<endl;
cout<<" 是否继续银行家算法演示,按‘Y‘或‘y‘键继续,按‘N‘或‘n‘键退出演示: ";
cin>>flag;
}
}
void version()
{
cout<<endl;
cout<<"\t*************************"<<endl;
cout<<"\t* *"<<endl;
cout<<"\t* 银 行 家 算 法 *"<<endl;
cout<<"\t* *"<<endl;
cout<<"\t*************************"<<endl;
}
void main() //主函数
{
int i=0,j=0,p;
version();
cout<<endl<<"请输入总进程数:";
cin>>M;
cout<<endl<<"***************************"<<endl;
cout<<"请输入总资源种类:";
cin>>N;
cout<<endl<<"***************************"<<endl;
cout<<"请输入各类资源总数:";
for(i=0;i<N;i++)
cin>>All[i];
cout<<endl<<"***************************"<<endl;
cout<<"输入各进程所需要的各类资源的最大数量:"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>Max[i][j];
if (Max[i][j]>All[j])
cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl;
}while (Max[i][j]>All[j]);
}
}
cout<<endl<<"********************************"<<endl;
cout<<"输入各进程已经分配的各类资源的数量:"<<endl;
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>Allocation[i][j];
if (Allocation[i][j]>Max[i][j])
cout<<endl<<"占有资源超过了声明的最大资源,请重新输入"<<endl;
}while (Allocation[i][j]>Max[i][j]);
}
}
for (j=0;j<N;j++) //初始化资源数量
{
p=All[j];
for (i=0;i<M;i++)
{
p=p-Allocation[i][j];//减去已经被占据的资源
Available[j]=p;
if(Available[j]<0)
Available[j]=0;
}
}
for (i=0;i<M;i++)
for(j=0;j<N;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
output();
bank();
}