PAGE操作系統課程設計任務書學院計算機與信息工程學院專業網絡工程課程名稱操作系統題目銀行家算法的實現完成期限自2013年6月3日至2013年6月30日共4周內容及任務一、項目的目的1.定義相關數據結構；2.編程實現銀行家算法；3.分析和驗證銀行家算法程序。二、項目任務的主要內容和要求根據銀行家算法的基本思想，設計相關數據結構，編寫程序實現銀行家算法中各個功能模塊，并通過數據驗證該算法;按照要求撰寫課程設計報告。三、項目設計（研究）思路銀行家算法是一個用來預防系統進入死鎖狀態的算法，用它可以判斷系統的安全性，如果系統當前處于安全狀態，則可以為申請資源的進程分配資源，如果不是安全狀態，則不能為申請資源的進程分配資源。銀行家算法執行過程中，首先判斷申請資源的進程所申請的資源數目是否合法，若是合法的，則可以為其進行試分配，再利用安全性算法求出安全序列，如果存在安全序列，則說明可以給申請資源的進程分配資源，分配成功，繼續為其它進程服務。如果找不到安全序列，則說明為該進程分配資源后系統會進入不安全狀態，所以不能為該進程分配資源，使該進程進入阻塞狀態。若申請資源的進程申請的資源數目不合法，則不需要進行試分配，直接使其進入阻塞狀態，處理其他申請資源的進程。首先對算法的設計從總體上進行了分析，然后分析各個細節，再對算法分模塊設計，并對各個模塊的算法思想通過流程圖表示，分塊編寫代碼，并進行調試和測試，最后進行組裝測試及系統測試，使其成為一個可以用來判斷系統安全狀態的程序。四、具體成果形式和要求1.深入理解銀行家算法。2.用C語言編程實現銀行家算法。3.建立相對友好的界面。4.撰寫課程設計文檔。進度安排起止日期工作內容2013.6.3—2013.6.8分析題目，分配任務，查找資料2013.6.9—2013.6.24編寫源代碼，測試并修改2013.6.25—2013.6.30書寫課程設計報告主要參考資料1.湯子瀛.計算機操作系統(第三版)[M].西安電子科技大學出版社.2009;2.方敏.操作系統教程[M].西安電子科技大學出版社.2006;3.周湘貞.操作系統原理與實踐教程[M].清華出版社.2005;4嚴蔚敏.數據結構(C語言版)[M].清華大學出版社.2009;指導教師意見（簽字）：年月日系（教研室）主任意見（簽字）：年月日操作系統設計說明書學院名稱：計算機與信息工程學院班級名稱：網工111班學生姓名：汪瑋，金良民，李亮，何玉琴，李寧學號：2011211301、2011211272、20112112772011211265、2011211278題目：銀行家算法的實現指導教師姓名：趙國柱起止日期：自2013年6月3日至2013年6月30日TOC\o"1-3"\h\u16030第一部分：正文部分 16873一、選題背景 114686二、設計思路 129277三、過程論述 1161653.1全性算法的算法思想 144023.1.1銀行家算法中的數據結構 1212003.1.2.設置向量 29823.1.3.安全性檢測流程圖 2306143.2.銀行家算法的算法思想 437273.2.1.銀行家算法 479103.2.2.銀行家算法流程圖 410830四、結果分析 524129五、結論 823958第二部分：參考文獻 829951第三部分：指導教師評語 931160第四部分：成績評定 910525附錄 10PAGE13第一部分：正文部分一、選題背景在具有多道程序并發執行能力的系統中，系統資源的利用率、進程執行的效率都大幅增加，但可能發生“死鎖”的危險。所謂死鎖，是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。而死鎖產生的原因有兩點：競爭資源和進程推進的順序不合法。為了避免死鎖，使得進程的執行能夠順利完成，引入銀行家算法進行解決。銀行家算法是具有代表性的避免死鎖的算法，由于該算法能用于銀行系統現金貸款的發放而得名。二、設計思路當系統在進行資源管理時，如果對進程申請的資源分配不當，可能會使系統進入死鎖狀態，因而后面到來的進程也無法順利執行。銀行家算法中，要對當前申請資源的進程申請資源的數目進行判斷，如果可以試分配，則試求出一個安全序列，如果可以求出，則說明給這個進程分配資源后系統不會進入不安全狀態，將該進程申請的資源分配給它，若求不出安全序列，則說明將資源分配給該進程后系統會進入不安全狀態，所以就使該進程進入阻塞狀態，等待以后可以分配資源時再執行該進程，然后系統繼續服務其它進程。通過這樣一個過程，可以有效避免系統進入死鎖狀態。三、過程論述3.1全性算法的算法思想系統在進行資源分配之前，應先計算此次資源分配后狀態的安全性。若此次分配后的狀態是安全狀態，則將資源分配給進程；否則，令進程等待。3.1.1銀行家算法中的數據結構1)可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果Available[j]=K，則表示系統中現有Rj類資源K個。2）最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示進程i需要Rj類資源的最大數目為K。3）分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一個進程的資源數。如果Allocation[i,j]=K,則表示進程i當前已分得Rj類資源的數目為K。4）需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i，j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。上述三個矩陣間存在下述關系：Need[i,j]=Max[i,j]-Allocation[i,j]3.1.2.設置向量(1)設置向量：工作向量Work：它表示系統可提供給進程繼續運行所需的各類資源數目，在執行安全性算法開始時，Work[]=Available[]。Finish[]：它表示系統是否有足夠的資源分配給每個進程，使之運行完成。開始時先做Finish[i]=false；當有足夠的資源分配給進程時，再令Finish[i]=true。(2)在進程中查找符合以下條件的進程：條件1：Finish[i]=ture；條件2：need[i][j]<=work[j]若找到，則執行步驟(3);否則，執行步驟(4)(3)當進程獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：work[j]=work[j]+allocation[i][j]；Finish[i]=ture；gotostep2；(4)最后循環檢查是否所有的Finish[i]=ture都滿足，如果是定義一個r，則r返回1表示系統處于安全狀態，否則，r返回0表示系統處于不安全狀態。3.1.3.安全性檢測流程圖調用check()函數對銀行家算法進行安全性檢測。安全行算法如以下流程圖所示：work[]是空閑資源矩陣，finish表示系統是否有足夠的資源分配給進程,(1)work[]=Available[],finish[]=false；當有足夠資源分配給進程時，令Finish[i]=true。(2)從進程集合中找一個能滿足①Finish[i]=false②Need<=Work的進程，若找到，則執行步驟（3）；否則，執行步驟（4）。(3)當進程P獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：safeprocess[k++]=i;Work=Work+Allocation;Finish[i]=true;轉向步驟（2）。(4)如果所有進程的Finish[i]=true,則表示系統處于安全狀態；否則，系統處于不安全狀態。調用check()函調用check()函數work[]=available[]finish[]=falseneed[][]<=work[]finish[]=false?work[]=work[]+allocation[][]finish[]=trueYN所有進程的finish[]==true?YN輸出安全序列，并打印出當前資源分配情況輸出提示：系統不安全調用結束圖3-1安全性檢測流程圖3.2.銀行家算法的算法思想3.2.1.銀行家算法先對用戶提出的請求進行合法性檢查，即檢查請求數是否不大于需求數，是否不大于可利用的。若請求合法，則進行試分配。最后對分配后的狀態調用安全性檢查算法進行安全性檢查。若安全，則分配，否則，不分配，恢復原來狀態，拒絕申請。進程i發出申請資源請求：(1)通過request[m]和available[m]的關系檢查申請量是否不大于需求量再檢查申請量是否不大于系統中的可利用資源數量，若條件不符重新輸入，不允許申請大于需求量。(2)若以上條件都滿足，則系統試探著將資源分配給申請的進程，并修改下面數據結構中的數值：Available[i,j]=Available[i,j]-Request[i][j]；Allocation[i][j]=Allocation[i][j]+Request[i][j]；need[i][j]=need[i][j]-Request[i][j]；(3)進行試分配，執行安全性檢查，調用check()函數檢查此次資源試分配后系統是否處于安全狀態。若安全，才正式將資源分配給進程；否則本次試探分配作廢，恢復原來的資源分配狀態，讓該進程等待。(4)用while循環語句實現輸入字符Y/N判斷是否繼續進行資源申請。3.2.2.銀行家算法流程圖銀行家算法流程圖圖形化描述了此算法基本功能，如圖3-2所示。系統初始化，輸入進程no1，輸入資源類數no2,輸入進程最大需求矩陣Max,已分配矩陣Allocation和可利用資源矩陣Available。need[][]=max[][]-allocation[][]。打印輸出此時資源分配情況表。輸入欲申請資源進程號，查看輸入是否合法。是的話輸入該進程的資源量，否的話重新申請資源進程號。判斷request[]>need[][]，是則進行繼續分配或者退出，否則判斷request[]>available[]。是則進行繼續分配或者退出，否則進行預分配。調用check（）函數進行安全性檢查。然后進行繼續分配或者退出是則，輸入欲申請資源進程號，否則退出。圖3-2銀行家算法流程圖四、結果分析 (1)運行banker.cpp文件，要求輸入進程總數和資源種類數，將進程總數設為5，資源總類數設為3，出現如圖4-1所示的界面。圖4-1系統界面圖(2)輸入max[][],allocation[][],available[]，max矩陣表示最大需求矩陣，allocation表示分配矩陣，available表示可利用資源向量。輸入各個矩陣的值。如圖4-2所示。圖4-2系統輸入數據圖(3)輸入完成并確認后，得到分配的情況，各類資源可利用的資源數為｛332｝，可以輸出一個安全序列{p1,p3,p4,p0,p2}，表示該系統當前為安全狀態，如圖5-3所示。圖4-3系統輸出結果圖從圖中可知道當前資源的分配情況，各類資源可利用的資源數以及系統當前的安全性序列。(4)上一步的輸入提示可以輸入請求資源的進程號、該進程所請求的資源數，確認后可得到請求以后資源的分配情況、各類資源可利用的資源數以及系統當前的安全性序列{p1,p3,p4,p0,p2}，如圖5-4所示。圖4-4輸入請求資源圖(5)通過上一步的提示可以選擇是否繼續分配。輸入Y表示繼續分配，輸入N表示不再分配。五、結論銀行家算法是通過檢查試分配，求安全序列，從而判斷是否可以為申請資源的進程分配資源，從而有效地避免系統進入死鎖狀態。雖然并非所有的不安全狀態都會產生死鎖狀態，但系統進入不安全狀態時，便可能進而進入死鎖狀態后，當系統在進行資源管理時，如果對進城申請的資源分配不當，可能會使系統進入死鎖狀態，因而后面到來的進程也無法順利執行。銀行家算法中，要對當前申請資源的進程申請資源的數目進行判斷，如果可以試分配，則試求出一個安全序列，如果可以求出，則說明給這個進程分配資源后系統不會進入不安全狀態，將該進程申請的資源分配給他，若求不出安全序列，則說明將資源分配給該進程后系統會進入不安全狀態，所以就使該進程進入阻塞狀態，等待以后可以分配資源時再執行該進程，然后系統繼續服務其它進程。通過這樣一個過程，可以有效避免系統進入死鎖狀態。反之，只要系統處于安全狀態，系統便可避免進入死鎖狀態。因此，避免死鎖的實質在于:如何使系統不進入不安全狀態。第二部分：參考文獻1.湯子瀛.計算機操作系統(第三版)[M].西安電子科技大學出版社.20092.方敏.操作系統教程[M].西安電子科技大學出版社.20063.周湘貞.操作系統原理與實踐教程[M].清華出版社.20054.嚴蔚敏.數據結構(C語言版)[M].清華大學出版社.2009學生簽名：填表日期：2013年6月30日第三部分：指導教師評語第四部分：成績評定指導教師簽名：填表日期：年月日附錄#include<stdio.h>#include<stdlib.h>#include<conio.h>#definem50intno1;//進程數intno2;//資源數intr;intallocation[m][m],need[m][m],available[m],max[m][m];voidmain(){ voidcheck(); voidprint(); inti,j,p=0,q=0; charc; intrequest[m],allocation1[m][m],need1[m][m],available1[m]; printf("*******************************************************\n"); printf("*銀行家算法的設計與實現*\n");printf("*******************************************************\n"); printf("1.請輸入進程總數:"); scanf("%d",&no1); printf("2.請輸入資源種類數:"); scanf("%d",&no2);printf("3.請輸入Max矩陣:\n"); for(i=0;i<no1;i++) for(j=0;j<no2;j++) scanf("%d",&max[i][j]);//輸入已知進程最大資源需求量 printf("4.請輸入Allocation矩陣:\n"); for(i=0;i<no1;i++) for(j=0;j<no2;j++) scanf("%d",&allocation[i][j]);//輸入已知的進程已分配的資源數 for(i=0;i<no1;i++) for(j=0;j<no2;j++) need[i][j]=max[i][j]-allocation[i][j]; printf("5.請輸入Available矩陣\n"); for(i=0;i<no2;i++) scanf("%d",&available[i]);//輸入已知的可用資源數 print();//輸出已知條件 check();//檢測T0時刻已知條件的安全狀態 if(r==1)//如果安全則執行以下代碼 { do{ q=0;p=0; printf("\n請輸入請求資源的進程號(0~4)：\n"); for(j=0;j<=10;j++) { scanf("%d",&i); if(i>=no1) { printf("輸入錯誤，請重新輸入：\n"); continue; } elsebreak; } printf("\n請輸入該進程所請求的資源數request[j]:\n"); for(j=0;j<no2;j++) scanf("%d",&request[j]); for(j=0;j<no2;j++) if(request[j]>need[i][j])p=1;//判斷請求是否超過該進程所需要的資源數 if(p) printf("請求資源超過該進程資源需求量，請求失敗！\n"); else { for(j=0;j<no2;j++) if(request[j]>available[j])q=1;//判斷請求是否超過可用資//源數 if(q) printf("沒有足夠的資源分配，請求失敗！\n"); else//請求滿足條件 { for(j=0;j<no2;j++) { available1[j]=available[j]; allocation1[i][j]=allocation[i][j]; need1[i][j]=need[i][j]; /*保存原已分配的資源數，仍需要的資源數和可用的資源數*/ available[j]=available[j]-request[j]; allocation[i][j]+=request[j]; need[i][j]=need[i][j]-request[j];/*系統嘗試把資源分配給請求的進程*/ } print(); check();//檢測分配后的安全性 if(r==0)//如果分配后系統不安全 { for(j=0;j<no2;j++) { available[j]=available1[j]; allocation[i][j]=allocation1[i][j]; need[i][j]=need1[i][j]; } printf("返回分配前資源數\n"); print(); } } }printf("\n你還要繼續分配嗎？YorN?\n"); //判斷是否繼續進行資源分配 c=getche(); }while(c=='y'||c=='Y'); }}voidcheck()//安全算法函數{ intg,f,v=0,i,j; intwork[m],a[m]; boolfinish[m]; r=1; g=no1; for(i=0;i<no1;i++) finish[i]=false;//初始化進程均沒得到足夠資源數并完成 for(i=0;i<no2;i++) work[i]=available[i];//work[i]表示可提供進程繼續運行的各類資源數 do{ for(i=0;i<no1;i++) { if(finish[i]==false) { f=1; for(j=0;j<no2;j++) if(need[i][j]>work[j]) f=0; if(f