操作系统课设电子稿.doc

一.课题简介银行家算法是避免死锁的一种重要方法，本课程设计要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升.二.程序总体设计随机分配算法:当进程申请资源时，如果系统中现存资源数能满足进程的当前资源申请量，就把资源能会产生死锁。随机分配算法很容易进入死锁.银行家分配算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。把各进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.三.算法的分析与设计模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1如果Request=Need,则转向2;否则,出错2如果Request=Available,则转向3,否则等待3系统试探分配请求的资源给进程AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST 4系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finishi=true;转24. 若所有进程的Finishi=true,则表示系统安全;否则,不安全!银行家算法数据结构: 假设有M个进程N类资源，则有如下数据结构： MAXM*N M个进程对N类资源的最大需求量 AVAILABLEN 系统可用资源数 ALLOCATIONM*N M个进程已经得到N类资源的资源量 NEEDM*N M个进程还需要N类资源的资源量初始化流程图如下:银行家算法流程图如下:四.程序的描述#include string.h #include iostream.h #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=3,3,2; /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; int RequestN=0,0,0; void main() /主函数,实现银行家算法的基本流程 int i=0,j=0; /初始化进程数i和资源数jchar flag=Y; /是否继续进行银行家演示void showdata(); /显示分配资源后的状态void changdata(int); /改变要申请的进程和所对应的资源int chkerr(int); /检测系统是否安全showdata(); while(flag=Y|flag=y) i=-1; while(i=M) /输入进程号和对应的进程需申请的资源数 cout 请输入需申请资源的进程号（从0到M-1i; if(i=M)cout 输入的进程号不存在，重新输入!endl; cout 请输入进程i申请的资源数endl; for (j=0;jN;j+) /判断申请资源是否小于还需要的资源 cout 资源jRequestj; if(RequestjNEEDij) /如果大于则出错 cout 进程i申请的资源数大于进程i还需要j类资源的资源量!; cout申请不合理，出错!请重新选择!endlAVAILABLEj) /判断申请资源是否小于系统可用资源 cout 进程i申请的资源数大于系统可用j类资源的资源量!; cout申请不合理，出错!请重新选择!endlendl; flag=N; break; if(flag=Y|flag=y) changdata(i); if(chkerr(i) /检测是否系统是否安全 showdata(); /输出结果 else showdata(); /不安全,直接输出结果 else showdata(); coutendl; coutflag; /进行第一次的资源申请及分配情况void showdata() int i,j; cout 系统可用的资源数为:endlendl; cout ; for (j=0;jN;j+)cout 资源j: AVAILABLEj; coutendl; coutendl; cout 各进程还需要的资源量:endlendl; for (i=0;iM;i+) cout进程i:; for (j=0;jN;j+)cout 资源j: NEEDij; coutendl; coutendl; cout 各进程已经得到的资源量: endlendl; for (i=0;iM;i+) cout进程i:; for (j=0;jN;j+)cout 资源j: ALLOCATIONij; coutendl; coutendl; /改变数据时系统的状态,写入此次申请的资源分配后的新状态void changdata(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) coutendl; cout 系统不安全! 本次资源申请不成功!endl; coutendl; return 1; coutendl; cout 经安全性检查，系统安全，本次分配成功。endl; coutendl; cout 本次安全序列：; for(i=0;iM;i+)cout进程tempi; coutendlendl; return 0; ;五.上机编程调试过程编此程序过程中,出现了不少错误1. C:Documents and Settings黑眼豆豆My DocumentsMy QQ FilesCpp1.cpp(63) : error C2660: changdata : function does not take 1 parameters执行 cl.exe 时出错. Changdata这个方法的成员变量有固定的数据类型,为整型,所以void changdata(),改为void changdata(int)2. Cpp1.obj : error LNK2001: unresolved external symbol int _cdecl chkerr(int) (?chkerrYAHHZ)Debug/Cpp1.exe : fatal error LNK1120: 1 unresolved externals执行 link.exe 时出错.经查错发现,chkerr方法里需要声明一个成员变量s,然后将进程i赋予s,循环运行此方法,才能实现相应的功能除此两个错误花了我很多时间,其他错误都是些诸如格式 拼写之类的小错误,在此就不一一列出了六.运行效果分析1.此系统中有5个进程：0，1，2，3，4， 3个资源：0，1，2下图显示了初始各进程还需要的资源量和已经得到的资源量：2.假定进程1申请1个0类资源，0个