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ì)內(nèi)容是銀行家算法，在操作系統(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)行效率。通過(guò)編寫可以基本上實(shí)現(xiàn)銀行家算法所要達(dá)到的基本目的，在輸入正確的情況下能夠輸出正確的安全序列，在不安全的情況下可以做出提醒，并且恢復(fù)原有輸入數(shù)據(jù)。 關(guān)鍵字：銀行家算法 最大需求矩陣 分配矩陣 需求矩陣 可利用資源量目 錄摘 要.（i）1 緒 論（1）2需求分析.（2）2.1 問(wèn)題描述.（2）2.2 產(chǎn)生條件.（2）2.3 運(yùn)行環(huán)境.（2）2.4 程序功能.（2）3 概要設(shè)計(jì).（3）3.1 程序模塊.（3） 3.2 模塊調(diào)用關(guān)系.（3） 3.3 數(shù)據(jù)結(jié)構(gòu).（3）

3、3.4 算法細(xì)想.（4）4 詳細(xì)設(shè)計(jì).（5） 4.1 模塊劃分.（5） 4.2 數(shù)據(jù)判斷.（5）4.3 函數(shù)調(diào)用.（5）4.4程序流程圖.（6）5 測(cè)試與分析.（8） 5.1程序調(diào)試.（8）5.2 程序測(cè)試.(8)6 實(shí)驗(yàn)心得 .(9)7 參考文獻(xiàn) .(10)附錄：源程序清單(11)1 緒論銀行家算法是操作系統(tǒng)當(dāng)中為避免鎖死的算法，并且是最具有代表性的避免鎖死的算法，能夠有效的在資源分配的過(guò)程中，對(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)。銀行家算法的來(lái)源是在銀行中，客戶申請(qǐng)貸款的數(shù)量

4、是有限的，每個(gè)客戶在第一次申請(qǐng)貸款時(shí)要聲明完成該項(xiàng)目所需的最大資金量，在滿足所有貸款要求時(shí)，客戶應(yīng)及時(shí)歸還。銀行家在客戶申請(qǐng)的貸款數(shù)量不超過(guò)自己擁有的最大值時(shí)，都應(yīng)盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當(dāng)于要申請(qǐng)資源的進(jìn)程。在避免死鎖的方法中，所施加的簡(jiǎn)直條件比在預(yù)防死鎖的方法中限制條件要弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，就可避免死鎖的發(fā)生。 所謂安全狀態(tài)與不安全狀態(tài)是指如果所有過(guò)程有可能完成執(zhí)行（終止），則一個(gè)狀態(tài)被認(rèn)為是安全的。由于系統(tǒng)無(wú)法知道什么時(shí)候一個(gè)過(guò)程將終止，或者

5、之后它需要多少資源，系統(tǒng)假定所有進(jìn)程將最終試圖獲取其聲明的最大資源并在不久之后終止。2 需求分析2.1 問(wèn)題描述： 在多道程序系統(tǒng)中，雖然能夠借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來(lái)改善系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量，但是依然有風(fēng)險(xiǎn)存在，那就是鎖死。所謂鎖死是指，多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程的這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們將無(wú)法再向前推進(jìn)。一組程序中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中的另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到資源，這種現(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)該具有以

6、下功能：1、 從外界輸入進(jìn)程數(shù)，資源數(shù)以及完成銀行家算法的所需的各類資源數(shù)。2、 當(dāng)輸入越界或者非法輸入時(shí)能夠提示錯(cuò)誤。3、 當(dāng)進(jìn)程推進(jìn)處于不安全狀態(tài)時(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ù)的輸入與輸出。3.1.1主函數(shù) 主函數(shù)用于輸出系統(tǒng)的主要操作界面，以及調(diào)用其他的函數(shù)，完成銀行家算法。3.1.2試分配： 對(duì)輸入的進(jìn)程的max、available、allocation以及r

