1、課程設(shè)計（論文）任務(wù)書 信息息工程 學(xué)院 計算機專業(yè) 3 班 一、課程設(shè)計(論文)題目目資源管理理系統(tǒng)的設(shè)計計與實現(xiàn)銀行家算算法實現(xiàn)二、課程設(shè)計(論文)工作作自 20008 年 6 月 23 日起至 2008 年 6 月 28 日止。三、課程設(shè)計(論文) 地點: 5#204 四、課程設(shè)計(論文)內(nèi)容容要求：1本課程設(shè)計計的目 配合計計算機操作系系統(tǒng)課程的的教學(xué)，通過過模擬操作系系統(tǒng)原理的實實現(xiàn)，使學(xué)生能更深刻刻地領(lǐng)會操作作系統(tǒng)工作原原理和操作系系統(tǒng)實現(xiàn)方法法的理解，并并可練習(xí)程序設(shè)計， 特開設(shè)此課課程設(shè)計。 2課程設(shè)計計的任務(wù)及要要求1）基本要求：用你熟悉語言編編程實現(xiàn)一個個資源管理系系統(tǒng)，該

2、系統(tǒng)統(tǒng)必須包括資資源的添加、刪刪除和修改等功能，并并且允許其它它進程來申請請這里的資源源，任何一個個進程來申請請資源時，必須先登登記該進程對對資源的申請請要求，然后后由系統(tǒng)檢查查當(dāng)前資源的狀況，并用銀行家算法法和安全性算算法來檢查是是否允許分配配資源給進程程。每個進程程申請資源的情況必須須進行記錄，并并作為課程設(shè)設(shè)計報告的一一部分數(shù)據(jù)。2）創(chuàng)新要求： 在基本要求達到到后，可進行行創(chuàng)新設(shè)計，如如改善算法性性能、友好的的人機界面等。3）課程設(shè)計論論文編寫要求求（1）要按照書書稿的規(guī)格打打印與寫課程程設(shè)計論文 （2）論文文包括目錄、功能描述、設(shè)計思路、具體實現(xiàn)、運行調(diào)試與分析討論、設(shè)計體會與與小結(jié)、

3、參考考文獻、附錄錄（源代碼）等等 （3）課程設(shè)計計論文裝訂按按學(xué)校的統(tǒng)一一要求完成4）答辯與評分分標(biāo)準(zhǔn)： （1）考勤與學(xué)學(xué)習(xí)態(tài)度：220分； （2）設(shè)計思路路：20分；（3）代碼實現(xiàn)現(xiàn)：20分；（4）調(diào)試與分分析：20分分；（5）回答問題題：10分；（6）論文規(guī)范范性：10分分。5）參考文獻1湯子瀛，哲哲鳳屏，湯小小丹.計算機操作作系統(tǒng).西安電子子科技大學(xué)出出版社2譚浩強 C程序設(shè)設(shè)計（第三三版） 清華華大學(xué)出版社社3 6）課程設(shè)計進進度安排內(nèi)容 天數(shù)地點 1天 5#2044 1天 5#2044 1天 5#2004學(xué)生簽名： 2008年 66 月 28 日課程設(shè)計(論文文)評審意見見（1）考勤

4、與態(tài)態(tài)度 （220分）：優(yōu)優(yōu)（）、良良（）、中中（）、一一般（）、差差（）； （2）設(shè)計思路路（200分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）代碼實現(xiàn)現(xiàn)（200分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）調(diào)試與分分析（200分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）回答問題題（100分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）論文規(guī)范范性 （110分）：優(yōu)優(yōu)（）、良良（）、中中（）、一一般（）、差差（）；評閱人： 職稱稱： 講師 2008 年66月30日目 錄TOC o 1-3 h z u HYPERLINK l _Toc202315992 緒

