編程序模擬銀行家算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上武漢理工大學(xué)華夏學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱： 操作系統(tǒng)原理 題 目： 編程序模擬銀行家算法 系 名： 信息工程系 專業(yè)班級(jí)： 軟件1121 姓 名： 鐘偉 學(xué) 號(hào)： 指導(dǎo)教師: 蘇永紅 2014年 6 月 13 日武漢理工大學(xué)華夏學(xué)院信息工程系課 程 設(shè) 計(jì) 任 務(wù) 書課程名稱： 操作系統(tǒng)原理課程設(shè)計(jì) 指導(dǎo)教師： 蘇永紅 班級(jí)名稱： 軟件1121 開課系、教研室： 軟件與信息安全 一、課程設(shè)計(jì)目的與任務(wù)操作系統(tǒng)課程設(shè)計(jì)是操作系統(tǒng)原理課程的后續(xù)實(shí)踐課程，旨在通過一周的實(shí)踐訓(xùn)練，加深學(xué)生對(duì)理論課程中操作系統(tǒng)概念，原理和方法的理解，加強(qiáng)學(xué)生綜合運(yùn)用操作系統(tǒng)原理、Linux系

2、統(tǒng)、C語言程序設(shè)計(jì)技術(shù)進(jìn)行實(shí)際問題處理的能力，進(jìn)一步提高學(xué)生進(jìn)行分析問題和解決問題的能力，包含系統(tǒng)分析、系統(tǒng)設(shè)計(jì)、系統(tǒng)實(shí)現(xiàn)和系統(tǒng)測(cè)試的能力。學(xué)生將在指導(dǎo)老師的指導(dǎo)下，完成從需求分析，系統(tǒng)設(shè)計(jì)，編碼到測(cè)試的全過程。二、課程設(shè)計(jì)的內(nèi)容與基本要求1、課程設(shè)計(jì)題目 編程序模擬銀行家算法2、課程設(shè)計(jì)內(nèi)容本課程設(shè)計(jì)要求在Linux操作系統(tǒng)，GCC編譯環(huán)境下開發(fā)。銀行家算法是避免死鎖的一種重要方法，本實(shí)驗(yàn)要求用用c/c+語言在Linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個(gè)簡單的銀行家算法程序。加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。思想：將一定數(shù)量的資金供多個(gè)用戶周轉(zhuǎn)使用，當(dāng)

3、用戶對(duì)資金的最大申請(qǐng)量不超過現(xiàn)存資金時(shí)可接納一個(gè)新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請(qǐng)量。銀行家對(duì)客戶的借款可以推遲支付，但是能夠使客戶在有限的時(shí)間內(nèi)得到借款，客戶得到所有的借款后能在有限的時(shí)間內(nèi)歸還。用銀行家算法分配資源時(shí)，測(cè)試進(jìn)程對(duì)資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當(dāng)前進(jìn)程的申請(qǐng)，否則推遲分配，這樣能夠保證至少有一個(gè)進(jìn)程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若OS能保證所有進(jìn)程在有限的時(shí)間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。 3、設(shè)計(jì)報(bào)告撰寫格式要求：1設(shè)計(jì)題目與要求 2 設(shè)計(jì)思想 3系統(tǒng)結(jié)構(gòu) 4 數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖 5 使用說明書（

4、即用戶手冊(cè)）：內(nèi)容包含如何登錄、退出、讀、寫等操作說明6 運(yùn)行結(jié)果和結(jié)果分析（其中包括實(shí)驗(yàn)的檢查結(jié)果、程序的運(yùn)行情況）7 自我評(píng)價(jià)與總結(jié) 8 附錄：程序清單，注意加注釋（包括關(guān)鍵字、方法、變量等），在每個(gè)模塊前加注釋；三、課程設(shè)計(jì)步驟及時(shí)間進(jìn)度和場地安排本課程設(shè)計(jì)將安排在第17周, 教育技術(shù)中心。具體安排如下：第一天，下發(fā)任務(wù)書，學(xué)生查閱資料第二天，系統(tǒng)設(shè)計(jì)和原型開發(fā)第三，四天 系統(tǒng)功能實(shí)現(xiàn)第五天，系統(tǒng)調(diào)試 測(cè)試 打包和驗(yàn)收周次星期一星期二星期三星期四星期五第17周第1-8節(jié)第1-8節(jié)第1-8節(jié)第1-8節(jié)第1-8節(jié)地點(diǎn)現(xiàn)教241現(xiàn)教241現(xiàn)教241現(xiàn)教241現(xiàn)教241四、課程設(shè)計(jì)考核及評(píng)分標(biāo)準(zhǔn)

