[操作系统]课程设计银行家算法
《操作系统》课程设计
题目:银行家算法
系 别:计算机信息与技术系 专 业:信息管理与信息系统 班 级: 学 号: 学生姓名: 张 伟 指导教师: 张 娟
2014年12月
目录
一 设计目的 ........................................................................................ 3 二 问题描述 ........................................................................................ 3 三 设计思路 ........................................................................................ 3 四 详细设计 ........................................................................................ 4 4.1.进程i发出请求资源申请 ........................................................ 4 4.2安全性检查算法(check()函数) ............................................... 4 五.流程图 ......................................................................................... 5 六 源程序: ........................................................................................ 8 七.程序运行调试结果: ................................................................. 13 7.1.程序初始化 ............................................................................... 13 7.2.检测系统资源分配是否安全结果 ............................................ 13 八 总结 ............................................................................................. 15
一 设计目的
通过设计和调试银行家算法,加深对死锁概念和死锁避免的理解
二 问题描述
在死锁的避免中,银行家算法把系统状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可以避免发生死锁。所谓安全状态,是指系统能按某种顺序为每个进程分配所需资源,直到最大需求,使每一个进程都可以顺利完成,即可找到一个安全资源分配序列。模拟实现这个工作过程。
三 设计思路
我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
3.1 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
3.2 顾客可以分期贷款,但贷款的总数不能超过最大需求量;
3.3 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
3.4 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。
四 详细设计
4.1.进程i发出请求资源申请
4.1.1如果Request [j]
4.1.2如果:Request i[j]
4.1.3若以上两个条件都满足,则系统试探着将资源分配给申请的进程,并修改下面数据结构中的数值:
Available[i,j]= Available[i,j]- Request [j]; Allocation[i][j]= Allocation[i][j]+ Request [j]; need[i][j]= need[i][j]- Request [j];
4.1.4试分配后,执行安全性检查,调用check()函数检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程;否则本次试探分配作废,恢复原来的资源分配状态,让该进程等待。
4.1.5用do{…}while 循环语句实现输入字符y/n判断是否继续进行资源申请。 4.2安全性检查算法(check()函数) 4.2.1设置两个向量:
工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,在执行安全性算法开始时,Work= Available。
工作向量Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=false;当有足够的资源分配给进程时,再令Finish[i]=true。 4.2.2在进程中查找符合以下条件的进程: 条件1:Finish[i]=false; 条件2:need[i][j]
若找到,则执行步骤(3)否则,执行步骤(4)
4.2.3当进程获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
Work[j]= Work[j]+ Allocation[i][j]; Finish[i]=true; goto step (2);
4.2.4如果所有的Finish[i]=true都满足,则表示系统处于安全状态,否则,处于不安全状态。
五.流程图
5.1安全性算法流程图
六 源程序:
程序源代码:
#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(
printf(
printf(
scanf(
printf(
scanf(
for(i=0;i
printf(
print(); //输出已知条件
check(); //检测T0时刻已知条件的安全状态
if(r==1) //如果安全则执行以下代码 {
do{
q=0;
p=0;
printf(
for(j=0;j
scanf(
printf(
else break; }
printf(
scanf(
if(request[j]>need[i][j]) p=1;
//判断请求是否超过该进程所需要的资源数 if(p)
printf(
for(j=0;j
if(request[j]>available[j]) q=1;
//判断请求是否超过可用资源数
if(q)
printf(
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(
}printf(
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)
}
void print() //输出函数
{
int i,j; { f=1; for(j=0;jwork[j]) f=0; if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i; //记录安全序列号 for(j=0;j0); f=1; for(i=0;i
printf(
printf(
{
printf(
for (j = 0; j
{printf(
for (j = 0; j
{printf(
for (j = 0; j
{printf(
printf(
}
printf(
printf(
for (j = 0; j
{printf(
printf(
}
七.程序运行调试结果:
7.1.程序初始化
7.2.检测系统资源分配是否安全结果
八 总结 课程设计是我们专业课程知识综合应用的实践训练,着是我们迈向社会,从事职业工作前一个必不少的过程.”千里之行始于足下”,通过这次课程设计,我深深体会到这句千古名言的真正含义.我今天认真的进行课程设计,学会脚踏实地迈开这一步,就是为明天能稳健地在社会大潮中奔跑打下坚实的基础.
明白了需求,下一个难点是如何通过软件实现。我所做的银行家算法这一题目,为了防止死锁,需要进行大量的判断,这也导致了一个问题,即在进行调试时,一旦出现问题,往往难以找到问题所在,针对这一问题,
通过本次课程设计,我对软件的开发的过程有了较为深入的了解,虽然只是对一个问题的简单模拟,但麻雀虽小五脏俱全,我对相关问题的解决已经有了一定的认识,对软件技术这门课程也有了更为透彻的感悟。本次课程设计,锻炼了我分析问题和解决问题的能力,为今后相关问题的解决积累了宝贵经验,也增强了自己的耐心与自信,受益匪浅。