銀行家算法報告匯總

1、金鼠科我號院課程設計報告成績題目銀行家算法程序設計課程名稱操作系統(tǒng)課程設計院部名稱信息技術學院專業(yè)計算機科學與技術學生姓名工2學號。課程設計地點"課程設計學時20指導教師絲金陵科技學院教務處制目錄I摘要II引言11、課程設計的目的和要求22、課程設計的環(huán)境23、課程設計的主要內(nèi)容23.1 、項目名稱23.2 、項目的主要內(nèi)容24、系統(tǒng)的組成及工作原理34.1、 系統(tǒng)主要過程的流程圖34.2、 系統(tǒng)的設計方法45、模塊劃分55.1 各模塊間的調(diào)用關系65.2 安全性算法流程圖76、運行與測試結果86.1 歡迎界面86.2 初始化界面86.3 界面顯示116.4 出錯界面圖126.5 程

2、序運行結束127、總結138、課程設計的心得體會149、參考文獻15附錄16摘要i隨著時代的發(fā)展，對生活的追求越來越高，生活品質也越來越好。在學習方面的研究也越來越有成效。Dijkstra提出的銀行家算法，是最具代表性的避免死鎖的算法。加深了解有關資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。死鎖的產(chǎn)生，必須同時滿足四個條件，即一個資源每次只能由一個進程占用：第二個為等待條件，即一個進程請求資源不能滿足時，它必須等待，但它仍繼續(xù)保持已得到的所有其他資源：第四個為循環(huán)等待條件，系統(tǒng)中存在若干個循環(huán)等待的進程，即其中每一個進程分別等待它前一個進程所持有的資源。防止死鎖的機構只

3、能確保上述四個條件之一不出現(xiàn)，則系統(tǒng)就不會產(chǎn)生死鎖。通過這個算法可用解決生活中的實際問題,如銀行貸款等。本文對如何用銀行家算法來處理操作系統(tǒng)給進程分配資源做了詳細的說明，包括需求分析、概要設計、詳細設計、測試與分析、總結、源程序清單。首先做了需求分析，解釋了什么是銀行家算法，并指出它在資源分配中的重要作用。然后給出了銀行家算法的概要設計，包括算法思路、步驟，以及要用到的主要數(shù)據(jù)結構、函數(shù)模塊及其之間的調(diào)用關系等。在概要設計的基礎上，又給出了詳細的算法設計，實現(xiàn)概要設計中定義的所有函數(shù),對每個函數(shù)寫出核心算法，并畫出了流程圖。接著對編碼進行了測試與分析。最后對整個設計過程進行了總結。關鍵字：死鎖

4、安全序列銀行家算法進程II引言Dijkstra(1965)提出了一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。它的模型基于一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，每個客戶都有一個貸款額度，銀行家知道不可能所有客戶同時都需要最大貸款額，所以他只保留一定單位的資金來為客戶服務，而不是滿足所有客戶貸款需求的最大單位。這里將客戶比作進程，貸款比作設備，銀行家比作系統(tǒng)?？蛻魝兏髯宰鲎约旱纳?，在某些時刻需要貸款。在某一時刻，客戶已獲得的貸款和可用的最大數(shù)額貸款稱為與資源分配相關的系統(tǒng)狀態(tài)。一個狀態(tài)被稱為是安全的，其條件是存在一個狀態(tài)序列能夠使所有的客戶均得到其所需的貸款。如果忽然所有的客

5、戶都申請，希望得到最大貸款額，而銀行家無法滿足其中任何一個的要求，則發(fā)生死鎖。不安全狀態(tài)并不一定導致死鎖，因為客戶未必需要其最大貸款額度，但銀行家不敢抱這種僥幸心理。銀行家算法就是對每一個請求進行檢查，檢查如果滿足它是否會導致不安全狀態(tài)。若是，則不滿足該請求；否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個距最大需求最近的客戶。如果可以，則這筆投資認為是能夠收回的，然后接著檢查下一個距最大需求最近的客戶，如此反復下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請求可以批準。在預防死鎖的幾種方法之中，都施加了較強的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可

6、能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。而最具代表性的避免死鎖的算法，便是Dijkstra的銀行家算法。利用銀行家算法，我們可以來檢測CPU»進程分配資源的情況，決定CPU是否響應某進程的的請求并為其分配資源，從而很好避免了死鎖121、課程設計的目的和要求目的：銀行家算法是避免死鎖的一種重要方法，本設計要求用C語言（或高級語言）編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。通過對這個算法的設計,讓學生能夠對書本知識有更深的理解,在操作和其它方面有更高的提升,同時對

