银行家算法实验报告13551

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

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

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

7、 系统试探分配资源，修改相关数据：AVAILABLEi-=REQUESTcus needi;ALLOCATIONcus needi+=REQUESTcus needi;NEEDcus needi-=REQUESTcus needi;(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废,系统恢复原状，进程等待。(5) 对于某一进程i，若对所有的j，有NEEDij=0，则表此进程资源分配完 毕，应将占用资源释放。3、安全性检查算法(1) 设置两个工作向量 Work=AVAILABLE;FINISH(2) 从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED&l

8、t;=Work;如找到，执行；否则，执行(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Fin ish=true;GOTO 2如所有的进程Finish= true ，则表示安全；否则系统不安全4、流程图1、整体流程图开始2、判断系统的安全性Safe ()六、运行结果1、系统不安全的输入（ 1）、本程序按下图建立 .txt 源文件，作为程序的初始化输入2）执行程序，读取源文件，并判断 T0 时刻所得结果 :2. 系统安全的输入（ 1）、本程序按下图建立 .txt 源文件，作为程序的初始化输入2）执行程序，读取源文件，并判断 T0 时刻所得结果 :3)

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

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

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

12、勇 著 人民邮电 2007-02-01【4现代操作系统（原书第3版）塔嫩鲍姆 （）, 向群，马洪兵著机械工业2009-07-01【5计算机操作系统教程尧学，史美林，高清华大学2006-10-01【6数据结构（STL框架）王晓东著清华大学2009-09-01【7计算机操作系统（第三版）汤子瀛等电子科技大学2007-05【8操作系统实验教程基于windows和Linux明等 清华大学 2010-09-01附：源程序#in clude<fstream.h>#i nclude<stdio.h> #in clude<stdlib.h>#define M 10 /最大进

13、程数#define N 3 /系统所拥有的资源类型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);/ 输出所有安全状态v

14、oid show();int Safe();判断系统是否处于安全状态int Request。;/请求资源分配函数void show()printf(" t%-9st%-9st%-9sn","MAX","Allocation","Need");printf(" tA B CtA B CtA B Cn");for(int i=0;i<n_pro;i+)printf("p%dt%d%4d%4dt",i,Maxi0,Maxi1,Maxi2);printf("%d%4d

15、%4dt",Allocationi0,Allocationi1,Allocationi2);printf("%d%4d%4dn",Needi0,Needi1,Needi2);printf(" 系统可利用资源数 :n");printf(" tAtBtCn"); printf("t%dt%dt%dn",Available0,Available1,Available2);int Readfile()/ 从磁盘读文件int i=0,j=0;/i 表进程， j 表资源ifstream inFile; / 文件inF

16、ile.open("test.txt"); / 打开输入文件，按照规定的格式提取线程等信息 for(j=0;j<N;j+)inFile >> Availablej;inFile.get();printf(" 系统最大资源数 :n");printf(" tAtBtCn"); printf("t%dt%dt%dn",Available0,Available1,Available2);inFile >> n_pro;inFile.get();printf(" 当前进程的数目 :%d

17、n",n_pro); while(i<n_pro) / 提取进程的相关资源信息 for(j=0;j<N;j+)inFile >> Maxij;for(j=0;j<N;j+)inFile >> Allocationij;for(j=0;j<N;j+)Needij = Maxij - Allocationij;Availablej -= Allocationij;i+; for(j=0;j<N;j+)Workj = Availablej;printf(" 显示初始化资源分配表 :n"); show();printf

18、("n");return 0;int Safe()判断系统是否是安全的int tempn=n_pro;int i=0,j=0,t=0;for(i=0;i<n_pro;i+) finishi=false;while(tempn)for(i=0;i<n_pro;i+)if(!finishi)int tp=0;/注释部分用于调试程序/printf("%dt%d%4d%4dt",i,Work0,Work1,Work2);/printf("%d%4d%4dn",Needi0,Needi1,Needi2);&&tp=(

19、Work0>=Needi0) && (Work1>=Needi1)(Work2>=Needi2);if(tp)finishi=true;for(int j=0;j<N;j+)Workj += Allocationij;flagt=i;/ printf("%dtflag%d=%d",i,t,flagt);system("pause");printf("n");t+;break;tempn-;for(i=0;i<n_pro;i+)if(finishi = false)printf("

20、 系统不安全 , 不存在安全序列 n");return -1;printf(" 系统是安全的 ,存在安全序列 :n");for(j=0;j<N;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<n;i+)int tp=0;&&tp=(Work0>=Needi0) && (

21、Work1>=Needi1) (Work2>=Needi2);if(tp)for(j=0;j<N;j+)Workj += Allocationij;flagt=i;p=1;else continue;for(int j=0;j<t;j+)if(flagt=flagj)for(j=0;j<N;j+)Workj -= Allocationij;p=0;break;if(p=1)if(t=n-1)for(k=0;k<n;k+)printf("p%-5d",flagk);printf("n");elsefor(k=0;k<

22、;N;k+)tempk = Workk - Allocationik;Safe1(flag,n,t+1);for(k=0;k<N;k+)Workk =tempk;return 0;int Request。/进程提出请求后，判断系统能否将资源分配给它int rq; 下标int RequestN;printf("请输入需要请求的进程号(04):");scanf("%d",&rq);printf("请输入需要请求的资源数(A B C):");scanf("%d%d%d",&Request0,&

23、;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);return -1;for(int j=0;j<N;j+)Availablej -= Requestj;Allocationrq