计算机操作系统课程设计.docx

1、 学 院信息科学与工程学院课程设计任务书题目：银行家算法 课程设计任务书及成绩评定课程设计的任务和具体要求指导教师签字： 日期：指导教师评语成绩：指导教师签字： 日期：课程设计所需软件、硬件等WIN-TC环境课程设计进度计划起至日期工作内容备注2014年6月6日1）从键盘输入当前系统的资源信息2）输入进程请求3）各种异常的处理参考文献、资料索引序号文献、资料名称编著者出版单位1 计算机操作系统汤子瀛，西安电子科技大学出版社,2007.86-132；2 C语言程序设计谭浩强，清华大学出版社,2009,(10):283；3目录一、绪论二、需求分析三、算法分析四、设计五、程序调试六、总结附录（源代码

2、）一、 绪论Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。银行家算法是一种最有代表性的避免死锁算法。在避免思死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入

3、不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，

4、所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。二、 需求分析2.1问题描述当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不

5、会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。.2.2基本要求（1）从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量，输出结果显示在DOS界面上；（2）输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果（主要包括资源分配表和安全序列）（3）要求要有各种异常的处理，

6、程序的可控制性和可连续性执行。包括对进程的存在有无检查，请求向量的不合法检查，试分配失败后的数据恢复和重新接受进程请求等。 2.3概要分析在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。所谓安全状态是指系统能按某种顺序如（称为安全序列），就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全

7、状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。2.4数据流模型输出结果信息录入输入信息安全性检查请求分配安全性检查三、算法分析3.1算法思路先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。3.2银行家算法步骤（1）如果Requestior =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requ

8、estor=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Request; Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3.3安全性算法步骤（1）设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源

9、分配给进程，使之运行完成，开始时先做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 process

