操作系統(tǒng)課程設(shè)計--銀行家算法 (3)

1、<p>　　《操作系統(tǒng)》課程考查試卷</p><p>　　課程名稱（Subject）： </p><p>　　系 別 (Department): </p><p>　　專 業(yè) (Major)： </p><p>　　姓 名 (Name)：

2、 </p><p>　　學(xué) 號 (Student’s Number) </p><p><b>　　摘 要</b></p><p>　　Dijkstra提出的銀行家算法，是最具代表性的避免死鎖的算法。 </p><p>　　本文對如何用銀行家算法來處理操作系統(tǒng)給進(jìn)程分配資源做了詳細(xì)的

3、說明，包括需求分析、概要設(shè)計、詳細(xì)設(shè)計、關(guān)鍵代碼、程序運行以及總結(jié)。  </p><p>　　首先做了需求分析，解釋了什么是銀行家算法，并指出它在資源分配中的重要作用。 </p><p>　　然后給出了銀行家算法的概要設(shè)計，包括算法思路、步驟，以及要用到的主要數(shù)據(jù)結(jié)構(gòu)、函數(shù)模塊及其之間的調(diào)用關(guān)系等。 </p><p>　　在概

4、要設(shè)計的基礎(chǔ)上，又給出了詳細(xì)的算法設(shè)計，實現(xiàn)概要設(shè)計中定義的所有函數(shù),對每個函數(shù)寫出核心算法，并畫出了流程圖。 </p><p>　　接著對編碼進(jìn)行了測試與分析（并在最后附上c語言編寫的程序代碼）。 最后對整個設(shè)計過程進(jìn)行了總結(jié)。</p><p>　　關(guān)鍵詞：操作系統(tǒng) 銀行家算法、c語言</p><p><b>　　目 錄</

5、b></p><p><b>　　一、設(shè)計題目</b></p><p><b>　　二、設(shè)計內(nèi)容</b></p><p><b>　　三、設(shè)計過程</b></p><p><b>　　3.1需求分析</b></p><p&

6、gt;<b>　　3.2概要設(shè)計</b></p><p><b>　　3.3詳細(xì)設(shè)計</b></p><p><b>　　3.4關(guān)鍵代碼</b></p><p><b>　　3.5程序運行</b></p><p><b>　　四、總結(jié)&

7、lt;/b></p><p><b>　　五、參考文獻(xiàn)</b></p><p><b>　　設(shè)計題目</b></p><p><b>　　《銀行家算法》</b></p><p><b>　　設(shè)計內(nèi)容</b></p><p>

8、　　操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計算機系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。而我本次課程設(shè)計就是得用銀行家算法來避免“死鎖”。銀行家算法就是一個分配資源的過程，使分配的序列不會產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時，每次分配后總存在著一個進(jìn)程，如果讓它單獨運行下去，必然可以獲得它所需要的全部資源，也就

9、是說，它能結(jié)束，而它結(jié)束后可以歸還這類資源以滿足其他申請者的需要。</p><p><b>　　三、設(shè)計過程</b></p><p><b>　　3.2概要設(shè)計</b></p><p>　　銀行家算法是一種最有代表性的避免死鎖的算法。 要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。 </p>

10、<p>　　安全狀態(tài)：如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。 不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。 那么什么是安全序列呢？ 安全序列：一個進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。 &l

11、t;/p><p>　　銀行家算法： 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之

12、和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配</p><p><b>　　3.3詳細(xì)設(shè)計</b></p><p>　　1．銀行家算法的思路</p><p>　　先對用戶提出的請求進(jìn)行合法性檢查，即檢查請求的是不大于需

13、要的，是否不大于可利用的。若請求合法，則進(jìn)行試分配。最后對試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來狀態(tài)，拒絕申請。</p><p>　　2．銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)</p><p>　　可利用資源向量 int Available[j] j為資源的種類。</p><p>　　最大需求矩陣 int

