銀行家算法模擬程序設(shè)計

1、銀行家算法模擬程序設(shè)計目錄一、課程設(shè)計的目的3二、課程設(shè)計的要求3三、課程設(shè)計題目描述3四、算法流程圖41、銀行家算法流程圖42、安全性檢查算法流程圖5五、課程設(shè)計之銀行家算法原理51銀行家算法的思路52銀行家算法53安全性檢查算法（IsSafe()函數(shù)）6六、源程序結(jié)構(gòu)分析及代碼實現(xiàn)71程序結(jié)構(gòu)72數(shù)據(jù)結(jié)構(gòu)73函數(shù)聲明84. 源代碼86. 運行界面14七、課程設(shè)計的總結(jié)16一、課程設(shè)計的目的操作系統(tǒng)是計算機(jī)系統(tǒng)的核心系統(tǒng)軟件，它負(fù)責(zé)控制和管理整個系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些資源，使計算機(jī)高效的工作。操作系統(tǒng)課程設(shè)計是操作系統(tǒng)理論課的必要補充，是復(fù)習(xí)和檢驗所學(xué)課程的重要手段，本課程設(shè)計的目

2、的是綜合應(yīng)用學(xué)生所學(xué)知識，通過實驗環(huán)節(jié)，加深學(xué)生對操作系統(tǒng)基本原理和工作過程的理解，提高學(xué)生獨立分析問題、解決問題的能力，增強學(xué)生的動手能力。二、課程設(shè)計的要求1分析設(shè)計內(nèi)容，給出解決方案（要說明設(shè)計實現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。2畫出程序的基本結(jié)構(gòu)框圖和流程圖。3對程序的每一部分要有詳細(xì)的設(shè)計分析說明。4源代碼格式要規(guī)范。5設(shè)計合適的測試用例，對得到的運行結(jié)果要有分析。6設(shè)計中遇到的問題，設(shè)計的心得體會。7按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計報告。三、課程設(shè)計題目描述 銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果

3、存在一個由系統(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(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。銀行家算法：我們可以把操作系統(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)存的資源可以滿足它的最

4、大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。四、算法流程圖錯誤Requesti<=Needi?1、銀行家算法流程圖 否 是進(jìn)程Pi阻塞Requesti<=Available?否 是試分配：Available -= RequestiAllocationi += RequestiNeedi -= Requesti 試將分配作廢，恢復(fù)

5、原資源分配狀態(tài)執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài) 不安全 安全正式分配2、安全性檢查算法流程圖Work=AvailableFinishi=0找一個滿足下列條件的進(jìn)程Finishi=0且Needi<Work所有進(jìn)程的Finishi=1?未找到是不是找到系統(tǒng)處于安全狀態(tài)系統(tǒng)處于不安全狀態(tài)Work += AllocationFinishi=1五、課程設(shè)計之銀行家算法原理1銀行家算法的思路 先對用戶提出的請求進(jìn)行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。若請求合法，則進(jìn)行試分配。最后對試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來狀態(tài)，

6、拒絕申請。2銀行家算法進(jìn)程mi發(fā)出請求申請k個j資源，Request mij=k (1) Request mij<=needmij,檢查申請量是否不大于需求量,若條件不符重新輸入，不允許申請大于需求量。(2) Request mij<=availablemij，檢查申請量是否小于系統(tǒng)中的可利用資源數(shù)量,若條件不符就申請失敗，阻塞該進(jìn)程，重新申請資源。(3) 若以上兩個條件都滿足，則系統(tǒng)試探著將資源分配給申請的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablei -= Requestmii;Allocationmii += Requestmii;Needmii -= Reques

7、tmii(4) 試分配后，執(zhí)行安全性檢查，調(diào)用IsSafe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。(5) 用while 循環(huán)語句實現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請。3安全性檢查算法（IsSafe()函數(shù)）(1) 設(shè)置兩個向量：工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時，Work= Available。Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做Finishi=0；當(dāng)有足夠的資源分配給進(jìn)程時，再令Finishi

8、=1。(2) 在進(jìn)程中查找符合以下條件的進(jìn)程：條件1：Finishi=0；條件2：needij<=Workj若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)(3) 當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj= Workj+ Allocationij；Finishi=1； (4) 如果所有的Finishi=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)六、源程序結(jié)構(gòu)分析及代碼實現(xiàn)1程序結(jié)構(gòu)程序共有以下七個部分：（1） 安全性檢查IsSafe()：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。（2） 初始化算法1Read()：用于程序開