5、課程設(shè)計(jì)考核將綜合考慮學(xué)生考勤和參與度，系統(tǒng)設(shè)計(jì)方案正確性，系統(tǒng)設(shè)計(jì)和開發(fā)效果以及課程設(shè)計(jì)報(bào)告書的質(zhì)量。具體評(píng)分標(biāo)準(zhǔn)如下：設(shè)置六個(gè)評(píng)分點(diǎn)（1）設(shè)計(jì)方案正確，具有可行性、創(chuàng)新性； 25分（2）系統(tǒng)開發(fā)效果較好； 25分（3）態(tài)度認(rèn)真、刻苦鉆研、遵守紀(jì)律； 10分（4）設(shè)計(jì)報(bào)告規(guī)范、課程設(shè)計(jì)報(bào)告質(zhì)量高、參考文獻(xiàn)充分 20分（5）課程設(shè)計(jì)答辯概念清晰，內(nèi)容正確 10分（6）課程設(shè)計(jì)期間的課堂考勤、答疑與統(tǒng)籌考慮。 10分 按上述六項(xiàng)分別記分后求和，總分按五級(jí)記分法記載最后成績。優(yōu)秀（10090分），良好（8089分），中等（7079分），及格（6069分），不及格（059分）目錄1設(shè)計(jì)題目與要求1.

6、1設(shè)計(jì)題目 編程序模擬銀行家算法1.2實(shí)驗(yàn)要求 本實(shí)驗(yàn)要求用用c/c+語言在Linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個(gè)簡單的銀行家算法程序。加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。2 設(shè)計(jì)思想將一定數(shù)量的資金供多個(gè)用戶周轉(zhuǎn)使用，當(dāng)用戶對(duì)資金的最大申請(qǐng)量不現(xiàn)存資金時(shí)可接納一個(gè)新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請(qǐng)量。銀行家對(duì)客戶的借款可以推遲支付，但是能夠使客戶在有限的時(shí)間內(nèi)得到借款，客戶得到所有的借款后能在有限的時(shí)間內(nèi)歸還。用銀行家算法分配資源時(shí)，測(cè)試進(jìn)程對(duì)資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當(dāng)前進(jìn)程的申請(qǐng)，否則推遲分配，這樣能夠

7、保證至少有一個(gè)進(jìn)程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若OS能保證所有進(jìn)程在有限的時(shí)間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。3實(shí)驗(yàn)環(huán)境系統(tǒng)平臺(tái)：LINUX開發(fā)語言：C 開發(fā)工具：PC機(jī)一臺(tái)4數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖4.1死鎖避免: 定義:：系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一 4.1.1破壞“不可剝奪”條件 在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即 得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請(qǐng) 4.1.2破壞“請(qǐng)求和保持”條件 要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有

8、資源，且僅當(dāng)該進(jìn) 程所要資源均可滿足時(shí)才給予一次性分配 4.1.3破壞“循環(huán)等待”條件 采用資源有序分配法： 把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次 、序進(jìn)行，否則操作系統(tǒng)不予分配。4.2安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)： 如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。一個(gè)進(jìn)程序列P1，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài) (安全狀態(tài)一定是沒有死鎖發(fā)生的) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。4

9、.3數(shù)據(jù)結(jié)構(gòu)：（1）可利用資源向量Available是個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。（2）最大需求矩陣Max這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n&

10、#215;m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。Needi,j=Maxi,j-Allocationi,j4.4安全性檢查算法4.4.1設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH4.4.2從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH=false;NEED<=Work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)4.4.3設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Finish=true;GOTO 24.4.4如所有的進(jìn)程Finish= true，則表示