7、程序設計的水平也有所提高。要求：設計一個n個并發(fā)進程共享mt系統(tǒng)資源的程序實現(xiàn)銀行家算法。要求包含：1） 、簡單的選擇界面。2） 、前系統(tǒng)資源的占用和剩余情況。3）、為進程分配資源，如果進程要求的資源大于系統(tǒng)剩余的資源，不與分配并且提示分配不成功。4）、撤銷作業(yè)，釋放資源。2、課程設計的環(huán)境奔騰以上計算機，裝有TurboC2.0軟件3、課程設計的主要內(nèi)容3.1 項目名稱銀行家算法程序設計3.2 項目的主要內(nèi)容（ 1）設計銀行家算法，能夠檢測系統(tǒng)某一時刻是否安全，輸出安全序列。（ 2）實現(xiàn)安全性檢測算法。即在某一進程在某時刻提出Request時，檢測系統(tǒng)是否能夠滿足該進程的請求，并得到一個安全序

8、列，若能夠得到一個安全序列，則系統(tǒng)能夠滿足它的請求，同意分配資源。若不能夠滿足，則回到請求前狀態(tài)。（ 3）對于此次課程設計通過需求分析、概要設計、詳細設計、測試與分析、總結、源程序清單等模塊進行全面分析，以加深對死鎖概念的理解，以及銀行家算法避免死鎖的過程。能夠利用銀行家算法，有效避免死鎖的發(fā)生，或檢測死鎖的存在。4、系統(tǒng)的組成及工作原理4.1系統(tǒng)主要過程流程圖4.1.1初始化算法流程圖4.1.2銀行家算法流程圖4.2系統(tǒng)的設計方法根據(jù)設計任務書的要求，畫出程序設計流程圖，確定程序的功能，把整個程序根據(jù)功能要求分解為各個子程序，利用TC語言分編寫程序代碼，然后進行上機調(diào)試、修改、進行連接，測試

9、，寫出設計總結報告。主要函數(shù)的核心代碼：1. 進行初始化輸入的函數(shù)2. 打印輸出的函數(shù)3. 利用安全性算法進行檢測的函數(shù)4. 進行資源分配的函數(shù)5. 利用行家算法進行判定的函數(shù)voidmainenter()/主要的輸入部分代碼printf("請輸入系統(tǒng)總共有的資源數(shù)：");scanf("%d",&n);printf("請輸入總共有多少個進程：");scanf("%d",&m);for(i=1;i<=n;i+)printf("第d類資源有的資源實例：”,i);scanf("%

10、d",&Availablei);for(i=1;i<=m;i+)for(j=1;j<=n;j+)printf("進程P%d對第讀資源的最大需求量：”,i,j);scanf("%d",&Maxij);Needij=Maxij;5、模塊劃分第一部分:銀行家算法(掃描)1.如果Request<=Need,則轉向2;否貝U,出錯2如果Request<=Available,則轉向3,否則等待3系統(tǒng)試探分配請求的資源給進程4系統(tǒng)執(zhí)行安全性算法第二部分:安全性算法1 .設置兩個向量(1) .工作向量:Work=Available

