操作系统课程设计报告银行家算法设计与实现

操作系统课程设计报告题目：银行家算法设计与实现 院 （系）： 计算机科学与工程学院 专 业： 对日软件 班 级： 080612 学 生： 学 号： 080608115 指导教师： 2010年12月4 操作系统课程设计报告 银行家算法设计与实现摘 要银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果不是安全状态，则不能为申请资源的进程分配资源。银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。论文首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行调试和测试，最后进行组装测试及系统测试，使其成为一个可以用来判断系统安全状态的程序。关键词：可用资源 最大需求矩阵 分配矩阵 需求矩阵 请求向量 试分配 安全性算法 安全序列目 录银行家算法设计与实现1摘 要1目 录21 绪论51.1课题背景51.2 课题意义51.3 运行环境52 需求分析12.1 问题描述12.2 基本要求12.3 概要分析23 算法思想33.1 安全性算法的算法思想33.1.1设置两个向量：33.1.2安全性检测33.2 银行家算法的算法思想43.2.1 银行家算法的思路43.2.2 银行家算法43.2.3 安全性检查算法54详细设计64.1银行家算法中用到的主要数据结构设计64.2算法整体设计与调用64.3模块设计与时间复杂度分析84.3.1 int check_distribution(int* p,int k)函数84.3.2 int check_safe()银行家算法84.3.2 void print()输出函数84.4程序流程图84.5.1 主函数void main（）函数流程图94.5.2 判断试分配函数int check_distribution(int* p,int k)流程图94.5.3银行家算法int check_safe()流程图104.5.4 输出函数void print() 流程图115 程序调试、分析与修改125.1分模块调试与分析125.1.1进程信息的输入与输出调试125.1.2 进程请求资源输入出错提示信息处理135.1.3 判断试分配函数int check_distribution(int* p,int k)135.1.4 求安全序列函数int check_safe()146 结论157 小结16参考文献17附录（源代码）181 绪论1.1课题背景在预防死锁的各种算法中，总的来说，都是施加了较强的限制条件，从而使实现简单，但却严重地损害了系统的性能。在避免死锁的算法中，施加的条件较较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统处于安全状态，便可避免死锁的发生。最具有代表性的避免死锁的算法是Dijkstra的银行家算法。这是因为该算法能用于银行系统现金贷款的发放而得名，在这一次的课程设计中就要对银行家算法从分析到实现，整体做一个详细的描述。1.2 课题意义（1）从课程设计上讲，提高自己的分析问题，解决问题和动手能力；（2）从银行家算法上本身讲，通过算法可以判断系统的安全性，对申请资源的进程进行限制，从而避免系统进入死锁状态。1.3 运行环境 Turbo C; Visual C+ 6.0 2 需求分析 2 需求分析2.1 问题描述 当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。2.2 基本要求 （1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进行有序的输入。 （2）对申请资源的进程要有合法性判断（如进程名，申请资源数等）。 （3）若有进程申请资源，首先要对它申请的资源数进行判断。 （4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。 2.3 概要分析在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。所谓安全状态是指系统能按某种顺序如（称为安全序列），就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。 27 操作系统课程设计报告 3 算法思想3.1 安全性算法的算法思想 思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。3.1.1设置两个向量（1）工作向量Workm: 它表示系统可提供给进程继续运行所需的各类资源数目， Work初=Available; （2） Finishn: 它表示系统是否有足够的资源分配给进程，使之运行完成。 false表示未完成， true表示完成。3.1.2安全性检测WorkAvailableFinish 根据Need赋值寻找进程i，满足Finish i false且Need i=work返回安全状态yWork=work+Allocation iFinish i true找到所有进程的Finish i true？没找到n返回不安全状态3.2 银行家算法的算法思想3.2.1 银行家算法的思路 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。3.2.2 银行家算法进程i发出申请资源请求： (1)调用check_distribution(int* p,int k)检查申请量是否不大于需求量再检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。 (2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Availablei,j= Availablei,j- Request ij；Allocationij= Allocationij+ Request ij；needij= needij- Request ij；(3)进行试分配，执行安全性检查，调用check_safe()函数检查此次资源试分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(4)用while 循环语句实现输入字符Y/N判断是否继续进行资源申请。3.2.3 安全性检查算法(1)设置向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。Finish，它表示系统是否有足够的资源分配给每个进程，使之运行完成。开始时先做Finishi=0；当有足够的资源分配给进程时，再令Finishi=1。(2)在进程中查找符合以下条件的进程：条件1：Finishi=0；条件2：needij=Workj若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；(4)最后循环检查是否所有的Finishi=1都满足，如果是，则返回1表示系统处于安全状态，否则，返回0表示系统处于不安全状态。 操作系统课程设计报告 4详细设计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* p,int k)函数判断是否可以进行试分配，如果满足试分配条件，调用int check_safe()函数求安全序列，如果可以求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申请资源的进程，最后用void print()函数输出分配资源后每个进程的信息。如果求不出安全序列，说明分配后系统会处于不安全状态，则不能将资源分配给该进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让该进程等待。继续判断其他申请资源的进程。 （1）int check_distribution(int* p,int k)：这个函数用来判断是否可以进行试分配，如果函数结果返回1，说明可以进行试分配，如果行数返回0，说明申请资源的进程申请的资源数目不满足Request =need或Request =available条件，不能为该进程进行试分配。 （2）int check_safe()：这个函数用来求安全序列，首先初始化Work0i= Availablei，然后循环找满足条件 Finishi=0 & Needi0 = Workk0的进程，k表示最近执行的进程的进程号，找到后将进程i 加入sequence向量，再将Finishi=1，表示进程可以顺利执行则Workkj=Workk-1j+Allocationij，k表示同上。再继续找下一个满足条件的进程。如果单循环结束时每个进程的Finishi都等于1，则说明可以找到安全序列，返回1，如果不是每个Finishi都等于1，则说明找不到一个安全序列，返回0 输入每个进程信息，调用银行家算法int check_safe()判断初始状态是否安全。 主 函 数 若有进程申请资源，首先用int check_distribution(int* p,int k)判断是否可以试分配。 满足生面条件，用int check_safe()函数求安全序列 ( 3 ) void print()：这个函数用来输出进程信息，按表格形式输出，并且输出顺序和安全序列相同，便于查看进程执行执行过程，并且在执行过程中各矩阵信息变化也很容易跟踪查看。 （4）系统模块 4.3模块设计与时间复杂度分析 4.3.1 int check_distribution(int* p,int k)：检查是否可以试分配函数用for(i=0; iM; i+)判断是否满足约束条件pi = Needki，时间复杂度为O(M)。 4.3.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)。4.3.2 void print()输出函数 for(i=0; iN; i+)for(j=0; jM; j+)循环输出每个进程的每一类资源信息，时间复杂度为O(N)或O(M)。 4.4程序流程图4.5.1 主函数void main（）函数流程图 （ 4-1） 4-14.5.2 判断试分配函数int check_distribution(int* p,int k)流程图（4-2） 4-24.5.3银行家算法int check_safe()流程图(4-3) 4-3 4.5.4 输出函数void print()流程图（4-4）4-45 程序调试、分析与修改5.1分模块调试与分析 函数的书写分模块进行，每完成一个模块进行调试、测试直到该函数运行无误。 5.1.1进程信息的输入与输出调试(1) 能正确无误的输入进程名向量processnemaN，输入系统现有各类资源数量AvailableM向量，输入每个进程对各类资源的最大需求数MaxNM矩阵，输入系统给每个进程已分配的各类资源数AllocationNM矩阵。输出程序过程如下：(2) 在进程信息输入中没有出现多大问题，在进程信息输出时，按设计要求输出的话应该是一个表格形式，在输出函数设计最初，由于有些部分分割或空格没有填充好，导致输出表格比较乱，没有达到设计要求，经过修改后输出形式才符合了设计要求，进程信息输入完成后，初始状态各进程信息输出如下：5.1.2 进程请求资源输入出错提示信息处理(1) 在系统询问是否有进程申请资源时，如果有输入信息出错，系统会给与出错提示，如果输入信息正确则系统将继续执行下面操作，执行如下：5.1.3 判断是否可以试分配函数int check_distribution(int* p,int k)(1) 在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件Request =need或Request =available,如果不满足将打出提示信息，如果满足，则返回1继续执行下面程序，执行结果如下：5.1.4 求安全序列函数int check_safe()(1) 如果申请资源的进程申请的资源数目满足试分配条件，则再用这个函数来求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源，系统恢复初始状态，打印出提示信息，执行结果如下：6 结论 银行家算法是通过检查试分配，求安全序列，从而判断是否可以为申请资源的进程分配资源，从而有效地避免系统进入死锁状态。 7 小结 7 小结虽然并非所有的不安全状态都会产生死锁状态，但系统进入不安全状态时，便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于；如何使系统不进入不安全状态。对先者 ang下图所示： 参考文献 参考文献1 数据结构实验指导书 网上资料2 计算机操作系统 汤子瀛 哲凤屏 汤小丹，西安电子科技大学出版社；3 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 check_distribution(int* p,int k)int i=0;int safe1=0,safe2=0;for(i=0; iM; i+)if(pi = Needki)safe1=safe1+1;if(pi = Availablei)safe2=safe2+1;if(M = safe1 & M = safe2)return 1;elsereturn 0;int check_safe() /检查是否安全，求安全序列int i=0,j=0,k=0,m=0;int finish=0;for(i=0; iM; i+)Workki=Availablei;/-Requesti;/初始化WOrk矩阵for(m=0; mN; m+)/N个进程最多找N趟if(1 != finish)finish=1;for(i=0; iN; i+) /找Need小于Work的进程if(0 = Finishi & Needi0 = Workk0 & Needi1 = Workk1 & Needi2 = Workk2)sequencek=i;/找到一个满足条件的进程，记录其序号k+;Finishi=1; /执行该进程for(j=0; jM; j+)Workkj=Workk-1j+Allocationij; /更新WOrk值for(i=0; iN; i+)/检查是否所有进程都执行完了finish=finish*Finishi;if(1 = finish)break;elsecontinue;/else/break;/for(i=0; iN; i+)for(j=0; jM; j+)Work_Allocationij=Workij+Allocationij;for(i=0; iM; i+)Availablei=Availablei-Requesti;return finish;/*输入进程信息：请分别输入每个进程对各类资源的最大需求数7 5 33 2 29 0 22 2 24 3 3请分别输入系统给每个进程已分配的各类资源数0 1 02 0 03 0 22 1 10 0 2请分别输入每个进程还需要每种资源的个数7 4 31 2 26 0 00 1 14 3 1信息输入完毕*/