银行家算法实验报告35989795.pdf

《银行家算法实验报告35989795.pdf》由会员分享，可在线阅读，更多相关《银行家算法实验报告35989795.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统实验报告 课题：银行家算法 专 业：班 级：学 号：姓 名：年 月 日 .目 录 一 实验目的 错误!未定义书签。二 实验内容 3 三 问题描述 3 四 设计思路 4 五 详细设计 5 六 运行结果 10 七 心得体会 16 八 参考文献 17 附 源程序 17 .一、实验目的 模拟实现银行家算法，用银行家算法实现资源分配。1加深了解有关资源申请、避免死锁等概念。2体会和了解死锁和避免死锁的具体实施方法。3、输入：1.系统中各类资源表 2.每个进程需要各类资源总数 系统分配给各个进程各类资源数 4、输出：1.判断 T0 时刻的安全性 2.如果系统是安全的，任意给出某个进程的一个资源请

2、求方式并判断系统能否接受此请求，如果可以接受，其输出全部安全序列，反之，不予分配。二、实验内容 1设计进程对各类资源最大申请表示及初值的确定。2设定系统提供资源的初始状况。3设定每次某个进程对各类资源的申请表示。4编制程序，依据银行家算法，决定其资源申请是否得到满足。5显示资源申请和分配时的变化情况。三、问题描述 银行家算法.顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，

3、以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。.在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。所谓安全状态，是指系统能按某种顺序为每个进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成，即可找到一个安全资源分配序列。模拟实现这个工作过程。四、设计思路 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求

4、量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法是一种最具代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列 P1，Pn，则系统处于安全状态。安全状态一定没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一

5、定导致死锁。.安全序列：一个进程序列P1，Pn是安全的，如果对于每个进程 Pi（0in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj（ji）当前占有资源量之和。先对系统从源文件中读取的数据进行安全性判断，然后对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，不大于系统可利用的资源。若请求合法，则进行试分配，最后对试分配状态调用安全性算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。五、详细设计 1、初始化 由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵 MAX、分配矩阵 ALLOCATION、需求矩阵 NEED 赋值

6、。2、银行家算法 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。设进程 cusneed 提出请求 REQUEST i，则银行家算法按如下规则进行判断。(1)如果 REQUEST cusneed i=NEEDcusneedi，则转(2)；否则，出错。.(2)如果 REQUEST cusneed i=AVAILABLEcusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVA

7、ILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。(5)对于某一进程 i，若对所有的 j，有 NEEDij=0，则表此进程资源分配完毕，应将占用资源释放。3、安全性检查算法(1)设置两个工作向量 Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEEDNEEDi或者 REQUESTiAVAILABLEi 报错

8、，重新输入 AVAILABLEi-=REQUEST i;ALLOCATIONi+=REQUEST i;NEEDi-=REQUESTi;初始化 安全性检查 安全 AVAILABLEi+=REQUEST i;ALLOCATIONi-=REQUEST i;NEEDi+=REQUESTi;保持原分配 进 程 执 行释放资源 继续分配 结束 YES NO YES NO YES YES NO NO.2、判断系统的安全性 Safe（）Safe（）开始初始化i，j，t,tempnFihishi=falsetp=(Work0=Needi0)&(Work1=Needi1)&(Work2=Needi2)Tempn=

9、0?Fin_pro?Finishi=0?Ytp=1?Finishi=true;Workj+=Allocationij;YYi+FTempn-Finishi=0?i=0in_pro?系统不安全YY结束i+F安全序列函数 .六、运行结果 1、系统不安全的输入（1）、本程序按下图建立.txt 源文件，作为程序的初始化输入 （2）执行程序，读取源文件，并判断 T0 时刻所得结果:.2.系统安全的输入（1）、本程序按下图建立.txt 源文件，作为程序的初始化输入 （2）执行程序，读取源文件，并判断T0 时刻所得结果:.（3）T0 时刻的安全序列 （4）不合理的分配 输入 P1 进程 Request（2

