操作系统银行家算法.docx
- 文档编号:14459888
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:20
- 大小:306.93KB
操作系统银行家算法.docx
《操作系统银行家算法.docx》由会员分享,可在线阅读,更多相关《操作系统银行家算法.docx(20页珍藏版)》请在冰点文库上搜索。
操作系统银行家算法
课程设计报告
课程名称:
操作系统
设计题目:
银行家算法
院系:
班级:
设计者:
学号:
课程设计任务书
姓名:
院(系):
专业:
学号:
任务起止日期:
课程设计题目:
银行家算法
课程设计要求及任务描述:
1.分析设计内容,给出解决方案
2.画出程序的基本结构框图和流程图。
3.对程序的每一部分要有详细的设计分析说明。
4.要求有数据结构的设计。
5.要附加源代码且格式要规范。
6.对得到的运行结果要有分析。
7.对设计中遇到的问题要写入总结。
8.按期提交完整的程序代码和课程设计报告。
工作计划及安排:
2014-1-2
上午:
认真阅读课程设计的各种要求,查阅相关资料
下午:
进行数据结构设计并画流程图
2014-1-3
上午:
交老师检查流程图并完善需要改进的不足
下午:
按照完善后的流程图开始编写程序
(变量统一定义及初始化函数部分代码编写)
2014-1-4
上午:
按照完善后的流程图编写程序
(安全判断函数和输出函数的编写)
下午:
按照完善后的流程图编写程序
(银行家算法函数和主函数的编写及调试)
2014-1-5
上午:
调试程序,完善细节功能
下午:
交老师检查程序,接受提问并完成课程设计实验报告。
2014-1-6
完善报告,提交报告
指导教师签字
年月日
课程设计(大作业)成绩
学号:
姓名:
指导教师:
课程设计题目:
银行家算法
完成情况总结:
本次设计中首先要解决的问题是对所做题目的理解。
像银行家算法这一问题,如果单看题目要求往往不知如何下手,更不要谈下一步的设计过程。
但是在看完并理解了ppt之后,就知道要从哪入手,在银行家算法中,重点和难点都是安全性的判断及输出安全序列。
明白了需求,下一个难点是如何通过软件实现。
为了防止死锁,需要进行大量的判断,这也导致了一个问题,即在进行调试时,一旦出现问题,往往难以找到问题所在。
在实现的时候,应该先给他试探性的分配资源,然后再来调用安全性检查函数,否则在调试时会先出现“是否继续?
‘Y’或‘N’”,此时就会出错。
在调试时,我还出现在输入‘Y’后,会异常退出的情况,这时,只要用getchar()就可以解决。
在这次课程设计中,我发现问题,解决问题,虽然也有没有解决的情况,但这让我复习了放下很久的C语言。
总体来说,解决问题的过程中,使我学到了许多平时忽略掉的问题,让我受益匪浅。
指导教师评语:
成绩:
填表时间:
指导教师签名:
课程设计报告
一、题目分析
在死锁的避免中,银行家算法把系统状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可以避免发生死锁。
所谓安全状态,是指系统能按某种顺序为每个进程分配所需资源,直到最大需求,使每一个进程都可以顺利完成,即可找到一个安全资源分配序列。
银行家算法基本原理:
操作系统在每一次分配之前都要进行以下操作,判断当前的资源请求是否安全,如果安全则实施分配,否则不予分配。
第1步:
操作系统对提出资源请求的进程按所请求的资源数目实施预分配,修改剩余资源数组、资源分配矩阵和剩余资源请求矩阵;
第2步:
将剩余资源数组代入剩余需求矩阵中与各元素进行比较,找到可以满足其所有资源需求的某个进程将它加入到安全序列中;
第3步:
将该进程运行结束后释放的资源累加到剩余资源数组中;
第4步:
再重复第2、3两步。
若所有进程都能够进入安全序列
如果不能实施分配,则将系统还原到预分配之前的状态。
二、程序设计
1.数据结构设计
(1)设计数据结构:
剩余资源数组available,如available[j]=k表示资源Rj现有k个。
(2)设计数据结构:
最大资源请求矩阵max,如max[i][j]=k表示进程Pi最多可申请k个类型为Rj的资源。
(3)设计数据结构:
资源分配矩阵allocation,定义每个进程现在所分配的各种资源类型的数量,如allocation[i][j]=k表示进程Pi现在分配了k个类型为Rj的资源。
(4)设计数据结构:
剩余资源请求矩阵claim,定义每个进程还需要的剩余的资源数,如claim[i][j]=k表示进程Pi还需要申请k个类型Rj的资源。
其中,claim[i][j]=max[i][j]-allocation[i][j]。
(5)设计函数完成功能:
系统内资源总数已知、各进程对各类资源最大需求数目已知、已分配资源数目已知的前提下,某进程提出各类资源的需求量时能判断状态是否安全,以决定是否予以分配。
2.函数设计
(1)初始化
由用户输入数据,分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量,已分配的资源数量赋值。
(2)安全性检查算法
1.设置两个工作向量Work=AVAILABLE;FINISH=false;
2.从进程集合中找到一个满足下述条件的进程,
FINISH==false;
CLAIM<=Work;
如找到,执行(3);否则,执行(4)
3.设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work+=ALLOCATION;
Finish=true;
4.如所有的进程Finish=true,则表示安全;否则系统不安全。
(3)银行家算法
在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
设进程j提出请求REQUEST[i],则银行家算法按如下规则进行判断。
(a).如果REQUEST[j][i]<=CLAIM[j][i],则转(b);否则,出错。
(b).如果REQUEST[j][i]<=AVAILABLE[j][i],则转(c);否则,出错。
(c).系统试探分配资源,修改相关数据:
AVAILABLE[i]-=REQUEST[j][i];
ALLOCATION[j][i]+=REQUEST[j][i];
CLAIM[j][i]-=REQUEST[j][i];
(d)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
(e)对于某一进程i,若对所有的j,有CLAIM[j][i]=0,则表此进程资源分配完毕,应将占用资源释放。
3.流程图
YES
NO
NO
YES
YES
YES
NO
4.代码
#include
#include
#include
#defineFALSE0
#defineTRUE1
#defineW10
#defineR20
intM;//总进程数
intN;//资源种类
intALL_RESOURCE[W];//各种资源的数目总和
intMAX[W][R];//M个进程对N类资源最大资源需求量
intAVAILABLE[R];//系统可用资源数
intALLOCATION[W][R];//M个进程已经得到N类资源的资源量
intCLAIM[W][R];//M个进程还需要N类资源的资源量
intRequest[R];//请求资源个数
voidshowdata()//函数showdata,输出资源分配情况
{
inti,j;
printf("\n\n各种资源的总数量(all):
\n");
for(j=0;j printf("资源%d: %d\n",j+1,ALL_RESOURCE[j]); printf("\n\n"); printf("系统目前各种资源可用的数为(available): \n"); for(j=0;j printf("资源%d: %d\n",j+1,AVAILABLE[j]); printf("\n\n"); printf("各进程还需要的资源量(CLAIM): \n\n"); printf("进程"); for(i=0;i printf("资源%d",i+1); printf("\n"); for(i=0;i { printf("进程p%d: ",i+1); for(j=0;j printf("%d",CLAIM[i][j]); printf("\n"); } printf("\n\n"); printf("各进程已经得到的资源量(allocation): \n\n"); printf("进程"); for(i=0;i printf("资源%d",i+1); printf("\n"); for(i=0;i { printf("进程p%d: ",i+1); for(j=0;j printf("%d",ALLOCATION[i][j]); printf("\n"); } printf("\n"); } voidchangdata(intk)//函数changdata,改变可用资源和已经拿到资源和还需要的资源的值 { intj; for(j=0;j { AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; CLAIM[k][j]=CLAIM[k][j]-Request[j]; } } voidrstordata(intk)//函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值 { intj; for(j=0;j { AVAILABLE[j]=AVAILABLE[j]+Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; CLAIM[k][j]=CLAIM[k][j]+Request[j]; } } intchkerr(ints)//函数chkerr,检查是否安全 { intWORK,FINISH[W]; inti,j,k=0; for(i=0;i FINISH[i]=FALSE; for(j=0;j { WORK=AVAILABLE[j]; i=s; do { if(FINISH[i]==FALSE&&CLAIM[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; } else { i++; } } while(i for(i=0;i if(FINISH[i]==FALSE) { printf("\n"); printf("系统不安全本次资源申请不成功\n"); printf("\n"); return1; } } printf("\n"); printf("经安全性检查,系统安全,本次分配成功。 \n"); printf("\n"); return0; } voidbank()//银行家算法 { inti=0,j=0; charflag='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 { printf("资源%d: ",j+1); scanf("%d",&Request[j]); if(Request[j]>CLAIM[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'键退出演示: "); getchar(); scanf("%c",&flag); } } voidmain()//主函数 { inti=0,j=0,p; printf("*************************************************************\n"); printf("银行家算法的模拟实现\n\n\n"); printf("班级: 2011级计科(3)班姓名: 叶萌学号: 201111010347\n"); printf("*************************************************************\n\n"); printf("请输入总进程数: "); scanf("%d",&M); printf("请输入总资源种类: "); scanf("%d",&N); printf("请输入总资源数: "); for(i=0;i scanf("%d",&ALL_RESOURCE[i]); printf("依次输入各进程所需要的最大资源数量: \n"); for(i=0;i { for(j=0;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("依次输入各进程已经占据的资源数量: \n"); for(i=0;i { for(j=0;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 { p=ALL_RESOURCE[j]; for(i=0;i { p=p-ALLOCATION[i][j];//减去已经被占据的资源 AVAILABLE[j]=p; if(AVAILABLE[j]<0) AVAILABLE[j]=0; } } for(i=0;i for(j=0;j CLAIM[i][j]=MAX[i][j]-ALLOCATION[i][j]; showdata(); bank(); } 三、结果分析 【初始化,输入各进程和资源的信息】 【输出初始化后各进程和资源的信息】 【P1申请的资源大于它还需要的资源量,提示出错】 【再次输出系统中各进程和资源的信息,并提示是否继续】 【继续分配,分配成功】 【输出分配成功后系统中资源和进程的信息】 【输入‘n’,退出】 四、实验总结及心得体会 本次设计中首先要解决的问题是对所做题目的理解。 像银行家算法这一问题,如果单看题目要求往往不知如何下手,更不要谈下一步的设计过程。 但是在看完并理解了ppt之后,就知道要从哪入手,在银行家算法中,重点和难点都是安全性的判断及输出安全序列。 明白了需求,下一个难点是如何通过软件实现。 为了防止死锁,需要进行大量的判断,这也导致了一个问题,即在进行调试时,一旦出现问题,往往难以找到问题所在。 在实现的时候,应该先给他试探性的分配资源,然后再来调用安全性检查函数,否则在调试时会先出现“是否继续? ‘Y’或‘N’”,此时就会出错。 在调试时,我还出现在输入‘Y’后,会异常退出的情况,这时,只要用getchar()就可以解决。 在这次课程设计中,我发现问题,解决问题,虽然也有没有解决的情况,但这让我复习了放下很久的C语言。 总体来说,解决问题的过程中,使我学到了许多平时忽略掉的问题,让我受益匪浅。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 银行家 算法