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

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

2、，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源， 當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時， 先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。算法：n ：系統(tǒng)中進程的總數(shù)m ：資源類總數(shù)Available: ARRAY1.m of integer;Max

3、: ARRAY1.n,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最大需求Allocation已分配資源Need需求資源Request請求資源當進程 pi 提出資源申請時，系統(tǒng)執(zhí)行下列步驟：( “ =為”賦值符號， “ =為”等號)step （ 1）若Request<=Need, goto step（ 2）；否則錯誤返回step （ 2）若Request<

4、=Available, goto step（3）；否則進程等待step （ 3）假設(shè)系統(tǒng)分配了資源，則有：Available=Available-Request;Allocation=Allocation+Request;Need=Need-Request若系統(tǒng)新狀態(tài)是安全的，則分配完成若系統(tǒng)新狀態(tài)是不安全的，則恢復(fù)原狀態(tài)，進程等待為進行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;安全性檢查的步驟：step (1):Work=Available;Finish=false;step (2)尋找滿足條件的i：a.

5、Finish=false;b.Need<=Work;如果不存在，goto step(4)step(3)Work=Work+Allocation;Finish=true;goto step(2)step (4)若對所有i,Finish=true, 則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)/* 銀行家算法，操作系統(tǒng)概念(OS concepts Six Edition)reedit by Johnny hagen， SCAU ，run at vc6.0*/#include "malloc.h"#include "stdio.h"#include "

6、;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 allocationint value;struct allocation *next;struct maxint

7、 value;struct max *next;struct available /*可用資源數(shù) */int value;struct available *next;struct need /*需求資源數(shù) */int value;struct need *next;struct pathint value;struct path *next;struct finishint stat;struct finish *next;int main()int row,colum,status=0,i,j,t,temp,processtest;struct allocation *allochead,

8、*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,*p

9、ath2;printf("n請輸入系統(tǒng)資源的種類數(shù):");scanf("%d",&colum);printf(" 請輸入現(xiàn)時內(nèi)存中的進程數(shù):");scanf("%d",&row);printf(" 請輸入已分配資源矩陣:n");for(i=0;i<row;i+)for (j=0;j<colum;j+)printf(" 請輸入已分配給進程p%d的 %c 種系統(tǒng)資源 :",i,'A'+j);if(status=0)allochead=a

10、lloc1=alloc2=(struct allocation*)malloc(alloclen);alloc1->next=alloc2->next=NULL;scanf("%d",&allochead->value);status+;elsealloc2=(struct allocation *)malloc(alloclen);scanf("%d,%d",&alloc2->value);if(status=1)allochead->next=alloc2;status+;alloc1->next=

11、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 系統(tǒng)資源最大需求 :",i,'A'+j); if(status=0)maxhead=maxium1=maxium2=(struct max*)malloc(maxlen);maxium1->next=maxium2->next=NULL;scanf

12、("%d",&maxium1->value);status+;elsemaxium2=(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(" 請輸入現(xiàn)時系統(tǒng)剩余的資源矩陣:n");for (j=0

13、;j<colum;j+)printf(" 種類%c 的系統(tǒng)資源剩余:",'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",&

14、;available1->value);work1->value=available1->value;status+;elseavailable2=(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->ne

15、xt=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);n

16、eed1->next=need2->next=NULL;need1->value=maxtemp->value-alloctemp->value;status+;elseneed2=(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;all

17、octemp=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+;elsefinish2=(struct finish*)malloc(finilen);finish2->stat=0;if(status=1)finihead->ne

18、xt=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->sta

19、t=0)for(j=0;j<colum;j+,needtemp=needtemp->next,worktemp=worktemp->next)if(needtemp->value<=worktemp->value)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+;elsepath2=(struct path*)malloc(pathlen);path2->value=i;if(status