14、Max[i][j] i為進(jìn)程的數(shù)量。</p><p>　　分配矩陣 int Allocation[i][j] </p><p>　　需求矩陣 int need[i][j]= Max[i][j]- Allocation[i][j]</p><p>　　申請各類資源數(shù)量 int Request i[j] i進(jìn)程申請j資源

15、的數(shù)量</p><p>　　工作向量 int Work[x] int Finish[y] </p><p>　　3．銀行家算法bank()</p><p>　　進(jìn)程i發(fā)出請求申請k個j資源，Request i[j]=k </p><p>　　(1)檢查申請量是否不大于需求量：Request i[j]<=need[

16、i,j],若條件不符重新輸入，不允許申請大于需求量。</p><p>　　(2)檢查申請量是否小于系統(tǒng)中的可利用資源數(shù)量：Request i[j]<=available[i,j]，若條件不符就申請失敗，阻塞該進(jìn)程，用goto語句跳轉(zhuǎn)到重新申請資源。</p><p>　　(3)若以上兩個條件都滿足，則系統(tǒng)試探著將資源分配給申請的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：</p>

17、<p>　　Available[i,j]= Available[i,j]- Request i[j]；</p><p>　　Allocation[i][j]= Allocation[i][j]+ Request i[j]；</p><p>　　need[i][j]= need[i][j]- Request i[j]；</p><p>　　(4)試分配后，執(zhí)

18、行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。</p><p>　　(5)用do{…}while 循環(huán)語句實現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請。</p><p>　　4．安全性檢查算法（safe()函數(shù)）</p><p>　　(1)設(shè)置兩個向

19、量：</p><p>　　工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時，Work= Available。</p><p>　　Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做Finish[i]=0；當(dāng)有足夠的資源分配給進(jìn)程時，再令Finish[i]=1。</p><p>　　(2)在進(jìn)程中查找