7、equest進(jìn)行分配，判斷是否可以正常分配。3.1.3 安全性測(cè)試：當(dāng)試分配完成時(shí)，通過(guò)安全性測(cè)試來(lái)對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)，安全時(shí)輸出安全序列，不安全時(shí)進(jìn)行提醒，并且恢復(fù)到初始化時(shí)輸入的數(shù)據(jù)。3.2模塊之間關(guān)系主函數(shù)可以調(diào)用系統(tǒng)的所有函數(shù)，以及輸出功能界面，將試分配函數(shù)，安全性測(cè)試函數(shù)和輸入輸出函數(shù)定義在主函數(shù)當(dāng)中，在需要時(shí)通過(guò)相應(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)的模塊，來(lái)進(jìn)行計(jì)算。3.3 數(shù)據(jù)結(jié)構(gòu)程序當(dāng)中需要四種數(shù)據(jù)結(jié)構(gòu)。1、可利用資源矩陣（available），當(dāng)available

8、=k時(shí)，這表示系統(tǒng)中有該類資源k個(gè)。 2、最大需求矩陣（max），當(dāng)max=k時(shí)，則表示進(jìn)程需要的資源為k個(gè)。3、分配矩陣（allocation），當(dāng)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ù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量

9、。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。4詳細(xì)設(shè)計(jì)4.1 程序模塊劃分：4.1.1 數(shù)據(jù)的初始化：根據(jù)提示輸入最大需求矩陣（max），可利用資源量（available），分配矩陣（allocation）所需的數(shù)據(jù)。4.1.2 輸出所對(duì)應(yīng)的矩陣：根據(jù)輸入的數(shù)據(jù)輸出對(duì)應(yīng)的矩陣，并且計(jì)算出需求矩陣（need），將完整的算法需要的數(shù)據(jù)呈現(xiàn)給操作者。4.1.3 試分配：根據(jù)操作者所輸入的進(jìn)程號(hào)已經(jīng)請(qǐng)求，對(duì)系統(tǒng)進(jìn)行時(shí)分配。4.1.4 安全測(cè)試當(dāng)試分配完成時(shí)可進(jìn)行安全性測(cè)試，當(dāng)進(jìn)程間是安全的時(shí)候則可以輸出相應(yīng)

10、的安全序列。如果錯(cuò)誤，則可以回到數(shù)據(jù)的初始化狀態(tài)。4.2 數(shù)據(jù)判斷 當(dāng)輸入的數(shù)據(jù)不符合規(guī)定時(shí)，可以對(duì)該數(shù)據(jù)進(jìn)行判斷，不符合條件重新輸入，例如：if(!(0=in&in=t-1)，在程序中，用于判斷所輸入的進(jìn)程號(hào)是否滿足要求，如果不滿足要求通過(guò)該語(yǔ)句輸出“cout該進(jìn)程不存在,重新輸入endl;”。4.3 函數(shù)調(diào)用通過(guò)switch語(yǔ)句對(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: che

11、cksafe(in); break;/安全性檢查case 5: refenpei(in); break;/恢復(fù)數(shù)據(jù) 4.4程序流程圖4.4.1數(shù)據(jù)初始化流程圖提示輸入有誤！輸入可利用資源數(shù)每個(gè)進(jìn)程已分配的各資源數(shù)輸入每個(gè)進(jìn)程所需要的各類資源數(shù)初始化輸入數(shù)據(jù)輸入進(jìn)程數(shù)t輸入資源數(shù)c數(shù)據(jù)初始化結(jié)束true輸出更改后的各資源數(shù)4.4.2安全性流程圖銀行家算法開(kāi)始是銀行家算法結(jié)束退出程序否是否再次分配available()+=request() allocation()-=request()need()+=request()錯(cuò)誤！不安全否是可以分配安全性檢測(cè)available()-=request()

12、 allocation()+=request()need()-=request()否錯(cuò)誤錯(cuò)誤否是是request（）=available()request（）=need()進(jìn)程提出request（）函數(shù)初始化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è)試: 5.2.1輸入初始化：5.2.2 矩陣輸出5.2.3 安全序列輸出5.2.4進(jìn)程不安全時(shí)6 實(shí)驗(yàn)心得操作系統(tǒng)是計(jì)算

13、系組成當(dāng)中最為重要的系統(tǒng)軟件，只有操作系統(tǒng)的存在在能夠使得計(jì)算機(jī)能夠有正常有序的進(jìn)行工作，操作系統(tǒng)對(duì)于計(jì)算機(jī)來(lái)說(shuō)是各項(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)有的資源能夠滿足，則

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

15、put(); /用于輸入的函數(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, allocationnm, neednm, requestm; int c,t;/資源進(jìn)程 int in;/用戶選擇的進(jìn)程號(hào)/*-*/void main( )int choice;char ch=y;coutc;coutt; doif(ch=y|ch=y)cout銀行家算法endl;

16、cout1:輸入所需數(shù)據(jù) endl;cout2:顯示矩陣 endl;cout3:試分配 endl;cout4:檢查安全性 endl;cout5:恢復(fù)數(shù)據(jù)到初始狀態(tài) endl;cout*endl;coutchoice;switch(choice)case 1: input();/輸入相關(guān)數(shù)據(jù)函數(shù) break;case 2: print();/打印輸出相關(guān)數(shù)據(jù)表函數(shù) break;case 3: coutin) if(!(0=in&in=t-1)cout該進(jìn)程不存在,重新輸入endl;else break; tryfenpei(in);/試分配 break;case 4: checksafe(in)

17、;/安全性檢查 break;case 5: refenpei(in);/恢復(fù)數(shù)據(jù) break;default: cout請(qǐng)(1-5)中選擇正確的操作序號(hào)!endl; break;cout要繼續(xù)進(jìn)行嗎?（y-是 n否）; else if(ch=n|ch=n)cout正在退出.endl;break;elsecout輸入無(wú)效!重新輸入.ch);/*-main函數(shù)結(jié)束-*/*-輸入函數(shù)-*/void input()int j,n,m;cout輸入 可利用資源:endl;for(j=0;jc;j+)/cout請(qǐng)輸入 availablejavailablej)if(availablej0)cout輸入數(shù)字