5、論 PAGEREF _Toc202315992 h - 3 - HYPERLINK l _Toc202315993 一、功能描述述 PAGEREF _Toc202315993 h - 3 - HYPERLINK l _Toc202315994 二、設(shè)計思路路 PAGEREF _Toc202315994 h - 3 - HYPERLINK l _Toc202315995 2.1銀行家算算法中的數(shù)據(jù)據(jù)結(jié)構(gòu) PAGEREF _Toc202315995 h - 3 - HYPERLINK l _Toc202315996 2.2銀行家算算法 PAGEREF _Toc202315996 h - 3 - H

6、YPERLINK l _Toc202315997 2.3安全性算算法 PAGEREF _Toc202315997 h 錯誤！未定定義書簽。 HYPERLINK l _Toc202315998 三、具體實現(xiàn)現(xiàn) PAGEREF _Toc202315998 h - 3 - HYPERLINK l _Toc202315999 3.1實現(xiàn)過程程 PAGEREF _Toc202315999 h 錯誤！未定定義書簽。 HYPERLINK l _Toc202316000 3.2流程圖 PAGEREF _Toc202316000 h 錯誤！未定定義書簽。 HYPERLINK l _Toc202316002 四、

7、運行調(diào)試試及結(jié)果分析析 PAGEREF _Toc202316002 h - 3 - HYPERLINK l _Toc202316005 五、設(shè)計體會會與小結(jié) PAGEREF _Toc202316005 h - 3 - HYPERLINK l _Toc202316006 六、參考文獻獻 PAGEREF _Toc202316006 h - 3 - HYPERLINK l _Toc202316007 七、附錄(源源代碼) PAGEREF _Toc202316007 h - 3 -緒 論這次課程設(shè)計要要求完成一個個資源管理系系統(tǒng)，該系統(tǒng)統(tǒng)必須包括資資源的添加、刪刪除和修改等等功能，并且且允許其它進進程

8、來申請這這里的資源，任任何一個進程程來申請資源源時，必須先先登記該進程程對資源的申申請要求，然然后由系統(tǒng)檢檢查當(dāng)前資源源的狀況，并并用銀行家算算法和安全性性算法來檢查查是否允許分分配資源給進進程。通過課課程設(shè)計，加加深我們對利利用銀行家算算法避免死鎖鎖的理解。在在設(shè)計中主要要的難點是用用語言編寫銀銀行家算法和和安全性算法法，使系統(tǒng)資資源分配能安安全進行，避避免系統(tǒng)死鎖鎖。具體要求如下下：（1）模擬擬一個銀行家家算法；（2）初始始化時讓系統(tǒng)統(tǒng)擁有一定的的資源；（3）如如果預(yù)分配后后，系統(tǒng)處于于安全狀態(tài)，則則修改系統(tǒng)的的資源分況；（4）如如果預(yù)分配后后，系統(tǒng)處于于不安全狀態(tài)態(tài)，則提示不不能滿足請求

9、求， 此次課課程設(shè)計的主主要內(nèi)容時模模擬實現(xiàn)動態(tài)態(tài)資源分配。同同時要求編寫寫和調(diào)試一個個系統(tǒng)動態(tài)資資源的簡單模模擬程序，觀觀察死鎖產(chǎn)生生的條件，并并使用適當(dāng)?shù)牡乃惴?，有效效的防止和避避免死鎖的發(fā)發(fā)生。功能描述在多道程序系統(tǒng)統(tǒng)中，雖可借借助于多個進進程的并發(fā)執(zhí)執(zhí)行，來改善善系統(tǒng)的資源源利用提高吞吞吐量，但可可能發(fā)生一種種危險死鎖。所所謂死鎖，是是指多個進程程運行中因爭爭奪資源而造造成的一種僵僵局，當(dāng)進程程處于這種僵僵持狀態(tài)時，若若無外力作用用，他們都無無法再向前推推進。雖然進程在運行行過程中，可可能發(fā)生死鎖鎖，但死鎖的的發(fā)生必須同同時具備四個個條件：互斥斥條件、請求求和保持條件件、不剝奪條條件、

