操作系统课程设计报告题目:银行家算法的模拟实现
专业计算机科学与技术
学生姓名姜雯
班级计算机131
学号1310704112
指导教师韩立毛
完成日期2015.7.10
信息工程学院
目录
1 概述 (2)
1.1 设计目的 (2)
1.2 设计内容 (2)
1.3 设计要求 (2)
2 设计原理 (2)
2.1银行家算法中的数据结构 (2)
2.2 银行家算法应用 (3)
3 设计思路 (4)
4 程序运行调试结果 (5)
4.1程序初始化 (5)
4.2检测系统资源分配是否安全结果 (7)
5 设计小结 (8)
6 参考文献 (8)
附录源程序代码 (9)
题目:银行家算法的模拟实现
1 概述
1.1 设计目的
1.进一步了解进程的并发执行。
2.加强对进程死锁的理解。
3.是用银行家算法完成死锁检测。
1.2 设计内容
给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝(银行家算法)模拟该进程组的执行情况。
1.3 设计要求
1.初始状态没有进程启动;
2.计算每次进程申请是否分配,如:计算出预分配后的状态情况(安全状态、不安全状态),如果是安全状态,输出安全序列;
3.每次进程申请被允许后,输出资源分配矩阵A和可用资源向量V;
4.每次申请情况应可单步查看,如:输入一个空格,继续下个申请。
2 设计原理
2.1 银行家算法中的数据结构
(1)、可利用资源向量Available,这是一个含有m个元素的数组,其中的每个元素代表一类可利用资源的数目,其初始值是系统中所配置的该类全部资源的数目,其数值随该类资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
(2)、最大需求矩阵Max,这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
(3)、分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已经分得Rj 类资源的数目为K。
(4)、需求矩阵Need。这也是一个n*m的矩阵,用以表示每个进程尚需要的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。上
述三个矩阵间存在以下关系:
Need[i,j]=Max[i,j]-Allocation[i,j]
2.2 银行家算法应用
模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成:一是银行家算法(扫描);二是安全性算法。
(1)银行家算法(扫描)
设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Ri 类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:
①如果Requesti[j]<= Need[i,j],便转向步骤2;否则认为出错,因为它所需的资源数已经超过了它所宣布的最大值。
②如果Requesti[j]<= Available[j],便转向步骤3;否则表示尚无足够资源,Pi 需等待。
③系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值。
Available[j]=Available-Requesti[j];
Allocation[i,j]=Allocation[i,j]+Requesti[j];
Need[i,j]=Need[i,j]-Request[j];
④系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来资源的分配状态,让进程Pi等待。
(2)安全性算法
系统所执行的安全性算法可描述如下:
①设置两个向量:一个是工作向量Work;它表示系统可提供给进程继续运行所需要的各类资源的数目,它含有m个元素,在执行安全性算法开始时,work=Availalbe;另一个是 Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=false;当有足够资源分配给进程时,再令Finish[i]=rue;
②从进程集合中找到一个能满足下述条件的进程:
一是Finish[i]==false;二是 Need[i,j]<=Work[j];若找到,执行步骤③,否则,执行步骤④;
③当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]=Work[j]+Allocation[i,j];
Finish[i]=true;
go to step②;
④如果所有进程的Finish[i]==true都满足,则表示系统处于安全状态,否则系统
处于不安全状态。
3 设计思路
1.进程一开始向系统提出最大需求量;
2.进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量;
3.若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待。
银行家算法流程如图16-4所示:
图16-4 银行家算法流程
银行家算法安全检测流程如图16-5所示:
图16-5 银行家算法安全检测流程4 程序运行调试结果
4.1 程序初始化
4.2检测系统资源分配是否安全结果
5 设计小结
“银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过
行家算法的理解,掌握了银行家算法避免死锁的过程和方法,理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能,并在其基础上考虑了输出显示格式的美观性,使界面尽可能友好。并且在编程时将主要的操作都封装在函数中,这样使程序可读性增强,使程序更加清晰明了。在算法的数据结构设计上考虑
作了一些考虑。当然,在编写和调试过程中我遇到了许多的问题,通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多,相信在今后的生活中也有一定帮助。
6 参考文献
[1] 韩立毛,李先锋. 计算机操作系统实践教程[M],南京:南京大学出版社,2011.10.
[2] 严蔚敏,吴伟民. 数据结构[M],北京:清华大学出版社,1997.4
[3] 张尧学,史美林. 计算机操作系统教程[M],北京:清华大学出版社,2000.8.
[4] 孙静宇. 计算机操作系统课程设计指导书[M],山西:太原理工出版社,2006.4.
附录源程序代码
#include
#include
#include
# define m 50
int no1; //进程数
int no2; //资源数
int r;
int allocation[m][m],need[m][m],available[m],max[m][m];
char name1[m],name2[m]; //定义全局变量void main()
{
void check();
void print();
int i,j,p=0,q=0;
char c;
int request[m],allocation1[m][m],need1[m][m],available1[m];
printf("**********************************************\n");
printf("* 银行家算法的设计与实现 *\n");
printf("**********************************************\n");
printf("请输入进程总数:\n");
scanf("%d",&no1);
printf("请输入资源种类数:\n");
scanf("%d",&no2);
printf("请输入Max矩阵:\n");
for(i=0;i for(j=0;j scanf("%d",&max[i][j]); //输入已知进程最大资源需求量 printf("请输入Allocation矩阵:\n"); for(i=0;i for(j=0;j scanf("%d",&allocation[i][j]); //输入已知的进程已分配的资源数 for(i=0;i for(j=0;j need[i][j]=max[i][j]-allocation[i][j]; //根据输入的两个数组计算出need 矩阵的值 printf("请输入Available矩阵\n"); for(i=0;i scanf("%d",&available[i]); //输入已知的可用资源数 print(); //输出已知条件 check(); //检测T0时刻已知条件的安全状态 if(r==1) //如果安全则执行以下代码 { do{ q=0; p=0; printf("\n请输入请求资源的进程号(0~4):\n"); for(j=0;j<=10;j++) { scanf("%d",&i); if(i>=no1) { printf("输入错误,请重新输入:\n"); continue; } else break; } printf("\n请输入该进程所请求的资源数request[j]:\n"); for(j=0;j scanf("%d",&request[j]); for(j=0;j if(request[j]>need[i][j]) p=1; //判断请求是否超过该进程所需要的资源数 if(p) printf("请求资源超过该进程资源需求量,请求失败!\n"); else { for(j=0;j if(request[j]>available[j]) q=1; //判断请求是否超过可用资源数 if(q) printf("没有做够的资源分配,请求失败!\n"); else //请求满足条件 { for(j=0;j { available1[j]=available[j]; allocation1[i][j]=allocation[i][j]; need1[i][j]=need[i][j]; //保存原已分配的资源数,仍需要的资源数和可用的资源数 available[j]=available[j]-request[j]; allocation[i][j]+=request[j]; need[i][j]=need[i][j]-request[j]; //系统尝试把资源分配给请求的进程 } print(); check(); //检测分配后的安全性 if(r==0) //如果分配后系统不安全 { for(j=0;j { available[j]=available1[j]; allocation[i][j]=allocation1[i][j]; need[i][j]=need1[i][j]; //还原已分配的资源数,仍需要的资源数和可用的资源数 } printf("返回分配前资源数\n"); print(); } } }printf("\n你还要继续分配吗?Y or N ?\n"); //判断是否继续进行资源分配 c=getche(); }while(c=='y'||c=='Y'); } } void check() //安全算法函数 { int k,f,v=0,i,j; int work[m],a[m]; bool finish[m]; r=1; for(i=0;i finish[i]=false; // 初始化进程均没得到足够资源数并完成for(i=0;i work[i]=available[i];//work[i]表示可提供进程继续运行的各类资源数k=no1; do{ for(i=0;i { if(finish[i]==false) { f=1; for(j=0;j if(need[i][j]>work[j]) f=0; if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i; //记录安全序列号 for(j=0;j work[j]+=allocation[i][j]; //释放该进程已分配的资源 } } } k--; //每完成一个进程分配,未完成的进程数就减1 }while(k>0); f=1; for(i=0;i { if(finish[i]==false) { f=0; break; } } if(f==0) //若有进程没完成,则为不安全状态 { printf("系统处在不安全状态!"); r=0; } else { printf("\n系统当前为安全状态,安全序列为:\n"); for(i=0;i printf("p%d ",a[i]); //输出安全序列 } } void print() //输出函数 { int i,j; printf("\n"); printf("*************此时刻资源分配情况*********************\n"); printf("进程名/号 | Max | Allocation | Need |\n"); for (i = 0; i < no1; i++) { printf(" p%d/%d ",i,i); for (j = 0; j < no2; j++) {printf("%d ",max[i][j]);} for (j = 0; j < no2; j++) {printf(" %d ",allocation[i][j]);} for (j = 0; j < no2; j++) {printf(" %d ",need[i][j]);} printf("\n"); } printf("\n"); printf("各类资源可利用的资源数为:"); for (j = 0; j < no2; j++) {printf(" %d",available[j]);} printf("\n"); } (程序结束)