試驗(yàn)二銀行家算法匯總

1、實(shí)驗(yàn)二( 3)銀行家算法一、實(shí)驗(yàn)?zāi)康?) 掌握死鎖的產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基本方法。2) 了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。3) 掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念4) 掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè) n 個(gè)并發(fā)進(jìn)程共享 m個(gè)系統(tǒng)資源的系統(tǒng)。 進(jìn)程課動(dòng)態(tài)申請(qǐng)資源和釋 放資源，系統(tǒng)按照進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。用銀行家算法設(shè)計(jì)實(shí)現(xiàn)。三、實(shí)驗(yàn)原理我們可以把操作系統(tǒng)看作是銀行家， 操作系統(tǒng)管理的資源相當(dāng)于銀行家管理 的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。為保證資金的安全 , 銀行家規(guī)定 :(1

2、) 當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就可接納 該顧客;(2) 顧客可以分歧貸款 , 但貸款的總數(shù)不能超過(guò)最大需求量 ;(3) 當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí) , 對(duì)顧客的貸款 可推遲支付 , 但總能使顧客在有限的時(shí)間里得到貸款 ;(4) 當(dāng)顧客得到所需的全部資金后 , 一定能在有限的時(shí)間里歸還所有的資 金.操作系統(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ù)與本次申

3、請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì) 資源的最大需求量。 若超過(guò)則拒絕分配資源， 若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資 源能否滿足該進(jìn)程尚需的最大資源量， 若能滿足則按當(dāng)前的申請(qǐng)量分配資源， 否 則也要推遲分配。四、算法實(shí)現(xiàn)(1) 初始化這組進(jìn)程的最大資源請(qǐng)求和依次申請(qǐng)的資源序列。 把各進(jìn)程已 占用和需求資源情況記錄在進(jìn)程控制塊中。 假定進(jìn)程控制塊的內(nèi)容包括： 進(jìn)程名， 狀態(tài)，當(dāng)前申請(qǐng)量，資源需求總量，已占資源量，能執(zhí)行完標(biāo)志。其中，進(jìn)程的 狀態(tài)有：就緒、等待和完成。當(dāng)系統(tǒng)不能滿足進(jìn)程的資源請(qǐng)求時(shí)，進(jìn)程處于等待 態(tài)。資源需求總量表示進(jìn)程運(yùn)行過(guò)程中對(duì)資源的總的需求量。已占資源量表示進(jìn)程目前已經(jīng)得到但還未歸

4、還的資源量。 因此，進(jìn)程在以后 還需要的剩余資源量等于資源需要總量減去已占資源量。 顯然每個(gè)進(jìn)程的資源需 求總量不應(yīng)超過(guò)系統(tǒng)擁有的資源總量。(2) 銀行家算法分配資源的原則是： 當(dāng)某個(gè)進(jìn)程提出資源請(qǐng)求時(shí)， 假定先 分配資源給它， 然后查找各進(jìn)程的剩余請(qǐng)求， 檢查系統(tǒng)的剩余資源量是否由于進(jìn) 程的分配而導(dǎo)致系統(tǒng)死鎖。若能，則讓進(jìn)程等待，否則，讓進(jìn)程的假分配變?yōu)檎?分配。a) 查找各進(jìn)程的剩余請(qǐng)求，檢查系統(tǒng)的剩余資源量是否能滿足其中一 進(jìn)程。如果能，則轉(zhuǎn) b) 。b) 將資源分配給所選的進(jìn)程，這樣，該進(jìn)程已獲得資源最大請(qǐng)求，最 終能運(yùn)行完成。標(biāo)記這個(gè)進(jìn)程為終止進(jìn)程，并將其占有的全部資源歸還給系統(tǒng)。重