10、環(huán)路等等待條件；防防止死鎖的機機構(gòu)只須確保保上述四個條條件之一不出出現(xiàn)，則系統(tǒng)統(tǒng)不會發(fā)生死死鎖。系統(tǒng)的狀態(tài)分為為安全狀態(tài)和和不安全狀態(tài)態(tài)，只要能使使系統(tǒng)都處于于安全狀態(tài)，便便可避免死鎖鎖。所謂安全全狀態(tài)，是指指系統(tǒng)能按某某種進程順序序（P1，P2，Pn），來為每每個進程Pii分配其所需需分配，直至至滿足每個進進程對資源的的最大需求，使使每個進程都都可順利地完完成。如果系系統(tǒng)無法找到到一個這樣地地安全系列，則則稱系統(tǒng)處于于不安全狀態(tài)態(tài)。在操作系統(tǒng)中研研究資源分配配策略時也有有類似的問題題，系統(tǒng)中有有限的資源要要供多個進程程使用，必須須保證得到資資源的進程能能在有限的時時間內(nèi)歸還資資源，以供它它進

11、程使用資資源。如果資資源分配不得得當(dāng)就會發(fā)生生進程循環(huán)等等待資源，各各進程都無法法繼續(xù)執(zhí)行下下去的死鎖現(xiàn)現(xiàn)象。而最有有代表性的避避免死鎖的算算法，是Diijkstrra的銀行家家算法。 銀行家算法法是避免死鎖鎖的一種重要要方法，在課課程設(shè)計中用用C語言編寫寫一個資源管管理系統(tǒng)，并并要用銀行家家算法和安全全性算法檢查查是否允許分分配資源給進進程，避免死鎖。通通過課程設(shè)計計，加深我們對了解有有關(guān)資源申請請、避免死鎖鎖等概念，并加加深我們對銀銀行家算法理理解。提高了了我們分析、解解決問題的能能力。設(shè)計思路在避免死鎖方法法中允許進程程動態(tài)地申請請資源，但系系統(tǒng)在進行資資源分配之前前，應(yīng)先計算算此次分配

12、資資源的安全性性，若分配不不會導(dǎo)致系統(tǒng)統(tǒng)進入不安全全狀態(tài)，則分分配，否則等等待。銀行家家算法是避免免死鎖的一種種重要方法，為為實現(xiàn)銀行家家算法，系統(tǒng)統(tǒng)必須設(shè)置若若干數(shù)據(jù)結(jié)構(gòu)構(gòu)。2.1銀行家算算法中的數(shù)據(jù)據(jù)結(jié)構(gòu) 1）可利用用資源向量AAvailaable是個含有m個元元素的數(shù)組，其其中的每一個個元素代表一一類可利用的的資源數(shù)目。如如果Avaiilableej=K，則表示示系統(tǒng)中現(xiàn)有有Rj類資源K個。 2）最大需求矩矩陣Max這是一個nmm的矩陣，它它定義了系統(tǒng)統(tǒng)中n個進程中的的每一個進程程對m類資源的最最大需求。如如果Maxi,j=K，則表示示進程i需要Rj類資源的的最大數(shù)目為為K。3）分配矩陣

13、AAllocaation這也是一個nm的矩陣，它它定義了系統(tǒng)統(tǒng)中每一類資資源當(dāng)前已分分配給每一進進程的資源數(shù)數(shù)。如果Alllocattioni,j=K，則表示示進程i當(dāng)前已分得得Rj類資源的數(shù)數(shù)目為K。4）需求矩陣NNeed。這也是一個nm的矩陣，用用以表示每一一個進程尚需需的各類資源源數(shù)。如果NNeedi,j=K，則表示進進程i還需要Rj類資源K個，方能完完成其任務(wù)。 Needi,j=Maxi,j-Alloocatiooni,j 2.2、銀行家家算法設(shè)Requessti是進程程Pi的請求向向量，如果RRequesstij=K，表示進程程Pi需要K個Rj類型的資資源。當(dāng)Pii發(fā)出資源請請求后，

