《操作系統(tǒng)--銀行家算法》 課程設計報告

《《操作系統(tǒng)--銀行家算法》 課程設計報告》由會員分享，可在線閱讀，更多相關《《操作系統(tǒng)--銀行家算法》 課程設計報告（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、《操作系統(tǒng)--銀行家算法》 課程設計報告 姓 名： 學 號： 班 級： 計科班 專 業(yè)： 目 錄 1 課程設計目的 …………………………………………………… 1 2 課程設計的要求 ………………………………………………… 1 3 課程設計題目描述 ……………………………………………… 2 4 課程設計之銀行家算法原理 …………………………………… 2 5 源程序結構分析及代碼實現(xiàn) …………………………………… 4 6 課程設計總結 …………………………………………………… 25 一、課程設計的目的 操作系統(tǒng)是計算機系統(tǒng)的核心系統(tǒng)軟件，它負責控制和管理整個系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些

2、資源，使計算機高效的工作?！恫僮飨到y(tǒng)課程設計》是《操作系統(tǒng)》理論課的必要補充，是復習和檢驗所學課程的重要手段，本課程設計的目的是綜合應用學生所學知識，通過實驗環(huán)節(jié)，加深學生對操作系統(tǒng)基本原理和工作過程的理解，提高學生獨立分析問題、解決問題的能力，增強學生的動手能力。 二、課程設計的要求 1．分析設計內(nèi)容，給出解決方案（要說明設計實現(xiàn)的原理，采用的數(shù)據(jù)結構）。 2．畫出程序的基本結構框圖和流程圖。 3．對程序的每一部分要有詳細的設計分析說明。 4．源代碼格式要規(guī)范。 5．設計合適的測試用例，對得到的運行結果要有分析。 6．設計中遇到的問題，設計的心得體會。 7．按期提交完整的程序代

3、碼、可執(zhí)行程序和課程設計報告。 三、課程設計題目描述 銀行家算法是一種最有代表性的避免死鎖的算法。 要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。 安全狀態(tài)：如果存在一個由系統(tǒng)中所有進程構成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。 不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。 那么什么是安全序列呢？ 　　安全序列：一個進程序列{P1，…，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj (j < i )當前占有資源量之和。 銀行家算法： 　　我們可以把操作系統(tǒng)

4、看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。 四、 課程設計之銀行家算法原理 1．銀行家算法的思路 先對

5、用戶提出的請求進行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。若請求合法，則進行試分配。最后對試分配后的狀態(tài)調(diào)用安全性檢查算法進行安全性檢查。若安全，則分配，否則，不分配，恢復原來狀態(tài)，拒絕申請。 2．銀行家算法中用到的主要數(shù)據(jù)結構 可利用資源向量 int Available[j] j為資源的種類。 最大需求矩陣 int Max[i][j] i為進程的數(shù)量。 分配矩陣 int Allocation[i][j] 需求矩陣 int need[i][j]= Max[i][j]- Allocation[i][j] 申請各類資源數(shù)量 int Request i[j] i進程申請j資

6、源的數(shù)量 工作向量 int Work[x] int Finish[y] 3．銀行家算法bank() 進程i發(fā)出請求申請k個j資源，Request i[j]=k (1)檢查申請量是否不大于需求量：Request i[j]<=need[i,j],若條件不符重新輸入，不允許申請大于需求量。 (2)檢查申請量是否小于系統(tǒng)中的可利用資源數(shù)量：Request i[j]<=available[i,j]，若條件不符就申請失敗，阻塞該進程，用goto語句跳轉(zhuǎn)到重新申請資源。 (3)若以上兩個條件都滿足，則系統(tǒng)試探著將資源分配給申請的進程，并修改下面數(shù)據(jù)結構中的數(shù)值： Available[i,j]= Avai

7、lable[i,j]- Request i[j]； Allocation[i][j]= Allocation[i][j]+ Request i[j]； need[i][j]= need[i][j]- Request i[j]； (4)試分配后，執(zhí)行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程；否則本次試探分配作廢，恢復原來的資源分配狀態(tài)，讓該進程等待。 (5)用do{…}while 循環(huán)語句實現(xiàn)輸入字符y/n判斷是否繼續(xù)進行資源申請。 4．安全性檢查算法（safe()函數(shù)） (1)設置兩個向量： 工作向量Work，它表示系統(tǒng)可提供給

8、進程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時，Work= Available。 Finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]=0；當有足夠的資源分配給進程時，再令Finish[i]=1。 (2)在進程中查找符合以下條件的進程： 條件1：Finish[i]=0； 條件2：need[i][j]<=Work[j] 若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4) (3)當進程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=1；