9、始進(jìn)行初始化數(shù)據(jù)，從文件中讀入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對各類資源最大需求數(shù)等。（3） 初始化算法2Input()：用于程序開始進(jìn)行初始化數(shù)據(jù)，從鍵盤上輸入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對各類資源最大需求數(shù)等。（4） Init():進(jìn)行銀行家算法模擬實現(xiàn)的模塊，調(diào)用其他各個模塊進(jìn)行銀行家算法模擬過程。（5） Menu():顯示菜單。（6） Design()：主界面設(shè)計模塊。（7） 主函數(shù)main()：逐個調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進(jìn)行2數(shù)據(jù)結(jié)構(gòu)銀行家算法中

10、用到的主要數(shù)據(jù)結(jié)構(gòu) ：int Available100 /各種資源可利用的數(shù)量int Allocation50100 /各進(jìn)程當(dāng)前已分配的資源數(shù)量int Max50100 /各進(jìn)程對各類資源的最大需求數(shù)int Need50100 /需求矩陣int Request 50100 /申請各類資源的數(shù)量int Work100 /工作向量，表系統(tǒng)可提供給進(jìn)程運行所需各類資源數(shù)量int Finish50 /表系統(tǒng)是否有足夠的資源分配給進(jìn)程，0為否，1為是int p50; /存儲安全序列int m， n; /m為進(jìn)程的數(shù)量,n為資源種類數(shù) 3函數(shù)聲明 int IsSafe();/安全性檢測void Read

11、();/從文件讀入數(shù)據(jù)void Input();/從鍵盤輸入數(shù)據(jù)void Init();/銀行家算法void Menu();/菜單void Design();/主界面設(shè)計4. 源代碼#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include <conio.h>void main() Design(); printf("請按任意鍵進(jìn)行初始化操作. n");printf("n");printf(" >>>"

12、);getch();system("cls");cout<<"請輸入進(jìn)程的數(shù)目: "cin>>m; cout<<"請輸入資源種類: " cin>>n;Menu(); int IsSafe()int i, j, k;int len=-1; /記錄安全序列的進(jìn)程個數(shù)，如果len=m，即表示處于安全狀態(tài)intWork100;for (i=0; i<n; i+) Worki = Availablei;for (i=0; i<m; i+)Finishi=0; for (i=0; i&l

13、t;m; i+) if(Finishi=1)continue;elsefor (j=0; j<n; j+)Needij = Maxij - Allocationij; if(Needij > Workj)break;if(Needij < 0) return 0;if(j=n) for (k=0; k<n; k+)Workk += Allocationik; Finishi=1; len+;plen=i;i=-1;else continue;if(len=m-1)cout<<"系統(tǒng)是安全的n"cout<<"安全序列是

14、: "for (i=0; i<=len; i+)cout<<pi;if(i!=len)cout<<"->"cout<<endl;return 1;else return 0;void Read() int i, j; FILE *fp; fp=fopen("Max.txt","r+");cout<<"從Max.txt文件中讀入數(shù)據(jù)，則每個進(jìn)程最多需要的各類資源數(shù)為:"<<endl;for(i=0;i<m;i+) for (j=0

