銀行家算法報告

1、成績 課程設計報告 題 目 銀行家算法程序設計 課 程 名 稱 操作系統課程設計 院 部 名 稱 信息技術學院 專 業(yè) 計算機科學與技術 班 級 。 學 生 姓 名 。 學 號 。 課程設計地點 。 課程設計學時 20 指 導 教 師 。 金陵科技學院教務處制目 錄目錄摘要 引言 11、課程設計的目的和要求22、課程設計的環(huán)境23、課程設計的主要內容 2 3.1、項目名稱23.2、項目的主要內容 24、系統的組成及工作原理 3 4.1、系統主要過程的流程圖 3 4.2、系統的設計方法 45、 模塊劃分 5 5.1各模塊間的調用關系 6 5.2安全性算法流程圖 76、運行與測試結果8 6.1歡迎

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

3、若干個循環(huán)等待的進程，即其中每一個進程分別等待它前一個進程所持有的資源。防止死鎖的機構只能確保上述四個條件之一不出現，則系統就不會產生死鎖。通過這個算法可用解決生活中的實際問題,如銀行貸款等。 本文對如何用銀行家算法來處理操作系統給進程分配資源做了詳細的說明，包括需求分析、概要設計、詳細設計、測試與分析、總結、源程序清單。首先做了需求分析，解釋了什么是銀行家算法，并指出它在資源分配中的重要作用。然后給出了銀行家算法的概要設計，包括算法思路、步驟，以及要用到的主要數據結構、函數模塊及其之間的調用關系等。在概要設計的基礎上，又給出了詳細的算法設計，實現概要設計中定義的所有函數,對每個函數寫出核心算

4、法，并畫出了流程圖。接著對編碼進行了測試與分析。最后對整個設計過程進行了總結。關鍵字：死鎖 安全序列 銀行家算法 進程II引 言Dijkstra (1965)提出了一種能夠避免死鎖的調度算法，稱為銀行家算法。它的模型基于一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，每個客戶都有一個貸款額度，銀行家知道不可能所有客戶同時都需要最大貸款額，所以他只保留一定單位的資金來為客戶服務，而不是滿足所有客戶貸款需求的最大單位。這里將客戶比作進程，貸款比作設備，銀行家比作系統。客戶們各自做自己的生意，在某些時刻需要貸款。在某一時刻，客戶已獲得的貸款和可用的最大數額貸款稱為與資源分配相關的系統狀態(tài)。

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

6、。在預防死鎖的幾種方法之中，都施加了較強的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。而最具代表性的避免死鎖的算法，便是Dijkstra的銀行家算法。利用銀行家算法，我們可以來檢測CPU為進程分配資源的情況，決定CPU是否響應某進程的的請求并為其分配資源，從而很好避免了死鎖1、課程設計的目的和要求目的：銀行家算法是避免死鎖的一種重要方法，本設計要求用C語言（或高級語言）編寫和調試一個簡單的銀行家算法程序。加深了解有關資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。通過對

7、這個算法的設計,讓學生能夠對書本知識有更深的理解,在操作和其它方面有更高的提升,同時對程序設計的水平也有所提高。要求：設計一個n個并發(fā)進程共享m個系統資源的程序實現銀行家算法。要求包含：1）、簡單的選擇界面。2）、前系統資源的占用和剩余情況。 3）、為進程分配資源，如果進程要求的資源大于系統剩余的資源，不與分配并且提示分配不成功。4）、撤銷作業(yè)，釋放資源。2、課程設計的環(huán)境奔騰以上計算機，裝有Turbo C 2.0軟件3、課程設計的主要內容3.1 項目名稱 銀行家算法程序設計3.2 項目的主要內容（1）設計銀行家算法，能夠檢測系統某一時刻是否安全，輸出安全序列。（2）實現安全性檢測算法。即在某

8、一進程在某時刻提出Request時，檢測系統是否能夠滿足該進程的請求，并得到一個安全序列，若能夠得到一個安全序列，則系統能夠滿足它的請求，同意分配資源。若不能夠滿足，則回到請求前狀態(tài)。（3）對于此次課程設計通過需求分析、概要設計、詳細設計、測試與分析、總結、源程序清單等模塊進行全面分析，以加深對死鎖概念的理解，以及銀行家算法避免死鎖的過程。能夠利用銀行家算法，有效避免死鎖的發(fā)生，或檢測死鎖的存在。4、系統的組成及工作原理4.1系統主要過程流程圖4.1.1初始化算法流程圖圖4.1初始化算法流程圖 4.1.2 銀行家算法流程圖圖4.2銀行家算法流程圖4.2 系統的設計方法根據設計任務書的要求，畫出