9、goto step 2； (4)如果所有的Finish[i]=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。 五、源程序結構分析及代碼實現(xiàn) 1．程序結構 程序共有以下五個部分： (1) .初始化chushihua()：用于程序開始進行初始化輸入數(shù)據(jù)：進程數(shù)量、資源種類、各種資源可利用數(shù)量、各進程的各種資源已分配數(shù)量、各進程對各類資源最大需求數(shù)等。 (2).當前安全性檢查safe()：用于判斷當前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。 (3).銀行家算法bank()：進行銀行家算法模擬實現(xiàn)的模塊，調(diào)用其他各個模塊進行銀行家算法模擬過程。 (4).顯示當前狀態(tài)show()：

10、顯示當前資源分配詳細情況，包括：各種資源的總數(shù)量(all)、系統(tǒng)目前各種資源可用的數(shù)量、各進程已經(jīng)得到的資源數(shù)量、各進程還需要的資源量。 (5).主程序main() 逐個調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進行。 2．數(shù)據(jù)結構 程序使用的全局變量： const int x=10，y=10； //定義常量 int Available[x]; //各種資源可利用的數(shù)量 int Allocation[y][y]; //各進程當前已分配的資源數(shù)量 int Max[y][y]; //各進程對各類資源的最大需求數(shù) int Need[y][y]; //還需求矩陣 int Req

11、uest[x]; //申請各類資源的數(shù)量 int Work[x]; //工作向量，表系統(tǒng)可提供給進程運行所需各類資源數(shù)量 int Finish[y]; //表系統(tǒng)是否有足夠的資源分配給進程，0為否，1為是 int p[y]; //存儲安全序列 int i,j; //全局變量，主要用于循環(huán)語句中 int n,m; //n為進程的數(shù)量,m為資源種類數(shù) int l=0,counter=0; 3．函數(shù)聲明 void chushihua(); 　　//系統(tǒng)初始化函數(shù) void safe(); 　//安全性算法函數(shù) void bank(); //銀行家算法函數(shù) void show (); 　//輸出當前資