10、2 1）与输入 P2 进程 Request（2 2 2）所得请求结果：.（5）合理的分配 1.存在安全序列：调用 Request（）函数，测试该函数的可行性，如输入 P1 进程 Request（0 1 2），所得结果：.2、不存在安全序列 输入 P0 进程 Request（0 2 0），所得结果:.七、心得体会 本次实验让我对银行家算法和死锁都有了一定的理解。知道了在资源一定的条件下为了让多个进程都能使用资源完成任务，避免死锁的产生可以从一开始就对系统进行安全性检查来判断是否将资源分配给正在请求的进程。但是银行家算法会加大系统的开销。此外，存在以下疑问，在系统不分配进程所请求的资源的时候，是否

11、会将此资源等待，直到拥有足够的资源的时候再来运行？进程会请求资源是指在执行的过程中只有拥有了足够数量的资源才可以执行下去，但是资源有限，进程数又有足够多，我们期望所有进程都可以在最短的时间内执行完。也许可以这样理解。操作系统的基本特征就是并发和共享，系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足、分配不当而引起“死锁”。本次课程设计就是用银行家算法来避免“死锁”。该算法就是一个资源分配过程，使分配序列不会产生死锁。此算法的中心思想就是，每次分配后总存在着一个进程，如果让它单独的运行下去，必然可以获得它所

12、需要的全部资源，而它结束后可以归还这类资源以满足其他申请者的需要。另外，我知道了在程序进行编写之前，先对程序的要求进行分析，弄清楚程序所需要的功能，然后将每个功能分成一个功能模块即调用函数来实现，无需过多的画蛇添足。八、参考资料.【1】计算机操作系统（第三版）汤小丹、梁红兵、汤子瀛、哲凤屏等 西安电子科技大学出版社 2007-05 【2】C+Primer 中文版（第 4 版）（美）Stanley B.Lippman 等 著 李师贤 等 译.人民邮电出版社,2006-03-01【3】C+Primer 习题解答（第 4 版）蒋爱军，李师贤，梅晓勇 著 人民邮电出版社 2007-02-01【4】现代

13、操作系统（原书第 3 版）塔嫩鲍姆（Tanenbaum.A.S），陈向群，马洪兵 著 机械工业出版社 2009-07-01【5】计算机操作系统教程 张尧学，史美林，张高 清华大学出版社 2006-10-01【6】数据结构（STL 框架）王晓东 著 清华大学出版社 2009-09-01【7】计算机操作系统（第三版）汤子瀛等 西安电子科技大学出版社 2007-05【8】操作系统实验教程基于 windows 和 Linux 秦明等 清华大学出版社 2010-09-01 附：源程序#include#include#include#define M 10/最大进程数#define N 3/系统所拥有的资

