銀行家算法報告和代碼(共20頁)

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

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

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

4、林編.計算機(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è)計技能百練.北京：中國鐵道出版社，2004.1五、審核批準(zhǔn)意見教研室主任（簽字） 設(shè)計總說明我們可以把操作系統(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)存

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

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

7、，直到最大需求，是每個進(jìn)程都可以順利完成，即可找到一個安全資源分配序列。模擬視線這個過程。3.需求分析3.1 數(shù)據(jù)需求 系統(tǒng)可分配資源量，進(jìn)程已申請到的資源量，進(jìn)程所需最大資源量，進(jìn)程還需要的資源量3.2 基本功能需求 此系統(tǒng)主要通過銀行家算法為進(jìn)程進(jìn)行資源的分配。3.3 非功能性需求用戶界面需求：簡潔、易用、易懂、友好的用戶界面。硬件要求：裝有Visual C+6.0的計算機(jī)?？煽啃孕枨螅罕ＷC用戶在正常使用本系統(tǒng)時，用戶的操作或誤操作不會產(chǎn)生數(shù)據(jù)的丟失。4.概要設(shè)計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)各個函數(shù)之間相互是有聯(lián)系的，比如在主函數(shù)中會調(diào)用其他的函數(shù)，在share函數(shù)中也對前面兩個函數(shù)進(jìn)行了調(diào)用。4.4 系統(tǒng)功能模塊圖圖4-4-1 系統(tǒng)功能模塊圖5.詳細(xì)設(shè)計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ù)對申請的資源進(jìn)行判定，如果合法，則予以分配；如果出錯，則不給分配。int safe()此函數(shù)當(dāng)為進(jìn)程分配資源以后，檢查這個狀態(tài)是不是安全的，如安全，則確認(rèn)分配；否則不予分配。5.3 系統(tǒng)功能模塊介紹顯示模塊：此模塊主要是顯示某時刻的資源分配情況。銀行家算法模塊：由銀行家算法對資源進(jìn)行分配，算法如下：（1）如果Requestij<or=N

10、eedi,j,便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。（2）如果Requestij<or=Availablej, 便轉(zhuǎn)向步驟3，否則，表示尚無足夠資源，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ù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。安全性檢查模塊：檢查資源分配后系統(tǒng)是否處于安全狀態(tài)，算法如下：（1）設(shè)置兩個向量： 工作向量Work,他表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work:=Available. Finish,他表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finishi:=flase；當(dāng)有足夠資源分配給進(jìn)程后，再令Finishi:=True.（2）從進(jìn)程集合中找到一個能滿足下述條件的進(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è)計圖5-4-! 安全性算法流程圖6.調(diào)試分析(1) 測試數(shù)據(jù)：根據(jù)主界面提示，輸入資源的名稱數(shù)量和進(jìn)程的數(shù)量以及進(jìn)程所需的最大需求量和已分配的資源，然后進(jìn)行觀察。(2) 算法改進(jìn)設(shè)想：在程序設(shè)計前期，代碼運(yùn)行語法部分沒有出現(xiàn)問題，但是在運(yùn)行時，在輸入已分配資源那塊出現(xiàn)問題，經(jīng)過

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

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

15、鳳屏、湯子瀛 編著.計算機(jī)操作系統(tǒng)（第三版）.西安：西安電子科技大學(xué)出版社，2007.5【2】史美林編.計算機(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è)計技能百練.北京：中國鐵道出版社，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<<"此時刻的資源分配情況為:"<<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、此時系統(tǒng)不分配資源！"<<endl;/不成功系統(tǒng)不安全return 0;cout<<endl<<"此時系統(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()/利用銀行家算法對申請資源對進(jìn)行判定char ch;int

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

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

26、t;<<i<<"申請的資源大于系統(tǒng)現(xiàn)在可利用的資源"cout<<" 分配出錯，不予分配!"<<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è)計與實(shí)現(xiàn)*"<<endl;cout<<endl<<"請首先輸入系統(tǒng)可供資源種類的數(shù)量:"cin>>n;N=n;for(i=0;i<n;i+)cout<<"資源"<<i+1<<"的名稱