Question

有没有人懂操作系统的银行家算法，最好有一道例题可以讲

Answer 1

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系 银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[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=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
银行家算法流程图
算法（C语言实现）
#include<STRING.H>
#include<stdio.h>
#include<stdlib.h>
#include<CONIO.H>/*用到了getch()*/
#defineM5/*进程数*/
#defineN3/*资源数*/
#defineFALSE0
#defineTRUE1
/*M个进程对N类资源最大资源需求量*/
intMAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*系统可用资源数*/
intAVAILABLE[N]={10,5,7};
/*M个进程已分配到的N类数量*/
intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};
/*M个进程已经得到N类资源的资源量*/
intNEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*M个进程还需要N类资源的资源量*/
intRequest[N]={0,0,0};
voidmain()
{
inti=0,j=0;
charflag;
voidshowdata();
voidchangdata(int);
voidrstordata(int);
intchkerr();
showdata();
enter:
{
printf("请输入需申请资源的进程号（从0到");
printf("%d",M-1);
printf("）:");
scanf("%d",&i);
}
if(i<0||i>=M)
{
printf("输入的进程号不存在，重新输入!\n");
gotoenter;
}
err:
{
printf("请输入进程");
printf("%d",i);
printf("申请的资源数\n");
printf("类别:ABC\n");
printf("");
for(j=0;j<N;j++)
{
scanf("%d",&Request[j]);
if(Request[j]>NEED[i][j])
{
printf("%d",i);
printf("号进程");
printf("申请的资源数>进程");
printf("%d",i);
printf("还需要");
printf("%d",j);
printf("类资源的资源量!申请不合理，出错!请重新选择!\n");
gotoerr;
}
else
{
if(Request[j]>AVAILABLE[j])
{
printf("进程");
printf("%d",i);
printf("申请的资源数大于系统可用");
printf("%d",j);
printf("类资源的资源量!申请不合理，出错!请重新选择!\n");
gotoerr;
}
}
}
}
changdata(i);
if(chkerr())
{
rstordata(i);
showdata();
}
else
showdata();
printf("\n");
printf("按'y'或'Y'键继续,否则退出\n");
flag=getch();
if(flag=='y'||flag=='Y')
{
gotoenter;
}
else
{
exit(0);
}
}
/*显示数组*/
voidshowdata()
{
inti,j;
printf("系统可用资源向量:\n");
printf("***Available***\n");
printf("资源类别:ABC\n");
printf("资源数目:");
for(j=0;j<N;j++)
{
printf("%d",AVAILABLE[j]);
}
printf("\n");
printf("\n");
printf("各进程还需要的资源量:\n");
printf("******Need******\n");
printf("资源类别:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("号进程:");
for(j=0;j<N;j++)
{
printf("%d",NEED[i][j]);
}
printf("\n");
}
printf("\n");
printf("各进程已经得到的资源量:\n");
printf("***Allocation***\n");
printf("资源类别:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("号进程:");
/*printf(":\n");*/
for(j=0;j<N;j++)
{
printf("%d",ALLOCATION[i][j]);
}
printf("\n");
}
printf("\n");
}
/*系统对进程请求响应，资源向量改变*/
voidchangdata(intk)
{
intj;
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];
}
}
/*资源向量改变*/
voidrstordata(intk)
{
intj;
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];
}
}
/*安全性检查函数*/
intchkerr()//在假定分配资源的情况下检查系统的安全性
{
intWORK[N],FINISH[M],temp[M];//temp[]用来记录进程安全执行的顺序
inti,j,m,k=0,count;
for(i=0;i<M;i++)
FINISH[i]=FALSE;
for(j=0;j<N;j++)
WORK[j]=AVAILABLE[j];//把可利用资源数赋给WORK[]
for(i=0;i<M;i++)
{
count=0;
for(j=0;j<N;j++)
if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])
count++;
if(count==N)//当进程各类资源都满足NEED<=WORK时
{
for(m=0;m<N;m++)
WORK[m]=WORK[m]+ALLOCATION[i][m];
FINISH[i]=TRUE;
temp[k]=i;//记录下满足条件的进程
k++;
i=-1;
}
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
printf("系统不安全!!!本次资源申请不成功!!!\n");
return1;
}
printf("\n");
printf("经安全性检查，系统安全，本次分配成功。\n");
printf("\n");
printf("本次安全序列：");
for(i=0;i<M;i++)//打印安全系统的进程调用顺序
{
printf("进程");
printf("%d",temp[i]);
if(i<M-1)
printf("->");
}
printf("\n");
return0;
}