11、安全；否則系統(tǒng)不安全。4.5程序流程圖5 使用說明書 5.1首先在終端中使用vi編輯器建立c的源文件5.2然后使用gcc編輯器編譯生成可執(zhí)行文件5.3使用命令./當(dāng)前名字，來執(zhí)行6運(yùn)行結(jié)果和結(jié)果分析 6.1輸入6.2輸出6.3結(jié)果分析這次的設(shè)計(jì)數(shù)據(jù)是通過一道實(shí)際的題目來體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個(gè)進(jìn)程分配資源，看它所請(qǐng)求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個(gè)安全隊(duì)列,看系統(tǒng)是否安全.再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 7自我評(píng)價(jià)與總結(jié)在本次實(shí)驗(yàn)中我們使用了liunx變成環(huán)境，讓我們更加系統(tǒng)深入的了解了liunx，gcc編程思路和思想，

12、同時(shí)讓我更加深刻的了解銀行家算法,了解死鎖的避免和預(yù)防，對(duì)操作系統(tǒng)對(duì)資源的申請(qǐng)和釋放有了更加深刻的理解，同時(shí)在編程過程中積極的向老師同學(xué)請(qǐng)教問題與他們一起探討在系統(tǒng)中存在的問題和漏洞。深入了解了銀行家算法的資源申請(qǐng)和資源分配的過程及原則。保證系統(tǒng)處于安全狀態(tài)。 經(jīng)過本周的課程設(shè)計(jì)，我對(duì)操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多知識(shí)。 ，終于我了由于對(duì) c 語言不夠熟練，在試驗(yàn)過程中，進(jìn)行了反復(fù)的修改和調(diào)試，解銀行家算法的基本原理，并且在此次的課程設(shè)計(jì)中我又復(fù)習(xí)了一下 c 語言，加深了對(duì)它的了解，而且在課程設(shè)計(jì)的過程中我們同樣學(xué)會(huì)了如何簡單的操作與使用 Linux 操作系統(tǒng)，學(xué)習(xí)到了許多 Linux

13、操作系統(tǒng)中常用的一些密令。 這次的設(shè)計(jì)數(shù)據(jù)是通過一道實(shí)際的題目來體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個(gè)進(jìn)程分配資源，看它所請(qǐng)求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個(gè)安全隊(duì)列看系統(tǒng)是否安全.再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動(dòng)態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。而我本次課程設(shè)計(jì)就是得用銀行家算法來避免“死鎖”。銀行家算法就是一個(gè)分配資源的過程，使分配的序列不會(huì)產(chǎn)生死鎖。此算法的中心思

14、想是：按該法分配資源時(shí)，每次分配后總存在著一個(gè)進(jìn)程，如果讓它單獨(dú)運(yùn)行下去，必然可以獲得它所需要的全部資源，也就是說，它能結(jié)束，而它結(jié)束后可以歸還這類資源以滿足其他申請(qǐng)者的需要。 通過這次實(shí)驗(yàn)，我體會(huì)到銀行家算法的重要性，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我來學(xué)習(xí)借鑒。通過這次實(shí)踐，我知道，要做一個(gè)課程設(shè)計(jì)，如果知識(shí)面只是停留在書本上，是不可能把課成設(shè)計(jì)完全地做好。在課程設(shè)計(jì)中，很多C語言的知識(shí)都忘了，每次的課程設(shè)計(jì)中都能將以前的知識(shí)順便再復(fù)習(xí)一遍，課程設(shè)計(jì)是給了我們一個(gè)機(jī)會(huì)去動(dòng)手和主動(dòng)復(fù)習(xí)，同時(shí)也是提醒我們應(yīng)該注重平時(shí)的積累。從課程設(shè)計(jì)以后還是要多多的動(dòng)手，在實(shí)踐中體會(huì)

15、理論知識(shí)，才能吸取經(jīng)驗(yàn)教訓(xùn)。經(jīng)過這次實(shí)驗(yàn)訓(xùn)練，我對(duì)這門課程有了更好的了解。8附錄：源程序清單#include<iostream.h>#include<string.h>#include<stdio.h>#define False 0#define True 1int Max100100=0;/各進(jìn)程所需各類資源的最大需求int Avaliable100=0;/系統(tǒng)可用資源char name100=0;/資源的名稱int Allocation100100=0;/系統(tǒng)已分配資源int Need100100=0;/還需要資源int Request100=0;/請(qǐng)求

