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

PAGEPAGE4實驗三死鎖

一、實驗題目設計一個n個并發(fā)進程共享m個系統(tǒng)資源的系統(tǒng)。進程可動態(tài)申請資源和釋放資源，系統(tǒng)按各進程的申請動態(tài)的分配資源。要求采用銀行家算法防止死鎖。二、實驗目的死鎖會引起計算機工作僵死，造成整個系統(tǒng)癱瘓。因此，死鎖現象是操作系統(tǒng)特別是大型系統(tǒng)中必須設法防止的。通過本次實驗，使學生掌握死鎖的概念和產生死鎖的原因和必要條件，預防和避免死鎖的方法，死鎖的檢測與解除。通過本次實驗，使學生加深了對死鎖概念的理解和掌握，深刻領會銀行家算法的實質及實現過程。三、設計思想（本程序中的用到的所有數據類型的定義，主程序的流程圖及各程序模塊之間的調用關系）程序流程圖安全（safe）函數框圖如下：2．邏輯設計用結構體數組表示3個進程，其中包括使用數組形式的線性表表示某個進程申請資源的列表（隊列），以及進程需要的總資源數、進程當前已經運行到的位置等信息。模擬分配的程序部分，采用循環(huán)隊列對各進程進行調度。3、物理設計全局變量的結構定義如下：boolavoid;structinfo//進程信息{longtot,n;//最大占用資源,申請次數longlist[16];//申請資源列表longpre[16];//已占用資源數longp;//已分配狀況的指針}pro[4];longLeftRes;程序的結構定義如下：intmain()//主函數{init();allot();}voidinit()//函數功能:輸入和初始化voidallot()//函數功能:模擬資源分配過程allot()使用以下函數模擬分配過程：boolrequire(longx)//函數功能:嘗試分配資源給進程xboolsafe(longx)//函數功能:檢查分配是否安全可以處理3種資源的程序全局變量結構如下：//共有3種資源，3個進程boolavoid;structinfo//進程信息{longtot[4];//最大占用資源數longp[4];//已經占有的資源數}pro[5];longLeftRes[4];//剩余資源數longqu[4];四、測試結果對于一組會導致死鎖的數據，分別選擇采用和不采用避免算法，結果如下：Avoiddeadlock?(Y/N)YPleaseinputtheresourse-requirelistsofthese3processes,onelistsinaline:23423331=================================================================Process1:234(Sum=9)Process2:233(Sum=8)Process3:31(Sum=4)=================================================================Process1require2unit(s)resourseSuccess!LeftResourse=8Process2require2unit(s)resourseSuccess!LeftResourse=6Process3require3unit(s)resourseSuccess!LeftResourse=3Process1require3unit(s)resourseDenied!NotsafeProcess2require3unit(s)resourseDenied!NotsafeProcess3require1unit(s)resourseSuccess!LeftResourse=2Process3finish.LeftResourse=6Process1require3unit(s)resourseDenied!NotsafeProcess2require3unit(s)resourseSuccess!LeftResourse=3Process1require3unit(s)resourseDenied!NotsafeProcess2require3unit(s)resourseSuccess!LeftResourse=0Process2finish.LeftResourse=8Process1require3unit(s)resourseSuccess!LeftResourse=5Process1require4unit(s)resourseSuccess!LeftResourse=1Process1finish.LeftResourse=10Finish如果不避免死鎖：Avoiddeadlock?(Y/N)NPleaseinputtheresourse-requirelistsofthese3processes,onelistsinaline:23423331=================================================================Process1:234(Sum=9)Process2:233(Sum=8)Process3:31(Sum=4)=================================================================Process1require2unit(s)resourseSuccess!LeftResourse=8Process2require2unit(s)resourseSuccess!LeftResourse=6Process3require3unit(s)resourseSuccess!LeftResourse=3Process1require3unit(s)resourseSuccess!LeftResourse=0Process2require3unit(s)resourseDenied!NoenoughresourseProcess3require1unit(s)resourseDenied!NoenoughresourseProcess1require4unit(s)resourseDenied!NoenoughresourseAlreadyDeadlockFinish改進版本（可以使用3種資源的程序）測試結果如下：五、系統(tǒng)不足與經驗體會系統(tǒng)不能處理多種不同資源的情況，也缺乏處理大規(guī)模數據的能力。safe函數的編寫是程序成功的關鍵，其中利用Change標記的思鄉(xiāng)值得仔細體會。六、附錄：源代碼（帶注釋）//*******************************************************//*操作系統(tǒng)實驗三死鎖*//*實驗學院一班（0436101）張元競(6040310110)*//*2006-10-15*//******************************************************/#include<cstdio>#include<cstring>#include<cstdlib>#include<ctime>//共有3種資源，3個進程boolavoid;structinfo//進程信息{longtot[4];//最大占用資源數longp[4];//已經占有的資源數}pro[5];longLeftRes[4];//剩余資源數longqu[4];voidinit()//函數功能:輸入和初始化{chartmp[128];longi,j;//以下由用戶選擇是否采用避免死鎖算法printf("是否采用避免死鎖算法?(Y/N)");gets(tmp);avoid=(tmp[0]=='Y'||tmp[0]=='y');//輸入各進程的資源信息printf("請輸入各進程的資源信息:\n");printf("依次輸入各進程所需要的最大資源數量:\n");for(i=1;i<=3;i++){for(j=1;j<=3;j++){scanf("%ld",&pro[i].tot[j]);}}printf("依次輸入各進程已經占據的資源數量:\n");for(i=1;i<=3;i++){for(j=1;j<=3;j++){do{scanf("%ld",&pro[i].p[j]);if(pro[i].p[j]>pro[i].tot[j])printf("\n占有資源超過了聲明的最大資源,請重新輸入\n");}while(pro[i].p[j]>pro[i].tot[j]);}}//初始化資源數量for(i=1;i<=3;i++){LeftRes[i]=10;//初始化總資源數為10for(j=1;j<=3;j++){LeftRes[i]-=pro[j].p[i];//減去已經被占據的資源}}//以下輸出資源狀況表printf("\n===============================================================\n");printf("%-20s","當前剩余資源");for(i=1;i<=3;i++){printf("%8ld",LeftRes[i]);}for(i=1;i<=3;i++){printf("\n%s%ld%-15s","進程",i,"(占用/最大)");for(j=1;j<=3;j++){printf("%4ld/%3ld",pro[i].p[j],pro[i].tot[j]);}}printf("\n===============================================================\n\n");}boolsafe(longx)//函數功能:檢查分配是否安全{longi,j,y[4];boolchange=1;boolT[4];longstack[4],top=0;memset(T,0,sizeof(T));for(i=1;i<=3;i++){y[i]=LeftRes[i]-qu[i];pro[x].p[i]+=qu[i];}while(change){change=0;for(i=1;i<=3;i++){if(T[i])continue;if(y[1]>=pro[i].tot[1]-pro[i].p[1]&&y[2]>=pro[i].tot[2]-pro[i].p[2]&&y[3]>=pro[i].tot[3]-pro[i].p[3]){for(j=1;j<=3;j++){y[j]+=pro[i].p[j];}T[i]=1;change=1;stack[++top]=i;}}}for(i=1;i<=3;i++){if(!T[i]){return0;}}printf("申請成功!安全序列為:");for(i=1;i<=top;i++)printf("%2ld",stack[i]);return1;}voidrequire(longx)//函數功能:嘗試分配資源給進程x{longi,j;if(LeftRes[1]<qu[1]||LeftRes[2]<qu[2]||LeftRes[3]<qu[3]){printf("申請被拒絕!沒有足夠的剩余資源。\n");return;}if(avoid){if(safe(x)){;}else{printf("申請被拒絕!不符合安全規(guī)則。\n");return;}}else{printf("申請成功!\n");}printf("\n===============================================================\n");printf("%-20s","當前剩余資源");for(i=1;i<=3;i++){printf("%8ld",LeftRes[i]-qu[i]);}for(i=1;i<=3;i++){printf("\n%s%ld%-15s","進程",i,"(占用/最大)");for(j=1;j<=3;j++){if(i==x&&!avoid)pro[i].p[j]+=qu[i];printf("%4ld/%3ld",pro[i].p[j