14、源类型 int MaxMN;/进程对各类资源的最大需求 int AllocationMN;/系统已为进程所分配的各类资源数 int NeedMN;/运行进程尚需的各类资源数 int WorkN;/运行进程时系统所拥有的资源数 bool finishM;/表示系统是否有足够的资源分配给进程 int AvailableN;/系统可利用的资源数 int n_pro=0;/进程的数目 int flagM=-1;/用于标记安全序列 int Readfile();/从磁盘读文件 int Safe1(int flag,int n,int t);/输出所有安全状态 void show();.int Safe(

15、);/判断系统是否处于安全状态 int Request();/请求资源分配函数 void show()printf(t%-9st%-9st%-9sn,MAX,Allocation,Need);printf(tA B CtA B CtA B Cn);for(int i=0;in_pro;i+)printf(p%dt%d%4d%4dt,i,Maxi0,Maxi1,Maxi2);printf(%d%4d%4dt,Allocationi0,Allocationi1,Allocationi2);printf(%d%4d%4dn,Needi0,Needi1,Needi2);printf(系统可利用资源数:

16、n);printf(tAtBtCn);printf(t%dt%dt%dn,Available0,Available1,Available2);int Readfile()/从磁盘读文件 int i=0,j=0;/i 表进程，j 表资源 ifstream inFile;/文件 in(test.txt);/打开输入文件，按照规定的格式提取线程等信息 for(j=0;j Availablej;in();printf(系统最大资源数:n);printf(tAtBtCn);printf(t%dt%dt%dn,Available0,Available1,Available2);inFile n_pro;i

17、n();printf(当前进程的数目:%dn,n_pro);while(in_pro)/提取进程的相关资源信息 for(j=0;j Maxij;for(j=0;j Allocationij;for(j=0;jN;j+)Needij=Maxij-Allocationij;Availablej-=Allocationij;i+;.for(j=0;jN;j+)Workj=Availablej;printf(显示初始化资源分配表:n);show();printf(n);return 0;int Safe()/判断系统是否是安全的 int tempn=n_pro;int i=0,j=0,t=0;for(

18、i=0;in_pro;i+)finishi=false;while(tempn)for(i=0;i=Needi0)&(Work1=Needi1)&(Work2=Needi2);if(tp)finishi=true;for(int j=0;jN;j+)Workj+=Allocationij;flagt=i;/printf(%dtflag%d=%d,i,t,flagt);system(pause);printf(n);t+;break;tempn-;for(i=0;in_pro;i+)if(finishi=false)printf(系统不安全,不存在安全序列n);return-1;.printf(

19、系统是安全的,存在安全序列:n);for(j=0;jN;j+)Workj=Availablej;Safe1(flag,n_pro,0);printf(n);return 0;int Safe1(int flag,int n,int t)int p,i,j,k;/p 为标记 int tempN;/临时数组 for(i=0;i=Needi0)&(Work1=Needi1)&(Work2=Needi2);if(tp)for(j=0;jN;j+)Workj+=Allocationij;flagt=i;p=1;else continue;for(int j=0;jt;j+)if(flagt=flagj)

20、for(j=0;jN;j+)Workj-=Allocationij;p=0;break;if(p=1)if(t=n-1)for(k=0;kn;k+)printf(p%-5d,flagk);printf(n);else .for(k=0;kN;k+)tempk=Workk-Allocationik;Safe1(flag,n,t+1);for(k=0;kN;k+)Workk=tempk;return 0;int Request()/进程提出请求后，判断系统能否将资源分配给它 int rq;/下标 int RequestN;printf(请输入需要请求的进程号(04):);scanf(%d,&rq)

21、;printf(请输入需要请求的资源数(A B C):);scanf(%d%d%d,&Request0,&Request1,&Request2);if(Needrq0 Request0|Needrq1 Request1|Needrq2 Request2)printf(进程 p%d 申请的资源大于它所需要的资源n 分配不合理，不予分配nn,rq);return-1;if(Available0 Request0|Available1 Request1|Available2 Request2)printf(进程 p%d 申请的资源大于系统现在可利用的资源n 分配不合理，不予分配nn,rq);retu

22、rn-1;for(int j=0;jN;j+)Availablej-=Requestj;Allocationrqj+=Requestj;Needrqj-=Requestj;printf(假定系统可为 p%d 分配，分配后的资源分配表:n,rq);show();printf(n);for(int k=0;kN;k+)Workk=Availablek;if(Safe().printf(系统进入不安全状态，不予分配nn);for(int j=0;jN;j+)Availablej+=Requestj;Allocationrqj-=Requestj;Needrqj+=Requestj;printf(此刻

23、的资源分配表为:n);show();printf(n);else printf(系统是安全的，以上序列是此刻所存在的安全序列!n);printf(系统已分配 p%d 所申请的资源!nn,rq);return 0;int main()system(color 0B);printf(n);printf(银行家算法 n);printf(学号：n);printf(班级：n);printf(姓名：n);printf(n);printf(从磁盘读取源文件n);Readfile();printf(T0 时刻的安全性:n);if(Safe()return-1;while(1)Request();return 0;