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

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：銀行家算法 安全性算法院 （系）：計(jì)算機(jī)科學(xué)與工程專(zhuān) 業(yè)：軟件工程班 級(jí)：130608班學(xué) 生：姚駿川學(xué) 號(hào)：130608118指導(dǎo)教師：姜虹 2015年12月28 目錄摘 要21 緒論11.1前言11.2研究意義12 需求分析32.1題目描述32.2銀行家算法32.3基本要求32.4目的33 概要設(shè)計(jì)53.1算法思路：53.2銀行家算法步驟53.3安全性算法步驟534數(shù)據(jù)結(jié)構(gòu)：64 詳細(xì)設(shè)計(jì)84.1主要函數(shù)的核心代碼：84.2系統(tǒng)主要過(guò)程流程圖84.3銀行家算法流程圖95 測(cè)試與分析105.1測(cè)試數(shù)據(jù)105.2銀行家算法的演示105.3分配資源由于大于可利用資源則失

2、敗。115.4 增加一個(gè)作業(yè)得到不安全序列。115.5分配資源由于大于最大資源則失敗。12附錄 源程序清單151 緒論1.1前言Dijkstra (1965)提出了一種能夠避免死鎖的調(diào)度算法，稱(chēng)為銀行家算法。它的模型基于一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶(hù)分別承諾了一定的貸款額度，每個(gè)客戶(hù)都有一個(gè)貸款額度，銀行家知道不可能所有客戶(hù)同時(shí)都需要最大貸款額，所以他只保留一定單位的資金來(lái)為客戶(hù)服務(wù)，而不是滿(mǎn)足所有客戶(hù)貸款需求的最大單位。這里將客戶(hù)比作進(jìn)程，貸款比作設(shè)備，銀行家比作系統(tǒng)?？蛻?hù)們各自做自己的生意，在某些時(shí)刻需要貸款。在某一時(shí)刻，客戶(hù)已獲得的貸款和可用的最大數(shù)額貸款稱(chēng)為與資源分配相關(guān)的系統(tǒng)狀態(tài)。

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

4、。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)的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿(mǎn)意的系統(tǒng)性能。在該方法中把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。而最具代表性的避免死鎖的算法，

5、便是Dijkstra的銀行家算法。利用銀行家算法，我們可以來(lái)檢測(cè)CPU為進(jìn)程分配資源的情況，決定CPU是否響應(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（稱(chēng)P1,P2,，Pn 序列為安全序列），來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿(mǎn)足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可以順利完成。安全狀態(tài)一定沒(méi)有死鎖發(fā)生。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)。那么，什么是安全序列呢？

6、如果對(duì)每一個(gè)進(jìn)程Pi(1<i<n)，它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前可利用的資源量與所有的進(jìn)程Pj(j<n)所占有的資源量之和，則稱(chēng)此進(jìn)程序列P1,P2,，Pn是安全的，稱(chēng)作安全序列。2.2銀行家算法 我們可以把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求資源相當(dāng)于客戶(hù)向銀行家貸款。操作系統(tǒng)按銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程尚需求的資源量，若是系統(tǒng)現(xiàn)存的資源可以滿(mǎn)足它尚需求的資源量，則按當(dāng)前的申請(qǐng)量來(lái)分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程申請(qǐng)的資源量是否超過(guò)了它尚需的資源量

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

