操作系统课程设计报告

1、 . . . 枣 庄 学 院计算机科学系课程设计任务书题 目： 银行家算法与实现 学号： 0 姓名： 海 专业： 计算机网络 课程： 操作系统 指导教师： 刚 职称： 讲师 完成时间：2011 年 06 月-2011年 06 月枣庄学院计算机科学系制2011年 月 日正 文1 课程设计简介1.1 课程设计题目银行家算法的模拟实现。应用银行家算法验证进程安全性检查与分配资源。1.2 课程设计目的本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。A、了解进程产生死锁的原因，了解为什么要进行死锁的避免。B、掌握银行家算法

2、的数据结构，了解算法的执行过程，加深对银行家算法的理解。1.3 课程设计容此次课程设计的主要容时模拟实现动态资源分配。同时要求编写和调试一个系统动态分配资源有效的防止和避免死锁的发生的简单模拟程序。设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。2 实验原理分析2.1 算法的来源与基本思想银行家算法，顾名思义是来源于银行的借贷业务，通过这个算法可以用来解决生活中的实际问题，如银行贷款等。一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统

3、中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。2.2 死锁产生的条件银行家算法是用来避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件：A、即一个资源每次只能由一个进程使用；B、第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；C、第三个为非剥夺条件，即在出现死

4、锁的系统中一定有不可剥夺使用的资源；D、第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。2.3 模拟进程申请资源把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需

5、求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.3 程序结构分析3.1 程序流程图程序流程图是人们对解决问题的方法、思路或算法的一种描述。 流程图的优点：（a）采用简单规的符号，画法简单；（b）结构清晰，逻辑性强； （c）便于描述，容易理解。 流程图采用规的符号 （1）起始框 （2）终止框 （3）执行框 （4）判别框本次制作流程图省略了起始框和终止框。安全性算法流程：银行家算法流程：注：程序初始化流程包含在银行家流程中但未画出。3.2 程序模块划分A.输出资源分配情况B.输出资源分配后后的情况C.银

6、行家算法: 设进程i提出请求Requestn，则银行家算法按如下规则进 行判断。 1)如果Requestn>Needi，n，则报错返回。 2)如果Requestn>Available，则进程i进入等待资源状态并返回。 3)假设进程i的申请已获批准，于是修改系统状态： Available=Available-Request Allocation=Allocation+Request Need=Need-Request 4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。D.安全性检查 1)设置两个工作向量Work=Available；Finish

7、M=False2)从进程集合中找到一个满足下述条件的进程， Finish i=False Need<=Work 如找到，执行(3)；否则，执行(4) 3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work=Work+Allocation Finish=TrueGO TO 2 (4)如所有的进程FinishM=true，则表示安全；否则系统不安全。4 数据结构分析算法用到的主要数据结构和C语言说明。（1）、可利用资源向量 INT AVAILABLEM M为资源的类型。（2）、最大需求矩阵 INT MAXNM N为进程的数量。（3）、已分配矩阵 INT ALLOCATIONNM

8、（4）、还需求矩阵 INT NEEDN假设有M个进程N类资源，则有如下数据结构:#define W 10#define R 20int M ; /总进程数int N ; /资源种类int ALL_RESOURCEW; /各种资源的数目总和int MAXWR; /M个进程对N类资源最大资源需求量int AVAILABLER; /系统可用资源数int ALLOCATIONWR; /M个进程已经得到N类资源的资源量int NEEDWR; /M个进程还需要N类资源的资源量int RequestR; /请求资源个数5 各子模块相关函数代码5.1 showdata()void showdata() /函数

9、showdata,输出资源分配情况 int i,j; cout<<" "<<endl; cout<<"各种资源的总数量(all):"<<endl; cout<<" " for (j=0;j<N;j+)cout<<" 资源"<<j<<": "<<ALL_RESOURCEj; cout<<endl<<endl; cout<<"系统目前各种资源

10、可用的数为(available):"<<endl; cout<<" " for (j=0;j<N;j+)cout<<" 资源"<<j<<": "<<AVAILABLEj; cout<<endl<<endl; cout<<"" cout<<" 各进程还需要的资源量(need):"<<endl<<endl; cout<<"

11、; " for (j=0;j<N;j+)cout<<setw(8)<<"资源"<<j; for (i=0;i<M;i+) cout<<endl<<"进程p"<<i<<":" for (j=0;j<N;j+)cout<<setw(8)<<NEEDij; cout<<endl; cout<<"" cout<<" 各进程已经得到的资源量(al

12、location): "<<endl<<endl; cout<<" " for (j=0;j<N;j+)cout<<setw(8)<<"资源"<<j; for (i=0;i<M;i+) cout<<endl<<"进程p"<<i<<":" for (j=0;j<N;j+)cout<<setw(8)<<ALLOCATIONij; cout<&l

