c實(shí)現(xiàn)銀行家算法

1、銀行家算法銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn,則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒(méi)有死鎖發(fā)生。不安全狀態(tài)：不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？安全序列：一個(gè)進(jìn)程序列P1 ,，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1 < i買(mǎi)n它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求

2、分配資源相當(dāng)于用戶(hù)向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿(mǎn)足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程 對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿(mǎn) 足該進(jìn)程尚需的最大資源量，若能滿(mǎn)足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。算法：n：系統(tǒng)中進(jìn)程的總數(shù)m :資源類(lèi)總數(shù)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;符號(hào)說(shuō)明：Available可用剩余資源Max最大需求Allocati on 已分配資源Need需求資源Request 請(qǐng)求資源當(dāng)進(jìn)程pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟：(“為賦值符號(hào)，“=為等號(hào))step (1 )若 Request<=Need, goto step (2);否則錯(cuò)誤返回step (2)若 Request<=Available, goto

4、 step(3);否則進(jìn)程等待step (3)假設(shè)系統(tǒng)分配了資源，則有：Available=Available-Request;Allocati on=Allocatio n+Request;Need=Need-Request若系統(tǒng)新?tīng)顟B(tài)是安全的，則分配完成若系統(tǒng)新?tīng)顟B(tài)是不安全的，則恢復(fù)原狀態(tài)，進(jìn)程等待為進(jìn)行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：Work:ARRAY1.m of in teger;Fi nish:ARRAY1. n of Boolea n;安全性檢查的步驟：step ：Work=Available;Fini sh=false;step尋找滿(mǎn)足條件的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)若對(duì)所有i,Finish=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)/*銀行家算法，操作系統(tǒng)概念(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 /* 可用資源數(shù) */int value;struct available *n ext;struct need /*需求資源數(shù)*/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請(qǐng)輸入系統(tǒng)資源的種類(lèi)數(shù):");scan f("%d",&colum);printf("請(qǐng)輸入現(xiàn)時(shí)內(nèi)存中的進(jìn)程數(shù)：”)；scan f("%d",&row);printf("請(qǐng)輸入已分配資源矩陣:n");for(i=0;i<row;i+)for (j=0;j<colum;j+)printf("請(qǐng)輸入已分配給進(jìn)程p%d的%c種系統(tǒng)資源:",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(”請(qǐng)輸入最大需求矩陣:n");for(i=0;i<row;i+)for (j=O;j<colum;j+)printf("請(qǐng)輸入進(jìn)程p%d種類(lèi)%c系統(tǒng)資源最大需求：",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(”請(qǐng)輸入現(xiàn)時(shí)系統(tǒng)剩余的資源矩陣：n&qu

13、ot;);for (j=0;j<colum;j+)printf(”種類(lèi)%c的系統(tǒng)資源剩余:",'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