计算机操作系统实验二银行家算法

1、实 验 报 告课程名称操作系统实验班级实验日期姓 名学号实验成绩实验名称银行家算法实验目的及要求1、了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生实验内容1、在多道程序系统中，虽可借助与多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险-死琐。产生死锁的原因可归结为两点：1：竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。2：进程间推进顺序非法。进程在运行过程中，请求和释放资

2、源的顺序不当，也同样会导致产生进程死锁。最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用与银行系统现金贷款的发放而得名的。 算法描述及实验步骤1.算法描述：设Requesti 是进程Pi的请求向量，如果Requestij=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按下面步骤进行检查：（1）如果Requestij=Needi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestij=Availablej,便转向步骤3；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修

3、改下面数据结构中的数值：Availablej:=Availablej-Requestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。2.数据结构银行家算法中的数据结构：（1） 可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的

4、数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K,则表示进程i还需要R

5、j类资源K个，方能完成其任务。(5) 工作数组Work.。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Worki=Worki+Allocationi。3.算法流程图程序初始化随机分配资源并显示在屏幕检查安全序列是否要申请资源退出程序输入RequestRequestNeedRequestAvailableNeedij=Needij-RequestjAvailablej=Availablej-Requestj报错检查安全序列保留原始Available、Request恢复原始Available、Request判Al

6、location=MaxAvailablej=Maxij+workjFinishi=1输出结果调试过程及实验结果实验结果为：附录#include #include #include # define m 50 int no1; /进程数int no2; /资源数int r;int allocationmm,needmm,availablem,maxmm; char name1m,name2m; /定义全局变量void main()void check();void print();int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm

7、,available1m;printf(*n);printf(* 银行家算法的设计与实现 *n); printf(*n);printf(请输入进程总数:n);scanf(%d,&no1);printf(请输入资源种类数:n);scanf(%d,&no2); printf(请输入Max矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&maxij); /输入已知进程最大资源需求量printf(请输入Allocation矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&allocationij); /输入已知

8、的进程已分配的资源数 for(i=0;ino1;i+)for(j=0;jno2;j+)needij=maxij-allocationij; /根据输入的两个数组计算出need矩阵的值 printf(请输入Available矩阵n);for(i=0;ino2;i+)scanf(%d,&availablei); /输入已知的可用资源数print(); /输出已知条件check(); /检测T0时刻已知条件的安全状态if(r=1) /如果安全则执行以下代码do q=0; p=0;printf(n请输入请求资源的进程号(04)：n);for(j=0;j=no1)printf(输入错误，请重新输入：n)

9、; continue; else break;printf(n请输入该进程所请求的资源数requestj:n);for(j=0;jno2;j+)scanf(%d,&requestj);for(j=0;jneedij) p=1; /判断请求是否超过该进程所需要的资源数if(p)printf(请求资源超过该进程资源需求量，请求失败！n);elsefor(j=0;javailablej)q=1;if(q) printf(没有做够的资源分配，请求失败！n);else /请求满足条件for(j=0;jno2;j+) available1j=availablej; allocation1ij=alloca

10、tionij;need1ij=needij; /保存原已分配的资源数，仍需要的资源数和可用的资源数availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系统尝试把资源分配给请求的进程print();check(); /检测分配后的安全性if(r=0) /如果分配后系统不安全for(j=0;jno2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij; /还原已分配的资源数，仍需要的资源数和可用的资源数p

11、rintf(返回分配前资源数n);print();printf(n你还要继续分配吗？Y or N ?n); /判断是否继续进行资源分配c=getche();while(c=y|c=Y);void check() /安全算法函数int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;ino1;i+)finishi=false; / 初始化进程均没得到足够资源数并完成for(i=0;ino2;i+) worki=availablei;/worki表示可提供进程继续运行的各类资源数k=no1;dofor(i=0;ino1;i+)if(finishi

12、=false)f=1;for(j=0;jworkj)f=0;if(f=1) /找到还没有完成且需求数小于可提供进程继续运行的资源数的进程finishi=true;av+=i; /记录安全序列号for(j=0;j0);f=1;for(i=0;ino1;i+) /判断是否所有的进程都完成if(finishi=false) f=0;break;if(f=0) /若有进程没完成，则为不安全状态printf(系统处在不安全状态！);r=0;elseprintf(n系统当前为安全状态，安全序列为：n);for(i=0;ino1;i+)printf(p%d ,ai); /输出安全序列void print() /输出函数int i,j;printf(n);printf(*此时刻资源分配情况*n);printf(进程名/号 | Max | Allocation | Need |n); for (i = 0; i no1; i+)printf( p%d/%d ,i,i); for (j = 0; j no2; j+) printf(%d ,