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

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：銀行家算法院 （系）：專業(yè)：班級(jí)：學(xué)生：學(xué)號(hào)：指導(dǎo)教師：2010 年 12 月操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：銀行家算法院 （系）：專業(yè)：班級(jí)：學(xué)生：學(xué)號(hào)：指導(dǎo)教師：2010 年 12 月銀行家算法摘 要本次的課程設(shè)計(jì)容是銀行家算法， 在操作系統(tǒng)當(dāng)中， 由于競(jìng)爭(zhēng)非剝奪性資源和進(jìn)程推進(jìn)的不當(dāng)，對(duì)系統(tǒng)的安全造成威脅， 所以，銀行家算法就是為了避免對(duì)系統(tǒng)產(chǎn)生死鎖而存在的。銀行家算法包括對(duì)請(qǐng)求資源的試分配和對(duì)安全性的考量，當(dāng)系統(tǒng)的安全性不能夠滿足的時(shí)候，則對(duì)系統(tǒng)進(jìn)行保護(hù)。在編寫銀行家算法的時(shí)候需要定義 Need（需求矩陣），Allocation （分配矩陣）， Max（最大需求矩陣

2、）以及 Available （可利用資源量）。在實(shí)現(xiàn)一系列的功能的時(shí)候使用的數(shù)組的結(jié)構(gòu)， 便于進(jìn)行矩陣的加減運(yùn)算， 可以提高程序的運(yùn)行效率。通過編寫可以基本上實(shí)現(xiàn)銀行家算法所要達(dá)到的基本目的， 在輸入正確的情況下能夠輸出正確的安全序列， 在不安全的情況下可以做出提醒， 并且恢復(fù)原有輸入數(shù)據(jù)。關(guān)鍵字： 銀行家算法最大需求矩陣分配矩陣需求矩陣可利用資源量目錄.i112.22.1 問題描述.2）2.2 產(chǎn)生條件.2）2.3 運(yùn)行環(huán)境.2）2.4 程序功能.2）3.33.1程序模塊.3）3.2模塊調(diào)用關(guān)系.3）3.3數(shù)據(jù)結(jié)構(gòu).3）3.4算法細(xì)想.4）4.54.1模塊劃分.5）4.2數(shù)據(jù)判斷. 5）4.

3、3函數(shù)調(diào)用.5）4.4程序流程圖.6）5.85.1程序調(diào)試.8）5.2程序測(cè)試.(8)6.(9)7.(10)(11)1 緒論銀行家算法是操作系統(tǒng)當(dāng)中為避免鎖死的算法， 并且是最具有代表性的避免鎖死的算法，能夠有效的在資源分配的過程中， 對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)。 整個(gè)算法的計(jì)算步驟為對(duì)輸入的數(shù)據(jù)進(jìn)行試分配， 并對(duì)安全性進(jìn)行檢測(cè)， 當(dāng)系統(tǒng)為安全的時(shí)，依照安全序列執(zhí)行程序， 如果不安全則進(jìn)入阻塞狀態(tài)。 銀行家算法的來源是在銀行中， 客戶申請(qǐng)貸款的數(shù)量是有限的， 每個(gè)客戶在第一次申請(qǐng)貸款時(shí)要聲明完成該項(xiàng)目所需的最大資金量，在滿足所有貸款要求時(shí)，客戶應(yīng)及時(shí)歸還。銀行家在客戶申請(qǐng)的貸款數(shù)量不超過自己擁有的

4、最大值時(shí)， 都應(yīng)盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當(dāng)于要申請(qǐng)資源的進(jìn)程。在避免死鎖的方法中， 所施加的簡直條件比在預(yù)防死鎖的方法中限制條件要弱，有可能獲得令人滿意的系統(tǒng)性能。 在該方法中， 把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，就可避免死鎖的發(fā)生。所謂安全狀態(tài)與不安全狀態(tài)是指如果所有過程有可能完成執(zhí)行（終止） ，則一個(gè)狀態(tài)被認(rèn)為是安全的。 由于系統(tǒng)無法知道什么時(shí)候一個(gè)過程將終止， 或者之后它需要多少資源， 系統(tǒng)假定所有進(jìn)程將最終試圖獲取其聲明的最大資源并在不久之后終止。2 需求分析2.1問題描述：在多道程序系統(tǒng)中，雖然能

