《計(jì)算機(jī)操作系統(tǒng)》銀行家算法實(shí)驗(yàn)

1、海南大學(xué)三亞學(xué)院計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)死鎖的避免銀行家算法專業(yè)班級(jí)：成員：提交時(shí)間：一、問題描述（標(biāo)題：宋體四號(hào)）內(nèi)容： 1、解釋什么是銀行家算法（宋體，小四，行間距1.5 倍）銀行家算法又稱“資源分配拒絕”法，其基本思想是，系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)受到進(jìn)程的請(qǐng)求后試探性的把資源分配給他，現(xiàn)在系統(tǒng)將剩下的資源和進(jìn)程集合中其他進(jìn)程還需要的資源數(shù)做比較，找出剩余資源能滿足最大需求量的進(jìn)程，從而保證進(jìn)程運(yùn)行完成后還回全部資源。這時(shí)系統(tǒng)將該進(jìn)程從進(jìn)程集合中將其清除。此時(shí)系統(tǒng)中的資源就更多了。反復(fù)執(zhí)行上面的步驟，最后檢查進(jìn)程的集合為空時(shí)就表明本次申請(qǐng)可行，系統(tǒng)處于安全狀態(tài)，可以實(shí)施

2、本次分配，否則，只要進(jìn)程集合非空，系統(tǒng)便處于不安全狀態(tài)，本次不能分配給他。請(qǐng)進(jìn)程等待我們可以把操作系統(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)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則

3、按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。2、銀行家算法提出的原因在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的 資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)一一死鎖。所謂死鎖(Deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局(Deadly_Embrace)當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再 向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。二、實(shí)驗(yàn)?zāi)康?、掌握死鎖概念、死鎖發(fā)生的原因、死鎖產(chǎn)生的必要條件2 、掌握死鎖的預(yù)防、死鎖的避免3 、深

4、刻理解死鎖的避免：安全狀態(tài)和銀行家算法三、問題分析1、什么是死鎖？死鎖如何產(chǎn)生？所謂死鎖， 是指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力的作用，它們都將無法再向前推進(jìn)。死鎖產(chǎn)生的原因：（ 1）競爭資源（ 2）進(jìn)程間推進(jìn)順序非法產(chǎn)生死鎖的必要條件：互斥條件，請(qǐng)求和保持條件不剝奪條件，環(huán)路等待條件。只要下面四個(gè)條件中有一個(gè)不具備，系統(tǒng)就不會(huì)出現(xiàn)死鎖?；コ鈼l件：即某個(gè)資源在一段時(shí)間內(nèi)只能由一個(gè)進(jìn)程占有，不能同時(shí)被兩個(gè)或兩個(gè)以上的進(jìn)程占有。不可搶占條件：進(jìn)程所獲得的資源在未使用完畢之前，資源申請(qǐng)者不能強(qiáng)行地從資源占有者手中奪取資源， 而只能由該資源的占有者進(jìn)程

5、自行釋放。占有且申請(qǐng)條件：進(jìn)程至少已經(jīng)占有一個(gè)資源，但又申請(qǐng)新的資源；由于該資源已被另外進(jìn)程占有，此時(shí)該進(jìn)程阻塞；但是，它在等待新資源之時(shí)，仍繼續(xù)占用已占有的資源。循環(huán)等待條件：存在一個(gè)進(jìn)程等待序列P1,P2, - Pn,其中P1 等待 P2 所占有的某一資源， P2 等待 P3 所占有的某一資源，而Pn等待P1所占有的某一資源，形成一個(gè)進(jìn)程循環(huán)等待環(huán)。2、死鎖對(duì)多道程序系統(tǒng)帶來的影響？在多道程序系統(tǒng)中， 雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行， 來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖（Deadlock）,是指多個(gè)進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局（Deadly_

