銀行家算法報(bào)告和代碼(共20頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程設(shè)計(jì)（論文）題 目： 銀行家算法 院 （系）： 信息與控制工程系 專業(yè)班級(jí)： 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 2016年 1 月 15日專心-專注-專業(yè)西安建筑科技大學(xué)華清學(xué)院課程設(shè)計(jì)（論文）任務(wù)書(shū)專業(yè)班級(jí)： 學(xué)生姓名： 指導(dǎo)教師（簽名）： 一、課程設(shè)計(jì)（論文）題目銀行家算法：設(shè)計(jì)一個(gè)n個(gè)并發(fā)進(jìn)程共享m個(gè)系統(tǒng)資源的程序以實(shí)現(xiàn)銀行家算法。二、本次課程設(shè)計(jì)（論文）應(yīng)達(dá)到的目的操作系統(tǒng)課程實(shí)踐性比較強(qiáng)。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件

2、工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。本題目要達(dá)到目的：了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配情況。掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。三、本次課程設(shè)計(jì)（論文）任務(wù)的主要內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計(jì)要求等） 要求：1）能顯示當(dāng)前系統(tǒng)資源的占用和剩余情況。2）為進(jìn)程分配資源，如果進(jìn)程要求的資源大于系統(tǒng)剩余的資源，不與分配并且提示分配不成功；3）撤銷作業(yè)，釋放資源。編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并采用適當(dāng)?shù)乃惴?，有效地防止和避免死鎖的發(fā)生。銀行家算法分配資源的原則是：系統(tǒng)掌握每

3、個(gè)進(jìn)程對(duì)資源的最大需求量，當(dāng)進(jìn)程要求申請(qǐng)資源時(shí)，系統(tǒng)就測(cè)試該進(jìn)程尚需資源的最大量，如果系統(tǒng)中現(xiàn)存的資源數(shù)大于或等于該進(jìn)程尚需求資源最大量時(shí)，就滿足進(jìn)程的當(dāng)前申請(qǐng)。這樣就可以保證至少有一個(gè)進(jìn)程可能得到全部資源而執(zhí)行到結(jié)束，然后歸還它所占有的全部資源供其它進(jìn)程使用。四、應(yīng)收集的資料及主要參考文獻(xiàn)： 操作系統(tǒng)經(jīng)典算法的編程實(shí)現(xiàn)資料非常豐富，可以在圖書(shū)館找書(shū)籍或在因特網(wǎng)上找資料，都很容易找到，但是大部分代碼是不全的，不能直接運(yùn)行，希望大家只是把它當(dāng)參考，編碼還是自己做。 參考文獻(xiàn)：【1】湯小丹、梁紅兵、哲鳳屏、湯子瀛 編著.計(jì)算機(jī)操作系統(tǒng)（第三版）.西安：西安電子科技大學(xué)出版社，2007.5【2】史美

4、林編.計(jì)算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程.西安：西安電子科技大學(xué)出版社，1996.8【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C+版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C+程序設(shè)計(jì)技能百練.北京：中國(guó)鐵道出版社，2004.1五、審核批準(zhǔn)意見(jiàn)教研室主任（簽字） 設(shè)計(jì)總說(shuō)明我們可以把操作系統(tǒng)看成是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存

5、的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配，若沒(méi)超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配，否則也要推遲。關(guān)鍵字：死鎖，安全序列，銀行家算法進(jìn)程目錄操作系統(tǒng)課程設(shè)計(jì)銀行家算法1.設(shè)計(jì)目的“操作系統(tǒng)”是計(jì)算機(jī)專業(yè)的核心專業(yè)課，“操作系統(tǒng)課程設(shè)計(jì)”是理解和鞏固操作系統(tǒng)基本理論、原理和方法的重要的實(shí)踐環(huán)節(jié)。 操作系統(tǒng)課程主要講述的內(nèi)容是多道操作系統(tǒng)的原理與技術(shù)，與其它計(jì)算機(jī)原理、編譯原理、匯編語(yǔ)言、計(jì)算