9、程序設計流程圖，確定程序的功能，把整個程序根據功能要求分解為各個子程序，利用TC語言分編寫程序代碼，然后進行上機調試、修改、進行連接，測試，寫出設計總結報告。主要函數的核心代碼：1. 進行初始化輸入的函數2. 打印輸出的函數3. 利用安全性算法進行檢測的函數4. 進行資源分配的函數5. 利用行家算法進行判定的函數void mainenter()/主要的輸入部分代碼printf(請輸入系統總共有的資源數：);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對第%d類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; 5、模塊劃分第一部分:銀行家算法(掃描)1如果Request=Need,則轉向2;否則,出錯2如果Request=Available,則轉向3,否則等待3系統試探分配請求的資源給進程4系統執(zhí)行安全性算法第二部分:安全性算法1.設置兩個向量(1).工作向量:Work=Available(表示系統可提供給進程繼續(xù)運行所需要的各類資源數目)(2).Finish:表示系統是否有足夠

11、資源分配給進程(True:有;False:沒有).初始化為False2.若Finishi=False&Need=Work,則執(zhí)行3;否則執(zhí)行4(I為資源類別)3.進程P獲得第i類資源,則順利執(zhí)行直至完成!并釋放資源:Work=Work+Allocation; Finishi=true;轉24. 若所有進程的Finishi=true,則表示系統安全;否則,不安全!5.1各模塊間的調用關系：主函數void main()要調用： printFrame()，print()，Safty()，mainenter() 安全性檢測函數Safty()要調用：print() 銀行家算法函數mainenter()要

12、調用print()、Safty()、和mainenter()本身void main() int k,h=1; while(h) system(cls); printf(nn 歡迎使用本程序 n); printf(nn 1:輸入系統的資源數、申請進程數、每個類資源的實例數); printf(n 2: 輸入進程的資源申請); printf(n 3: 輸出系統狀態(tài)); printf(n 4: 退出程序); printf(nn please choose ); scanf(%d,&k); switch(k) case 1:mainenter(); break; case 2:mainrequest()

13、; break; case 3:mainprint(); break; case 4:h=0; break; printf(n); system(pause); system(cls); printf(nn 謝謝使用 n); printf(nn See you next time!nnn);5.2安全性算法流程圖圖5.1安全性算法流程圖6運行與測試結果6.1運行程序成功之后的歡迎界面圖6.1歡迎界面6.2初始化程序圖6.2初始化界面圖6.3輸入數據圖6.4申請進程1圖6.5申請進程2圖6.6申請進程3圖6.7申請進程56.3界面顯示圖6.8界面顯示6.4出錯界面圖圖6.9出錯界面6.5程序運行

14、結束圖6.10程序結束畫面7、總結在本程序代碼中，銀行家算法用數組函數來實現。首先，輸入欲申請資源的進程以及其所申請的資源數，存放在Request數組中。然后，判斷進程請求的資源數是否大于其所需的資源數，若大于則報錯并返回，若不大于則繼續(xù)判斷它是否大于系統在此時刻可利用的資源數，同樣，如果大于則報錯并反回，如果不大于則調用函數來進行預分配，之后再調用安全型算法safty檢查。最后，無論此次分配是否成功，我們都可以選擇繼續(xù)分配或者退出系統。在銀行家算法這個系統之中，所采用的數據結構應是最基本的部分。銀行家算法的數據結構我們采用了一維數組與二維數組來存儲，比如最大需求量Max、已分配資源數Allo

15、cation、仍需求資源數Need、以及系統可利用的資源數、申請各類資源等數組。數據結構雖然重要但卻只是基礎，而最主要的用以實現系統功能的應該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統的安全性。除此之外，在程序當中，我們也得強調一下對輸入的合法性的判斷。比如，我們輸入的欲申請資源的進程號沒有在系統已存在的進程當中，或者進程號定義為整型，但是卻錯輸成字母等情況，我們需要對這些情況進行判斷，讓程序報錯返回而并非因錯誤而中斷。這樣的情況處理起來比較麻煩，相當于對每次輸入針對各種不同的情況都得做判斷。我也沒有涵蓋全部的輸入，僅僅只是對輸入的進程號不在已存在進程當中、以及輸入的操作選

