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

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

19
2020年4月19日
文档仅供参考，不当之处，请联系改正。

操作系统课程设计

（银行家算法的模拟实现）
一、 设计目的
1、进一步了解进程的并发执行。
2、加强对进程死锁的理解。
3、用银行家算法完成死锁检测。
二、 设计内容
给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。
三、 设计要求
1、初始状态没有进程启动。
2、计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列。
3、每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V。
4、每次申请情况应可单步查看，如：输入一个空格，继续下个申请。
四、 算法原理
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、 银行家算法应用
模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法（扫描）；二是安全性算法。
（1）银行家算法（扫描）
设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
①如果Requesti[j]<=Need[i,j]，便转向步骤②；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。
②如果Requesti[j]<=Allocation[i,j]，便转向步骤③；否则表示尚无足够资源，Pi需等待。
③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。
Available[j]=Available-Requesti[j]；
Allocation[i,j]=Allocation[i,j]+Requesti[j]；
Need[i,j]=Need[i,j]-Requesti[j]；
④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，已完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。
五、 安全性算法
系统所执行的安全性算法可描述如下：
①设置两个向量：一个是工作向量Work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=Available；另一个是Finish；它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true；
②从进程集合中找到能满足下述条件的进程：
一是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都满足，则表示系统处于安全状态，否则系统处于不安全状态。
五、 设计思路
1、进程一开始向系统提出最大需求量；
2、进程每次提出新的需求（分期贷款）都统计是否超出它事先提出的最大需求量；
3、若正常，则判断该进程所需剩余量（包括本次申请）是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。
六、 程序运行调试结果
3、 程序初始化

2、检测系统资源分配是否安全结果

七、 小结
“银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过程中我们遇到过许多问题也学到了很多东西。经过这周的课程设计，我加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。而且在编程时将主要的操作都封装在函数中，这样使程序可读性增强，使程序更加清晰明了。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考了很多网络资料也参考了一些别人写的的程序综合这些算法思想和自己的思路对程序做了很好的设计方式对一些算法的优越性等也作了一些考虑。当然，在编写和调试过程中我遇到了许多的问题，经过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多，相信在今后的生活中也有一定帮助。

附：程序源代码：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
# 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<no1;i++)
for(j=0;j<no2;j++)
scanf("%d",&max[i][j]); //输入已知进程最大资源需求量

printf("请输入Allocation矩阵:\n");
for(i=0;i<no1;i++)
for(j=0;j<no2;j++)
scanf("%d",&allocation[i][j]); //输入已知的进程已分配的资源数

for(i=0;i<no1;i++)
for(j=0;j<no2;j++)
need[i][j]=max[i][j]-allocation[i][j]; //根据输入的两个数组计算出need矩阵的值

printf("请输入Available矩阵\n");
for(i=0;i<no2;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<no2;j++)
scanf("%d",&request[j]);
for(j=0;j<no2;j++)
if(request[j]>need[i][j]) p=1;
//判断请求是否超过该进程所需要的资源数
if(p)
printf("请求资源超过该进程资源需求量，请求失败！\n");
else
{
for(j=0;j<no2;j++)
if(request[j]>available[j]) q=1;
//判断请求是否超过可用资源数
if(q)
printf("没有做够的资源分配，请求失败！\n");

else //请求满足条件
{
for(j=0;j<no2;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<no2;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<no1;i++)
finish[i]=false; // 初始化进程均没得到足够资源数并完成
for(i=0;i<no2;i++)
work[i]=available[i];//work[i]表示可提供进程继续运行的各类资源数
k=no1;
do{
for(i=0;i<no1;i++)
{
if(finish[i]==false)
{
f=1;
for(j=0;j<no2;j++)
if(need[i][j]>work[j])
f=0;
if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程
{
finish[i]=true;
a[v++]=i; //记录安全序列号
for(j=0;j<no2;j++)
work[j]+=allocation[i][j]; //释放该进程已分配的资源
}
}
}
k--; //每完成一个进程分配，未完成的进程数就减1
}while(k>0);
f=1;
for(i=0;i<no1;i++) //判断是否所有的进程都完成
{
if(finish[i]==false)
{
f=0;
break;
}
}
if(f==0) //若有进程没完成，则为不安全状态
{
printf("系统处在不安全状态！");
r=0;
}
else
{
printf("\n系统当前为安全状态，安全序列为：\n");
for(i=0;i<no1;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");
}

（程序结束）