11、(表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源數(shù)目)(2) .Finish:表示系統(tǒng)是否有足夠資源分配給進程(True:有;False:沒有).初始化為False2. 若Finishi=False&&Need<=Work,則執(zhí)行3;否則執(zhí)行4(I為資源類別)3. 進程P獲得第i類資源,則順利執(zhí)行直至完成!并釋放資源:Work=Work+Allocation;Finishi=true;轉24. 若所有進程的Finishi=true,則表示系統(tǒng)安全;否則,不安全!5.1各模塊間的調(diào)用關系：主函數(shù)voidmain()要調(diào)用：printFrame()，print()，Safty(

12、)，mainenter()安全性檢測函數(shù)Safty()要調(diào)用：print()銀行家算法函數(shù)mainenter()要調(diào)用print()、Safty()、和mainenter()本身voidmain()intk,h=1;while(h)system("cls");n歡迎使用本程序n");printf("nn1:輸入系統(tǒng)的資源數(shù)、申請進程數(shù)、每個類資源的實例數(shù)");n2:輸入進程的資源申請");n3:輸出系統(tǒng)狀態(tài)");n4:退出程序");printf("nnpleasechoose");scanf(&

13、quot;%d",&k);switch(k)case1:mainenter();break;case2:mainrequest();break;case3:mainprint();break;case4:h=0;break;printf("n");system("pause");system("cls");printf("nn謝謝使用n");printf("nnSeeyounexttime!nnn");5.2安全性算法流程圖圖5.1安全性算法流程圖6運行與測試結果6.1運行程序

14、成功之后的歡迎界面歡迎使用本程序工;輸入系統(tǒng)的資源數(shù).2：3：4:申請進程數(shù).數(shù)也叫心序例出的偏退爵出類進一個人二|二pleasechoose圖6.1歡迎界面6.2初始化程序仁科,C:Progra>FilesMicrosoftVisualStudioMyProjects44Debug44.exe,歡迎使用本程序n輸入系統(tǒng)的資源數(shù)、申請進程數(shù)、2：3：4：數(shù)M黑序例出的庠退寓出類進一個人二*二3需:50V'、數(shù)157小靄實實能旗需或CKtfMw:lP請請WRWB圖6.2初始化界面?？?C:,Progra>FilesBicrosoftVisualStudioByProjects

15、44Debug44.exe,4：圖6.3輸入數(shù)據(jù)-口產(chǎn)753322902222433量量量量量量量量量量量量量量量巖巖芯巖芯片芯片芯至尊翼型翼型翼型翼型翼型翼型翼而大大大大大大大大大大大大大大大發(fā)157F與日W譬W皆W譬WWWW瞽W薯W取的的的的的的的的的的的的的的罐實實s-bb.-:.-htjtt123123123123123.勺勺'''''':；:'''''''':'',;,1-TT7,npftHS-口5-n5-口s-ns-n5-n5-5-s-fi-s-nfi-F

16、s-n5-Fs-n.育有有年身膏人宮目餅胃胃胃胃-耳胃-餅胃-餅ri.T.T.-.-¥-.-.h.-.K.-.-.1-.s-.s-.s-.-.ch統(tǒng)去e系總、as入人一le料c科*C:%Progra>FilesIBicrosoftVisualStudioMyProjects44Debug44.exe*歡迎使用本程序的藁退雷出tt-類進一個人二*二工:輸入系統(tǒng)的資源數(shù).申請進程數(shù)、2:"""10量<量a犀pleas?choose2PP®B請輸入進模P珈案科原的6$1$2$35$4$5CStfltic倩按任意鍵繼續(xù)一.圖6.4申請進程1

17、G：。*C: PrograM FilesHicrosoft Visual StudioMyProjects44Debug44, exe14歡迎使用本程序;輸入系統(tǒng)的資源數(shù)、申請進程數(shù)、3；*««*，呼，n|fla建口.ggg.F.嘈！|.巧EE.ggg.葉室小F.i數(shù)M明心序例里的篁退爵出n-類近-個人二第二pleasechoDse2資源的蟹PL21麻2卷P121對3類學源的源的驚的1$2$3$4$Ssafe零tdtic：括按任意鍵繼續(xù)一量量量圖6.5申請進程2口，*C:Progra>FilesMicrosoftVisualStudioByProjects44Debu

18、g44.exe歡迎使用本程序口輸入系統(tǒng)的資源數(shù)、申請進程數(shù)、2：3：4：數(shù)重心例累SI.的；m爵出n類進個入i-pleasechoose2請搦入里道資源的嚶：、3請輸入啜程PI31對1類資源的請瓠入進程P13國建,原的請輸入進樓珈爰餐植的302>:量>:WWWininin$2$3$4$5$1safestatic請按任意鍵繼續(xù).圖6.6申請進程3。猛*C:PrograM FilesIBicrosoft Visual StudioMyProjects44Debug44.exeii*歡迎使用本程序r輸入系統(tǒng)的資源數(shù)、¥¥*««!BBBill199B

19、If-»W¥¥'申請進程數(shù).的退雷出fl-類進一個人二第二數(shù)請態(tài)序please>cboose2m領人里道資源的蜂：5請諭入壬程p過i三三源的語甫入進程P河2三真原的請喘入進檀p巾奚簧總的6$2$4$5$513：afestatic懵按任意槌繼續(xù)一.量量量士明M用也明由inin圖6.7申請進程56.3界面顯示8*C:Progra>FilesMicrosoftVisualStudioByProjects44Debug44.exen|x|歡迎使用本程序U輸入系統(tǒng)的資源數(shù)、申請進程數(shù)、2：3：4：數(shù)M堤心序例出的豪退寓出類進一個人二*二c等進as入入入p

20、主月胃高choose2逋資源的曝：1程p11對1類資源的用請量:槿PI1先空美費源的臼請量:出錯！進程申請的資源數(shù)多于它自己申報的最大量Pill必須等待請輸入進程P對3類資源的申請量：7出錯！進程申請的資源數(shù)多于它自己申報的最大量P【1J必須等待Linsafestatic請按任意鍵繼續(xù).圖6.8界面顯示6.4出錯界面圖*C:Progra>FilesMicrosoftVisualStudioByProjects44Debug44.exe*歡迎使用本程序工;輸入系統(tǒng)的資源數(shù)、2：數(shù)重心序出 的簟退 幅出 類進 一 個人3 3 另二please111choose 2道資源的進程：3 程P13對

21、1類資源的 槨pm就2美赍源的Em請量：2申請量：320出錯！進程申請的資源數(shù)勇于它自己申報的最大量unsafestatic宿按任意鍵繼續(xù)一.圖6.9出錯界面.西6.5程序運行結束。科*C:VProgra*FilesMicrosoftVisualStudioMrProjects44Debug44.exe*謝謝使用Seeyounexttime?!?Pressanykeytocontinue圖6.10程序結束畫面7、總結在本程序代碼中，銀行家算法用數(shù)組函數(shù)來實現(xiàn)。首先，輸入欲申請資源的進程以及其所申請的資源數(shù)，存放在Request數(shù)組中。然后，判斷進程請求的資源數(shù)是否大于其所需的資源數(shù)，若大于則報

22、錯并返回，若不大于則繼續(xù)判斷它是否大于系統(tǒng)在此時刻可利用的資源數(shù)，同樣，如果大于則報錯并反回，如果不大于則調(diào)用函數(shù)來進行預分配，之后再調(diào)用安全型算法safty檢查。最后，無論此次分配是否成功，我們都可以選擇繼續(xù)分配或者退出系統(tǒng)。在銀行家算法這個系統(tǒng)之中，所采用的數(shù)據(jù)結構應是最基本的部分。銀行家算法的數(shù)據(jù)結構我們采用了一維數(shù)組與二維數(shù)組來存儲，比如最大需求量Max、已分配資源數(shù)Allocation、仍需求資源數(shù)Need、以及系統(tǒng)可利用的資源數(shù)、申請各類資源等數(shù)組。數(shù)據(jù)結構雖然重要但卻只是基礎，而最主要的用以實現(xiàn)系統(tǒng)功能的應該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統(tǒng)的安全性。

23、除此之外，在程序當中，我們也得強調(diào)一下對輸入的合法性的判斷。比如，我們輸入的欲申請資源的進程號沒有在系統(tǒng)已存在的進程當中，或者進程號定義為整型，但是卻錯輸成字母等情況，我們需要對這些情況進行判斷，讓程序報錯返回而并非因錯誤而中斷。這樣的情況處理起來比較麻煩，相當于對每次輸入針對各種不同的情況都得做判斷。我也沒有涵蓋全部的輸入，僅僅只是對輸入的進程號不在已存在進程當中、以及輸入的操作選擇不存在兩種情況分別作了判斷，并且針對第二種情況設定了五次輸入錯誤的話系統(tǒng)關閉的功能。而因為對于某些比如進程號本來設定就是整型，因此對輸入的是字母的判別因比較復雜而未能加上。通過對本次銀行家算法的程序進行修改對其結

24、構更加明確。8、課程設計的心得體會操作系統(tǒng)的基本特征就是并發(fā)和共享，系統(tǒng)允許多個進程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計算機資源，操作系統(tǒng)應采用動態(tài)分配的策略，但是這樣就容易因資源不足、分配不當而引起“死鎖”。本次課程設計就是用銀行家算法來避免“死鎖”。該算法就是一在程序進行編寫之前，先對程序的要求進行分析，弄清楚程序所需要的功能，然后將每個功能分成一個功能模塊即調(diào)用函數(shù)來實現(xiàn)，無需過多的畫蛇添足。編寫這個簡易的銀行家算法讓我知道了在資源一定的條件下為了讓多個進程都能使用資源完成任務，避免死鎖的產(chǎn)生可以從一開始就對系統(tǒng)進行安全性檢查來判斷是否將資源分配給正在請求的進程。但

25、是銀行家算法會加大系統(tǒng)的開銷。在資源分配過程，使分配序列不會產(chǎn)生死鎖。此算法的中心思想就是，每次分配后總存在著一個進程，如果讓它單獨的運行下去，一周的操作系統(tǒng)課程設計，我學到了很多課本上沒有的知識。想要完成模擬銀行家算法的C語言程序，首先就是要徹底熟悉算法，了解算法的基本原理，才能開始著手程序設計在程序設計設計過程中，遇到了一些困難，通過向同學詢問，翻閱資料等問題被一一解決了。首先就是在知識層面上了解了銀行家算法這種進程調(diào)度和避免死鎖的算法，并用c語言程序真正模擬出安全性檢查和銀行家算法過程，復習了之前所學C語言和數(shù)據(jù)結構的知識；在編程過程中雖然遇到很多困難，解決問題的過程中，同時也鍛煉了我不

26、怕困難，勇于迎接挑戰(zhàn)的精神，為以后的工作打下了堅實的基礎。9、參考文獻1湯小丹等，計算機操作系統(tǒng)第三版，西安電子科技大學出版社，2007年2塔嫩鮑姆等，操作系統(tǒng)設計與實現(xiàn)，電子工業(yè)出版社，20073羅宇等，操作系統(tǒng)課程設計，機械工業(yè)出版社，20054鄭扣根著，操作系統(tǒng)概念，高等教育出版社，20105嚴蔚敏，吳偉明著，數(shù)據(jù)結構，北京清華大學出版社，20066斯托林肯著，操作系統(tǒng)：精髓與設計原理，機械工業(yè)出版社，2010附錄#include<stdio.h>#include<stdlib.h>#include<conio.h>intAvailable10;int

27、Max1010;intAllocation1010=0;intNeed1010=0;intWork10;intFinish10;intRequest1010;intPause10;intList10;inti,j;intn;intm;inta;intl,e;intb=0,c=0,f=0,g;/可使用資源向量/最大需求矩陣/分配矩陣/需求矩陣/工作向量/狀態(tài)標志/進程申請資源向量/系統(tǒng)資源總數(shù)/總的進程數(shù)/當前申請的進程號/計數(shù)器/計數(shù)器voidmainenter()/主要的輸入部分代碼printf("請輸入系統(tǒng)總共有的資源數(shù)：");scanf("%d",

28、&n);printf("請輸入總共有多少個進程：");scanf("%d",&m);for(i=1;i<=n;i+)printf("第%d類資源有的資源實例：",i);scanf("%d",&Availablei);for(i=1;i<=m;i+)for(j=1;j<=n;j+)printf("進程P%d對第%d類資源的最大需求量：scanf("%d",&Maxij);Needij=Maxij;voidmainrequest()/進程提

29、出新申請的代碼部分printf("請輸入申請資源的進程：");",i,j);scanf("%d",&a);for(i=1;i<=n;i+)printf("請輸入進程P%d%d類資源的申請量：",a,i);scanf("%d",&Requestai);if(Requestai>Needai)printf("n出錯！進程申請的資源數(shù)多于它自己申報的最大量n");if(Requestai>Availablei)printf("nP%d必須等待n&q

30、uot;,a);/以下是試探性分配Availablei=Availablei-Requestai;Allocationai=Allocationai+Requestai;Needai=Needai-Requestai;Worki=Availablei;for(i=1;i<=m;i+)Pausei=Availablei;/Pausei只是一個暫時寄存的中間變量，為防止在下面/安全性檢查時修改到Availablei而代替的一維數(shù)組Finishi=false;for(g=1;g<=m;g+)for(i=1;i<=m;i+)b=0;/計數(shù)器初始化for(j=1;j<=n;j+)

31、if(Needij<=Pausej)b=b+1;if(Finishi=false&&b=n)for(l=1;l<=n;l+)Pausel=Pausel+Allocationil;Finishi=true;printf("$%d",i);/依次輸出進程安全序列之一中每個元素printf("n");for(i=1;i<=m;i+)if(Finishi=true)f=f+1;統(tǒng)計Finishi=true的個數(shù)if(f=m)printf("safestatic");f=0;將計數(shù)器f重新初始化，為下一次提出新的進程申請做準備elseprintf("unsafestatic");/以下代碼為當系統(tǒng)被判定為不安全狀態(tài)時/返回提出申請前的狀態(tài)for(i=