5、夠借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量，但是依然有風(fēng)險(xiǎn)存在，那就是鎖死。所謂鎖死是指，多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程的這種僵持狀態(tài)時(shí)，若無外力作用，它們將無法再向前推進(jìn)。一組程序中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中的另一進(jìn)程所占有的資源， 因而永遠(yuǎn)無法得到資源， 這種現(xiàn)象就叫做進(jìn)程死鎖。2.2產(chǎn)生條件：1、進(jìn)程間競(jìng)爭(zhēng)非剝奪性資源2、2.3運(yùn)行環(huán)境Visual C+ 6.02.4程序功能在該程序中應(yīng)該具有以下功能：1、從外界輸入進(jìn)程數(shù)，資源數(shù)以及完成銀行家算法的所需的各類資源數(shù)。2、當(dāng)輸入越界或者非法輸入時(shí)能夠提示錯(cuò)誤。3、當(dāng)進(jìn)程推進(jìn)處于不安全狀態(tài)

6、時(shí)要能夠進(jìn)行提示處于不安全狀態(tài)，并且能夠恢復(fù)數(shù)據(jù)到初始狀態(tài)。當(dāng)請(qǐng)求資源量大于可利用資源數(shù)時(shí)要能夠進(jìn)行提醒，并且重新輸入。4、當(dāng)數(shù)據(jù)完成初始化時(shí)，要能夠輸出數(shù)據(jù)所對(duì)應(yīng)的矩陣。3 概要設(shè)計(jì)3.1 程序模塊本程序包括了四個(gè)基本模塊： 主函數(shù)、試分配、安全性測(cè)試、數(shù)據(jù)的輸入與輸出。主函數(shù)主函數(shù)用于輸出系統(tǒng)的主要操作界面，以及調(diào)用其他的函數(shù)， 完成銀行家算法。試分配：對(duì)輸入的進(jìn)程的Max、 Available、Allocation以及 Request 進(jìn)行分配，判斷是否可以正常分配。安全性測(cè)試：當(dāng)試分配完成時(shí)， 通過安全性測(cè)試來對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)， 安全時(shí)輸出安全序列，不安全時(shí)進(jìn)行提醒，并且恢復(fù)到初

7、始化時(shí)輸入的數(shù)據(jù)。3.2 模塊之間關(guān)系主函數(shù)可以調(diào)用系統(tǒng)的所有函數(shù)，以及輸出功能界面，將試分配函數(shù)，安全性測(cè)試函數(shù)和輸入輸出函數(shù)定義在主函數(shù)當(dāng)中， 在需要時(shí)通過相應(yīng)的選項(xiàng)進(jìn)行調(diào)用。而試分配與安全性測(cè)試是并列的兩個(gè)函數(shù)， 存在執(zhí)行試分配后需對(duì)安全序列進(jìn)行判斷。輸入輸出函數(shù)， 確定數(shù)值，并將相對(duì)應(yīng)的數(shù)據(jù)輸入到對(duì)應(yīng)的模塊，來進(jìn)行計(jì)算。3.3數(shù)據(jù)結(jié)構(gòu)程序當(dāng)中需要四種數(shù)據(jù)結(jié)構(gòu)。1、可利用資源矩陣（ Available ），當(dāng) Available=k 時(shí)，這表示系統(tǒng)中有該類資源 k 個(gè)。2 、最大需求矩陣（Max），當(dāng) Max=k時(shí)，則表示進(jìn)程需要的資源為k 個(gè)。3、分配矩陣（ Allocation），當(dāng)

8、 Allocation=k時(shí)，則表示進(jìn)程當(dāng)前已被分得 k 個(gè)資源。4 、需求矩陣（ Need），當(dāng) Need=k時(shí)，則表示進(jìn)程還需要k 個(gè)資源才能夠完成。3.4 算法思想操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源， 當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量， 如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源， 否則就推遲分配。 當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。 若超過則拒絕分配資源， 若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量， 若能滿足則按當(dāng)前的申請(qǐng)量分配資源，

