銀行家算法課程設(shè)計(jì)

1、擊*7步/享XIANTECHNOLOGICALUNIVERSITY操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：銀行家算法安全性算法院（系）：計(jì)算機(jī)科學(xué)與工程專業(yè)：軟件工程班級(jí)：130608班學(xué)生：姚駿川學(xué)號(hào)：130608118指導(dǎo)教師：姜虹2015年12月28目錄摘要錯(cuò)誤!未定義書簽。1 緒論11.1 前言11.2 研究意義12 需求分析32.1 題目描述32.2 銀行家算法32.3 基本要求32.4 目的33 概要設(shè)計(jì)53.1 算法思路：53.2 銀行家算法步驟53.3 安全性算法步驟53.4 4數(shù)據(jù)結(jié)構(gòu)：64 詳細(xì)設(shè)計(jì)84.1 主要函數(shù)的核心代碼：84.2 系統(tǒng)主要過(guò)程流程圖84.3 銀行家算法流程圖95

2、測(cè)試與分析105.1 測(cè)試數(shù)據(jù)105.2 銀行家算法的演示105.3 分配資源由于大于可利用資源則失敗。115.4 增加一個(gè)作業(yè)得到不安全序列。115.5 分配資源由于大于最大資源則失敗。12附錄源程序清單151緒論1.1 前言Dijkstra(1965)提出了一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。它的模型基于一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，每個(gè)客戶都有一個(gè)貸款額度，銀行家知道不可能所有客戶同時(shí)都需要最大貸款額，所以他只保留一定單位的資金來(lái)為客戶服務(wù)，而不是滿足所有客戶貸款需求的最大單位。這里將客戶比作進(jìn)程，貸款比作設(shè)備，銀行家比作系統(tǒng)?？蛻魝兏髯宰鲎约旱纳猓?/p>

3、在某些時(shí)刻需要貸款。在某一時(shí)刻，客戶已獲得的貸款和可用的最大數(shù)額貸款稱為與資源分配相關(guān)的系統(tǒng)狀態(tài)。一個(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è)

4、距最大需求最近的客戶，如此反復(fù)下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn)。1.2 研究意義在多道程序系統(tǒng)中，多個(gè)進(jìn)程的并發(fā)執(zhí)行來(lái)改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖(Deadlock)，是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局(DeadlyEmbrace)，當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無(wú)外力作用，他們都無(wú)法在向前推進(jìn)。要預(yù)防死鎖，有摒棄“請(qǐng)求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件等方法。但是，在預(yù)防死鎖的幾種方法之中，都施加了較強(qiáng)的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性

5、能。在該方法中把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。而最具代表性的避免死鎖的算法，便是Dijkstra的銀行家算法。利用銀行家算法，我們可以來(lái)檢測(cè)CPU»進(jìn)程分配資源的情況，決定CP久否響應(yīng)某進(jìn)程的的請(qǐng)求并為其分配資源，從而很好避免了死鎖的產(chǎn)生。2需求分析2.1 題目描述銀行家算法是一種最具有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)的安全狀態(tài)和不安全狀態(tài)。所謂安全狀態(tài)，是指系統(tǒng)能按照某種進(jìn)程順序P1,P2,，Pn（稱P1,P2,Pn序列為安全序列），來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可以順利完成。安全狀

6、態(tài)一定沒(méi)有死鎖發(fā)生。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。那么，什么是安全序列呢？如果對(duì)每一個(gè)進(jìn)程Pi（1<i<n），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前可利用的資源量與所有的進(jìn)程Pj（j<n）所占有的資源量之和，則稱此進(jìn)程序列P1,P2,，Pn是安全的，稱作安全序列。2.2 銀行家算法我們可以把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求資源相當(dāng)于客戶向銀行家貸款。操作系統(tǒng)按銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程尚需求的資源量，若是系統(tǒng)現(xiàn)存的資源可以滿足它尚需求的資源量，則按當(dāng)前的申請(qǐng)量來(lái)分

