银行家算法课程设计报告

银行家算法一．需求分析1.在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。2.银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，„，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列{P1，„，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有资源量之和。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。3.设计要求：设计一n个并发进程共享m个系统资源的程序实现银行家算法。要求包括：（1）简单的初始化界面；（2）系统资源的占用和剩余情况；（3）为进程分配资源，用银行家算法对其进行检测，分为以下三种情况：A.所申请的资源大于其所需资源，提示分配不合理不予分配并返回；B.所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回；C.所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：a.预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回；b.与分配后系统进入不安全状态，提示系统不安全并返回；（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入；（5）撤销作业，释放资源。二．概要设计（一）算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。(二)算法步骤：（1）如果Requesti＜or=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的值：Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。三．详细设计#defineSIZE11intavailable[SIZE];intclaim[SIZE][SIZE];intallocation[SIZE][SIZE];intneed[SIZE][SIZE];intrequest[SIZE][SIZE]={0};//记录某个进程申请各个资源类中的资源实例的数量intfinish[SIZE]={0};//工作变量，用于判断进程是否已经执行过，初始状态全部为0，即未执行intp[SIZE];//记录序列执行顺序intava;//记录系统有多少个资源类intprocess;//记录进程数量intr;//记录当前要申请资源的进程的序号intkey=1;这部分程序一开始定义了程序所需要的矩阵，资源类，进程数等等，用来记录进程资源的分配情况，可见的显示了银行家算法。voidshowdate();voidallot();intinit();intcheck();这些事主函数运行时所要调用的函数，首先要调用的是init（）函数，这个函数初始化了claim[SIZE][SIZE]矩阵和allocation[SIZE][SIZE]矩阵，初始化成功以后就开始给进程分配资源，开始调用allot()函数，银行家算法的核心之一就是进行资源类的分配，下面是分配的过程：试分配------进行安全性检测-----分配成功当然，进行安全性检测后，如果不安全，我们要记得数据重置，也是资源的回收。for(i=0;iava;i++)//假设分配{available[i]=available[i]-request[r][i];allocation[r][i]=allocation[r][i]+request[r][i];need[r][i]=need[r][i]-request[r][i];}//intret=check();if(check()==0)//安全检测{printf(安全检测失败,可能发生死锁,数据重置\n);for(i=0;iava;i++)//重置数据{available[i]=available[i]+request[r][i];allocation[r][i]=allocation[r][i]-request[r][i];need[r][i]=need[r][i]+request[r][i];}}else{intkey=0;for(j=0;java;j++){if(need[r][j]==0){key++;}}if(key==ava){for(j=0;java;j++){available[j]+=allocation[r][j];allocation[r][j]=0;}}}printf(\n进程顺利执行.\n\n);return;如果安全检测时安全的，则程序就会找出一个安全的序列，例如：p0,p1,p2,p3,p4。此程序在找安全序列的时候每次都是从头开始找的for(i=0;iprocess;i++){for(j=0;java;j++)////寻找条件Need[i]=Work[i]{if(need[i][j]work[j]){break;}}if((j==ava)&&(finish[i]==0))///寻找条件Finish[i]=false，每次从头开始找安全序列{finish[i]=1;for(k=0;kava;k++){work[k]=work[k]+allocation[i][k];}p[l]=i;//记录安全序列l++;//i=-1;///重置i，为了寻找安全序列}else{continue;}if(l==process)//可以找到安全序列，输出并结束{printf(\n系统安全!\n);printf(安全序列为：);for(k=0;kl;k++){printf(P(%d),p[k]);if(k!=l-1){printf(--);}}return1;}}printf(\n系统不安全，不能满足你的要求！\n);return0;最后一步是调用显示函数showdate()函数，此函数让我们更加直观的看到银行家算法的运行过程，{printf(P(%d),i);for(j=0;java;j++){printf(%d,claim[i][j]);}printf(\n);}printf(\nAllocation\n);printf();ava_xh();for(i=0;iprocess;i++){printf(P(%d),i);for(j=0;java;j++){printf(%d,allocation[i][j]);}printf(\n);}printf(\nNeed\n);printf();ava_xh();for(i=0;iprocess;i++){printf(P(%d),i);for(j=0;java;j++){printf(%d,need[i][j]);}printf(\n);}printf(\nAvailable\n);ava_xh();for(i=0;iava;i++){printf(%d,available[i]);显示了分配资源过后的need[SIZE][SIZE]矩阵和available[SIZE]和allocation[SIZE][SIZE]矩阵。四．测试初始化输入：正常的分配成功，及其安全序列：请求的资源造成了系统的不安全，存在安全隐患：五．总结在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如已分配资源数allocation[]、仍需求资源数need[]、以及系统可利用的资源数available[]、申请各类资源request[]、进程个数r[]等数组,其中每一个进程还使用了结构体。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。安全性检测我们是用check()函数来实现的。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些——比如进程号——本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。设计的存在着以下不足：一、不能实现并发操作，即当总资源同时满足几个进程所需要的资源数时，这些进程不能同时进行，只能一一按进程顺序执行。二、扫描进程顺序单一，只能按进程到来的顺序（即编号）来扫描，从而产生的安全顺序只能是在这个顺序的基础上产生的，而其实安全顺序是有多个的。三、对进程数和资源数进行的数量进行了限制，都只能最多有十个。四、运行程序后，界面较差，进程数，所需要资源数，已分配资源数，能用资源数，不能一目了然。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。附录：程序代码：#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includestdlib.h#includemalloc.h#includewindows.h#defineSIZE11intavailable[SIZE];intclaim[SIZE][SIZE];intallocation[SIZE][SIZE];intneed[SIZE][SIZE];intrequest[SIZE][SIZE]={0};//记录某个进程申请各个资源类中的资源实例的数量intfinish[SIZE]={0};//工作变量，用于判断进程是否已经执行过，初始状态全部为0，即未执行intp[SIZE];