9、否則也要推遲分配。4 詳細(xì)設(shè)計(jì)4.1程序模塊劃分：數(shù)據(jù)的初始化：根據(jù)提示輸入最大需求矩陣（Max），可利用資源量（ Available ），分配矩陣（ Allocation ）所需的數(shù)據(jù)。輸出所對(duì)應(yīng)的矩陣：根據(jù)輸入的數(shù)據(jù)輸出對(duì)應(yīng)的矩陣，并且計(jì)算出需求矩陣（Need），將完整的算法需要的數(shù)據(jù)呈現(xiàn)給操作者。試分配：根據(jù)操作者所輸入的進(jìn)程號(hào)已經(jīng)請(qǐng)求，對(duì)系統(tǒng)進(jìn)行時(shí)分配。安全測(cè)試當(dāng)試分配完成時(shí)可進(jìn)行安全性測(cè)試， 當(dāng)進(jìn)程間是安全的時(shí)候則可以輸出相應(yīng)的安全序列。如果錯(cuò)誤，則可以回到數(shù)據(jù)的初始化狀態(tài)。4.2數(shù)據(jù)判斷當(dāng)輸入的數(shù)據(jù)不符合規(guī)定時(shí)，可以對(duì)該數(shù)據(jù)進(jìn)行判斷， 不符合條件重新輸入，例如： if(!(0<

10、;=in&&in<=t-1)，在程序中，用于判斷所輸入的進(jìn)程號(hào)是否滿足要求，如果不滿足要求通過該語句輸出“ cout<<" 該進(jìn)程不存在 , 重新輸入 "<<endl; ”。4.3函數(shù)調(diào)用通過 switch 語句對(duì)所調(diào)用的函數(shù)進(jìn)行判斷。switch(choice)case 1: Input();break;/輸入相關(guān)數(shù)據(jù)函數(shù)case 2: Print();break;/打印輸出相關(guān)數(shù)據(jù)表函數(shù)case 3: cout<<"請(qǐng)輸入有請(qǐng)求的進(jìn)程號(hào) :" break；case 4: checksafe(i

11、n); break;/安全性檢查case 5: refenpei(in); break;/恢復(fù)數(shù)據(jù)4.4 程序流程圖數(shù)據(jù)初始化流程圖初始化輸入數(shù)據(jù)輸入資源數(shù)c輸入進(jìn)程數(shù)t輸入每個(gè)進(jìn)程所需要的各類資源數(shù)每個(gè)進(jìn)程已分配的各資源數(shù)提示輸入有誤！輸入可利用資源數(shù)True輸出更改后的各資源數(shù)數(shù)據(jù)初始化結(jié)束安全性流程圖銀行家算法開始函數(shù)初始化進(jìn)程提出Request（）Request （ ）<=Need()是Request （ ）<=Available()是Available()-=Request()Allocation()+=Request()Need()-=Request()安全性檢測(cè)是可以

12、分配否錯(cuò)誤否錯(cuò)誤否錯(cuò)誤！不安全Available()+=Request()Allocation()-=Request()Need()+=Request()是否再次否退出程序分配是銀行家算法結(jié)束5 測(cè)試與分析5.1 程序調(diào)試 :1、在數(shù)據(jù)初始化當(dāng)中要考慮到輸入進(jìn)程數(shù)是否為負(fù)數(shù)，是否為字符。2、在安全性算法當(dāng)中要考慮到當(dāng)不安全時(shí)，數(shù)據(jù)能否恢復(fù)，是否可以重新進(jìn)行分配。當(dāng)輸入的Request 大于 Need或者大于 Available的情況，當(dāng)大于是需要重新輸入。5.2程序測(cè)試 :輸入初始化：矩陣輸出安全序列輸出進(jìn)程不安全時(shí)6 實(shí)驗(yàn)心得操作系統(tǒng)是計(jì)算系組成當(dāng)中最為重要的系統(tǒng)軟件， 只有操作系統(tǒng)的存在在

13、能夠使得計(jì)算機(jī)能夠有正常有序的進(jìn)行工作， 操作系統(tǒng)對(duì)于計(jì)算機(jī)來說是各項(xiàng)活動(dòng)的組織者和指揮者。 而銀行家算法的存在則是為了保證這個(gè)系統(tǒng)能夠正常的安全的進(jìn)行工作的保證。 我們可以把操作系統(tǒng)看成是銀行， 而銀行家算法則可以看成是銀行的管理者，而各類資源則可以看成時(shí)銀行的資金，而進(jìn)程則是客戶。 作為管理者的銀行家算法則需要使得在銀行的資金， 即操作系統(tǒng)的資源進(jìn)行正常有序的分配，以保證操作系統(tǒng)能夠正常運(yùn)轉(zhuǎn)。 并保證在進(jìn)程有足夠的資源進(jìn)行運(yùn)轉(zhuǎn)。操作系統(tǒng)按照銀行家制定的規(guī)則進(jìn)行資源分配，當(dāng)進(jìn)程首次申請(qǐng)資源是，要測(cè)試進(jìn)程對(duì)最遠(yuǎn)的最大需求是多少， 如果系統(tǒng)現(xiàn)有的資源能夠滿足， 則最該進(jìn)程分配資源，否則推遲分配。

14、當(dāng)進(jìn)程在執(zhí)行過程，依然要求分配資源時(shí)，則先測(cè)試該進(jìn)程已占用的資源數(shù)與需求數(shù)是否超過了該進(jìn)程的最大需求。 若超過，應(yīng)該拒絕分配資源。銀行家算法作為系統(tǒng)資源的保障，起著舉足輕重的作用，所以多銀行家算法必須有深入的了解，從而認(rèn)識(shí)操作系統(tǒng)的工作過程。7 參考文獻(xiàn)1 計(jì)算機(jī)操作系統(tǒng)（第三版） 湯小丹 梁紅兵 哲鳳屏 湯子瀛 編著 電子科技大學(xué)2 軟件工程王長元 晉惠 等編著 地圖3 操作系統(tǒng)原理 孟慶昌 等編著 機(jī)械工業(yè)附錄：源程序清單：#include <iostream.h>#define M 10 / #define N 50 /資源類數(shù)進(jìn)程數(shù)void Input(); /用于輸入的函

15、數(shù)void Print(); /用于打印輸出表格的函數(shù)void tryfenpei(int i);/試分配函數(shù)void checksafe(int x);/安全檢測(cè)函數(shù)void refenpei(int i);/恢復(fù)數(shù)據(jù)函數(shù)/ 定義初始化數(shù)組int AvailableM,MaxNM,int c,t;/資源進(jìn)程int in;/用戶選擇的進(jìn)程號(hào)/*-*/void main( )int choice;char ch='Y'cout<<" 輸入資源數(shù)： "cin>>c;cout<<" 輸入進(jìn)程數(shù)： "cin&g

16、t;>t;doif(ch='Y'|ch='y')cout<<" 銀行家算法 "<<endl;cout<<"1: 輸入所需數(shù)據(jù)"<<endl;cout<<"2: 顯示矩陣"<<endl;cout<<"3: 試分配"<<endl;cout<<"4: 檢查安全性"<<endl;cout<<"5: 恢復(fù)數(shù)據(jù)到初始狀態(tài)"

17、;<<endl;cout<<"*"<<endl;cout<<" 請(qǐng)選擇操作序號(hào)： "cin>>choice;switch(choice)case 1: Input();/輸入相關(guān)數(shù)據(jù)函數(shù)break;case 2: Print();/打印輸出相關(guān)數(shù)據(jù)表函數(shù)break;case 3:cout<<" 請(qǐng)輸入有請(qǐng)求的進(jìn)程號(hào) :"while(cin>>in)if(!(0<=in&&in<=t-1)cout<<"

18、該進(jìn)程不存在 , 重新輸入 "<<endl;else break;tryfenpei(in);/break;case 4: checksafe(in);/break;case 5: refenpei(in);/break;default: cout<<"請(qǐng)(1-5)break;試分配安全性檢查恢復(fù)數(shù)據(jù)中選擇正確的操作序號(hào)!"<<endl;cout<<" 要繼續(xù)進(jìn)行嗎 ?（ y- 是 n 否） "else if(ch='N'|ch='n')cout<<&q

19、uot; 正在退出 ."<<endl;break;elsecout<<"輸入無效 ! 重新輸入 ."<<endl;while(cin>>ch);/*-main-*/函數(shù)結(jié)束/*- -*/輸入函數(shù)void Input()int j,n,m;cout<<" 輸入 可利用資源 :"<<endl;for(j=0;j<c;j+)/cout<<"請(qǐng)輸入 Available"<<j<<":"while(ci

20、n>>Availablej)if(Availablej<0)cout<<" 輸入數(shù)字無效，請(qǐng)重新輸入"<<endl;else break;cout<<" 輸入 最大需求 :"<<endl;for(n=0;n<t;n+)/各個(gè)進(jìn)程循環(huán)輸入for(m=0;m<c;m+)/c個(gè)類資源 ABC循環(huán)輸入while(cin>>Maxnm)if(Maxnm<0)cout<<" 輸入數(shù)字無效，請(qǐng)重新輸入"<<endl;else br

21、eak;cout<<" 輸入 占有資源 :"<<endl;for(n=0;n<t;n+)/各個(gè)進(jìn)程循環(huán)輸入for(m=0;m<c;m+)/c個(gè)類資源 ABC循環(huán)輸入while(cin>>Allocationnm)if(Allocationnm<0)cout<<" 輸入數(shù)字無效，請(qǐng)重新輸入"<<endl;else break;Neednm=Maxnm-Allocationnm;cout<<" 初始化完成 !."<<endl;/*-輸入函

22、數(shù)結(jié)束-*/*-*/void Print()輸出函數(shù)int i,j;cout<<"|*|*|*|*|*|"<<endl;cout<<"|*|"<<endl;cout<<"|進(jìn)程 |"<<endl;|Max| Allocation |Need| Availablecout<<"|*|*|*|*|*|"<<endl;for(i=0;i<t;i+)cout<<"| p"<<i&

23、lt;<" | "for(j=0;j<c;j+)cout<<Maxij<<""cout<<"| "for(j=0;j<c;j+)cout<<Allocationij<<""cout<<"| "for(j=0;j<c;j+)cout<<Needij<<" "cout<<"| "if(i=0)for(j=0;j<c;j+)c

24、out<<Availablej<<""cout<<"| "if(i>0)cout<<"|"cout<<endl;cout<<"|*|*|*|*|*|"<<endl;/*-*/輸出函數(shù)結(jié)束/*- -*/ void tryfenpei(int n) 試分配函數(shù)int i;cout<<" 您輸入的是 "<<"p"<<n<<""

25、<<" 進(jìn)程 "<<endl; cout<<" 該進(jìn)程需求量為： "for(i=0;i<c;i+)cout<<Needni<<" "cout<<endl;cout<<"請(qǐng)輸入請(qǐng)求資源的數(shù)目:"for(i=0;i<c;i+)while(cin>>Requesti)if (Requesti<0)cout<<"!輸入的數(shù)字無效 ."<<endl;else if (R

26、equesti>Needni)cout<<"!超出進(jìn)程需求量 "<<endl<<endl;else if (Requesti>Availablei)cout<<"!系統(tǒng)沒有足夠的可用資源量滿足進(jìn)程需要"<<endl<<endl;else break;cout<<"輸入成功，輸入的是："for(int f=0;f<c;f+)cout<<Requestf<<" "cout<<endl

27、;cout<<"執(zhí)行銀行家算法，進(jìn)行試分配."<<endl;for( f=0;f<c;f+)Availablef = Availablef - Requestf;Allocationnf = Allocationnf + Requestf;Neednf = Neednf-Requestf;cout<<"試分配完成 !"<<endl;/*-試分配函數(shù)結(jié)束-*/*- -*/安全檢測(cè)函數(shù)void checksafe(int x)cout<<" 進(jìn)入安全性檢測(cè) ."<<endl;int i,m,apply,j,k=0,flag=0;int WorkM,tempN;bool FinishN; /t為進(jìn)程數(shù)for(i=0;i<c;+i)Worki=Availablei;for(i=0;i<t;i+)Finishi=false;for(i=0;i<t;i+)apply=0;for(j=0;j<c;j+)if (false=Finishi && Needij<=Workj)apply+;/標(biāo)記是否所需的資源都得到滿足if(apply=c)for(m=0;m<c;m+)Work