5、復(fù)第 a) 步和第 b) 步，直到所有進(jìn)程都標(biāo)記為終止進(jìn)程，或直到一個(gè)死鎖 發(fā)生。若所有進(jìn)程都標(biāo)記為終止進(jìn)程， 則系統(tǒng)的初始狀態(tài)是安全的， 否則為不安 全的。若安全，則正式將資源分配給它，否則，假定的分配作廢，讓其等待。數(shù)據(jù)結(jié)構(gòu)：#define MAXPROCESS 50/*最大進(jìn)程數(shù) */#define MAXRESOURCE 100/* 最大資源數(shù) */* 可用資源數(shù)組 */* 最大需求矩陣 */int AVAILABLEMAXRESOURCE;int MAXMAXPROCESSMAXRESOURCE;int ALLOCATIONMAXPROCESSMAXRESOURCE; 分 /*配矩陣

6、 */int NEEDMAXPROCESSMAXRESOURCE; /* 需求矩陣 */ int REQUESTMAXPROCESSMAXRESOURCE;/*進(jìn)程需要資源數(shù) */bool FINISHMAXPROCESS;/*系統(tǒng)是否有足夠的資源分配 */int pMAXPROCESS;/* 記錄序列 */int WorkMAXRESOURCE;/* 工作數(shù)組 */int m,n;/*m個(gè)進(jìn)程 ,n 個(gè)資源*/string showdata14=max ,allo,need,aval;/*繪制資源以及進(jìn)程狀態(tài)時(shí)使用 */string showdata25=work,need,allo,w+a

7、l,finish;/*繪制銀行家算法過(guò)程時(shí)使用 */五、流程圖1：主函數(shù)流程圖：調(diào)用初始化函數(shù) (Init)安全性檢測(cè) (Safe)Y銀行家算法 (Bank)圖 1 主函數(shù)流程圖2：初始化流程圖圖 2 初始化流程圖3：安全性檢測(cè)流程圖圖 3 安全性檢測(cè)流程圖4:銀行家算法流程圖YAVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi;分配資源結(jié)束返回圖 4 銀行家算法流程圖六、源程序#include #include #include using namespa

8、ce std;#define MAXPROCESS 50/* 最大進(jìn)程數(shù) */#define MAXRESOURCE 100/* 最大資源數(shù) */int AVAILABLEMAXRESOURCE;/* 可用資源數(shù)組 */int MAXMAXPROCESSMAXRESOURCE; /* 最大需求矩陣 */ int ALLOCATIONMAXPROCESSMAXRESOURCE/*; 分 配矩陣 */ int NEEDMAXPROCESSMAXRESOURCE; /* 需求矩陣 */ int REQUESTMAXPROCESSMAXRESOURCE; / * 進(jìn)程需要資源數(shù) */* 系統(tǒng)是否有足夠

9、的資/* 記錄序列 */* 工作數(shù)組 */*m個(gè)進(jìn)程,n 個(gè)資源*/bool FINISHMAXPROCESS; 源分配 */ int pMAXPROCESS;int WorkMAXRESOURCE;int m,n;string showdata14= string showdata25= 用標(biāo)題 */max , allo , need , aval ; /* 輸出表格用標(biāo)題 */ work , need , allo , w+al , finish ; /* 輸出表格void iShow()int size,size2;cout 系統(tǒng);for (int k=0;k4;k+)size=show

10、data1k.length();size2=(n*3+5-size)/2; /* 計(jì)算出字符前端的空格 */coutsetw(size2+size)showdata1ksetw(size2) ;/* 使 得文字在資源標(biāo)志 ABC總寬度下劇中 */ coutendl; cout 資源;for (k=0;k4;k+)char sourcename=A ; /* 資源命名，從 A開(kāi)始 */ cout ;for (int kk=0;kkn;kk+)cout sourcename; sourcename+; cout ;coutendl;for (int ii=0;iim;ii+)coutP ii ;

11、/*輸出進(jìn)程名及狀態(tài) */ for (int jj=0;jjn;jj+) coutsetw(3)MAXiijj;cout ;for (jj=0;jjn;jj+) coutsetw(3)ALLOCATIONiijj;cout ;for (jj=0;jjn;jj+) coutsetw(3)NEEDiijj;cout ;if (ii=0)for (int iii=0;iiin;iii+) coutsetw(3)AVAILABLEiii;cout endl;void fShow() /* 顯示表格 */cout 系統(tǒng) ;for (int k=0;k5;k+)int size=showdata2k.le