16、擇不存在兩種情況分別作了判斷，并且針對第二種情況設定了五次輸入錯誤的話系統關閉的功能。而因為對于某些比如進程號本來設定就是整型，因此對輸入的是字母的判別因比較復雜而未能加上。通過對本次銀行家算法的程序進行修改對其結構更加明確。8、課程設計的心得體會操作系統的基本特征就是并發(fā)和共享，系統允許多個進程并發(fā)執(zhí)行，并且共享系統的軟、硬件資源。為了最大限度的利用計算機資源，操作系統應采用動態(tài)分配的策略，但是這樣就容易因資源不足、分配不當而引起“死鎖”。本次課程設計就是用銀行家算法來避免“死鎖”。 該算法就是一在程序進行編寫之前，先對程序的要求進行分析，弄清楚程序所需要的功能，然后將每個功能分成一個功能模

17、塊即調用函數來實現，無需過多的畫蛇添足。編寫這個簡易的銀行家算法讓我知道了在資源一定的條件下為了讓多個進程都能使用資源完成任務，避免死鎖的產生可以從一開始就對系統進行安全性檢查來判斷是否將資源分配給正在請求的進程。但是銀行家算法會加大系統的開銷。在資源分配過程，使分配序列不會產生死鎖。此算法的中心思想就是，每次分配后總存在著一個進程，如果讓它單獨的運行下去，一周的操作系統課程設計，我學到了很多課本上沒有的知識。想要完成模擬銀行家算法的C語言程序，首先就是要徹底熟悉算法，了解算法的基本原理，才能開始著手程序設計在程序設計設計過程中，遇到了一些困難，通過向同學詢問，翻閱資料等問題被一一解決了。首先

18、就是在知識層面上了解了銀行家算法這種進程調度和避免死鎖的算法，并用C語言程序真正模擬出安全性檢查和銀行家算法過程，復習了之前所學C語言和數據結構的知識；在編程過程中雖然遇到很多困難，解決問題的過程中，同時也鍛煉了我不怕困難，勇于迎接挑戰(zhàn)的精神，為以后的工作打下了堅實的基礎。9、參考文獻1湯小丹等，計算機操作系統第三版，西安電子科技大學出版社，2007年2塔嫩鮑姆等，操作系統設計與實現，電子工業(yè)出版社，20073羅宇等，操作系統課程設計，機械工業(yè)出版社，20054鄭扣根著，操作系統概念，高等教育出版社，20105嚴蔚敏，吳偉明著，數據結構，北京 清華大學出版社，20066斯托林肯著，操作系統：精

19、髓與設計原理，機械工業(yè)出版社，2010附錄#include#include#includeint Available10; /可使用資源向量int Max1010; /最大需求矩陣int Allocation1010=0; /分配矩陣int Need1010=0; /需求矩陣int Work10; /工作向量int Finish10; /狀態(tài)標志int Request1010; /進程申請資源向量int Pause10;int List10;int i,j;int n; /系統資源總數int m; /總的進程數int a; /當前申請的進程號int l,e; /計數器int b=0,c=0,f

20、=0,g; /計數器void mainenter()/主要的輸入部分代碼printf(請輸入系統總共有的資源數：);scanf(%d,&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類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /進程提出新申請的代碼部分 pr

21、intf(請輸入申請資源的進程：); scanf(%d,&a);for(i=1;iNeedai) printf(n出錯！進程申請的資源數多于它自己申報的最大量n); if(RequestaiAvailablei) printf(nP%d必須等待n,a);/以下是試探性分配 Availablei=Availablei-Requestai; Allocationai=Allocationai+Requestai; Needai=Needai-Requestai; Worki=Availablei;for(i=1;i=m;i+) Pausei=Availablei;/Pausei只是一個暫時寄存的中

22、間變量，為防止在下面 /安全性檢查時修改到Availablei而代替的一維數組 Finishi=false;for(g=1;g=m;g+) for(i=1;i=m;i+) b=0; /計數器初始化 for(j=1;j=n;j+) 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;/統計Finishitrue的個數if (f=m) printf(safe static); f=0;/將計數器f重新初始化，為下一次提出新的進程申請做準備else printf( unsafe static );/以下代碼為當系統被判定為不安全狀態(tài)時 /返回提出申請前的狀態(tài) for(i=1;i=n;i+) Availablei=Availablei+Requestai; Allocationai=Allocationai-Requestai; Needai=Need