18、無(wú)效，請(qǐng)重新輸入endl;else break;cout輸入 最大需求:endl;for(n=0;nt;n+)/各個(gè)進(jìn)程循環(huán)輸入for(m=0;mmaxnm)if(maxnm0)cout輸入數(shù)字無(wú)效，請(qǐng)重新輸入endl;else break;cout輸入 占有資源:endl;for(n=0;nt;n+)/各個(gè)進(jìn)程循環(huán)輸入for(m=0;mallocationnm)if(allocationnm0)cout輸入數(shù)字無(wú)效，請(qǐng)重新輸入endl;else break;neednm=maxnm-allocationnm; cout初始化完成!.endl;/*-輸入函數(shù)結(jié)束-*/*-輸出函數(shù)-*/void

19、 print()int i,j;cout|*|*|*|*|*|endl;cout|*| | | | |endl;cout| 進(jìn)程| max | allocation | need | available |endl;cout|*|*|*|*|*|endl;for(i=0;it;i+)cout| pi | ;for(j=0;jc;j+)coutmaxij ;cout| ;for(j=0;jc;j+) coutallocationij ;cout| ;for(j=0;jc;j+)coutneedij ;cout| ;if(i=0)for(j=0;jc;j+)coutavailablej ;cout

20、0)cout |;coutendl;cout|*|*|*|*|*|endl;/*-輸出函數(shù)結(jié)束-*/*-試分配函數(shù)-*/void tryfenpei(int n)int i;cout您輸入的是 pn 進(jìn)程endl; cout該進(jìn)程需求量為： ; for(i=0;ic;i+) coutneedni ; coutendl; cout請(qǐng)輸入請(qǐng)求資源的數(shù)目:; for(i=0;irequesti) if (requesti0) cout!輸入的數(shù)字無(wú)效.needni) cout!超出進(jìn)程需求量endlavailablei) cout!系統(tǒng)沒(méi)有足夠的可用資源量滿足進(jìn)程需要endlendl; else b

21、reak; cout輸入成功，輸入的是：;for(int f=0;fc;f+)coutrequestf ; coutendl; cout執(zhí)行銀行家算法，進(jìn)行試分配.endl;for( f=0;fc;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;ic;+i)worki