操作系統(tǒng)-銀行家算法

廣州大學學生實驗報告開課學院及實驗室：計算機科學與工程實驗室 2015年11月29日實驗課程名稱操作系統(tǒng)實驗成績實驗項目名稱實驗2 銀行家算法指導老師一、實驗目的.理解銀行家算法。.掌握進程安全性檢查的方法及資源分配的方法。.加深了解有關資源申請、避免死鎖等概念。.體會和了解死鎖和避免死鎖的具體實施方法。二、實驗內容(1)設計進程對各類資源最大申請表示及初值確定。(2)設定系統(tǒng)提供資源初始狀況。(3)設定每次某個進程對各類資源的申請表示。(4)編制程序，依據(jù)銀行家算法，決定其申請是否得到滿足。三、實驗原理整體流程：從文件中讀也數(shù)據(jù)二判斷系統(tǒng)是否是安?.詁求資二J前斷系統(tǒng)是否分配資源資源否結束 算法設計：n：系統(tǒng)中進程的總數(shù)m：資源類總數(shù)Available:ARRAY[1..m]ofinteger;Max:ARRAY[1..n,1..m]ofinteger;Allocation:ARRAY[1..n,1..m]ofinteger;Need:ARRAY[1..n,1..m]ofinteger;Request:ARRAY[1..n,1..m]ofinteger;符號說明：Available可用剩余資源Max最大需求Allocation已分配資源Need需求資源Request請求資源當進程pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：（“二”為賦值符號，“二二”為等號）step（1）若Request<=Need,gotostep（2）；否則錯誤返回step（2）若Request<=Available,gotostep（3）；否則進程等待step(3)假設系統(tǒng)分配了資源，則有：Available二Available-Request;Allocation二Allocation+Request;Need=Need-Request若系統(tǒng)新狀態(tài)是安全的，則分配完成若系統(tǒng)新狀態(tài)是不安全的，則恢復原狀態(tài)，進程等待為進行安全性檢查，定義數(shù)據(jù)結構：Work:ARRAY[1..m]ofinteger;Finish:ARRAY[1..n]ofBoolean;安全性檢查的步驟：step(1):Work=Available;Finish=false;step(2)尋找滿足條件的i：a.Finish==false;b.Need<=Work;如果不存在，gotostep(4)step(3)Work=Work+Allocation;Finish=true;gotostep(2)step(4)若對所有i,Finish=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)四、實驗設備卬57下虛擬機VMware-workstation-11.0.0及CentOS-5.8-i386五、實驗要求.輸入系統(tǒng)進程數(shù)量n和資源類型數(shù)量m。.輸入每類資源的數(shù)量。.輸入每個進程每類資源的最大需求量和已獲資源量。檢驗系統(tǒng)的安全系。六、實驗程序#include"malloc.h"#include"stdio.h"#include"stdlib.h"#definealloclensizeof(structallocation)#definemaxlensizeof(structmax)#defineavalensizeof(structavailable)#defineneedlensizeof(structneed)#definefinilensizeof(structfinish)#definepathlensizeof(structpath)structallocation{intvalue;structallocation*next;);structmax{intvalue;structmax*next;)；structavailable/*可用資源數(shù)*/{intvalue;structavailable*next;);structneed/*需求資源數(shù)*/{intvalue;structneed*next;);structpath{intvalue;structpath*next;);structfinish{intstat;structfinish*next;);intmain(){introw,colum,status=0,i,j,t,temp,processtest;structallocation*allochead,*alloc1,*alloc2,*alloctemp;structmax*maxhead,*maxium1,*maxium2,*maxtemp;structavailable*avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1;structneed*needhead,*need1,*need2,*needtemp;structfinish*finihead,*finish1,*finish2,*finishtemp;structpath*pathhead,*path1,*path2;printf("請輸入系統(tǒng)資源的種類數(shù):")；scanf("%d",&colum);printf("請輸入現(xiàn)時內存中的進程數(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+1,'A'+j);if(status==0){ allochead二alloc1二alloc2=(structallocation*)malloc(alloclen);alloc1->next=alloc2->next=NULL;scanf("%d",&allochead->value);status++;else{alloc2=(structallocation*)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系統(tǒng)資源最大需求:"，i+1,'A'+j);if(status==0){ maxhead二maxium1二maxium2=(structmax*)malloc(maxlen);maxium1->next=maxium2->next=NULL;scanf("%d",&maxium1->value);status++;)else{maxium2=(structmax*)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;j<colum;j++){printf("種類%c的系統(tǒng)資源剩余:"，’A'+j);if(status==0){ avahead二available1二available2=(structavailable*)malloc(avalen);workhead=work1=work2=(structavailable*)malloc(avalen);available1->next=available2->next=NULL;work1->next=work2->next=NULL;scanf("%d",&available1->value);work1->value=available1->value;status++;)else{available2=(structavailable*)malloc(avalen);work2=(structavailable*)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=(structneed*)malloc(needlen);need1->next=need2->next=NULL;need1->value=maxtemp->value-alloctemp->value;status++;)else{need2=(structneed*)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=(structfinish*)malloc(finilen);finish1->next=finish2->next=NULL;finish1->stat=0;status++;)else{finish2=(structfinish*)malloc(finilen);finish2->stat=0;if(status==1){finihead->next=finish2;status++;)finish1->next=finish2;finish1=finish2;})finish2->next=NULL;/*Initializationcompleated*/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;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=(structpath*)malloc(pathlen);path1->next=path2->next=NULL;path1->value=i;status++;)else{path2=(structpath*)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;})elsefor(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系統(tǒng)處于非安全狀態(tài)!\n");exit(0);}finishtemp=finishtemp->next;}printf("\n系統(tǒng)處于安全狀態(tài).\n");printf（"安全序列為：\n"）;do{printf（"p%d",pathhead->value+1）;）while（pathhead=pathhead->next）;printf（"\n"）;return0;}七、總結心得（一）實驗分析設系統(tǒng)中有三種類型的資源（A、B、C）和五個進程（P1、P2、P3、P4、P5）,A資源的數(shù)量為17,B資源的數(shù)量為5,C資源的數(shù)量為20。在T0時刻系統(tǒng)狀態(tài)如下表所求。迸程跟大資源需要量已分配資源數(shù)量系統(tǒng)剩余資源數(shù)量ABCABCABCP155g2122 3 3P2536402P34011405P4425204P5424314請輸入系統(tǒng)資源的種類數(shù)：3請輸入現(xiàn)時內存中的進程數(shù)二5清瑜入己分配諼源矩陣：請輸入已分配給進程pl的A種系統(tǒng)資源二N清鋪人已分配給進程pl的B種系統(tǒng)資源"請輸入已分配給進程pl的C種系統(tǒng)資源;2請輸入已分配給進程P2的A種系統(tǒng)資源請福人已分配冷迸程P2的B種系統(tǒng)資源：3請播入巴分配給進程P2的C種系統(tǒng)資堰二包請輸入已分配給進程P3的A種系統(tǒng)資源請輸入已分配給進程P3的5種系統(tǒng)資源;9請輸入已分配給進程P3的C種系統(tǒng)資源”請輸入已分配給進程p4的A種系統(tǒng)資源：2請輸入已分配給進程P4的B種系統(tǒng)資源二。清輸入己分配給進程P4的C種系統(tǒng)資源：4諳輸入已分配給進程P5的A種系統(tǒng)資源：3清輸入已分配給進程psPS的8種系統(tǒng)資源門請輸入已分配給進程的C種系統(tǒng)資源請輸入最大急求矩陣:請