12、ngth();int size2=(n*3+5-size)/2;coutsetw(size2+size)showdata2ksetw(size2) coutendl;cout 資源 ;for (k=0;k4;k+)char sourcename=A ;cout ;for (int kk=0;kkn;kk+)coutsetw(3)sourcename; sourcename+; cout ;coutendl;void Init() /* 初始化算法 */int i,j;coutm;coutn;cout 請(qǐng)輸入每個(gè)進(jìn)程最多所需的各資源數(shù) ,按照 mx n矩陣輸 入 endl;for (i=0;im

13、;i+)for (j=0;jMAXij;cout 請(qǐng)輸入每個(gè)進(jìn)程已分配的各資源數(shù) , 也按照 mx n 矩陣輸 入 endl;for (i=0;im;i+)for (j=0;jALLOCATIONij;NEEDij=MAXij-ALLOCATIONij;if (NEEDij0)cout您輸入的第 i+1 個(gè)進(jìn)程所擁有的第 j+1個(gè)資源數(shù)錯(cuò)誤 , 請(qǐng)重新輸入 : endl;j-;continue ;cout 請(qǐng)輸入各個(gè)資源現(xiàn)有的數(shù)目 : endl;for (i=0;iAVAILABLEi;iShow();bool Safe() /* 安全性算法 */fShow();int i,j,k,l=0;f

14、or (i=0;in;i+)Worki=AVAILABLEi;for (i=0;im;i+)FINISHi= false ;for (i=0;im;i+)if (FINISHi= true )continue ;elsefor (j=0;jWorkj)break ;if (j=n)FINISHi= true ;coutP i ;for (k=0;kn;k+) coutsetw(3)Workk; cout ;for (k=0;kn;k+) coutsetw(3)NEEDik; cout ;for (k=0;kn;k+) coutsetw(3)ALLOCATIONik; cout ;for (k=

15、0;kn;k+) coutsetw(3)Workk+ALLOCATIONik; cout ;coutsetw(3) true endl;for (k=0;kn;k+)Workk+=ALLOCATIONik;pl+=i;i=-1; /* 再次由進(jìn)程從小到大遍歷 */- 10 -else continue ;if (l=m) /* 進(jìn)程記錄 p的數(shù)量等于資源總量，全部進(jìn)程均已經(jīng)滿足 */cout 系統(tǒng)是安全的 endl;cout 安全序列 : endl;for (i=0;il;i+)coutpi;if (i!=l-1)cout ;cout endl; return true ;cout n 無(wú)法繼

16、續(xù)找到可滿足的進(jìn)程 ! endl;cout 系統(tǒng)是不安全的 endl;return false ;void Bank() /* 銀行家算法 */int i,cusneed; /*cusneed 為進(jìn)程 */char again;while (1)coutcusneed;cout n 請(qǐng)輸入進(jìn)程所請(qǐng)求的各資源的數(shù)量 endl;for (i=0;iREQUESTcusneedi;for (i=0;iNEEDcusneedi)- 11 -cout您輸入的請(qǐng)求數(shù)超過(guò)進(jìn)程的需求量 ! 請(qǐng)重新輸入 ! AVAILABLEi)cout 您輸入的請(qǐng)求數(shù)超過(guò)系統(tǒng)有的資源數(shù) ! 請(qǐng)重新輸入 ! endl;cont

17、inue ;for (i=0;in;i+) /* 先分配資源 */AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;if (Safe()cout 同意分配請(qǐng)求 ! endl;elsecout 您的請(qǐng)求被拒絕 ! endl;for (i=0;in;i+) /* 資源分配后不安全，回滾分配資源操作 */ AVAILABLEi+=REQUESTcusneedi;ALLOCATIONcusneedi-=REQUESTcusneedi;NEEDcusneedi+=REQUESTcusneed