银行家算法详细流程

❶ 操作系统银行家算法

不会分配，看一下银行家算法的流程。
可以看到 在step(1)若Request<=Need, goto step(2);否则错误返回.
原因如下，每个进程开始之前，都必须声明自己需要的各类资源的最大值Max。
Need 需求资源 = Max 最大需求 - Allocation 已分配资源
进程运行过程中，不能再要比Need还多的资源。

参考书 操作系统概念(OS concepts Six Edition)

算法:
n:系统中进程的总数
m:资源类总数

符号说明:
Available 可用剩余资源
Max 最大需求
Allocation 已分配资源
Need 需求资源
Request 请求资源

当进程pi提出资源申请时, 系统执行下列
步骤:("="为赋值符号, "=="为等号)
step(1)若Request<=Need, goto step(2);否则错误返回
step(2)若Request<=Available, goto step(3);否则进程等待
step(3)假设系统分配了资源, 则有:
Available=Available-Request;
Allocation=Allocation+Request;
Need=Need-Request
若系统新状态是安全的, 则分配完成
若系统新状态是不安全的, 则恢复原状态, 进程等待
为进行安全性检查, 定义数据结构:
Work:ARRAY[1...m] of integer;
Finish:ARRAY[1...n] of Boolean;
安全性检查的步骤:
step (1):
Work=Available;
Finish=false;
step (2) 寻找满足条件的i:
a. Finish==false;
b. Need<=Work;
如果不存在, goto step(4)
step(3)
Work=Work+Allocation;
Finish=true;
goto step(2)
step (4) 若对所有i, Finish=true, 则系统处于安全状态, 否则处于不安全状态

❷ 银行家算法的算法实现

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程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(输入的进程号不存在，重新输入! );gotoenter;}err:{printf(请输入进程);printf(%d,i);printf(申请的资源数 );printf(类别:ABC );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(类资源的资源量!申请不合理，出错!请重新选择! );gotoerr;}else{if(Request[j]>AVAILABLE[j]){printf(进程);printf(%d,i);printf(申请的资源数大于系统可用);printf(%d,j);printf(类资源的资源量!申请不合理，出错!请重新选择! );gotoerr;}}}}changdata(i);if(chkerr()){rstordata(i);showdata();}elseshowdata();printf( );printf(按'y'或'Y'键继续,否则退出 );flag=getch();if(flag=='y'||flag=='Y'){gotoenter;}else{exit(0);}}/*显示数组*/voidshowdata(){inti,j;printf(系统可用资源向量: );printf(***Available*** );printf(资源类别:ABC );printf(资源数目:);for(j=0;j<N;j++){printf(%d,AVAILABLE[j]);}printf( );printf( );printf(各进程还需要的资源量: );printf(******Need****** );printf(资源类别:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(号进程:);for(j=0;j<N;j++){printf(%d,NEED[i][j]);}printf( );}printf( );printf(各进程已经得到的资源量: );printf(***Allocation*** );printf(资源类别:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(号进程:);/*printf(: );*/for(j=0;j<N;j++){printf(%d,ALLOCATION[i][j]);}printf( );}printf( );}/*系统对进程请求响应，资源向量改变*/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(系统不安全!!!本次资源申请不成功!!! );return1;}printf( );printf(经安全性检查，系统安全，本次分配成功。 );printf( );printf(本次安全序列：);for(i=0;i<M;i++)//打印安全系统的进程调用顺序{printf(进程);printf(%d,temp[i]);if(i<M-1)printf(->);}printf( );return0;}