12、源分配情況 4．主函數(shù)main() int main() { cout<<…… //顯示程序開始提示信息 chushihua(); //初始化函數(shù)調(diào)用 cout<

13、cout<<“＼n安全的狀態(tài)!!!“<>“<<“進程“<<“(“<

14、BLE[[i]-=REQUEST[i]; ALLOCATION[i]+=REQUEST[i]; NEED[i]-=REQUEST[i]; 輸入進程的數(shù)量 輸入資源種類數(shù) 輸入個資源當前可用資源數(shù) 輸入各進程當前已分配的資源數(shù) 輸入各進程對各類資源的最大需求 輸出提示：輸入有誤，請重新輸入 初始化函數(shù)chushihua()結束，銀行家函數(shù) Bank() 提出請求REQUEST[i] Error; REQUEST[i]<=NEED[i] REQUEST[i]<=AVAILABLE[[i] Error; Safe(); 輸出提示：你的請求被拒！ AVAILABLE[i]-=REQUEST[i]；AL

15、LOCATION[i]-=REQUEST[i]; NEED[i]+=REQUEST[i]； 輸出提示：同意分配請求 是否進行再次分配 退出程序，銀行家算法Bank()結束; 安全性算法Safe()開始 Work=AVAILABLE; FINISH=false； NEED[i]<=Work&&FINISH[i]=false; Work+=ALLOCATION[i]; FINISH[i]=ture; 所有進程的FINISH=ture； 輸出提示：系統(tǒng)是不安全的 安全，輸出安全序列 Return ture； 安全算法safe()結束 2. 源程序代碼： #include #

16、include #include using namespace std; #define TRUE 1 //定義 TRUE =1 #define FALSE 0 //定義 FLASE=0 void bank(vector,vector >,vector >,int ,int ); //聲明bank（應行家算法） int safe(vector Available,vector > Need,vector > Allocation,int n

17、,int m);//聲明safe（）安全性算法 void init(); /*************************************主函數(shù)main()**************************************************************/ void main() { init(); int safe(vector Available,vector > Need,vector > Allocation,int n,int m); } /************************

18、**************初始化函數(shù)init()*********************************************************/ void init() { int m; //m資源類數(shù) int n; //進程數(shù) cout<<“輸入資源類數(shù)“<>m; vector Available(m); //動態(tài)申請數(shù)組Available可用資源向量 cout<<“輸入各類資源總數(shù):“<

19、****/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Available.txt文件中讀入數(shù)據(jù)*/ /************************************************************************/ /*/ for (int i=0;i>Available[i]; } //*/ FILE *fp; fp=fopen(“Available.txt“,“r+“); cout<<“從Available.txt文件中讀入數(shù)據(jù)，并輸出“<

20、 for(int i=0;i>n; vector > Max(n, vector(m)); /************************************************************************/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Max.txt文件中讀入數(shù)據(jù)*/ /**

21、**********************************************************************/ /* for ( i=0;i>Max[i][j]; while (Max[i][j]>Available[j]) { cout<>Max[i][j]; } } }//*/ fp=fopen(“Max

22、.txt“,“r+“); cout<<“從Max.txt文件中讀入數(shù)據(jù)，并輸出“< > Allocation(n, vector(m)); vector > Need(n, vector(m)); /

23、************************************************************************/ /* 下面的被剛掉的為在DOS下輸入資源向量*/ /*未被剛掉的是從Allocation.txt文件中讀入數(shù)據(jù)*/ /************************************************************************/ /* for ( i=0;i

24、<“類資源的數(shù)目“; cin>>Allocation[i][j]; while(Allocation[i][j]>Max[i][j]) { cout<>Allocation[i][j]; } Need[i][j]=Max[i][j]-Allocation[i][j]; Available[j] =Available[j]-Allocation[i][j]; } }//*/ fp=fopen(“Allocation.txt“,“r+“); cout<<“Allocation.txt從文件中讀入數(shù)據(jù)，并輸出“<

25、or(i=0;i Available,v

26、ector > Need,vector > Allocation,int n,int m); cout<<“此狀態(tài)安全!“< Available,vector

27、ector > Need,vector > Allocation,int n,int m) { vector Request(m); int all=0; //定義變量all，如果all==0，表示進程已經(jīng)運行完，如果all>=1，表示還有進程沒有運行完 for (int i=0;i

28、重新初始化all， while (1) { while (all==0) { all=0; //如果all==0，表示進程已經(jīng)運行完，如果all>=1，表示還有進程沒有運行完 //循環(huán)直至all>0,即找到一個未運行完的進程 cout<<“任選一個進程作為當前進程0--“<>jc; for (int j=0;j

29、>Request[i]; while(Request[i]>Need[jc][i]||Request[i]>Available[i]) { cout<<“請求向量無法滿足“<

30、location[jc][i]=Allocation[jc][i]+Request[i]; Need[jc][i]=Need[jc][i]-Request[i]; } int bb=0; bb=safe(Available,Need,Allocation,n,m);//調(diào)用安全性算法，判斷此次資源分配后，系統(tǒng)是否處安全狀態(tài) if (1==bb) { cout<<“系統(tǒng)成功分配資源“<

31、Allocation[jc][i]=Allocation[jc][i]-Request[i]; Need[jc][i]=Need[jc][i]+Request[i]; } } cout<<“您還想再次請求分配嗎?是請按y/Y,否請按其它鍵“<>again; if(again==＇y＇||again==＇Y＇) { all=0; continue; } break; } } /**************************************安全性算法safe()函數(shù)*************************************************

32、********/ int safe(vector Available,vector > Need,vector > Allocation,int n,int m) { vector Work(m),Finish(n);//申請工作向量work，finish Work=Available; vector count(n); //記錄安全序列 int len=-1; //記錄安全序列的進程個數(shù)，如果len==n，即表示所有的finish【i】=true，處于安全狀態(tài) for(int i=0;i

33、[i]=FALSE; for (i=0;i

34、1) { cout<<“系統(tǒng)是安全的“<“; } } cout<

35、應采用動態(tài)分配的策略，但是這樣就容易因資源不足，分配不當而引起“死鎖”。而我本次課程設計就是得用銀行家算法來避免“死鎖”。銀行家算法就是一個分配資源的過程，使分配的序列不會產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時，每次分配后總存在著一個進程，如果讓它單獨運行下去，必然可以獲得它所需要的全部資源，也就是說，它能結束，而它結束后可以歸還這類資源以滿足其他申請者的需要。 本次程序就是按照上面的思路展開的。但是因為時間上的倉促，本課程設計的存在著以下不足：一、不能實現(xiàn)并發(fā)操作，即當總資源同時滿足幾個進程所需要的資源數(shù)時，這些進程不能同時進行，只能一一按進程順序執(zhí)行。二、掃描進程順序單一，只能按進程到來的順序（即編號）來掃描，從而產(chǎn)生的安全順序只能是在這個順序的基礎上產(chǎn)生的，而其實安全順序是有多個的。三、對進程數(shù)和資源數(shù)進行的數(shù)量進行了限制，都只能最多有十個。四、運行程序后，界面較差，進程數(shù)，所需要資源數(shù)，已分配資源數(shù)，能用資源數(shù)，不能一目了然。 這次課程設計時間上雖說倉促點，但是我依然學到了很多的實用性知識。除了更深的了解這個算法，而且對C語言進行了復習，而且其過程中有很多的知識點都不記得了，所以在此感謝在此過程中幫助過我的老師和同學。 最后的感悟就是：只要你親自動手，你就能學到知識。 再次感謝幫助過我的老師和同學！