15、;j<n;j+)fscanf(fp,"%d",&Maxij);cout<<Maxij<<" "cout<<endl;fclose(fp); fp=fopen("Allocation.txt","r+");cout<<"從Allocation.txt文件中讀入數(shù)據(jù)，則每個進(jìn)程已分配的各類資源數(shù)為:"<<endl;for(i=0;i<m;i+)for (j=0;j<n;j+)fscanf(fp,"%d&q

16、uot;,&Allocationij);cout<<Allocationij<<" " Needij = Maxij - Allocationij;cout<<endl;fclose(fp); fp=fopen("Available.txt","r+");cout<<"從Available.txt文件中讀入數(shù)據(jù)，則現(xiàn)有空閑各類資源數(shù)為:"for (i=0; i<n; i+)fscanf(fp,"%d",&Availablei)

17、;cout<<Availablei<<" " cout<<endl;fclose(fp);void Input() int i, j;cout<<"輸入每個進(jìn)程最多所需的各類資源數(shù)，按照"<<m<<"*"<<n<<"矩陣輸入"<<endl;for (i=0; i<m; i+) for (j=0; j<n; j+)cin>>Maxij; cout<<"輸入每個進(jìn)程已

18、分配的各類資源數(shù)，按照"<<m<<"*"<<n<<"矩陣輸入"<<endl;for (i=0; i<m; i+) for (j=0; j<n; j+)cin>>Allocationij;for (i=0; i<m; i+) for (j=0; j<n; j+)Needij = Maxij - Allocationij;if(Needij<0)cout<<"你輸入的第"<<i+1<<&quo

19、t;個進(jìn)程的第"<<j+1<<"個資源數(shù)錯誤，請重新輸入"<<endl;j-;continue; cout<<"請輸入現(xiàn)有未分配的各類資源數(shù)目："for (i=0; i<n; i+)cin>>Availablei;void Init()int i, mi;char ok; IsSafe();while(1) /死循環(huán)，只要括號里為非零，就一直循環(huán)這條句子。cout<<"請輸入要申請資源的進(jìn)程號(第一個進(jìn)程號為0，以此類推)"cin>>m

20、i;cout<<"請輸入該進(jìn)程所請求的各類資源的數(shù)目:" for (i=0;i<n;i+) cin>>Requestmii; for (i=0;i<n;i+) while(Requestmii>Needmii)cout<<"你輸入的請求數(shù)超過進(jìn)程的需求數(shù)，錯誤！"<<endl;break;while(Requestmii>Availablei) cout<<"你輸入的請求數(shù)超過系統(tǒng)的資源數(shù)，系統(tǒng)無法滿足！"<<endl; break;bre

21、ak; for (i=0;i<n;i+)Availablei -= Requestmii;Allocationmii += Requestmii; Needmii -= Requestmii;if(IsSafe()cout<<"系統(tǒng)成功分配資源！"<<endl;elsecout<<"系統(tǒng)未能成分配資源,收回預(yù)分配資源！"<<endl;for (i=0; i<n; i+) Availablei += Requestmii;Allocationmii -= Requestmii;Needmii +=

22、 Requestmii;for (i=0; i<m; i+)Finishi=0; cout<<"你還想再次請求分配嗎？是請按y/Y,否請按n/N: "while(1)cin>>ok;if(ok='y' | ok='Y' | ok='n' | ok='N')break;else continue; if(ok='y' | ok='Y')continue; else system("cls"); Menu(); void Menu()

23、 int code; printf("* * * * * * * * * * * * * * * * * * * * * * *n");printf("* 請選擇： *n");printf("* - *n");printf("* 1.從文件中讀入數(shù)據(jù) *n"); printf("* 2.從鍵盤輸入數(shù)據(jù) *n");printf("* 3.退出 *n");printf("* * * * * * * * * * * * * * * * * * * * * * *n&quo

24、t;);printf("請選擇操作： bb"); scanf("%d", &code);doswitch(code) case 1:Read(); Init(); break; case 2:Input(); Init(); break; case 3: system("cls"); Design(); printf("謝謝使用銀行家算法! n"); printf("n"); exit(0); break; default:cout<<"選擇錯誤！請重新選擇：&qu