10、nemaN; /进程名(2）可利用资源向量int AvailableM; /资源清单系统中现有各资源空闲个数。(3）最大需求矩阵int MaxNM; /最大需求矩阵每个进程对各资源的最大需求数分配矩阵(4）已分配矩阵int AllocationNM;/分配矩阵系统给每个进程已分配的各类资源数(5）需求矩阵int NeedNM; /需求矩阵每个进程还需要每种资源的个数申请各类资源数量(6）申请向量int Request M /进程申请资源的向量(7）工作向量int WorkNM; /初始第一个向量为Available,随寻找安全序列时为其余每个向量赋值，可以防止安全序列未找到而丢了初始状态的值(

11、8）安全序列向量int sequenceN=0;/存放安全序列号(9）标志向量int FinishN /求安全序列时记录每个进程是否可以顺利执行4.2程序的模块void main()/系统主函数intcheck_distribution()/安全性检查函数intcheck_safe()/银行家算法函数void print()/输出函数4.3程序流程图五、程序调试函数的书写分模块进行，每完成一个模块进行调试、测试直到该函数运行无误。1、进程信息的输入与输出调试(1) 能正确无误的输入进程名向量processnemaN，输入系统现有各类资源数量AvailableM向量，输入每个进程对各类资源的最大

12、需求数MaxNM矩阵，输入系统给每个进程已分配的各类资源数AllocationNM矩阵。输出程序过程如下图所示：(2) 在进程信息输入中没有出现多大问题，在进程信息输出时，按设计要求输出的话应该是一个表格形式，在输出函数设计最初，由于有些部分分割或空格没有填充好，导致输出表格比较乱，没有达到设计要求，经过修改后输出形式才符合了设计要求，进程信息输入完成后，初始状态各进程信息输出如下：2、进程请求资源输入出错提示信息处理在系统询问是否有进程申请资源时，如果有输入信息出错，系统会给与出错提示，如果输入信息正确则系统将继续执行下面操作，执行如下：3、判断是否可以试分配函数intcheck_distr

13、ibution(int* p,int k)在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件Request =need或Request =available,如果不满足将打出提示信息，如果满足，则返回1继续执行下面程序，执行结果如下：4、求安全序列函数intcheck_safe()如果申请资源的进程申请的资源数目满足试分配条件，则再用这个函数来求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源，系统恢复初始状态，打印出提示信息，执

14、行结果如下：六、总结经过几天的操作系统课程设计，我学习到了很多东西。首先，这次课程设计的内容是银行家算法，我用的编程工具是VC+，语言使用的是C语言，目的是模拟实现处理机避免死锁；其次，通过模拟实现算法，我更进一步地学习了C语言，这使我的编程能力得到了提高。解决死锁，我们要检测一个安全状态，虽然并非所有的不安全状态都会产生死锁状态，但系统进入不安全状态时，便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果

15、可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于如何使系统不进入不安全状态。很明显这些概念在操作系统上是非常重要的东西，我相信这对我以后的学习也有很大的帮助。附录（源代码）#include#include#include#include /*用到了getch()*/#defin

16、e 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类资源的资源量*/in

17、t RequestN=0,0,0;void main()int i=0,j=0;char flag;voidshowdata();voidchangdata(int);voidrstordata(int);intchkerr(int);showdata();enter:printf(请输入需申请资源的进程号（从0到);printf(%d,M-1);printf(）:);scanf(%d,&i);if(i=M)printf(输入的进程号不存在，重新输入!n);goto enter;err:printf(请输入进程);printf(%d,i);printf(申请的资源数n);printf(类别:A

18、BCn);printf();for(j=0;jNEEDij)printf(%d,i);printf(号进程);printf(申请的资源数进程);printf(%d,i);printf(还需要);printf(%d,j);printf(类资源的资源量!申请不合理，出错!请重新选择!n);goto err;elseif(RequestjAVAILABLEj)printf(进程);printf(%d,i);printf(申请的资源数大于系统可用);printf(%d,j);printf(类资源的资源量!申请不合理，出错!请重新选择!n);goto err;changdata(i);if(chkerr

19、(i)rstordata(i);showdata();elseshowdata();printf(n);printf(按y或Y键继续,否则退出n);flag=getch();if(flag=y|flag=Y)goto enter;elseexit(0);/*显示数组*/voidshowdata()inti,j;printf(系统可用资源向量:n);printf(*Available*n);printf(资源类别:ABCn);printf(资源数目:);for(j=0;jN;j+)printf(%d,AVAILABLEj);printf(n);printf(n);printf(各进程还需要的资源

20、量:n);printf(*Need*n);printf(资源类别:ABCn);for(i=0;iM;i+)printf();printf(%d,i);printf(号进程:);for(j=0;jN;j+)printf(%d,NEEDij);printf(n);printf(n);printf(各进程已经得到的资源量:n);printf(*Allocation*n);printf(资源类别:ABCn);for(i=0;iM;i+)printf();printf(%d,i);printf(号进程:);/*printf(:n);*/for(j=0;jN;j+)printf(%d,ALLOCATION

21、ij);printf(n);printf(n);/*系统对进程请求响应，资源向量改变*/voidchangdata(int k)int j;for(j=0;jN;j+)AVAILABLEj=AVAILABLEj-Requestj;ALLOCATIONkj=ALLOCATIONkj+Requestj;NEEDkj=NEEDkj-Requestj;AVAILABLEj=AVAILABLEj+ALLOCATIONkj;/*资源向量改变*/voidrstordata(int k)int j;for(j=0;jN;j+)AVAILABLEj=AVAILABLEj+Requestj;ALLOCATIONk

22、j=ALLOCATIONkj-Requestj;NEEDkj=NEEDkj+Requestj;/*安全性检查函数*/intchkerr(int s)int WORK,FINISHM,tempM;inti,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;elsei+;for(i=0;iM;i+)if(FINISHi=FALSE)printf(n);printf(系统不安全!本次资源申请不成功!n);printf(n);return 1;printf(n);printf(经安全性检查，系统安全，本次分配成功。n);printf(n);printf(本次安全序列：n);printf(进程依次为);for(i=0;i);printf(n);return 0;19