操作系统课程设计银行家算法模拟实现.doc

课 程 设 计 报 告课程设计名称： 银行家算法模拟实现 系 ： 学生姓名： 班 级： 学 号： 成 绩： 指导教师： 开课时间： 学年 学期题目要求：一设计题目 银行家算法模拟实现二主要内容设计目的1、 了解多道程序系统中，多个进程并发执行的资源分配。2、 掌握思索的产生原因、产生死锁的必要条件和处理死锁的基本方法。3、 掌握预防死锁的方法，系统安全状态的基本概念。4、 掌握银行家算法，了解资源在进程并发执行中的资源分配策略。5、 理解死锁避免在当前计算机系统不常使用的原因。三具体要求设计一个n个并发进程共享m个系统资源的系统，进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。四进度安排序号内 容时间（天）1熟悉课题、分析课题0.52对系统进行模块分解，问题分析和确定解决方案13编程调试34测试和差错15书写课程设计报告16考核1合 计7.5五成绩评定考核方法：根据学生平时表现、测试检查、课程设计报告、运行演示和学生回答问题相结合的形式作为考核依据，考察学生的动手能力，独立分析解决问题的能力和创新精神，并根据学生的学习态度综合考评。平时表现（占30%），课程设计报告（占40%），课程答辩（占30%）。成绩评定：成绩分“优秀”、“良好”、“中等”、“及格”、“不及格”五个级别。“优秀”为100分到90分，“良好”为89分到80分，“中等”为79分到70分，“及格”为69分到60分，“不及格”为60分以下。目录1.需求分析42.概要设计43.详细设计64.调试分析125.总结166.参考文献161.需求分析1、始化这组进程的最大资源请求和一次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪，等待和完成。当系统不能满足进程的资源请求时，进程出于等待状态。资源需求总量表示进程运行过程中对资源的总的需求量。已占资源量表示进程目前已经得到但还为归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。陷入每个进程的资源需求总量不应超过系统拥有的资源总量。2、银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。A) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程，如果能，则转B）。B）将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。重复第A)步和B)步，直到所有进程都标记为终止进程，或知道一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。2.概要设计2.1设计思想当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。2.2数据结构假设有m个进程，则有如下数据结构:#define w 50 /宏定义#define r 50 /宏定义int m; /总进程数 int allw;/各种资源的数目总和int maxwr; /m个进程最大资源需求量int availabler; /系统可用资源数int allocationwr; /m个进程已经得到资源的资源量int needwr; /m个进程还需要资源的资源量int requestr; /请求资源个数2.3程序流程图开始输入进程数m，各资源总数，初始化Available向量i=1i<=m输入进程i的最大需求向量max。max<=资源总数i+YNNY错误初始化need任选一个进程作为当前进程（0到m-1）该进程的Need向量为0输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示NY该进程已运行结束Need矩阵为0Y结束3.详细设计3.1算法思想银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。否则拒绝分配。3.2银行家算法设Requestn，是进程的请求向量，如果Requestn=m，则表示该进程需要m个资源。当该进程发出资源请求后，系统按下述步骤进行检查：(1)如果Requestn=Needi，n，便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。 (2)如果Requestn>Available，则进程i进入等待资源状态，返回。 (3)假设进程i的申请已获批准，于是修改下面数据结构中的数值： Available=Available-Request Allocation=Allocation+RequestNeed=Need-Request (4)系统执行安全性检查，如安全，则分配成立；否则恢复原来的资源分配状态，系统恢复原状，进程等待。 程序void bank() /银行家算法 int i=0,j=0; char flag='Y' while(flag='Y'|flag='y') i=-1; while(i<0|i>=m) cout<<" 请输入需申请资源的进程号（从0到"<<m-1<<"）:" cin>>i; if(i<0|i>=m)cout<<" 该进程号不存在，请重新输入!"<<endl; cout<<" 请输入进程"<<i<<"申请的资源数:" for (j=0;j<1;j+) cout<<" " cin>>requestj; if(requestj>needij) /若请求的资源数大于进程还需要i类资源的资源量j cout<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要资源的资源量!" cout<<"申请不合理，请重新选择!"<<endl<<endl; flag='1' break; else if(requestj>availablej) /若请求的资源数大于可用资源数 cout<<" 进程"<<i<<"申请的资源数大于系统可用资源的资源量!" cout<<"申请不合理!请重新选择!"<<endl<<endl; flag='1' break; if(flag='Y'|flag='y') change(i); /调用change(i)函数，改变资源数 if(chkerr(i) /若系统安全 rstore(i); /调用rstore(i)函数，恢复资源数 show(); /输出资源分配情况 else /若系统不安全 show(); /输出资源分配情况 else /若flag=N|flag=n show(); cout<<endl; cout<<" 是否继续(Y/N): " cin>>flag; 3.3安全性检查算法(1)设置两个工作向量Work=Available；FinishM=False(2)从进程集合中找到一个满足下述条件的进程， Finish i=False Need<=Work 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work=Work+Allocation Finish=True GO TO 2 (4)如所有的进程FinishM=true，则表示安全；否则系统不安全。程序int chkerr(int s) /检查安全性 int work,FInISHw; int i,j,k=0; for(i=0;i<m;i+)FInISHi=false; for(j=0;j<1;j+) work=availablej; i=s; do if(FInISHi=false&&needij<=work)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<<endl; cout<<" 系统安全，分配成功。"<<endl; cout<<endl; return 0; 3.4 修改数据结构中的数值改变可用资源和已经拿到资源和还需要的资源的值void change(int k) int j; for (j=0;j<1;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; 3.5 如果分配失败，则恢复原来的资源分配状态恢复可用资源和已经拿到资源和还需要的资源的值void rstore(int k) int j; availablej=availablej+requestj; allocationkj=allocationkj-requestj; needkj=needkj+requestj; 3.6 输出显示实现人机交互的各类资源输出显示情况。void show() /输出资源分配情况 int i,j; cout<<"资源总量:"<<" " for (j=0;j<1;j+)cout<<" "<<allj; cout<<endl<<endl; cout<<"系统目前资源可用数:"<<" " for (j=0;j<1;j+)cout<<" "<<availablej; cout<<endl<<endl; cout<<"进程名 各进程还需要的资源量"<<endl; for (i=0;i<m;i+) for (i=0;i<m;i+) cout<<"进程"<<i<<": " for (j=0;j<1;j+)cout<<needij<<" " cout<<endl; cout<<endl; cout<<"进程名 各进程已经得到的资源量"<<endl; for (i=0;i<m;i+) cout<<"进程"<<i<<": " for (j=0;j<1;j+)cout<<allocationij<<" " cout<<endl; cout<<endl; void change(int k) /改变可用资源和已经拿到资源和还需要的资源的值 int j; for (j=0;j<1;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; 3.7 主函数void main() /主函数 int i=0,j=0,p; cout<<"-银行家算法模拟-"<<endl; cout<<"请输入总进程数:" cin>>m; cout<<"请输入总资源数:" for(i=0;i<1;i+) cin>>alli; cout<<"依次输入各进程所需要的最大资源数量:"<<endl; for (i=0;i<m;i+) for (j=0;j<1;j+) do cin>>maxij; if (maxij>allj) cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl; while (maxij>allj); cout<<"依次输入各进程已经占据的资源数量:"<<endl;for (i=0;i<m;i+) for (j=0;j<1;j+) do cin>>allocationij; if (allocationij>maxij) cout<<endl<<"占有资源超过了声明的最大资源,请重新输入"<<endl; while (allocationij>maxij); /初始化资源数量 for (j=0;j<1;j+) p=allj; for (i=0;i<m;i+) p=p-allocationij;/减去已经被占据的资源 availablej=p; if(availablej<0) availablej=0; for (i=0;i<m;i+) for(j=0;j<1;j+) needij=maxij-allocationij; show(); bank();3.8 定义全局变量#include "string.h" #include "iostream"using namespace std;#define false 0 #define true 1 #define w 50 /宏定义#define r 50 /宏定义int m; /总进程数 int allw;/各种资源的数目总和int maxwr; /m个进程最大资源需求量int availabler; /系统可用资源数int allocationwr; /m个进程已经得到资源的资源量int needwr; /m个进程还需要资源的资源量int requestr; /请求资源个数4.调试分析图4-1图4-1这里为3个进程（进程0.1.2）共用10个资源，分别需要的最大资源数为3,4,3.已经占有的资源数为：1,2,2. 分配给0号进程1个资源，系统安全，分配成功图4-24-2再分配给0号进程1个资源，系统安全，分配成功图4-34-3分配给1号进程3个资源，因为1号资源还需要2个即达到最大需要资源数，故申请不合理，分配不成功图4-4图4-4重新设定2个进程（0,1）共用5个资源。分别需要的最大资源数为4,3.已经占有的资源数为3,1。进程1申请2个资源，大于系统可用资源数。申请不合理，故申请失败。图4-5图4-5进程1申请1个资源，此时发生死锁，故申请失败。（发生死锁后，程序出错。）5.总结由于本人技术与经验的不足，在设计n类资源时出现未找到解决方法的错误，因此只把资源种类设计成只有一类。这样程序的编写得到简化。当然在实际实现时会出现很多类资源，这是这个程序需要改进的地方。进程请求资源后，若产生死锁，则程序出错。相信随着对操作系统与死锁等问题的深入了解，会更好的完善这个程序。在上学期的数据库课程里已经初步认识了银行家算法，对它有了一定的了解。它是避免死锁的主要方法，书上的介绍也许不够详细与完整，所以在这次课程设计中，通过查阅大量书籍资料，让我对它产生了一定的深入认识，只是由于一些个人原因，未能及时完成。在以后的学习中，这种算法还将会有很多地方要用到的。所以不能报着“学过就完事”的态度。当然，以后可能还会有比这种算法更好的算法，但是核心思想与它的目的是不会变的。所以，弄懂弄透了之后，再学习操作系统的更多知识会更容易上手。6.参考文献1.汤小丹计算机操作系统（第三版）西安：电子科技大学出版社；2.张丽芬操作系统实验教程清华大学出版社。