7、配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程申請(qǐng)的資源量是否超過(guò)了它尚需的資源量。若超過(guò)則拒絕分配，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)尚存的資源是否滿足該進(jìn)程尚需的資源量，若滿足即可按當(dāng)前的申請(qǐng)量來(lái)分配，若不滿足亦推遲分配。2.3 基本要求（ 1）設(shè)計(jì)用來(lái)保存：可利用資源向量Available、最大需求矩陣Max、分配矩陣Allocation、需求矩陣Need。（2）編寫銀行家算法，安全性檢測(cè)算法。要求在不安全時(shí)輸出錯(cuò)誤信息。（ 3）編寫輸出函數(shù)，能對(duì)進(jìn)程申請(qǐng)后的系統(tǒng)狀態(tài)進(jìn)行輸出。2.4 目的根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解題目，敘述系統(tǒng)的要求，明確程序要求實(shí)現(xiàn)的功能以及限制條件

8、。明白自己需要用代碼實(shí)現(xiàn)的功能，清楚編寫每部分代碼的目的，做到有的放矢，有條理不遺漏的用代碼實(shí)現(xiàn)銀行家算法。3概要設(shè)計(jì)3.1 算法思路：先對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求是否大于需要的，是否大于可利用的。若請(qǐng)求合法，則進(jìn)行預(yù)分配，對(duì)分配后的狀態(tài)調(diào)用安全性算法進(jìn)行檢查。若安全，則分配；若不安全，則拒絕申請(qǐng)，恢復(fù)到原來(lái)的狀態(tài)，拒絕申請(qǐng)。3.2 銀行家算法步驟（1）如果Requesti<=Need,則轉(zhuǎn)向步驟（2）；否則，認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。（2）如果Request<or=Available,則轉(zhuǎn)向步驟（3）;否則，表示系統(tǒng)中尚無(wú)足夠的資源，進(jìn)

9、程必須等待。（3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available=Available-Requesti;Allocation=Allocation+Request;Need=Need-Request;4 4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。5 .3安全性算法步驟（1）設(shè)置兩個(gè)向量工作向量Work它表示系統(tǒng)可提供進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目,執(zhí)行安全算法開(kāi)始時(shí)，Work=Allocation;布爾向量Finish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開(kāi)始時(shí)先做Finishi=false，當(dāng)有足夠資源分配給進(jìn)程時(shí)

10、，令Finishi=true。2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：Finishi=falseNeed<=Work;如找到，執(zhí)行步驟(3)；否則，執(zhí)行步驟(4)。(3)當(dāng)進(jìn)程P獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work=Work+Allocation;Finishi=true;轉(zhuǎn)向步驟(2)。(4)如果所有進(jìn)程的Finishi=true,則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。34數(shù)據(jù)結(jié)構(gòu)：3.4.1 主要用到的數(shù)據(jù)結(jié)構(gòu)：(1) 最大需求矩陣Max(2) 已分配矩陣Allocation(3) 仍需求矩陣Need=Max-Allocati

11、on(4) 可利用資源向量Available(5) 申請(qǐng)各類資源向量Request(6) 工作向量work,Finish(7)存放安全序列temp(8) 存放系統(tǒng)可提供資源work(9) 資源的名字name3.4.2 程序模塊：intmain()/主函數(shù)voidshowdata()/顯示資源矩陣intchangdata(inti)/進(jìn)行資源分配intsafe()/安全性算法voidshare()網(wǎng)J用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定voidaddresources()/顏力口資源voidchangeresources()/修改資源函數(shù)voidaddprocess()/添加作業(yè)3.4.3 各模塊間