16、資源向量int temp100=0;/存放安全序列int Work100=0;/存放系統(tǒng)可提供資源int p100=0;int q100100=0;int z100100=0;int M=100;/作業(yè)的最大數(shù)為100int N=100;/資源的最大數(shù)為100int gg=1;void showdata()/顯示資源矩陣 int i,j; cout<<endl<<"此時(shí)刻的資源分配情況為："<<endl; cout<<" Max Allocation Need Avaliable"<<endl;

17、 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<<Maxij<<" " cout<<&quo

18、t; " 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<<Avaliablej<<" "/輸出分配資源 cout<<endl; int changdata(int

19、i)/進(jìn)行資源分配 int j;for (j=0;j<M;j+) /pj=Avaliablej; Avaliablej=Avaliablej-Requestj; /qij=Allocationij; Allocationij=Allocationij+Requestj; /zij=Needij; Needij=Needij-Requestj;return 1;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=Avaliablei;cout<<

20、endl<<" 安全性檢查 "<<endl;cout<<" Work Need Allocation Work+Allocation Finish"<<endl;cout<<"進(jìn)程名 "for(h=0;h<4;h+) for(s=0;s<N;s+) cout<<names<<" " cout<<" " cout<<endl;for(i=0;i<M;i+) apply=0;

21、 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<<" " cout<<" "for(d=0;d<N;d+)cout<<Needid<<" " cout<<"

22、 "for(d=0;d<N;d+)cout<<Allocationid<<" " cout<<" " for(m=0;m<N;m+) Workm=Workm+Allocationim; cout<<Workm<<" " /變分配數(shù) Finishi=True; tempk=i;cout<<" " cout<<"true"<<" " cout<<end

23、l;i=-1; k+; flag+; for(i=0;i<M;i+) if(Finishi=False) for(j=0;j<N;j+)Avaliablej=Avaliablej+Requestj; Allocationij=Allocationij-Requestj; Needij=Needij+Requestj; cout<<endl<<"系統(tǒng)進(jìn)入不安全狀態(tài)！此時(shí)系統(tǒng)不分配資源！"<<endl;/不成功系統(tǒng)不安全 return 0; cout<<endl<<"此時(shí)系統(tǒng)是安全的!"

24、<<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 i=0,j=0;ch='y'cout<<endl<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<<M-1&l

25、t;<"):" 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>>Requestj;/輸入需要申請(qǐng)的資源 for (j=0;j<N;j+) if(Requestj>Needij)/判斷申請(qǐng)是否大于需求，若大于則出錯(cuò) cout<<end

26、l<<"進(jìn)程 "<<i<<"申請(qǐng)的資源大于它需要的資源" cout<<" 分配不合理，不予分配！"<<endl; ch='n' break; else if(Requestj>Avaliablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則 /出錯(cuò) cout<<endl<<"進(jìn)程"<<i<<"申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源" cout<<" 分配出

27、錯(cuò)，不予分配!"<<endl; ch='n' break; if(ch='y') changdata(i);/根據(jù)進(jìn)程需求量變換資源 showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源 safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 int main()/主函數(shù) int t=1,i,j,number,choice,m,n,flag;char ming;cout<<"*銀行家算法的設(shè)計(jì)與實(shí)現(xiàn)*"<<endl;cout<<endl<<"請(qǐng)首先輸入系統(tǒng)可供資源種類

28、的數(shù)量:"cin>>n;N=n;for(i=0;i<n;i+) cout<<"資源"<<i+1<<"的名稱:" cin>>ming; namei=ming; cout<<"資源的數(shù)量:" cin>>number; Avaliablei=number;cout<<endl;cout<<"請(qǐng)輸入作業(yè)的數(shù)量:"cin>>m;M=m;cout<<endl<<"請(qǐng)輸入各進(jìn)程的最大需求量("<<m<<"*"<<n<<"矩陣)Max:"<<endl;for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>