6、機(jī)網(wǎng)絡(luò)、程序設(shè)計(jì)等專業(yè)課程關(guān)系十分密切。本課程設(shè)計(jì)的目的綜合應(yīng)用學(xué)生所學(xué)知識(shí)，建立系統(tǒng)和完整的計(jì)算機(jī)系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握操作系統(tǒng)基本理論與管理方式。在算法基礎(chǔ)上，解決實(shí)際的管理功能的問(wèn)題，提高學(xué)生實(shí)際應(yīng)用、編程的能力。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠撰寫比較規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。2.問(wèn)題描述在死鎖的皮免責(zé)，銀行家算法把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)便可以避免發(fā)生死鎖。所謂安全狀態(tài)，是指系統(tǒng)能按某種順序?yàn)槊總€(gè)進(jìn)程分配所需資源

7、，直到最大需求，是每個(gè)進(jìn)程都可以順利完成，即可找到一個(gè)安全資源分配序列。模擬視線這個(gè)過(guò)程。3.需求分析3.1 數(shù)據(jù)需求 系統(tǒng)可分配資源量，進(jìn)程已申請(qǐng)到的資源量，進(jìn)程所需最大資源量，進(jìn)程還需要的資源量3.2 基本功能需求 此系統(tǒng)主要通過(guò)銀行家算法為進(jìn)程進(jìn)行資源的分配。3.3 非功能性需求用戶界面需求：簡(jiǎn)潔、易用、易懂、友好的用戶界面。硬件要求：裝有Visual C+6.0的計(jì)算機(jī)?？煽啃孕枨螅罕ＷC用戶在正常使用本系統(tǒng)時(shí)，用戶的操作或誤操作不會(huì)產(chǎn)生數(shù)據(jù)的丟失。4.概要設(shè)計(jì)4.1 數(shù)據(jù)結(jié)構(gòu)數(shù)組：可利用資源向量Available 最大需求矩陣Max分配矩陣Allocation 需求矩陣Need4.2

8、系統(tǒng)包含的函數(shù)void showdata()； /顯示主界面函數(shù) int safe()； /安全性算法函數(shù)void share()； /銀行家算法int main()； /主函數(shù)4.3 函數(shù)間的關(guān)系此系統(tǒng)各個(gè)函數(shù)之間相互是有聯(lián)系的，比如在主函數(shù)中會(huì)調(diào)用其他的函數(shù)，在share函數(shù)中也對(duì)前面兩個(gè)函數(shù)進(jìn)行了調(diào)用。4.4 系統(tǒng)功能模塊圖圖4-4-1 系統(tǒng)功能模塊圖5.詳細(xì)設(shè)計(jì)5.1 結(jié)構(gòu)體的詳細(xì)定義int Available50=0;int Max5050=0;int Allocation5050=0;int Need5050=0;int Request50=0;int Work50=0;char

9、name100=0;int temp50=0;int Finish50=0;5.2 系統(tǒng)函數(shù)詳細(xì)介紹void showdata()此函數(shù)主要是在確定好資源和進(jìn)程以及各進(jìn)程的最大需求量和已分配的資源后，顯示的此刻資源的分配情況。void share()此函數(shù)對(duì)申請(qǐng)的資源進(jìn)行判定，如果合法，則予以分配；如果出錯(cuò)，則不給分配。int safe()此函數(shù)當(dāng)為進(jìn)程分配資源以后，檢查這個(gè)狀態(tài)是不是安全的，如安全，則確認(rèn)分配；否則不予分配。5.3 系統(tǒng)功能模塊介紹顯示模塊：此模塊主要是顯示某時(shí)刻的資源分配情況。銀行家算法模塊：由銀行家算法對(duì)資源進(jìn)行分配，算法如下：（1）如果Requestij<or=N

10、eedi,j,便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。（2）如果Requestij<or=Availablej, 便轉(zhuǎn)向步驟3，否則，表示尚無(wú)足夠資源，Pi需等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej：= AvailablejRequestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j：= Needi,jRequestij;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試

11、探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。安全性檢查模塊：檢查資源分配后系統(tǒng)是否處于安全狀態(tài)，算法如下：（1）設(shè)置兩個(gè)向量： 工作向量Work,他表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)，Work:=Available. Finish,他表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi:=flase；當(dāng)有足夠資源分配給進(jìn)程后，再令Finishi:=True.（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=flase； Needi,j<or=Workj;若找到，執(zhí)行步驟（3），否則，執(zhí)行步驟（