6、Embrace）當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再 向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程 。3、如何預(yù)防死鎖？摒棄“請(qǐng)求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件4、死鎖的預(yù)防：什么是安全態(tài)？如何保證多個(gè)進(jìn)程在某個(gè)時(shí)刻是處于安全態(tài)的？所謂安全態(tài)是指系統(tǒng)能按某種進(jìn)程順序（P1, P2,，Pn） （稱（P1, P2,，Pn）序列為安全序列）來為每個(gè)進(jìn)程 Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都順利的完成。四、設(shè)計(jì)方案1、數(shù)據(jù)結(jié)構(gòu)的建立

7、1) .可利用資源向量AVAILABLE這是一個(gè)含有M元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其3初始值是系統(tǒng)中所配置的該類全部可哦那個(gè)資源的數(shù)目， 其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)的改變。2) .最大需求矩陣MAX這是一個(gè)M*N勺矩陣，它定義了系統(tǒng)中N 個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)M類資源的最大需求。3) .分配矩陣ALLOCATION這也是一個(gè)M*N勺矩陣，它定義了系統(tǒng) 中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。4) .需求矩陣NEED這也是一個(gè)M*N勺矩陣，用以表示每一個(gè)進(jìn)程 尚需的各類資源數(shù)。5) .NEEDR,W=MAXR,W-ALLOCATIONR,W數(shù)據(jù)結(jié)構(gòu)詳細(xì)介紹如下

8、：假設(shè)有M個(gè)進(jìn)程N(yùn)類資源，則有如下數(shù)據(jù)結(jié)構(gòu)：#define W 10#define R 20int A ； / 總進(jìn)程數(shù)int B ； / 資源種類int ALL_RESOURCEW; / 各種資源的數(shù)目總和int MAXW; /M個(gè)進(jìn)程對(duì)N類資源最大資源需求量int AVAILABLE ; / 系統(tǒng)可用資源數(shù)int ALLOCATIONW ; /M 個(gè)進(jìn)程已經(jīng)得到N類資源的資源量int NEEDW ; /M 個(gè)進(jìn)程還需要N類資源的資源量int Request ; / 請(qǐng)求資源個(gè)數(shù)主要函數(shù)說明void showdata();/ 主要用來輸出資源分配情況void changdata(int);

9、/主要用來輸出資源分配后后的情況void rstordata(int); /用來恢復(fù)資源分配情況, 如:銀行家算法時(shí) , 由于分配不安全則要恢復(fù)資源分配情況int chkerr(int); / 銀行家分配算法的安全檢查void bank();/ 銀行家算2、算法的設(shè)計(jì)設(shè) Requesti 是進(jìn)程 Pi 的請(qǐng)求向量。 如果 Requesti , j=k ，表示 Pi 需 k 個(gè) Rj 類資源。 當(dāng) Pi 發(fā)出資源請(qǐng)求后， 系統(tǒng)按下述步驟進(jìn)行檢查 :(1) if (Requesti<=Needi) goto (2);else error( “over request ” );(2) if (

10、Requesti<=Availablei) goto (3);else wait();(3) 系統(tǒng)試探性把要求資源分給Pi (類似回溯算法)。并根據(jù)Requesti分配修改下面數(shù)據(jù)結(jié)構(gòu)中的值。Availablei = AvailableiAllocationi = Allocationi + RequestiNeedi = Needi-Requesti;(4) 系統(tǒng)執(zhí)行安全性檢查，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程以完成此次分配；若不安全，試探方案作廢，恢復(fù)原資源分配表，讓進(jìn)程Pi 等待。系統(tǒng)所執(zhí)行的安全性檢查算法可描述如下：設(shè)置兩個(gè)向量： Free

11、 、 Finish工作向量 Free 是一個(gè)橫向量，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目， 它含有的元素個(gè)數(shù)等于資源數(shù)。 執(zhí)行安全算法開始時(shí)，F(xiàn)ree = Available.標(biāo)記向量 Finish 是一個(gè)縱向量，表示進(jìn)程在此次檢查中中是否被滿足，使之運(yùn)行完成，開始時(shí)對(duì)當(dāng)前未滿足的進(jìn)程做Finishi =false ；當(dāng)有足夠資源分配給進(jìn)程(Needi<=Free) 時(shí)，F(xiàn)inishi=true ， Pi 完成，并釋放資源。(1) 從進(jìn)程集中找一個(gè)能滿足下述條件的進(jìn)程Pi Finishi = false( 未定 ) Needi <= Free （ 資源夠分 ）(2) 當(dāng)

