1、<p>　　《 操作系統(tǒng) 》</p><p><b>　　課程設計報告</b></p><p>　　系 別： 信息科學與技術系 </p><p>　　專業(yè)班級： </p><p>　　學生姓名：

2、 </p><p>　　指導教師： </p><p><b>　　目 錄</b></p><p>　　一、課程設計目的和意義3</p><p>　　二、課程設計題目描述及算法3</p><p>　　三、課程設計報告內容3</p&g

3、t;<p><b>　　1.算法描述3</b></p><p><b>　　2.數據結構4</b></p><p>　　3.主要函數說明4</p><p><b>　　4.算法流程圖5</b></p><p>　　5.運行結果及說明7</p>

4、<p>　　6.附錄清單及分析8</p><p><b>　　四、總結14</b></p><p>　　一、課程設計目的和意義</p><p>　　了解掌握銀行家算法，學會模擬實現資源分配，同時有要求編寫和調試一個系統(tǒng)分配資源的簡單模擬程序，觀察死鎖產生的條件，并使用適當的算法，有效的防止和避免死鎖的發(fā)生</p>

5、<p>　　二、課程設計題目描述及算法</p><p>　　題目：銀行家算法設計</p><p>　　設計要求：編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。設進程I提出請求Request[N]，則銀行家算法按如下規(guī)則進行判斷。</p><p>　　(1)如果Request[N]<=NEED[I，N]，則轉(2)；否則，出錯。</p&g

6、t;<p>　　(2)如果Request[N]<=AVAILABLE，則轉(3)；否則，出錯。</p><p>　　(3)系統(tǒng)試探分配資源，修改相關數據：</p><p>　　AVAILABLE=AVAILABLE-REQUEST</p><p>　　ALLOCATION=ALLOCATION+REQUEST</p><p&g