12、4）。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj：= Workj+ Allocationi,j；Finishi：=true；go to step 2;（4）如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。5.4 具體模塊設(shè)計(jì)圖5-4-! 安全性算法流程圖6.調(diào)試分析(1) 測(cè)試數(shù)據(jù)：根據(jù)主界面提示，輸入資源的名稱數(shù)量和進(jìn)程的數(shù)量以及進(jìn)程所需的最大需求量和已分配的資源，然后進(jìn)行觀察。(2) 算法改進(jìn)設(shè)想：在程序設(shè)計(jì)前期，代碼運(yùn)行語(yǔ)法部分沒(méi)有出現(xiàn)問(wèn)題，但是在運(yùn)行時(shí)，在輸入已分配資源那塊出現(xiàn)問(wèn)題，經(jīng)過(guò)

13、不斷地修改和請(qǐng)教，終于成功運(yùn)行出來(lái)。7.使用說(shuō)明圖7-1 系統(tǒng)界面圖圖7-2資源分配圖圖7-3 安全性檢查圖圖7-4 預(yù)分配資源圖圖7-5預(yù)分配資源安全檢查圖圖7-6 預(yù)分配資源出錯(cuò)圖8.設(shè)計(jì)總結(jié)此次操作系統(tǒng)課程設(shè)計(jì)，實(shí)現(xiàn)了銀行家算法，他是避免死鎖的重要方法。其中，我學(xué)到了很多的東西。首先，接到設(shè)計(jì)題目之后，在對(duì)本題目進(jìn)行分析的時(shí)候，我懂得了一個(gè)很重要的道理，那就是說(shuō)一個(gè)程序的產(chǎn)生需要一個(gè)對(duì)題目要求有一個(gè)正確全面的分析。其次，就該考慮程序算法的問(wèn)題了，一個(gè)好的算法是一個(gè)好程序的靈魂，也決定了一個(gè)程序的質(zhì)量。通過(guò)課程設(shè)計(jì)，我加深了對(duì)操作系統(tǒng)這門課的認(rèn)識(shí)。使自己對(duì)軟件的使用能力得到提升。通過(guò)操作系

14、統(tǒng)這門課的課程設(shè)計(jì)，我更加知道了實(shí)踐的重要性。在做課設(shè)的過(guò)程當(dāng)中，遇到了很多的問(wèn)題。比如，在運(yùn)行程序時(shí)，輸入已分配資源時(shí)出現(xiàn)問(wèn)題，怎么調(diào)都調(diào)不正確，于是及時(shí)向郭同學(xué)請(qǐng)求幫助，她認(rèn)真地對(duì)待并且解決了問(wèn)題，使我能夠及時(shí)地明白哪里不對(duì)并且改正。課程設(shè)計(jì)幾天的時(shí)間下來(lái)，對(duì)操作系統(tǒng)這門課有了更深的了解，它是一門很重要的課程，算法比較多，需要我們很好地去掌握。而且在過(guò)程當(dāng)中，我們也好地復(fù)習(xí)了c語(yǔ)言這門課，在計(jì)算機(jī)領(lǐng)域，很多課程都是相互聯(lián)系的，相互交叉的，所以我們應(yīng)該認(rèn)真地對(duì)待每一門課程。這次的課設(shè)讓我明白，以后一定要自己多動(dòng)手做，這樣才能印象深刻，才能更好地掌握這門課。9.參考文獻(xiàn)【1】湯小丹、梁紅兵、哲

15、鳳屏、湯子瀛 編著.計(jì)算機(jī)操作系統(tǒng)（第三版）.西安：西安電子科技大學(xué)出版社，2007.5【2】史美林編.計(jì)算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程.西安：西安電子科技大學(xué)出版社，1996.8【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C+版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C+程序設(shè)計(jì)技能百練.北京：中國(guó)鐵道出版社，2004.1 10程序源代碼#include<stdio.h>#include<iostream.h>#include<string.h>#define f

16、alse 0#define true 1int Available50=0;int Max5050=0;int Allocation5050=0;int Need5050=0;int Request50=0;int Work50=0;char name100=0;int temp50=0;int Finish50=0;int M=50; / 作業(yè)最大數(shù) int N=50; /資源最大數(shù)void showdata()int i,j;cout<<"此時(shí)刻的資源分配情況為:"<<endl;cout<<endl;cout<<"