14、系統(tǒng)統(tǒng)按下述步驟驟進行檢查：如果RequeestijNeedi,j，便便轉(zhuǎn)向步驟22；否則認為為出錯，因為為它所需要的的資源數(shù)已超超過它所宣布布最大值。1）如果ReqquestiijAvaillablej，便轉(zhuǎn)向向步驟(3)；否則， 表示尚無足足夠資源，PPi須等待。 2）系統(tǒng)試探著著把資源分配配給進程Pii，并修改下下面數(shù)據(jù)結(jié)構(gòu)構(gòu)中的數(shù)值：Availabblej=Avaiilableej-Requuestij;Allocattioni,j=Alloocatiooni,j+Requuestij; Needi,j=Needdi,j-Requuestij;3）系統(tǒng)執(zhí)行安安全性算法，檢檢查此次資源源

15、分配后，系系統(tǒng)是否處于于安全狀態(tài)。若若安全，才正正式將資源分分配給進程PPi，以完成成本次分配；否則， 將本次的試試探分配作廢廢，恢復(fù)原來來的資源分配配狀態(tài)，讓進進程Pi等待。2.3、安全性性算法1）設(shè)置兩個向向量：工作向量Worrk: 它表表示系統(tǒng)可提提供給進程繼繼續(xù)運行所需需的各類資源源數(shù)目，它含含有m個元素，在在執(zhí)行安全算算法開始時，Work=Available; 工作向量Finnish: 它表示系統(tǒng)統(tǒng)是否有足夠夠的資源分配配給進程，使使之運行完成成。開始時先先做Finiishi=falsse; 當(dāng)有有足夠資源分分配給進程時時， 再令Finiishi=truee。 2）從進程集合合中找到

16、一個個能滿足下述述條件的進程程： Finishi=falsse; Needi,jWorkj；若找到到，執(zhí)行 (3)，否則則，執(zhí)行 (4)3）當(dāng)進程Pii獲得資源后后，可順利執(zhí)執(zhí)行，直至完完成，并釋放放出分配給它它的資源，故故應(yīng)執(zhí)行：Workj=Worki+Alloocatiooni,j;Finishi=true;go to sstep 22; 4）如果所有進進程的Finnishi=truee都滿足， 則表示系統(tǒng)統(tǒng)處于安全狀狀態(tài)；否則，系系統(tǒng)處于不安安全狀態(tài)具體實現(xiàn)3.1、實現(xiàn)過過程在程序中設(shè)計五五個進程，分分別為pr00,pr1,pr2,ppr3,prr4。共享三三類資源。在在這個資源管管理系

17、統(tǒng)中對對進程的所需需最大資源(Max)、已已分配給當(dāng)前前進程資源(Alloccationn)和系統(tǒng)可可用資源(AAvailaable)分分別進行了初初始化了值。進程可動態(tài)地申請資源和釋放資源，系統(tǒng)按各進程的申請動態(tài)地分配資源。要求程序具有顯示和打印各進程的某一時刻的資源分配表和安全序列，若分配不安全，則釋放分配的資源，防止使系統(tǒng)進入不安全狀態(tài)。顯示和打印各進程依次要求申請的資源號以及為某進程分配資源后的有關(guān)資源數(shù)據(jù)。程序還可以實現(xiàn)對系統(tǒng)的修改。如果修改系統(tǒng)可用資源(Available)，和進程分配資源。程序具體的設(shè)設(shè)計是：函數(shù)數(shù)void showddata()用來顯示資資源矩陣，包包括系統(tǒng)可用

18、用資源數(shù)目，進進程對資源最最大需求數(shù)，系系統(tǒng)已分配給給進程的資源源數(shù)，進程還還需求資源。通通過以上顯示示，很直觀的的觀察到資源源分配和修改改的過程。函函數(shù)sharre()用來來利用銀行家家算法對某個個進程申請資資源對進行判判定。函數(shù)iint chhangdaata(innt i)用用來實現(xiàn)資源源試探分配。主主要執(zhí)行的步步驟是 ： Avaaliabllej=Avaliiablej-Reequesttj；Alloccationnijj=Alloocatioonij+Reequesttj；Needij=Needdijj-Reqquestj。函數(shù)safe()用來實現(xiàn)現(xiàn)安全性算法法，對分配后后的資源進行

