实验二银行家算法汇总

《实验二银行家算法汇总》由会员分享，可在线阅读，更多相关《实验二银行家算法汇总（18页珍藏版）》请在装配图网上搜索。

1、实验二( 3 )银行家算法一、实验目的1) 掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。2) 了解多道程序系统中，多个进程并发执行的资源分配。3) 掌握预防死锁的方法，系统安全状态的基本概念4) 掌握银行家算法，了解资源在进程并发执行中的资源分配策略。二、实验内容设计一个 n 个并发进程共享 m 个系统资源的系统。进程课动态申请资源和释 放 资源，系统按照进程的申请动态的分配资源。用银行家算法设计实现。三、实验原理我们可以把操作系统看作是银行家， 操作系统管理的资源相当于银行家管理 的 资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全 ,银行家规定 :

2、(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳 该顾 客;(2) 顾客可以分歧贷款 , 但贷款的总数不能超过最大需求量 ;(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时 , 对顾客的贷款 可推 迟支付 , 但总能使顾客在有限的时间里得到贷款 ;(4) 当顾客得到所需的全部资金后 , 一定能在有限的时间里归还所有的资 金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时， 要 测试该进程对资源的最大需求量， 如果系统现存的资源可以满足它的最大需求 量则 按当前的申请量分配资源， 否则就推迟分配。 当进程在执行中继续申请资源 时，先 测试该进程已占用的

3、资源数与本次申请的资源数之和是否超过了该进程对 资源的最大 需求量。 若超过则拒绝分配资源， 若没有超过则再测试系统现存的资 源能否满足该 进程尚需的最大资源量， 若能满足则按当前的申请量分配资源， 否 则也要推迟分 配。四、算法实现(1) 初始化这组进程的最大资源请求和依次申请的资源序列。 把各进程已 占用 和需求资源情况记录在进程控制块中。 假定进程控制块的内容包括： 进程名， 状 态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的 状态 有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于等待 态。资源 需求总量表示进程运行过程中对资源的总的需求量。已占资源量

4、表示进程目前已经得到但还未归还的资源量。 因此，进程在以后 还 需要的剩余资源量等于资源需要总量减去已占资源量。 显然每个进程的资源需 求总 量不应超过系统拥有的资源总量。(2) 银行家算法分配资源的原则是： 当某个进程提出资源请求时， 假定先 分 配资源给它， 然后查找各进程的剩余请求， 检查系统的剩余资源量是否由于进 程的 分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真 分配。a) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一 进程。如果能，则转 b) 。b) 将资源分配给所选的进程，这样，该进程已获得资源最大请求，最 终能运行 完成。标记这个进程为终止进

5、程，并将其占有的全部资源归还给系统。重复第 a) 步和第 b) 步，直到所有进程都标记为终止进程，或直到一个死锁 发 生。若所有进程都标记为终止进程， 则系统的初始状态是安全的， 否则为不安 全 的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。/* 最大进程数 */* 最大资源数 */* 可用资源数组 */数据结构：#define MAXPROCESS 50#define MAXRESOURCE 100 int AVAILABLEMAXRESOURCE;int MAXMAXPROCESSMAXRESOURCE; /* 最大需求矩阵 */ int ALLOCATIONMAXPR

6、OCESSMAXRESOURCE; 分/*配矩阵 */ int NEEDMAXPROCESSMAXRESOURCE; /* 需求矩阵 */ intREQUESTMAXPROCESSMAXRESOURCE;/*进程需要资源数 */的资源分配*/in t pMAXPROCESS;/*int WorkMAXRESOURCE;/*int m,n; /*m string showdata14=max ,allo,need,aval;/*记录序列*/工作数组*/个进程,n个资源*/绘制资源以及进程状态时使用*/string showdata25=work,need,allo,w+al,finish;/*绘

7、制银行家算法过程时使用*/五、流程图1:主函数流程图:开始调用初始化函数(lnit)安全性检测(Safe)Y银行家算法(Bank)图 1 主函数流程图2:初始化流程图Init()丿始输入进程的数H输入疋确NY显示当前系统状态(iShow)结束返I输入 ALLOCATIONijI输入 MAXij输入 AVAELABLEij提示错谋,匝新 输入朴I应数据输入资源的种类n图 2 初始化流程图YN所右进程FINISHi-ture结束返回系统不安冷，返回 false输山进在及资漁变化结果Worki=A VAILABLEi;FNISHiHa!se;NEEDi=Work&FINISHi=falseWorki