8、算法。3 概要設(shè)計(jì)3.1算法思路： 先對(duì)用戶(hù)提出的請(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）如果Requestor=Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無(wú)足夠的資源，進(jìn)程必須等待。（3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available=Availabl

9、e-Requesti;Allocation=Allocation+Request;Need=Need-Request;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。3.3安全性算法步驟（1）設(shè)置兩個(gè)向量工作向量Work。它表示系統(tǒng)可提供進(jìn)程繼續(xù)運(yùn)行所需要的各類(lèi)資源數(shù)目，執(zhí)行安全算法開(kāi)始時(shí)，Work=Allocation;布爾向量Finish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開(kāi)始時(shí)先做Finishi=false，當(dāng)有足夠資源分配給進(jìn)程時(shí)，令Finishi=true。（2）從進(jìn)程集合中找到一個(gè)能滿(mǎn)足下述條件的進(jìn)程：Finishi=falseNeed<

10、 =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)：主要用到的數(shù)據(jù)結(jié)構(gòu)：(1) 最大需求矩陣Max(2) 已分配矩陣Allocation(3) 仍需求矩陣Need=Max-Allocation(4) 可利用資源向量Available(5) 申請(qǐng)各類(lèi)資源向量Request(6) 工作向量 work , Finish

11、（7）存放安全序列 temp(8) 存放系統(tǒng)可提供資源 work(9)資源的名字 name程序模塊： int main()/主函數(shù)void showdata()/顯示資源矩陣int changdata(int i)/進(jìn)行資源分配int safe()/安全性算法void share()/利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定void addresources()/添加資源void changeresources()/修改資源函數(shù)void addprocess()/添加作業(yè)各模塊間的調(diào)用關(guān)系：主函數(shù)void main()要調(diào)用： showdata()，safe()，addresources()，add

12、process(),changeresources(),changdata(int i)安全性檢測(cè)函數(shù)safe()銀行家算法函數(shù)share() 要調(diào)用 changdata(int i), 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è)試與分析5.1測(cè)試數(shù)據(jù)本次測(cè)試一共5個(gè)進(jìn)程，分別為p0、p1、p2、p3、p4.，資源分配情況如下表：資源情況

13、進(jìn)程MaxA B CAllocationA B CNeedA B CAvailableA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P20 9 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1結(jié)果截圖：圖5.15.2銀行家算法的演示進(jìn)行資源的分配，為進(jìn)程1分配了（1，0，2），進(jìn)行安全算法得到如下的結(jié)果。圖5.25.3分配資源由于大于可利用資源則失敗。圖5.35.4 增加一個(gè)作業(yè)得到不安全序列。圖5.45.5分配資源由于大于最大資源則失敗。圖5.56 總結(jié)操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行

14、，并且共享系統(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é)束后可以歸還這類(lèi)資源以滿(mǎn)足其他申請(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)定義為整型，但是卻錯(cuò)輸成字母等情

15、況，我們需要對(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ù)雜而未能加上。總之，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來(lái)學(xué)習(xí)借鑒。參考文獻(xiàn)1 湯小丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng). 西安：西安電子科技大學(xué)出版社，2007.2 嚴(yán)蔚敏，吳偉民.數(shù)

16、據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，2006.附錄 源程序清單#include<iostream.h>#include<string.h>#include<stdio.h>#define False 0#define True 1int Max100100=0;/各進(jìn)程所需各類(lèi)資源的最大需求int Avaliable100=0;/系統(tǒng)可用資源char name100=0;/資源的名稱(chēng)int Allocation100100=0;/系統(tǒng)已分配資源int Need100100=0;/還需要資源int Request100=0;/請(qǐng)求資源向量int temp100=0

17、;/存放安全序列int Work100=0;/存放系統(tǒng)可提供資源int M=100;/作業(yè)的最大數(shù)為100int N=100;/資源的最大數(shù)為100void showdata()/顯示資源矩陣 int i,j; cout<<"系統(tǒng)目前可用的資源Avaliable:"<<endl; for(i=0;i<N;i+) cout<<namei<<" " cout<<endl; for (j=0;j<N;j+) cout<<Avaliablej<<" &quo

18、t;/輸出分配資源 cout<<endl; cout<<" Max Allocation Need"<<endl; cout<<"進(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<<&qu

19、ot; " for(j=0;j<N;j+) cout<<Maxij<<" " cout<<" " for(j=0;j<N;j+) cout<<Allocationij<<" " cout<<" "for(j=0;j<N;j+) cout<<Needij<<" " cout<<endl; int changdata(int i)/進(jìn)行資源分配 int j;for

