銀行家算法報(bào)告

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

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

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

4、法，并畫(huà)出了流程圖。接著對(duì)編碼進(jìn)行了測(cè)試與分析。最后對(duì)整個(gè)設(shè)計(jì)過(guò)程進(jìn)行了總結(jié)。關(guān)鍵字：死鎖 安全序列 銀行家算法 進(jìn)程II引 言Dijkstra (1965)提出了一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。它的模型基于一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，每個(gè)客戶都有一個(gè)貸款額度，銀行家知道不可能所有客戶同時(shí)都需要最大貸款額，所以他只保留一定單位的資金來(lái)為客戶服務(wù)，而不是滿足所有客戶貸款需求的最大單位。這里將客戶比作進(jìn)程，貸款比作設(shè)備，銀行家比作系統(tǒng)?？蛻魝兏髯宰鲎约旱纳?，在某些時(shí)刻需要貸款。在某一時(shí)刻，客戶已獲得的貸款和可用的最大數(shù)額貸款稱為與資源分配相關(guān)的系統(tǒng)狀態(tài)。

5、一個(gè)狀態(tài)被稱為是安全的，其條件是存在一個(gè)狀態(tài)序列能夠使所有的客戶均得到其所需的貸款。如果忽然所有的客戶都申請(qǐng)，希望得到最大貸款額，而銀行家無(wú)法滿足其中任何一個(gè)的要求，則發(fā)生死鎖。不安全狀態(tài)并不一定導(dǎo)致死鎖，因?yàn)榭蛻粑幢匦枰渥畲筚J款額度，但銀行家不敢抱這種僥幸心理。銀行家算法就是對(duì)每一個(gè)請(qǐng)求進(jìn)行檢查，檢查如果滿足它是否會(huì)導(dǎo)致不安全狀態(tài)。若是，則不滿足該請(qǐng)求；否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個(gè)距最大需求最近的客戶。如果可以，則這筆投資認(rèn)為是能夠收回的，然后接著檢查下一個(gè)距最大需求最近的客戶，如此反復(fù)下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn)

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

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

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

9、程序設(shè)計(jì)流程圖，確定程序的功能，把整個(gè)程序根據(jù)功能要求分解為各個(gè)子程序，利用TC語(yǔ)言分編寫程序代碼，然后進(jìn)行上機(jī)調(diào)試、修改、進(jìn)行連接，測(cè)試，寫出設(shè)計(jì)總結(jié)報(bào)告。主要函數(shù)的核心代碼：1. 進(jìn)行初始化輸入的函數(shù)2. 打印輸出的函數(shù)3. 利用安全性算法進(jìn)行檢測(cè)的函數(shù)4. 進(jìn)行資源分配的函數(shù)5. 利用行家算法進(jìn)行判定的函數(shù)void mainenter()/主要的輸入部分代碼printf(請(qǐng)輸入系統(tǒng)總共有的資源數(shù)：);scanf(%d,&n);printf(請(qǐng)輸入總共有多少個(gè)進(jìn)程：);scanf(%d,&m);for(i=1;i=n;i+) printf(第%d類資源有的資源實(shí)例：,i); scanf(%

10、d,&Availablei);for(i=1;i=m;i+) for(j=1;j=n;j+) printf(進(jìn)程P%d對(duì)第%d類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; 5、模塊劃分第一部分:銀行家算法(掃描)1如果Request=Need,則轉(zhuǎn)向2;否則,出錯(cuò)2如果Request=Available,則轉(zhuǎn)向3,否則等待3系統(tǒng)試探分配請(qǐng)求的資源給進(jìn)程4系統(tǒng)執(zhí)行安全性算法第二部分:安全性算法1.設(shè)置兩個(gè)向量(1).工作向量:Work=Available(表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目)(2).Finish:表示系統(tǒng)是否有足夠

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

12、調(diào)用print()、Safty()、和mainenter()本身void main() int k,h=1; while(h) system(cls); printf(nn 歡迎使用本程序 n); printf(nn 1:輸入系統(tǒng)的資源數(shù)、申請(qǐng)進(jìn)程數(shù)、每個(gè)類資源的實(shí)例數(shù)); printf(n 2: 輸入進(jìn)程的資源申請(qǐng)); printf(n 3: 輸出系統(tǒng)狀態(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運(yùn)行與測(cè)試結(jié)果6.1運(yùn)行程序成功之后的歡迎界面圖6.1歡迎界面6.2初始化程序圖6.2初始化界面圖6.3輸入數(shù)據(jù)圖6.4申請(qǐng)進(jìn)程1圖6.5申請(qǐng)進(jìn)程2圖6.6申請(qǐng)進(jìn)程3圖6.7申請(qǐng)進(jìn)程56.3界面顯示圖6.8界面顯示6.4出錯(cuò)界面圖圖6.9出錯(cuò)界面6.5程序運(yùn)行

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

15、cation、仍需求資源數(shù)Need、以及系統(tǒng)可利用的資源數(shù)、申請(qǐng)各類資源等數(shù)組。數(shù)據(jù)結(jié)構(gòu)雖然重要但卻只是基礎(chǔ)，而最主要的用以實(shí)現(xiàn)系統(tǒng)功能的應(yīng)該有兩個(gè)部分，一是用銀行家算法來(lái)判斷，二是用安全性算法來(lái)檢測(cè)系統(tǒng)的安全性。除此之外，在程序當(dāng)中，我們也得強(qiáng)調(diào)一下對(duì)輸入的合法性的判斷。比如，我們輸入的欲申請(qǐng)資源的進(jìn)程號(hào)沒(méi)有在系統(tǒng)已存在的進(jìn)程當(dāng)中，或者進(jìn)程號(hào)定義為整型，但是卻錯(cuò)輸成字母等情況，我們需要對(duì)這些情況進(jìn)行判斷，讓程序報(bào)錯(cuò)返回而并非因錯(cuò)誤而中斷。這樣的情況處理起來(lái)比較麻煩，相當(dāng)于對(duì)每次輸入針對(duì)各種不同的情況都得做判斷。我也沒(méi)有涵蓋全部的輸入，僅僅只是對(duì)輸入的進(jìn)程號(hào)不在已存在進(jìn)程當(dāng)中、以及輸入的操作選

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

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

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

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

20、=0,g; /計(jì)數(shù)器void mainenter()/主要的輸入部分代碼printf(請(qǐng)輸入系統(tǒng)總共有的資源數(shù)：);scanf(%d,&n);printf(請(qǐng)輸入總共有多少個(gè)進(jìn)程：);scanf(%d,&m);for(i=1;i=n;i+) printf(第%d類資源有的資源實(shí)例：,i); scanf(%d,&Availablei);for(i=1;i=m;i+) for(j=1;j=n;j+) printf(進(jìn)程P%d對(duì)第%d類資源的最大需求量：,i,j); scanf(%d,&Maxij); Needij=Maxij; void mainrequest() /進(jìn)程提出新申請(qǐng)的代碼部分 pr

21、intf(請(qǐng)輸入申請(qǐng)資源的進(jìn)程：); scanf(%d,&a);for(i=1;iNeedai) printf(n出錯(cuò)！進(jìn)程申請(qǐng)的資源數(shù)多于它自己申報(bào)的最大量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只是一個(gè)暫時(shí)寄存的中

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