12、的調(diào)用關(guān)系：主函數(shù)voidmain()要調(diào)用：showdata()，safe()，addresources(，)addprocess(),changeresources()c,hangdata(inti)安全性檢測(cè)函數(shù)safe()銀行家算法函數(shù)share()要調(diào)用changdata(inti),showdata(),safe()4詳細(xì)設(shè)計(jì)4.1 主要函數(shù)的核心代碼：1 .進(jìn)行初始化輸入的函數(shù)2 .輸出的函數(shù)3 .利用安全性算法進(jìn)行檢測(cè)的函數(shù)4 .進(jìn)行資源分配的函數(shù)5 .利用銀行家算法進(jìn)行判定的函數(shù)4.2 系統(tǒng)主要過(guò)程流程圖圖4.1主要流程圖4.3銀行家算法流程圖圖4.2銀行家流程圖5測(cè)試與分析

13、5.1 測(cè)試數(shù)據(jù)本次測(cè)試一共5個(gè)進(jìn)程，分別為p0、pl、p2、p3、p4.,資源分配情況如下表:源情況進(jìn)程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2092302600P3222211011P4433002431結(jié)果截圖:圖5.15.2 銀行家算法的演示進(jìn)行資源的分配，為進(jìn)程1分配了（1,0,2）,進(jìn)行安全算法得到如下的結(jié)果圖 5.35.3 分配資源由于大于可利用資源則失敗。圖5.35.4 增加一個(gè)作業(yè)得到不安全序列。圖 5.45.5 分配資源由于大于最大資源則失敗5.56總結(jié)操作系統(tǒng)的基本特征是并發(fā)與共享。

14、系統(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ì)就是得用銀行家算法來(lái)避免“死鎖”。銀行家算法就是一個(gè)分配資源的過(guò)程，使分配的序列不會(huì)產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時(shí)，每次分配后總存在著一個(gè)進(jìn)程，如果讓它單獨(dú)運(yùn)行下去，必然可以獲得它所需要的全部資源，也就是說(shuō)，它能結(jié)束，而它結(jié)束后可以歸還這類資源以滿足其他申請(qǐ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)定義為整

15、型，但是卻錯(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)中、以及輸入的操作選擇不存在兩種情況分別作了判斷，并且針對(duì)第二種情況設(shè)定了五次輸入錯(cuò)誤的話系統(tǒng)關(guān)閉的功能。而因?yàn)閷?duì)于某些比如進(jìn)程號(hào)本來(lái)設(shè)定就是整型，因此對(duì)輸入的是字母的判別因比較復(fù)雜而未能加上?？傊y行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來(lái)學(xué)習(xí)借鑒。參考文獻(xiàn)1 湯小丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng).西安：西安電子科技大學(xué)出版社，2007.

16、2 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，2006.附錄源程序清單#include<iostream.h>#include<string.h>#include<stdio.h>#defineFalse0#defineTrue1intMax100100=0;/各進(jìn)程所需各類資源的最大需求intAvaliable100=0；/系統(tǒng)可用資源charname100=0;資源的名稱intAllocation100100=0；/系統(tǒng)已分配資源intNeed100100=0；/還需要資源intRequest100=0；/請(qǐng)求資源向量inttemp100=0；/存

17、放安全序列intWork100=0；/存放系統(tǒng)可提供資源intM=100;作業(yè)的最大數(shù)為100intN=100;資源的最大數(shù)為100voidshowdata。/顯示資源矩陣intij;cout«"系統(tǒng)目前可用的資源Avaliable:"vvendl;for(i=0;i<N;i+)cout«namei«"cout«endl;for(j=O;j<N;j+)cout«Avaliablej«""/輸出分配資源cout«endl;cout«"MaxAll

18、ocationNeed"«endl;COUtVV”進(jìn)程名"；for(j=0;j<3;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«"for(j=0;j<N;j+)cout«Alloc

19、ationij«"cout«"for(j=0;j<N;j+)cout<<Needij<<""cout<<endl;intchangdata(inti)/進(jìn)行資源分配intj;for(j=0;j<M;j+)Avaliablej=Avaliablej-Requestj;Allocationij=Allocationij+Requestj;Needij=Needij-Requestj;return1;intsafe()/安全性算法inti,k=0,m,a,Finish100=0;intj;in

20、tflag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;i<M;i+)a=0;for(j=0;j<N;j+)if(Finishi=False&&Needij<=Workj)a+;if(a=N)for(m=0;m<N;m+)Workm=Workm+Allocationim;/變分配數(shù)Finishi=True;tempk=i;i=-1;k+;flag+;for(i=0;i<M;i+)if(Finishi=False)cout<<"系統(tǒng)不安全"&