19、行計算，若分分配資源后，系系統(tǒng)是安全的的，則資源完完成本次分配配。若不安全全將本次的試試探分配作廢廢，調(diào)用shhifangg()函數(shù)恢恢復(fù)原來的資資源分配狀態(tài)態(tài)。資源修改改功能用 RRevisiion()來來實現(xiàn)。 3.2流程程圖運行調(diào)試及結(jié)果果分析為了便于檢驗程程序的正確性性，這里用了了書上的數(shù)據(jù)據(jù)進行了初始始化。程序運運行時選擇11 ,輸入進進程pr1的的請求向量（11,0,2）經(jīng)經(jīng)過程序計算算，資源分配配成功。資源源具體分配過過程如下圖所所示。得出一一個安全序列列為pr1,pr3,ppr0,prr2,pr44。這與書上上的有點不同同，但經(jīng)過計計算，這也是是一個正確的的安全序列。對對進程提

20、出的的請求向量，系系統(tǒng)可能存在在多個安全序序列。主要是是在安全路徑的的找算法上。進程pr0請求求資源：prr0發(fā)出請求求向量(0,2,0)，由由于Requuest0不不大于Neeed0,Reequestt0不大于AAvailaable0。系系統(tǒng)試探著為為它分配資源源。由結(jié)果可知，系系統(tǒng)不安全。則則系統(tǒng)不分配配資源，并回回收系統(tǒng)預(yù)分分配給pr00的資源。程序運行時選擇擇2,進行系系統(tǒng)資源的修修改。這里選選擇修改系統(tǒng)統(tǒng)可用資源。修修改后的Avvailabble為(22,3,2)。資源修改改成功。設(shè)計體會與小結(jié)結(jié)一周的操作系統(tǒng)統(tǒng)課程設(shè)計終終于結(jié)束了，雖雖然很忙碌很很疲勞，但感感覺收獲還是是蠻大的。我

21、我?guī)缀趺刻斓牡膶Ｗ⒑托羷趧?，喚回了我我對操作系統(tǒng)統(tǒng)的重新的認認識，在編寫寫程序不斷出出現(xiàn)錯誤和改改正的過程序序中加深了我我對銀行家算算法的理解。這這個系統(tǒng)的功功能基本能滿滿足要求，完完成了對資源源的修改還有有用銀行家算算法和安全性性算法來檢查查是否允許分分配資源給進進程。在課程程設(shè)計的過程程中，通過與與同組人的相相互討論，很很多問題迎刃刃而解。讓我我從中體會到到是小組合作作的力量。設(shè)計主要由兩部部分組成：第一部分:銀行家算法(掃掃描)1.如果Reqquest=Needd,則轉(zhuǎn)向22;否則,出出錯2.如果Reqquest=Avaiilablee,則轉(zhuǎn)向33,否則等待待3.系統(tǒng)試探分分配請求的資資

22、源給進程4.系統(tǒng)執(zhí)行安安全性算法安全性算法1.設(shè)置兩個向向量(1).工作向量:Work=Availlable(表示系統(tǒng)可可提供給進程程繼續(xù)運行所所需要的各類類資源數(shù)目) (2).Finissh:表示系系統(tǒng)是否有足足夠資源分配配給進程(TTrue:有有;Falsse:沒有).初始化為為Falsee 2.若FFinishhi=FFalse&Needd=Worrk,則執(zhí)行行3;否則執(zhí)執(zhí)行4(I為為資源類別) 3.進程程P獲得第ii類資源,則則順利執(zhí)行直直至完成!并并釋放資源: Workk=Workk+Alloocatioon; Finiishi=truee; 轉(zhuǎn)2 4. 若若所有進程的的Finiss

23、hi=true,則表示系統(tǒng)統(tǒng)安全;否則則,不安全!第二部分主要是是進行資源的的修改。在這這里可以修改改資源的可用用資源和資源源還需求資源源。由于時間間有限，還不不是很完善，系系統(tǒng)還有許多多不盡人意的的地方。這些些都有待進一一步改善參考文獻1湯子瀛，哲哲鳳屏，湯小小丹.計算機機操作系統(tǒng).西安：西安安電子科技大大學(xué)出版社，220052 譚浩強強 C程序設(shè)設(shè)計（第三三版） 清華華大學(xué)出版社社3 附錄(源代碼)#includde#includde#definee M 5 /定義義進程數(shù) #definee N 3 /定義資源數(shù)數(shù) #definee Falsse 0#definee Truee 1int