20、符合以下條件的進(jìn)程：</p><p>　　條件1：Finish[i]=0；</p><p>　　條件2：need[i][j]<=Work[j]</p><p>　　若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)</p><p>　　(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：</p>&l

21、t;p>　　Work[j]= Work[j]+ Allocation[i][j]；</p><p>　　Finish[i]=1；</p><p>　　goto step 2；</p><p>　　(4)如果所有的Finish[i]=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。</p><p><b>　　3.4關(guān)鍵

22、代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <conio.h> </p><p>　　# define m 50</p><p>　　int no

23、1; //進(jìn)程數(shù)</p><p>　　int no2; //資源數(shù)</p><p><b>　　int r;</b></p><p>　　int allocation[m][m],need[m][m],available[m],max[m][m]; </p><p>　　char name1[m],name2[m];

24、 //定義全局變量</p><p>　　void main()</p><p><b>　　{</b></p><p>　　void check();</p><p>　　void print();</p><p>　　int i,j,p

25、=0,q=0;</p><p><b>　　char c;</b></p><p>　　int request[m],allocation1[m][m],need1[m][m],available1[m];</p><p>　　printf("**********************************************

26、\n");</p><p>　　printf("* 銀行家算法的設(shè)計與實現(xiàn) *\n");</p><p>　　printf("**********************************************\n");</p><p>　　printf("請

27、輸入進(jìn)程總數(shù):\n");</p><p>　　scanf("%d",&no1);</p><p>　　printf("請輸入資源種類數(shù):\n");</p><p>　　scanf("%d",&no2);</p><p>　　printf("請輸入M

28、ax矩陣:\n");</p><p>　　for(i=0;i<no1;i++)</p><p>　　for(j=0;j<no2;j++)</p><p>　　scanf("%d",&max[i][j]); //輸入已知進(jìn)程最大資源需求量</p><p>　　printf("請輸入

29、Allocation矩陣:\n");</p><p>　　for(i=0;i<no1;i++)</p><p>　　for(j=0;j<no2;j++)</p><p>　　scanf("%d",&allocation[i][j]); //輸入已知的進(jìn)程已分配的資源數(shù)</p><p>　　f

30、or(i=0;i<no1;i++)</p><p>　　for(j=0;j<no2;j++)</p><p>　　need[i][j]=max[i][j]-allocation[i][j]; //根據(jù)輸入的兩個數(shù)組計算出need矩陣的值</p><p>　　printf("請輸入Available矩陣\n");</p>

31、<p>　　for(i=0;i<no2;i++)</p><p>　　scanf("%d",&available[i]); //輸入已知的可用資源數(shù)</p><p>　　print(); //輸出已知條件</p><p>　　check(); //檢測T0時刻已知條件的安全狀態(tài)</p><

32、;p>　　if(r==1) //如果安全則執(zhí)行以下代碼</p><p><b>　　{</b></p><p><b>　　do{ </b></p><p><b>　　q=0;</b></p><p><b>　　p=0;</b></p&g

33、t;<p>　　printf("\n請輸入請求資源的進(jìn)程號(0~4)：\n");</p><p>　　for(j=0;j<=10;j++)</p><p><b>　　{</b></p><p>　　scanf("%d",&i);</p><p>　　i

34、f(i>=no1)</p><p><b>　　{</b></p><p>　　printf("輸入錯誤，請重新輸入：\n");</p><p>　　continue; </p><p><b>　　}</b></p><p>　　else

35、 break;</p><p><b>　　}</b></p><p>　　printf("\n請輸入該進(jìn)程所請求的資源數(shù)request[j]:\n");</p><p>　　for(j=0;j<no2;j++)</p><p>　　scanf("%d",&reque

36、st[j]);</p><p>　　for(j=0;j<no2;j++)</p><p>　　if(request[j]>need[i][j]) p=1; </p><p>　　//判斷請求是否超過該進(jìn)程所需要的資源數(shù)</p><p><b>　　if(p)</b></p><p>

37、　　printf("請求資源超過該進(jìn)程資源需求量，請求失?。n");</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(j=0;j<no2;j++)</p><p>　　if(request[j]>av

38、ailable[j]) q=1; </p><p>　　//判斷請求是否超過可用資源數(shù)</p><p><b>　　if(q) </b></p><p>　　printf("沒有做夠的資源分配，請求失?。n");</p><p>　　else

39、 //請求滿足條件</p><p><b>　　{</b></p><p>　　for(j=0;j<no2;j++) </p><p><b>　　{</b></p><p>　　available1[j]=available[j]; </p><p>　　allo

40、cation1[i][j]=allocation[i][j];</p><p>　　need1[i][j]=need[i][j]; </p><p>　　//保存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)</p><p>　　available[j]=available[j]-request[j]; </p><p>　　allo

41、cation[i][j]+=request[j];</p><p>　　need[i][j]=need[i][j]-request[j];</p><p>　　//系統(tǒng)嘗試把資源分配給請求的進(jìn)程</p><p><b>　　}</b></p><p><b>　　print();</b></p

42、><p>　　check(); //檢測分配后的安全性</p><p>　　if(r==0) //如果分配后系統(tǒng)不安全</p><p><b>　　{</b></p><p>　　for(j=0;j<no2;j++)</p><p><b>　　{</b><

43、;/p><p>　　available[j]=available1[j]; </p><p>　　allocation[i][j]=allocation1[i][j];</p><p>　　need[i][j]=need1[i][j];</p><p>　　//還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)</p><p&

44、gt;<b>　　}</b></p><p>　　printf("返回分配前資源數(shù)\n");</p><p><b>　　print();</b></p><p><b>　　}</b></p><p><b>　　}</b></

45、p><p>　　}printf("\n你還要繼續(xù)分配嗎？Y or N ?\n"); </p><p>　　//判斷是否繼續(xù)進(jìn)行資源分配</p><p>　　c=getche();</p><p>　　}while(c=='y'||c=='Y');</p><p>&l

46、t;b>　　}</b></p><p><b>　　}</b></p><p>　　void check() //安全算法函數(shù)</p><p><b>　　{</b></p><p>　　int k,f,v=0,i,j;</p><p>　　int wo

47、rk[m],a[m];</p><p>　　bool finish[m];</p><p><b>　　r=1;</b></p><p>　　for(i=0;i<no1;i++)</p><p>　　finish[i]=false; // 初始化進(jìn)程均沒得到足夠資源數(shù)并完成</p><p&g