7、t;　　NEED=NEED-REQUEST</p><p>　　(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復原狀，進程等待。</p><p>　　上述三個矩陣存在如下關系：Need[i,j]= Max[i，j]- Allocation[i，j]</p><p>　　三、課程設計報告內容</p><p><

8、b>　　1.算法描述</b></p><p>　　設Request[i] 是進程Pi的請求向量，如果Requesti[j]=K,表示進程Pi需要K個Rj類型的資源，當Pi發(fā)出資源請求后，系統(tǒng)按下面步驟進行檢查：</p><p>　?。?）如果Requesti[j]<=Need[i,j]，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。<

9、/p><p>　?。?）如果Requesti[j]<=Available[j],便轉向步驟3；否則，表示尚無足夠資源，Pi須等待。</p><p>　?。?）系統(tǒng)試探著把資源分配給進程Pi，并修改下面數據結構中的數值：</p><p>　　Available[j]:=Available[j]-Requesti[j];</p><p>　　A

10、llocation[i,j]:=Allocation[i,j]+Requesti[j];</p><p>　　Need[i,j]:=Need[i,j]-Requesti[j];</p><p>　?。?）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。<

11、;/p><p><b>　　2.數據結構</b></p><p>　?。?） 可利用資源向量Available。這是一個含有n個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K,則表示系統(tǒng)中現有Rj類資源K個。</p><p&

12、gt;　　（2）最大需求矩陣Max。這是一個m*n的矩陣，它定義了系統(tǒng)中n個進程中每一個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。</p><p>　?。?）分配矩陣Allocation。這也是一個m*n的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,則表示進程i當前已分得Rj類資源的數目為K。</p&

13、gt;<p>　?。?）需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K,則表示進程i還需要Rj類資源K個，方能完成其任務。</p><p>　　(5) 工作數組Work.。這是一個含有n個元素的數組，它代表可以提供分配的資源數，初始值是Available中的數值，隨著資源的回收，它的值也會改變，公式是Work[i]=Work[i]+Alloc

14、ation[i]。</p><p><b>　　3.主要函數說明</b></p><p>　?。?） Main() 主函數：用來顯示資源的分配情況和提示信息，同時用Main函數來調用其它子程序。 </p><p>　?。?）Safe() 函數：用來檢查是否有安全序列，如果存在則返回一個‘1’給主函數，否則返回‘0’。</p>&l

15、t;p>　　(3) Disp() 函數：用來顯示隨機生成的資源包括Max、Need、Allocation、Available。</p><p>　　(4) Request() 函數：用來進行資源請求，分為手動的和隨機申請。同時對申請的資源進行判斷，檢查申請是否有效，如果有效則返回一個‘1’給主函數，否則返回‘0’。</p><p><b>　　4.算法流程圖</b&g

16、t;</p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y </b></p><p><b>　　N</b></p><p><b>　　Y</b>&l

17、t;/p><p><b>　　Y </b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　5.運行結果及說明</b></p><p>　　圖1 不存在安全序列</p&

18、gt;<p>　　隨機分配完資源后，進行安全檢查，在檢查過程中在屏幕上顯示檢查信息，上圖為資源分配不安全時顯示的信息。若在程序中不將int i,j,k,h,l;改為int I; 在檢查Available是否滿足Need時將檢查m*n遍，并存在表達有歧異，改后就不需要全部檢查，而是Available只要有一個不滿足Need就停止檢查。</p><p><b>　　圖2 存在安全路徑</

19、b></p><p>　　存在安全路徑后，在屏幕上顯示變化過程和安全路徑。提示是否申請資源。</p><p>　　由上圖可知，進程p0最大需要的三種資源數分別為10 7 9，需求資源數為4 3 1，當前已分配資源數為6 4 8，可利用資源數為11 6 11。p1、p2同理。</p><p>　　三個矩陣存在如下關系:Need[i,j]= Max[i，j]- A

20、llocation[i，j]</p><p>　　process[0]->need[0]</p><p>　　work[0]=17—已分配資源數6，可分配資源數11，則最大分配數17</p><p>　　同理work[1]=10 、work[2]=19</p><p>　　Process[0]->need[1]</p>

21、<p>　　Work[0]=22—已分配資源數5，可分配17，則總可分配資源數22</p><p><b>　　后面的同理。</b></p><p><b>　　圖3 為申請資源</b></p><p>　　選擇1則進行隨機資源分配，選擇2則進行手動資源分配。</p><p><

22、b>　　圖4 手動分配</b></p><p>　　為保證程序只在選擇的數為0、1或2時繼續(xù)進行，使用If語句進行判斷，不是選擇的這三個進程數時終止程序并提示重新輸入。</p><p>　　圖5 給p0手動配后生成的圖形</p><p><b>　　與</b></p><p>　　圖6 隨機分配生成的圖

23、形</p><p><b>　　比較</b></p><p>　　當手動輸入的數小于所需資源數時，所需數減小，已分配數增多，p0原需要4 3 1， 手動分配1 2 1后，為3 1 0，已分配變?yōu)? 6 9，p1 、p2同理；當手動資源數為4 4 2時，need為0 0 0，但allocation為10 8 11，并不等于10 7 9 ，出現錯誤。</p>

24、<p><b>　　圖7 隨機分配</b></p><p>　　當選擇1時，進行隨機分配，隨機分配的資源數為3 2 1，無法滿足需要，產生錯誤。</p><p><b>　　6.附錄清單及分析</b></p><p>　　#include<stdio.h></p><p>　

25、　#include <stdlib.h></p><p>　　#include<time.h></p><p>　　#define M 3</p><p>　　#define N 3</p><p>　　int Need[M][N],Allocation[M][N],Avalible[N],Max[M][N],fini

26、sh[N];</p><p>　　//Need :進程需要的資源數Allocation:進程已分配的資源; Avalible:進程可供分配的資源</p><p>　　void display(int *a,int n) //顯示一維數組</p><p>　　{ int i;</p><p>　　for(i=0;i<n;i++)&

27、lt;/p><p>　　printf("%3d",a[i]);</p><p><b>　　}</b></p><p>　　void disp() //顯示資源列表</p><p>　　{ int i;//--原為int i,j,k,h,l，改后Available只要有一個不滿足Need就停

28、止檢查;</p><p>　　printf("Nnumber\t Max\t\t need\t\t allocation\t avalible\n");</p><p>　　for(i=0;i<M;i++)</p><p>　　{printf("p%d\t",i);//--分別顯示P0,P1,P2的Max,N

29、eed,Allocation,Avalible</p><p>　　display(Max[i],N);</p><p>　　printf("\t");</p><p>　　display(Need[i],N);</p><p>　　printf("\t");</p><p>　

30、　display(Allocation[i],N);</p><p>　　printf("\t");</p><p><b>　　if(i==0)</b></p><p>　　display(Avalible,N);</p><p>　　printf("\n");</p>

31、;<p><b>　　} }</b></p><p>　　void grand(int *a,int *b,int n) //分配資源</p><p><b>　　{ int i;</b></p><p>　　for(i=0;i<n;i++)</p><p>　　a[i]=

