免死锁的算法。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。
那么什么是安全序列呢？
安全序列：一个进程序列是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
银行家算法：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
算法：
n：系统中进程的总数
m：资源类总数
Available: ARRAY[1..m] of integer;
Max: ARRAY[1..n,1..m] of integer;
Allocation: ARRAY[1..n,1..m] of integer;
Need: ARRAY[1..n,1..m] of integer;
Request: ARRAY[1..n,1..m] of integer;
符号说明：
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,则系统处于安全状态，否则处于不安全状态
/* 银行家算法，操作系统概念(OS concepts Six Edition)
reedit by Johnny hagen，SCAU，run at vc6.0
*/
#include "malloc.h"
#include "stdio.h"
#include "stdlib.h"
#define alloclen sizeof(struct allocation)
#define maxlen sizeof(struct max)
#define avalen sizeof(struct available)
#define needlen sizeof(struct need)
#define finilen sizeof(struct finish)
#define pathlen sizeof(struct path)
struct allocation
{
int value;
struct allocation *next;
};
struct max
{
int value;
struct max *next;
};
struct available /*可用资源数*/
{
int value;
struct available *next;
};
struct need /*需求资源数*/
{
int value;
struct need *next;
};
struct path
{
int value;
struct path *next;
};
struct finish
{
int stat;
struct finish *next;
};
int main()
{
int row,colum,status=0,i,j,t,temp,processtest;
struct allocation *allochead,*alloc1,*alloc2,*alloctemp;
struct max *maxhead,*maxium1,*maxium2,*maxtemp;
struct available *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1;
struct need *needhead,*need1,*need2,*needtemp;
struct finish *finihead,*finish1,*finish2,*finishtemp;
struct path *pathhead,*path1,*path2;
printf("\n请输入系统资源的种类数:");
scanf("%d",&colum);
printf("请输入现时内存中的进程数:");
scanf("%d",&row);
printf("请输入已分配资源矩阵:\n");
for(i=0;i<row;i++)
{
for (j=0;j<colum;j++)
{
printf("请输入已分配给进程 p%d 的 %c 种系统资源:",i,'A'+j);
if(status==0)
{
allochead=alloc1=alloc2=(struct allocation*)malloc(alloclen);
alloc1->next=alloc2->next=NULL;
scanf("%d",&allochead->value);
status++;
}
else
{
alloc2=(struct allocation *)malloc(alloclen);
scanf("%d,%d",&alloc2->value);
if(status==1)
{
allochead->next=alloc2;
status++;
}
alloc1->next=alloc2;
alloc1=alloc2;
}
}
}
alloc2->next=NULL;
status=0;
printf("请输入最大需求矩阵:\n");
for(i=0;i<row;i++)
{
for (j=0;j<colum;j++)
{
printf("请输入进程 p%d 种类 %c 系统资源最大需求:",i,'A'+j);
if(status==0)
{
maxhead=maxium1=maxium2=(struct max*)malloc(maxlen);
maxium1->next=maxium2->next=NULL;
scanf("%d",&maxium1->value);
status++;
}
else
{
maxium2=(struct max *)malloc(maxlen);
scanf("%d,%d",&maxium2->value);
if(status==1)
{
maxhead->next=maxium2;
status++;
}
maxium1->next=maxium2;
maxium1=maxium2;
}
}
}
maxium2->next=NULL;
status=0;
printf("请输入现时系统剩余的资源矩阵:\n");
for (j=0;j<colum;j++)
{
printf("种类 %c 的系统资源剩余:",'A'+j);
if(status==0)
{
avahead=available1=available2=(struct available*)malloc(avalen);
workhead=work1=work2=(struct available*)malloc(avalen);
available1->next=available2->next=NULL;
work1->next=work2->next=NULL;
scanf("%d",&available1->value);
work1->value=available1->value;
status++;
}
else
{
available2=(struct available*)malloc(avalen);
work2=(struct available*)malloc(avalen);
scanf("%d,%d",&available2->value);
work2->value=available2->value;
if(status==1)
{
avahead->next=available2;
workhead->next=work2;
status++;
}
available1->next=available2;
available1=available2;
work1->next=work2;
work1=work2;
}
}
available2->next=NULL;
work2->next=NULL;
status=0;
alloctemp=allochead;
maxtemp=maxhead;
for(i=0;i<row;i++)
for (j=0;j<colum;j++)
{
if(status==0)
{
needhead=need1=need2=(struct need*)malloc(needlen);
need1->next=need2->next=NULL;
need1->value=maxtemp->value-alloctemp->value;
status++;
}
else
{
need2=(struct need *)malloc(needlen);
need2->value=(maxtemp->value)-(alloctemp->value);
if(status==1)
{
needhead->next=need2;
status++;
}
need1->next=need2;
need1=need2;
}
maxtemp=maxtemp->next;
alloctemp=alloctemp->next;
}
need2->next=NULL;
status=0;
for(i=0;i<row;i++)
{
if(status==0)
{
finihead=finish1=finish2=(struct finish*)malloc(finilen);
finish1->next=finish2->next=NULL;
finish1->stat=0;
status++;
}
else
{
finish2=(struct finish*)malloc(finilen);
finish2->stat=0;
if(status==1)
{
finihead->next=finish2;
status++;
}
finish1->next=finish2;
finish1=finish2;
}
}
finish2->next=NULL; /*Initialization compleated*/
status=0;
processtest=0;
for(temp=0;temp<row;temp++)
{
alloctemp=allochead;
needtemp=needhead;
finishtemp=finihead;
worktemp=workhead;
for(i=0;i<row;i++)
{
worktemp1=worktemp;
if(finishtemp->stat==0)
{
for(j=0;jnext,worktemp=worktemp->next)
if(needtemp->valuevalue)
processtest++;
if(processtest==colum)
{
for(j=0;j<colum;j++)
{
worktemp1->value+=alloctemp->value;
worktemp1=worktemp1->next;
alloctemp=alloctemp->next;
}
if(status==0)
{
pathhead=path1=path2=(struct path*)malloc(pathlen);
path1->next=path2->next=NULL;
path1->value=i;
status++;
}
else
{
path2=(struct path*)malloc(pathlen);
path2->value=i;
if(status==1)
{
pathhead->next=path2;
status++;
}
path1->next=path2;
path1=path2;
}
finishtemp->stat=1;
}
else
{
for(t=0;t<colum;t++)
alloctemp=alloctemp->next;
finishtemp->stat=0;
}
}
else
for(t=0;t<colum;t++)
{
needtemp=needtemp->next;
alloctemp=alloctemp->next;
}
processtest=0;
worktemp=workhead;
finishtemp=finishtemp->next;
}
}
path2->next=NULL;
finishtemp=finihead;
for(temp=0;temp<row;temp++)
{
if(finishtemp->stat==0)
{
printf("\n系统处于非安全状态!\n");
exit(0);
}
finishtemp=finishtemp->next;
}
printf("\n系统处于安全状态.\n");
printf("\n安全序列为: \n");
do
{
printf("p%d ",pathhead->value);
}
while(pathhead=pathhead->next);
printf("\n");
return 0;
}
另外,站长团上有产品团购,便宜有保证
银行家算法程序代码
#include
#include
#include
#define FALSE 0
#define TRUE 1
#define W 10
#define R 10
int M ; // 总进程数
int N ; // 资源种类
int ALL_RESOURCE[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_RESOURCE[j];
cout<<endl;
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"目前各种资源可利用的数量为:"<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<AVAILABLE[j];
cout<<endl;
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"各进程还需要的资源数量:"<<endl<<endl;
for(i=0;i<N;i++)
cout<<" 资源"<<i;
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(i=0;i<N;i++)
cout<<" 资源"<<i;
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];
}
}
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];
int i,j;
for(j=0;j<N;j++) WORK[j]=AVAILABLE[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=M)
{
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<endl<<" 请输入需申请资源的进程号:";
cin>>i;
if(i=M) cout<<" 输入的进程号不存在，重新输入!"<<endl;
}
cout<<" 请输入进程"<<i<<"申请各类资源的数量:"<<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;
}
void main() // 主函数
{
int i=0,j=0,p;
version();
getchar();
cout<<endl<<"请输入总进程数:";
cin>>M;
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"请输入总资源种类:";
cin>>N;
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"请输入各类资源总数:(需要输入数为"<<N<<"个)";
for(i=0;i<N;i++)
cin>>ALL_RESOURCE[i];
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"输入各进程所需要的各类资源的最大数量:(需要输入数为"<<M*N<<"个)";
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>MAX[i][j];
if (MAX[i][j]>ALL_RESOURCE[j])
cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl;
}
while (MAX[i][j]>ALL_RESOURCE[j]);
}
}
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"输入各进程已经占据的各类资源的数量:(需要输入数为"<<M
*N<<"个)";
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_RESOURCE[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();
}
实验结果分析
1.根据下面给出的系统中资源分配情况，以及各个进程的资源申请情况，通过银行家算法来判断各进程的资源请求能否满足（要求记录程序的运行过程）。
已分配的资源最大需求量
A BCABC
P1 0 10753
P2 2 00322
P3 3 02902
P4 2 11222
P5 0 02433
剩余资源ABC
33 2