48、t;　　for(i=0;i<no2;i++)</p><p>　　work[i]=available[i];//work[i]表示可提供進(jìn)程繼續(xù)運行的各類資源數(shù)</p><p><b>　　k=no1;</b></p><p><b>　　do{</b></p><p>　　for(i=0;i

49、<no1;i++)</p><p><b>　　{</b></p><p>　　if(finish[i]==false)</p><p><b>　　{</b></p><p><b>　　f=1;</b></p><p>　　for(j=0;j&

50、lt;no2;j++)</p><p>　　if(need[i][j]>work[j])</p><p><b>　　f=0;</b></p><p>　　if(f==1) //找到還沒有完成且需求數(shù)小于可提供進(jìn)程繼續(xù)運行的資源數(shù)的進(jìn)程</p><p><b>　　{</b><

51、/p><p>　　finish[i]=true;</p><p>　　a[v++]=i; //記錄安全序列號</p><p>　　for(j=0;j<no2;j++)</p><p>　　work[j]+=allocation[i][j]; //釋放該進(jìn)程已分配的資源</p><p><b>　　}&

52、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　k--; //每完成一個進(jìn)程分配，未完成的進(jìn)程數(shù)就減1</p><p>　　}while(k>0);</p><p><b>　　

53、f=1;</b></p><p>　　for(i=0;i<no1;i++) //判斷是否所有的進(jìn)程都完成</p><p><b>　　{</b></p><p>　　if(finish[i]==false) </p><p><b>　　{</b></p>

54、<p><b>　　f=0;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(f==0) //若有進(jìn)程沒完成，則為不安

55、全狀態(tài)</p><p><b>　　{</b></p><p>　　printf("系統(tǒng)處在不安全狀態(tài)！");</p><p><b>　　r=0;</b></p><p><b>　　}</b></p><p><b>　

56、　else</b></p><p><b>　　{</b></p><p>　　printf("\n系統(tǒng)當(dāng)前為安全狀態(tài)，安全序列為：\n");</p><p>　　for(i=0;i<no1;i++)</p><p>　　printf("p%d ",a[i]);

57、 //輸出安全序列</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void print() //輸出函數(shù)</p><p><b>　　{</b></p><p><b>　　int i,

58、j;</b></p><p>　　printf("\n");</p><p>　　printf("*************此時刻資源分配情況*********************\n");</p><p>　　printf("進(jìn)程名/號 | Max | Allocation |

59、 Need |\n");</p><p>　　for (i = 0; i < no1; i++)</p><p><b>　　{</b></p><p>　　printf(" p%d/%d ",i,i);</p><p>　　for (j = 0; j <

60、; no2; j++) </p><p>　　{printf("%d ",max[i][j]);}</p><p>　　for (j = 0; j < no2; j++) </p><p>　　{printf(" %d ",allocation[i][j]);}</p><p>　　for

61、 (j = 0; j < no2; j++)</p><p>　　{printf(" %d ",need[i][j]);}</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n"

62、;);</p><p>　　printf("各類資源可利用的資源數(shù)為:");</p><p>　　for (j = 0; j < no2; j++) </p><p>　　{printf(" %d",available[j]);}</p><p>　　printf("\n");

63、</p><p><b>　　}</b></p><p><b>　　3.5程序運行</b></p><p><b>　　程序初始化</b></p><p>　　2、檢測系統(tǒng)資源分配是否安全結(jié)果</p><p><b>　　四、總結(jié)</b

64、></p><p>　　在這次作業(yè)之后我更加了解關(guān)于死鎖的問題，知道了銀行家的算法的具體思想，以后要多動手、動腦才行。</p><p><b>　　五、參考文獻(xiàn)</b></p><p>　　[1] 《計算機操作系統(tǒng)》西安電子科技大學(xué)出版社，湯小丹、梁紅兵、哲鳳屏、湯子瀛</p><p>　　[2] 《操作系統(tǒng)》浙江