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

廣州大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告開課學(xué)院及實(shí)驗(yàn)室：計(jì)算機(jī)科學(xué)與工程實(shí)驗(yàn)室 2015年11月29日實(shí)驗(yàn)課程名稱操作系統(tǒng)實(shí)驗(yàn)成績實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)2 銀行家算法指導(dǎo)老師一、實(shí)驗(yàn)?zāi)康?理解銀行家算法。.掌握進(jìn)程安全性檢查的方法及資源分配的方法。.加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念。.體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。二、實(shí)驗(yàn)內(nèi)容(1)設(shè)計(jì)進(jìn)程對(duì)各類資源最大申請(qǐng)表示及初值確定。(2)設(shè)定系統(tǒng)提供資源初始狀況。(3)設(shè)定每次某個(gè)進(jìn)程對(duì)各類資源的申請(qǐng)表示。(4)編制程序，依據(jù)銀行家算法，決定其申請(qǐng)是否得到滿足。三、實(shí)驗(yàn)原理整體流程：從文件中讀也數(shù)據(jù)二判斷系統(tǒng)是否是安?.詁求資二J前斷系統(tǒng)是否分配資源資源否結(jié)束 算法設(shè)計(jì)：n：系統(tǒng)中進(jìn)程的總數(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;符號(hào)說明：Available可用剩余資源Max最大需求Allocation已分配資源Need需求資源Request請(qǐng)求資源當(dāng)進(jìn)程pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟：（“二”為賦值符號(hào)，“二二”為等號(hào)）step（1）若Request<=Need,gotostep（2）；否則錯(cuò)誤返回step（2）若Request<=Available,gotostep（3）；否則進(jìn)程等待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)，進(jìn)程等待為進(jìn)行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：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)若對(duì)所有i,Finish=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)四、實(shí)驗(yàn)設(shè)備卬57下虛擬機(jī)VMware-workstation-11.0.0及CentOS-5.8-i386五、實(shí)驗(yàn)要求.輸入系統(tǒng)進(jìn)程數(shù)量n和資源類型數(shù)量m。.輸入每類資源的數(shù)量。.輸入每個(gè)進(jìn)程每類資源的最大需求量和已獲資源量。檢驗(yàn)系統(tǒng)的安全系。六、實(shí)驗(yàn)程序#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("請(qǐng)輸入系統(tǒng)資源的種類數(shù):")；scanf("%d",&colum);printf("請(qǐng)輸入現(xiàn)時(shí)內(nèi)存中的進(jìn)程數(shù):")；scanf("%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+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("請(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+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("請(qǐng)輸入現(xiàn)時(shí)系統(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;}七、總結(jié)心得（一）實(shí)驗(yàn)分析設(shè)系統(tǒng)中有三種類型的資源（A、B、C）和五個(gè)進(jìn)程（P1、P2、P3、P4、P5）,A資源的數(shù)量為17,B資源的數(shù)量為5,C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)如下表所求。迸程跟大資源需要量已分配資源數(shù)量系統(tǒng)剩余資源數(shù)量ABCABCABCP155g2122 3 3P2536402P34011405P4425204P5424314請(qǐng)輸入系統(tǒng)資源的種類數(shù)：3請(qǐng)輸入現(xiàn)時(shí)內(nèi)存中的進(jìn)程數(shù)二5清瑜入己分配諼源矩陣：請(qǐng)輸入已分配給進(jìn)程pl的A種系統(tǒng)資源二N清鋪人已分配給進(jìn)程pl的B種系統(tǒng)資源"請(qǐng)輸入已分配給進(jìn)程pl的C種系統(tǒng)資源;2請(qǐng)輸入已分配給進(jìn)程P2的A種系統(tǒng)資源請(qǐng)福人已分配冷迸程P2的B種系統(tǒng)資源：3請(qǐng)播入巴分配給進(jìn)程P2的C種系統(tǒng)資堰二包請(qǐng)輸入已分配給進(jìn)程P3的A種系統(tǒng)資源請(qǐng)輸入已分配給進(jìn)程P3的5種系統(tǒng)資源;9請(qǐng)輸入已分配給進(jìn)程P3的C種系統(tǒng)資源”請(qǐng)輸入已分配給進(jìn)程p4的A種系統(tǒng)資源：2請(qǐng)輸入已分配給進(jìn)程P4的B種系統(tǒng)資源二。清輸入己分配給進(jìn)程P4的C種系統(tǒng)資源：4諳輸入已分配給進(jìn)程P5的A種系統(tǒng)資源：3清輸入已分配給進(jìn)程psPS的8種系統(tǒng)資源門請(qǐng)輸入已分配給進(jìn)程的C種系統(tǒng)資源請(qǐng)輸入最大急求矩陣:請(qǐng)