32、b[i];</p><p><b>　　}</b></p><p>　　int check(int *a,int *b,int n) //檢查Allocation是否與Max相等</p><p><b>　　{ int i;</b></p><p>　　for(i=0;i<n;i+

33、+)</p><p>　　{if(a[i]<b[i]) return 0;}</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int compare(int *a,int *b,int n) //比較數組的大小<

34、/p><p><b>　　{ int i;</b></p><p>　　;//原本為char flag</p><p>　　for(i=0;i<n;i++)</p><p>　　{ if (a[i]<b[i])</p><p><b>　　return 0;</

35、b></p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int comp(int *a,int *b,int n,int m) //比較數組</p&

36、gt;<p><b>　　{int i;</b></p><p>　　for(i=0;i<n;i++)</p><p>　　{ if (a[i]>b[i])</p><p>　　{ if(m==1)</p><p>　　printf("request Number%d resouce

37、have an error request overflow avalible[%d]\n",i+1,i);</p><p><b>　　if(m==2)</b></p><p>　　printf("request Number%d resouce have an error request overflow Need[%d]\n",i+

38、1,i);</p><p>　　return 0; }}</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　void dec(int *a,int *b,int n) //數組相減</p><p

39、>　　{ int i;</p><p>　　for(i=0;i<n;i++)</p><p>　　a[i]-=b[i];</p><p><b>　　}</b></p><p>　　char input() //輸入數據</p><p>

40、;　　{ char c;</p><p>　　c=getchar()-0x30;</p><p><b>　　return c;</b></p><p><b>　　}</b></p><p>　　void add(int *a,int *b,int n,int m) //數組相加

41、</p><p><b>　　{ int i ;</b></p><p>　　for(i=0;i<n;i++)</p><p>　　a[i]+=b[i];</p><p>　　for(i=0;i<n;i++)</p><p>　　{ if(m==0) printf("Aval

42、ible[%d]=%d ",i,a[i]);</p><p>　　if(m==3)printf("\n");</p><p>　　if(m==1) printf("work valuese changed work[%d]=%d\n",i,a[i]);</p><p><b>　　}</b>

43、</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　int safe()//檢查安全序列</p><p>　　{ int i,count=0,n,r1=1;//原為int i,count=0,n,j,r1=1;</p>

44、<p>　　int work[N],sr[M],flag;</p><p>　　int finish1[N];</p><p>　　grand(work,Avalible,N);</p><p>　　printf("check safe list......\n");</p><p>　　for(i=0;i<

45、;N;i++)</p><p>　　finish1[i]=-1;</p><p>　　for(n=0;n<M;n++)</p><p>　　{ for(i=0;i<M;i++)</p><p>　　{ flag=compare(work,Need[i],N);</p><p>　　if (flag==0)

46、{printf("can't satisfy process[%d]->need[%d] ",n,i);break;}</p><p>　　if(finish1[i]==-1&&flag==1&&finish[i]==-1)</p><p>　　{ printf("find a right need----proc

47、ess[%d]->need[%d]\n",n,i);</p><p>　　add(work,Allocation[i],N,r1);</p><p>　　finish1[i]=1; sr[count]=i;</p><p>　　count++; //記錄安全序列</p><p><b>　　} }}</b

48、></p><p>　　if(count>=M)</p><p>　　{ printf("-----have an safe list-----\n");</p><p>　　for(i=0;i<M;i++)</p><p>　　{ if(i!=M-1)</p><p>　　p

49、rintf("p%d->",sr[i]);</p><p><b>　　else</b></p><p>　　printf("p%d\n",sr[i]);</p><p>　　} return 1; }</p><p><b>　　else</b><

50、;/p><p>　　{ printf("after check there no safe list.....\n");</p><p>　　printf("can't apply resouce\n");</p><p><b>　　return 0;</b></p><p&g

51、t;<b>　　} }</b></p><p>　　int ran_request()//隨機請求資源</p><p>　　{ int i,flag1,flag2,r1=1,r2=2,r3=3;</p><p>　　int request[N],pn;//N=3</p><p>　　pn=rand()%2;

52、//pn進程標志</p><p>　　printf("Process[%d] call for resouce\n",pn); //隨機進程X請求資源</p><p>　　for(i=0;i<N;i++)</p><p>　　request[i]=rand()%5; //將隨機資源給request[i],i=1,2,3,其實r

53、equest是現在將要給予的資源</p><p>　　//而且request[1],[2],[3]即代表3種不同的資源類型</p><p>　　for(i=0;i<M;i++)</p><p>　　finish[i]=-1; </p><p>　　printf("random produce request[%

54、d]:",N); //隨機產生分配數</p><p>　　display(request,N); //顯示request[]數組</p><p>　　printf("\n");</p><p>　　if(finish[pn]==-1) //finish記錄進程是否分配完成

55、 </p><p><b>　　{</b></p><p>　　flag1=comp(request,Avalible,N,r1);//flag1</p><p>　　flag2=comp(request,Need[pn],N,r2);//flag2</p><p>　　if(flag1==1&&a

56、mp;flag2==1)</p><p><b>　　{ </b></p><p>　　printf("call for request availible");//顯示需求有效</p><p>　　dec(Avalible,request,N);//Avalible-request,指針形式，下2同</p>

57、<p>　　dec(Need[pn],request,N);//Need-request</p><p>　　add(Allocation[pn],request,N,r3);//Allocation+request</p><p><b>　　disp();</b></p><p>　　if(safe()==1)</p>

58、;<p><b>　　{ </b></p><p>　　if(check(Allocation[pn],Max[pn],N)==1)</p><p><b>　　{ </b></p><p>　　add(Avalible,Allocation[pn],N,0);</p><p>

59、;　　finish[pn]=1; </p><p><b>　　}</b></p><p>　　return 1; </p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　return

60、 0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　printf("the resouce have assingned\n");<

61、;/p><p><b>　　}</b></p><p>　　int request() //手動申請資源</p><p>　　{ int request[N],pn;</p><p>　　int i,flag1,flag2,r1=1,r2=2,r3=3;</p><p>　　

62、for(i=0;;i++)</p><p><b>　　{</b></p><p>　　printf("please input the request number which you want:");</p><p>　　scanf("%d",&pn);</p><p

63、>　　printf("\n");</p><p>　　if(pn>=0 && pn<=2) break;</p><p><b>　　else </b></p><p>　　printf(" input error,please input again!\n");//非

64、進程數0、1、2警告</p><p><b>　　}</b></p><p>　　printf("please input the request number:\n");</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b><

65、/p><p>　　printf("The %d request:\n",i);</p><p>　　scanf("%d",&request[i]);</p><p><b>　　}</b></p><p>　　for(i=0;i<N;i++)</p><

66、;p>　　finish[i]=-1;</p><p>　　printf("random produce request[%d]:",N);</p><p>　　display(request,N); </p><p>　　printf("\n");</p><p>　　if(finish[pn]=

67、=-1) //finish記錄進程是否分配完成 </p><p><b>　　{</b></p><p>　　flag1=comp(request,Avalible,N,r1);//flag1</p><p>　　flag2=comp(request,Need[pn],N,r2);//flag2</p

68、><p>　　if(flag1==1&&flag2==1)</p><p><b>　　{ </b></p><p>　　printf("call for request availible");//顯示需求有效</p><p>　　dec(Avalible,request,N);//A

69、valible-request,指針形式，下2同</p><p>　　dec(Need[pn],request,N);//Need-request</p><p>　　add(Allocation[pn],request,N,r3);//Allocation+request</p><p><b>　　disp();</b></p>

70、<p>　　if(safe()==1)</p><p><b>　　{ </b></p><p>　　if(check(Allocation[pn],Max[pn],N)==1)</p><p><b>　　{ </b></p><p>　　add(Avalible,Alloc

71、ation[pn],N,0);</p><p>　　finish[pn]=1; </p><p><b>　　}</b></p><p>　　return 1; </p><p><b>　　}</b></p><p><b>　　else</b><

72、;/p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　printf("the

73、resouce have assingned\n");</p><p><b>　　}</b></p><p>　　int main()</p><p>　　{int i,j,s_flag;</p><p><b>　　char c,s;</b></p><p>　

74、　int av[N],s_ll[M][N];</p><p>　　for(i=0;i<M;i++)</p><p>　　{finish[i]=-1;}</p><p>　　srand(time(NULL));</p><p>　　for(i=0;i<M;i++)</p><p>　　for(j=0;j<

75、;N;j++)</p><p>　　{ Allocation[i][j]=rand()%10;</p><p>　　Need[i][j]=rand()%10;</p><p>　　Max[i][j]=Allocation[i][j]+Need[i][j];</p><p><b>　　}</b></p>

76、<p>　　for(i=0;i<N;i++)</p><p>　　{Avalible[i]=rand()%12; }</p><p>　　disp();s_flag=safe();</p><p>　　if(s_flag==1)</p><p>　　{ printf("request resource---(Y/N)

77、\n");</p><p>　　c=getchar();</p><p>　　if(c=='Y'||c=='y')</p><p><b>　　{</b></p><p>　　N1: printf("1---------random request resouce

78、\n");</p><p>　　printf("2---------request resouce by man\n");</p><p>　　grand(av,Avalible,N); //保存原始的available的值</p><p>　　for(i=0;i<M;i++)</p><p&g

79、t;<b>　　{ </b></p><p>　　grand(s_ll[i],Allocation[i],N);}//grand函數為分配資源函數</p><p>　　getchar();</p><p>　　Mnu:s=getchar();</p><p>　　switch(s) //進行分配選擇<

80、/p><p><b>　　{ </b></p><p>　　case '1':if(ran_request()==1) //ran_request()隨機請求資源</p><p><b>　　{</b></p><p>　　printf ("continue request(Y

81、/N)\n");</p><p>　　getchar();c=getchar();</p><p>　　if(c=='Y'||c=='y')</p><p>　　goto N1; }</p><p><b>　　else</b></p><p><b

82、>　　{ </b></p><p>　　grand(Avalible,av,N);</p><p>　　for(i=0;i<M;i++)</p><p>　　grand(Allocation[i],s_ll[i],N); }</p><p>　　//grand(int *a,int *b,int n)/為分配資源函數，

83、b按n大小賦值于a</p><p><b>　　break;</b></p><p>　　case '2':if(request()==1) //--request()手動申請資源</p><p><b>　　{</b></p><p>　　printf("continue

84、 request(Y/N)\n");</p><p>　　getchar();c=getchar();</p><p>　　if(c=='Y'||c=='y')</p><p><b>　　goto N1;}</b></p><p><b>　　else </b

85、></p><p><b>　　{</b></p><p>　　grand(Avalible,av,N);//grand(int *a,int *b,int n)</p><p>　　//為分配資源函數，b按n大小賦值于a</p><p>　　for(i=0;i<M;i++)</p><p

86、>　　grand(Allocation[i],s_ll[i],N);}</p><p><b>　　break;</b></p><p>　　default:printf("input error,please input agin...\n");goto Mnu;</p><p><b>　　}}</

87、b></p><p>　　if(c=='N'||c=='n')</p><p>　　printf("Thank for your use....\n"); } </p><p>　　return 0; }</p><p><b>　　六、總結</b></p

88、><p>　　通過這次的課程設計，我了解掌握了銀行家算法，學會模擬實現資源分配，同時通過編寫和調試一個系統(tǒng)分配資源的簡單模擬程序，觀察到了死鎖產生的條件，并使用適當的算法，有效的防止和避免死鎖的發(fā)生。</p><p>　　雖然操作系統(tǒng)是以前學的，再接觸時遺忘了許多，但是通過老師的講解，同學的幫助，自己也仔細地看了這次課程設計的實驗指導，撿回了許多東西，對于銀行家算法的設計、編寫的思路變得清晰。

89、通過幾天反復的閱讀實驗指導，仔細的思考出現的問題，反復推敲、測試與修改，終于能完滿的完成課程設計任務。課程設計的時間雖然不長，但帶了給我知識，也帶給了我戰(zhàn)勝困難、完成任務的歡樂。希望以后有更多的機會接觸這類的課程設計。</p><p><b>　　課程設計成績:</b></p><p>　　注:教師按學生實際成績（平時成績和業(yè)務考核成績）登記并錄入教務MIS系統(tǒng)，由系