银行家算法实验报告.docx

操作系统课程设计报告题目：银行家算法院（系）：计算机学院专业：计算机科学与技术班级：学生：学号：指导教师：2012年 01月摘要银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果不是安全状态，则不能为申请资源的进程分配资源。银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。论文首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行调试和测试，最后进行组装测试及系统测试，使其成为一个可以用来判断系统安全状态的程序。关键词：可用资源 最大需求矩阵 分配矩阵 需求矩阵 安全性算法 安全序列目录一、绪论1二、需求分析2三、算法分析3四、详细设计4五、程序调试7六、总结10参考文献11附录（源代码）12 操作系统课程设计（银行家算法） 一、 绪论1.1前言Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1.2研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。二、 需求分析2.1问题描述当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。2.2基本要求（1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进行有序的输入。（2）对申请资源的进程要有合法性判断（如进程名，申请资源数等）。（3）若有进程申请资源，首先要对它申请的资源数进行判断。（4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。2.3概要分析在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。所谓安全状态是指系统能按某种顺序如（称为安全序列），就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。三、算法分析3.1算法思路先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。3.2银行家算法步骤（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request; Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3.3安全性算法步骤（1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeedor=Work如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finishi=true;转向步骤（2）。（4）如果所有进程的Finishi=true,则表示系统处于安全状态；否则，系统处于不安全状态。四、详细设计4.1主要用到的数据结构(1）进程名向量 char processnemaN; /进程名(2）可利用资源向量 int AvailableM; /资源清单系统中现有各资源空闲个数。(3）最大需求矩阵 int MaxNM; /最大需求矩阵每个进程对各资源的最大需求数分配矩阵 (4）已分配矩阵 int AllocationNM;/分配矩阵系统给每个进程已分配的各类资源数 (5）需求矩阵 int NeedNM; /需求矩阵每个进程还需要每种资源的个数申请各类资源数量 (6）申请向量 int Request M /进程申请资源的向量(7）工作向量 int WorkNM; /初始第一个向量为Available,随寻找安全序列时为其余每个向量赋值，可以防止安全序列未找到而丢了初始状态的值(8）安全序列向量 int sequenceN=0;/存放安全序列号(9）标志向量 int FinishN /求安全序列时记录每个进程是否可以顺利执行4.2程序的模块void main()/系统主函数int check_distribution()/安全性检查函数int check_safe()/银行家算法函数void print()/输出函数4.3模块设计与复杂度分析141. int check_distribution(int* p,int k)：检查是否可以试分配函数用for(i=0; iM; i+)判断是否满足约束条件pi = Needki，时间复杂度为O(M)。 2. int check_safe()银行家算法(1) 用for(i=0; iM; i+)循环Workki=Availablei;/-Requesti初始化Work矩阵(2) 用for(m=0; mN; m+)循环找出满足（0 = Finishi & Needi0 = Workk0 & Needi1 = Workk1 & Needi2 = Workk2）条件的进程，修改各资源信息。因为是N个进程，所以最多循环N次就可以找出所有矩阵。(3) 用for(i=0; iN; i+)/检查是否所有进程都执行完了，如果所有进程都可执行则finish值等于1。(4) 由上面执行可以得出int check_safe()函数时间复杂度为O(N)或O(M)。3. void print()输出函数 for(i=0; iN; i+)for(j=0; jM; j+)循环输出每个进程的每一类资源信息，时间复杂度为O(N)或O(M)。4.5程序流程图1. 主函数void main（）函数流程图 2. int check_distribution(int* p,int k)流程图 3.银行家算法int check_safe()流程图 4.输出函数print（）流程图五、程序调试函数的书写分模块进行，每完成一个模块进行调试、测试直到该函数运行无误。1、进程信息的输入与输出调试(1) 能正确无误的输入进程名向量processnemaN，输入系统现有各类资源数量AvailableM向量，输入每个进程对各类资源的最大需求数MaxNM矩阵，输入系统给每个进程已分配的各类资源数AllocationNM矩阵。输出程序过程如下图所示：(2) 在进程信息输入中没有出现多大问题，在进程信息输出时，按设计要求输出的话应该是一个表格形式，在输出函数设计最初，由于有些部分分割或空格没有填充好，导致输出表格比较乱，没有达到设计要求，经过修改后输出形式才符合了设计要求，进程信息输入完成后，初始状态各进程信息输出如下：2、进程请求资源输入出错提示信息处理在系统询问是否有进程申请资源时，如果有输入信息出错，系统会给与出错提示，如果输入信息正确则系统将继续执行下面操作，执行如下：3、 判断是否可以试分配函数int check_distribution(int* p,int k)在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件Request =need或Request =available,如果不满足将打出提示信息，如果满足，则返回1继续执行下面程序，执行结果如下：4、求安全序列函数int check_safe()如果申请资源的进程申请的资源数目满足试分配条件，则再用这个函数来求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源，系统恢复初始状态，打印出提示信息，执行结果如下：六、总结经过几天的操作系统课程设计，我学习到了很多东西。首先，这次课程设计的内容是银行家算法，我用的编程工具是VC+，语言使用的是C语言，目的是模拟实现处理机避免死锁；其次，通过模拟实现算法，我更进一步地学习了C语言，这使我的编程能力得到了提高。当然最重要的是我更深地理解了对于死锁的避免，死锁是会影响并发执行的，是操作系统最需要解决得问题。解决死锁，我们要检测一个安全状态，虽然并非所有的不安全状态都会产生死锁状态，但系统进入不安全状态时，便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于如何使系统不进入不安全状态。很明显这些概念在操作系统上是非常重要的东西，我相信这对我以后的学习也有很大的帮助；最后，这次在课程设计的过程中遇到很多困难，但是这些困难我在同学们以及老师的帮助下解决了，在此我要感谢郭伟同学和指导老师惠老师，谢谢他们帮助我，指导我。参考文献1 计算机操作系统 汤子瀛，西安电子科技大学出版社；2 C语言程序设计 谭浩强， 清华大学出版社；附录（源代码）#include#define N 5 /进程个数#define M 3 /资源种类数void print();int check_safe();int check_distribution(int* p,int k);char processnemaN; /进程名int RequestM; /请求向量int FinishN;/标记某一个进程是否可以执行int WorkNM; /初始为Available,随寻找安全序列而变化，防止安全序列未找到而丢了初始状态的值int AvailableM; /资源清单系统中现有各资源空闲个数int Work_AllocationNM;int MaxNM; /最大需求矩阵每个进程对各类资源的最大需求数int AllocationNM;/分配矩阵系统给每个进程已分配的各类资源数int NeedNM; /需求矩阵每个进程还需要每种资源的个数int sequenceN=0;/存放安全序列号void main()int i=0,j=0,k=0;/记录申请资源的进程的序列号int flag=0; /标记输入的进程名是否存在int safe=0; /标志系统是否出于安全状态,0表示不安全，1表示安全int distribution=0; /标志是否可以进行试分配0表示可以，1表示不可以char flag1; /标记是否有进程申请资源 /NeedNM=MaxNM-AllocationNM;char name; /要请求资源的进程名printf(银行家算法n);printf( 请分别初始化各矩阵信息 n);printf(*请输入各进程的进程名n); /进程名连续输入for(i=0; iN; i+)scanf(%c,&processnemai);printf(请输入现有各资源空闲个数n);for(i=0; iM; i+)scanf(%d,&Availablei);printf(请分别输入每个进程对各类资源的最大需求数n);for(i=0; iN; i+)for(j=0; jM; j+)scanf(%d,&Maxij);printf(请分别输入系统给每个进程已分配的各类资源数n);for(i=0; iN; i+)for(j=0; jM; j+)scanf(%d,&Allocationij);/printf(请分别输入每个进程还需要每种资源的个数n);for(i=0; iN; i+)for(j=0; jM; j+)Needij=Maxij-Allocationij;printf(信息输入完毕n);for(i=0; iN; i+)sequencei=i;print();safe=check_safe(); /检查初始状态是否安全if(0 = safe)printf(系统现处于不安状态，不能为进程分配资源，进入死锁状态。n);exit(0);else if(1 = safe)printf(系统处于安全状态，可以为进程分配资源。n);while(1)safe=0; getchar();printf(是否有进程请求系统资源.? (Y/N) n);flag1=getchar();/scanf(%c,&flag1);if(Y = flag1 | y = flag1)printf(请输入进程名:); getchar();while(1)/name=;scanf(%c,&name);for(i=0; iN; i+) /检查进程名输入是否正确if(name = processnemai )flag=1; /输入的进程名存在k=i;break;/找到申请资源的进程序列号跳出getchar();/将在此之前的一个回车接收了，不然会影响输入if( flag != 1 )/进程名输入不合法printf(你输入的进程不存在，请重新输入:);continue;elsebreak;/进程名输入合法，则执行下面操作else if(N = flag1 | n = flag1)printf(进程执行完毕，退出系统。n);break;else if(N != flag1 & Y != flag1 & n != flag1 & y != flag1)printf(你的输入有误，请重新输入: );continue;printf(请输入该进程请求各类资源的数量n);for(i=0; iM; i+)scanf(%d,&Requesti);distribution=check_distribution(Request,k); /检查是否可以试分配if(1 = distribution) /*检查safe=check_safe(); /可以试分配，则求安全序列if(1 = safe) /试分配成功printf(试分配成功，可以为该进程分配资源。n);/distribution /是否给申请资源的进程分配资源for(i=0; iM; i+)Allocationki=Allocationki+Requesti; /为进程分配资源后修改该进程的有关资源数Needki=Needki-Requesti;printf(分配后各资源数量如下:n);print();printf(分配成功!n);printf(系统剩余资源数各为: );for(i=0; iM; i+)printf(%d ,Availablei);printf(n);continue;else /试分配失败printf(试分配失败，有可能进入死锁状态，请等待。n);/未求出安全序列continue; else /试分配失败printf(该进程申请的资源太多，无法分配，请等待。n);continue;void print()int i,j;printf( 资源 Work NeedtAllocationtWork+Allocationt Finishnn);printf( 进程名 A B C A B C t A B C t A B Cn);printf(n);for(i=0; iN; i+)printf( %c ,processnemasequencei);for(j=0; jM; j+)printf(%d ,Worksequenceij);printf( );for(j=0; jM; j+)printf(%d ,Needsequenceij);printf( );for(j=0; jM; j+)printf(%d ,Allocationsequenceij);printf( );for(j=0; jM; j+)printf(%d ,Work_Allocationsequenceij);printf( );printf(%d,Finishi);printf(nn);int ch