银行家算法 OS课程设计.doc

南京工程学院 算通081班 周洁 南京工程学院课程设计报告书 课程设计题目 银行家算法 课 程 名 称 计算机操作系统 院（系、部、中心） 通信工程学院 专 业 计算机通信工程 班 级 算通081班 姓 名 周 洁 学 号 208080311 起 止 日 期 11.06.1911.06.24 指 导 教 师 王少东老师 目录1.设计目的.12.设计要求.23.设计的选题背景及设计计划1）选题背景.32）设计应达到的要求.44概要设计 1）银行家算法步骤.5 2）安全性算法步骤.6 3）主要数据结构设计.65.设计实现过程 1）算法整体设计与调用7 2）程序流程图76.设计结果验证.97.设计存在的不足 程序设计繁杂.118.设计总结.119.参考文献 .13附录：源程序清单.131. 设计目的 银行家算法是一种最有代表性的避免死锁的算法。把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 本次课程设计通过在UNIX环境中用C语言编写和终端调试实现银行家算法的程序，达到进一步掌握银行家算法，理解系统产生死锁的原因以及系统避免死锁的方法，增强理论联系实际的能力的目的。2. 设计要求 对银行家算法进行编程，使之： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回。 B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查： a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。3.设计的选题背景及设计计划 1）选题背景 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家 管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大 需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟 分配。 2）设计应达到的要求 5.2死锁预防: 预防死锁的方法是使产生死锁的四个必要条件中的2、3、4条件之一不能成立。即： 一、摒弃“请求和保持”条件。系统规定所有进程在开始运行之前，都必须一次性申请其在整个运行过程中所需的全部资源。使该进程再整个运行过程中不会提出资源请求，因而摒弃了请求条件。又由于进程在等待期间没有占有任何资源，所以也摒弃了保持条件。 二、摒弃“不剥夺”条件。系统规定，进程逐个提出对资源的要求，当一个已经保持了某些资源的进程，再提出新的资源请求而未被满足时，必须释放已经保持的所有资源，待以后需要是在再重新申请。 三、摒弃“环路等待”条件。系统规定所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求都必须严格按资源序号递增的顺序提出。5.3安全状态与不安全状态 在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。 安全状态是指，系统能按某种进程顺序（P1， P2， P3，Pn），来为每个进程分配所需资源，直至满足每个进程对资源的最大需求，是每个进曾都可以顺利完成。 如果系统找不到这样一个序列，系统就处于不安全状态。虽然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态。只要系统处于安全状态，系统便可以避免进入不安全状态。 安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。 4.设计原理1）主要数据结构设计(1) 最大需求矩阵Max：这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，j=K，则表示进程i需要Rj类资源的最大数目为K。(2) 已分配矩阵Allocation：这也是一个n*m的矩阵，它定义了系统中每一类资源 当前已分配给没一进程的资源数。如果Allocationi，j=K，则表示 进程i当前已分得Rj类资源的数目为K。(3) 仍需求矩阵Need=Max-Allocation：这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。(4) 可利用资源向量Available：这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有Rj 类资源K个。申请各类资源向量Request(5) 工作向量 work：表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时work：=available；(6) Finish：表示系统是否有足够的资源分配给进程，使之运行完成。初始化finishi:=false;有足够资源分配给进程时，令finishi：=true。2）银行家算法步骤（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requestor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request; Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3）安全性算法步骤（1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeedNEEDnj) 、if(RequestjAVAILABLEj) 用来判断是否可以进行试分配，如果判断结果为真，说明申请资源的进程申请的资源数目不满足Request =need或Request =available条件，不能为该进程进行试分配，如果判断结果为0，说明可以进行试分配。 （2）int chkerr()：这个函数用来求安全序列，首先初始化 WORK=AVAILABLEj; ，然后当iM时循环找满足条件 FINISHi=FALSE&NEEDij=WORK的进程，表示进程可以顺利执行则WORK=WORK+ALLOCATIONij。再继续找下一个满足条件的进程。如果单循环结束时每个进程的Finishi都等于1，则说明可以找到安全序列，返回1，如果不是每个Finishi都等于TRUE，则说明找不到一个安全序列，返回i=0；2）程序流程图：开始初始化 读入初始化状态时的资源分配表 读入请求向量申请不合理，出错!请重新选择Requestij=Needj NO 申请不合理，出错!请重新选择Requestij=Availablej NO Availablej:=Availablej-Requestij;Allocationi,j:=Allocationi,j+Requestj;Needi,j:=Needi,j-Requestij;赋值：Work:=Available;Finish:=F依次查找Needi=Workj;Finishi=F分配不成功 找不到将所Workj:=Worki+Allocationi,j;Finishi:=true; 有Finishi置F所有Finish为T系统安全，显示安全序列资源回收判断pi.flag=T？返回Dos 进行下一轮测试安全性算法流程图：6. 设计结果验证7.设计存在的不足 1）在设计中，首先是资源利用不足，因为在程序中是直接输出最大资源需求量MAXMN，可用资源数AVAILABLEN，M个进程已经得到N类资源的资源量ALLOCATIONMN，最大资源需求量NEEDMN，不能够再改变他们，所以程序运用范围比较小；2） 再者，在“请输入需申请资源的进程号”中进行的for循环申请资源进程号只能一次增加，没有达到随机选择的效果。3)进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中作了判断。而因为对于某些比如进程号本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。 8.设计总结 通过一个周的课程设计，我加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。并且还巩固了C语言知识，掌握了用C语言实现银行家算法的方法。 在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max、已分配资源数Allocation、仍需求资源数Need、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。在本程序代码中，银行家算法用voidchangdata()、void rstordata() 函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于则调用changedata( )函数来进行预分配，之后再调用安全型算法int chkerr() 检查。最后，无论此次分配是否成功，我们都可以选择继续分配。安全性检测我们是用int chkerr()函数来实现的。首先，Finish为布尔型，默认是False，即该进程未完成。而Work即该系统中可以用来工作的资源数最开始为系统最初可以用的资源数。然后，我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立，即Finish=False且Need=Work是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加，存放于当前可用来工作的资源量当中，即Work=Work+Allocation，并将Finish的值改为True。否则便将此进程的优先级减一，排在队位，然后开始往后循环。待所有的进程循环完毕，我们再次判断是否还存在进程的Finish=False，如果仍存在，则说明系统没有安全序列，处于不安全状态，不可以进行分配；否则，系统处于安全状态，将预分配变为实际分配，求出安全序列并且将实际分配后的资源分配情况打印输出。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。虽然并非所有的不安全状态都会产生死锁状态，但系统进入不安全状态时，便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于；如何使系统不进入不安全状态。总之，在这次课程设计中，我学到了很多知识与调试方法。9.参考文献 1 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统. 西安：西安电子科技大学出版社，2007.2 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.3 赵莉，杨国梁，孙喁喁，徐飞. Java程序设计教程. 西安：西安科技大学出版社，2009.附录：源程序清单17#include #include #include #define M 5 #define N 3 #define FALSE 0 #define TRUE 1 /*M个进程对N类资源最大资源需求量*/ int MAXMN=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3; /*系统可用资源数*/ int AVAILABLEN=10,5,7; /*M个进程已经得到N类资源的资源量 */int ALLOCATIONMN=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2; /*M个进程对N类资源最大资源需求量*/int NEEDMN=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1; /*M个进程还需要N类资源的资源量*/ int RequestN=0,0,0; void showdata() int i,j; printf(银行家算法:n); printf( -wlecomen); printf(系统可用的资源数为:n); printf( ); for (j=0;jN;j+) printf( 资源); printf(%d,j); printf(:); printf(%d ,AVAILABLEj); printf(nn); printf(各进程还需要的资源量:n); for (i=0;iM;i+) printf( 进程); printf(%d,i); printf(: ); for (j=0;jN;j+) printf(资源); printf(%d,j); printf(:); printf(%d ,NEEDij); printf(n); printf(n各进程已经得到的资源量: n); for (i=0;iM;i+) printf( 进程); printf(%d ,i); for (j=0;jN;j+) printf(资源); printf(%d,j); printf(:); printf(%d ,ALLOCATIONij); printf(n); void changdata(int k) /计算可用资源数，还需资源数 int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj; void rstordata(int k) /资源总数之和 int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj+Requestj; ALLOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj; int chkerr(int s) /判断系统是否安全 int WORK,FINISHM,tempM; int i,j,k=0; for(i=0;iM;i+) FINISHi=FALSE; for(j=0;jN;j+) WORK=AVAILABLEj; i=s; while(iM) if (FINISHi=FALSE&NEEDij=WORK) WORK=WORK+ALLOCATIONij; FINISHi=TRUE; tempk=i; k+; i=0; else i+; for(i=0;iM;i+) if(FINISHi=FALSE) printf(n); printf(系统不安全! 本次资源申请不成功!n); printf(n); return 1; printf(n); printf(经安全性检查，系统安全，本次分配成功。n); printf(n); printf( 本次安全序列：); for(i=0;i); printf(n); return 0; int main() int i=0,j=0; char flag=Y; void showdata(); /函数的声明void changdata(int); void rstordata(int); int chkerr(int); showdata(); /调用函数，显示界面while(flag=Y|flag=y) i=-1; int n; chkerr(i); changdata(i); rstordata(i); while(n=M) printf(请输入需申请资源的进程号（从0到4，否则重输入!）:); scanf(%d,&n); if(n=M) printf(输入的进程号不存在