本科毕业论文---银行家算法模拟实现.doc
《本科毕业论文---银行家算法模拟实现.doc》由会员分享,可在线阅读,更多相关《本科毕业论文---银行家算法模拟实现.doc(21页珍藏版)》请在咨信网上搜索。
计算机操作系统程序设计 课程考核报告 银行家算法模拟实现 班 级: 09软件(1) 学 号: 姓 名: 指导老师: 目录 1. 课程设计简介------------------------------------------------3 1.1课程设计题目------------------------------------------------------------- 3 1.2课程设计目的-----------------------------------------3 1.3 课程设计要求----------------------------------------3 2 实验原理分析-------------------------------------------4 2.1 算法的来源及基本思想---------------------------------4 2.2 死锁产生的条件---------------------------------------4 2.3 模拟进程申请资源-------------------------------------5 3 概要设计------------------------------------------------5 4 详细设计------------------------------------------------7 5 代码设计------------------------------------------------8 6 调试分析----------------------------------------------- 14 7 心得体会------------------------------------------------21 8 参考文献------------------------------------------------21 1 课程设计简介: 1.1 课程设计题目 银行家算法的模拟实现。应用银行家算法验证进程安全性检查及分配资源。 1.2 课程设计目的 本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用适当的算法,有效地防止和避免死锁地发生。 A、了解进程产生死锁的原因,了解为什么要进行死锁的避免。 B、掌握银行家算法的数据结构,了解算法的执行过程,加深对银行家算法的理解。 1.3 课程设计要求 设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源,系统按各进程的申请动态的分配资源。要求采用银行家算法实现。 (1) 初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括:进程名,状态,当前申请量,资源需求总量,已占资源量,能执行完标志。其中,进程的状态有:就绪、等待和完成。当系统不能满足进程的资源请求时,进程处于等待态。资源需求总量表示进程运行过程中对资源的总的需求量。 已占资源量表示进程目前已经得到但还未归还的资源量。因此,进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。 (2) 银行家算法分配资源的原则是:当某个进程提出资源请求时,假定先分配资源给它,然后查找各进程的剩余请求,检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能,则让进程等待,否则,让进程的假分配变为真分配。 (a) 查找各进程的剩余请求,检查系统的剩余资源量是否能满足其中一进程。如果能,则转b)。 (b) 将资源分配给所需的进程,这样,该进程已获得资源最大请求,最终能运行完成。标记这个进程为终止进程,并将其占有的全部资源归还给系统。 重复第a)步和第b )步,直到所有进程都标记为终止进程,或直到一个死锁发生。若所有进程都标记为终止进程,则系统的初始状态是安全的,否则为不安全的。若安全,则正式将资源分配给它,否则假定的分配作废,让其等待。 2 实验原理分析: 2.1 算法的来源及基本思想 银行家算法,顾名思义是来源于银行的借贷业务,通过这个算法可以用来解决生活中的实际问题,如银行贷款等。一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。 2.2 死锁产生的条件 银行家算法是用来避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。 死锁的产生,必须同时满足四个条件: A、即一个资源每次只能由一个进程使用; B、第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,单它仍继续宝石已得到的所有其他资源; C、第三个为非剥夺条件,即在出现死锁的系统中一定有不可剥夺使用的资源; D、第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源。 防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。银行家算法是避免死锁的方法中,施加的限制条件较弱的,有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。 2.3 模拟进程申请资源 把一个进程需要和已占有资源的情况记录在进程控制中,假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时,表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然,,每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁. 3 概要设计: 银行家算法可分为个主要的功能模块,其描述如下: 1.初始化 由用户输入数据,分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量(Max),已分配的资源数量赋值。 2.安全性检查算法 (1)设置两个工作向量Work=AVAILABLE;FINISH=false; (2)从进程集合中找到一个满足下述条件的进程, FINISH==false; NEED<=Work; 如找到,执行(3);否则,执行(4) (3)设进程获得资源,可顺利执行,直至完成,从而释放资源。 Work+=ALLOCATION; Finish=true; (4).如所有的进程Finish= true,则表示安全;否则系统不安全。 3. 银行家算法 在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程j提出请求REQUEST [i],则银行家算法按如下规则进行判断。 (1).如果REQUEST [j] [i]<= NEED[j][i],则转(2);否则,出错。 (2).如果REQUEST [j] [i]<= AVAILABLE[j][i],则转(3);否则,出错。 (3).系统试探分配资源,修改相关数据: AVAILABLE[i]-=REQUEST[j][i]; ALLOCATION[j][i]+=REQUEST[j][i]; NEED[j][i]-=REQUEST[j][i]; 用到的数据结构: 实现银行家算法要有若干数据结构,它们用来表示资源分配系统的状态。令n表示系统中进程的数目,m表示资源的分类数。还需要以下数据结构: 1).Available是一个长度为m的向量,它表示每类资源可用的数量。Available [j]=k,表示j类资源可用的数量为k。 2).Max是一个n×m矩阵,它表示每个进程对资源的最大需求。Max [i,j]=k,表示进程pi至多可以申请k个j类资源单位。 3).Allocation是一个n×m矩阵,它表示当前分给每个进程的资源数目。Allocation [i,j]=k,表示进程i当前分到k个j类资源。 4).Need是一个n×m矩阵,它表示每个进程还缺少多少资源。Need[i,j]=k,表示进程pi尚需k个j类资源才能完成其任务。显然Need[i,j]= Max [i,j]- Allocation [i,j]。 4 详细设计: 1主函数main() 要求在主函数中输入运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量(Max),已分配的资源数量,并对这些数据进行有效性检验,不符合条件的数据要进行重新输入。 2函数showdata( ) Showdata()函数用来输出资源的分配情况。对各进程资源的总数量、系统目前可利用的资源数量、各进程还需要的资源数量及各进程已分配的资源数量进行输出。 3函数bank( ) Bank()函数为银行家算法,对需申请资源的进程号j和所要申请的资源数量Request[j]进行输入,并分别将Request[j]与Need[i][j]和Available[j]进行比较,观察所要申请的资源数目是否合理。如合理,则判断此时系统是否安全,若安全则输出资源的分配情况,否则输出原来的系统资源分配情况,重新输入申请资源的数量。 4函数changdata( ) Changdata()函数用来改变可用资源和已经拿到资源和还需要的资源的值。当申请的资源数目合理时,对现在的系统资源分配情况进行刷新。 5函数chkerr() Chkerr()函数用来检查系统此时的安全性。如果系统能够找到一个安全执行的序列,则各进程能正常运行终结,否则,此进程进入阻塞状态。 6函数 rstordata( ) Changdata()函数,改变可用资源和已经拿到资源和还需要的资源的值。若判断出申请资源后系统是安全的,则要改变系统现在的资源分配情况: Available[j]= Available[j]+Request[j]; Allocation[k][j]= Allocation [k][j]-Request[j]; Need[k][j]=Need[k][j]+Request[j] 5 代码设计: #include<string.h> #include<stdio.h> #include<stdlib.h> #define FALSE 0 #define TRUE 1 #define W 10 #define R 20 int M ; //总进程数 int N ; //资源种类 int ALL_RESOURCE[W];//各种资源的数目总和 int MAX[W][R]; //M个进程对N类资源最大资源需求量 int AVAILABLE[R]; //系统可用资源数 int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量 int NEED[W][R]; //M个进程还需要N类资源的资源量 int Request[R]; //请求资源个数 void showdata() //函数showdata,输出资源分配情况 { int i,j; printf("\n\n各种资源的总数量(all):\n"); for (j=0;j<N;j++) printf(" 资源 %d: %d\n",j+1,ALL_RESOURCE[j]); printf("\n\n"); printf("系统目前各种资源可用的数为(available):\n"); for (j=0;j<N;j++) printf(" 资源 %d: %d\n", j+1, AVAILABLE[j]); printf("\n\n"); printf("各进程还需要的资源量(need):\n\n"); printf(" 进程 "); for(i=0;i<N;i++) printf(" 资源%d ",i+1); printf("\n"); for (i=0;i<M;i++) { printf("进程p%d:",i+1); for (j=0;j<N;j++) printf(" %d ",NEED[i][j]); printf("\n"); } printf("\n\n"); printf(" 各进程已经得到的资源量(allocation): \n\n"); printf(" 进程 "); for(i=0;i<N;i++) printf(" 资源%d ",i+1); printf("\n"); for (i=0;i<M;i++) { printf("进程p%d: ",i+1); for (j=0;j<N;j++) printf(" %d ",ALLOCATION[i][j]); printf("\n"); } printf("\n"); } void changdata(int k) //函数changdata,改变可用资源和已经拿到资源和还需要的资源的值 { int j; for (j=0;j<N;j++) { AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];}} void rstordata(int k) //函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值 {int j; for (j=0;j<N;j++) { AVAILABLE[j]=AVAILABLE[j]+Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j];}} int chkerr(int s) //函数chkerr,检查是否安全 { int WORK,FINISH[W]; int i,j,k=0; for(i=0;i<M;i++) FINISH[i]=FALSE; for(j=0;j<N;j++) { WORK=AVAILABLE[j]; i=s; do { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; } else { i++; } }while(i<M); for(i=0;i<M;i++) if(FINISH[i]==FALSE) { printf("\n"); printf(" 系统不安全!!! 本次资源申请不成功!!!\n"); printf("\n"); return 1; } } printf("\n"); printf(" 经安全性检查,系统安全,本次分配成功。\n"); printf("\n"); return 0; } void bank() //银行家算法 { int i=0,j=0; char flag='Y'; while(flag=='Y'||flag=='y') { i=-1; while(i<0||i>=M) { printf(" 请输入需申请资源的进程号(从P1到P%d,否则重输入!):",M); printf("p"); scanf("%d",&i); if(i<1||i>M) printf(" 输入的进程号不存在,重新输入!\n"); } printf(" 请输入进程P%d申请的资源数:\n",i); for (j=0;j<N;j++) { printf(" 资源%d:",j+1); scanf("%d",&Request[j]); if(Request[j]>NEED[i-1][j]) //若请求的资源数大于进程还需要i类资源的资源量j { printf(" 进程P%d申请的资源数大于进程P%d还需要%d类资源的资源量!",i,i,j); printf("申请不合理,出错!请重新选择!\n\n"); flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) //若请求的资源数大于可用资源数 { printf("进程P%d申请的资源数大于系统可用%d类资源的资源量!",i,j); printf("申请不合理,出错!请重新选择!\n\n"); flag='N'; break; } } } if(flag=='Y'||flag=='y') { changdata(i-1); //调用changdata(i)函数,改变资源数 if(chkerr(i-1)) //若系统安全 { rstordata(i-1); //调用rstordata(i)函数,恢复资源数 showdata(); //输出资源分配情况 } else //若系统不安全 showdata(); } //输出资源分配情况 else //若flag=N||flag=n showdata(); printf("\n"); printf("是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: "); scanf("%c",&flag); } } void main() //主函数 { int i=0,j=0,p; printf(" *************************************** \n"); printf(" 银行家算法的模拟实现 \n"); printf(" 20090307143 吴天一 \n"); printf(" *************************************** \n\n"); printf("请输入总进程数:"); scanf("%d",&M); printf("请输入总资源种类:"); scanf("%d",&N); printf("请输入总资源数(all_resource):"); for(i=0;i<N;i++) scanf("%d",&ALL_RESOURCE[i]); printf("依次输入各进程所需要的最大资源数量(max):\n"); for (i=0;i<M;i++) { for (j=0;j<N;j++) { do { scanf("%d",&MAX[i][j]); if (MAX[i][j]>ALL_RESOURCE[j]) printf("\n占有资源超过了声明的该资源总数,请重新输入!\n"); }while (MAX[i][j]>ALL_RESOURCE[j]); } } printf("依次输入各进程已经占据的资源数量(allocation):\n"); for (i=0;i<M;i++) { for (j=0;j<N;j++) { do { scanf("%d",&ALLOCATION[i][j]); if (ALLOCATION[i][j]>MAX[i][j]) printf("\n占有资源超过了声明的最大资源,请重新输入\n"); }while (ALLOCATION[i][j]>MAX[i][j]); } }//初始化资源数量 for (j=0;j<N;j++) { p=ALL_RESOURCE[j]; for (i=0;i<M;i++) { p=p-ALLOCATION[i][j];//减去已经被占据的资源 AVAILABLE[j]=p; if(AVAILABLE[j]<0) AVAILABLE[j]=0; } } for (i=0;i<M;i++) for(j=0;j<N;j++) NEED[i][j]=MAX[i][j]-ALLOCATION[i][j]; showdata(); bank(); } 6 调试分析: 输出结果如下图所示: 当输入进程数和资源种类数及总资源量、所需最大资源数量Max和已分配资源量时,系统调用后showdata()函数,显示现在系统的资源分配情况。当输入需要申请的进程号和其所需的资源数目时,系统调用bank()函数,在进行安全性检验,若此时系统安全,则系统为其分配资源,若此时系统没有通过安全性检验,则显示提示语句,恢复系统原来的资源分配情况,再重新进行选择。 下图所显示的程序运行结果所输入的数据都是有效的,无效数据的输入这里因为篇幅的原因没有给出。当输入的结果大于其范围时,程序会输出提示语句,此后再重新输入数据。 以课本P110银行家算法之例为例 资源不足时 资源足够时 资源足够且请求分配资源足够时 资源足够但请求资源不足时 7 心得体会 一周的操作系统课程设计,我学到了很多课本上没有的知识。想要完成模拟银行家算法的C语言程序,首先就是要彻底熟悉算法,了解算法的基本原理,才能开始着手程序设计在程序设计设计过程中,遇到了一些困难,通过向同学询问,翻阅资料等,问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和避免死锁的算法,并用C语言程序真正模拟出安全性检查和银行家算法过程,复习了之前所学C语言和数据结构的知识;在编程过程中虽然遇到很多困难,解决问题的过程中,同时也锻炼了我不怕困难,勇于迎接挑战的精神,为以后的挑战磨练了必胜的信心。 8 参考文献 [1] 计算机操作系统(第三版) 作者:汤子瀛- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 本科毕业 论文 银行家 算法 模拟 实现
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文