c实现银行家算法

1、银行家算法银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn,则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1 ,，Pn是安全的，如果对于每一个进程Pi(1 < i买n它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求

2、分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程 对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满 足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。算法：n：系统中进程的总数m :资源类总数Available: ARRAY1.m of integer;Max: ARRAY1.n,

3、1.m of integer;Allocation: ARRAY1.n,1.m of integer;Need: ARRAY1.n,1.m of integer;Request: ARRAY1.n,1.m of integer;符号说明：Available可用剩余资源Max最大需求Allocati on 已分配资源Need需求资源Request 请求资源当进程pi提出资源申请时，系统执行下列步骤：(“为赋值符号，“=为等号)step (1 )若 Request<=Need, goto step (2);否则错误返回step (2)若 Request<=Available, goto

4、 step(3);否则进程等待step (3)假设系统分配了资源，则有：Available=Available-Request;Allocati on=Allocatio n+Request;Need=Need-Request若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待为进行安全性检查，定义数据结构：Work:ARRAY1.m of in teger;Fi nish:ARRAY1. n of Boolea n;安全性检查的步骤：step ：Work=Available;Fini sh=false;step寻找满足条件的i：a. Fini sh=false;b.

5、 Need<=Work;如果不存在，goto step(4)step(3)Work=Work+Allocatio n;Fini sh=true;goto step(2)step (4)若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态/*银行家算法，操作系统概念(OS concepts Six Edition)reedit by Johnny hagen， SCAU，run at vc6.0*/#i nclude "malloc.h"#i nclude "stdio.h"#i nclude "stdlib.h&qu

6、ot;#define alloclen sizeof(struct allocation)#define maxlen sizeof(struct max)#defi ne avale n sizeof(struct available)#defi ne n eedle n sizeof(struct n eed)#defi ne fin ile n sizeof(struct fini sh)#defi ne pathle n sizeof(struct path)struct allocati onint value;struct allocati on *n ext;struct max

7、int value;struct max *n ext;struct available /* 可用资源数 */int value;struct available *n ext;struct need /*需求资源数*/int value;struct n eed *n ext;；struct pathint value;struct path *n ext;；struct finishint stat;struct finish *n ext;int mai n()int row,colum,status=0,i,j,t,temp,processtest;struct allocati o

8、n *allochead,*alloc1,*alloc2,*alloctemp;struct max *maxhead,*maxium1,*maxium2,*maxtemp;struct available*avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1;struct n eed *n eedhead,* need1,* need2,* needtemp;struct finish *finihead,*finish1,*finish2,*finishtemp;struct path *p

9、athhead,*path1,*path2;printf("n请输入系统资源的种类数:");scan f("%d",&colum);printf("请输入现时内存中的进程数：”)；scan f("%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)all

10、ochead=alloc1=alloc2=(struct allocatio n*)malloc(allocle n);alloc1-> next=alloc2-> next=NULL;scan f("%d",&allochead->value);status+;elsealloc2=(struct allocati on *)malloc(allocle n);scan f("%d,%d", &alloc2->value);if(status=1)allochead->n ext=alloc2;status

11、+;alloc1- >n ext=alloc2;alloc仁alloc2;alloc2-> next=NULL;status=0;printf(”请输入最大需求矩阵:n");for(i=0;i<row;i+)for (j=O;j<colum;j+)printf("请输入进程p%d种类%c系统资源最大需求：",i,'A'+j);if(status=0)maxhead=maxium1=maxium2=(struct max*)malloc(maxle n);maxium1- >n ext=maxium2->n ext

12、=NULL;scan f("%d",&maxium1->value);status+;elsemaxium2=(struct max *)malloc(maxle n);scan f("%d,%d", &maxium2->value);if(status=1)maxhead->n ext=maxium2;status+;maxium1- >n ext=maxium2;maxium1=maxium2;maxium2-> next=NULL;status=O;printf(”请输入现时系统剩余的资源矩阵：n&qu

13、ot;);for (j=0;j<colum;j+)printf(”种类%c的系统资源剩余:",'A'+j);if(status=0)avahead=available仁available2=(struct available*)malloc(avale n); workhead=work仁work2=(struct available*)malloc(avale n); available>n ext=available2->n ext=NULL;work1- >n ext=work2->n ext=NULL;scan f("%

14、d",&available1->value);work1->value=available1->value;status+;elseavailable2=(struct available*)malloc(avale n); work2=(struct available*)malloc(avale n);scan f("%d,%d", &available2->value);work2->value=available2->value;if(status=1)avahead->n ext=availabl

15、e2;workhead->n ext=work2;status+;available>n ext=available2;available仁available2;work1- >n ext=work2;work仁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=O)n eedhead=need仁 need2=(struct n

16、 eed*)malloc( needle n);n eedl- >n ext=n eed2->n ext=NULL;n eed1->value=maxtemp->value-alloctemp->value; status+;elsen eed2=(struct n eed *)malloc( needle n);n eed2->value=(maxtemp->value)-(alloctemp->value);if(status=1)n eedhead->n ext=n eed2;status+;n eed1- >n ext=n e

17、ed2;need仁need2;maxtemp=maxtemp-> next;alloctemp=alloctemp->n ext;need2-> next=NULL;status=0;for(i=0;i<row;i+)if(status=0)fin ihead=fi ni sh1=fi ni sh2=(struct fini sh*)malloc(fi nile n);fin ish1-> next=fi nish2-> next=NULL;fini sh1->stat=0;status+;elsefini sh2=(struct fini sh*)m

18、alloc(fi nile n);fin ish2->stat=0;if(status=1)fin ihead->n ext=fi ni sh2;status+;fini sh1- >n ext=fi ni sh2;fini sh1=fi ni sh2;finish2->next=NULL; /*lnitialization compleated*/status=0;processtest=0;for(temp=0;temp<row;temp+)alloctemp=allochead;n eedtemp=n eedhead;fini shtemp=fi nihea

19、d;worktemp=workhead;for(i=0;i<row;i+)worktemp1=worktemp;if(fini shtemp->stat=0)for(j=0;j<colum;j+, needtemp=n eedtemp-next,worktemp=worktemp-> next)if(n eedtemp->value<=worktemp->value)processtest+;if(processtest=colum)for(j=0;j<colum;j+)worktemp1->value+=alloctemp->value;worktemp1=worktemp1- >n ext;alloctemp=alloctemp->n ext;if(status=0)pathhead=path1=path2=(struct path*)malloc(pathle n);path1-> next=path2-> next=NULL;path1->value=i;status+;elsepath2=(struct path*)malloc(pathle n);path2->value=i;if(status=1)pathh