17、; Max Allocation Need Available "<<endl;cout<<"進(jìn)程名 "for(j=0;j<4;j+)for(i=0;i<N;i+)cout<<namei<<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<Ma

18、xij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" "for(j=0;j<N;j+)cout<<Needij<<" "if(i=0)cout<<" "for(j=0;j<N;j+)cout<<Availablej<<" "cout<<e

19、ndl;int safe()/安全性算法int i,d,k=0,m,h,s,apply,Finish100=0;int j;int flag=0;for(i=0;i<N;i+)Worki=Availablei;cout<<endl<<" 安全性檢查 "<<endl;cout<<" Work Need Allocation Work+Allocation Finish"<<endl;cout<<"進(jìn)程名 "for(h=0;h<4;h+)for(s=0;s

20、<N;s+)cout<<names<<" "cout<<" "cout<<endl;for(i=0;i<M;i+) apply=0;for(j=0;j<N;j+)if (Finishi=false&&Needij<=Workj) apply+;if(apply=N) cout<<" "<<i<<" "for(d=0;d<N;d+)cout<<Workd<<&quo

21、t; "cout<<" "for(d=0;d<N;d+)cout<<Needid<<" "cout<<" "for(d=0;d<N;d+)cout<<Allocationid<<" "cout<<" "for(m=0;m<N;m+) Workm=Workm+Allocationim;cout<<Workm<<" "/變分配數(shù)Finishi=t

22、rue;tempk=i;cout<<" "cout<<"true"<<" "cout<<endl;i=-1; k+;flag+;for(i=0;i<M;i+)if(Finishi=false)for(j=0;j<N;j+)Availablej=Availablej+Requestj;Allocationij=Allocationij-Requestj;Needij=Needij+Requestj;cout<<endl<<"系統(tǒng)進(jìn)入不安全狀態(tài)！

23、此時(shí)系統(tǒng)不分配資源！"<<endl;/不成功系統(tǒng)不安全return 0;cout<<endl<<"此時(shí)系統(tǒng)是安全的!"<<endl;/如果安全，輸出成功 cout<<"安全序列為:"for(i=0;i<M;i+)/輸出運(yùn)行進(jìn)程數(shù)組cout<<tempi;if(i<M-1) cout<<"->"cout<<endl;return 0;void share()/利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定char ch;int

24、 i=0,j=0;ch='y'int sum=0;cout<<endl<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<<M-1<<"):" cin>>i;/輸入須申請(qǐng)的資源號(hào)cout<<endl<<"請(qǐng)輸入進(jìn)程 "<<i<<" 申請(qǐng)的資源:"<<endl;for(j=0;j<N;j+)cout<<namej<<":"cin>>

25、Requestj;/輸入需要申請(qǐng)的資源for (j=0;j<N;j+)if(Requestj>Needij) cout<<endl<<"進(jìn)程 "<<i<<"申請(qǐng)的資源大于它需要的資源"cout<<" 分配不合理，不予分配！"<<endl;ch='n'break;else if(Requestj>Availablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則 /出錯(cuò)cout<<endl<<"進(jìn)程&quo

26、t;<<i<<"申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源"cout<<" 分配出錯(cuò)，不予分配!"<<endl;ch='n'break; if(ch='y') int o;for(o=0;o<M;o+) Availableo=Availableo-Requesto;Allocationio=Allocationio+Requesto;Needio=Needio-Requesto;/根據(jù)進(jìn)程需求量變換資源for(int p=0;p<N;p+) if(Needip=0)sum

27、+;if(sum=N) for(int u=0;u<N;u+)Availableu+=Allocationiu;Allocationiu-=Maxiu;Neediu+=Maxiu;showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 int main()/主函數(shù)int t=1,i,j,number,m,n,flag;char ming;cout<<"*銀行家算法的設(shè)計(jì)與實(shí)現(xiàn)*"<<endl;cout<<endl<<"請(qǐng)首先輸入系統(tǒng)可供資源種類的數(shù)量:"cin>>n;N=n;for(i=0;i<n;i+)cout<<"資源"<<i+1<<"的名稱