21、lt;<endl;/不成功系統(tǒng)不安全return-1;)coutvv”系統(tǒng)是安全的！"vvendl;如果安全，輸出成功COUtVV"分配的序歹:"；for(i=0;i<M;i+)/輸出運(yùn)行進(jìn)程數(shù)組cout«tempi;if(i<M-1)cout«"->"cout«endl;return0;)voidshare。/用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定(charch;inti=0,j=0;ch='y'cout«"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"

22、1;M-1«"):"；cin»i;/輸入須申請(qǐng)的資源號(hào)coutvv”請(qǐng)輸入進(jìn)程"«i«"申請(qǐng)的資源:"«endl;for(j=0;j<N;j+)(cout«namej«":"cin»Requestj;/輸入需要申請(qǐng)的資源)for(j=O;j<N;j+)if(Requestj>Needij)/判斷申請(qǐng)是否大于需求，若大于則出錯(cuò)(COUtVV”進(jìn)程"«i«"申請(qǐng)的資源大于它需要的資源cout&

23、#171;"分配不合理，不予分配！"«endl;ch='n'break;)elseif(RequestO>Avaliablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則/出錯(cuò)COUtVV”進(jìn)程“VViVV”申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源cout«"分配出錯(cuò)，不予分配!"«endl;ch='n'break;)if(ch='y')changdata(i);僑艮據(jù)進(jìn)程需求量變換資源showdata();/f艮據(jù)進(jìn)程需求量顯示變換后的資源safe();/服據(jù)進(jìn)程需求量進(jìn)行銀行家算

24、法判斷voidaddresources()/添力口資源intn,flag;cout<<”請(qǐng)輸入需要添加資源種類的數(shù)量：”；cin>>n;flag=N;N=N+n;for(inti=0;i<n;i+)cout<<"名稱:"cin>>nameflag;cout<<"數(shù)量:"；cin>>Avaliableflag+;showdata();safe();voiddelresources()刪除資源charming;inti,flag=1;cout<<”請(qǐng)輸入需要?jiǎng)h除的資源名

25、稱："docin>>ming;for(i=0;i<N;i+)if(ming=namei)flag=0;break;if(i=N)cout<<”該資源名稱不存在，請(qǐng)重新輸入："while(flag);for(intj=i;j<N-1;j+)namej=namej+1;Avaliablej=Avaliablej+1;N=N-1;showdata();safe();voidchangeresources()/修改資源函數(shù)cout<<"系統(tǒng)目前可用的資源Avaliable:"<<endl;for(int

26、i=0;i<N;i+)cout<<namei<<":"<<Avaliablei<<endl;cout<<"輸入系統(tǒng)可用資源Avaliable:"<<endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"經(jīng)修改后的系統(tǒng)可用資源為"<<endl;for(intk=0;k<N;k+)cout<<namek<<":&q

27、uot;<<Avaliablek<<endl;showdata();safe();voidaddprocess()/徐力口作業(yè)intflag=M;M=M+1;cout<<"請(qǐng)輸入該作業(yè)的最大需求量Max"<<endl;for(inti=0;i<N;i+)cout<<namei<<":"cin>>Maxflagi;Needflagi=Maxflagi-Allocationflagi;showdata();safe();intmain()主函數(shù)inti,j,number

28、,choice,m,n,flag;*”<<endl;charming;cout<<"*資源管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)cout<<"請(qǐng)首先輸入系統(tǒng)可供資源種類的數(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<<"請(qǐng)輸入各進(jìn)程的最大需求量("<<m<<"*"<<n<<"矩陣)Max:"<<e