24、Maxx3=7,5,3,3,2,2,99,0,2,2,22,2,4,3,33;int Avaaliablle=3,3,22; /系統(tǒng)可用資資源int Alllocatiion3=0,1,00,2,0,0,3,0,2,22,1,1,0,00,2;/系統(tǒng)已已分配資源int Neeed33=77,4,3,1,22,2,6,0,00,0,1,1,4,3,1;/還需要資資源int Reqquest3;void shhowdatta()/顯示資源矩矩陣 int i,j; prinntf(系系統(tǒng)可用的資資源:n); prinntf(rresoucce:); for (j=0;jN;jj+) prinntf(

25、%d,AAvaliaablejj);/輸出分配資資源 prinntf(n); prinntf(各各進程的資源源需求:nn); for (i=0;iM;ii+) printtf(prr%d: ,i); ffor (jj=0;jN;j+) prinntf(%d,MMaxij);/輸出最最大需求資源源數(shù) prinntf(n); prinntf(各各進程得到資資源:n); for (i=0;iM;ii+) pprintff(pr%d: ,i); ffor (jj=0;jN;j+) prrintf(%d,Alloocatioonij);/輸出已分分配資源數(shù) prinntf(n); priintf(各進程

26、還需需求資源:n); for (i=0;iM;ii+) printtf(prr%d: ,i); foor(j=00;jN;j+) priintf(%d,Needij);/輸輸出還需要資資源數(shù) printtf(nn); int chaangdatta(intt i)/進行資源分分配 int jj; for (j=0;jjM;j+) AAvaliaablejj=Avaaliabllej-Requeestj; AAllocaationij=Alloocatioonij+Reequesttj; NNeediij=Needij-Requuestjj; returrn 1;int chkkerr()/安全

27、性性算法 int WWork33,FinnishMM=0,temppM; innt i,kk=0,m,applyy; int jj; Work0=Avvaliabble0; Worrk1=Avaliiable1; Work2=Avvaliabble2; for(ii=0;iM;i+) applyy=0;for(jj=0;j3;j+)if (Finisshi=Falsse&Neeedij=Workj) appply+;if(applyy=3)forr(m=0;m3;mm+)Worrkm=Workm+Alllocattioniim;/變分配配數(shù)Finnishii=Truue;temmpk=i;i=

28、-1; k+; elsse iff(Finiishi=Fallse) if(i=M-1) pprintff(系統(tǒng)不不安全n);/不不成功系統(tǒng)不不安全 rreturnn -1; breeak; priintf(系統(tǒng)資源分分配成功!);/如如果安全，輸輸出成功 priintf(分配的序列列:n); for(i=0;iiM;i+)/輸輸出運行進程程數(shù)組 printtf(prr%d ,temppi);returrn 0;void shhare()/利用銀銀行家算法對對申請資源對對進行判定char cch;int i=0,j=00;ch=y;printff(n請請輸入要求分分配的資源進進程號從(00 t

29、o 44):); scanf(%d,&i);/輸入須申請請的資源號 priintf(請輸入進程程 %d 申申請的資源:n,ii);for(j=0;j33;j+)printtf(第 %d 個資資源:,jj+1);scanff(%d,&Reqquestj);/輸入需要要申請的資源源 ffor (jj=0;jNeeedij)/判斷申請請是否大于需需求，若大于于則出錯 prrintf(進程 %d 申請的的資源大于它它需要的資源源,i); pprintff( errror!n); chh=n; bbreak; else if(RRequesstjAvaliiablej)/判斷申請是是否大于當(dāng)前前資源，若大大于則 /出錯priintf(進程 %dd 申請的資資源大于avvailabble,ii); printtf( eerror!n); ch=nn;