12、 Pi 獲得資源后，認(rèn)為它完成，回收資源:Free = Free + Allocationi ;Finishi = true ;Go to step(1);試探此番若可以達(dá)到Finish0.n:=true，則表示系統(tǒng)處于安全狀態(tài)， 然后再具體為申請(qǐng)資源的進(jìn)程分配資源。 否則系統(tǒng)處于不安全狀態(tài)。3、算法的優(yōu)化4、研究問題的推廣五、方案實(shí)施1、任務(wù)劃分(1) 流程圖初始化算法流程圖銀行家算法流程圖：安全性算法流程圖：2、具體代碼#include <string.h>#include <iostream>using namespace std ;#define FALSE 0

13、#define TRUE 1#define W 10 / 最大進(jìn)程數(shù)W=10#define R 20 / 最大資源總數(shù)R=20int M ;int N ;int ALL_RESOURCEW;int AVAILABLER; / 可利用資源向量int MAXWR; / 最大需求矩陣需求矩陣進(jìn)程請(qǐng)求向量數(shù)據(jù)輸入數(shù)據(jù)顯示進(jìn)程請(qǐng)求資源數(shù)據(jù)改變數(shù)據(jù)恢復(fù)系統(tǒng)安全性的檢測(cè)檢測(cè)最大需求int ALLOCATIONWR; / 分配矩陣int NEEDWR; / int RequestR; / void inputdata(); / void showdata(); / void changdata(int k);

14、/ void restoredata(int k); / int chksec(int s); / int chkmax(int s); /void bank(); / 檢測(cè)分配的資源是否合理void main() int i,j;inputdata();for(i=0;i<M;i+) j=chksec(i);if (j=0) break;if (i>=M)cout<<" 錯(cuò)誤提示： 經(jīng)安全性檢查發(fā)現(xiàn)， 系統(tǒng)的初始狀態(tài)不安全！ ！ ！ n"<<endl;else"<<endl; cout<<"

15、提示：經(jīng)安全性檢查發(fā)現(xiàn)，系統(tǒng)的初始狀態(tài)安全！ bank();)void inputdata() int i=0,j=0,p;cout<<" 請(qǐng)輸入總進(jìn)程數(shù):"<<endl;docin>>M;if (M>W) cout<<endl<<"總進(jìn)程數(shù)超過了程序允許的最大進(jìn)程數(shù)，請(qǐng)重新輸入:"<<endl;while (M>W);cout<<endl;cout<<"請(qǐng)輸入資源的種類數(shù):"<<endl;do cin>>

16、;N;if (N>R)cout<<endl<<"資源的種類數(shù)超過了程序允許的最大資源種類數(shù)，請(qǐng)重新輸入:"<<endl; while (N>R);cout<<endl;cout<<"請(qǐng)依次輸入各類資源的總數(shù)量，即設(shè)置向量all_resource:"<<endl;for(i=0;i<N;i+)cin>>ALL_RESOURCEi;cout<<endl;cout<<"請(qǐng)依次輸入各進(jìn)程所需要的最大資源數(shù)量，即設(shè)置矩陣 max:

17、"<<endl;for (i=0;i<M;i+)for (j=0;j<N;j+)do cin>>MAXij;if (MAXij>ALL_RESOURCEj)入 :"<<endl; while (MAXij>ALL_RESOURCEj);cout<<endl;cout<<" 請(qǐng)依次輸入各進(jìn)程已經(jīng)占據(jù)的各類資源數(shù)量，即設(shè)置矩陣allocation:"<<endl;for (i=0;i<M;i+)for (j=0;j<N;j+)do cin>>