8、+=ALLOCA TIONi F!NISHi=true输出找到的安全序列、返回 true(Safe。开始绘制结果表格头部(fShow)图 3 安全性检测流程图4:银行家算法流程图REQUESTcusneed 刖 u =NEEDcusneedi(Bank()廿始输入进程诂求资源REQUESTcusneedi输入请求资源的进稈cusneedYREQUESTcusneedi=AVAILABLEiAVAILABLEi-=REQUESTcus needi;ALLOCATIONcus needi+=REQUESTcusneedi; NEEDcus needi-=REQUESTcus图 4 银行家算法流程图

9、六、源程序#in clude #include #include using namespacestd;#define MAXPROCESS 50#define MAXRESOURCE 100/* 最大进程数 */* 最大资源数 */int AVAILABLEMAXRESOURCE; /* 可用资源数组 */ int MAXMAXPROCESSMAXRESOURCE; /* 最大需求矩阵 */ int ALLOCATIONMAXPROCESSMAXRESOURCE/*; 分配矩阵 */ intNEEDMAXPROCESSMAXRESOURCE; /* 需求矩阵 */ intREQUESTMAX

10、PROCESSMAXRESOURCE; /* 进程需要资源数 */* 系统是否有足够的资/* 记录序列 */* 工作数组 */*m个进程,n个资源*/bool FINISHMAXPROCESS; 源分配 */ int pMAXPROCESS;int WorkMAXRESOURCE;int m,n;string max , showdata14= string allo ,need,aval ; /*输showdata25= 用标出表格用标题 */ work , need , allo , w+al ,finish ; /*输出表格void iShow()int size,size2;cout

11、系统;for (int k=0;k4;k+)size=showdata1k.length();size2=(n*3+5-size)/2;/* 计算出字符前端的空格 */coutsetw(size2+size)showdata1ksetw(size2) ;/*使 得文字 在资源标志 ABC 总宽度下剧中*/coutendl; cout 资源 ;for (k=0;k4;k+)char sourcename=A ; /* 资源命名，从 A 开始*/ cout ;for (int kk=0;kkn;kk+)cout sourcename; sourcename+;cout ;coutendl;for

12、(int ii=0;iim;ii+)cout P ii ;/* 输出进程名及状态 */ 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 系统 ;for (in

13、t k=0;k5;k+)int size=showdata2k.length();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;coutvv请输入每个进程最多所需

14、的各资源数，按照mx * ,矩阵输入 endl;for (i=0;im;i+)for (j=0;jMAXij;coutvv请输入每个进程已分配的各资源数,也按照vvmvvx vvn ,矩阵输入 ALLOCATIONij;NEEDij=MAXij-ALLOCATIONij;if (NEEDijv0)coutvv您输入的第vvi+1vv个进程所拥有的第vvj+1vv个资源数错误 , 请重新输入 : vvendl;j-;continue ;coutvv 请输入各个资源现有的数目 : vvendl;for (i=0;ivn;i+) cinAVAILABLEi;iShow();bool Safe()/*

15、 安全性算法 */fShow();int i,j,k,l=0;for (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+) c

16、outsetw(3)ALLOCATIONik; cout for (k=0;kn;k+) coutsetw(3)Workk+ALLOCATIONik; cout ;coutsetw(3) true endl;for (k=0;kn;k+) Workk+=ALLOCATIONik; pl+=i;i=-1; /* 再次由进程从小到大遍历 */else continue ;if (l=m) /*进程记录 p 的数量等于资源总量，全部进程均已经满足*/cout 系统是安全的 endl;cout 安全序列 : endl;for (i=0;il;i+) coutpi;if (i!=l-1) cout ;

17、cout endl; return true ; cout n 无法继续找到可满足的进程 ! endl;cout 系统是不安全的 cusneed;coutvv n请输入进程所请求的各资源的数量vvendl;for (i=0；iREQUESTcusneedi;for (i=0;ivn;i+)if (REQUESTcusneediNEEDcusneedi)coutvv您输入的请求数超过进程的需求量 ! 请重新输入 ! vvendl;continue ;if (REQUESTcusneediAVAILABLEi)coutvv 您输入的请求数超过系统有的资源数 ! 请重新输入 ! vvendl;con

18、tinue ;for (i=0;ivn;i+) /*先分配资源 */AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;if (Safe()coutvv 同意分配请求 ! vvendl;elsecoutvv 您的请求被拒绝 ! vvendl;for (i=0;ivn;i+) /*资源分配后不安全，回滚分配资源操作 */ AVAILABLEi+=REQUESTcusneedi;ALLOCATIONcusneedi-=REQUESTcusneedi;NEEDcusneedi+=REQUESTcusneedi;for (i=0;ivm;i+)FINISHi= false ;endl;coutagain;if (again= y |again= Y ) continue ; break ;void main()while (true )Init();if (Safe() break ; /* 如果初始化安全，跳出while 循环 */cout 当前系统不安全，请重新初始化系统 n Bank();七、实验结果及分析 八、心得体会七、运行示例及结果分析结果分析：八、心得体会