13、t;endl; 5.2 changdata(int k)void changdata(int k) /函数changdata,改变可用资源和已经拿到资源和还需要的资源的值 int j; for (j=0;j<N;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj; 5.3 rstordata(int k)void rstordata(int k) /函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值 int j; for (j=0;j

14、<N;j+) AVAILABLEj=AVAILABLEj+Requestj; ALLOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj; 5.4 chkerr(int s)int chkerr(int s) /函数chkerr,检查是否安全 int WORK;/FINISHW int i,j,k=0; for(i=0;i<M;i+)FINISHi=FALSE; for(j=0;j<N;j+) WORK=AVAILABLEj; i=s; do if(FINISHi=FALSE&&NEEDij<=W

15、ORK) WORK=WORK+ALLOCATIONij; FINISHi=TRUE; i=0; else i+; while(i<M); for(i=0;i<M;i+) if(FINISHi=FALSE) cout<<endl; cout<<" 系统不安全! 本次资源申请不成功!"<<endl; cout<<endl; return 1; cout<<"进程p"<<i<<"状态：阻塞"<<endl; cout<<en

16、dl; cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl; cout<<endl; return 0; 5.5 set()void set() /进程状态显示函数int t10; for(int i=0;i<M;i+) ti=0; for(int j=0;j<N;j+)if(NEEDij=0) ti+=1; for(i=0;i<M;i+) if(ti=N)cout<<"进程p"<<i<<"状态：运行结束"<<end

17、l; for(int k=0;k<N;k+) AVAILABLEk=AVAILABLEk+ALLOCATIONik; ALLOCATIONik=0; else cout<<"进程p"<<i<<"状态：等待调用"<<endl;5.6 bank()void bank() /银行家算法 int i=0,j=0; char flag='Y' while(flag='Y'|flag='y') i=-1; while(i<0|i>=M) cout<

18、<" 请输入需申请资源的进程号（从P0到P"<<M-1<<"，否则重输入!）:" cout<<"p"cin>>i; if(i<0|i>=M)cout<<" 输入的进程号不存在，重新输入!"<<endl; cout<<" 请输入进程P"<<i<<"申请的资源数:"<<endl; for (j=0;j<N;j+) cout<<

19、" 资源"<<j<<": " cin>>Requestj; if(Requestj>NEEDij) /若请求的资源数大于进程还需要i类资源的资源量j cout<<" 进程P"<<i<<"申请的资源数大于进程P"<<i<<"还需要"<<j<<"类资源的资源量!" cout<<"申请不合理，出错!请重新选择!"<<

20、;endl<<endl; flag='N' break; else if(Requestj>AVAILABLEj)/若请求的资源数大于可用资源数 cout<<" 进程P"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!" cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; flag='N' break; if(flag='Y

21、'|flag='y') changdata(i); /调用changdata(i)函数，改变资源数 if(chkerr(i) /若系统不安全 rstordata(i); /调用rstordata(i)函数，恢复资源数 showdata();/调用showdata()函数，输出资源分配情况 else /若系统安全 showdata(); /调用showdata()函数，输出资源分配情况 set(); else /若flag=N|flag=n showdata(); /调用showdata()函数，输出资源分配情况 cout<<endl; cout<<

22、;" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: " cin>>flag; 6 程序运行结果分析6.1 示例数据进程数：2资源数：2资源0：10资源1：20资源0（最大需求）资源1（最大需求）进程001进程11020资源0（已占有）资源1（已占用）进程000进程1686.2 运行结果输入数据完成初始化 演示图6-2-1注：初始化时，如果输入数据不符合要求，程序能给出错误提示并要求使用者重新输入数据。为简便期间，省去此功能的截屏图像。演示者可以自行上机体会。计算机自动

23、检测水所有进程能否构成一个安全序列。 演示图6-2-2如果能够构成安全序列，就显示出是否进行手动申请资源。输入k 开始手动申请资源。 演示图6-2-3申请资源并进行安全性检查 演示图6-2-2继续演示 演示图6-2-3提示出错继续演示 演示图6-2-4输入N结束演示6.3 出现问题与解决方案A、源程序中未考虑进程状态会随着程序运行发生变化，为了完善程序专门编写了状态函数void set（）来显示进程状态。如图6-2-2与图6-2-4倒数2、3行中均显示了进程状态。B、源程序中指定资源数必须是三种，经过改进后资源数可以为1到10中的任意数。C、源程序资源矩阵的输出界面不能自动适应数据长度的变化，修改后资源的矩阵输出界面中的数据显示获得了改善。7 心得体会这次课程设计没有将程序初始化代码段分离出来，以至于程序的结构不清晰，由于初始化代码不是一个独立的函数致使程