18、;ALLOCATIONij;if (ALLOCATIONij>MAXij) cout<<endl<<" 已占有的資源數(shù)量超過了聲明的最大資源數(shù)量請(qǐng)重新輸入 :"<<endl;while (ALLOCATIONij>MAXij);cout<<endl;for (i=0;i<M;i+)for(j=0;j<N;j+)NEEDij=MAXij-ALLOCATIONij;for (j=0;j<N;j+) p=ALL_RESOURCEj;for (i=0;i<M;i+) p=p-ALLOCATIONij

19、;AVAILABLEj=p;if(AVAILABLEj<0)AVAILABLEj=0;)void showdata() int i j;cout«"各種資源的總數(shù)量，即向量 all_resource 為:"vvendl;cout«"for (j=Oj<N；j+)cout«"資源"vvjvv"： "«ALL_RESOURCEj;cout«endl«endl;cout«"當(dāng)前系統(tǒng)中各類資源的可用數(shù)量，即向量 available為:&quo

20、t;vvendl;cout«"for (j=Oj<N；j+)cout«"資源"vvjvv"： "«AVAILABLEj;cout«endl«endl;cout«"各進(jìn)程還需要的資源數(shù)量，即矩陣 need為:"vvendlvvendl;for (i=0;i<M;i+)cout«"進(jìn)程 P"«i«":for (j=O;j<N;j+)cout«NEEDij«"cou

21、t«endl;)cout«endl;cout«"各進(jìn)程已經(jīng)得到的資源量，即矩陣 allocation "«endl«endl;for (i=0;i<M;i+) cout«"進(jìn)程 P”vvivv"："；for (j=O;j<N;j+)cout«ALLOCATIONij«"cout«endl; cout<<endl;void changdata(int k) int j;for (j=0;j<N;j+)AVAILABLE

22、j=AVAILABLEj-Requestj;ALLOCATIONkj=ALLOCATIONkj+Requestj;NEEDkj=NEEDkj-Requestj;void restoredata(int k)int j;for (j=0;j<N;j+) AVAILABLEj=AVAILABLEj+Requestj;ALLOCATIONkj=ALLOCATIONkj-Requestj;NEEDkj=NEEDkj+Requestj;int chksec(int s)int WORK,FINISHW;int i,j,k=0;for(i=0;i<M;i+)FINISHi=FALSE;for(

23、j=0;j<N;j+) WORK=AVAILABLEj;i=s;do if(FINISHi=FALSE&&NEEDij<=WORK)WORK=WORK+ALLOCATIONij;FINISHi=TRUE;i=0;elsei+;while(i<M);for(i=0;i<M;i+)if(FINISHi=FALSE) return 1; return 0;int chkmax(int s) int j,flag=0;for(j=0;j<N;j+)if (MAXsj=ALLOCATIONsj) flag=1;AVAILABLEj=AVAILABLEj+MA

24、Xsj;MAXsj=0; return flag;void bank()int i=0,j=0;char flag='Y'while(flag='Y'|flag='y')(i=-1;while(i<0|i>=M) cout<<"請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)(從 P0到P”<<M-1<<”,否則重新輸入！)：”；cout<<"p"cin>>i;if(i<0|i>=M)cout<<"輸入的進(jìn)程號(hào)不存在，重新輸入！&quo

25、t;<<endl;cout<<" 請(qǐng)輸入進(jìn)程 P"<<i<<"申請(qǐng)的資源數(shù):"<<endl;for (j=0;j<N;j+) cout<<"資源"<<j<<":"cin>>Requestj;if(Requestj>NEEDij) cout<<" 進(jìn)程P"<<i<<"申請(qǐng)的資源數(shù)大于進(jìn)程 P"<<i<<"還需要 "<<j<<"類資源的資源量!"cout<<" 申請(qǐng)不合理，出錯(cuò)！請(qǐng)重新選擇！"<<endl<<endl;flag='N'break; else if(Requestj&