20、(j=0;j<M;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj;return 1;int safe()/安全性算法int i,k=0,m,a,Finish100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;i<M;i+) a=0; for(j=0;j<N;j+) if (Finishi=False&&Need

21、ij<=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)不安全"<<endl;/不成功系統(tǒng)不安全 return -1; cout<<"系統(tǒng)是安全的!"<<endl;/如果安全，輸出成功 cout<<"分配的序列:"

22、;for(i=0;i<M;i+)/輸出運(yùn)行進(jìn)程數(shù)組 cout<<tempi; if(i<M-1) cout<<"->" cout<<endl; return 0;void share()/利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定char ch;int i=0,j=0;ch='y'cout<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<<M-1<<"):" cin>>i;/輸入須申請(qǐng)的資源號(hào)cout<<"請(qǐng)輸入

23、進(jìn)程 "<<i<<" 申請(qǐng)的資源:"<<endl;for(j=0;j<N;j+) cout<<namej<<":" cin>>Requestj;/輸入需要申請(qǐng)的資源 for (j=0;j<N;j+) if(Requestj>Needij)/判斷申請(qǐng)是否大于需求，若大于則出錯(cuò) cout<<"進(jìn)程 "<<i<<"申請(qǐng)的資源大于它需要的資源" cout<<" 分配不

24、合理，不予分配！"<<endl; ch='n' break; else if(Requestj>Avaliablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則 /出錯(cuò) cout<<"進(jìn)程"<<i<<"申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源" cout<<" 分配出錯(cuò)，不予分配!"<<endl; ch='n' break; if(ch='y') changdata(i);/根據(jù)進(jìn)程需求量變換資源 showdat

25、a();/根據(jù)進(jìn)程需求量顯示變換后的資源 safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 void addresources()/添加資源 int n,flag;cout<<"請(qǐng)輸入需要添加資源種類(lèi)的數(shù)量:"cin>>n;flag=N;N=N+n;for(int i=0;i<n;i+) cout<<"名稱(chēng):" cin>>nameflag; cout<<"數(shù)量:" cin>>Avaliableflag+;showdata();safe();void delr

26、esources()/刪除資源char ming;int i,flag=1;cout<<"請(qǐng)輸入需要?jiǎng)h除的資源名稱(chēng)："do cin>>ming;for(i=0;i<N;i+) if(ming=namei) flag=0; break; if(i=N) cout<<"該資源名稱(chēng)不存在，請(qǐng)重新輸入："while(flag);for(int j=i;j<N-1;j+) namej=namej+1; Avaliablej=Avaliablej+1; N=N-1;showdata();safe();void chan

27、geresources()/修改資源函數(shù)cout<<"系統(tǒng)目前可用的資源Avaliable:"<<endl; for(int i=0;i<N;i+) cout<<namei<<":"<<Avaliablei<<endl;cout<<"輸入系統(tǒng)可用資源Avaliable:"<<endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"

28、經(jīng)修改后的系統(tǒng)可用資源為"<<endl;for (int k=0;k<N;k+) cout<<namek<<":"<<Avaliablek<<endl;showdata();safe();void addprocess()/添加作業(yè) int flag=M;M=M+1;cout<<"請(qǐng)輸入該作業(yè)的最大需求量Max"<<endl;for(int i=0;i<N;i+) cout<<namei<<":" cin&

29、gt;>Maxflagi; Needflagi=Maxflagi-Allocationflagi;showdata();safe();int main()/主函數(shù) int i,j,number,choice,m,n,flag;char ming;cout<<"*資源管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)*"<<endl;cout<<"請(qǐng)首先輸入系統(tǒng)可供資源種類(lèi)的數(shù)量 :"cin>>n;N=n;for(i=0;i<n;i+) cout<<"資源"<<i+1<<"的名稱(chēng):" 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:"<&l